Anders (OP)


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)


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


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


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)


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/r30hashfunction/wiki/R30HashFunctionYou 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


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


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)


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: Message  Hash value  aaaaaaaaaaaaaaaaaa  f257274bd5c24f00b46718fd1ca4eba7b4f9cb6e2ad6ad1e37052faef1bbd9c8  aaaaaaaaaaaaaaaaab  f257274bd5e2439806662c8974ba0ce0466179da04755ec3e18cc8fea4202282  aaaaaaaaaaaaaaaaac  f257274bd5c24f00b467187d070bf196aecffa11f0d27bceb9bbf637b3cfe038  aaaaaaaaaaaaaaaaad  f257274bd5c24f00b467187d070bf196aecffa0df0d27b98feb474ede682559e  aaaaaaaaaaaaaaaaae  f257274bd5e24300b467187d070bf196aecffa0df0d27b980eaf332cf1222f82 
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


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)


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


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)


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)


July 27, 2014, 08:54:01 AM Last 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


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


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)


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


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)


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


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.




