What is ASICBoost?

Preface

ASICBoost can be said to be a good V-washing, and many smart minds have become brainless and illogical. It is recommended to read these two articles first to sort out your own thoughts.

• https://medium.com/@samcole_74219/asicboost-655a73d48ae4(http://8btc.com/thread-50972-1-1.html)

• http://hackingdistributed.com/2017/04/05/bitcoin-drama-response/

Bitcoin Mining and SHA256

Let's first briefly review the Bitcoin mining mechanism and the SHA256 algorithm. Bitcoin mining is to calculate the SHA256 hash value twice for the 80-byte block header, that is, SHA256 (SHA256 (BlockHeader)). The result of this operation must be less than the target corresponding to the current network difficulty. The block header includes a 4-byte version number, the hash of the previous block header (32 bytes), the Merkle Root of the current candidate block package transaction (32 bytes), the timestamp (4 bytes), the difficulty (4 bytes), and the Nonce (4 bytes). In each round of mining, the version number, the previous block header, and the difficulty are all determined, and miners need to constantly modify the Nonce to construct a block header that meets the difficulty. However, the search space of Nonce is obviously not enough (2^32), so miners also need to modify the Coinbase transaction to obtain a new Merkle Root, that is, change it once every 2^32 hashes.

Block header

When calculating the SHA256 of this block header, we need to first fill it with fixed padding bits to 128 bytes, 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 is unchanged, and the first 12 bytes of the second half are also unchanged. Therefore, almost all chips have 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 optimization effect is (61/64+1)/3 = 65%, an increase of 35%.

ASICBoost

Merkle Root looks awkward in the diagram. It would be better if Satoshi Nakamoto had made the Version the third field when designing it. In this way, the first 4 bytes of the second half are fixed. If we don’t have such high requirements for the timestamp, the first 12 bytes can be completely fixed. For the chip, 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.

ASICBoost

The question then becomes whether it is possible to efficiently find a Merkle Root with the same suffix? How much of an efficiency improvement can this have?

How to cut trees efficiently?

Merkle Root is the root of the Merkle tree calculated from all transactions in the block.

Merkle Tree (Quoted from Mastering Bitcoin Chapter 7)

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 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:

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

2. Swap the order of any transaction

3. The white paper only gives method 2 as an example 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. For example, to change transaction A, we only need to recalculate HA, HAB, HABCDEFGH and the root. To exchange transactions (IJKL) and (MNOP), we only need to recalculate HIJKLMNOP and the root.

Detecting ASICBoost

1. Is the block version correct?

2. Does the transaction order conform to the default priority?

3. It seems that it is impossible to detect the modification of Coinbase, but this method is less efficient than method 2

Segregated Witness

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.