# Are hash functions chaotic?

I'm looking into "bitcoin like" mining processes. Say a security process uses a hash of data as proof that the data was known at some point in time.

From what I understand, hash functions are pseudorandomly generated based on the initial seed (the raw data).

If the hash function is chaotic, then the seed data should have strange attractors. If so, then I may be able to map a seed to its attractor and "pre-mine" using attractor buckets.

Are these pseudorandom functions deterministic chaotic systems?

-
"chaos", "deterministic chaos" - that's not a useful concept in crypto (they're buzzwords). Anyway, you haven't defined those terms. I suggest you edit your question to provide a precise technical definition of what you mean by chaos, and what the motivation/context for the question is, and what problem you're actually trying to solve. –  D.W. May 12 at 22:14
its not a buzzword at all. "Small differences in initial conditions (such as those due to rounding errors in numerical computation) yield widely diverging outcomes for such dynamical systems, rendering long-term prediction impossible in general.[1] This happens even though these systems are deterministic, meaning that their future behavior is fully determined by their initial conditions, with no random elements involved.[2] In other words, the deterministic nature of these systems does not make them predictable.[3][4] This behavior is known as deterministic chaos, or simply chaos. " –  jaybny May 12 at 22:17
Again, I suggest you edit your question to try to provide a precise technical definition. You might start by quantifying what "small" means in this context, and what you mean by a "difference", and what you mean by "initial conditions", in this specific context. If you can't do that.... you might want to re-think your "not a buzzword" stance. This site is best used for well-posed technical questions, not for open-ended or subjective discussions, so it's important to spend a lot of thought into how to frame a precise technical question. –  D.W. May 12 at 22:20
for example a tent map is chaotic. en.wikipedia.org/wiki/Tent_map –  jaybny May 12 at 22:23
@jaybny: I have done quite a bit of work with fractals, and noise functions (though not at a technical level suitable for answering on this site). I have come to the conclusion that although some of the internals of hash functions share concept names with complexity and chaos theories, such as non-linearity, these things are not really the same, and it is not necessarily that useful to import those ideas here. Although it is possible to import the maths from the chaotic systems - for instance the population size model in chaotic region could make a random number generator (probably poor). –  Neil Slater May 13 at 7:40

No. That's not going to help you. The cycle structure of a random function is well-studied, and it doesn't help you break hash-chaining, "proof-of-work", Bitcoin, etc. Crypto schemes already take into account the structure of (the graph of) a random function. It's not going to help you "pre-mine" and get some speedup on breaking Bitcoin (for instance).

For instance, the graph of a random function $\{0,1\}^n\to \{0,1\}^n$ typically has the following form: there is a single large cycle of length $\Theta(2^{n/2})$, such that most inputs eventually lead to the cycle. Starting from a random input, the length of the path that leads to that large cycle is typically $\Theta(2^{n/2})$. This does not break standard schemes for hash-chaining, proof-of-work, Bitcoin, etc., as the parameters for their hash function is chosen to take this structure into account.

Whether you want to count this as "chaos" depends upon your precise definition of "chaos", which you haven't provided in the question. Anyway, from a technical/scientific/engineering perspective, what label we assign it (chaos or not) is less important than the technical properties it provides and the security goals it can help to protect.

-

There are many papers about chaos based hash functions but as far as I know none of them is used in commercial applications. Because there are problems with chaos based cryptography schemes. The most important one is the most challenging. There is no chaos in digital systems. Chaos is defined on continous spaces. Therefore, it is a very rare chance that your pseudorandom numbers are produced by a chaotic system. So most probably you won't encounter strange attractors from your pseudorandom sequence. Proper hash functions depend on more reliable algorithms.

-
I feel, the aspect of discrete vs continuous goes even further: Chaotic systems often stem from systems with unstable differential equations, combined with uncountable numbers like reals and (for actual experiments) the uncertainty principle. All this is absent in finite algebraic structures. –  tylo Oct 7 at 11:12

In chaos theory the defining attribute of a chaotic system is that small changes in the starting state tend to compound. If you look at the internal round structure of many hash functions, you will see a similar phenomenon: a single bit's change in the input will spread more and more evenly to all the state bits as you go through the rounds, until it is (assumed to have) evenly spread to all the bits.

If you iterate further, taking a hash of a hash etc., you would eventually find attractors. Both fixed points and cycles are possible. However, the mathematical structure of a hash function has been designed to resist analysis trying to find these attractors and the time to find them or end up in them by brute force is huge for secure-sized hash functions. If would on average take approximately $2^{n/2}$ iterations to end up in a cycle.

Now, those attractors do not matter in the least for most applications of hash functions, including the proof of work used in cryptocurrencies. Only one or two iterations of the hash function are used in the proof of work. The output image of a 256-bit hash only loses around a bit of its size from two iterations, so it is nowhere near to getting to those attractors.

-