A simulation of Bitcoin’s emergent consensus

Bitcoin Unlimited proposes a market-driven, distributed approach to consensus on network rules based on Nakamoto Consensus. We call this approach Emergent Consensus. If you are not familiar with the details of Emergent Consensus, here is an excellent article and demonstration on the specific mechanics of Emergent Consensus.

People who are skeptical about emergent consensus often question whether it will maintain a blockchain, or whether it will cause continuous blockchain forks in a network fully running an emergent consensus algorithm.

Because "emergent consensus" is fundamentally based on "Nakamoto consensus", its compatibility is proven in the Bitcoin white paper (Section 11).

However, simulations of the algorithm are useful for investigating specific outcomes given specific input conditions, and they are also useful for experimenting with slightly different emergent consensus algorithms, which are meant to find those that converge quickly but whose details are difficult to capture in mathematical analysis.

Here I have created a simple simulation. The code essentially allows you to create a set of simulated miners and run different parameters with different large blocks (EB), accepted depths (AD) and different generation specifications. The code then simulates the creation of a blockchain. The code may change the settings of the miners, so we can see what happens when some hash functions choose to start mining larger blocks.

What the simulation does is that we can run thousands of individual instances of transitions between large blocks and small blocks.

This is still a work in progress, in the sense that it would be interesting to simulate more mining configurations. This paper reports 2 sets of results – one that wants to keep the blocksize low, and one that is working to bring the network to a higher blocksize.

In all cases reported, EB is set to 1MB for small blocks and 2MB for large blocks. AD is set to 4, and the block generation size is set to the same value as EB.

Typical case: 75%/25% activation

In today's "block size debate", I think 75% is a well-considered majority, a ratio that can be seriously considered a sufficient majority to want larger blocks. I ran 1000 tests, simulating 6000 seconds before the fork, and 1,000,000 seconds after the fork. So we expect about 1670 (1006000/600) blocks in a typical run.

The longest branch was 4 blocks, the average number of orphans was only 2 blocks, and the worst case had 8 orphans. In 334 runs we had no small forks (this would happen if the 75% majority mined AD blocks before the 25% minority mined 1 block), in 559 runs we had only 1 small fork. In 81 runs we had 2 forks, in 22, 3, and 1 runs we got 3, 4, and 6 forks respectively. These multiple branches are the result of the 25% minority getting lucky and finding some blocks outside of the 75% of miners that mined a certain number of blocks in a row, resulting in the majority returning to the small blockchain.

Minor cases: 60/40 activation

In the 60/40 activation hard fork (1000 runs every 100600 seconds), the longest fork is still 4 blocks, and only 3 blocks are orphaned on average, with the worst case being 15 orphans in 1800 runs. But as you might expect with a minority, there is a "long tail" of failed fork attempts. I'm just referring to the raw data included. You can read it like this: X:Y means that Y run produced X fork.

So in the data below, there was only 1 fork in 511 runs, and 5 forks in 24 runs.

 0: 139, 1: 511, 2: 182, 3: 84, 4: 44, 5: 24, 6: 7, 7: 8, 8: 1

Surprising results: What happens if the network hashrate activates a hard fork 50/50?

People who don't understand emergent consensus algorithms often assume that a 50/50 split will result in a non-convergent (i.e. non-unique) network. These are the results for 1000 runs of transactions from 1MB to 2MB blocks:

 Maximum fork depth: 4
Maximum number of orphan blocks: 34
Average orphan blocks: 5

 The X:Y run produces the X fork {0: 61, 1: 392, 2: 211, 3: 118, 4: 75, 5: 54, 6: 29, 7: 19, 8: 21, 9: 8, 10: 3, 11: 6, 13: 2, 18: 1}

Even if the network activates a hard fork 50/50, the network still maintains consensus!

In the run that created about 2000 blocks, the maximum small hashrate branch chain length was 4 blocks, and in the worst case, we got 34 orphan blocks.

But in 61 runs we did not get any small hashrate branches, and in most runs we got less than 2 small hashrate branches.

By the way, the 61 runs with no branches is a good sanity check for the correctness of the simulation, because it is easy to analyze mathematically. No branching chains means that there are 4 large blocks that need to be created in a row, and with 50/50 probability that is equivalent to flipping a coin 4 times and getting heads every time. The probability of this is (1/2)∧4 or 1/16, so from over 1000 runs we expect to see it happen about 62.5 times.

Appendix: Results Data

You may want to cut this data into a wider text editor:

 SPLIT (block height, max blocks, avg blocks): max fork depth, max orphans, avg orphans, { X:Y where Y runs had X forks }

 SPLIT (block height, maximum block, average block): maximum fork depth, maximum orphan block, average orphan block, {X:Y run produces X fork}

 0.500000/0.500000 (1790, 1797, 1674): 4, 34, 5, {0: 61, 1: 392, 2: 211, 3: 118, 4: 75, 5: 54, 6: 29, 7: 19, 8: 21, 9: 8, 10: 3, 11: 6, 13: 2, 18: 1}
0.600000/0.400000 (1816, 1820, 1673): 4, 15, 3, {0: 139, 1: 511, 2: 182, 3: 84, 4: 44, 5: 24, 6: 7, 7: 8, 8: 1}
0.667000/0.333000 (1790, 1792, 1669): 4, 13, 2, {0: 195, 1: 563, 2: 157, 3: 53, 4: 25, 5: 3, 6: 2, 7: 2}
0.750000/0.250000 (1800, 1800, 1670): 4, 8, 2, {0: 334, 1: 559, 2: 81, 3: 22, 4: 3, 6: 1}
0.800000/0.200000 (1799, 1799, 1667): 4, 11, 1, {0: 422, 1: 517, 2: 52, 3: 8, 6: 1}
0.900000/0.100000 (1797, 1797, 1667): 4, 4, 1, {0: 625, 1: 357, 2: 17, 3: 1}
0.950000/0.050000 (1789, 1789, 1669): 3, 3, 1, {0: 829, 1: 169, 2: 2}

Thanks Sickpig.