Understanding Bitcoin's mining difficulty adjustment algorithm

“In the design of Bitcoin, the PoW consensus algorithm is an extremely exciting part. Miners need to spend a certain amount of computing power to construct a legal block header according to the current mining difficulty of the entire network, so that the entire network can accept the block and add it to the ledger, thereby obtaining block rewards. Mining difficulty is a variable parameter. In order to control the average block speed to 10 minutes per block, every 2016 blocks, the nodes in the entire network will recalculate and set a new difficulty value consistent with the entire network according to a unified algorithm. Before understanding the difficulty adjustment algorithm, you must first be familiar with the generation process of blocks and ledgers, as well as the data structure of block headers. Readers who are already familiar with this knowledge can jump directly to the third part.”

Block and ledger generation process

1) Transaction broadcast: The user signs and sends the transaction to any one or more network nodes. If the transaction is correct, after verification by the node, the node will continue to broadcast it to other nodes, and eventually it will be transmitted to most of the mining nodes;

2) Block production: After receiving the transaction, the miner node packages the transaction into a block and calculates the root hash value of the Merkle Tree corresponding to the transaction. The block header is constructed through mining operations until the hash value of the block header meets the mining difficulty requirement;

3) Block broadcast: After any miner node successfully mines a block, it will immediately broadcast the block to the entire network. Similar to transaction broadcast, other nodes in the entire network will verify the legitimacy of the block;

4) Ledger acceptance: If only one legitimate block is produced in the same period and there are no other legitimate blocks competing with it, the block will be included in the ledger. If there are competing blocks, it depends on the will of the majority of the computing power of the entire network to choose which block path branch to inherit and expand. The chain with the greatest cumulative difficulty and the longest will eventually win. The legitimate blocks that are not included in the ledger become orphan blocks and are eliminated.

"The path chosen by the will of the majority of computing power": The blockchain miners can be collectively regarded as a marching army. In the process of fighting and advancing, some people often fall behind or go astray. So how to distinguish the diversion path from the main path? Of course, the route chosen by the mainstream army with the main military power is the main path.

(Figure 1, the chain with the largest cumulative difficulty and the longest duration is the main chain, from Bitcoin Developer Reference)

Block and header data structure

The block header data only takes up 80 bytes of storage space. Due to the introduction of the transaction Merkle Tree Root, the block header can represent the entire block and can be transmitted and processed independently. In the simple schematic diagrams of Figures 2 and 3, not all fields are fully given. The actual block header data structure contains 6 fields:

Version : 4 bytes, the version of the Bitcoin protocol. Miners can set the free bits in the 4 bytes to vote for computing power;

Previous Block Hash : 32 bytes, the hash value of the previous block header data (double SHA256), through which each block is linked in sequence to form a blockchain account book;

Transaction Merkle Root : 32 bytes, Merkle Tree Root hash value (double SHA256) of the transactions in this block;

Block generation time (Time) : 4 bytes, using UNIX epoch time, must be greater than the median time value of the previous 11 blocks, but cannot exceed 2 hours from the current time;

Mining difficulty threshold (nBits, or Bits) : 4 bytes, a simplified encoding of the target threshold for mining difficulty. The hash value (double SHA256) of the current block must be less than or equal to this threshold;

Random number (Nonce) : 4 bytes. By adjusting this value multiple times, double SHA256 hash operation is performed on the current block header data to meet the requirements of the mining difficulty threshold.

(Figure 2, the structure of the block, from "Bitcoin: A Peer-to-Peer Electronic Cash System")

(Figure 3, chain-structured ledger, from Bitcoin: A Peer-to-Peer Electronic Cash System)

Block speed and mining difficulty adjustment

The block header hash value occupies 32 bytes (265 bits). If MAX=2**256 is defined, the block header hash value ranges from 0 to MAX-1. The result of double SHA256 hash operation on the block header must be in the range of 0 to MAX. A threshold TT (Target_Threshold) is taken within this range, and it is stipulated that the block header hash value must be in the range of 0 to TT to be legal. Therefore, the mining operation is to continuously adjust the three fields in the block header: Nonce, Time, Merkle Root, and try to calculate the hash value in the range of 0 to TT (invalid in the range of TT to MAX) to obtain a legal block header.

Due to the design characteristics of the hash function, its output results are basically evenly distributed in the value range . The larger the TT, the greater the probability that the hash operation result falls in the range of 0 to TT, and the mining difficulty is low. Conversely, the smaller the TT, the greater the mining difficulty. This is like archery. If the target is large, it is easy to hit, and if the target is small, it is difficult to hit. Adjusting the value of TT also adjusts the difficulty of mining. Since TT needs to occupy 256 bits, in order to shorten the total size of the block header, the Bits field of the block header is obtained by simplifying the encoding of TT.

In the Bitcoin network, mining nodes may join or leave at any time, so the hash power of the entire network often changes. Assuming that the mining difficulty remains unchanged, if the computing power of the entire network increases, the block generation speed will become faster, and it will take less than 10 minutes on average to generate a block. On the contrary, if the computing power of the entire network decreases, the block generation speed will become slower, and it will take more than 10 minutes on average to generate a block. If you need to maintain an average of 10 minutes to generate a block, you must dynamically adjust the mining difficulty (that is, the value of the Bits field) as the computing power of the entire network changes.

The reason why the algorithm of "adjusting the difficulty every 2016 blocks" is adopted instead of adjusting it every time a block is produced may be because when Satoshi Nakamoto designed Bitcoin, he did not foresee the emergence of mining machines, mining farms, and mining pools, nor did he foresee that a large amount of computing power could be switched between BTC, BCH, and other systems that use the same hash algorithm, causing a large fluctuation in the computing power of the entire network. After all, Bitcoin is a groundbreaking invention and it is difficult to achieve perfection. People's exploration and improvement of blockchain technology must be continuous and iterative.

Assuming that the height of the block currently being produced is an integer multiple of 2016 (the block height is counted from 0), the value of TT should be adjusted. If the expected output time of the last 2016 blocks is recorded as S (2016*10*60 seconds) and the actual output time is recorded as R, then S/R reflects the multiple relationship between the actual speed of block production and the expected speed. Adjust the value of TT to TT*S/R, that is, enlarge or reduce the target range of the hash value according to the value of S/R, and the average speed of block production will be close to the expected 10 minutes/block.

From another perspective, we first define a formula DIFF=MAX/TT, which is equivalent to dividing the interval 0-MAX into DIFF sub-intervals, and 0-TT is the first interval. From a probability point of view, after trying DIFF hash operations, the interval 0-TT can be hit once, and this DIFF can be considered as the difficulty value. When TT and MAX are equal, the DIFF value is 1, which means that it can be hit by executing 1 hash operation. However, the commonly used method of calculating the difficulty value is not like this. When Bitcoin was first launched, it may be that Satoshi Nakamoto set an initial TT value based on the mining computing power conditions at the time, recorded as BMAX:

0x00000000FFFF000000000000000000000000000000000000000000000000000000000000000, and then define the formula BDIFF=BMAX/TT, it can be concluded that the initial benchmark difficulty value BDIFF is 1 (that is, the minimum difficulty value). Later, in some mining pools, a PMAX was set: 0x00000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF, and the difficulty value was calculated according to the formula PDIFF=PMAX/TT. BDIFF, PDIFF, and DIFF are all used to express difficulty, but the corresponding benchmark maximum values ​​(BMAX, PMAX, MAX) are different. BDIFF is more commonly used, and its intuitive meaning is: compared with the initial minimum difficulty value of 1, the current difficulty has increased to BDIFF times.

For example, through the block browser https://www.blockchain.com/zh/btc/block-height/481824, you can find that the header hash value of Block#481,824 (2016*239) is 0000000000000000001c8018d9cb3b742ef25114f27563e3fc4a1902167f9893, and the contents of each field in its header are:

Version:

0x20000002 (in hexadecimal, miners voted with one of the bits in favor of Segwit)

Previous Block Hash：

0x0000000000000000000cbeff0b533f8e1189cf09dfbebf57a8ebe349362811b80 (displayed in hexadecimal)

Merkle Root:

0x6438250cad442b982801ae6994edb8a9ec63c0a0ba117779fbe7ef7f07cad140 (displayed in hexadecimal)

Time: 24 Aug 2017, 01:57:37 (displayed as date and time)

Bits: 0x18013ce9 (displayed in hexadecimal)

Nonce: 575,995,682 (in decimal)

Querying the previous block Block#481,823, we can get Bits as 0x180130e0, while Block#481,824 adjusted the mining difficulty and adopted a new value of 0x18013ce9.最高位字节18 （十进制的24）表示TT数值的字节长度，而013ce9表示TT最高位3个字节的数值，由此得出TT的值为0x 013ce9 000000000000000000000000000000000000000000，补满前导0扩展到256位（32字节），则为0x0000000000000000 013ce9 000000000000000000000000000000000000000000，计算0x00000000FFFF0000000000000000000000000000000000000000000000000000 / 0x00000000000000000 013ce9 00000000000000000000000000000000000000000000000, the result (BDIFF) is: 888,171,856,257.32, which means that the mining difficulty when producing Block #481,823 is 888,171,856,257.32 times the initial minimum difficulty (1), and the computing power of the entire network has increased dramatically.