This is an authoritative technical book on the Ethereum proof of stake protocol. It will start with some preliminary content and cover some consensus basics not limited to Ethereum.
Author: Ben Edgington
Translator: tiao
This article is the second half of the chapter "Fundamentals of Consensus". The first half can be found in "Upgrading Ethereum: Fundamentals of Consensus".
Fork Choice Rule
As we have seen, for various reasons—network delays, network interruptions, misordering of message receipt, malicious behavior by peer nodes—nodes on the network will eventually have different views of the network state. Ultimately, we want every correct node on the network to have a consistent linear view of history, forming a common view of the system state. The protocol's fork choice rule is designed to achieve this consistency.
Given a block tree and some decision criteria based on a node's local view of the network, the fork choice rule is intended to select the branch most likely to become the final linear canonical chain from all available branches. In other words, when a node attempts to converge to the canonical view, it will choose the branch least likely to be pruned from the block tree.
The fork choice rule implicitly selects a branch by choosing a block at the top of a branch, known as the head block.
For any correct node, the first criterion of any fork choice rule is that the block it selects must be valid, compliant with the protocol's rules, and all of its ancestors must also be valid. Any invalid blocks will be ignored, and any blocks built on top of invalid blocks are themselves invalid.
Given this, there are many different examples of fork choice rules.
The proof of work protocols in Ethereum and Bitcoin use the "heaviest chain rule" [4] (sometimes referred to as the "longest chain," although this is not entirely accurate). The head block is the top of the chain with the most accumulated "work" completed under proof of work.
In Ethereum's proof of stake Casper FFG protocol, the fork choice rule is to "follow the chain containing the highest justified checkpoint," and never to revert a block that has been finalized.
In Ethereum's proof of stake LMD GHOST protocol, the fork choice rule is reflected in its name: it adopts the "greediest, heaviest observed subtree." It involves computing the cumulative votes of validators on a block and its descendant blocks. It also applies the same rules as Casper FFG.
We will explain the second and third examples in their respective chapters.
You may have noticed that these fork choice rules are all methods for assigning a numerical score to a block. The winning block—the head block—has the highest score. The idea behind this is that when all correct nodes eventually see a certain block, they will unambiguously recognize it as the head block and choose to follow its branch, regardless of their own other views of the network. Therefore, all correct nodes will eventually reach a consensus on a single canonical chain traced back to the genesis.
Reorgs and Reversions
When a node receives a new block (and in proof of stake, new votes on blocks), it re-evaluates the fork choice rule based on the new information. The most common case is that the new block will be a child of the block the node currently considers the head block and will become the head block.
However, sometimes the new block may be a descendant of some other block in the block tree (note that if the node does not have the parent block of the new block, it needs to ask its peer nodes for the parent block, and the same goes for any other blocks it knows it is missing).
In any case, running the fork choice rule on the updated block tree may point to a head block on a different branch than the previous head block. When this happens, the node must perform a reorganization, also known as a rollback. It kicks out (rolls back) any blocks previously included in its chain and adopts the blocks on the new head block branch.
In the following diagram, the node evaluates block F as the head block, so its chain consists of blocks A, B, D, E, F. The node knows about block C, but it is not in the node's view of the chain; block C is on a side branch.
After some time, the node receives block G, which is not built on the node's current head block F, but on a branch of block C. Depending on the details of the fork choice rule, the node may still evaluate F as a better head block than G, and thus ignore G. But in the current scenario, let's assume the fork choice rule indicates that G is the better head block.
Blocks D, E, and F are not ancestors of block G, so they need to be removed from the node's canonical chain. Any transactions or information contained in these blocks will be rolled back as if they were never received. The node must completely roll back to process the state after block B.
After rolling back to block B, the node can add blocks C and G to its chain and process them accordingly. Once done, the node has completed the reorganization of its chain.
Later, a block H may appear built on top of block F. If the fork choice rule indicates that the new head block should be H, the node will perform another reorganization, rolling back to block B and establishing the blocks on branch H.
In proof of work and Ethereum's proof of stake protocols, brief reorganizations of one or two blocks are not uncommon due to network propagation delays. Unless the chain is under attack, or there are flaws in the formulation of the fork choice rule or its client implementation, very long reorganizations should be extremely rare.
Security and Liveness
When discussing consensus mechanisms, two important concepts often come up: security and liveness.
Security
Informally, an algorithm is considered secure if "bad things don't happen" [5].
Examples of bad things that could happen in a blockchain environment include cryptocurrency double-spending or conflicting finalizations of checkpoints.
An important aspect of security in distributed systems is "consistency." That is, if we ask different (honest) nodes about the state of the chain at a certain point of progress, such as the balance of an account at a specific block height, we should always get the same answer regardless of which node we ask. In a secure system, every node has an unchanging, consistent view of the history of the chain.
In practice, security means that our distributed system "behaves like a centralized instance, performing only one atomic operation at a time" (quoted from Castro and Liskov). In Vitalik's centralization spectrum, a secure system is logically centralized.
Liveness
Again informally, an algorithm is considered to have liveness if "good things eventually happen".
In a blockchain environment, this is often understood to mean that the chain can always add a new block; it never gets stuck in a state where it cannot produce a new block containing transactions.
"Availability" is another way to look at this issue. I want the chain to be available, which means that if I send a valid transaction to an honest node, it will eventually be included in a block extending that chain.
Both cannot be achieved at the same time!
The CAP theorem is a famous result in distributed systems theory, stating that no distributed system can simultaneously provide (1) consistency, (2) availability, and (3) partition tolerance. Partition tolerance refers to the ability to continue functioning when communication between nodes is unreliable. For example, network failures may divide nodes into two or more groups that cannot communicate with each other.
It is easy to demonstrate the CAP theorem in the context of blockchain. If the Amazon Web Services (AWS) goes offline, causing all nodes hosted by AWS to be able to communicate with each other but not with the outside world, or if a country blocks all incoming and outgoing connections, preventing any gossip traffic from passing through, both scenarios would divide the nodes into two unrelated groups, A and B.
Suppose an account connected to group A sends a transaction. If the nodes in group A process the transaction, their final state will be different from the nodes in group B who did not see the transaction. Therefore, overall, we lose consistency among all nodes, and thus lose security. The only way to avoid this situation is for the nodes in group A to refuse to process the transaction, in which case we lose availability and liveness.
In summary, the CAP theorem implies that we cannot expect to design a consensus protocol that is both secure and live under all circumstances, as we have no choice but to operate on an unreliable network, i.e., the internet [6].
Ethereum Prioritizes Liveness
In favorable network conditions, the Ethereum consensus protocol can provide both security and liveness simultaneously, but in less smooth network operations, it prioritizes liveness. In the case of network partition, nodes on both sides of the partition will continue to produce blocks. However, finality (a property of security) will no longer occur on both sides of the partition. Depending on the staking ratio managed on both sides, either one side will continue to achieve finality, or neither side will continue to achieve finality.
Ultimately, unless the partition is resolved, both sides will regain finality due to a novel inactivity leak mechanism. However, this will ultimately lead to a security failure. Each chain will ultimately determine a different history, and the two chains will become irreconcilable and independent.
Finality
We will discuss finality extensively in the following chapters, as it is a property of the security of the chain.
Finality refers to some blocks never being rolled back. When a block is finalized, all honest nodes on the network agree that the block will remain in the chain's history forever, and therefore all of its ancestors will also remain in the chain's history. Finality makes your pizza payment irreversible, just like using cash. This is the ultimate protection against double-spending [7].
Some consensus protocols, such as the classic PBFT or Tendermint, finalize every round (every block). Once a round of transactions is included in the chain, all nodes agree that it will exist forever. On one hand, these protocols are very "secure": once a transaction is included in the chain, it will never be rolled back. On the other hand, they are prone to liveness failures: if nodes cannot reach consensus—e.g., if more than one-third of the nodes are shut down or unavailable—then no transactions can be added to the chain, and the chain will stop running.
Other consensus protocols, such as Bitcoin's Nakamoto consensus, have no finality mechanism at all. There is always the possibility of someone presenting an alternative chain with more accumulated work. When this happens, all honest nodes must reorganize their chains accordingly, rolling back any transactions they processed before. Heuristic methods such as the number of confirmations your block has are just approximations of finality and cannot be guaranteed [8].
Ethereum's consensus layer prioritizes liveness but also strives to provide security guarantees in a finality-like manner in favorable conditions. This is an attempt to have the best of both worlds. Vitalik defends this as follows [9]:
The general principle is that you want to give users "as much consensus as possible": if > 2/3 of the nodes reach consensus, then we get regular consensus. But if < 2/3, there's no need to stop and do nothing, obviously, even though the security of new blocks is temporarily reduced, the chain can still continue to grow. If individual applications are not satisfied with the lower security level, they are free to ignore those blocks until they are finalized.
In Ethereum's consensus layer, finality is provided by the Casper FFG mechanism, which we will explore soon. The idea is that all honest validators regularly agree on recent checkpoint blocks, and they never revert these blocks. Then, the block and all its ancestor blocks are "finalized"—they will never change, and if you ask any honest node on the network about them or their ancestor blocks, you will always get the same answer.
Ethereum's finality is "economic finality." In theory, the protocol could finalize two conflicting checkpoints, i.e., two contradictory views of the chain's history. However, this is only possible at a huge and quantifiable cost. Except for the most extreme attack or failure scenarios, finality is final.
The Casper FFG section delves into the workings of this finality mechanism.
See Also
Anything involving Leslie Lamport is always worth reading, and the original 1982 paper "The Byzantine Generals Problem" co-authored by him, Shostak, and Pease contains many insights. While their proposed algorithm is highly inefficient under today's conditions, the paper is a great introduction to reasoning about general consensus protocols. The groundbreaking 1999 paper "Practical Byzantine Fault Tolerance" by Castro and Liskov also had a significant impact on the design of Ethereum's Casper FFG protocol. However, you might want to contrast these "classic" approaches with the elegant simplicity of the proof of work described by Satoshi Nakamoto in the 2008 Bitcoin whitepaper. If there is any advantage to proof of work, it is its simplicity.
We mentioned the 2012 paper "Perspectives on the CAP Theorem" by Gilbert and Lynch. This paper provides a deep exploration of the concepts of consistency and availability (or security and liveness in our context) and is highly readable.
Due to differences in fork choice rule client implementations, the Ethereum beacon chain experienced a reorganization of seven blocks in May 2022. These differences were known at the time and were considered harmless. It turned out not to be the case. Barnabé Monnot's description of this event is very insightful.
Vitalik's blog post "On Settlement Finality" provides a deeper and more detailed exploration of the concept of finality.
For the systems we are building, our ideal is that they are politically decentralized (to achieve permissionless and censorship resistance), architecturally decentralized (to achieve resistance to single points of failure), but logically centralized (to achieve consistent results). These standards have a significant impact on how we design consensus protocols. Vitalik explores these issues in "The Meaning of Decentralization".
免责声明：本文章仅代表作者个人观点，不代表本平台的立场和观点。本文章仅供信息分享，不构成对任何人的任何投资建议。用户与作者之间的任何争议，与本平台无关。如网页中刊载的文章或图片涉及侵权，请提供相关的权利证明和身份证明发送邮件到support@aicoin.com，本平台相关工作人员将会进行核查。
