Rule 30 automaton as hash function

[Anders]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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

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

[grau]

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]

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]

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]

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]

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]

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]

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]

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]

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