Crypto Trader Digest

ASICBOOST is a methodology of reducing the amount of work a mining ASIC is required to 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 and therefore there are two chunks. The ASICBOOST methodology involves keeping the value of one of the chunks the same, for multiple hashing attempts. This reduces the work required by only partially doing the work for this chunk, for multiple hashing attempts.

This research note should be considered as an illustrative overview of covert ASICBOOST, not an accurate or detailed analysis. Some of the complexities have been overlooked.

It is not known whether miners are actually using this methodology to mine Bitcoin or not. 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, without reaching any conclusions. The ASICBOOST methodology was first formally described in a paper published in March 2016.

When a Bitcoin miner hashes, for each attempt, some data in the block header is changed, such that the hash is different. The string which 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), for each hashing attempt. Once all the nonces have been exhausted, the extra nonce, which is located in the coinbase transaction (on the bottom left of the image) is altered, to provide extra entropy. Changing the coinbase transaction alters the Merkle root hash, which impacts both chunk 1 and chunk 2, such that work is required on each chunk of the block header to calculate the PoW. Contrary to a popular myth, the extra nonce was in Satoshi’s original Bitcoin design and was not added later to provide extra entropy to miners.

Using this methodology, instead of changing the extra nonce the miner alters the 4 byte version bits field in the block header instead (top left of the image). This implies 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 and this ASICBOOST methodology is therefore easily detectable.

The aim here is 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, using the brute force method.

In order to find one such collision the square root of 2^32 hashing attempts are expected to be required. This is because we are looking for one 4 byte collision, which is 32 bits. This requires 2^32 attempts and then we square root this due to the birthday paradox. This is a 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 therefore this is an inefficient process.

The following methodologies may make this process more efficient:

• Option 1 – Produce empty or smaller blocks. This simply reduces the size of the Merkle tree and therefore fewer hashing operations are required to generate a different Merkle root hash. The extra nonce can therefore be varied in the normal way to produce more Merkle root hashes.
• Option 2 – Shuffling the branches of the right hand side of the Merkle tree. An illustration of this is provided in the red circles in the explanatory image. By shuffling the top of the right hand side of the Merkle tree, a new Merkle root hash is generated, by only doing 2 extra hashes, regardless of the size of the Merkle tree. This may be possible, but there could be restrictions preventing such shuffling, such as transaction ordering. If one transaction spends the output of another transaction in the same block, it must be to the right hand side of it.
• Option 3 – Shuffling the position of transactions on the right hand side of the tree, or swapping transactions.

The above methodologies could be combined.

As shown in blue in the explanatory image, the Segregated Witness proposal gives the miner the option (if they want to use SegWit) of adding a 2nd Merkle tree to the block, with the Merkle root hash of this tree inside the coinbase transaction.

This 2nd Merkle tree is required to have the same structure as the main Merkle tree, the difference is that transaction inputs redeemed by segregating the witness, have their signature in the 2nd Merkle tree (as well as the other transaction data). In contrast to this, only the version, inputs, outputs and locktime of the transactions remain in the main Merkle tree, with the signature excluded. 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 2nd Merkle tree. Therefore any efficiency gains from option 2 or option 3 above, are lost, and covert ASICBOOST becomes inefficient.

However, after the SegWIt upgrade, a miner could still do covert ASICBOOST, but only by either using option 1 or by excluding the optional witness commitment. The theory is that doing either of these things, too often, may be suspicious and that the miner would like to keep the usage of ASICBOOST as unprovable, to maintain a secret competitive advantage.

There have been accusations that a large mining pool may be using covert ASICBOOST and that this pool is therefore 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 pools hardware products. This 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 to covert ASICBOOST in particular and could also be used for overt ASICBOOST.
• The pool in question is said to own some patents related to ASICBOOST, which could be considered as circumstantial evidence.
• Further circumstantial evidence is that this may be an explanation for the company’s desire to prevent SegWit being activated on Bitcoin. Although in our view, even if this is true, this may only be part of the reason for attempting to prevent the activation of SegWit.

In our view, although it is possible the allegations are true, the evidence is not conclusive.

BitMEX is not a licensed financial advisor. The information presented in this newsletter is an opinion, and is not purported to be fact. Bitcoin is a volatile instrument and can move quickly in any direction. BitMEX is not responsible for any trading loss incurred by following this advice.

Written By: BitMEX - Bitcoin Mercantile Exchange