Satoshi Nakamoto invented Bitcoin in 2008, and created for the first time a trustless decentralized money. Despite its many innovations, blockchain has some issues. In this blog post I’ll investigate some of them. I’ll explain how Bitcoin forks work and how they affect its security. If you’re already familiar with the subject, you can check out the next post that explains how this problem can be solved with the BlockDAG paradigm.
Note: This blog post assumes you are familiar with the basics of how Bitcoin and proof-of-work works. If you are not, you can watch this video (or any of the many resources that are available on the subject).
The Basics of Bitcoin Mining
Bitcoin miners always mine blocks that point to the tip of the current chain.
Note: In this post arrows point from new blocks to their parents. The orientation of the diagram can be changed due to screen space and other considerations, but this rule will always remain.
But sometimes the situation is a bit more complex than that. The Bitcoin network occasionally has “forks”: a situation where the miner needs to decide between a few competing chains. Which chain tip will the miner point to in such a situation? Let’s examine a case where a miner has a chain of 4 blocks A, B, C, D (see figure 2) and then it gets a new chain with blocks E and F. Which tip should the miner extend now? Should it mine a block on top of D or F? The easiest way to solve it will be to just ignore blocks that do not extend the current tip, but then we’re introduced with another problem: what happens to a miner that was offline when blocks A-D were created gets blocks E and F before them? If it follows the above rule it’ll mine on top of block F, all other miners will ignore its blocks and it’ll be split from the rest of the network.
In order to prevent such problems we need to find a mining rule that can objectively decide between two chains, even if the miner was not present at the time of their creation. This is why miners follow the longest-chain rule, that states an honest miner should always mine on the longest chain (it’s more accurate to say most-accumulated proof-of-work chain, but this won’t be covered by this article). So in the above example all miners (up-to-date miners and later joiners) will mine on top of block D.
The only exception to this rule is if we have two (or more) chains with equal length (see figure 3). This condition usually happens when one miner mines a block D and another miner mines block E before it’s aware to the existence of block D. This occasion is very rare, since the average block rate in the Bitcoin network is 10 minutes, but it still happens from time to time.
When this situation occurs, each miner will mine on the first tip it has seen. This is only a temporary condition that will be resolved once one of the miners will successfully mine on top of one of the chains, and then the longest-chain rule will be applied again.
Why Are Forks so Rare?
The blockchain is called a chain and not a tree for a reason: the vast majority of the Bitcoin blocks belong to the main chain, and forks happen very rarely (There were only 27 forks in the 6 months prior to the time of writing). Why is that?
The fork rate is affected by two variables: the block creation rate and the network delay.
The network delay is the time it takes for a block to be known to all of the miners. Bitcoin’s network delay is about 1 second, and a new block is created on average every 600 seconds (10 minutes). Because the average block creation time is 600 times bigger than the network delay, it’s highly unlikely that a block will be mined while another block is still being propagated.
Reorgs and 51% Attacks
We can see that the longest-chain rule makes us vulnerable to history rewrites if an attacker mines a chain that is longer than the honest chain after the fact.
A history rewrite attack (usually called a reorg, short for reorganization) can be utilized for fraudulent payments. Let’s look at figure 5 as an example: Chuck wants to buy a car from Alice, so he pays her 2 BTC. Alice sees the transaction is included in block D so she gives him the car, but a short while after Chuck succeeds to mine two consecutive blocks E and F on top of block C, where he uses the same funds he used to buy the car to pay for himself. Because of the longest-chain rule all miners abandon block D and start extending block F, and poor Alice stays without bitcoin and without a car. This is what is called a double spend attack.
To protect herself from such an attack Alice can wait a few blocks after block D before she gives Chuck the car, to reduce the chance that Chuck will succeed to build a competing chain. If Alice sees 10 blocks built on top of block D without any fork, she’ll know it’ll be highly unlikely for Chuck to mine a competing chain of 10 blocks, and will give him the car.
But what if Chuck has more than 51% of the mining power? In such a situation no matter how much time Alice will wait, Chuck will be able to make a successful reorg, because his block creation rate is higher than all of the other miners’ creation rates combined. The 51% reorg attack is a fundamental flaw in all proof-of-work systems: because the longest-chain rule cannot differentiate between honest and malicious miners, a malicious miner with enough computational power can rewrite history to its own needs. This is why any proof-of-work system needs to assume that at least 50% of the honest mining power belongs to honest participants.
All of that is nice and well, but…
How Forks Harm Security
Yonatan Sompolinsky and Aviv Zohar published a paper where they showed how the 51% attack threshold can be reduced when increasing Bitcoin’s throughput. I’ll try to explain it in the next paragraphs.
Bitcoin’s current throughput is about 7 transactions per second, because its blocks are limited to ~2.3 MB, which means each block can contain about 4000 transactions. Let’s try to see how bitcoin will behave if we try to scale it to Visa levels, so it can process 2000 transactions per second. In such a situation we expect the blocks to be 285 times bigger (655 MB blocks). The network delay can go from 1 second to 285 seconds (this is very naive calculation assuming the delay is completely linear).
How will the Bitcoin network behave under 285 seconds network delay? In a network with 285 seconds delay and average block creation rate of one block in every 600 seconds (10 minutes), we have a 285/600=0.475 chance that another block will be created (this assumes that miners are directly connected to each other, which is probably pretty much the case in Bitcoin). It means that almost 50% of the blocks will belong to forks!
But how is it related to 51% attacks? In figure 7 you can see that although 9 blocks were mined on top of A, only 6 of them were included as part of the main chain. So if an attacker wants to double spend a transaction in block B it’ll have to only create a 7 blocks chain, instead of 10. So in order to sustain a continuous reorg attack, the attacker has to create blocks faster than the main chain, but not faster than the whole network. If we take the case where half of the blocks are forked, it means only two third of them will go into the main chain, which means an attacker can have only 50%×(2/3)=33% of the hashing power in order to sustain an attack!
So we can see that by trying to increase Bitcoin’s throughput we make it more vulnerable to attacks. This is a very serious problem, and is one of the main reasons why Bitcoin’s block size remains so small.
We’ve seen that there’s a trade off between Bitcoin’s throughput and security — As long as we increase Bitcoin’s throughput we increase the number of forks and reduce the threshold for reorg attacks to be less than 50%. In the next post we’ll see how the BlockDAG paradigm can solve this issue and allow high throughput without harming security.