Diagram of the Merkle trees inside a Bitcoin block. (Source: BitMEX Research)
AsicBoost is a way to reduce the amount of work a mining ASIC must do in order to compute a hashing attempt for Bitcoin’s proof of work (PoW). SHA256, which is the hashing algorithm used for Bitcoin’s PoW, splits the data into 64-byte chunks before the computations occur. The Bitcoin block header is 80 bytes in size and so is split between two chunks — chunk 1 and chunk 2 in the image above. AsicBoost keeps the value of one of the chunks the same over multiple hashing attempts. This requires the miner to do only partial work for this chunk, for multiple hashing attempts.
The AsicBoost methodology was first formally described in a paper published in March 2016.
It is not known whether or not miners are actually using this method to mine Bitcoin. We do not have sufficient evidence to conclude one way or the other. The purpose of this piece is to outline the theory of covert AsicBoost and this should be considered merely an illustrative overview of covert AsicBoost, not an accurate or detailed analysis. We have overlooked some of the complexities.
”Normal” hashing
When a Bitcoin miner hashes, some data in the block header is changed for each attempt, to make the hash different. The string that changes is called the “nonce”.
The miner varies the 4-byte nonce, which is located in the block header (on the top right of the image above), for each hashing attempt. Once all the nonces have been exhausted, the extra nonce, which is located in the coinbase transaction (bottom left of the image) is altered, to provide extra entropy. Changing the coinbase transaction alters the Merkle root hash, which affects both chunk 1 and chunk 2, such that work is required on each chunk of the block header to calculate the PoW.
Satoshi’s original Bitcoin design contained the extra nonce, contrary to popular myth that it was added later to provide extra entropy to miners.
Overt AsicBoost
Instead of changing the extra nonce, a miner using AsicBoost alters the 4-byte version field in the block header (top left of the image). This implies that chunk 2 remains unchanged for multiple hashing attempts and work is therefore saved. If this methodology is used, changes in the version bits are visible to everyone, which makes this AsicBoost methodology easily detectable.
Covert AsicBoost
Covert AsicBoost aims to keep the last 4 bytes of the Merkle root hash the same while generating entropy by changing the first 28 bytes of the Merkle root hash. Therefore, chunk 2 remains unchanged for multiple hashing attempts and work is saved.
However, finding multiple Merkle root hashes where the last 4 bytes collide is not easy. The only way to do this is to calculate many hashes with brute force.
Miners must look for one collision of 4 bytes, which is 32 bits — so this collision is one of 232 hashing attempts. We take the square root this due to the birthday paradox to arrive at a n approximate expected total of 65,536 attempts.
Each attempt may require changing the extra nonce to generate a new Merkle root hash. However, due to the structure of the Merkle tree, this would require even more additional hashing. If we change the extra nonce, a new is hash is required for each row of the Merkle tree. For a large Bitcoin block with perhaps 10 or more rows, this is a lot of extra work and is an inefficient process.
The following methodologies may make this process more efficient:
- Option 1 is to produce empty or smaller blocks. This simply reduces the size of the Merkle tree and therefore requires fewer hashing operations to generate a different Merkle root hash. The extra nonce can therefore vary in the normal way to produce more Merkle root hashes.
- Option 2 is shuffling the branches of the right side of the Merkle tree. The red circles in the explanatory image show this at work. Shuffling the top right side of the Merkle tree generates a new Merkle root hash with only two extra hashes, regardless of the size of the Merkle tree. This may be possible, but restrictions such as transaction ordering might prevent such shuffling. If one transaction spends the output of another transaction in the same block, the spender must be to the right side of it.
- Option 3 is shuffling the position of transactions on the right side of the tree, or swapping transactions.
The above methodologies could be combined.
Impact of the Segregated Witness upgrade proposal
As shown in blue in the explanatory image, the Segregated Witness (SegWit) proposal gives the miner the option to use SegWit and add a second Merkle tree to the block, with the Merkle root hash of this tree inside the coinbase transaction.
This second Merkle tree must have the same structure as the main Merkle tree; the difference is that transaction inputs redeemed by segregating the witness have their signatures (as well as the other transaction data) in the second Merkle tree. Only the version, inputs, outputs, and locktime of the transactions remain in the main Merkle tree. Since the transaction structure must be the same, any alterations to the main Merkle tree, such as shuffling branches, must also be reflected in the second Merkle tree, which therefore impacts the witness commitment. Any efficiency gains from option 2 or option 3 above are lost, rendering covert AsicBoost inefficient.
After the SegWit upgrade, a miner could still use covert AsicBoost, but only by using option 1 or excluding the optional witness commitment. Doing either of these things too often may seem suspicious, yet the miner who is using AsicBoost might like to hide its usage to maintain a secret competitive advantage.
Alleged evidence of the usage of covert ASICBOOST
There have been accusations that a large mining pool may be using covert AsicBoost, making this pool more profitable than other miners. Evidence for this claim is said to include the following:
-
- The particular pool in question produces a much higher proportion of empty or smaller blocks than its mining peers (we will publish research on this in the coming weeks).
- The ability to do AsicBoost is built inside the company’s hardware products. This ability has been available for over a year and may be costly to include. One could argue that this investment would be wasted if AsicBoost is not being used. However, this hardware-based evidence does not point in particular to covert AsicBoost and could also be used for overt AsicBoost.
- The pool in question is said to own patents related to AsicBoost, which if true is circumstantial evidence.
- Further circumstantial evidence is the company’s desire to prevent SegWit being activated on Bitcoin. Even if this is true, this may however only be part of the reason for attempting to prevent the activation of SegWit.
Although it is possible that the allegations are true, the evidence is not conclusive.