What’s the Proof of Work algorithm?

One of the technologies on which cryptocurrencies like Bitcoin are based is an algorithm called Proof-Of-Work (POW), but what is it exactly ?

Hash function

To thoroughly understand how the Proof-Of-Work can keep the Bitcoin network safe and secure, we need to take a look at its main component, the hash function. The hash function can be compared to a box that blends and mixes whatever you put in it (input) and gives back a fixed-size value (output).
There are different types of hash functions, but most of them have the following characteristics:

  1. Regardless of the input dimention, the output will always have the same size. For example, SHA-256 (the hash function used for Bitcoin) has a 256-bit output. This means that an infinite amount of input values can generate the same output value, but if the set of possible output values is large enough, finding two identical values will be practically impossible. Some hash functions, though, have actually turned out to be vulnerable to this kind of attack, which is called collision attack (MD5 for example).
  2. Based on the output, it’s impossible to infer the input that generated it, unless you try out all the possible combinations.
  3. A slight change in the input value totally changes the output value. Based on 2 output values, it’s impossible to infer that their corresponding inputs are similar.
  4. It’s impossible to find two input values that will generate an identical output value.

Let’s see some examples of hash SHA-256:

sha256(“https://www.cryptoitalia.org”) = 1.140285 e+76
sha256(“cerutti gino”) = 3.372745e+76
sha256(“Cerutti Gino”) = 1.062060e+77

In the three examples above, we have changed the size and the content of the input given to the SHA256 function and the function has given us back three simple numbers (expressed here in scientific notation).

Notice that we could have fed the function a whole Encyclopedia and the result would have still been indistinguishable from the other ones.

Puzzle Friendliness

Let’s consider the following challenge: in a group competition the winner will be the one who can find a second word to append to the string “Cerutti Gino” so that its hash value is smaller than 1.0e+76. The possible solutions to this quiz are infinite, but the only way to find one (as we said, it’s impossible to infer an input from its output) is to try out different options until we find a satisfying result. For example, by adding numbers we obtain the following results (here you can find a simple ruby script to reproduce this result):

sha256(“Cerutti Gino”) = 1.062060e+77
sha256(“Cerutti Gino 0”) = 3.513323e+76
sha256(“Cerutti Gino 1”) = 7.238681e+75
sha256(“Cerutti Gino 2”) = 1.148018e+77
sha256(“Cerutti Gino 3”) = 1.155217e+77
sha256(“Cerutti Gino 4”) = 1.618563e+76
sha256(“Cerutti Gino 5”) = 1.011127e+77
sha256(“Cerutti Gino 6”) = 1.155818e+77
sha256(“Cerutti Gino 7”) = 2.284173e+76
sha256(“Cerutti Gino 8”) = 7.995554e+76
sha256(“Cerutti Gino 9”) = 7.452182e+76
sha256(“Cerutti Gino 10”) = 1.056836e+77

The winning ticket is the one containing the value “Cerutti Gino 1”. Notice that the smaller is the limit that we set as the threshold below which our output needs to be, the harder it is to find a valid solution. The limit is searching for a value of 0, which would imply the violation of rule #4 (which we mentioned above).

POW for Bitcoin

For Bitcoin, the input of the hash function is nothing but the header of a block, which also contains a memory space called nonce. This value is what miners modify to look for a combination that will generate a hash with a smaller value than the one specified in nBits (which is still contained in the header) and which is based on the network difficulty.
The Bitcoin network requires today such small output values that miners are working at a pace of about 8,464,247,238,000,000,000 hash per second.

Adjusting the difficulty

In the example above, we have established as valid any output whose resulting hash has a smaller value than 1.0e+76. In order to keep up with the constant generation of 6 blocks per hour, the Bitcoin network regularly modifies this value. The parameter from which the new value of the puzzle is deduced is called difficulty and it changes every 2016 blocks. The new difficulty is calculated based on the amount of time that has been required to generate these 2016 blocks and then changing the previous value accordingly. For example, if the hash power has increased by 10%, we should expect about 6.6 blocks per hours instead of 6, so the algorithm has to increase the difficulty and decrease the threshold value of the puzzle.

Why do we need the POW for Bitcoin ?

First of all to prove that we’ve had to use electric power to create a new block and thus establishing an economic barrier to protect the network. This way, if an attacker wanted to write or overwrite valid blocks would have to “spend” millions of dollars worth of electricity. This barrier will progressively adjust as the value of the entire network keeps increasing, because when mining becomes profitable, new miners join in and as a consequence the difficulty increases too.
Secondly, by modifying the quiz difficulty, the network self-adjusts and guarantees a constant stream of about 6 new blocks per hour, which allows to keep track of time in the blockchain.

Lascia un commento