A candidate heuristic for covert ASICBoost detection on-chain

Covert AsicBOOST is a topic that for many requires no introduction.  Today, we are going to discuss one possible form of potential on-chain evidence of covert ASICBoost use.  We will justify the heuristic, explain in what cases it may lead to false positives (or negatives), and present some initial attempts at parsing the data we have available to try to tackle the following question: “Did any miner, at any point in its mining history, activate covert ASICBoost on chain?”.

This work was originally included in a draft technical report that was intended to analyze the issue in far more depth, though the creation of this report was abandoned due to lack of interest across my collaborators, and, to be honest, myself.  I abandoned this work in April of 2017 (almost one year ago!), with a plan to get back to it and find some concrete, unbiased results.  Being that this has never materialized, and I am unlikely to return to this problem in the future, I would like to present our preliminary directions to the community.

If you don’t understand Bitcoin mining, this post is not for you, as I won’t be providing any background.

Note that this does NOT represent finished, validated, peer reviewed, or otherwise substantiated work; read with a lot of skepticism and take any conclusions derived from such a heuristic with a grain of salt without RIGOROUS PEER REVIEW.

An observation

The birth of this heuristic started with an astute observation by Ari Juels.  Namely, Ari observed that in ASICBoost, the nonce selection is actually moved outside the inner mining loop.  Consider mining in Bitcoin (from the ASICBoost whitepaper):

Bitcoin mining loop

and now mining in ASICBoost:

Screenshot from 2018-02-01 14-27-15

One key difference likely allows us to actually statistically detect the use of ASICBoost on-chain.  Look at the nonce value for both loops.  In the original Bitcoin loop, the nonce is incremented any time a solution is tried.  When you go through N nonces, you’ve tried N solutions.  On the other hand, ASICBoost’s inner mining loop depends on tryign multiple mid-states with the same nonce.  Pictorally, the nonce is red in the Bitcoin mining loop (changes every iteration), and green in the ASICBoost mining loop (fixed across inner iterations).  For an ASICBoost loop, for any nonce, a miner attempts the number of solutions equal to the number of collisions it has generated.  This means, with ASICBoost, when you go through N nonces, you’ve tried cN solutions for some constant c > 1.

What does this mean in practice?  This means that if you take hardware not running ASICBoost and turn it on, the hardware will explore the nonce space slower, trying more solutions for each nonce before moving onto the next nonce.  Despite exploring the space slower, ASICBoost uses the multiplicative factor c described above to gain an advantage in how many solutions per second are tried, the relevant metric determining success probability.  If a miner without ASICBoost takes p solutions to find a correct block (determined only by network difficulty, assuming these hash functions appear random), a miner with ASICBoost will also take p solutions.  The miner without ASICBoost will find a solution with nonce p, and the miner with ASICBoost will find a solution with nonce p/c.  Note that the nonce at which observed solutions are found depends only on number of solutions attempted and difficulty, not on time to execute a particular solution, the parameter for which ASICBoost optimizes.

To make this clearer, let’s look at the informal pseudocode of ASICBoost.

Without ASICBoost ASICBoost
while True:
    blockHeader = ...  # based on Merkle root and other fields
    sha256Block0 = sha256Expand(blockHeader[0 : 64])
    midState = sh256Compress(sha256InitVector, sha256Block0)

    for i in range(2**32):  # Try nonces
        blockHeader.nonce = i
        sha256Block1 = padAndExpand(blockHeader[64 : 80])
        singleSha = sh256Compress(midState, sha256Block1)

        sha256Block2 = padAndExpand(singleSha)
        doubleSha = sh256Compress(sha256InitVector, sha256Block2)
        if doubleSha < target:
            miningSuccessful(blockHeader)  # Jackpot!
while True:
    blockHeader = ...  # based on various fields
    candidates = dict()  # 4 bytes -> sets of blocks
    for i in range(...):  # Generate the more the merrier
        tempBh = blockHeader.randomizeMerkle()
        sha256Block0 = sha256Expand(tempBh[0 : 64])
        tempBh.midState = sh256Compress(sha256InitVector, sha256Block0)
        candidates[tempBh.merkleRoot[28 : 32]].add(tempBh)

    for i in range(2**32):  # Try nonces
        for key in candidates:
            tempBh = candidates[key][0]
            tempBh.nonce = i
            sha256Block1 = padAndExpand([64 : 80])

            for tempBh in candidates[key]:
                singleSha = sh256Compress(tempBh.midState, sha256Block1)
                sha256Block2 = padAndExpand(singleSha)
                doubleSha = sh256Compress(sha256InitVector, sha256Block2)
                if doubleSha < target:
                    miningSuccessful(blockHeader)  # Jackpot!

ASICBoost attempts more than one solution to the Bitcoin block puzzle per nonce (in the above simplified pseudocode, i, with both components bolded)!  For each i, Bitcoin mining will try one solution, and for each i, ASICBoost tries > len(candidates) * i solutions.

The candidate

In general, Bitcoin nonces exhibit a strong selection bias, as most miners begin searching for solutions at zero and use a hardware adder to increment their nonces (in the case of ASICs).  Consider then an Antminer S9 that is running ASICBoost and one that is not; for identical puzzles and runs, the Antminer running ASICBoost is more likely to get lucky earlier in the nonce space, exhibiting a stronger selection bias towards 0 and thus shifting the PDF in the previous link to the left.

One important caveat is that the above is no longer directly applicable to Bitcoin today.  With a nonce space of 2^32 and a hashrate of 14TH/s for an Antminer S9, an S9 will explore the entire nonce space around 3,000 times per second.  Selection bias is thus lost in the noise, and we expect a uniform nonce distribution across the space.  Fortunately, Bitcoin comes to the rescue with a standard for extending the nonce space with additional bits, formalized in the Stratum protocol.   This additional bit space is called “extraNonce2″.

We can thus estimate how many tries it took a particular block to be found by the hardware mining it by concatenating the extraNonce2 and nonce (extraNonce2 << 4 + nonce, or extraNonce2 * 2 ** 32 + nonce being the precise equation we use).  Because the nonce space is small enough to be insignificant, we can safely estimate this by looking only at extraNonce2 distribution.

Generally, as difficulty increases and a given hardware unit is less likely to find a solution with a smaller extraNonce, representing the decreased profitability of this hardware (which otherwise runs with relatively constant electricity and expenses).

This gives us a super easy heuristic.  Find two pools running Bitmain hardware, one suspected of running ASICBoost and one not.  We cover how to find which datacenters are running BitMain hardware and do this comparison in the next section.

Of course this is only one possible application of the heuristic.  Other potential applications include:

  1. Looking at one datacenter over time; pronounced drops in the extraNonce2 these datacenters tend to find without a corresponding network-wide difficulty increase would indicate ASICBoost being “switched on”.
  2. Looking at the same hardware as it moves across BTC/BCH; many miners are quite generous in tagging datacenter IDs and other miner information in the block header, potentially allowing this kind of tracking.

Note that it doesn’t matter how good the hardware is, whether it is an S7 or an S9.  You can even compare across non-equivalent hardware, as long as the mining loop is suspected to be the same (reasonable within a single manufacturer).  This is because what’s different between hardware is how fast a solution is generated and explored, which we argued above was irrelevant; the relevant parameter of how many solutions are explored per nonce is constant across using the same high-level mining loop.

Leveraging “luck” analysis

Now let’s take a look at some real data.  All the code generating this data is posted here in its half baked state, and requires Python 3 to run.

We look at additional coinbase outputs from various pools, common storage points for additional data like identifying pool and datacenter information and potentially extra nonce values.  I’ve gathered this data for several pools, including Antpool, BTCC, and Bitfury, up to around block 461k, when I terminated this work.  For each, I’ve also provided scripts (eg – Antpool) attempting blind decodings of potential values for extraNonce and extraNonce2.  My conjectured space for these looks something like this (for Bitmain):

Antpool conjectured extranonce1 space, 431897-460564
Antpool conjectured extranonce1 space, 431897-460564
Conjectured Antpool extranonce2 space, stronger selection bias displayed
Conjectured Antpool extranonce2 space, stronger bias displayed

Notice that the conjectured extraNonce space approximates the number of machines being run, as extraNonce represents unique “jobs”.  Some selection bias is exhibited as it is likely numbers lower than zero will appear more often in the presence of churn.  Our conjectured extranonce2 space exhibits much stronger selection bias, albeit the kind of selection bias associated with a space that is never fully explored.  Some noise exists in the data, shown here as vertical bars of uncommon extraNonces.  These likely indicate blocks whose coinbase data we have misparsed: because disparate miners across datacenters can join the same pool, there is no requirement for miners in the same pool to use the same header encoding strategies.  That being said, a clear dominant pattern and selection bias exists in the data, suggesting the possibility of a dominant strategy across Antpool for selecting this value.  The script for extracting this conjectured data is here, though it likely needs severe improvements or review before such conjectures can be trusted.

Conjectured evolution of Antpool extraNonce2 over time.
Conjectured evolution of Antpool extraNonce2 over time.

After identifying and validating this extraNonce2 (to be clear, work I have *not done*), it is possible to make graphs like the above, showing the evolution of extraNonce2 values as time passes.  The horizontal axis shows blocks on the chain, while the vertical axis shows conjectured extraNonce2 values.  Vertical slices therefore represent snapshots of extraNonce2 distributions at various moments in time.  The distribution is generally clustered strongly, though a variety of outliers exist, likely due to parsing errors or miner inconsistencies as mentioned previously.  Confirming with Bitmain the location of their default extraNonce2 for Antpool miners could further serve to validate this data.  The code for generating this graph is here.

The above range of blocks are then broken into chunks, of 2000, 5000, and 10000 Antpool-mined blocks.  Trendlines for the corresponding extraNonce2 values are then drawn through these timed blocks; the red line is the entire data (showing increase in network difficulty over time).  The black line represents 2000 block chunks, the orange line 5000 blocks, and the purple line 10000 blocks.

Because we have not validated our observations of extraNonce2, it is hard to draw conclusions from the above.  That being said, we do see the expected steady increase in extraNonce2 values over time.  An interesting point is around block 400,000, where the clear trend of previously ~linear increase rates is reversed to decreasing extraNonce2 values.  While this does not mean Antpool contained miners using ASICBoost on chain, these trend changes merit further investigation and substantiation.

Unfortunately, it is at this point that I abandoned that work; it would be great to update these graphs for a more modern, post-BCH reality, and to continue this investigation with rigorous, formal statistical hypotheses and tests.  Unfortunately, definitively confirming the location of extraNonce2 may require miner cooperation or substantial mining expertise, neither of which I possess.

Complications

There are several potential pitfalls in the application of this heuristic, pitfalls which will undoubtedly be exaggerated by inevitable political attacks in its validity.  These pitfalls are as follows:

  • Vendors can build defeat devices: If you know that this heuristic will be used, a vendor can trivially build in hardware/software strategically skipping every c‘th nonce, where c is the miner’s advantage in the first section.  Alternatively, each nonce can be skipped with probability 1/c to achieve the same effect.  I believe it is highly unlikely that such defeat devices occur, for two reasons: firstly, this heuristic was not known publicly at the time of implementation, and would have required substantial foresight to design for defensively.  Secondly, such a strategy would leave a trace in the hardware of miners, which would need to support such a capability.
  • extraNonce2 may be impossible to ascertain definitively: Potentially valid strategies for choosing a new extraNonce2 include shuffling transactions in a block, and other operations that may make it hard to answer definitively the question of “what is extraNonce2 for a given block”?  If extraNonce2 cannot be ascertained reliably, the heuristic will not work on the Bitcoin network today.  Initial investigations into potentially promising sources of extraNonce2 did not suggest this unavailability, though it is possible that further study will.  An example of breaking the ability to determine this would be random starting extraNonces or using multiple starting points in the space or techniques like transaction reordering.  Frequent settings changes can also confuse this data and introduce excessive noise.
  • This heuristic is not peer reviewed: I am not an expert on BTC mining; potentially weird “mining by proxy” setups or other factors may influence the applicability of this heuristic.  I haven’t thought of any confounding factors myself, so I open this to the community.  Perhaps we can discuss on reddit.

Despite this, I believe the candidate we propose represents the best possible detection heuristic for covert ASICBoost currently proposed.  The operative term now if anyone is in the future interested in the historical question of whether this strategy was used, is now “put up or shut up”.  All required data is in the block headers of the Bitcoin blockchain, none of which is going anywhere.  Otherwise, I would be happy to hear about why this heuristic is broken towards the advancement of my own knowledge of Bitcoin mining intricacies.

Conclusions

The proposed heuristic is just one of many potential imperfect detectors of ASICBoost.  Unlike many other heuristics (like analyzing post-SegWit or cross-BTC/BCH hashpower for similar luck metrics), it has the nice property that it can only be defeated by a miner who foresaw its use, and then only by a miner using a nonstandard adder in their nonce or extraNonce increment strategy.  I look forward to future analyses by other researchers and Bitcoin users fascinated by covert ASICBoost on-chain.

My sincerest thanks to LaurentMT, who answered my open call for help in parsing this data last year.  We spent many hours together in IRC, leading nowhere.  Alas, this is science, and sincerest thanks are still due.

Leave a Reply