Towards a Practical CBC Casper

Transcript

next up I'd like to welcome a teacher a researcher at the etherion foundation to talk about towards CBC Casa hey guys welcome to my talk on towards practical CBC Casper I'm gonna be introducing some CBC concepts and then telling you why you should care about them I'll discuss a decent proposal for CBC and the beacon chain followed by some research updates

and then I'll roadmap so Casper correct by construction is not just a single consensus protocol it's this family of consensus protocols and they are characterized by having the same safety proof so we start from a minimal CBC protocol that we specify them further and further until we reach our requirements and since they've been formed from this master template we can be guaranteed that they satisfy the same safety proofs so just a little bit of background maybe 20 30 years ago consensus protocols were synonymous with traditional DFT techniques like pbft

there and more recently blockchain projects have started utilizing those in the form of Casper FFG and tender mint Bitcoin introduced a different class of consensus which is Nakamoto consensus or proof-of-work consensus and there is Casper CVC and maybe have lunch so Casper CVC is one of the families of consensus protocols that's suitable for proof of state cryptocurrencies and it's it's very different from traditional BFD techniques because it doesn't have any in protocol thresholds and well that leads to like severely different types of characteristics which we look into so

why should you care why should you care about for cbc at all well one thing that you may not have seen before is you have some degree of safety even if more than one-third of your nodes are faulty so well you mean you're not going to get this with any type of quorum intersection argument that PFD algorithms make so any type of 2/3 quorum kind of a thing is not going to get you safety if more than 1/3 nodes faulty and the second thing is we can tolerate up to 1/2 of line nodes or crash nodes but that's subject to ongoing research online the strategies more motivation the protocol is simple

it's it's not very complex to grasp it has very few working components and each of these components is formally defined and there are extensive proofs about its correctness and finally all of these protocols are correct by construction which means that small tweaks in how it works as long as you don't change the way that they are constructed it's not going to break consensus safety so that's that's a major advantage you can play around with it but you still have some strong guarantees all right so one of the major selling points of Kasper CVC is this subjective fault tolerance threshold which means that since there

is no in protocol threshold you can basically choose your desired level of safety on let's say blocks for for block chains so you know let's let's take an example here you have 5 validators and let's say you have two forks for zero and fork one and well here the red color represents a low level of certainty in that fork and green color here represents a high level of certainty and as vitalik presented in this talk in the morning this level of certainty is basically the number of people that have to break rules in order to propose something contradictory so you can see at at the beginning evaluators are

proposing ones Zero's and that goes on for quite a bit and all of this is in the red which means that you have no level of safety on on on these values on these values of zeros and ones as you progress further you can see that the network is kind of converging towards zero and lots of people are producing zeros and this orange and yellow color represents like an increasing level of safety and then finally you get to the green which is a very high degree of certainty now one important point is you know this may seem like Bitcoin where the more people mining on a for the the stronger that food becomes but it's it's not like

Bitcoin it's really deterministic there is no probabilistic kind of guarantees here it's completely deterministic and well the intuition behind this is a certain degree of common knowledge which increases in the network as more nodes start proposing the same things so let's talk about a recent proposal of incorporating CVC elements in the beacon chain so why would we want to do this why do we I mean we can chain is already a great proposal why do we want to incorporate any CVC elements well the beacon chain consensus has kind of two moving parts one of them is the finality

gadget and the other is the lmd ghost which is possible for short-term chain growth and the other is responsible for finalizing key box usually they you know play well together and like kind of fight together but under adverse conditions given the right kind of bad conditions things can go wrong so if you have for example a small militia stake like some bad Network latency you can actually pit them against each other and I'm going to show you one of the case so I'm picking this example from an e3 search post yeah so let's say you have two forks for K and for B and you come across this condition now note that this

condition in itself is is hard to reach you need like some really weird Network latency to make this happen but let's say that you do end up in this situation and you have three slots here the first slot has a 70/30 split the second one has 60 30 and this one has 60 30 as well so you can see that in round 2 and round 3 10 percent of the votes have not been made yet so we are going to assume that these are malicious woods who will vote late and try to kind of prevent finalization from happening and they will try to flip-flop the folk choice so as you can see here the latest justified block is in 4k leading to the 4 choice whenever being in 4k next the

10% malicious people actually do what and they vote for 4b and this leads to this being the latest justified block and then the 4s winner is in for P so we flip-flopped from 4k to 4 B and then we can actually make it happen again by voting on this block so the 10% malicious what's going to this and then the four choices for K again and actually this can go on for a sustained amount of time given that you have this really weird kind of network latency which allows for these conditions to arise so why Kasper CBC's is it really going to help to solve situations like this yes it is because the 4 choice is actually quite simple it's only LM d

cost and all these issues that arise due to you know chain growth issues between lmd and the finality gadget will be avoided but them but the biggest selling point would be that since there are very few number of rules the attack surface is lower and the security analysis is much easier so you can you can think of Kasper CBC for beacon chain as this lmd only proposal so why why wasn't it done already like what prevented it from being implemented already so well the problem is efficiency of lmd ghost over long

ranges so currently in the beacon chain you execute LM D goes for a height of like between two epochs so you don't really care about how efficient it is because it's maximum of just the range between two epochs but if you're going to do our MD Ghost only which means you're trying to execute it from Genesis till the tip it gets quite expensive very fast so this is Vitalik solution proposal which is called bitwise lnd ghost which proposes an efficiency improvement in executing their LMD ghost for choice and well it's really good because it's actually really close to the e 2.0 spec there there are very small deviations

and specifically the for choice rule becomes LMD ghost only you add some new attestation metadata to the state and there are new fashion conditions but it's just one slashing condition and this makes for a really good side project for client does if anyone wants to pick it up you can come and reach me or italic and it's you can find more information about this in the e 2.0 spec github issue 433 and 701 all right some research updates and how CVC is moving towards practicality so if I've shown you this diagram before this is the message structure that

clients observe so the clients have to detect safety for themselves so there are no thresholds there is no point at which you say okay I've seen 2/3 votes and now I'm deeming this block as being final that's not going to happen you have to look at this emerging structure of messages and then figure out what level of finality you have for yourself so let's say you're a client and you observe this method structure you want to get to this and basically you have to execute some algorithm which provides you a score for each of these messages which is House what is your degree of certainty on that message how many people need to break rules or equivocate

in order to propose something contradictory so earlier research had reduced this problem of directing finality to the NP problem of click so basically the complexity was exponential which is not feasible for large sized problems but then there has recently search has reduced it down to quadratic in the number of validators which makes it quite practical and you can check it out and find out more about it on hacking research dot CH there are some efforts towards formal verification so layer X headed by area is working towards the

formal verification of the CBC draft paper in Isabelle Linus research so there has there as there has been some uncertainty about whether cbc is live well there isn't any impossibility proof that say cbc isn't life instead we have this naive liveness strategy which proves that you can have situate you can define a live cbc protocol so just some details about it it's based on the reliable broadcast primitive by baraka it's a round based protocol and it takes o of n square communication per round and in the case of binary consensus when we are deciding on a bit it's going to

lead to finality with a very high degree in three rounds but the drawback is this two-thirds honest assumption that the lab will broadcast parameter makes also this is not really practical because it's basically round based and it has n squared complexity per round so you know we need to research more and go towards practical liveness strategies and if you want to join into this then you're very welcome and you can reach out to me now for the road map some clarifications first there is Casper CBC resource roadmap that is independent of project deployments so it's not dependent on aetherium 2.0 releasing or something

there is also an implementation roadmap which is parallel to the e 2.0 roadmap there have been some efforts towards implementation of a parity client with CVC consensus rules and more importantly none of these roadmaps conflict with the 2.0 well well eat 2.0 actually means team aetherium research and Kasper CVC research are not that different they share more in common than you think most the most notable point would be this LMD ghost fortress rule alright now for the present state of Casper CBC research as for the

specification of the minimal Casper CBC protocol there is a safety proof for the minimal protocol some useful for choice rules have been proposed like latest honest message driven ghosts and basic sharding for choice rule and there is a proposal for a light plan LMD estimators these are probably the more useful for choice rules in CBC and for these we have an algorithm to detect the degree of finality which was the depiction I showed you earlier and there is also a plausible lightness argument with respect to sharding there is a hierarchical sharding design which many of you may have seen in visualizations

it uses cross shard messaging and there are strong atomicity guarantees about these cross rod messaging systems the future road map we need to work on validator strategies that is likeness strategies and we need to find out more ways of expressing them formally proof of stake research that's a big that's a big thing on the to-do list penalties and rewards for faults and optimal behavior and well one of the important theoretical to do is a game theoretic analysis that the rewards and penalty scheme that we come up with actually leads to the honest protocol being the equilibrium so

that's a big thing and for sharding we need to come up with a strong light client specification load balancing for higher hierarchical sharding and efficiency improvements in general two things to measure things that are missing here are data availability and data validity but I'm pretty sure we can kind of reuse the earth 2.0 research in order to do this all right thank you guys and you can reach out to me on Twitter [Applause]