V God and Paradigm Research Partner: Ethereum 2.0 will be able to resist reorganization attacks after the merger

Original title: Ethereum Reorgs After The Merge
Written by: Vitalik Buterin, co-founder of Ethereum, and Georgios Konstantopoulos, research partner at Paradigm Translated by: Chen Zou

Recently, there has been discussion about the possibility of miners adopting a supposedly modified Ethereum client that would allow them to accept bribes and queue transactions in selected blocks. (The main use case for such bribes is to attack DeFi protocols).

In this post, we will explain why this attack mode will be much harder to execute after the Ethereum 2.0 merge.

What is the Fork Choice Rule and why is it important?

The fork choice rule is a function evaluated by the client that takes as input the set of blocks and other messages it has seen, and outputs to the client what the "canonical chain" is. The fork choice rule is necessary because there may be multiple valid chains to choose from (for example, if two competing blocks with the same parent are published at the same time).

A reorg is a special event where a block that was once part of the classic chain is no longer part of the classic chain because a competing block beat it. Finality refers to the situation where the fork choice rule favors a certain block so much that it is mathematically impossible (or at least economically infeasible) for that block to be re-compiled.

In some fork choice rules (such as Tendermint), reorgs are impossible; the fork choice rule simply extends the existing chain by adding any blocks that have passed BFT consensus and finalized. In other fork choice rules, reorgs are very frequent.

What is the current state of Ethereum?

In proof-of-work (PoW) blockchains like Ethereum, we often see the “longest chain rule” (or more precisely, the “highest total difficulty chain rule”). This means that when a client finds 2 blockchains, it chooses the one with the highest total difficulty (i.e. the sum of the difficulties of all blocks in that chain).

For example, assuming the difficulty of a block can be 100 or 110, imagine the following scenario.

• We start syncing from block 1 with a difficulty of 100.

• Blocks 2a and 3a arrive with difficulty 100 each, and we insert them into our chain, forming a fork with a total difficulty of 300.

• Block 3b with difficulty 110 arrives, announcing 2a as its parent, forming a fork with a total difficulty of 310. The fork choice rule will notice that the "heaviest" chain is now the second fork, and will switch to it. This is a 1 block reorg, as only block 3a was changed. Note that these blocks are not completely discarded, as a new block may arrive that causes the fork choice to switch back to the first fork.

• Blocks 2b and 3c arrive, each with a difficulty of 110, creating a new fork with a total difficulty of 320! This means that the difficulty of the fork choice is 320. The fork choice rule will now use 2b instead of 2a, and 3c instead of 3b, which were both blocks in the previous classic chain. This is a re-combination of 2 blocks.

You can see what this will do. If a new block 4a arrives, announcing 3a as its parent, the fork choice rule will switch back to the first fork, and so on.

Impact of chain reorganization

Because of latency, brief reorgs happen all the time. Miner A and miner B may find a valid block at the same time, but because of the way blocks propagate across a p2p network, one part of the network will see A's block first and another part will see B's block first. If both blocks have the same difficulty, there is a tie and clients either choose at random or choose the block they saw earlier. Often, the tie is eventually broken when a third miner, C, builds a block on top of either A's block or B's block, and the other block is forgotten. Occasionally, bad luck will result in a 2-5 block reorg. Reorgs that take longer than this are almost always due to extreme network failures, client errors, or malicious attacks.

Short reorganizations are not fatal, but they still have serious consequences for the network.

• Node costs: When a reorganization occurs, there will be some storage issues since one has to switch to the new fork, potentially rolling back transactions or modifying the blockchain state.

• Degraded user experience: The possibility of a re-fork means that users will need to wait longer before they can safely see transactions involving them as “confirmed.” An important sub-case of this is businesses such as exchanges needing to wait longer before accepting deposits.

• Uncertainty in transaction context: When users send a transaction, they have low certainty about the context in which the transaction will be executed (e.g., will the most recent N blocks be recovered? Notably, this increases the likelihood of unexpected failures of DeFi trading pairs, worse-than-expected transaction outcomes, or harmful MEV extractions.

• Increased possibility of 51% hashrate attack: In a system driven by the longest chain rule, if the miners on the chain are reordered from B1 to B2, then the difficulty of B1 no longer helps to ensure the security of the chain. The attacker no longer needs to defeat all honest miners, they only need to defeat the part of honest miners that have not been reorganized. If reorganizations are frequent, this greatly simplifies the attacker's work.

The worst possible scenario

In the worst case, frequent reorganizations can render a blockchain's settlement guarantees completely invalid and prevent it from proceeding. Normally, the "incentive-compatible" strategy for block producers should be to extend the longest chain. However, what happens if the post-state of a certain block is profitable (e.g., has very high fees or MEV that can only be extracted by building a block directly after this block)? This question has been explored in the past in the context of Bitcoin without block rewards and selfish mining, and today in the context of MEV related to DeFi in the Ethereum ecosystem.

In these cases, there is a strong incentive to try to "steal" fees or MEV by competing instead of extending the tip of the classic chain. In the example below, the post-block 1 state is profitable and block 2a has already been mined. However, not 1 but 3 block producers choose to mine on block 1 instead of block 2a (to claim any MEV exposed after block 1), and this can be extended to any number of parties.

For obvious reasons, such a pattern opens the door to malicious 51% hashrate attacks. We call miners who engage in such reorg mining tactics "myopic rationality" because the decision to do so may be rational in the short term. However, they have explicit (coin minters) or implicit (miners) long positions on Ethereum (because fees and block rewards are denominated in Ethereum), which means that any such attack that reduces user trust in Ethereum is against their ultimate interest and therefore irrational in the long run.

Merged Ethereum and Proof of Stake

In Nakamoto PoW, blocks are "serialized" in fork choice. First, a block is mined, at which point a competing block has the potential to reorganize it. If that block survives as part of the classic chain, after (on average) 13 seconds, some other miner builds a second block on top of it. At this point, a chain of two competing blocks is needed to reorganize it. As more blocks are built on top, the difficulty of reorganizing the chain continues to increase, but slowly.

Ethereum's beacon chain implements a PoS protocol called Gasper, with a fork selection rule called LMD-GHOST. In contrast to Nakamoto PoW, there are 2 roles in the block production process.

• Proposer: A validator’s task is to propose a block.

• Participants: A group of validators vote on which block they believe is the head of the classic chain. The validators' votes are called "attestations" and they assign "weights" to blocks. Controlling the validators means controlling the fork selection rule.

Every 12 seconds there is a "slot" which represents an opportunity to propose a block. For each slot, a shuffling algorithm pseudo-randomly selects a committee consisting of 1/32 of all validators, where one validator in each committee is the proposer and the rest are approvers. Validators vote in parallel on the blocks they believe are part of the classic chain. Since committees are sampled pseudo-randomly, there is no way for an attacker to concentrate their validators into a single location.

Today, the beacon chain has 196,000 validators, which means that each slot has a committee of size 6125. Therefore, refactoring even a single block is extremely difficult, as an attacker who controls only a few validators has no way to defeat the honest majority of thousands of participants.

To get some intuition about why this is the case, let’s look at an example with 2 slots and 24 validators, 9 of which are malicious. The validators are split into two committees, and due to the random shuffle, it is unlikely that an adversary can control more than 50% of either group they are assigned to and cause a reorg.

More formally, the probability that a malicious actor with p% of the stake controls more than 50% of a committee of size N validators follows a binomial distribution (with k = N/2).

Calculating the probabilities for different situations, we get the following table:

We now understand that a straightforward reorg would require the attacker to control close to 50% of the validators.

There are more subtle attacks that are possible if the attacker has 25-49% of validators. However, these attacks have known fixes that can be implemented unnoticed, increasing security to close to the unconditional 50%.

Finally, long-term recovery is impossible because all blocks deeper than 2 epochs into the past are considered “finalized”, i.e., it is impossible to recover from the past. If an attacker causes two conflicting blocks to be finalized (e.g. by controlling 67% of the stake), the system will need to fall back to social intervention to recover.

Game theory in restructuring strategy adoption

Now that we have seen how reorg strategies work for different fork choice rules, it is worth going through a simple game theory example to understand when it would make sense for a miner or validator to profitably use software that executes a reorg strategy.

We can describe each case informally using a reward matrix, where “bug” means “downloading and using software that performs anti-fraud.” The rewards are short-sighted and do not take into account long-term consequences.

Satoshi Proof of Work

In longest chain PoW, short-range reorgs can be probabilistically performed with even a small fraction of the validator set. Occasionally there will always be blocks with profitable post-states, so that even a 1-10% chance of success makes it worthwhile to try to compete with existing children of that block.

A miner can be a medium sized mining pool that relies on their likelihood of finding the next 2-3 blocks in a row, or they can send a portion of their income into a contract that anyone can claim in order to bribe other people running the same software to build on their chain and help it fight against the existing Classic chain.

Therefore, some miners may be tempted to run the reorg client.

Gasper

In Gasper, reorgs of slots 1-64 are possible, but require the attacker to control a large portion of the entire validator set (since they can't concentrate their stakes on a specific slot, they need to have a large enough stake to randomly choose within the range of slots they want to attack). Adopting reorg mining software is useless unless a very large number of other validators also adopt it.

Therefore, if 51% of validators are even slightly altruistic, then no one running the reorg software is a stable equilibrium.

Tendermint

In Tendermint, the situation is even cleaner: reorgs are impossible, and any violation of single-slot finality requires more than 1/3 of the validators to be slashed. Similar to the case with Gasper, this also means that a stable equilibrium is achieved when no one is running the reorg software.

From the above we can see that although adopting "reorg geth" is possible in all cases, the fork choice rule based on the concept of parallel proof has an honest equilibrium state, and it will be more stable than the equilibrium in Nakamoto fork choice.

Lessons from Experience

In the context of Ethereum, the most effective preventive measure is to further accelerate the work of merging, especially to quickly achieve a credible ability to conduct an "emergency merge" to transition the chain to PoS. Rushing to merge will have a high risk of damaging the infrastructure, but if many miners begin to attack the chain again, a credible commitment will resist such behavior.

The period close to a merger is the most risky because miners are still in charge of the system, but their time horizon is shortened. However, two factors mitigate this risk.

• Ethereum miners are often also (i) miners on other blockchains, and/or (ii) members of other Ethereum communities, so they still have incentives to behave well.

• As the merger approaches, the difficulty, cost and risk of doing an emergency merge are decreasing. An emergency merge will be highly disruptive a few months before the scheduled date of the merger. Two weeks before the scheduled date of the merger, it will be a parameter setting for customers to verify that the operator has completed the download.

After the merger, reorganization verification will become a smaller problem, because a single validator or a small group of validators cannot reorganize on their own. A successful reorganization attack must solve the extremely difficult coordination problem of getting most validators offline at the same time. However, some small risks still exist. If further security is desired, Ethereum can further adjust the fork selection rule to increase the requirement for a reorganization attack to a theoretical maximum of 50%, or find a way to move directly to a consensus of single-slot inality.

This article is reproduced from BitpushNews and reprinted with permission from Planet Daily