5 ms·
Great visualization. Might become my new screensaver.
by M4tze 5y ago
Great visualization. Might become my new screensaver.
- colejohnson66 5y agoOne could even feed the hash back into itself to get a different result each time
- em3rgent0rdr 5y agohow long would the cycle last before it starts repeating?
- tromp 5y agoOn the order of 2^256 steps, if SHA-256 behaves randomly, since the largest cycle in a random permutation on N elements has expected length ~ 0.62 * N.
- MayeulC 5y agoThen wouldn't that be 0.62*2^256, closer to 2^255 ? Not that it makes a notable difference: at 1 fs per step (1000 GHz, or 1 TH/s), that would take about 4.5e65 years to happen. The universe is only about 1e10 years old...
- tromp 5y agoIt would be at least that, with a smaller contribution to the expectation from smaller cycles. That's why I said "on the order of", i.e. not much smaller.
- pbsd 5y agoSHA-256 is not a permutation; the expected cycle length is ~2^128. It's how collisions are (generically) found.
- colejohnson66 5y agoPigeonhole principle?
- pbsd 5y agoEach new output value i can collide with output 1, 2, ..., i-1. So the collision probability of iteration i is (i-1)/2^256. Adding all of the iterations up you have 1/2^256 + 2/2^256 + ... + (i-1)/2^256 = 0.5 i (i-1)/2^256 which approaches 1/2 as you get to 2^128. In reality you use some variant of Rho which does not store every previous value but uses something like Floyd's cycle detection or distinguished points and requires minimal storage, at the cost of some extra hash computations but still on the order of 2^128.
- dragontamer 5y agoThis situation calls for Birthday paradox, not pigeon hole.
- deleted 5y ago[deleted]