On Solving the 51% Attack Problem In Bitcoin (Part 1)

The 51% attack problem in Bitcoin is one of the most difficult challenges and also one of the most valuable to solve. The Bitcoin whitepaper tells us that “The system is secure as long as honest nodes collectively control more CPU power than any cooperating group of attacker nodes.”

But can we do better than this?

Bitcoin is an economic system. Referring again to the whitepaper as it discusses a potential attacker: “He ought to find it more profitable to play by the rules, such rules that favour him with more new coins than everyone else combined, than to undermine the system and the validity of his own wealth”

Yet we know that not all actors are rational. There could be state-sponsored entities with virtually unlimited funding, or corporations that are willing to invest/lose vast sums of money for some strategic or other benefit.

If we can create a way for honest miners to achieve distributed consensus and extend the ledger even if the face of a malicious majority, it will be a monumental advancement for Bitcoin.

The dangers of a mining monopoly

The purpose of Bitcoin is to provide a distributed ledger that powers permissionless peer-to-peer cash. A 51% attack is not dangerous merely because it can create a double-spend which causes a merchant to lose money, but rather because it can destroy the entire system.

WiIth a majority of sustained hashpower, an attacker can continuously (or periodically) invoke a blockchain reorganization (“reorg”) which disrupts the reliability of the network. At the extreme, they can mine empty blocks forever and only extend the chain on their own blocks, shutting all others out and causing the chain to be completely unusable.

Previous approaches to the problem

Gavin Andresen proposed that we could prevent a malicious miner from publishing empty blocks with a consensus rule that required inclusion of priority transactions. But this seems to be a weak solution. Not only would a well-funded attacker certainly be able to create their own transactions which appear to be valid economic activity, but also this does not prevent re-org attacks in general.

ZenCash proposed a penalty system for delayed blocks, where the proof-of-work of an attacker’s blocks is diminished by a penalty factor. Although these kinds of systems can stop certain attacks, they also have drawbacks. They may still allow deep reorgs or reorg attempts which hurt 0-conf reliability. The attacker can also flip this scheme on the honest miners with a simultaneous block attack.

In this attack, the malicious miner would mine 2 valid chains in secret from the same block height, and broadcast them at the same time from different nodes. Some honest miners would get block A first and believe block B to be the attack, and others would see the opposite. The two groups would then penalize each other and possibly never converge.

And if the penalty is only applied to a certain number of blocks, then a majority attacker can simply continue to mine until they have a longest chain once again.

Invalidating blocks

The next logical approach is to simply allow miners to invalidate a suspicious looking block and make a clean break. When a block is invalidated, the chain extending from that block is null and void. This is a clean break.

However, how do you decide exactly what is suspicious?

The Threshold Paradox

A simple attempt to identify a malicious re-org block could be to set a time limit, but this is problematic as we will discover.

For example, if the tip of the chain is on block height 100, and a duplicate block of height 100 comes in, we might say that the block is invalid if a node observes it coming in N seconds after the existing block of the same height.

But what value should N be? Assuming no network or propagation issues, most of the time a block header can be broadcast to most nodes within about a second. So, let’s say that we choose a value much larger: for example 15 seconds. Anything that comes in after 15 seconds is clearly invalid.

That sounds simple enough, but what if a block comes exactly at the 15 second mark? Some nodes might get it slightly earlier or later than other nodes, and thus half the network could see it as valid, and half invalid.

This is the paradoxical aspect here, because no matter how big you set it (for example 3 minutes), the situation still exists which could split the chain accidentally or be exploited intentionally when a block lands right on the chosen time marker. It would perhaps seem, intuitively, that nodes should be able to use some common sense setting that can tell if a block is coming in too late.

The paradox is explained by the fact that the setting creates a boundary or “fault line”.

Block re-org depth ( “automatic checkpoints”)

The next logical question is if we can identify a block height beyond which re-orgs are forbidden. For example, any reorg deeper than 4 blocks could be invalid. But this too runs into a threshold timing problem because if a 3-block reorg is attempted while another miner is also broadcasting the 4th block, then some nodes will see it as valid, and some will see it as invalid, causing a chain split once again.

Nakamoto Consensus and the Byzantine General’s Problem

Nakamoto Consensus is a term used to describe Bitcoin’s use of the highest proof-of-work chain to identify the correct version of the ledger. The reason it works flawlessly is that there is always a distinct, measurable, and indisputable number that can be agreed on.

In addition, it is deterministic in such a way that non-mining nodes can simply and easily follow along with the consensus decision.

The Byzantine generals problem describes a group of generals who want to attack a city, but they do not have an easy way to coordinate their attack. In Bitcoin, we might think of each solved block as a “general” that the rest of the army can follow. Doing the work thus designates a miner as having a turn to play the role of general.

We start to realize the genius of using proof of work as a distributed timestamping mechanism and how very difficult it is to create another form of it that does not rely on proof-of-work, proof-of-stake, or other blockchain protocol.

Looking for Clues

If the basic idea of how the blockchain should work is that miners solve one block at a time and extend the ledger, then we want to identify and penalize bad behavior that circumvents this system.

It is somewhat of a myth that Bitcoin needs to handle reorgs of a large number on any sort of regular basis. Most orphans are of a single block. Occasionally, there will be a 2-block orphan chain. 3 is almost unheard of. Longer reorgs only occur because of a software bug, not normal network activity.

This knowledge can help us, because we do not need to handle reorgs of unbounded size; we only need to be able to handle them within practical limits.

Another important consideration is that strictly using the longest-chain rule allows new nodes to see exactly what happened and know which chain they should follow. They do not need to be aware of reorg attempts, late blocks, etc. So, perhaps giving up this aspect is an acceptable trade-off if it allows online nodes to reach consensus on the correct honest chain.

Non fully distributed solutions

If we imagine a simply solution to not allow reorgs more than 6 blocks, then we know that a 6-block reorg that comes at the same time as a new block could split the chain. However, it would be easy for attentive miners to detect the split and reset it.

But this requires human intervention, and perhaps coordination between honest miners. It is not something that can be fully automated.

This can work as a practical matter, but it is not a fully distributed solution. If currently there is a group of honest pools which trust each other and which the community trusts, it works. But this breaks down at global scale in an environment where nobody is sure who they can trust.

Another non-distributed solution is to allow a group of trusted pools (perhaps 3 out of 5 signatures) to invalidate a block. This could be done in a way where nodes have to observe the re-org taking place; the pools cannot arbitrarily direct the chain.

These are more war-time ideas. Ultimately, we need to keep looking for fully distributed solutions.

Bitcoin ABC’s 0.18.5 Patch

The Bitcoin Cash client ABC 0.18.5 uses both a penalty and a maximum re-org depth in such a way that attacks are expensive and difficult. It is not a perfect solution. If exchanges require at least 10+ confirmations and if miners are attentive, it will be harder to disrupt the network than without this patch.

This should not be a permanent solution and we should keep improving it.

Thinking Outside the Box

It should be clear that 51% attacks are not an easy problem to solve. But, breakthroughs happen regularly in the blockchain space from outside-the-box thinking.

I have a few ideas myself. In the next part of the series, I will unveil one solution I came up with using a slightly different approach.