1 post tagged

Blockchain

Forks in the Blockchain: Discrepancies Between Competing Chains

Moshe Shababo

“Satoshi Nakomoto’s main invention is the decentralized mechanism for emergent consensus. Emergent, because consensus is not achieved explicitly — there is no election or fixed moment when consensus occurs. Instead, consensus is an emergent artifact of the asynchronous interaction of thousands of independent nodes, all following simple rules.”

~ Andreas Antonopoulos, Mastering Bitcoin

When you cannot, or simply choose not to trust any form of central authority, you are positioned in a new paradigm of trust where one cannot simply ask an oracle — a centralized service — about the current state of the system. Instead, the consensus becomes merely an abstract notion of what will eventually become accepted by the network.

The blockchain is a ledger data structure which is replicated across an unreliable network, and contains the records of all transactions. It is being constantly updated in a distributed manner, by different nodes, with new accounting data. Each update (a new block) needs some time in order to propagate, so at a given point the blockchain cannot be fully consistent across the entire network. The consensus protocol can only guarantee the emergence of a consensus over long time scales.

For this reason, a blockchain transaction can be confirmed only by the magnitude of a probability, and can never be 100% fully confirmed. At any given time, there may be multiple valid chains (versions of the blockchain) competing in the network, so different nodes might have different perspectives on the history of transactions. This condition, called a fork, can happen on a daily basis. It may be triggered by one of the following reasons:

  • Race conditions
  • Incompatible change in the consensus rules (hard fork)
  • 51% attack

An open blockchain network has the same fundamental characteristics of the Internet: decentralized, open, border-less, permission-less.

Concentration of bitcoin nodes around the world. Some of them are miners (bitinfocharts.com)

Miners are special types of nodes in the network which are competing with each other in order to update the ledger, by creating the next valid block in the chain. They are doing so by attempting to solve a difficult hash puzzle.

When one of them manages to find a solution to the hash puzzle, it constructs the new block’s header, and propagates it to the network. Nodes gradually receive the block, validate it, and add it to their local copy of the blockchain. For mining nodes, receiving a new block means that they have lost the race, and so they immediately begin to compete for the next block, by attempting to extend the one they received.

Now imagine two different miners, on the opposite sides of the globe, working on the hash puzzle. Miner A succeeds at some point, and starts propagating his new valid block to the network. In the meanwhile, Miner B also succeeds, and is doing the same, with his own new valid block.

This results in a split network — some of it which has accepted and propagated Miner A’s block (because they heard about it first), and some which accepted and propagated Miner B’s block. This scenario creates two equally valid chains, which will now compete with each other.

Competing chains

Two different sides of the network now hold two different chains, and attempt to extend them further. At some point, some miner will solve the hash puzzle, and will propagate his next new valid block. He may be arbitrarily on either side of the network — so either he will extend Miner A’s block, or Miner B’s.

Let’s assume he’s on Miner B’s side.

Competing chains

When Miner B’s side receives the new block, they continue as usual — extending their existing chain, and start working on the hash puzzle for the next block. But when Miner A’s side receive that block, they realize that they were working on the wrong chain, because they just heard about a longer chain.

“The ‘main chain’ at any time is whichever valid chain of blocks has the most cumulative proof-of-work associated with it. Under most circumstances this is also the chain with the most blocks in it” ~ Mastering Bitcoin

Bitcoin’s Consensus Protocol offers a very simple mechanism on how to resolve discrepancies between competing chains, and achieve a network-wide consensus: nodes will always converge on the longest valid chain, which represents the greatest cumulative work, for it is self-evident that it is the one which required the greatest hash power, and so it is, by definition, the consensus chain (in a world in which consensus is being voted for by hash power).

Miners that encounter a longer chain will immediately converge with it. If not, they put themselves at risk of not being in the consensus, and working on a minority chain, which will probably result in them losing all chances to gain any compensation for their expensive mining efforts.

The consensus protocol solves race conditions scenarios by offering an eventual convergence model that takes about 10 minutes (the average time for the creation of a new block). This form of accidental fork in the blockchain might happen daily, and is primarily triggered by latency of any kind — whether it’s on the network (communication between nodes), or in the nodes themselves (the block validation processing time).

Scenarios in which an accidental fork will be extended further, into two or even three consecutive blocks are rare. In order for the fork to grow longer, race conditions need to happen consecutively, in a way that neither of the sides overtake the other one by becoming the longest chain. The chances of this happening get exponentially smaller as the chain grows longer.

From this comes the notion of transaction confirmations, which represent the number of blocks that have been created after, and including, the block which contains the transaction. The higher it is, the more likely that the transaction will remain on the consensus chain. Six confirmations, which take about one hour on average, are considered to be the highest means of security that is reasonable to use, in a low-trust, high-risk transaction.

If this is so, how come, on March 11th, 2013, starting at block 225430, the bitcoin network experienced a 24-block fork?

It obviously didn’t happen from a race condition, which can hardly create a 3-block fork. In that famous incident, it happened for a different reason: a software update, a change in the implementation details, which turned out to be non-compatible due to a bug, and thus caused an unintentional hard fork.

In a hard fork, the notion of “fork” does not represent merely a fork in the chain, but rather a complete network partitioning. Nodes which are operating under a different set of consensus rules will reject each other’s transactions, and eventually will disconnect from each other. This will lead to two chains that will not consolidate: the network will not converge, and the two different chains will continue to evolve independently, representing a different ledger.

But in the March 11th, 2013 case, there was no real intention to change the consensus and split the network. What happened is that the 0.8 release of the most popular Bitcoin Node implementation, Bitcoind, introduced a different database for storing the blocks, switching from BerkeleyDB to LevelDB, as part of a performance optimization effort. Some of the miners upgraded to version 0.8 (LevelDB), and started to produce blocks which caused miners using version 0.7 (BerkeleyDB) to fail, and thus to reject it. Eventually, two parallel chains were created, one by the 0.7 Miners and one by the 0.8 Miners.

The community got into a big panic, but managed to agree that they should settle on the 0.7 chain, since the 0.8 was the incompatible one. 0.8 Miners started a rollback process, but the 0.8 chain was 13 blocks ahead of the 0.7 chain. Due to the decentralized structure of the network, they all had to do it voluntarily, by switching their hash power to the other chain’s favor. And so, after a few hours, the 0.7 chain managed to surpass the 0.8 chain, by becoming the longest chain.

The damage: unrewarded 24 blocks worth of hash power, and a few double-spend attacks (although mostly were done as POC, so merchants were eventually compensated).

Conclusion

Chain forks are a natural phenomenon which arise from the decentralized nature of the network, and might happen due to race conditions or 51% attacks (which is out of the scope of this article). The consensus protocol is designed to manage this by offering an eventual convergence mechanism, which guarantees that only one consensus chain will prevail.

Hard forks, on the contrary, occur when different parts of the network are operating on a different set of rules, and so the consensus protocol cannot offer any sort of convergence model — it is up to human beings, those who operate software on the network, to reach a mutual agreement between them, in a traditional, old-fashioned way (by screaming at each other on IRC and other forums, engaging in a twitter war, etc.), or else the network will be partitioned for good.

Blockchain