The quick and easy part of bitcoin mining is checking the digital signatures of those spending their coins and then confirming that there hasn't been a double spend. Then comes the slow part. Miners guess a value for a number known as a nuance and then take the (Sha256) Hash of the verified transactions and the nuance. If the result is less than the currently specified threshold, then the miner can announce his block to the community. The vast majority of the nuances guessed lead to a hash that is greater than then threshold and so are rejected.
Miners seek a number called a nuance such that
\[Hash( transactions, nuance) < threshold \]
When the nuance is found, it represents proof that the mining community has done a lot of work. This approach is known as a proof of work algorithm.
Well, suppose someone were to invert the Hash function, they would start with say (threshold - 1) and then work out the nuance that would achieve that. So they could mine bitcoin without doing the work. Bitcoin would be unable to continue using the proof of work algorithm and would very likely collapse. For bitcoin to survive it is important that no one known has to invert the hash function.
The Hash function that bitcoin uses is called Sha256. (For details look at the
wikipedia article).
For the rest of this blog post, I'm going to focus on the part of the algorithm where we start with 512 bits, they are processed through 16 preliminary iterations and then a further 48 standard iterations, at the end of which we have 256 output bits. The algorithm has the following attributes:
- It is not a secret, anyone who wants can look at the code or indeed write their own code to implement it.
- It is completely deterministic and repeatable. It gives the same answer every time.
- There are no 'if' statements.
One of the operations carried out is integer addition. The inputs are put into groups of 32 bits and then the 32 bits are treated as an integer. Pairs of integers are added. If we go down a level from the integer to the bits that make it up, we can implement the integer addition using the AND operator and an XOR operator on pairs of bits.
The rest of the algorithm can be implemented using:
NOT operator, which takes one bit as an input and has one output bit.
XOR operator, which takes two bits as input and has one output bit.
AND operator, which takes two bits as input and has one output bit.
So the entire algorithm can be represented as a directed graph going from the 512 input nodes to the 256 output nodes. Every node represents one bit. The inputs bits are set and then after that every other node is assigned a value of either 0 or 1. A node is assigned a value just once.
If a NOT operator was used to assign the value, then it has one precedent.
On the other hand if an AND or XOR operator is used then it will have 2 precedents.
However nodes can have any number of dependents. The graph is strictly directed. There are no circular loops.
So now we might ask the question: how might someone invert this algorithm. Suppose the output was fixed or indeed constrained, how could we find appropriate inputs?
Well, lets start with the NOT operator.
This is very straight forward to invert. Indeed if you apply the NOT operator to the output, then you'll recover the input.
Now lets move on to the XOR operator. It is also known as the 'exclusive or'. A XOR B is A or B but not both.
| Input A | Input B | A XOR B |
| 1 | 1 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
Suppose: A XOR B = 0
that means that A and B are the same. They could both be 1 or both be 0. We just know that they are not different. So if we are traversing our graph from the outputs to the intputs, (i.e. from right to left in the image above) then A XOR B = 0 imposes the simple relationship between A and B that A=B.
On the other hand: A XOR B = 1
tells us that A and B are different. So if we go from right to left across our graph then that condition needs to be maintained.
So the XOR output will tell us if the inputs are the same or different.
The final operator we need to deal with is the AND operator.
| Input A | Input B | A AND B |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 0 |
When A AND B = 1,
that implies that both A and B are 1 and so if we have that condition, then we can take a step back through the graph and set the two inputs to 1.
A more difficult case to deal with is: A AND B = 0
In that case either A or B could be 1, but not at the same time.
So that relationship between A and B is (a little bit) complicated.
The Sha256 algorithm consists of 64 iterations ( 16 preliminary, followed by 48 standard). However on each iteration the bits pass through numerous NOT, XOR and AND operators.
In my implemenetation in Java
(which is available in github)
I had:
NOT operator called 117,248 times.
XOR operator called 58,880 times.
AND operator called 106,240 times.
There are a number of ways those numbers could be reduced. For example we could use an OR operator. But if someone was trying to come up with an algorithm to invert the Sha256, then introducing new operators may make it more complicated. Indeed we could replace the XOR with 5 calls to an AND so then we just have lots of AND's and NOT's to invert.
To successfully invert the Sha256, the run time should not grow exponentially with the number of operators N. Something linear in N would be great. Something quadratic in N may be doable.
One method that might be tried would be a probabilistic approach, assigning each node a value between 0 and 1 (inclusive).
For example if we had: A AND B = 0
then we might set A =1/3 and B=1/3.
Reflecting the fact that they are both more likely to be zero than 1.
We could attempt to traverse the graph from right to left and back again a number of times until we had a stable solution. Perhaps a simulated anealing method could be tried. But the problem is that the values in the graph are not stable. One flipped input bit has a huge cascade effect through the graph. It would be very difficult to get a probabalistic method to work because of that instability.
A very different way of trying to reverse it would be to bring the constraints on the nodes through the graph from the outputs back to the inputs. For example if an output needs to be 0 and it is assigned using an AND operator then we know that the two inputs cannot both be 1. We could then pass that constraint back to their precedents.
However in this case if we are not clever then the constraints would grow exponentially as we go back through the graph. If a node has some contraints, then they are passed on to its two precedents, in many cases each of which will have 2 precedents, which in turn may have 2 precedents. Typically to pass from the outputs to the inputs, bits need to pass through 200 AND operators. \(2^{200}\) is a very big number. Someone would need to be very smart in how they compress the constraints to prevent the exponential explosion.
If we observe the Sha256 calculator as it goes from the input to the outputs we find we just need 512 currently live nodes (bits). After a while the inputs are no longer needed. Later, after the intermediate nodes are used, they too are no longer needed. 512 is a comparatively small number. Similarly, someone going back through the graph (from the outputs to the inputs) just needs to keep track of 512 bits at any given point in time. That's not a lot of memory. How difficult could it be to invert the Sha256?
Well, so far no-one has been able to work out how to do it...
We can see that \(z^z\) decreases in the range 0 to 1/e, after that it increases and keeps on increasing. So for positive z, we will have a maximum of two solutions to \( z^z = k\), where k is some constant. We have two solutions already, so we now know there aren't any more,
