Rule 30 automaton as hash function - page 5.

grau

hero member

Activity: 836

Merit: 1030

bits of proof

Quote from: Anders on July 27, 2014, 03:00:07 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

Anders

full member

Activity: 126

Merit: 100

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

Anders

full member

Activity: 126

Merit: 100

Quote from: grau on July 27, 2014, 02: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.

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.

grau

hero member

Activity: 836

Merit: 1030

bits of proof

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.

grau

hero member

Activity: 836

Merit: 1030

bits of proof

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

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

Anders

full member

Activity: 126

Merit: 100

Quote from: grau on July 27, 2014, 01: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?

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

Activity: 836

Merit: 1030

bits of proof

Quote from: Anders on July 27, 2014, 01:36:51 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

full member

Activity: 126

Merit: 100

Quote from: grau on July 27, 2014, 01:17:04 AM

Quote from: Anders on July 27, 2014, 01:11:09 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

hero member

Activity: 836

Merit: 1030

bits of proof

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?

grau

hero member

Activity: 836

Merit: 1030

bits of proof

Quote from: Anders on July 27, 2014, 01:11:09 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.

Anders

full member

Activity: 126

Merit: 100

Quote from: grau on July 27, 2014, 12:46:40 AM

Quote from: Anders on July 27, 2014, 12: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:

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

Activity: 836

Merit: 1030

bits of proof

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.

grau

hero member

Activity: 836

Merit: 1030

bits of proof

Quote from: Anders on July 27, 2014, 12: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:

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.

Anders

full member

Activity: 126

Merit: 100

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.

Anders

full member

Activity: 126

Merit: 100

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

full member

Activity: 126

Merit: 100

Quote from: Peter R on July 26, 2014, 08:46:22 PM

I mined my name Cheesy

I noticed that the nonce needs to be on the left side of the message, as the hashing seems much more effective moving to the right than moving to the left (as Grau observed too). So, I think this phenomenon needs to be better understood before you can decide what column to take your hash from and how many rows to calculate.

Nice. So for that smaller hash at least is shows that leading zeros can be achieved with R30. Yes, the right side of the Rule 30 automaton is more chaotic it seems. But did you skip at least 1.5 times the number of bits in the initial condition? That's the smallest number of generations needed for both left and right side to become "blended" back into the center column.

Anders

full member

Activity: 126

Merit: 100

Quote from: grau on July 26, 2014, 03:28:52 PM

Note that computation of the below area is sufficient.

Yes, that area is what is calculated in my Java (and latest JavaScript) version of R30.

Peter R

legendary

Activity: 1162

Merit: 1007

I mined my name Cheesy

I noticed that the nonce needs to be on the left side of the message, as the hashing seems much more effective moving to the right than moving to the left (as Grau observed too). So, I think this phenomenon needs to be better understood before you can decide what column to take your hash from and how many rows to calculate.

grau

hero member

Activity: 836

Merit: 1030

bits of proof

Does not "seem" to hurt.

grau

hero member

Activity: 836

Merit: 1030

bits of proof

Note that R30 has an apparent asymmetry in its "chaos".

The below pictures hint that left and right side of an input do not receive the same "kind" of hashing. Likely irrelevant, but puzzling.

Topic: Rule 30 automaton as hash function - page 5. (Read 10616 times)