Technical explanation of ASICBoost patent gate and Bitcoin package mining principle

Preface: The recent "ASICBoost patent gate" incident has caused a sensation in the entire cryptocurrency circle and will affect the future of Bitcoin. The entire patent technology involves the low-level process of Bitcoin packaging and mining, which may be difficult for many people to understand. After referring to a large number of documents, this article attempts to introduce the entire mining technology knowledge in an easy-to-understand way. Any support judgment should be based on objective judgment based on technology, which will be much more reliable than judgment based on subjective comments of some people.

First article, HASH algorithm

A hash algorithm, also known as a hash function, maps a binary value of arbitrary length to a shorter binary value of fixed length. This small binary value is called a hash value.

　　For easier understanding, you can think of the familiar WinRAR compression software. No matter whether there is only one original file or several original files, they can be compressed into a RAR file. When any original file is changed, the recompressed RAR file will change and will no longer be the previous file.

The hash algorithm is somewhat similar, but the object it processes is not a file, but a string. The original string of any length is "compressed" into a string, namely the hash string. Any slight change in the original string will cause the hash to change. The difference from RAR is that the hash result cannot be "decompressed" to restore it to the original string.

There are many kinds of hash algorithms, typical hash algorithms include MD2, MD4, MD5, SHA-1, SHA-2, SHA-256, SHA-512, SHA-3, RIPEMD-160 and SCRYPT algorithm (used by Litecoin and Dogecoin), etc. SHA256 algorithm is widely used in Bitcoin, and RIPEMD160 algorithm is only used when generating coin addresses from public keys. SHA256 algorithm is generally used when hash is used elsewhere. Its characteristics are shown in the figure below: any string is converted into 256 bits of random 0 or 1.

Part 2: The underlying mechanism of mining

In fact, it is easy to understand what the underlying mining machine is doing. It is to continuously change the original data to continuously calculate the hash value under the SHA256 algorithm , and succeed when certain conditions are met.  

2.1 What conditions must be met for success?

See the recent block hash of block 461,228 for an example.

000000000000000001f682adc333ebb751e63b204c8f8aa7b595e11394d5a154

The first 17 are all zeros, and the numbers after them must be less than a certain number to meet the conditions. These hash value results are random, and the only way to make them so regular is to constantly change the original content and try again, and select those that meet the difficulty conditions from a large number of random results. The difficulty is not fixed. It is adjusted every 2016 blocks (about two weeks, 2016/6/24=14) mined according to the mining power of the entire network. If the time taken to mine 2016 blocks is less than two weeks, the difficulty will be increased; if it is longer than two weeks, the difficulty will be reduced.

2.2 What is the original data?

Instead of taking the hash value of the entire block content, only the 80-byte block header is subjected to the SHA256 algorithm. These 80 bytes are specifically divided into six parts.

1) Version number: 4 bytes, changes when voting

According to the current BIP9 upgrade specification, the version number is used to vote on the fork upgrade plan supported by the block itself. If SW is supported, the version number is 0×20000002. For details, please refer to the following article:

9.6Bite Jiang-Bitcoin Block Version Number Knowledge and Upgrade Specification BIP9

2) Previous block Hash: 32 bytes, changes when a new block is created

This is the key to stringing blocks into a blockchain, indicating which block this block was mined on. When a new legal block appears in the Bitcoin network, the hash of the new block must be replaced in time, otherwise it may be isolated even if it is mined.

3) Transaction tree root MerkleRoot: 32 bytes, changes with transaction time

All transactions should be hashed, but the amount of calculation is too large, so all transactions are combined into a 32-byte hash data using the Merkle Root Hash method. It can represent all transactions, and any small change in any transaction will cause a change in the MerkleRoot. There will be more discussion and diagrams later.

4) Timestamp: 4 bytes, current time slightly changed

It is best to write the current time, but it is not very strict. A certain time deviation is allowed, but it cannot be too large. If the deviation is too large, the block will be isolated. Because it is not strict, sometimes the next block is earlier than the timestamp of its previous block. This is possible, but the real birth time is of course the previous block first, then the next block.

5) Current difficulty value Bits: 4 bytes, changes every two weeks or so

It is determined by the computing power of the entire network and readjusted every 2016 blocks. The adjustment algorithm is fixed, which means that when adjusting, everyone can calculate it based on historical data, rather than being specified by anyone. How to use four bytes to represent the difficulty? It is somewhat similar to the scientific notation of astronomical numbers. The first byte V1 represents the number of bits shifted to the right, and the remaining three bytes V3 represent the specific valid data.

F(nBits)=V3 * 2^(8*(V1-3) ​​)

6) Random number Nonce: 4 bytes, changeable at any time

This is for miners to adjust when mining, so that they can find the right value so that the hash result of the block header can meet the difficulty requirement. It is estimated that Satoshi Nakamoto made a mistake in designing this parameter. It is only 4 bytes, which was enough in the CPU mining era, but it is not enough in the GPU era. All the Nonce can be tried once in a few seconds. However, the above timestamp TimeStamp can be fine-tuned. Once adjusted, it can be mined for a few more seconds, which is barely enough. However, in the era of professional mining machines and mining pools, Nonce is far from enough. Since each field generally has a clear and fixed meaning and cannot be easily changed, it turns to the 32-byte transaction tree root MerkleRoot.

Part 3: Interaction between miners and mining pools

In the early days, miners could mine independently. However, as the difficulty of mining increases, individual miners can no longer compete with the mining pool model. Take a look at the block situation in the past 7 days in the figure below. The vast majority of blocks are mined by mining pools. There is a clear division of labor and cooperation between mining pools and miners.

3.1 Mining services provided by mining pools to miners

The collection of bit transactions is done on the mining pool, which needs to run a full node, but miners do not. As indicated by the blue line in the figure below, the mining pool will generate those black dots from the transactions to be packaged, and then send them to the miners from time to time. In addition, a basic coinbase transaction is constructed and sent to the miners. In theory, the coinbase transaction content given by the mining pool to the miners can remain unchanged for a long time. However, after the implementation of SW isolation, the coinbase needs to be changed whenever there is an adjustment in the transaction order or transaction content. In addition, the mining pool must provide block header data other than MerklerRoot and Nonce.

3.2 Miners’ contribution to mining pools

After receiving the information from the mining pool, the first step for miners is to calculate the red dots . To improve the coinbase transaction, a random number is usually added to improve it, and then the coinbase transaction is hashed with SHA256. The second step is to calculate the green dots , and then merge the result of the coinbase with the black dots in the figure below one by one to get the hash of the previous layer, and finally get the top transaction tree root MerklerRoot. The third step is to calculate the block header hash . With MerklerRoot, combined with the block header data provided by the mining pool, a randomly changing Nonce can form a complete block header, which is used to calculate the hash. When the Nonce is completely traversed and the timestamp is changed enough, it is normal to return to the first step to replace a random number to re-perfect the coinbase transaction, and then the MerklerRoot value in the second step will eventually be different. ASICBoost may update MerklerRoot by swapping the transaction order. The fourth step is to submit the successful Share calculation results . It does not have to meet the difficulty of the entire network. As long as it meets the mining difficulty set by the mining pool, it can be submitted. Generally, it is submitted to the mining pool's own miner ID and task ID, the coinbase random number, and the block header's timestamp and random number Nonce. The mining pool will verify it in time after receiving it. If it meets the requirements, it will record a credit contribution and check whether it meets the difficulty requirements of the entire network. If it meets the requirements, it will be broadcasted and released, so that a new block can be mined, and the amount of coins that each miner should have will be allocated according to the recorded credit Share number.

For more details, see: 9.8Bite Sauce Bitcoin [Mining Pool] History, Functions and Significance and "The Evolution of Blockchain Core Technology - Mining Evolution"

Part 4: Patented ASICBoost Optimization

If you can still understand it clearly after reading this, it means you have a high IQ. But this is not the end of mining wisdom. There are even smarter people who have designed the ASICBoost patent, which can theoretically increase the mining efficiency by 30%. However, it requires the tacit cooperation of hardware and software, especially the mining machine and the mining pool.

The specific patent details are not very clear. But thanks to @拿铁大's Weibo, a good description of the content has been given. This article quotes part of it for illustration.

　　According to current understanding, to put it simply, it uses the internal calculation rules of the SHA256 algorithm, first in groups of 64 bytes, and then in groups of 4 bytes. The ASICBoost patent should be to use the method of exchanging transaction positions, without modifying the coinbase, to quickly obtain many identical MerklerRoots at the end of the 4 bytes, so that the hardware can accelerate and optimize the calculation of the hash value of the two SHA256 of the block header, that is, the speed of SHA256 ( SHA256 ( BlockHeader )).

When calculating the SHA256 of this block header, we need to first pad it to 128 bytes with fixed padding bits, and then SHA256 will process it in groups of 64 bytes, which can be simply considered as F (F (initial value of the SHA256 specification, the first half), the second half). F needs to split these 64 bytes into groups of 4 bytes and perform 64 rounds of calculations. Combined with the above figure, it is not difficult to find that the first 28 bytes and the last 4 bytes of the Merkle Root are separated. In the process of modifying the Nonce, the first half remains unchanged, and the first 12 bytes of the second half are also unchanged. Therefore, almost all chips have now made these two optimizations, namely the processing results of the first half (midstate in getwork) and the results of the first 3 rounds of the second half (midstate3). The effect of this optimization is (61/64+1)/3 = 65.1%, an increase of 34.9%

Merkle Root looks awkward in the diagram. It would be better if Satoshi Nakamoto had made Version the third field when designing it (that is, put Version after MerkleRoot). In this way, the first 4 bytes of the second half are fixed. If we don’t have such high requirements for timestamps, the first 12 bytes can be completely fixed. For chips, more calculations can be saved, and some corresponding circuits can be removed. ASICBoost pushes this idea one step further: we build a group of Merkle Roots with the same last 4 bytes.

The question then becomes whether it is possible to efficiently find a Merkle Root with the same suffix? How much is the efficiency improvement? The ASICBoost white paper mentions a very efficient method and gives a table:

The impact of the number of Merkle Root collisions on efficiency in the ASICBoost white paper The impact of the number of Merkle Root collisions on efficiency in the ASICBoost white paper. (The table means that if five Merkle Roots with the same last 4 bytes are found, the efficiency can be improved by 20%)

The essence of the problem here is a 32-bit hash collision. According to the "birthday paradox", the number of attempts required to find a set of collisions is not very many. We only need 77,000 attempts to have a 50% probability of finding two Merkle Roots with the same suffix. Of course, for a mining machine, only 2 are far from enough. If it is a mining farm, it should be equipped with special hardware to generate enough tasks. There are usually two ways to try a new Merkle Root:

Method 1: Modify Coinbase transaction . This method seems to be the simplest and most hidden, but the white paper believes that it is not efficient enough ;

Method 2: Swap the order of any transaction. The white paper only gives an example of method 2, and does not give other methods. Note that for both 1 and 2, the new Merkle Root does not need to be calculated from the bottom up.

Part 5: Relationship with Segregated Verification SW

Segregated Witness SW: Segregated Witness isolates the signature and puts it at the back, achieving a soft expansion effect of about 1.7MB on the chain. In addition, many currency technologies such as LN Lightning Network and side chain technology are waiting for SW activation. Why would the profiteers of the ASICBoost patent hinder SW?

5.1 ASICBoost patent requires swapping the order of transactions

In order to quickly generate a large number of Merkle Roots, and select more Merkle Roots with the same last 4 bytes, and then send them to miners. This is mainly done in the mining pool, so it is not enough to have only mining machines that support ASICBoost without the cooperation of the mining pool. In addition, the mining machine needs the cooperation of the mining machine hardware to receive these Merkle Roots with the same last 4 bytes, and can perform special hardware storage optimization. Therefore, it is not enough to have only mining pools that support ASICBoost and mining machines without ASICBoost. And I don’t think there will be too many detailed traces of using ASICBoost on the blockchain, except that the transaction order is a bit messy, which is not neat to begin with, and there may be a higher empty block rate than other mining pools, because when there is only coinbase transaction, it will be faster to find the Merkle Root with the same last 4 bytes.

5.2 ASICBoost patent, efficiency reduced after SW isolation verification implementation

Because it will no longer be possible to easily swap the order of any transaction. Because SW will have a Witness Merkle Root to write into the OP_return output of the coinbase transaction. In other words, swapping the transaction order did not affect the coinbase before, but after the implementation of SW isolation verification, swapping the transaction order, then the Witness Merkle Root may have to follow the change, and then the coinbase will change. In the end, it will be more convenient to directly modify the coinbase according to the above method 1 to find the Merkle Root with the same last 4 bytes. Therefore, the implementation of SW isolation verification cannot completely prevent the implementation of the ASICBoost patent, but it will reduce its efficiency, thereby reducing the interests of the implementers of the ASICBoost patent.

In addition, the latest EXTBLK extension block scheme was almost immediately accepted and supported by the blockchain because although the EXTBLK extension block is also written into the OP_return output of the coinbase transaction, the transactions in EXTBLK are relatively independent of the main chain transactions, and exchanging the order of transactions on the main chain should not affect the EXTBLK Merkle Root.

It is understandable to oppose a certain plan for one's own benefit, but one should speak the truth instead of using other reasons (saying that the SW code is too complicated and requires too many changes and is unsafe, but not supporting LTC to use SW to help test the code first). Nor can one support opposing and unreliable versions (BU is so bad that it will only have a few bugs in the short term, and EC has a more complicated consensus, but one still strongly supports it, just because BU does not affect ASICBoost).

I call on ASICBoost holders to think more about the entire cryptocurrency community. You cannot damage the interests of the entire cryptocurrency community for the sake of temporary interests. There are still more than a hundred cryptocurrency applications waiting for SW activation. And it is not that the ASICBoost patent is completely invalid, it is just that the efficiency is reduced. You can continue to use the ASICBoost patent by adjusting the random number in the coinbase. In the future, it will become two steps. The first step is the Merkle Root miner running in the mining pool, calculating a large number of Merkle Roots with the same last 4 bytes. The next step is to give the same Merkle Root data with the suffix to the Bitcoin miner that supports the ASICBoost patent.

After the patent technology is made public, there is no need to be secretive. The entire mining industry can collectively enter the next stage. In the future, major mining pools will no longer just compete on network speed and distribution fee ratio, but also on the Merkle Root mining machine capabilities of the mining pool.

Related articles: 9.9Bite Jiang calls for [SW synthetic fork] Detailed explanation of Bitcoin isolation verification

Continuing to quote "What is ASICBoost?"

So what does this have to do with SegWit? SegWit introduces "witness tx id", and the transaction has another new ID in addition to the original ID, which is the transaction hash obtained using the new transaction serialization format (excluding the signature part). Correspondingly, we also have a new Witness Merkle Tree and Witness Merkle Root. Due to the soft fork implementation, we cannot replace the existing Merkle Root, but add an OP_Return output to the Coinbase transaction and write this "WMR". This also means that for any changes to transactions or transaction order, we have to recalculate the "WMR" from the bottom up, which greatly reduces the efficiency of logging.

OK, I know why you want to block SegWit. It turns out you want to secretly use ASICBoost . Not only will you block SegWit, you will also block all progress of Bitcoin.

Stop it. . . .

Being able to use ASICBoost + oppose SegWit does not mean opposing SegWit for ASICBoost.

You see two things existing at the same time and think that one of them is the cause of the other. Your mistake is that two things existing at the same time may not necessarily have a causal relationship.