Echo: The Yuliang Complex of Casper FFG and Casper CBC

Editor's Note: This article comes fromEthereum enthusiasts (ID: Ethfans)Editor's Note: This article comes from

This article is a translation by Qiu Jun, a member of the Taipei Ethereum Meetup community, from a long tweet by Vitalik introducing the development of Casper in August 2018. One year later, the fork selection rule of Eth2.0 has been determined to be LMD Ghost, not IMD Ghost, which Vitalik expressed his preference in this long tweet, but the evolution history of Casper mentioned in the article is still full of insights.

foreword

secondary title

foreword

The following text begins.

Introduction

Introduction

I will use a series of tweets to explain the research history/line/progress of the Ethereum Casper consensus agreement, including the FFG vs CBC debate, the conversion of the hybrid model to full PoS, the role of randomness, the design considerations of the consensus mechanism, and other issues.

secondary title

Nothing at stake and remote attacks

Proof-of-stake research in Ethereum started with the Slasher agreement in January 2014. Although the Slasher algorithm is not very ideal, it introduces some important concepts, especially the use of penalties to solve the "nothing-at-stake problem (Nothing-at-Stake Problem)". However, the penalties I've used are fairly minimal, just canceling voting rewards. Vlad Zamfir joined in mid-2014, and he quickly introduced the method of requiring validators to stake. The deposit is a larger number than the reward, and doing wrong actions will result in the deposit being taken away (Vlad's paraphrase here).

We spent most of the second half of 2014 trying to solve the "Long-Range Attack", where the attacker can withdraw their deposit from the main chain and form another attack chain with more signatures, In this way, newly joined nodes are deceived into thinking that the attack chain is a main chain. If the time point of the attack chain and the main chain fork is relatively close to the current time, the attack chain will not cause problems, because if the verifier signs two conflicting messages on both chains at the same time, this signature can be used as a punishment for the verifier evidence to forfeit the deposit; however, if the fork occurred a long time ago (hence the term remote attack), the attacker can withdraw the deposit to avoid forfeiture.

We concluded that long-range attacks are inevitable for roughly the same reasons as PoW proponents say. However, we did not accept their conclusions. Because we found that we can introduce two additional security assumptions to solve remote attacks: 1. Nodes must log in at least once every 4 months (the deposit takes 4 months to withdraw); Backtracking.

Having established the use of deposits and penalties, we next need to decide what they are. We know that what we want is "economic finality", and validators will sign blocks based on the following method: once a block is finalized, if a conflicting block is to be finalized, a majority of validators must sign Send out messages that conflict with your previous messages. But for such a message, it can be detected and punished by the chain.

Casper CBC

I wrote a stinking, long, and off-topic "Bet Consensus" article. Staking consensus is an interesting proposal: validators place a bet on which block will be finalized, and the stake determines which chain will reach consensus. PoW also has this property because mining is a staking. If you bet on the right chain, you get rewarded; if you bet on the wrong chain, you lose mining costs. But in PoS we can have higher odds: validators’ odds start low, but as validators see each other’s confidence in a block gradually increase, everyone’s odds increase exponentially in parallel , until everyone stakes the same block, this is finalized.

secondary title

At the same time, Vlad began to do a lot of research on mechanism design, especially making Casper more resistant to oligopoly. We also started working on 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 in BFT, for example, 2/3 of the PBFT nodes must be honest nodes), and he wants to use what he calls "Correct by Construction (CBC)" The method tries to reinvent BFT (Vlad's original words: link 1 / link 2 / link 3).

To detect finality, nodes look for patterns in messages. These messages can prove that a majority of validators reliably voted for some block B in one way, and that deviation from B required a majority of validators to switch votes illegally. For example, if all nodes voted for B, then all nodes voted for "the block containing everyone's vote for B", which proves that they support B and know that everyone else supports B, so they will have no conversion legal grounds.

Casper FFG

In the end I gave up on staking consensus because the approach seemed fundamentally risky. I also went back and tried to understand how PBFT works. It took a while, but after a few months I figured it out.

secondary title

Finalization is a very important development: once a block is finalized, it can guarantee security no matter how late the network is (unlike PoW, which requires multiple block confirmations), and the backtracking block requires more than 1/3 of the verifiers to cheat, and can is detected and the deposit is destroyed. As a result, the cost of retroactive finalization could run into the hundreds of millions of dollars. Both Casper CBC and FFG achieve this feature in different ways.

FFG vs CBC

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

secondary title

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

In the original version of FFG, PoW will run a chain block by block, and PoS will follow to finalize the block; Casper CBC is full PoS from the beginning. Meanwhile, Vlad and I each theorized about consensus incentives.

A very important distinction here is "Uniquely Attributable Faults" - you can know who is responsible when something goes wrong and get punished, and "Non-uniquely Attributable Faults" - An error may be caused by one of many parties. A classic case of a non-uniquely attributable error is offline vs shielding (Censorship), also known as "speaker-listener error equivalence". It is impossible to determine whose fault it is).

Punishing uniquely attributable errors (Casper FFG cuts the deposit condition) is easy; punishing non-uniquely attributable errors is hard. What if you couldn't tell if blocks stopped being finalized because a minority of nodes went offline or because a majority of nodes blocked a minority? There are currently three solutions to this issue: 1. Penalize both sides slightly; 2. Penalize both sides severely (Vlad's preference); 3. Split the chain into two, punish one side of the two chains each, and let the market decide which Chains are more valuable (my preference). Or you can refer to this article I wrote.

In November 2017, I cut the deposit condition of Casper FFG and the 1/3 node due to "Quadratic Leak" The solutions to offline problems are written as papers.

Of course, I am very aware that resorting to social aspects to solve 51% attacks is not very good, so I began to look for ways to at least allow nodes on the chain to automatically detect "legal chains" and "attack chains". This is an early idea. This is a good idea, but still suboptimal, unless the network is lag-free, it can only guarantee an upper bound on the difference in suspicion scores between nodes, and not all nodes fully agree.

It is worth mentioning that all the above issues are not unique to PoS. In fact in PoW, people tend to just give up and assume that preventing a 51% attack is next to impossible, and that a 51% attack is an apocalypse that must be avoided at all costs. However, as is the case with Ethereum, Vlad and I mistook the word "ambitious" for a compliment and continued to investigate different ways to mitigate and recover from 51% attacks.

In early 2018, Vlad's research at CBC began to advance rapidly, including the progress of safety proof. —Watch this epic 2-hour briefing to keep up with research progress through March 2018 In the meantime, Casper FFG has also made significant progress, and the decision to implement it by contract makes development easier. On December 31, 2017, we released the Python version of the testnet.

secondary title

Integration of Casper with the sharding development route

Unfortunately, development of FFG has slowed down. Although implementing FFG with contracts makes some things easier, it makes it more difficult to transfer from EVM to EWASM and from single-chain Casper to sharded Casper in the future. In addition, the team's R&D work is divided into "Main Chain Casper" and "Shard Chain Casper". It is conceivable that a lot of unnecessary duplication of work has occurred between these two teams.

In June 2018, we made a major decision: to abandon Casper FFG, which is implemented by contracts, and instead pursue Casper, which operates as an independent chain. Such a design will make sharding easier.

The switch to full PoS has caused me to start thinking more seriously about PoS's fork selection rules. Both Casper FFG and CBC require all verification nodes to vote in each "Epoch" to finalize a block, which means that tens of thousands of signatures are sent to each verification node every second. BLS signature aggregation makes it computationally cost feasible. But I want to try to use these additional signatures to make the chain more stable and achieve the security equivalent of "100 confirmations" in a few seconds. Here are my initial thoughts (link 1/link 2).

However, all these fork selection methods have a shortcoming: they all divide the verification nodes into "Attesters" and "Proposers", and these block producers who are responsible for generating blocks have big power. This is not very good, mainly because it requires us to have a very secure on-chain random number generator to pick out block nodes fairly, and on-chain random number generators are difficult, and some simple methods such as RANDAO seem to have More and more questions. Justin Drake and I set out to solve this problem: Justin uses VDF, which is a function with deterministic and verifiable output, but requires a large amount of non-parallelizable sequence time to operate, making early tampering impossible; Vlad teaches compromise, using GHOST-based fork selection rules to greatly reduce the dependence on block producers, allowing the chain to grow undisturbed when malicious block producers are greater than 90% and honest witness nodes are greater than 50% . Vlad is happy, but not overly happy: he prefers LMD GHOST, and I prefer IMD GHOST.

Around the same time, I was also trying to come up with a way to "pipelining" Casper FFG, reducing the finalization time from 2.5 epochs to a theoretical optimum of 2 epochs. I'm happy that the RPJ fork selection rule (later renamed IMD GHOST) works well with FFG. It also has a very important "stability": the fork choice is a good prediction of future fork choices. This seems obvious, but it's very easy to make fork rules that don't have this property. The latest progress is: LMD GHOST may only have 25% fault tolerance in 2 rounds due to technical details, but IMD GHOST can still have a full 33% fault tolerance (currently there is no document). (Translation: When the translation was completed, Ethereum 2.0 used LMD GHOST)

The main trade-off between FFG and CBC is: CBC seems to have better theoretical properties; while FFG seems easier to implement. At the same time, VDF has also made a lot of progress.