3
$\begingroup$

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"?

Improve this question
$\endgroup$
3
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – e-sushi
    Commented Apr 3, 2016 at 19:58
  • $\begingroup$ e-sushi - seems like that chat room doesn't exist.. there was really good information and those comments were from over 2 years ago, is there any way I can recover these? $\endgroup$
    – jaybny
    Commented Jul 12, 2016 at 23:28
  • $\begingroup$ Moderators can "undelete" such rooms, which I've already done while writing this comment. You should be able to view it again (and maybe grab an offline copy of any stuff you might want to keep accessible). $\endgroup$
    – e-sushi
    Commented Jul 12, 2016 at 23:54

3 Answers 3

Reset to default
5
$\begingroup$

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. It 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 crypto-currencies. Typically 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. You cannot have enough iterations to reach an attractor without making the function too costly to compute.

Improve this answer
$\endgroup$
7
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – tylo
    Commented Oct 7, 2014 at 11:12
  • $\begingroup$ It's probably worth noting that there has been some recent progress on hash functions using discrete chaotic iterations. Check out this PDF from 2017 for example. $\endgroup$
    – sfmiller940
    Commented Jan 5, 2019 at 0:35
6
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.