Topic: Rule 30 automaton as hash function - page 4. (Read 10616 times)
Fewest calculations so far and with 7N: http://jsfiddle.net/34FyH/
But how to prove that 7N is enough mathematically? 
We enumerated all three bit patterns and 7N is enough to propagate any change to the middle column, even in worst case pattern. A pattern with repetition cycle of more than 3 bits or a random pattern must start local triangles that propagate at a higher slope than the worst case two bit pattern 01010 ...
Is this enough?
Well, enough for what? I think we should first be clear of properties needed for the purpose of block header hashing.
My take is:
- no known inverse - Wolfram demonstrated nicely that the middle column gives no clue of the input after a few generations.
- full propagation - the nonce should be able to flip any bit in the hash - we think given with 7N generations.
- proof of work - means no shortcuts, irreducible, given more clearly than in SHA256
- able to meet any difficulty target - thats a hard question, but did someone prove it for SHA256d? I think not. If there was an attempt to prove this, it would be easier for this one.
did I missed some?
I don't believe it's a requirement to select the hash bits from the central column (although I realize that this is what Mathematica does with Random[]). Given the fact that the influence of the nonce propagates better moving right than moving left, I think it makes sense to select a column to the right of center. If your example image (nice graphics BTW) shows the worst case propagation, then perhaps this is sufficient:
But how to prove that 7N is enough mathematically?
We enumerated all three bit patterns and 7N is enough to propagate any change to the middle column, even in worst case pattern. A pattern with repetition cycle of more than 3 bits or a random pattern must start local triangles that propagate at a higher slope than the worst case two bit pattern 01010 ...
Is this enough?
Well, enough for what? I think we should first be clear of properties needed for the purpose of block header hashing.
My take is:
- no known inverse - Wolfram demonstrated nicely that the middle column gives no clue of the input after a few generations.
- full propagation - the nonce should be able to flip any bit in the hash - we think given with 7N generations.
- proof of work - means no shortcuts, irreducible, given more clearly than in SHA256
- able to meet any difficulty target - thats a hard question, but did someone prove it for SHA256d? I think not. If there was an attempt to prove this, it would be easier for this one.
did I missed some?
Tell me I'm not the only one who initially misread this headline and imagined something completely different...
- has constant memory requirement, that is just two arrays one of the current and one for next generation of the evolution,
Actually, I use only one array for the cellular automaton in my implementation. I save a single value in a temporary variable, then write the result of the next generation into the array, and for the next calculation I use the temporary variable instead of the value in the array, iterated from left to right for all the cells.
I do not think such algorithm should be optimised for space, rather time. Yours is rather sub-optimal doing everything sequentially although substitutions are independent and not using that even in software operating on bit arrays is faster than on individual bits. I think I will write one that beats this with a few magnitudes for fun
Later today .. now I rather play with the kids.
Yes, definitely. The memory requirement is tiny. Then two arrays may be faster. And also to calculate with for example 16-bit words instead of 1 bit at a time as I do now.
If you want to compare the hash values, use my latest version 7N and with reversed bits (the least significant bit for each byte in the message now starts from the left in the automaton): http://jsfiddle.net/MA3vS/
Fortunately it seems that 7N is enough. I tested with messages of length 100,000 bits:
The R30 hash for "UUU...U" is: e4ebe82d717cf60eb6b7d6473f647d733fb0efbfe930bd3048bb14b0cbe7e97f
The R30 hash for "UUU...V" is: 0f821effa4773fdbbe6d7a8c50bd2146c0fe75e577fab0d59dd57c8aa582ba78
But how to prove that 7N is enough mathematically?
The R30 hash for "UUU...U" is: e4ebe82d717cf60eb6b7d6473f647d733fb0efbfe930bd3048bb14b0cbe7e97f
The R30 hash for "UUU...V" is: 0f821effa4773fdbbe6d7a8c50bd2146c0fe75e577fab0d59dd57c8aa582ba78
But how to prove that 7N is enough mathematically?
- has constant memory requirement, that is just two arrays one of the current and one for next generation of the evolution,
Actually, I use only one array for the cellular automaton in my implementation. I save a single value in a temporary variable, then write the result of the next generation into the array, and for the next calculation I use the temporary variable instead of the value in the array, iterated from left to right for all the cells.
I do not think such algorithm should be optimised for space, rather time. Yours is rather sub-optimal doing everything sequentially although substitutions are independent and not using that even in software operating on bit arrays is faster than on individual bits. I think I will write one that beats this with a few magnitudes for fun
Later today .. now I rather play with the kids.
- has constant memory requirement, that is just two arrays one of the current and one for next generation of the evolution,
Actually, I use only one array for the cellular automaton in my implementation. I save a single value in a temporary variable, then write the result of the next generation into the array, and for the next calculation I use the temporary variable instead of the value in the array, iterated from left to right for all the cells.
It seems the 0,1,0,1 ... and 1,0,1,0 ... two bit patterns are the worst case that need >7N evolutions.
And there is a corner case of 0,0,0 ... hat leads to a hash of 0,0,0....
And there is a corner case of 0,0,0 ... hat leads to a hash of 0,0,0....
I think 7N is enough. I tried up to 15,360 bits and it works, with different hash results for UUUU...U and UUUU...V. It also works when changing the start of the message to VUUU...U.
R30 with 7N: http://jsfiddle.net/2Mxt2/
The case with all zeros is taken care of by the extra bits for the length of the message. It's only the empty message '' that results in hash value zero.
I have no idea of hardware design, but guess that the whole net could be laid out as is without a memory, it would just need exact clocking.
With such hash function:
- the work needed is exactly quantified by number of logical operations, no implementation specific gimmicks.
- units implementing rule 30 are identical and utmost simple
- all units can run in parallel for a single layer
- has constant memory requirement, that is just two arrays one of the current and one for next generation of the evolution,
- irreducibility of computation could be rigorously proven
Its single parameter is the number of evolutions before emitting the hash.
This parameter should be set >= 7 times input width.
- the work needed is exactly quantified by number of logical operations, no implementation specific gimmicks.
- units implementing rule 30 are identical and utmost simple
- all units can run in parallel for a single layer
- has constant memory requirement, that is just two arrays one of the current and one for next generation of the evolution,
- irreducibility of computation could be rigorously proven
Its single parameter is the number of evolutions before emitting the hash.
This parameter should be set >= 7 times input width.
It seems the 0,1,0,1 ... and 1,0,1,0 ... two bit patterns are the worst case that need >7N evolutions.
And there is a corner case of 0,0,0 ... hat leads to a hash of 0,0,0....
And there is a corner case of 0,0,0 ... hat leads to a hash of 0,0,0....
It seems 7 is the bare minimum for a setup like in Bitcoin 80 bytes -> 32 bytes hash.
I got 7 too by trial and error. But is that the worst case pattern? And what about the leftmost value?
Thats the beauty of the minimum design. One can enumerate all patterns to figure the worst case, since inputs are only 3 bit wide there are only 8 possible patterns.
The leftmost must be fine.
Actually there are 2 2 bit patters in addition 0,1,0,1 ... and 1,0,1,0... so we have 10 cases.
It seems 7 is the bare minimum for a setup like in Bitcoin 80 bytes -> 32 bytes hash.
I got 7 too by trial and error. But is that the worst case pattern? And what about the leftmost value?
Thats the beauty of the minimum design. One can enumerate all patterns to figure the worst case, since inputs are only 3 bit wide there are only 8 possible patterns.
The leftmost must be fine.
It seems 7 is the bare minimum for a setup like in Bitcoin 80 bytes -> 32 bytes hash.
I got 7 too by trial and error. But is that the worst case pattern? And what about the leftmost value?
It seems 7 is the bare minimum for a setup like in Bitcoin 80 bytes -> 32 bytes hash.
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)
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.
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.
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.
Jump to: