Mining Fees, Block Data, Block Headers, and Proof-of-Work
Now that we have some background on what the mining process does for Bitcoin, let's cover the specifics. This chapter covers the technical process, including mining fees, block data, block headers, and Proof-of-Work.
Mining the Block
Proof-of-Work Algorithm
A hash algorithm takes an arbitrary-length data input and produces a fixed-length deterministic result, a digital fingerprint of the input. For any specific input, the resulting hash will always be the same and can be easily calculated and verified by anyone implementing the same hash algorithm. The key characteristic of a cryptographic hash algorithm is that it is computationally infeasible to find two different inputs that produce the same fingerprint (known as a collision). As a corollary, it is also virtually impossible to select an input in such a way as to produce a desired fingerprint, other than trying random inputs.
With SHA256, the output is always 256 bits long, regardless of the size of the input. In SHA256 example, we will use the Python interpreter to calculate the SHA256 hash of the phrase, "I am Satoshi Nakamoto".
Example 8. SHA256 example
$ python Python 3.7.3 >>> import hashlib >>> hashlib.sha256(b"I am Satoshi Nakamoto").hexdigest() '5d7c7ba21cbbcd75d14800b100252d5b428e5b1213d27c385bc141ca6b47989e'
SHA256 example shows the result of calculating the hash of "I am Satoshi Nakamoto": 5d7c7ba21cbbcd75d14800b100252d5b428e5b1213d27c385bc141ca6b47989e. This 256-bit number is the hash or digest of the phrase and depends on every part of the phrase. Adding a single letter, punctuation mark, or any other character will produce a different hash.
Now, if we change the phrase, we should expect to see completely different hashes. Let's try that by adding a number to the end of our phrase, using the simple Python scripting in SHA256 script for generating many hashes by iterating on a nonce.
Example 9. SHA256 script for generating many hashes by iterating on a nonce
link:code/hash_example.py[]
Running this will produce the hashes of several phrases, made different by adding a number at the end of the text. By incrementing the number, we can get different hashes, as shown in SHA256 output of a script for generating many hashes by iterating on a nonce.
Example 10. SHA256 output of a script for generating many hashes by iterating on a nonce
$ python hash_example.py I am Satoshi Nakamoto0 => a80a81401765c8eddee25df36728d732... I am Satoshi Nakamoto1 => f7bc9a6304a4647bb41241a677b5345f... I am Satoshi Nakamoto2 => ea758a8134b115298a1583ffb80ae629... I am Satoshi Nakamoto3 => bfa9779618ff072c903d773de30c99bd... I am Satoshi Nakamoto4 => bce8564de9a83c18c31944a66bde992f... I am Satoshi Nakamoto5 => eb362c3cf3479be0a97a20163589038e... I am Satoshi Nakamoto6 => 4a2fd48e3be420d0d28e202360cfbaba... I am Satoshi Nakamoto7 => 790b5a1349a5f2b909bf74d0d166b17a... I am Satoshi Nakamoto8 => 702c45e5b15aa54b625d68dd947f1597... I am Satoshi Nakamoto9 => 7007cf7dd40f5e933cd89fff5b791ff0... I am Satoshi Nakamoto10 => c2f38c81992f4614206a21537bd634a... I am Satoshi Nakamoto11 => 7045da6ed8a914690f087690e1e8d66... I am Satoshi Nakamoto12 => 60f01db30c1a0d4cbce2b4b22e88b9b... I am Satoshi Nakamoto13 => 0ebc56d59a34f5082aaef3d66b37a66... I am Satoshi Nakamoto14 => 27ead1ca85da66981fd9da01a8c6816... I am Satoshi Nakamoto15 => 394809fb809c5f83ce97ab554a2812c... I am Satoshi Nakamoto16 => 8fa4992219df33f50834465d3047429... I am Satoshi Nakamoto17 => dca9b8b4f8d8e1521fa4eaa46f4f0cd... I am Satoshi Nakamoto18 => 9989a401b2a3a318b01e9ca9a22b0f3... I am Satoshi Nakamoto19 => cda56022ecb5b67b2bc93a2d764e75f...
Each phrase produces a completely different hash result. They seem completely random, but you can reproduce the exact results in this example on any computer with Python and see the same exact hashes.
The number used as a variable in such a scenario is called a nonce. The nonce is used to vary the output of a cryptographic function, in this case to vary the SHA256 fingerprint of the phrase.
To make a challenge out of this algorithm, let's set a target: find a phrase that produces a hexadecimal hash that starts with a zero. Fortunately, this isn't difficult! SHA256 output of a script for generating many hashes by iterating on a nonce shows that the phrase "I am Satoshi Nakamoto13" produces the hash 0ebc56d59a34f5082aaef3d66b37a661696c2b618e62432727216ba9531041a5, which fits our criteria. It took 13 attempts to find it. In terms of probabilities, if the output of the hash function is evenly distributed we would expect to find a result with a 0 as the hexadecimal prefix once every 16 hashes (one out of 16 hexadecimal digits 0 through F). In numerical terms, that means finding a hash value that is less than 0x1000000000000000000000000000000000000000000000000000000000000000. We call this threshold the target and the goal is to find a hash that is numerically equal to or less than the target. If we decrease the target, the task of finding a hash that is less than the target becomes more and more difficult.
To give a simple analogy, imagine a game where players throw a pair of dice repeatedly, trying to throw equal to or less than a specified target. In the first round, the target is 11. Unless you throw double-six, you win. In the next round the target is 10. Players must throw 10 or less to win, again an easy task. Let's say a few rounds later the target is down to 5. Now, more than half the dice throws will exceed the target and therefore be invalid. It takes exponentially more dice throws to win, the lower the target gets. Eventually, when the target is 2 (the minimum possible), only one throw out of every 36, or 2% of them, will produce a winning result.
From the perspective of an observer who knows that the target of the dice game is 2, if someone has succeeded in casting a winning throw it can be assumed that they attempted, on average, 36 throws. In other words, one can estimate the amount of work it takes to succeed from the difficulty imposed by the target. When the algorithm is based on a deterministic function such as SHA256, the input itself constitutes proof that a certain amount of work was done to produce a result equal to or below the target. Hence, Proof-of-Work.
Tip: Even though each attempt produces a random outcome, the probability of any possible outcome can be calculated in advance. Therefore, an outcome of specified difficulty constitutes proof of a specific amount of work.
In SHA256 output of a script for generating many hashes by iterating on a nonce, the winning "nonce" is 13 and this result can be confirmed by anyone independently. Anyone can add the number 13 as a suffix to the phrase "I am Satoshi Nakamoto" and compute the hash, verifying that it is less than the target. The successful result is also Proof-of-Work, because it proves we did the work to find that nonce. While it only takes one hash computation to verify, it took us 13 hash computations to find a nonce that worked. If we had a lower target (higher difficulty) it would take many more hash computations to find a suitable nonce, but only one hash computation for anyone to verify. Furthermore, by knowing the target, anyone can estimate the difficulty using statistics and therefore know how much work was needed to find such a nonce.
Tip: The Proof-of-Work must produce a hash that is equal to or less than the target. A higher target means it is less difficult to find a hash that is equal to or below the target. A lower target means it is more difficult to find a hash equal to or below the target. The target and difficulty are inversely related.
Bitcoin's Proof-of-Work is very similar to the challenge shown in SHA256 output of a script for generating many hashes by iterating on a nonce. The miner constructs a candidate block filled with transactions. Next, the miner calculates the hash of this block's header and sees if it is equal to or smaller than the current target. If the hash is greater than the target, the miner will modify the nonce (usually just incrementing it by one) and try again. At the current difficulty in the bitcoin network, miners have to try quadrillions of times before finding a nonce that results in a low enough block header hash.
A very simplified Proof-of-Work algorithm is implemented in Python in Simplified Proof-of-Work implementation.
Example 11. Simplified Proof-of-Work implementation
link:code/proof-of-work-example.py[]
Running this code, you can set the desired difficulty (in bits, how many of the leading bits must be zero) and see how long it takes for your computer to find a solution. In Running the Proof-of-Work example for various difficulties, you can see how it works on an average laptop.
Example 12. Running the Proof-of-Work example for various difficulties
$ python proof-of-work-example.py* Difficulty: 1 (0 bits) [...] Difficulty: 8 (3 bits) Starting search... Success with nonce 9 Hash is 1c1c105e65b47142f028a8f93ddf3dabb9260491bc64474738133ce5256cb3c1 Elapsed Time: 0.0004 seconds Hashing Power: 25065 hashes per second Difficulty: 16 (4 bits) Starting search... Success with nonce 25 Hash is 0f7becfd3bcd1a82e06663c97176add89e7cae0268de46f94e7e11bc3863e148 Elapsed Time: 0.0005 seconds Hashing Power: 52507 hashes per second Difficulty: 32 (5 bits) Starting search... Success with nonce 36 Hash is 029ae6e5004302a120630adcbb808452346ab1cf0b94c5189ba8bac1d47e7903 Elapsed Time: 0.0006 seconds Hashing Power: 58164 hashes per second [...] Difficulty: 4194304 (22 bits) Starting search... Success with nonce 1759164 Hash is 0000008bb8f0e731f0496b8e530da984e85fb3cd2bd81882fe8ba3610b6cefc3 Elapsed Time: 13.3201 seconds Hashing Power: 132068 hashes per second Difficulty: 8388608 (23 bits) Starting search... Success with nonce 14214729 Hash is 000001408cf12dbd20fcba6372a223e098d58786c6ff93488a9f74f5df4df0a3 Elapsed Time: 110.1507 seconds Hashing Power: 129048 hashes per second Difficulty: 16777216 (24 bits) Starting search... Success with nonce 24586379 Hash is 0000002c3d6b370fccd699708d1b7cb4a94388595171366b944d68b2acce8b95 Elapsed Time: 195.2991 seconds Hashing Power: 125890 hashes per second [...] Difficulty: 67108864 (26 bits) Starting search... Success with nonce 84561291 Hash is 0000001f0ea21e676b6dde5ad429b9d131a9f2b000802ab2f169cbca22b1e21a Elapsed Time: 665.0949 seconds Hashing Power: 127141 hashes per second
As you can see, increasing the difficulty by 1 bit causes a doubling in the time it takes to find a solution. If you think of the entire 256-bit number space, each time you constrain one more bit to zero, you decrease the search space by half. In Running the Proof-of-Work example for various difficulties, it takes 84 million hash attempts to find a nonce that produces a hash with 26 leading bits as zero. Even at a speed of more than 120,000 hashes per second, it still requires 10 minutes on a laptop to find this solution.
At the time of writing, the network is attempting to find a block whose header hash is equal to or less than:
0000000000000000029AB9000000000000000000000000000000000000000000
As you can see, there are a lot of zeros at the beginning of that target, meaning that the acceptable range of hashes is much smaller, hence it's more difficult to find a valid hash. It will take on average more than 1.8 zeta-hashes (thousand billion billion hashes) for the network to discover the next block. That seems like an impossible task, but fortunately the network is bringing 3 exa-hashes per second (EH/sec) of processing power to bear, which will be able to find a block in about 10 minutes on average.