Proof-of-work

[shuijian-xu]

Proof-of-work is called “mining” for a very good reason. Like with physical mining, there is something that miners are searching for. A typical gold mining operation processes 45 tons of dirt and rock before accumulating 1 oz of gold. This is because gold is very rare. However, once gold is found, it’s very easy to verify that the gold is real. There are chemical tests, touchstones, and many other ways to tell relatively cheaply whether the thing found is gold.

Similarly, proof-of-work is a number that provides a very rare result. To find a proof-of-work, the miners on the Bitcoin network have to churn through the numerical equivalent of dirt and rock. Like with gold, verifying proof-of-work is much cheaper than actually finding it.

[shuijian-xu]

So what is proof-of-work? Let’s look at the hash256 of the block header we saw before to find out:

020000208ec39428b17323fa0ddec8e887b4a7c53b8c0a0a220cfd000000000000000000 5b0750fce0a889502d40508d39576821155e9c9e3f5c3157f961db38fd8b25be1e77a759 e93c0118a4ffd71d

from helper import hash256 block_id = hash256(bytes.fromhex('020000208ec39428b17323fa0ddec8e887b4a7c5\ 3b8c0a0a220cfd0000000000000000005b0750fce0a889502d40508d39576821155e9c9e3f5c31\ 57f961db38fd8b25be1e77a759e93c0118a4ffd71d'))[::-1] print('{}'.format(block_id.hex()).zfill(64)) # 1 0000000000000000007e9e4c586439b0cdbe13b1370bdd9435d76a644d047523

1 We are purposefully printing this number as 64 hexadecimal digits to show how small it is in 256-bit terms.

sha256 is known to generate uniformly distributed values. Given this, we can treat two rounds of sha256, or hash256, as a random number. The probability of any random 256-bit number being this small is tiny. The probability of the first bit in a 256-bit number being 0 is 0.5, the first two bits being 00, 0.25, the first three bits being 000, 0.125, and so on. Note that each 0 in the hexadecimal just shown represents four 0- bits. In this case, we have the first 73 bits being 0, which has a probability of 0.573, or about 1 in 1022. This is a really tiny probability. On average, 1022 (or 10 trillion trillion) random 256-bit numbers have to be generated before finding one this small. In other words, we need to calculate 1022 in hashes on average to find one this small. Getting back to the analogy, the process of finding proof-of-work requires us to process around 1022 numerical bits of dirt and rock to find our numerical gold nugget.

[shuijian-xu]

Proof-of-work is the requirement that the hash of every block header in Bitcoin must be below a certain target. The target is a 256-bit number that is computed directly from the bits field (in our example, e93c0118). The target is very small compared to an average 256-bit number.

[shuijian-xu]

The bits field is actually two different numbers. The first is the exponent, which is the last byte. The second is the coefficient, which is the other three bytes in little-endian. The formula for calculating the target from these two numbers is:

target=coefficient×256^exponent–3

This is how we calculate the target given the bits field in Python:

from helper import little_endian_to_int bits = bytes.fromhex('e93c0118') exponent = bits[-1] coefficient = little_endian_to_int(bits[:-1]) target = coefficient * 256**(exponent - 3) print('{:x}'.format(target).zfill(64)) #1 0000000000000000013ce9000000000000000000000000000000000000000000

1 We are purposefully printing this number as 64 hexadecimal digits to show how small the number is in 256-bit terms.

A valid proof-of-work is a hash of the block header that, when interpreted as a little-endian integer, is below the target number. Proof-of-work hashes are exceedingly rare, and the process of mining is the process of finding one of these hashes. To find a single proof-of-work with the preceding target, the network as a whole must calculate 3.8 × 10^21 hashes, which, when this block was found, could be done roughly every 10 minutes. To give this number some context, the best GPU mining card in the world would need to run for 50,000 years on average to find a single proof-of-work below this target.

We can check that this block header’s hash satisfies the proof-of-work as follows:

from helper import little_endian_to_int proof = little_endian_to_int(hash256(bytes.fromhex('020000208ec39428b17323\ fa0ddec8e887b4a7c53b8c0a0a220cfd0000000000000000005b0750fce0a889502d40508d3957\ 6821155e9c9e3f5c3157f961db38fd8b25be1e77a759e93c0118a4ffd71d'))) print(proof < target) #1 True

1 target is calculated above

We can see that the proof-of-work is lower by lining up the numbers in 64 hex characters:

TG: 0000000000000000013ce9000000000000000000000000000000000000000000

ID: 0000000000000000007e9e4c586439b0cdbe13b1370bdd9435d76a644d047523