Popular Science | Casper FFG: A Consensus Agreement Targeting Equity Proof

Foreword

 

In 2017, Vitalik Buterin and Virgil Griffith jointly published Casper the Friendly Finality Gadget (Casper FFG) . Casper FFG is a PBFT-inspired and improved consensus protocol. Although it is designed to be simple , its proof of security is not simple (Easy) .

The author will analyze the principle of Casper FFG in this paper. The reader can get a glimpse of the problems and design concepts that the proof of equity has tried to solve. In addition, Casper FFG is a consensus mechanism of Ethereum 2.0. Understanding its operation can also help researchers and developers to further understand the design of Ethereum 2.0.

Finally, I would like to especially thank Ethereum researcher Chih-Cheng Liang (Liang Zhicheng) for providing important materials and discussing and giving back with the author. Without his help, there will be no such article.

• How much decentralization is “decentralized finance”?
• Telegram blockchain network will be compatible with Ethereum
• EU Commission confirms preliminary antitrust investigation of Facebook's Libra

How did Casper FFG start?

Ethereum's Proof-of-Stake (PoS) study dates back to the 2014 article. Since then, Ethereum researchers have been moving towards the goal of "realizing a PoS-based consensus agreement." The design of the PoS Consensus is a cross-cutting and rather complex issue involving computer science/economics/cryptography. Ethereum has the most cross-disciplinary team in the blockchain ecosystem, and the research on PoS can be quite thorough.

The author recently translated an important document about the development of Casper FFG:

Casper FFG and Casper CBC's Yu Qing complex

Casper FFG is inspired by PBFT and can be seen as an improved PBFT – it inherits the important design of PBFT while adding new mechanisms and simplifying several rules. If the reader is unfamiliar with PBFT, you can refer to the author's previous analysis of PBFT:

If you want to understand the blockchain, you can't ignore the classic: PBFT

In short, PBFT is a consensus agreement with a two-round voting mechanism with the following characteristics:

• Permissioned : Only nodes that are "allowed" can participate in the consensus.
• Leader-based : Only the dominant node is responsible for Propose. Other nodes are only responsible for voting. Therefore, the View Change mechanism is needed to control the dishonest dominant node.
• Communication-based : Use a deterministic majority to form a consensus rather than a non-Deterministic quiz.
• Safety-over-Liveness : The protocol guarantees the security of the consensus (ie, no fork) regardless of the delay of the network, which gives the Instant Finality of the protocol.

The immediate finalization of PBFT may be the main reason why it is favored by Vitalik. Vitalik also wrote a summary after reading PBFT, and proposed important ideas that evolved into Casper FFG in the future.

Predecessor of Casper FFG: 4 rules for cutting deposits

Although PBFT has immediate finalization, it does not have the ability to resist collusion. Therefore, it needs a punishment mechanism to curb evil behavior. As long as the node makes the rule of overstepping, it must bear economic losses – through economic law. Adjusting the behavior of the node is the design philosophy of PoS . Any node that pays the deposit can join the network to participate in the consensus, without anyone's permission, so the consensus based on the PoS model is non-licensed (Permissionless).

Here is a clarification of the "license". We will say that he is "non-licensed" because any verification node can join and quit. But if he wants to maintain a list of verification nodes when he joins, from this point of view it is a bit of a "licensing system." From the perspective of PBFT, the voting verification node must also be selected from the list of licenses.

Then the next question is: Which actions should be punished ? Vitalik carefully scrutinized PBFT and found that PBFT requires only four rules (assertions in PBFT) to ensure that the consensus works well:

Minimum deposit conditions

Vitalik summarizes these four rules in this article and refers to them as PBFT's "Minimal Slashing Conditions". Any violation of these 4 rules will be taken away. The four rules are as follows:

  1. Commit (commit_req): Cannot submit after receiving the 2/3 node preparation message.  2. Prepare (prepare_req): Each preliminary message can only point to a height (Epoch) that also has 2/3 node preparation messages, and these preparation messages must all point to the same height.  3. Prepare commit consistency (prepare_commit_consistency): Any new prepared message can only point to the last submitted or other updated height.  4. Do not repeat preparation (no_double_prepare): Can not send two preparations at the same height. 

These 4 rules can be further reduced to 2:

  A verification node v must not issue two different votes: <ν, s1, t1, h(s1), h(t1)> and <ν, s2, t2, h(s2), h(t2)>, And make any of the following conditions true: 1. h(t1) = h(t2) ​​Verify that the node must not issue two different votes for a certain height.  2. h(s1) < h(s2) < h(t2) ​​< h(t1) Verify that the node must not cast a vote that is highly/circular around another voting height. 

These two rules are the minimum deposit conditions for Casper FFG.

How does Casper FFG work?

-Casper FFG: Checkpoint Tree –

Casper FFG is an overlay that abstracts the Block Proposing Mechanism and is only responsible for forming consensus. The blocking mechanism is implemented by the underlying chain, and the Block Proposal from the underlying chain is called Checkpoints . The checkpoints form a Checkpoint Tree . For example, the block hashes with heights of 0, 50, 100, and 150 are taken out to form a new tree, as shown in the figure above. The bottommost checkpoint is called the root checkpoint (Root).

Each node must send a vote to the checkpoint. The content of the vote is a link consisting of two checkpoints of different heights. The starting point of the link is low, called the source . The end of the link. The height is higher and is called the target . The node broadcasts the vote to the network and collects votes from other nodes at the same time. If the sum of the deposits of the nodes voting for a link L exceeds 2/3 of the total deposit, then L is called the absolute majority link (Supermajority Link) , denoted by s → t. For example, in the above figure, an absolute majority is formed between b1 / b2 / b3, which is represented by b1 → b2, b2 → b3.

Starting from the root checkpoint, if an absolute majority link is formed between the two checkpoints, the target of the link enters the "justified" state; and the link is established at the source of the "certified" status. Then enter the "Finalized" state; the root checkpoint is preset to the "certified" and "finalized" states. It can be seen that after each checkpoint, each checkpoint will be "Justify" and then "Finalize" , which is almost equivalent to PBFT's "preparation" and "submission". For example, in the branch on the right side of the above figure, r / b1 / b2 are both "finalized" and only b3 is "certified".

Then verify which nodes check the nodes to establish a link? Each node must follow the Fork Choice Rule to select the next checkpoint to be connected. The rule of Casper FFG is to select the checkpoint with the highest "certified" status .

-Casper FFG: Verify the fork caused by a large change in the set of nodes –

Since Casper FFG enables any node that deposits a deposit to become a verification node, the Validator Set dynamically changes over time. The node needs to wait for a period of time from exiting the network to taking out the deposit, which is called the Withdrawal Delay . Each checkpoint C has its corresponding Dynasty (Dynasty) , which is defined as the number of finalized checkpoints from the root checkpoint to C. For example, in the above figure, the dynasty number of b3 is 3. Each generation of checkpoints corresponds to two sets of verification nodes: a front-end (Front) verification node set (including the nodes joined by this generation) and a back-end (Rear) verification node set (including the nodes exited by this generation). In theory, the front-end/back-end collection of each generation of checkpoints is highly repetitive, but it is difficult to ensure that the nodes collude to cause a large change in the front-end/back-end collection. If this happens, the deposit of the bad node may not be cut off when the error occurs (because A bad node has quit) causing security to be compromised. For example, in the above figure, verify that node A can exit, which means that A exits for C's fork (green), but for C fork (purple), A never quits. Therefore, A has the means to continue to invest in the old chain C, but the new chain C' can not cut the deposit of A (because it has been withdrawn).

In order to make every generation of checkpoints really blame when it goes wrong, the Stitching Mechanism is needed to "sew" the front/back collection of checkpoints to ensure that every error is blamed (the possibility of error) Is a front-end collection or a back-end collection).

In summary, Casper FFG has improved almost every aspect of PBFT:

• Economic constraints : PBFT is a licensing system that relies on organizations that already have a foundation of trust to run the agreement; Casper FFG is a non-licensing system that introduces at least a minimum deposit threshold and uses the risk of economic loss to constrain the behavior of the node. Nodes can be run together without any trust base between nodes to achieve true decentralization.
• Abstract block-out mechanism : PBFT relies on honest leader nodes to generate blocks and requires view-of-view transformation mechanism to control Byzantine nodes; Casper FFG does not need to pay attention to the underlying block-out mechanism, and only needs to be responsible for forming consensus. The advantage of the block abstraction is that the outbound frequency of the underlying chain does not have to be consistent with the consensus frequency of the overlay chain, which can increase efficiency and reduce the burden on the network. For example, only 1 checkpoint is generated for every 100 bottom blocks.
• Pipelined voting : PBFT has several kinds of voting messages such as < Prepare >, <Commit >, < View-change >; Casper FFG has only one < Vote > and the content of the voting is not a single block/request, but It's two checkpoints that form a link, which makes Casper FFG much simpler without sacrificing too much expressiveness. These checkpoints that form a chain structure will go through two rounds of voting at two different heights. Since each round of voting will finalize the source and the target, the consensus can be advanced as a pipeline. A similar design concept also appeared in Hot-Stuff. Interestingly, the author Dahlia Malkhi also wrote an article comparing Hot-Stuff with Casper FFG.
• Robust anti-aggression : PBFT does not have resistance to long-range attacks and Catastrophic Crash ; Casper FFG has a special mechanism to defend against these two attacks: for remote attacks, the node must Regularly sync blocks and Revert blocks that have been finalized; for catastrophic crashes, Casper FFG introduces the "Inactivity Leak" mechanism. For the description of these two attacks, the author will write another article in the future.

Due to the simplicity of the Casper FFG, the Ethereum researcher once implemented the contract version of Casper FFG:

However, this contract version of Casper FFG was later abandoned! In the contract version, it is assumed that voting can be processed in parallel, but there are many intermediate states in calculating voting returns. The order of different voting processes will affect the final state, which means that parallelization will not reach a consensus. To correct this problem, you must make a lot of changes in the contract and the client, and lose the spirit of "logic implementation with contracts, avoiding modification of the client." Therefore, in order to better integrate Casper FFG with other optimization proposals (such as shards), the new Ethereum 2.0 is debut.

Casper FFG in Ethereum 2.0

– Ethereum 2.0: Segmentation –

Ethereum 2.0 is a distributed ledger based on EVM and integrating Casper FFG with numerous optimization proposals (based on shards). In addition to implementing PoS, Ethereum 2.0 also attempts to expand the number of transactions per second (TPS) to the order of 10,000, making the blockchain an infrastructure such as the Internet, and allowing any 32 ethers to be stored. The node of the deposit of the currency can be the verification node.

Sharding is an important design to increase Scalability and is the most important goal of Ethereum 2.0. Fragmentation is a division of labor . We can use a simple example to illustrate the concept of fragmentation (the actual explanation is much more complicated than this): 2 people write 2 questions, 2 people write different questions and then combine It must be more efficient than writing 2 questions for each of the two people.

At present, Ethereum has only one blockchain, and all nodes must handle all transactions separately (as if 2 people have completed 2 jobs); in Ethereum 2.0, the network is divided into 1024 slices (Shard) , each running separately. A Shard Chain , which will process each part of the transaction and then submit the result to a Beacon Chain (as if the two people have different questions). Therefore, Ethereum 2.0 is expected to have 1 beacon chain and 1024 segmentation chains.

It is worth noting that a slice is an abstraction layer and does not specifically refer to a certain group of nodes . In order to understand this concept better, the author expands the above example: assuming that the homework has two steps of finding an answer and copying the answer , then A/B 2 people write 2 questions, and the fast reading A finds the answer to the first question. Read B with slow speed to find the answer to question 2; copy the answer to question 1 from B with fast hand speed , and copy the answer to question 2 with slow hand A. In this way, A / B can be responsible for the different steps of different topics according to the fast/slow of reading/writing.

Similarly, in Ethereum 2.0, in addition to 1024 slices, there will be 1024 Persistent Committees and 1024 Crosslink Committees:

• Each piece will correspond to 1 continuous committee and 1 cross-linking committee. As in the above example, each topic can correspond to different individuals according to the steps of reading/writing.
• Use the On-chain Random Number to determine the assignment of each committee, as in the previous example, assign the title according to the fast/slow read/write (the details of the implementation of the random number on the chain are left to be detailed later).
• The continuous committee is responsible for maintaining the fragmentation chain and generating the Shard Block . The Cross-Linking Committee is responsible for maintaining the beacon chain and generating the Beacon Block . As in the above example, it is responsible for finding answers and speed. Quickly responsible for copying the answer. The block node (Block Proposer) of each block is also determined by the random number on the chain.

In other words, each verification node needs to maintain one unique beacon chain and one fragmented chain of the belonging film, and will also belong to one cross-linking committee and one continuous committee corresponding to the fragment.

Casper FFG is an overlay chain running on Ethereum 2.0. This overlay chain is also composed of checkpoints. The span between checkpoints is called the period (Epoch) , and one period (Epoch) is cut into 64 periods (Slot). ) , each time period corresponds to 16 slices (16 = 1024 ÷ 64), so each slice has a corresponding time period in each period, and can only broadcast its vote on the checkpoint when it is its turn, and each minute The film can only cast 1 vote in one time period—that is, each slice needs to form a consensus on the content of the vote first, but the method of forming consensus within each film has not yet been finalized. The latest proposal is to use aggregated signature. In addition, Casper FFG's fork selection rule in Ethereum 2.0 is the latest message-driven GHOST (Latest-Message Driven GHOST, LMD GHOST) .

In theory, Casper FFG's vote at each checkpoint should be separated from the voting of the underlying block mechanism; in fact, the underlying voting content of Ethereum 2.0 will also contain top-level voting content (checkpoint links), like top-level voting The bottom-level voting Piggyback is used to optimize performance. So at the end of each period, each film receives votes from all other films during that period, and Casper FFG activity is maintained.

Conclusion

 

Casper FFG is a bold attempt to achieve a proof of equity, and its performance in Ethereum 2.0 is worth looking forward to. However, Ethereum 2.0 still has many problems to be solved, such as Light Client/On-chain Random Number Generator/Cross-shard Transaction. At the same time, many Ethereum 2.0 competitors have also proposed new consensus protocols and fragmentation technologies, such as RapidChain / Harmony / Chainspace and so on.

Casper FFG and Ethereum 2.0 are the result of continuous research and development by many researchers/developers, but there has been a lack of Chinese materials to provide systematic discussion. I hope this article can help researchers/developers in the Chinese world to quickly understand Casper FFG. Essentials with Ethereum 2.0. (Finish)

Original link:

Https://medium.com/taipei-ethereum-meetup/intro-to-casper-ffg-and-eth-2-0-95705e9304d6

Author: Juin Chiu

This article was first published in the Medium station of the Taipei Ethereum Meetup. EthFans was authorized to reprint. In order to comply with the habits of mainland readers, the simplified and traditional conversion was carried out and some terms were changed to idioms.

We will continue to update Blocking; if you have any questions or suggestions, please contact us!