BIP101 implementation flaws

27th August 2015

0. Introduction
With the release of Bitcoin XT 0.11A at the start of August, the block size debate hit high gear and has been hogging the news since then. This post is not going to add to that pile, and it's not an attack against Bitcoin XT or BIP101, and it's not about my preference (which would be for a dynamic block size, such as this one).

It's about glaring flaws in the BIP101 implementation as it is described by Gavin Andresen here) which could and should be easily fixed.


The flaws are in the Deployment section:

Deployment shall be controlled by hash-power supermajority vote (similar to the technique used in BIP34), but the earliest possible activation time is 2016-01-11 00:00:00 UTC.

Activation is achieved when 750 of 1,000 consecutive blocks in the best chain have a version number with the first, second, third, and thirtieth bits set (0x20000007 in hex). The activation time will be the timestamp of the 750'th block plus a two week (1,209,600 second) grace period to give any remaining miners or services time to upgrade to support larger blocks. If a supermajority is achieved more than two weeks before 2016-01-11 00:00:00 UTC, the activation time will be 2016-01-11 00:00:00 UTC.

The salient points here are:

• A supermajority is defined as 750 of the last 1,000 blocks declaring support for BIP101 by changing their version number 

• The check for supermajority occurs every new block

• There appears to be no end date for voting

This protocol means that at some point after voting begins, it is almost certain that activation will occur without a supermajority - that is when the true proportion of the network is less than 75%.

1. Flaw #1
Why is it so likely that activation will occur without a supermajority being reached? Simply put, binomial variance. The first source is in the choice of 750 (or more) of the last 1,000 blocks as the determination of a supermajority - the assumption is that the true proportion of the network voting for BIP101 is close to 75%, which is not necessarily true.

Flaw #1: Variance isn't considered when selecting such a low supermajority.

It doesn't look too bad - it's about a 1.5% chance that, for example, a true proportion of 0.72 could produce more than 749 blocks of the last 1,000. How about something less likely? A proportion of 0.7 will produce more than 749 blocks once in about five thousand times. 

So the variance is not too bad, and although a true supermajority might not be reached, it's probably going to be close - so is this really a significant problem? 

2. Flaws #2 and #3
Notice that "once in about five thousand times" in the last section? That's only about five weeks at the current block rate - so can we expect that one in five thousand chance to occur after five weeks?

The number of failure attempts before a success occurs in trials of this type is called a geometrically distributed random variable, and can be used to find the probability of some arbitrary true proportion resulting in more than 749 blocks of a sequential 1,000, after that true proportion has been present for some number of blocks.

For example, for a proportion of 0.7, the probability of creating 750 or more blocks from a sequence of one thousand blocks before January 2016 (say approximately 20,000 blocks):

So, it's very likely that, if the true proportion of support was 0.7 right now, that by January 11th next year (the earliest activation date), that activation will have been achieved - without a 75% supermajority.  

Flaw #2: Support for BIP101 is assessed every block, increasing the chance of sub-supermajority activation of BIP101.

However, there's no defined end of voting, so rather than stopping at 20,000 blocks, voting could continue for a hundred thousand blocks (a couple of years) or more. If this happened, even some of the less likely true proportions could give rise to BIP101 activation:

After a couple of years (if voting continued for so long) it's conceivable that a true proportion of just over 2/3 could activate BIP101.

Flaw #3: No final date  / final block height for voting increases the chance of sub-supermajority activation of BIP101.

3. Not Bitcoin XT
This is a fork of Bitcoin XT that advertises support for BIP101 but won't actually activate. If any large number of miners started to use this version, if and when activation occurred it's possible that anyone using Bitcoin XT would be on a minority fork.

Determining just how probable is a little tricky, since in this case multinomial distribution probabilities need to be calculated from the true proportions of the BIP101 voters, the fake BIP101 voters and non-voting proportion, so that the probability of premature BIP101 activation occurs when:

• True proportion of BIP101 voters is less than 0.5, and
• True proportion of BIP101 voters plus true proportion of fake BIP101 voters create 750 of 1000 sequential blocks.

Rather than read through textbooks and try to remember how to do that, I wrote a quick simulation and let it run while I cooked dinner. In the plot I've removed all results with a probability of 0 or 1 to make it a bit easier to read.

We're interested in the vertical section through the plot at a true BIP voter proportion of 0.5 - the largest proportion which cannot be a majority. 

So, how likely is it that a true proportion of fake voter of say 0.18 could prematurely activate BIP101? About one in a couple of hundred thousand.

Given the thousands of trials that will occur and the open-ended nature of voting, the actual probability of premature BIP101 activation is actually significant with small true proportions - one large mining pool, or a couple of smaller ones in collusion.

4. Bugfix
These flaws are simple to fix:

• Use 95% as the supermajority. This alone makes the most significant impact on risk of premature activation.
• Don't test for activation every block - instead test for the proportion of blocks that vote BIP101 (altering the version number) each retarget, for the 2016 blocks since the last retarget - 1915 blocks of 2016 would be approximately 95% of the network. A reduced number of trials means low probability events do not become more probable.
• Have an end date (or end height) after which voting ends, so trials can't continue indefinitely.

5. Summary
As it stands, the BIP101 has implementation flaws that could cause BIP101 activation with a significantly sub-supermajority, or (in the presence of fake BIP101 voters) a minority. It is almost certain that if BIP101 is activated, it will be with a sub-supermajority, or even a minority. 

It also allows true proportions of fake voters to be sufficiently low that it becomes quite possible for one large mining pool or a couple of smaller ones in collusion contributing fake BIP101 votes to cause premature BIP101 activation.

Examples:

• A BIP101 voter true proportion of 0.69 could activate BIP101 within about ten weeks with a probability of more than 10%. If continued for a couple of years, the probability of sub-supermajority activation increases to about 70%. 
• A BIP101 voter true proportion of 0.5 with a fake BIP101 voter true proportion of 0.18 has a probability of premature BIP101 activation of 3% at about ten weeks, and about 40% after a couple of years.

Fixes for these issues are outlined in part 4 above.

Find a typo or spelling error? Email me with the details at organofcorti@organofcorti.org and if you're the first to email me I'll pay you 0.01 btc per ten errors.

Please refer to the most recent blog post for current rates or rule changes.

I'm terrible at proofreading, so some of these posts may be worth quite a bit to the keen reader.

Exceptions:

• Errors in text repeated across multiple posts: I will only pay for the most recent errors rather every single occurrence.
• Errors in chart texts: Since I can't fix the chart texts (since I don't keep the data that generated them) I can't pay for them. Still, they would be nice to know about!

I write in British English.