Twitter | Search | |
vitalik.eth
1. Today I am going to make a tweet storm explaining the history and state of Ethereum's Casper research, including the FFG vs CBC wars, the hybrid => full switch, the role of randomness, mechanism design issues, and more.
Reply Retweet Like More
vitalik.eth 15 Aug 18
Replying to @VitalikButerin
2. Ethereum proof of stake research began in Jan 2014 with Slasher (). Though the algorithm is highly suboptimal, it introduced some important ideas, most particularly the use of penalties to solve the nothing at stake problem ().
Reply Retweet Like
vitalik.eth 15 Aug 18
Replying to @VitalikButerin
3. That said, the penalties that I used were very small, only canceling out signing rewards. Vlad Zamfir joined in mid-2014, and he quickly moved toward requiring validators to put down *deposits*, much larger in size than rewards, that could be taken away for misbehavior.
Reply Retweet Like
vitalik.eth 15 Aug 18
Replying to @VitalikButerin
4. Here's Vlad's retelling:
Reply Retweet Like
vitalik.eth 15 Aug 18
Replying to @VitalikButerin
5. We spent much of late 2014 trying to deal with "long range attacks", where attackers withdraw their stake from deposits on the main chain, and use it to create an alternate "attack chain" with more signatures than the main chain, that they could fool clients into switching to.
Reply Retweet Like
vitalik.eth 15 Aug 18
Replying to @VitalikButerin
6. If the attack chain diverges from the main chain at a fairly recent point in time, this is not a problem, because if validators sign two conflicting messages for the two conflicting chains this can be used as evidence to penalize them and take away their deposits.
Reply Retweet Like
vitalik.eth 15 Aug 18
Replying to @VitalikButerin
7. But if the divergence happened long ago (hence, long range attack), attackers could withdraw their deposits, preventing penalties on either chain.
Reply Retweet Like
vitalik.eth 15 Aug 18
Replying to @VitalikButerin
8. We eventually decided that long range attacks are unavoidable for pretty much the reasons PoW proponents say (eg. ). However, we did not accept their conclusions.
Reply Retweet Like
vitalik.eth 15 Aug 18
Replying to @VitalikButerin
9. We realized that we could deal with long range attacks by introducing an additional security assumption: that clients log on at least once every four months (and deposits take four months to withdraw), and clients simply refuse to revert further than that.
Reply Retweet Like
vitalik.eth 15 Aug 18
Replying to @VitalikButerin
10. This was anathema to PoW proponents because it feels like a trust assumption: you need to get the blockchain from some trusted source when you sync for the first time.
Reply Retweet Like
vitalik.eth 15 Aug 18
Replying to @VitalikButerin
11. But to us dirty subjectivists, it did not seem like a big deal; you need some trusted source to tell you what the consensus rules of the blockchain are in any case (and don't forget software updates), so the additional trust required by this PoS assumption is not large.
Reply Retweet Like
vitalik.eth 15 Aug 18
Replying to @VitalikButerin
12. Here's Vlad's retelling:
Reply Retweet Like
vitalik.eth 15 Aug 18
Replying to @VitalikButerin
13. Now that we settled on deposits and penalties, we had to decide what those deposits and penalties _are_. We knew that we wanted an "economic finality" property, where validators would sign on blocks in such a way that ...
Reply Retweet Like
vitalik.eth 15 Aug 18
Replying to @VitalikButerin
14 ...once a block was "finalized", no _conflicting_ block could be finalized without a large portion of validators having to sign messages that conflict with their earlier messages in a way that the blockchain could detect, and hence penalize.
Reply Retweet Like
vitalik.eth 15 Aug 18
Replying to @VitalikButerin
15. I went on a big long, and ultimately unproductive, tangent on a direction I called "consensus by bet":
Reply Retweet Like
vitalik.eth 15 Aug 18
Replying to @VitalikButerin
16. Consensus by bet was an interesting construction where validators would make bets on which block would be finalized, and the bets themselves determined which chain the consensus would favor.
Reply Retweet Like
vitalik.eth 15 Aug 18
Replying to @VitalikButerin
17. The theory was that PoW also has this property, as mining is a bet where if you bet on the right chain, you gain (reward - mining cost), and if you bet on the wrong chain, you lose the mining cost, except with PoS we could push the odds on the bets much higher.
Reply Retweet Like
vitalik.eth 15 Aug 18
Replying to @VitalikButerin
18. The odds on validators' bets would start off low, but as validators saw each other getting more and more confident about a block, everyone's odds would rise exponentially, in parallel, until eventually they would bet their entire deposits on a block. This would be "finality".
Reply Retweet Like
vitalik.eth 15 Aug 18
Replying to @VitalikButerin
19. In the meantime, Vlad started heavily researching mechanism design, particularly with an eye to making Casper more robust against oligopolies, and we also started looking at consensus algorithms inspired by traditional byzantine fault tolerance theory, such as Tendermint.
Reply Retweet Like
vitalik.eth 15 Aug 18
Replying to @VitalikButerin
20. Vlad decided that traditional BFT was lame (he particularly disliked hard thresholds, like the 2/3 in PBFT and Tendermint), and he would try to effectively reinvent BFT theory from scratch, using an approach that he called "Correct by Construction" (CBC)
Reply Retweet Like
vitalik.eth 15 Aug 18
Replying to @VitalikButerin
Reply Retweet Like
vitalik.eth 15 Aug 18
Replying to @VitalikButerin
22. The correct-by-construction philosophy is very different from traditional BFT, in that "finality" is entirely subjective. In CBC philosophy, validators sign messages, and if they sign a message that conflicts with their earlier message...
Reply Retweet Like
vitalik.eth 15 Aug 18
Replying to @VitalikButerin
23 ... they have to submit a "justification" proving that, in the relevant sense, the new thing they are voting for "has more support" than the old thing they were voting for, and so they have a right to switch to it.
Reply Retweet Like
vitalik.eth 15 Aug 18
Replying to @VitalikButerin
24. To detect finality, clients look for patterns of messages that prove that the majority of validators is reliably voting for some block B in such a way that there is no way they can switch away from B without a large fraction of validators "illegally" switching their votes.
Reply Retweet Like
vitalik.eth 15 Aug 18
Replying to @VitalikButerin
25. For example, if everyone votes for B, then everyone votes on a block that contains everyone's votes for B, that proves that they support B and are aware that everyone else supports B, and so they would have no legitimate cause for switching to something other than B.
Reply Retweet Like
vitalik.eth 15 Aug 18
Replying to @VitalikButerin
26. I eventually gave up on consensus-by-bet because the approach seemed too fundamentally risky, and so I switched back to trying to understand how algorithms like PBFT work. It took a while, but after a few months I figured it out.
Reply Retweet Like
vitalik.eth 15 Aug 18
Replying to @VitalikButerin
27. I managed to simplify PBFT () and translate it into the blockchain context, describing it as four "slashing conditions", rules that state what combinations of messages are self-contradictory and therefore illegal:
Reply Retweet Like
vitalik.eth 15 Aug 18
Replying to @VitalikButerin
28. I defined a rule for determining when a block is finalized, and proved the key "safety" and "plausible liveness" properties: (i) if a block is finalized, then there is no way for a conflicting block to get finalized without >= 1/3 violating a slashing condition ...
Reply Retweet Like
vitalik.eth 15 Aug 18
Replying to @VitalikButerin
29. ... (ii) if a block is finalized, 2/3 honest validators can always cooperate to finalize a new block. So the algorithm can neither "go back on its word" nor "get stuck" as long as > 2/3 are honest.
Reply Retweet Like
vitalik.eth 15 Aug 18
Replying to @VitalikButerin
30. I eventually simplified the minimal slashing conditions down from four to two, and from there came Casper the Friendly Finality Gadget (FFG), which is designed to be usable as an overlay on top of any PoW or PoS or other blockchain to add finality guarantees.
Reply Retweet Like
vitalik.eth 15 Aug 18
Replying to @VitalikButerin
31. Finality is a very significant advancement: once a block is finalized, it is secure regardless of network latency (unlike confirmations in PoW), and reverting the block requires >= 1/3 of validators to cheat in a way that's detectable and can be used to destroy their deposits
Reply Retweet Like