On Solving the 51% Attack Problem in Bitcoin (Part 3)
It turns out I am not the only one who has been thinking a lot about this problem. Jonathan Toomim wrote a post describing a similar scheme which I will link to at the bottom of this article.
I had a chance to chat with Jonathan and some other smart people, and discovered how to improve on my idea.
Blocks, Not Headers
The first important detail is that we need to deal with time at which the node downloads the block, not just the header. The reason is that a malicious miner could broadcast the header but never publish all the transactions in the block. Then, other nodes would left in a state of limbo. This attacker could simply wait until another miner published a header only then publish the rest of the block, which would throw the consensus algorithm into uncertainty.
So because the whole block is required, it means that propagation takes longer. However, most nodes should have most transactions already. This is the point of Graphene and similar schemes. Remember that CTOR can improve Graphene’s propagation efficiency by 7 times!
Time Delay Penalty Based on Multiple Blocks
In the simple scheme in Part 2, the delay of the first block of an alternate chain tip set the penalty factor for all subsequent blocks on that chain.
However, there are a few problems that can arise here. First, what happens if 2 blocks are broadcast at the same time, and a node happens to receive block “A”, and then loses their internet connectivity? If block “B” happens to become the valid honest chain, and the node comes online later, they will penalize the entire chain B, even if “A” becomes an orphan with no subsequent blocks.
Also, it is possible to have a slow connection or slowly propagating blocks for parts of the network. If a single block determines the fate of the chain, it can run into the chain split scenario.
To improve the algorithm then, I propose that the average delay is taken between the blocks. Each block would be compared to its “cousin” on the opposing chain: The delay between 101A and 101B is taken, then summed with the delay between 102A and 102B, etc… and divided by the total number of blocks in the opposing chain tips. If the chain that was initially delayed is longer than the first-seen chain, then the blocks without cousins count as zero delay.
So, continuing with the example above when the node receives blocks A and B, assuming they came back online 15 minutes later and saw block B for the first time, along with B2, which extends B. B2 would be penalized 900 seconds… but B2 doesn’t have an “A2” counterpart, so the entire B-B2 chain is penalized 450 seconds not 900. When B3 and B4 come in, now its 225, which is a 22.5% penalty (or 77.5% weight). At this point, the B chain should have more weight already since its 4 blocks long (4 x .775 = 3.1), which is much bigger than 1.
Poison Blocks Are Naturally Penalized
If there is a block that takes a long time to propagate (for example, because it is created privately and not from mempool transactions), it will cause other nodes to penalize it, even if it is not a clear case of building at a block height that has already been seen.
This is ok. Other miners can then build on top of the other chain. Depending on how bad the delay is, the chain will be penalized. But whether it is penalized a lot or a little, one chain or the other will pull ahead.
Could an attacker try to isolate a node by privately feeding them transactions while all other miners get the poison block? They could try this, but nodes share transactions they receive, they would get to most nodes’ mempools.
Adjusting for Finality
In this version of the algorithm, the penalty factor for the entire opposing chain keeps decreasing the longer the chain grows. This would means that eventually the longest chain rules in the end. This is both good and bad. It’s good if a mistake was made and the opposing chain is the honest chain. It’s bad if we are trying to defeat an attacker and we give him the chance to simply persist and win by brute force, even when we are reasonably sure he is malicious.
We are already departing from traditional Nakamoto Consensus and attempting to create something better, and we acknowledge we can never be 100% sure. With that in mind, we can add one more rule to our algorithm, as follows:
The number of blocks used for penalty calculation shall be no more than 30.
30 blocks is more than enough time to weigh the penalty the chain should have and will give plenty of room on both ends — either to punish an attacker or to forgive an honest chain that was received late.
Let’s see how this rule works in practice: Suppose an attacker mines a secret chain 10 blocks deep. If each block takes 10 minutes, thats 100 minutes, or an average of 50 minutes (3000 seconds). They could mine 20 more blocks and still have a 1000 second penalty (100%). They can never win the race.
But without this rule, they could mine for say 100 total blocks, decreasing their penalty to 30%. If they mine 100 blocks before the honest chain reaches 70, they can win.
Blue Moon Cases
Let’s say an underwater cable was cut, or some other “once in a blue moon” very unusual situation occurs. Imagine something causes a network partition so that China mines 30 blocks on one chain while the USA mines 30 blocks on another chain.
In this case, the 30-block rule would create a permanent chain split. However, it is worth noting that even without this rule, the penalty would already be so severe that it might take many days of mining both sides of the chain to reach convergence, which seems unlikely anyway.
Since the event we are talking about is extremely rare, and its even more unlikely that miners would compete in such a way, it seems like a weak argument against such a finality component.
Summary of Algorithm
So, let us summarize the solution we have arrived at so far:
An alternate chaintip is penalized by a factor that is calculated by averaging the delays (in seconds) of each opposing block, using a maximum of 30 blocks starting at the point of divergence, and assumes a 0 delay in the case when there is no opposing block. The average delay is then divided by 10 and then becomes a percentage. (700 seconds delay means the chain has a 70% penalty).
Jonathan Toomim has created an algorithm which is similar in spirit to the one I have presented, but his is more complex. I suspect it may be superior but I haven’t studied it in great depth yet. His algorithm is described in more detail here, and includes code simulation. It should be noted that Toomim’s algo also could or should be paired with an additional finality component.
I believe that the Bitcoin Cash community should explore, develop, and test these kinds of algorithms in earnest. We can then deploy them and protect ourselves from future “hash wars” and malicious attacks.
Acknowledgements: Thanks to the following people who spent many hours with me discussing the 51% attack topic in the past several weeks: Mark Lundeberg, Emin Gün Sirer, Jonathan Toomim, Olivier Janssens, Peter Rizun, Amaury Sechet, Jason Cox, Shammah Chancellor.