Bitcoin Forum
September 16, 2024, 12:10:13 PM
 News: Latest Bitcoin Core release: 27.1 [Torrent]
 Home Help Search Login Register More
 Pages: 1 2 3 [4] 5 6 7 8  All
 Author Topic: Rule 30 automaton as hash function  (Read 10607 times)
Anders (OP)
Full Member

Offline

Activity: 126
Merit: 100

 Re: Rule 30 automaton as hash function July 27, 2014, 04:23:29 AM

The right side of the automaton is where the "randomness" is so the right value in blue needs to be mixed back into the center column:

Anders (OP)
Full Member

Offline

Activity: 126
Merit: 100

 Re: Rule 30 automaton as hash function July 27, 2014, 04:45:58 AM

The same with the leftmost value in the initial condition. It needs to become "randomized" in the right side of the automaton and then brought into the center column. Otherwise the hash values will be similar for similar messages. This means 1.5 N rows where N is the number of bits in the initial condition.

grau
Hero Member

Offline

Activity: 836
Merit: 1030

bits of proof

 Re: Rule 30 automaton as hash function July 27, 2014, 04:46:40 AM

The right side of the automaton is where the "randomness" is so the right value in blue needs to be mixed back into the center column:

Excuse, but that sounds arbitrary to me.
I am looking for the least complex but irreducible hash, and am not convienced that "mixing back" would be needed.

grau
Hero Member

Offline

Activity: 836
Merit: 1030

bits of proof

 Re: Rule 30 automaton as hash function July 27, 2014, 05:07:42 AM

You see below that the hash is already part of the right side of an R30 evolution and that every bit of it has input from every bit of the value to be hashed.

Anders (OP)
Full Member

Offline

Activity: 126
Merit: 100

 Re: Rule 30 automaton as hash function July 27, 2014, 05:11:09 AM

The right side of the automaton is where the "randomness" is so the right value in blue needs to be mixed back into the center column:

Excuse, but that sounds arbitrary to me.
I am looking for the least complex but irreducible hash, and am not convienced that "mixing back" would be needed.

I added this to the R30 Wiki page:

"The right side of the Rule 30 cellular automaton has chaotic behavior while the left side shows regularities. This means that the leftmost bit value in the initial condition needs to reach the right side and then back into the center column, which requires at least 1.5 N rows calculated before the hash value is extracted, where N is the number of bits in the initial condition." -- https://code.google.com/p/r30-hash-function/wiki/R30HashFunction

You can try with 0.5 N which is the value needed for both left and right side of the initial condition to reach the center column. The hash values then become poor with similar messages producing similar hashes, without enough randomness needed for well approximation of a random oracle.
grau
Hero Member

Offline

Activity: 836
Merit: 1030

bits of proof

 Re: Rule 30 automaton as hash function July 27, 2014, 05:17:04 AM

You can try with 0.5 N which is the value needed for both left and right side of the initial condition to reach the center column. The hash values then become poor with similar messages producing similar hashes, without enough randomness needed for well approximation of a random oracle.

I have not seen the proof for above, yet. It is only your intuition against mine.
grau
Hero Member

Offline

Activity: 836
Merit: 1030

bits of proof

 Re: Rule 30 automaton as hash function July 27, 2014, 05:32:04 AM

It appears that neither of us had the right intuition. I plotted the effect of a bit on the outer right side. The question is: What is the slope of the yellow line?

Anders (OP)
Full Member

Offline

Activity: 126
Merit: 100

 Re: Rule 30 automaton as hash function July 27, 2014, 05:36:51 AM

You can try with 0.5 N which is the value needed for both left and right side of the initial condition to reach the center column. The hash values then become poor with similar messages producing similar hashes, without enough randomness needed for well approximation of a random oracle.

I have not seen the proof for above, yet. It is only your intuition against mine.

Here is a hash function with 0.5 N: http://jsfiddle.net/UQ6B7/

Examples of poor hash values with 0.5 N:

Compare with R30:

 Message Hash value aaaaaaaaaaaaaaaaaa 1e37052faef1bbd9c866c69a246ee30536f9b68133e5101ea7f290b630303138 aaaaaaaaaaaaaaaaab c3e18cc8fea420228257228e7ef0a0addc4554130b343d5f43d5e1dcb47dff0e aaaaaaaaaaaaaaaaac ceb9bbf637b3cfe0383a2b2c6c67cc0174946e5387a6fa136290dac8f71dfa68 aaaaaaaaaaaaaaaaad 98feb474ede682559e459ceaae5518563fabdb3b06da4a488f46069750730877 aaaaaaaaaaaaaaaaae 980eaf332cf1222f82052e23d535a551793971725362acb7a192e0afa9243957

Yikes! It seems that 2.5 N is too small value too. Hmm... The chaotic mixing of Rule 30 needs to be better understood.

grau
Hero Member

Offline

Activity: 836
Merit: 1030

bits of proof

 Re: Rule 30 automaton as hash function July 27, 2014, 05:41:56 AM

Yikes! It seems that 2.5 N is too small value too. Hmm... The chaotic mixing of Rule 30 needs to better understood.

Exactly. See the slope question I raised before.
Anders (OP)
Full Member

Offline

Activity: 126
Merit: 100

 Re: Rule 30 automaton as hash function July 27, 2014, 05:42:07 AM

It appears that neither of us had the right intuition. I plotted the effect of a bit on the outer right side. The question is: What is the slope of the yellow line?

Interesting. The area on the right seems to be the chaotic part. And the slope at a steeper angle than 45 degrees. See my previous post where it seems that I was wrong about 2.5 N.
grau
Hero Member

Offline

Activity: 836
Merit: 1030

bits of proof

 Re: Rule 30 automaton as hash function July 27, 2014, 05:58:25 AM

Here you are from Wolfram, "Sensitivity to initial conditions"

https://www.wolframscience.com/nksonline/page-251?firstview=1
grau
Hero Member

Offline

Activity: 836
Merit: 1030

bits of proof

 Re: Rule 30 automaton as hash function July 27, 2014, 06:25:17 AM

I run quite a few initial conditions to see that the slope is far from trivial, see example:

I see no safe lower bound for the slope yet.

Anders (OP)
Full Member

Offline

Activity: 126
Merit: 100

 Re: Rule 30 automaton as hash function July 27, 2014, 07:00:07 AM

I run quite a few initial conditions to see that the slope is far from trivial, see example:

I see no safe lower bound for the slope yet.

Wow. That's pretty nonlinear. Maybe my initial value of 4N is needed after all. Then the hash value will be taken from below where the slope crosses the center column. Unless the slope can bend nonlinearly the other way in some extreme ways. Tricky.
Anders (OP)
Full Member

Offline

Activity: 126
Merit: 100

 Re: Rule 30 automaton as hash function July 27, 2014, 08:54:01 AMLast edit: July 27, 2014, 09:38:50 AM by Anders

The influence of the right side bit may look nonlinear yet the mixing of cell values is actually a linear process. The bits have influenced each other fully first at the blue lines. And then those values need to reach the center column, which means 2.5 N.

In my previous version I started the automaton at the message bits. It should start with the whole initial condition which includes the concatenated length bits, like this: http://jsfiddle.net/74TNa/

This version with 2.5 N produces better hash values:

 Message Hash value aaaaaaaaaaaaaaaaaa e43391dfc7da619e4639a6f0b46559772f39ac7b4d258dd60f5652226a550822 aaaaaaaaaaaaaaaaab 42bec61717e9f484b29653b5da5e0060f00bf41516e007440644e8df1d9aec94 aaaaaaaaaaaaaaaaac 5282f5d32d100117b0c5a05a8ae5994e6d36d32e7445003aca97830516b9177c aaaaaaaaaaaaaaaaad 2f11a9e1094d1b5982f97405b4aa1c015dce940fc25fd81935bee5c6ec7ad7ae aaaaaaaaaaaaaaaaae 375bc9e8757b2b1840408532b992bde636272025e43d7a1e95cf07b0512747c5
grau
Hero Member

Offline

Activity: 836
Merit: 1030

bits of proof

 Re: Rule 30 automaton as hash function July 27, 2014, 09:10:21 AM

Wow. That's pretty nonlinear. Maybe my initial value of 4N is needed after all. Then the hash value will be taken from below where the slope crosses the center column. Unless the slope can bend nonlinearly the other way in some extreme ways. Tricky.

In degenerate cases you would even need 5N, see below for 010101... initial conditions
grau
Hero Member

Offline

Activity: 836
Merit: 1030

bits of proof

 Re: Rule 30 automaton as hash function July 27, 2014, 09:16:38 AM

It should start with the whole initial condition which includes the concatenated length bits

Sounds alchemy. You just hope that length in binary representation is not a specific pattern as above.
Anders (OP)
Full Member

Offline

Activity: 126
Merit: 100

 Re: Rule 30 automaton as hash function July 27, 2014, 09:44:55 AM

It should start with the whole initial condition which includes the concatenated length bits

Sounds alchemy. You just hope that length in binary representation is not a specific pattern as above.

The length bits are only there to make distinctions between messages that otherwise would produce only zeros or messages that end with zeros which would give identical initial conditions without the length bits. So the length bits must be included. And the initial condition includes those length bits. In my previous version I added the length bits without including them in the number of bits of the initial condition.
grau
Hero Member

Offline

Activity: 836
Merit: 1030

bits of proof

 July 27, 2014, 09:55:48 AM

The length bits are only there to make distinctions between messages that otherwise would produce only zeros or messages that end with zeros which would give identical initial conditions without the length bits. So the length bits must be included. And the initial condition includes those length bits. In my previous version I added the length bits without including them in the number of bits of the initial condition.

I do not care of a variable length message, but am looking for the least complex irreducible computation hash for a block header. Message wrapping should be in an other logical layer either.

Here is what I get for a special pattern 80 byte input attempting to produce 32 bytes of hash after 5N length. It still fails.

Anders (OP)
Full Member

Offline

Activity: 126
Merit: 100

 Re: Rule 30 automaton as hash function July 27, 2014, 10:07:28 AM

The length bits are only there to make distinctions between messages that otherwise would produce only zeros or messages that end with zeros which would give identical initial conditions without the length bits. So the length bits must be included. And the initial condition includes those length bits. In my previous version I added the length bits without including them in the number of bits of the initial condition.

I do not care of a variable length message, but am looking for the least complex irreducible computation hash for a block header. Message wrapping should be in an other logical layer either.

Here is what I get for a special pattern 80 byte input attempting to produce 32 bytes of hash after 5N length. It still fails.

Ok, good point. The worst case pattern needs to be identified, and then the number of rows needed for that pattern. I tested with messages UUUUUU... for which I needed 7N before the hash values started to become different! (U = ASCII 0x55 = 01010101)
grau
Hero Member

Offline

Activity: 836
Merit: 1030

bits of proof

 Re: Rule 30 automaton as hash function July 27, 2014, 10:10:00 AM

It seems 7 is the bare minimum for a setup like in Bitcoin 80 bytes -> 32 bytes hash.

 Pages: 1 2 3 [4] 5 6 7 8  All