Learn Ethereum in 2024. #8. Forks and finality.

Ethereum’s ledger consists of a chain of blocks, structured by the inclusion of the hash of the preceding block in the header of the subsequent block. Consequently, every block effectively points to its predecessor, except for the initial block, known as the genesis block, which stands alone without pointing to any previous block. The final block, which doesn’t have any subsequent blocks linked to it, is referred to as the “head” of the chain. Ideally, all nodes within the network should consistently agree on a unique chain. However, in reality, each node maintains its own view of the chain.

Forks

There are various reasons why two nodes might possess different chains, ranging from internet latency issues to the dishonest behavior of certain nodes. To illustrate how disagreements regarding the correct blockchain can arise naturally, let’s consider an example. Picture a network comprising only three nodes: N1, N2, and N3, operating under a proof-of-work consensus mechanism. At a specific moment, all three nodes agree that the following chain is correct: A — B — C, where block A represents the genesis block and block C is the head of the chain.

So, N1 successfully mines block D and adds it to its blockchain, which now becomes A — B — C — D. It then communicates this update to N2. Almost simultaneously, N3, unaware of N1’s mining activity, also mines a block, E, and its chain becomes A — B — C — E. Following Ethereum’s protocol, N3 also shares this information with N2. Then, N2 receives information about the existence of two chains: A — B — C — D and A — B — C — E. At this point, the nodes hold differing views on which chain is “the real one”.

What occurred at that moment is a temporary fork in the network, meaning the chain temporarily diverged into two branches. Depending on the chosen consensus mechanism, forks may be more common, rare, or even impossible. In Ethereum’s case, forks are possible. The question arises: which chain should N2 regard as correct? This is precisely what the consensus mechanism addresses: it establishes a specific rule to determine the correct chain.

The longest chain

A simplistic rule for determining the true chain could be to count the number of blocks in each chain and select the longest one. However, in our example, this would result in a tie as both chains have 4 blocks. A more sophisticated rule, adopted by Bitcoin and (the before merge) Ethereum, is to choose the chain with the highest difficulty. I’ll explain how this works, but it’s worth noting that this consensus mechanism is frequently referred to as the “longest chain,” despite this not being the most accurate name.

In a mechanism that uses proof-of-work, each block possesses a difficulty that quantifies the challenge of mining the block. Consequently, the chosen chain must be the one with the highest total difficulty, calculated as the sum of the difficulties of all blocks within the chain. Referring to the sum in the image below, N2 will select A — B — C — E as the correct chain, as its total difficulty surpasses that of A — B — C — D. Consequently, if N2 mines a new block, F, it will append F immediately after E.

After creating the chain A — B — C — E — F, N2 will send its new chain to N1 and N3. N3 will certainly be pleased because the new chain is consistent with its own. However, N1 will not be very happy because its block D is no longer part of the chain. Blocks that have been appended to the chain but are subsequently excluded are referred to as orphan blocks. Since miners are rewarded for including blocks in the chain and block D is no longer part of the chain, N1 will not receive its reward, at least not in Bitcoin. In Ethereum before the Merge, even if block D did not become part of the chain, the miner still received a small reward as compensation for successfully mining a block. Block D remains within the network as an uncle block but is not part of the chain. Consequently, its transactions will not be recorded in the ledger and will not contribute to altering the state of Ethereum.

Block reorganization

Transactions from block D will return to the so-called mempool and will eventually be included in some future block. So, we can observe that the blockchain is not entirely “safe”. Let’s suppose Alice initiates a transaction of 1 million Bitcoins to Bob, and that transaction was included in block D. Then Alice shows Bob that the transaction was indeed included in block D and assures Bob that he can now return Alice’s kidnapped cat. Bob, upon verifying the blockchain according to N1’s view, confirms that Alice’s transaction was included and returns Alice’s cat. However, at the end of the day, block D becomes an orphan block, and the 1 million bitcoin transaction has not been executed. If Alice acts quickly, she can abort the transaction.

So we can see the blockchain isn’t a rigid chain but rather a fluid one, accommodating forks and block reorganizations. Before exploring the finality problem, let’s consider an alternative consensus mechanism to the chain with the highest total difficulty, known as GHOST.

GHOST

GHOST, an acronym for Greedy Heaviest-Observed Sub-Tree, is a consensus mechanism proposed by Yonatan Sompolinsky and Aviv Zohar in 2013 for Bitcoin, utilizing proof-of-work. Unlike relying solely on the highest difficulty chain, GHOST considers a sub-tree that incorporates orphaned blocks. Let’s grasp the concept of GHOST through an example. In the figure below, the chain A — B — C — E — F — G — L is the longest (and let’s assume also the heaviest), but the GHOST consensus mechanism selects the chain A — B — C — H — J — M because it is the heaviest, counting orphan blocks as well.

Note that, at a given moment, 4 blocks point to C: blocks O, H, D, and E. Only 1 block points to E (block F), whereas 3 blocks (P, J, and K) point to H. What GHOST does is utilize this entire tree of blocks to determine the correct chain.

Although GHOST was proposed for Bitcoin, it was never implemented by the Bitcoin protocol. Ethereum adopted the idea of GHOST and initially planned to implement it during the proof-of-work era, which ultimately did not occur. Currently, Ethereum employs a proof-of-stake version of GHOST called LMD-GHOST. In it, instead of considering difficulties within its sub-tree, it takes into account attestations from its validators. While it’s not necessary to delve deeply into this concept now, it’s worth noting that even within a mechanism like proof-of-work, there exist several possible algorithms for establishing consensus. Thus, the proof-of-work mechanism serves as a foundation for establishing a consensus mechanism rather than being the consensus mechanism itself. In more technical terms, proof-of-work acts as a tool to prevent sybil attacks within a consensus mechanism.

Safety and liveness

Let’s briefly delve into the nomenclature of distributed systems. A system is called safe when nothing bad happens in it, and called live if something good will eventually happen. That’s a bit of a vague definition, so let’s look at it in the context of blockchain. When we say nothing bad will happen, we are saying that there will be no forks. In other words, there will always be one and only one chain that everyone will agree on. Therefore, neither Bitcoin nor Ethereum are safe systems. It is possible to create safe mechanisms for blockchains, but it is not always desirable. Let’s imagine a safe system: let’s say that, to include a block in the chain, 2/3 of the validators have to approve it. Once this approval occurs, the block is included and can never become an orphan. We say the block is finalized. A safe consensus mechanism, for example, is the delegated Byzantine Fault Tolerance used by the Neo Network. It may seem ideal, but we will see that it is not necessarily.

Let’s consider a scenario where, in this type of consensus mechanism, for some reason, more than 1/3 of the validators are offline. Perhaps there’s an issue with the internet or they refuse to participate due to an internal dispute. Consequently, no new blocks will be included in the chain until these validators come back online or new validators are chosen. Thus, despite this mechanism being safe, it lacks the property of liveness. In Ethereum, even with the loss of 1/3 of the validators, new blocks will continue to be included. Ethereum has chosen the path of liveness over safety, although recently it has sought to achieve a balance between both paths.

Finality

The problem with blockchains that prioritize liveness over safety is the issue of finality. As we have observed, it’s impossible to assert that a block is truly final, since it can become an orphan. In Bitcoin, this issue is essentially irreversible. In such consensus mechanisms, blocks are only probabilistically finalized. This means that, as the blockchain expands, it becomes increasingly improbable for older blocks to become orphans. The same principle applies to the growth of computing power in a proof-of-work-based network. Despite never achieving technical finality, blocks that are approximately five blocks away from the head of the chain have an exceedingly small chance of being reorganized.

Casper FFG

After the Merge, Ethereum adopted a consensus mechanism that included a checkpoint-based finalization process, named Caspter FFG (Casper the Friendly Purpose Gadget). We won’t delve into its details now, but the concept is that validators periodically vote for checkpoints that they consider finalized. Once finalized, such blocks cannot be reversed unless 1/3 of all ether on the network is destroyed — an attack that would cost hundreds of billions of dollars.

Thus, Ethereum currently employs a consensus mechanism that incorporates both safety and liveness features. While it’s not entirely safe due to the possibility of block reorganization, it includes checkpoints that we can consider secure. In a future article, we will delve deeper into Ethereum’s current consensus mechanism, which combines elements of LMD-GHOST and Casper FFG.