Technical Discussion on AsicBoost and SegWit

The discussion about AsicBoost and SegWit has become much quieter, but I still want to try to explain it from a technical perspective:

1. What is AsicBoost

2. What is the Relationship Between AsicBoost and SegWit?

Before talking about these two things, we cannot do without a key word:挖矿, so let’s talk about mining first!

Mining

Bitcoin mining mechanism: Bitcoin mining mechanism uses the SHA256 algorithm, but the SHA256 algorithm is not done for the entire block, but only for the block header (Block Header). The following figure shows the composition of the block:

From the above picture, we can see which fields are combined and then hashed to get the Block hash. The field with yellow background is the block header, which contains:

1. Version Number

2. The hash of the previous block

3. Merkle root

4. timestamp

5. bits(difficulty)

6. Nonce

In a round of mining, the version number, the hash of the previous block, and the difficulty are all fixed. All miners need to do is to constantly modify the Nonce to change the hash value of the current block to find Block Header that is less than the current difficulty.

But the available search space for Nonce is not enough because the number of bits of Nonce is only 4 bytes . The number of bits occupied by each field in the Block Header is:

A 4-byte Nonce means that its search probability space is 2^32 , which means that it can be traversed with 4G hash operations, which can be completed in an instant for a single mining machine.

When the search space of Nonce is insufficient, only timestamp and Merkle root can be changed. The timestamp can be adjusted forward or backward, but the search space after adjustment is still insufficient.

Miners obtain new Merkle Root by modifying Coinbase transactions, transaction order, or other methods, and then traverse Nonce again 2 ³² times. The Merkle Root is 32 bytes, and its search space is large enough.

To summarize Bitcoin mining:

Simply put, Bitcoin mining is to change the block hash by constantly changing the Nonce to find a Block Header that is less than the current difficulty. However, the search space of Nonce is too small. If the corresponding block header is not found after 2 ³² hashes, the Merkle Root needs to be changed and recalculated.

The above briefly describes the Bitcoin mining mechanism, but what about AsicBoost ?

AsicBoost

AsicBoost is an algorithm related to SHA256的计算and Block Header结构. When calculating the block header hash, it needs to be padded to 128 bytes before SHA256 calculation. The block header shown above is only 80 bytes, and the remaining 48 bytes need to be filled to 128 bytes.

The process of calculating the hash of 128 bytes is divided into two steps, the first 64 bytes are calculated together, and the last 64 bytes are calculated together:

Such a padded Block Header hash is:

 SHA256=F(Chunk1)+B(Chunk2)
Chunk1=(version)+(Previous hash)+F28(Merkle root)
Chunk2=B4(Merkle Root)+Timetamp+Bits+Nonce+padding

Combined with the above, a phenomenon occurs when calculating block hash:

Every time the value of Nonce is changed, the value of Chunk1 remains unchanged, which means that every time the Nonce is changed, you only need to recalculate B(Chunk2) and combine it with the last calculated F(Chunk1) .

This is a method to optimize mining . After the optimization, the Nonce is changed in the searchable space in each round, and the formula for calculating SHA256 becomes:

SHA256=F(Chunk1)(unchanged)+B(Chunk2)`

Basically all mining machines have done this optimization . Based on this optimization, AsicBoost has extended the idea and found another optimization method:

Since Chunk 1 can be kept unchanged, is there any way to keep Chunk 2 unchanged? From the previous formula, we can see that Chunk 2 can be kept unchanged as long as the last 4 bits of Merkle Root , the timestamp, and the Nonce are kept unchanged.

If we can find that the last four digits of Merkle Root are the same, then we can get another optimization formula with the same timestamp and nonce:

SHA256=F(Chunk1)`+B(Chunk2)(unchanged)

For timestamp, it is basically unchanged during a round of mining, while Nonce is traversed in the search space within 2 ^32. The remaining problem is to find enough Merkle Roots with the same last four digits, so that the calculation results of the latter part can be reused each time the Nonce is traversed, which effectively reduces the calculation and increases the probability of finding the block hash.

As mentioned above, a new Merkle Root can be obtained by changing the transaction order, changing the Coinbase, etc., so that the Merkle Root with the same last 4 bits can be found through collision. What is the probability of finding the same hash with the same last 4 bits through collision? According to the "birthday paradox" (the probability that the last 4 bits of the same bytes are the same 32 bits), its probability is:

There is a 50% chance that the last four digits of the hash will be the same after 77,000 collisions. How much can such a collision increase the probability? The AsicBoost white paper gives the following results:

This optimization can theoretically improve the collision efficiency by 20%, and the performance improvement of merging is about 7%. AsicBoost can be implemented in software and also through chips (hardware). How to change Merkle Root :

1. Modifying Coinbase transactions, the white paper believes that it is not efficient enough

2. Another way is to update the order of the Merkle tree

3. …other ways

It can be seen that AsicBoost is an optimization based on the Bitcoin block header and SHA256 algorithm , not an attack.

AsicBoost has only one technical optimization

It is clear that AsicBoost neither destroys the current Bitcoin protocol nor produces unusable blocks, nor does it cause any security issues for Bitcoin.
The optimization based on SHA256 algorithm has also appeared several times in the history of Bitcoin:
1. When changing Nonce as mentioned above, the first half F (Chunk1) does not need to be recalculated
2. The first three rounds of the latter part can also be optimized, refer to ms3steps
3. …
4. AsicBoost

It can be said that all software and systems have the possibility of being optimized, and the history of Bitcoin mining is a process of continuously optimizing efficiency.
How should we define优化and攻击? This is a question worth thinking about. Optimizing the calculation of the first 64 bits of SHA256 is allowed, but does optimizing the calculation of the last 64 bits constitute攻击?

AsicBoost is an optimization algorithm that increases the probability of hash collision based on the original Bitcoin mining to find a more suitable Block Header and increase the probability of finding the block header. It is not a vulnerability.

If there is a technology that improves the efficiency of Bitcoin mining, I hope that miners can apply this technology as soon as possible, so that attackers will not have a technical advantage over miners. After all, computing power is the foundation of Bitcoin security. If attackers are ahead of miners in technology, the possibility of Bitcoin being attacked will increase a lot.

After introducing AsicBoost , let’s take a look at the relationship between AsicBoost and SegWit.

SegWit and AsicBoost

SegWit (Segregated Witness) is isolated verification. Its application will change TX. It will adopt a new TX ID: Witness ID

Correspondingly, the Witness ID corresponds to Witness Merkle Tree , and then there is Winess Merkel Root . Where is Winess Merkel Root written? The answer is Coinbase .

In the SegWit protocol, Coinbase will add a new output. The new output is:

 output_data = WITNESS_COMMITMENT_HEADER + ser_uint256(uint256_from_str(hash256(ser_uint256(witness_root)+ser_uint256(witness_nonce))))
script = CScript([OP_RETURN, output_data])

The newly added output includes: OP_RETURN + WITNESS information + Witness Merkle Root hash composed of the script.

The calculation of Witness Merkle Root does not include Coinbase , thus avoiding the endless loop caused by the mutual changes between Coinbase and Witness Merkle Root .

This brings up a problem. If any transaction position is changed in SegWit , Witness Merkle Root will change. Coinbase must include Witness Merkle Root information, which will affect the change of Coinbase. The change of Coinbase will cause the Merkle Root of the entire block to change.

If the AsicBoost used in SegWit obtains a new Merkle Root by changing the transaction order, the efficiency will be reduced because Witness Merkle Root and Merkle Root need to be calculated at the same time, thereby reducing the efficiency of AsicBoost .

This is the impact of SegWit on AsicBoost. But we cannot ignore an important fact: SegWit and AsicBoost are not mutually exclusive:

As long as the block header structure remains unchanged, AsicBoost optimization still exists and is still effective.

The way to change Coinbase to obtain Merkle Root in SegWit has the same effect as changing Coinbase in the current protocol, because Witness Merkle Root does not include Coinbase TX.

SegWit and AsicBoost are not mutually exclusive, and it does not mean that AsicBoost optimization does not exist in SegWit. In SegWit , using AsicBoost can also be optimized in engineering: calculating Merkle Root also requires calculating hash, and the calculation of block hash can be blocked from time to time during the calculation of Merkle Root. Parallel calculation will be a better optimization method. In the case of parallel calculation, the efficiency reduction brought by changing Coinbase to obtain Merkle Root will not be particularly obvious.

Summarize

How AsicBoost works:

When calculating the block header, the Merkle Root is split into two parts, which results in the mining efficiency being improved if the last 4 bits of the same Merkle Root are used to calculate the block hash.

SegWit:

SegWit needs to use Wintess TX ID , and then there is a new Witness Merkle Root Witness Merkle Root , which will be written into Coinbase, but Coinbase itself will not be written into Witness Merkle Root . Because of the soft fork, the structure of the block header has not changed.

Based on the above, the following conclusions can be drawn:

AsicBoost is essentially just an optimization based on the block header structure and SHA256 algorithm.

AsicBoost and SegWit are not mutually exclusive

As long as the block header structure and SHA256 algorithm remain unchanged, AsicBoost will always exist.

SegWit will have an impact on the way transactions are exchanged in AsicBoost

In SegWit, every change in transaction order will result in a change in Coinbase, which will require recalculation of Merkle Root . Changes in transaction order will result in changes in Witness Merkle Root and Merkle Root .

If there is a better way to engineer AsicBoost, it will still work in SegWit

In addition to the inefficiency of changing the transaction order to update the Merkle Root, the engineering optimization AsicBoost method is still effective. For example, parallel computing, etc.

AsicBoost is just a way to optimize mining, and AsicBoost optimization has not disappeared in SegWit because the structure of the block has not changed. G Maxwell proposed a way to change the block header in his email so that AsicBoost can no longer be used. I don’t oppose this proposal, but I think it is unnecessary. If miners are not allowed to optimize the calculation of the last 64 bytes, then shouldn’t the optimization calculation of the first 64 bytes also be banned? And it is hard to say whether other similar optimizations will appear in the future. Should they all be banned?

Under given conditions, humans always find a way to find method A that is better than the original method B. The history of mankind is the history of continuous improvement in efficiency.

Share a Weibo post I saw: