This was funny. Suppose you wanted to build a node that linked to itself. You'd have to find a fixed point in the combination of functions that adds other data to the link and hashes it. Finding a fixed point of a hashing function is hard.
This was funny. Suppose you wanted to build a node that linked to itself. You'd have to find a fixed point in the combination of functions that adds other data to the link and hashes it. Finding a fixed point of a hashing function is hard.
Using the big-step, little-step cycle detection algorithm to avoid using gigantic amounts of memory, you're then looking at an average of 1.5 * 2^129 iterations of updating your graph of 256-bit cryptographic hashes in order to discover you've hit a periodic point.
Offhand, I don't know the probability that there's a fixed point for a given starting point for a random mapping of 256-bit values to 256-bit values, but my intuition is that it's vanishingly small. If anyone has an elegant derivation of the probability, I'd love to see it.
This doesn't tell you anything about concentration bounds or whatever, but it's a neat fact nonetheless.
Unfortunately, it's a random mapping, not necessarily a random permutation. An ideal block cipher would be modeled as a random permutation. Though, in this particular case the domain and range are the same, so unless I'm missing something, the expected number of fixed points comes out to 1 by the same reasoning.
Note though that a correct block cipher is necessarily a permutation, because it's invertible (by definition, a permutation is just an invertible mapping with domain and range equal). A hash function on the other hand needn't be a permutation even when you restrict the domain to inputs of the same bit length as the hash output.