Vitalik: Casper FFG and Casper CBC's Yu Qing Complex

Editor's Note: This article is a translation of Qiu Jun, a member of the Taipei Ethereum Meetup community. Translated from August 2018, Vitalik introduced the long tweet of Casper's development. Over the course of the year, Eth2.0's fork selection rule has been identified as LMD Ghost, rather than Vitalik's preferred IMD Ghost in the long tweet, but the history of Casper's conception mentioned in the article is still a good one.

Foreword

 

Ethereum's research on the PoS consensus model began in 2014, and these studies later evolved into the well-known Casper the Fridenly Finality Gadget (FFG) / Correct by Construction (CBC) consensus models, which are composed of two different teams. There are many differences in development. Vitalik used a series of tweets to outline the development of Casper since 2014. Since the Chinese community still lacks a summary of the Casper development route, the translator has translated this series of tweets into Chinese and added some annotations. Can be an important document for developers or researchers in learning Casper, and expect readers to have a more intuitive understanding of Casper design philosophy.

• QKL123 market analysis | Bitcoin is good for the upside, the cottage is not good (0904)
• Three of the world's top 10 banks are their customers, and Baton, a “blocked” blockchain project, received $12 million in Series A financing.
• Thinking about how to invest in the Internet, blockchain and digital currency in the next decade from Web 3.0

In order to avoid blunt reading, readers are advised to master the important concepts of PBFT / Casper FFG / GHOST. The PBFT part can refer to the translator's article: If you want to understand the blockchain, you can't ignore the classic: PBFT. Finally, I would like to especially thank Chih-Cheng Liang, a researcher at the Ethereum Foundation, for providing a lot of materials and assistance in reviewing.

The following text begins.

Introduction

 

I will use a series of tweets to explain the research history/series/progress of the Ethereum Casper Consensus Agreement, including the FFG vs CBC debate, the transition from a hybrid model to a full PoS, the role of randomness, the design considerations of consensus mechanisms, and Other issues.

Disinterested issues and remote attacks

Ethereum's proof of equity study began in January 2014 with the Slasher Agreement. Although the Slasher algorithm is not very ideal, it introduces some important concepts, especially the use of fines to solve the " Nothing-at-Stake Problem ". However, the fines I use are quite small and I only cancel the voting award. Vlad Zamfir joined in mid-2014 and he quickly introduced a method for the verifier to deposit. The deposit is a larger number than the reward, and the wrong behavior will cause the deposit to be taken away (here is a remark from Vlad).

We spent most of the second half of 2014 trying to solve the " Long-Range Attack ", which allowed attackers to withdraw their deposits from the main chain and form another attack chain with more signatures. So deceive the newly added nodes and let them think that the attack chain is a main chain. If the attack chain and the main chain are at a fairly close point from the current time, the attack chain will not cause problems, because if the verifier simultaneously signs two conflicting messages on both links, the signature can be regarded as a penalty verifier. Evidence to confiscate the deposit; but if the fork occurred long ago (hence the name of a ranged attack), the attacker could take the deposit to avoid being confiscated.

We conclude that remote attacks are unavoidable for roughly the same reasons as PoW advocates say. However, we did not accept their conclusions. Because we found that we can introduce two additional security assumptions to solve the remote attack: 1. The node has to log in at least once every 4 months (the deposit takes 4 months to withdraw); 2. The node directly rejects more than 4 months. Backtracking.

This is a disgusting thorn in the PoW advocates because it feels like a "trust assumption": every time you sync a block, you must trust a source to get the blockchain. But for our embarrassing subjectivists, this is not a big problem: in either case, you need a trusted source to tell you the consensus rules used by the blockchain (and don't forget the software update) So the extra trust required for PoS is not that great (here is a retelling of Vlad).

Once the deposits and fines have been established, we will decide what they are. We know that what we want is " economicality, " and the verifier will sign the block based on the following: Once a block is finalized, if a conflicting block is to be finalized, most of the verifiers must be signed. A message that conflicts with your previous message. But for such a message, it can be detected and punished by the chain.

I wrote a "Bet Consensus" article that is stinky, long and digressive. The bet consensus is an interesting proposal: the verifier bets which block will be finalized, and the bet determines which chain will form a consensus. PoW also has this property because mining is a bet. If you bet on the right chain, you will be rewarded; if you bet on the wrong chain, you lose the cost of mining. But at PoS we can have higher odds: the verifier's odds are low at first, but as the verifiers see each other's confidence in a certain block gradually increase, everyone's odds will rise in parallel. Until everyone is betting on the same block, this is the finalization.

Casper CBC

 

At the same time, Vlad began a lot of research on mechanism design, especially to make Casper more resistant to oligopoly. We also began to study consensus inspired by classical Byzantine fault tolerance (BFT), such as Tendermint. Vlad thinks that classical BFT is not convincing (he particularly dislikes the hard threshold of BFT, for example, 2/3 of PBFT nodes must be honest nodes), he wants to call him a "Correct by Construction (CBC)" The way to try to reinvent BFT (Vlad's original words: link 1 / link 2 / link 3).

The reason why the correctly constructed philosophy is quite different from the traditional BFT is that "finalization" is completely subjective. The philosophy of the CBC is that the verification node signs the message, and if they sign a message that conflicts with their previous message, they must submit a "Justification" to prove that the new message they voted is compared to the old one. There is more support under it to get the right to "convert".

In order to detect the finalization, the node seeks the mode of the message. These messages can prove that most verification nodes vote for a block B reliably in a way that deviates from B and most of the verifiers illegally convert votes. For example, if all nodes vote for B, then all nodes vote for "blocks that contain everyone's votes on B." This proves that they support B and know that everyone else supports B, so they won't convert. Legal reasons.

Finally, I gave up the bet consensus because this approach seems to be fundamentally risky. I also tried to understand how PBFT works. Although it took a little while, I understood it after a few months.

Casper FFG

 

I tried to simplify the PBFT, put it into the context of the blockchain, and describe it as four "Slashing Conditions", which spell out which combinations of messages are self-contradictory and therefore violate the rules. I define the rules that determine whether a block is finalized and prove the most critical " Safety " and " Plausible Liveness ": 1. If a block is finalized, it cannot be less than 1/3 The verifier violates the cut deposit condition to finalize another conflicting block; 2. If a block is finalized, 2/3 honest verifiers can always cooperate to finalize the new block. So as long as there are 2/3 honest verifiers, the algorithm won't overturn the previous decision (security) or stuck (active). In the end, I reduced the deposit deposit condition from 4 to 2 and developed it into Casper FFG – designed to provide a finalized overlay for any PoW/PoS/other type of blockchain.

Finalization is a very important development: once the block is finalized, no matter how delayed the network is, it is guaranteed to be safe (unlike PoW requires multiple block acknowledgments), and the backtracking block requires more than 1/3 of the certifiers to cheat. It was detected and the deposit was destroyed. Therefore, the cost of retrospective finalization can be as high as hundreds of millions of dollars. In different ways, Casper CBC and FFG have achieved this feature.

It should be noted that both Casper CBC and FFG are abstract overlays that need to be built on top of an existing fork selection rule. In the vernacular, the Casper CBC is the finalized layer (upper layer) adapted to the fork selection rule (lower layer); the Casper FFG is the forked selection rule (lower layer) adapted to the finalized overlay (upper layer).

FFG vs CBC

 

Vlad's initial preference for the fork selection rule was "Latest Message-Driven GHOST (LMD GHOST)" – a modified GHOST for PoS; my initial preference was to take "PolyPoS" (Hybrid) PoS) ", using PoW as the base for the fork selection rule.

In the original version of FFG, PoW will operate a chain block by block, and PoS will follow the block immediately; Casper CBC is the complete PoS from the beginning. At the same time, Vlad and I each proposed the theory of consensus incentives.

One very important difference here is "Uniquely Attributable Faults" – you can know who is responsible and penalized when something goes wrong, and "Non-uniquely Attributable Faults" – A mistake may be caused by one of the parties. A classic case of non-unique accountable error is offline vs. censorship, also known as "talker-listener error equivalence" (translation: whether the speaker did not speak, or the listener did not hear, Unable to determine who is wrong).

It is easy to punish the only blameworthy error (Casper FFG cut deposit conditions); it is difficult to punish non-uniquely blameable errors. What if you can't tell if a block stops finalizing because a few nodes are offline or because most nodes are blocking a few? There are currently three solutions to this topic: 1. Slightly punishing both sides; 2. Severely punishing both sides (Vlad's preference); 3. Dividing the chain into two, each punishing one side of the two chains, and letting the market decide which Chains are more valuable (my preference). Or you can refer to this one I wrote.

In November 2017, I cut the deposit conditions for Casper FFG and the 1/3 node due to "Quadratic Leak" due to the increase in the amount of deduction for the deposit as the offline time increases. The solution to the offline problem is written into a thesis.

Of course, I know very well that resorting to the social level to solve 51% attacks is not very good, so I started to find ways to at least allow the nodes on the chain to automatically detect the "legal chain" and "attack chain". This is an early idea. This idea is not bad, but it is still not optimal. Unless there is no delay in the network, it can only guarantee the upper limit of the difference in suspect scores between nodes, and not all nodes fully agree.

At the same time, my main critique of Vlad's model is related to "Discouragement Attacks", which can effectively threaten to create 51% of attacks to cause everyone to lose money, thus driving all others to quit, so only very low The cost can dominate the chain. Vlad (and Georgios Piliouras) began to build an economic model to assess the actual cost of doing the above attack under his model.

It is worth mentioning that all of the above issues are not unique to PoS. In fact, in PoW, people tend to give up directly and assume that it is almost impossible to prevent 51% of attacks, and 51% of attacks are the last days that must be avoided at all costs. However, like the tradition of Ethereum, Vlad and I mistakenly regard the word "ambitious" as a compliment, and continue to study different ways of slowing down and restoring 51% of attacks.

At the beginning of 2018, Vlad's research at CBC began to advance rapidly, including the progress of safety certification. – Looking at this epic 2-hour newsletter to keep up with the research progress as of March 2018, Casper FFG has also made significant progress, and the decision to implement the contract makes the development work easier. On December 31, 2017, we released the Python version of the test network.

Casper integration with the shard development route

 

Unfortunately, the development of FFG has slowed down. Implementing FFG with contracts While making things easier, it makes it harder to move from EVM to EWASM and from single-chain Casper to Casper. In addition, the team's research and development work is divided into "main chain Casper" and "segment chain Casper", it is conceivable that a lot of unnecessary duplication of work between the two teams.

In June 2018, we made a major decision: to abandon the contract-implemented Casper FFG, and instead to pursue a Casper that operates in a separate chain, such a design would make sharding easier.

The conversion of full PoS led me to think more seriously about PoS's fork selection rules. Both Casper FFG and CBC require all verification nodes to vote at each Epoch to finalize the block, which means that tens of thousands of signatures are sent to each verification node per second. BLS signature aggregation makes it feasible in terms of computational cost. But I want to try to use these extra signatures to make the chain more stable and get the security equivalent to "100 acknowledgments" in a matter of seconds. Here is my initial thought (link 1 / link 2).

However, all of these methods of fork selection have one drawback: they all divide the verification nodes into "Attesters" and "Proposers", and these are the nodes that are responsible for generating the blocks. Big power. This is not very good, mainly because it requires us to have a very secure random number generator on the chain to pick out the block nodes fairly, and the random number generator on the chain is difficult, and some simple methods such as RANDAO seem to have More and more problems. Justin Drake and I started to solve this problem: Justin uses VDF, which is a function with deterministic and verifiable output, but requires a large number of non-parallelizable sequence times to perform operations, making it impossible to change ahead of time; Vlad teaches compromises, using GHOST-based fork selection rules to significantly reduce reliance on outbound nodes, allowing chains to grow undisturbed with malicious outbound nodes greater than 90% and honest witness nodes greater than 50%. . Vlad is very happy, but still not happy: he prefers LMD GHOST, and I prefer IMD GHOST.

At about the same time, I also tried to come up with a way to "pipelining" the Casper FFG, reducing the finalization time from 2.5 periods to the theoretically optimal 2 periods. I am happy that the RPJ fork selection rule (later renamed IMD GHOST) is well compatible with FFG. It also has a very important "stability": fork selection is a good predictor of future fork selection. This seems obvious, but it's easy for us to make a fork rule that doesn't have this feature. Recent developments are: LMD GHOST may only be 25% fault tolerant in 2 rounds due to technical details, but IMD GHOST can still have a full 33% fault tolerance (currently no documentation). (Translated by: When the translation is completed, Ethereum 2.0 uses LMD GHOST)

The main trade-off between FFG and CBC is that CBC seems to have a good theoretical nature; FFG seems to be easier to implement. At the same time, VDF has made a lot of progress.

Also, I recently decided to study Leslie Lamport's 1982 old paper, in which he proposed a consensus algorithm: if all nodes, including observers, are assumed to be online and have very low network latency, then 99% fault tolerance. The assumption of network latency is logically unsuitable as a primary consensus algorithm. However, it can work quite well in a situation: as a suspected score alternative to 51% mask detection: Basically, if 51% of the conspiracy groups start blocking blocks, other verification nodes and general nodes can detect the masked Occurs and uses a 99% fault-tolerant consensus algorithm to achieve the consensus that is being masked and to coordinate minority forks. The long-term goal of this research is to minimize the reliance on the social layer and maximize the cost of disrupting chain stability, minimizing the possibility of using social layer backtracking.

What else? Part of the FFG also has formal proofs, complete specifications, and continuous progress in implementation (more than 3 teams have started!) with a focus on safe and rapid development. The parts of the CBC are similar. Let's go ahead!

(Finish)

(A lot of hyperlinks are provided in the article, please click to read the original text to get the EthFans website)

Original link:

Https://medium.com/taipei-ethereum-meetup/history-and-state-of-ethereums-casper-research-85e8fba26002

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!