Examining Bitmain’s Claims about ASICBoost

Bitmain recently published a blog post that made several claims about their use of ASICBoost. In this article, I seek to examine their claims.

The Difference Between Overt and Covert ASICBoost

I’ve written about ASICBoost before, but I’ve seen a lot of confusion about the difference between overt (or version-based) ASICBoost and covert (Merkle Root based) ASICBoost. In order to examine Bitmain’s claims properly, we need to understand the difference between the two.

A Little Bit about Bitcoin Block Headers

The Bitcoin block header is exactly 80 bytes long. It consists of the following fields:

You can see that version goes from bytes 0–4, previous block from bytes 4 to 36, Merkle Root from 36 to 68, etc.

The key to making ASICBoost work is that the last 16 bytes of the block header has to stay the same through multiple runs of finding proof-of-work. That is, the last 4 bytes of Merkle Root, Time, Nbits and Nonce have to be exactly the same. If so, part of SHA256 can be pre-computed and save a lot of energy in finding proof-of-work.

How Does Overt ASICBoost Work?

Overt ASICBoost keeps the same Previous Block and Merkle Root for every run and changes the version. There are 4 bytes in version, or 32 bits that can be manipulated. This turns out to be plenty for ASICBoost to work and in fact, you really don’t need more than 4 bits or so of the 32 bits.

The problem with overt ASICBoost is that the version field is currently used by BIP9 to signal for various features. It would be obvious to the network if a miner were using overt ASICBoost since somewhere between 1 to 4 bits would essentially be random in every block the miner found.

How Does Covert ASICBoost Work?

Covert ASICBoost keeps the same version and Previous Block for every run and changes the Merkle Root. But note that Merkle Root bleeds into the 16 bytes that ASICBoost cares about. Specifically, the last 4 bytes.

In order to change the Merkle Root, and yet not change the last 16 bytes of the header, a miner would need to find some collisions of the Merkle Root. This can be done by just computing a large number of Merkle Roots. If you find two Merkle Roots with the same last 4 bytes, you can use them for covert ASICBoost.

This is a lot like the birthday problem where you can try to figure out how many people have to be in a room before you find two with the same birthday (the answer, unintuitively, is 23 for about a 50% chance). As Gregory Maxwell pointed out, you actually only need to calculate about 2¹⁶ different Merkle Roots before you have a 50% chance of finding a collision in the last 4 bytes. To find 4 Merkle Roots that have the same last 4-bytes (like the number of people in a room before you have 4 with the same birthday), is 2²⁴ different Merkle Roots.

To calculate that many Merkle Roots efficiently, you need to calculate a lot of left halves and a lot of right halves. To get 2²⁴ Merkle Roots, you would need 2¹² left halves and 2¹² right halves. You can combine every left half you have with every right half you have to get the 2²⁴ Merkle Roots. Calculating different left halves is pretty easy. You can change the coinbase transaction slightly and recalculate the left half (note the coinbase transaction always lives on the left side, as it’s the first transaction).

Calculating the right half is a little more complicated. This is because you don’t want to change anything on the left half, specifically the coinbase transaction (incidentally, this is why Segwit is involved in all this as changing anything, including order, on the right side changes the coinbase transaction when segwit is activated). Remember that the coinbase transaction distributes to the miner all the mining fees from every transaction. So if you change the mining fee on any transaction on the right as a part of calculating a new right half, your left sides all are no longer valid. Thus, what you have to do is make sure the fees stay the same, but change the right side hash. This can be done several ways, including substituting with a transaction with the same fee, changing the order of transactions, etc.

To get 2¹⁶ different right sides, you need 9 transactions to change the order on. If these 9 transactions have the same exact fee, even if the block was strictly ordered by fee, this makes covert ASICBoost completely undetectable as those 9 transactions can be switched around with impunity.

I’ve examined about a day’s worth of blocks on mainnet and have concluded that most blocks have way more than 9 transactions that are both on the right side of the Merkle Tree and have the exact same fees. Essentially, every block (mined by different pools) could have used covert ASICBoost or not used covert ASICBoost. There’s no way to know by examining the blocks or transactions or fees.

Another thing about the covert method. You can generate 2²⁴ different Merkle Roots by creating an empty block and that would be a bit simpler, though still require a lot of RAM. More technical details and how efficient this method with respect to the overt method are here.

Some Facts about Covert ASICBoost

Covert ASICBoost requires a lot of memory. You need to store about 2²⁴ Merkle Roots which are 32 bytes at a minimum. That’s 256 MB of really fast memory, and probably more to accommodate for unlucky searches. You can reduce this memory requirement by getting less collisions.

You need a lot of transactions in order to use the Merkle Tree method. You need at least 25, preferably more. This may not sound like a lot to those used to Bitcoin, but most other coins, including testnet, have a lot less transactions per block.

Covert ASICBoost is a lot more complicated than overt ASICBoost. You need a lot of memory, you need to calculate a lot more hashes and you need to do a lot of transaction shuffling. Overt is a lot faster and easier to design than the covert method.

Neither overt nor covert ASICBoost are currently supported by the Stratum protocol, which is the default mining pool software protocol. Overt needs to change version bits and covert needs to change the right side of the Merkle Tree, both of which are impossible with Stratum.

Bitmain and ASICBoost

Bitmain claims to have tested ASICBoost on Testnet, but have not used it on Mainnet. This only refers to overt ASICBoost. They specifically referred to covert ASICBoost as “not practical in a production environment”. Further, they claim their circuit design supports ASICBoost, but that almost certainly refers to overt ASICBoost only.

Examining Claims

Finding overt ASICBoost is easy on Testnet as block headers would have weird version values. Indeed this seems to be the case as I’ve shown in the code published here. There are a bunch of testnet blocks around block 300,000 (October 2014) which have version fields that look pretty random and aren’t used ever again. Normal blocks near those blocks have the version number of 2. The same analysis on mainnet blocks shows that there are no weird version-number blocks.

Testing covert ASICBoost would be a little bit challenging. Most blocks on Testnet don’t have enough transactions to be able to test covert ASICBoost properly. Remember, you need about 9 transactions on the right side of the Merkle Tree. You can, of course generate your own testnet transactions. You can also test the empty-block method.

Note this breakdown of AntPool’s (owned by Bitmain) stratum extensions seem to support Bitmain’s claims of having used overt ASICBoost but not covert ASICBoost. Multi-version refers to overt ASICBoost, or how many bits can be used in the version field of the block header. Covert ASICBoost as explained by Greg Maxwell would require additional data, like what transaction ordering is required on the right side of the Merkle Tree, or which transaction hashes need to be in what position, which isn’t in that hidden configuration or their source code for implementing Stratum.

Conclusion

In this light, Bitmain’s claims of having used overt ASICBoost on Testnet, but not on Mainnet are fully consistent with the data on their respective blockchains. Specifically, it looks as though overt ASICBoost was tested by someone (likely Bitmain) around October of 2014.

Bitmain claims not to have implemented covert ASICBoost (they claim it’s impractical), and that’s also consistent with the data on both blockchains. It must be explained here that covert ASICBoost is relatively easy to hide on Mainnet given the number of transactions with the same fees and no general required ordering of transactions exist in Bitcoin other than being topologically sorted (that is, dependency order). Covert ASICBoost could also have been used on Testnet, but with more difficulty.

The evidence on both blockchains are fully consistent with Bitmain’s stance (only used overt ASICBoost and only on Testnet) and Greg Maxwell’s stance (covert ASICBoost may have been used).

It is my opinion that to determine whether covert ASICBoost has been used, a line of inquiry into whether 256 MB (or thereabouts) of fast memory is practical given the price of Antminer’s equipment and whether there is evidence of Stratum extensions that specifically order the right side of the Merkle tree would be the most fruitful in terms of settling claims of covert ASICBoost usage.