Optimal Flexible Consensus and its Application to Ethereum with Joachim Neu | a16z crypto research

Transcript

uh welcome everyone to today's a16z crypto research seminar um very pleased to welcome yum noi from Stanford uh where he's getting close to finishing up his PhD uh he's done for many years really excellent work in blockchain consensus uh particularly with applications to the ethereum ecosystem and we'll hear about his latest work on that topic today so all yours thank you so much yeah it's great to be here uh thanks for having me uh welcome everyone uh so the topic of today's talk is optimal flexible consensus uh and its application uh to e ethereum uh that's a topic that uh you know I hope you'll you'll appreciate uh you know spans kind of the gamut from relatively consensus

theoretic uh all the way to a relatively applicable uh kind of to the ethereum stack uh as it is today um the talk is designed to take 40 minutes so we'll see late start maybe we'll still uh finish in time though uh this is Joint work with sson my PhD colleague at Stanford uh Le Yang from MIT another PhD student uh and my adviser David Chay and uh if you want to know you know all the nitty-gritty details uh the paper is up on archive um there will be a link later also to the source code uh that kind of comes to the comes with the etherum part of of the story so let me get started uh here is my you know one slight uh recap of the consensus problem uh which is really at

the basis of uh you know blockchains that we that we see in the wild out there right so what happens in a blockchain um you know there's a bunch of replicas a bunch of validators a bunch of nodes running the system uh they receive transactions um from users right and then um they run a certain protocol they talk to each other they run you know what we colloquially call the consensus protocol uh more specifically the replica logic here uh I I write as Pi um and then there are some clients uh that have a wallet and they're interested in whether uh their transactions have taken place and in which order these transactions take place so Alice and Bob right and uh the the replicas are producing some sort of uh you know advice string uh that

goes to the clients and the clients then use uh what I call a confirmation rule uh here denoted by C uh in order to recover uh the sequence of transactions that was agreed upon by the blockchain right so Alice recovers a log uh and Bob recovers a log what do we want from uh you know this ordering service that is the blockchain um what properties do we want from such an ordering service to be useful uh typically there are two properties uh one is what we call liveness which is that you know if there is a transaction that is honestly produced and being sent to all the replicas then eventually that transaction should make it uh to the output log of every client so that's somehow you know non- censorship if you

will and the second property uh is what we call safety which is that you any two clients at any two points in time right they have a log and these logs should be consistent so one of the logs should be uh a prefix of the other log or vice versa okay so far I assume uh you probably have seen this and then the setting I'm in right here is why is this problem hard right the problem is hard because there's delay in the n in the network right when these nodes talk to each other um their messages don't arrive instantly in fact uh you know I'm operating in what we call the partially synchronous setting so there might be a network partition so uh you know sometimes you know for a sustained period of time maybe there are some nodes that cannot talk to each other and

then uh also some of these replicas uh they're malicious so I'm assuming F fraction of them uh might not even be following the protocol that we specify and in that case right these consensus guarantees we don't get them all the time we get them under the assumption that the adversary is not too uh is not too strong right so I'm going to introduce uh you know two parameters if you will uh one is called the liveness resilience and uh I'm going to say okay I want to make sure that liveness holds uh if the adversary is weaker than this liveness resilience uh parameter and then uh the same same for safety resilience right so there's a TS um and I want to make sure that you know if the

adversary is not too strong um then um there is safety in the system long are consist so I should be thinking about like the permission setting where f is just a number of replicas or yes yep permission setting correct okay and classically right the protocols you probably have seen a few in in the past few weeks uh classically the liveness and safety the protocols are parameterized such that the liveness and safety resilience is one3 all right so that's that's kind of the setting now you know oneir is that good enough and you know these are the numbers from like a few a few days ago right you look up uh 8 million out of 22.7 million e um uh Stak are currently with Lio that's you

know one organization arguably you know a dow basically but but still you know they share some infrastructure they share some governance process Etc uh and that's controlling basically more than a third uh of the stake at the moment and so uh given this uh scenario our clients you know the depending on what what their application is um might have certain certain thoughts what they would like the protocol to provide to them right so for example Alice in our example Alice is working for one of the larger exchanges right and the exchanges have the problem that you know people make deposits in a currency then they uh transact on the exchange and then they withdraw in some other currency and the question is you know if somebody

deposits a million dollars worth of eth at what point should you make that balance available for trading on the platform and in particular at what point should you uh allow for that balance to be withdrawn in some other currency right in particular you know you want really want to make sure if somebody deposits eth uh exchanges it for Bitcoin and then withdraws the Bitcoin that the eth stays with you right you absolutely do not want to see a safety violation you do not want to see the log roll back and so a user in this uh setting a client in this setting U might reasonably say say you know with respect to the safety and liveness resilience it'd be better if the system provided higher safety resilience even if that comes at the expense of low aliveness

resilience right it's okay to not confirm a deposit for for a bit if the system is currently under stress um but it it'd be good if if something is uh confirmed you cannot roll it back so we call this a safety favoring uh client and then on the other hand you know maybe there's Bob um and Bob is uh you know want to build an optimistic rollup and uh for safety on the optimistic rollup uh Bob relies on L1 liveness because otherwise fraud proofs cannot be uh posted on the L1 um and then you know if there's fraud on the L2 um that cannot be proven that cannot be prevented and then you lose L2 safety possibly so you know Bob says really you

know I I care about the minimum of these twos you know safety matters yes but liveness matters also because otherwise I lose safety uh on the L2 so you know let's not reduce the liveness resilience uh further than than where we are so we call Bob aliveness preserving uh client okay given you know these two clients right obviously their needs at the moment uh you know cannot be satisfied by by one protocol right um and so we want to accom yep so maybe to tie that together on the previous slide um right so what's interesting here is like so Li out you hear very different opinions about whether it matters the Lio is 35% or not right some people worry about it some people don't and so

like what you're saying is with this like client specific sort of setting right basically whoever you are however you feel about Lio you can set your parameters accordingly right correct it can be sort of a client specific opinions about how much to worry about that right uh if you're if you're uh uh you know if you don't worry about Li you don't have to change things but uh it' be nice if the protocol supported kind of flexibility that you can basically choose your resilience uh depending on what you think is you know more important for your application of this requirement there is a uh kind of a a formalization uh of a consensus problem uh that is called flexible consensus and so the idea there is that

it comes from uh this paper originally um at least that's the first reference I'm aware of called flexible Bustin fall tolerance uh and there's uh another related work which kind of points to the fact that you know the discuss is really very much about kind of strengthening the safety uh resilience which is called strengthen fall tolerance and the idea here is that um maybe you know can we design protocols such that every client can kind of choose their own liveness safety resilience pair and then we guarantee these consensus properties for all clients that have chosen resiliences that actually turn out to be true you know given how strong the adversary is right so kind of we try to do the best uh for every client that has made a

reasonable assumption uh about the world and about the adversary power and so then you know this this this uh previous kind of consensus formulation changes in the following way right Alice and Bob they now both uh have a resilience pair ra rather than having a global resilience pair right so every client now has a resilience pair and what that really means is Alice and Bob also use different uh confirmation rules really right but different only in the sense that they're parameterized kind of for different operating points now what we what we want to make sure right we want to ensure the consensus properties for all the clients that have chosen resiliences uh that are sufficiently high uh compared to the adversary right

so if a client uh chooses a uh aliveness resilience greater than F then that particular client uh should enjoy liveness and if two clients choose safety resiliences uh greater than f um then these two uh clients should be consistent so the consensus protocol will be will be engineered independent of the list of this pairs yes that's a very good question correct um so the question that we're asking is um what are these kind of pairs right um that a per a particular consensus protocol can support So ideally exactly so ideally we would like to have a protocol that can you know support as large a range as

large you know a possible choice of these resilience pairs as possible possible basically but it's it's not clear that that that's actually possible so we'll see uh in the talk um but yes that's that's precisely the question so what resilience pairs what is kind of the maximum flexibility uh that a protocol can provide I so there's another way of thinking about that like one thing would just be like you're given tkl and TKS and now you could imagine trying to design a extensus protocol that just worked for that specific pair correct right but then what you'd love is one protocol to rule them all right where basically you simultaneously got all of those pairs okay exactly so in the original problem right we had we only had one uh one resilience pair and we are allowed to design our protocol with respect to that

one resilience pair now we're given uh you know a set of resilience Pairs and we want to come up with a protocol that satisfies that supports all of these resilience pairs at the same time so now there are two questions one is you know for what set of resilience pairs can you give me one protocol that supports all of them at the same time and then the second question is is there some sort of kind of Maximum set that you could possibly hope for and is there even one protocol that can do the whole set correct yes okay so this is kind of the problem right so it's clear hopefully what what is the problem we're studying right we want to design these flexible consensus protocols and we're interested in supporting this maximal possible uh set

of resilience Pairs and you know what's possible even right and uh just as as Tim pointed out right now we can okay we you know we'll plot this right we plot the liveness resilience over the safety resilience right remember um you know the the standard protocols that um you know we use out there for example hot stuff or even Casper FFG kind of part of ethereum um has a systemwide replica Quorum right so this is a quorum that gets used as a parameter by the replicas of 2/3 and the operating Point wherein is this 1/3 1/3 resilient right what I Pres presented earlier as kind of the classical result and the problem with these protocols is

well all the clients kind of have to you know have to follow this point right so clients don't they're not really able to choose uh what operating point they want they basically have to choose this operating Point okay now you know in order to understand what is possible kind of in this diagram right the first thing we we should uh you know keep in mind is that there are some impossibility results of you know we know that certain law are definitely not possible they're not even possible for a single uh log protocol how can they how could they possibly be possible for a multi- log protocols right so there's the uh famous ds88 result uh which basically imposes this constraint it says okay everything kind

of uh on the on the right hand side of this uh diagonal line here uh there we cannot expect to to support any client that makes a makes a resilience choice of that kind okay and then then yeah within kind of this trade-off right uh Bob is you know wants to operate basically down here in the bottom right corner right uh and Alice would you know basically want to operate in the top left corner and so this particular choice of protocol with this one systemwide replica Quorum you know Bob is fairly happy with um but alysis is not really happy with this right and now what we can do in these protocols is um we can tune the Quorum right and then if we change the the

Quorum this operating Point basically starts walking up that diagonal line right and so we can choose a different protocol instance that is parameterized differently basically the replica code is different code and in that different protocol we're now all operating all the clients are operating here in the top left corner right so now Alice is happy but Bob is not happy right that's basically summary of uh you know no flexibility um is is no good in that sense right we would like to support flexibility so these traditional pbft style protocols as they are um they do not give us any flexibility and so is it as simple as just moving up and down this boundary is

just sort of choosing what's your threshold for what constitutes a super majority when you do vote him is it kind of simple yes that is basically what what happens if you tune the uh the replica Corum exactly yes the the the the main point here I think you you pointed it out before right but I want to make sure that's absolutely clear is this is a systemwide parameter right so all the all the validators in ethereum need to be running this parameter it affects how they cast their votes Etc and so it's not possible that different clients can kind of you know assume a different Quorum and then uh you know operate at different points here simultaneously this is like one one operating point for the whole protocol there was another question no yeah uh so I'm just curious like so you

said you know different clients are operating at different points and let's say Bob chooses like a safety threshold that's like really bad um so then he has to like adjust his threshold up again um is there a way like basically the protocol just does that so you know the protocol starts with always being safe but uh maybe it's like not live for some time and then it kind of adjusts itself to whatever it like thinks so yeah so this this some assumptions of course of like the advertiser isn't like grow this basically uh this basically just bobs decision right so in some sense the idea here is that if Bob chooses a resilience that is lower than the adversary in some sense Bob acts adversarially right in some sense Bob is

not like you cannot really guarantee uh stuff about Bob if Bob basically says I'm willing to accept any block even if it has zero signatures right and so um in that sense um you I mean it's it's only a choice kind of on the client side so you could implement the client uh in such a a way that you know the client kind of autocorrects if there is a safety violation or something like this but it's really up to the client at this point uh it doesn't seem to be kind of core to the to the kind of the consensus kind of problem formulation okay cool all right but I've also mentioned right there are already uh flexible consensus protocols right so

you know what operating points do they achieve you know I don't want to go into all the details of how exactly these prot calls work but suffice it to say you know they have an additional parameter so in addition to the systemwide replica Quorum there is now also every client chooses some local Quorum and applies this local Quorum in a particular way that I don't want to go too much into detail but the result of it is that all of the operating points uh on this line are achievable okay so I pick a replica Quorum and then for that replica Quorum I get a line um and if if I'm a liveness preserving uh client then I have a way to to choose my local Quorum in such a

way that I'm at the bottom right and if I'm a safety favoring client then I have a way to kind of choose my local quarum to choose my local confirmation rule in such a way that I'm you know as far top left as possible okay but you know there's still in this particular case right there's still quite a gap between uh you know what the most safety favoring uh client can actually achieve in this protocol versus you know what you could seems like you could hope for right yeah where does ether like the current ethereum mechanism fit on this thing but doesn't ethereum have like the Dual kind of so it's got lmd ghost which is on the left and Casper on the right like is is there two points for ethereum no okay um for the ethereum part we

basically only look at the Casper part because the kind of the data the dynamically available tip is uh in this setting which is like the partially synchronous setting isn't even safe at all okay and so the the dynamically available um kind of second log we we basically sweep it under the rug and we're looking at kind of the the Casper output the the finalizations and the finalizations as they currently are they're operating down here but your your you know foreshadowing kind of what I what I'll talk about in a moment is that there is a way to kind of uh make Casper flexible also okay you could also imagine reasing the question in the synchronous setting

if you want it right and you might get a different graph say again you could Reas the question in the synchronous setting yes yes and you might get a different graph yep yep uh in fact this impossibility result goes away Etc yes um you can ask totally ask the question in the synchronous setting okay and then in FBF and in sft again you can now tune the system wide replica quum right currently we in this for this particular line we've chosen it to be 2/3 but we can crank it up right and then this line starts kind of walking up to the top left right and now the parameterization becomes better for Alice our safety favoring client but it becomes worse for Bob right Bob is now away from where Bob would like to

operate so these protocols you know they give us some flexibility but there are some gaps right what about the gaps yes Nakamoto consensus is also flexible in some sense no um depending your confirmation rule like you can tune this uh safety parameter kind yeah Nakamoto has a type of flexibility not really with respect to the uh the resiliences safety and liveness resilience they're coupled in the protocol but uh with respect to the latency and the error probability yes uh confirmation error probability okay so what I will be talking about um is a family of protocols that we call Olex protocols which stands for optimal flexibility um

and what they achieve is this trade-off C so basically now with this protocol we can have a single protocol instance in which we can support both safety favoring clients and you know maximally liveness uh liveness preserving clients simultaneously and that is done you know this protocol technically still has some sort of a systemwide replica quum but at this point there's no there's no purpose in in tuning that right so all that's being tuned here is you know the system runs with one Quorum and then clients have kind of their o their own uh client specific confirmation forms their own confirmation roles so in this case you know Alice and Bob are both happy because the protocol can support both of them and you know there's a theorem which says these Olex

protocols give us optimal flexible consensus in the sense that uh you know any set that were given uh of resilience pairs that satisfy uh the impossibility result um and have the property that you know we want to strengthen the safety resilience right so the safety resilience is greater than the liess resilience any of these pairs we can satisfy simultaneously cool so how do we build this interestingly there's a uh there's a generic Construction in which we can take you know a closed box kind of protocol off the shelf uh add some stuff to it and then it becomes an optimally flexible uh protocol and that's what I'm going to go through first because that you know builds some intuition of kind of what are the mechanisms that are at

play and then we'll see that you know there are different ways to kind of realize these mechanisms and there is a way to realize this in ethereum in such a way that we don't even have to change the replica code okay but let's first look at kind of the generic construction right so we want a consensus protocol this box is my consensus protocol in a block diagram there are transactions coming in and then we have all of these different logs of all of the different clients uh coming out right and alysis is this one it has uh no uh liveness resilience and and one safety resilience and Bobs is this one with like 1/3 one3 and you know our code our protocol again has has some replica logic right and it uh so there's a replica in the picture and it has a

client logic so there are clients in the picture right and here's how the protocol works so First We Take This off-the-shelf closed box protocol operating at 1/3 1/3 resilience pair right and that protocol we're just putting all the transactions come in uh the replicas put them in put them into this protocol and that that protocol outputs some log okay that's an internal log though right we we're going to do something to that log here's what it looks like right so the the protocol is running transactions get confirmed right this is from the perspective of this replica this is kind of the the internal log that it sees right and then when the internal log has grown a little bit there is this second stage of the protocol which we call Perma lock and

vote and what it really does is you know the replica looks at this output the internal log at this output log and then says okay I'm going to you know this is my log I'm going to lock on it I have to be uh careful with the language lock on this right so I'm applying a lock here and then I'm going to cast a vote I'm going to let Alice and Bob know hey uh by the way I'm locked on this uh on this part of the log of the internal log this is the internal log that I hereby vote for right this these are the post votes I'm voting for this and we'll see what voting means right so Alice and Bob they collect these post votes from our replica but also from some other replicas and then once they have enough of these post votes they have their

client local Quorum right so they they choose their Quorum you know in such a way that liveness is uh is satisfied and and consistency is satisfied uh they choose their quarum and then they confirm their respective output log and now you know the internal log keeps growing right and what does the replica do well you know periodically it says okay here's the new log right this is what I'm going to lock now right and again I'm going to cast my vote and you know you know more replicas cast their votes and so Alice and Bob keep uh confirming stuff and what does it mean okay we have talked about post voting we have kind of seen what this locking thing is but we haven't really seen in

what sense it's a lock it's a lock in the following sense um if the internal log were to have a safety violation right so suppose there's suddenly there's a new output that's consistent with earlier output then the replica looks at this and says no no this is inconsistent with what I've already locked I've basically given a promise to Alis and Bob that I will never endorse anything inconsistent with the votes that I've already given them so I'm not going to I'm not going to lock this guy and I'm not going to vote for this guy I'm not going to give a vote to Alison Bob for this uh conflicting log okay so the key the key mechanism to keep in mind about what this protocol

does right is it it's running a consensus protocol at 1/3 1/3 and then it has a peral loock and post vote uh stage and what really happens in the peral loock and V post vote stage is that if a replica has ever post voted on a certain log right then um if the replica is honest we can infer that the replica must be locked on that particular log and that it will never cast a post vote for something inconsistent did you say that so clients should speak to multiple validators when they do this correct yes a little bit of a change in the right or clients receive the votes not not necessarily talk to multiple replicas but they see all the votes from different replicas just like

they do right now yeah uhhuh so here's the case that the safety of the consensus is violated because the quum the amount of visiting notes is higher yes very good correct yes so we'll we'll see in a moment uh what happens so could you repeat what there said uh the question was uh how is it possible that you know there is this safety violation here basically on the first stage protocol right I think you were pointing out the fact that this can only happen if the adversary is stronger than 1/3 right exactly because this protocol is is safe up to one3 okay so let's look at why why is this you know why basically you know why why does this give us flexible consensus right can we reason through the liveness

and the safety uh of this protocol and it's actually you know fairly straightforward so bear with me in 5 minutes we we have this um so let let's think about liveness right let's assume we're we're looking at a particular client K and that client K has made a reasonable choice in terms of its liveness resilience right its liveness resilience is actually greater than F and also um you know it's it's a client that has chosen a point in this feasible triangle right somewhere here on this diagonal line right then you know look at the graph right if you choose a point anywhere on this line uh it must be the case that your liveness resilience is smaller than 1/3 but and we have assumed that uh your liveness resilience is adequate so f is

even smaller than that so what what does that mean that means the base protocol in this condition is safe and live and if the base protocol is safe and live it means all of these logs across honest replicas will be consistent and if they're all consistent and they're all live then all the permal locks that honest uh honest replicas will ever adopt they will all be consistent and the liveness gives us that you know if there if any honest replica sees a certain output log right eventually all honest replicas will see that output log and because that output log is consistent with any previous Perma lock that it might have adopted they will actually also vote post vote for that particular log and because of this every client eventually you know if the client

has chosen the the Quorum adequately in particular in such a way that you know enough votes from all honest replicas are enough to actually meet the Quorum then the client uh will be live and will eventually confirm that output l so is it fair to say like the only thing that you're worried is going to go wrong with liveness is when like in that left picture where you kind of have a lock on something and then there's a fork you're not going to vote for but then if there's no Forks in the first place that problem can't happen and so you're fine yes two two things I'm concerned right one is outright this guy not be live because if this guy is not live then no transactions go through and the other option is precisely this right what if this guy is unsafe then my replicas here

might be locking on inconsistent stuff and then I might never get enough votes to to from yes and the idea is well if that happens right then um you know the the liveness that I'm expecting I'm expecting too much liveness right this cannot happen for any possible choice of liveness resilience that is actually feasible so suppose we have two clients right both of them have chosen adequate safety resiliences greater than F and remember right we choose the quarum in a particular way right now for contradiction assume there are some conflicting confirmation right so assume you know some client outputs kind of the red log up there and some client outputs the blue log down there clients I mean

outputting logs here right not intermediary logs logs actually coming out of the protocol right then what's what must have happened okay the client who output the the red chain right has seen a certain number qk of votes for that particular chain right for that chain or longer chains right and at the same time the client who outputs the blue log right has seen a set Q qk Prime of votes for that blue log right but now because of the choice of the Quorum okay so right these are basically all the replicas that voted for red these are all the replicas that voted for blue but there are only so many replicas right this like uh black uh rectangle here right

and then we can reason that because the the quorums are chosen uh as large as they are chosen it must be the case that in this intersection the these two sets these two quorums must actually intersect and the intersection is greater than F in particular there is an honest replica in this intersection but now we've already seen earlier right that an honest replica would never vote for two inconsistent things because of the construction of the protocol so this cannot be so the protocol must be safe so what what have we seen what have we learned right in some sense there are three mechanisms at play here three I don't know what to call them features or three like you know three like gadgets somehow in this protocol right one is this idea of peral locking and the idea

of peral locking is you know we're using that in order to avoid contributing towards conflicting confirmations both in the in the future and conflicting confirmations in the past right in the sense that you know if we permalock on some if we vote on something right if we post vote on something the post votes tell our clients hey I have permal locked on this and what it means is if a a client sees a post vote from an honest replica for a certain log it knows that this replica will not in the future and has not in the past post voted for anything inconsistent and then the third mechanism is this uh client specific quorums um that basically allow us to uh output these uh flexible logs and now we can ask okay uh you know post voting and

peral locking these are kind of two mechanisms that we need on the replica side right these are like systemwide kind of uh mechanisms on the other hand the confirmation rule these uh client specific quorums they are client logic they're kind of local decisions every you know every user basically of the system can choose their own uh confirmation Quorum and we can look at different constructions there are different constructions in this Olex uh family um how we Implement these three mechanisms okay the construction you guys have just seen is kind of the generic construction as an add-on for any protocol right you take any protocol that's 1/3 1/3 resilient you add this additional Perma locking and vote uh and

the client uh specific confirmation quorums and you'll get an optimal flexible uh protocol you know essentially adding post vote permalock and Confirmation rule external to the protocol then the second construction is well if we look at these chained pbft style protocols right they basically use chaining in order to unify a bunch of rounds of voting that happen in in the pbft protocol into you know one streamline kind of propose and vote procedure I don't know if you guys have seen uh hot stuff or streamlet or or any protocol uh in the past few weeks um but yeah suffice it to say you know they're all relatively similar they all use this

trick that you know votes can kind of you know one vote can really kind of use multiple per serve multiple purposes at the same time and we can basically for free add at on top uh you know this kind of purpose of being a post vote so we get you know post voting basically for free in these protocols we still need to add a locking mechanism and we still need to add these client specific confirmation quorums and then you know the next step is oflex confirmation rules for ethereum where it turns out ethereum so Casper in particular Casper FFG is is one of these chained pbft style protocols so we get you know the votes for free we can reuse the votes that are already in the protocol and it

turns out there is a performance optimization um in the specification that effectively already implements the Locking logic that we need so we don't have to add the peral Locking uh kind of on top of the protocol what this means is you know looking back at what's replica logic and client logic is we get optim optimal flexible consensus for ethereum without making any systemwide changes everybody can just you know start following this new confirmation Rule and then uh have the the um the flexible uh guarantees yes uh can you remind me how many uh replicas the client talks to is it just one or is it okay so so the client needs to hear votes from all the

replicas just like just needs to talk to one but it these can be related right so any anybody can give can give them to you so is it true that if I just talk to everyone and I collect like you know whatever uh like I just talk to everyone separately and then locally I can say okay if 80 if my safety thresholder is 80% then I'll just uh if 80% of the nodes say this portion of the Ledger is finalized then I finalize it locally that's my confirmation role and now like I can do this with no changes to the protocol just with the added model assumption that the client talks to all the nodes so there's no extra voting or locking your uh no this doesn't work yeah this this would be exactly fb's construction so flexible bft is is

pretty much doing this it's basically saying what if a client just instead of applying uh this you know systemwide quum applies a local like larger Quorum right but otherwise there is no post voting and no permal locking then you get exactly the um the trade-off of the FBF curve which is not the full trade-off there there are some gaps but in in there also you need to talk to everyone um there also the relaying happens the the talking to everybody doesn't really change anything because it's all signed anyway so um let me give you one sentence of intuition why this is the problem with this construction is that even though the client locally applies this very high Quorum that does not stop the replicas basically from turning against confirmations that the

client has locally made so you locally see this very high Quorum but the replicas apply this much lower Quorum and so the replicas you know if the adversary is sufficiently strong uh the replicas basically start casting votes that are inconsistent with your high Quorum confirmation and so the replicas basically turn against the clients and that's precisely what the post voting and peral locking rules out right the peral Locking does exactly this thing where you know you lock and you will never vote for anything inconsistent no matter what so I guess this works it's just not optimal in that case yes yeah you you get like you get some flexibility but you don't get all the way there can you say a bit more about the peral loocks and ethereum yes given that there's people in the room that know a

lot correct I'm coming there right now uh so this is uh you know the figure one of ethereum consensus right just to uh kind of kind of answer Noah's question right what what what we're looking at here right ethereum's protocol is this composition of lmd ghost and Casper FFG it outputs two logs right but what we're interested in specifically you know we're we're interested in high safety right and safety is kind of the domain of Casper FFG and so what we're interested in is kind of boosting the safety of Casper FFG okay so we're trying to kind of make finalizations even more safe we want to have super finalizations if you will okay so here is uh you know quick quick as concise as hopefully possible

summary of of ethereum's uh Casper part right so ethereum is a blockchain so there are blocks and then you know the protocol is basically propos a block and then we do a bunch of voting right and we vote for a certain block and then somebody proposes a block again and there's voting again okay and then there is this traditional Casper FFG finality rule right that says if you see you know roughly it's not exact 2/3 on one block you need to see 2/3 of votes on like a bunch of consecutive blocks uh but basically if you see 2/3 of votes uh then you finalize this block a and then you output it according to the uh finality kind of default confirmation rule of Casper

FFG okay now here's the thing about the locking mechanism in ethereum specification they go one step further they not only say if you see this then you know that's your that's your finalized log they also say if you see the situation that something is finalized in your opinion you will lock on this guy and even if later you see a conflicting block that also has enough votes to be finalized you will not output that you will always be locally consistent the reason they do this is performance optimization right once you have finalized stuff you can basically forget about every block and every vote on everything that's inconsistent with it and so you don't have to kind of walk the block tree every uh every time you

just basically keep track of you know your neogenesis kind of the most recent finalization and you do consensus only with respect to that so they have this as a performance optimization but it turns out that's exactly the locking mechanism that we need in order to implement the peral Locking so the next thing that happens in ethereum is that um okay so you know you have a rough sense now where the peral Locking comes from right leaves us with two more things the client specific confirmation quorums and somehow these post votes right and so here's here's the next thing in ethereum votes are not just you know floating around kind of next to blocks they also get included on chain they also get reported on chain so in this

case the Block C right would contain all the votes that are necessary uh you know would would at some point contain enough votes so that based on C and its prefix you can reason that a must be uh must be finalized okay so that's an important property and now we come to the um to the post votes and and client uh specific uh confirmation quorums namely if C has a certain number of qk of votes right what does this mean this means any not any replica that has voted for C must have seen all the votes that attest to the fact that a is finalized so any replica that votes for C right must have

locked according to the protocol rules for a so that's exactly the mechanism that we were going after earlier with the post vot remember every time I see a post vote I can infer something about the Locking about the Perma lock at honest replicas so this is the confirmation rule the conf the new confirmation rule is the following if you see a block a and a Block C in such a way that um a according to the votes included in C or in the prefix of c a is finalized and you see qk votes on C then you confirm with this Olex confirmation rule you confirm a and the reasoning is exactly this if an honest

replica has voted on C you know that if the replica is honest it must have locked on a which in turn means if there was another condition you know where somebody could be confirming right where you have a block F and votes finalizing f are included in H and H also has a quorum then you know that this replica will not would not have been voting for that block because that block is in like these two blocks are inconsistent with a and the replica must have already been been locked on a so you will not confirm F so you know we're safe basically so yeah the the two kind of ingredients here right we have uh the client specific quorums that enable the flexible resiliences you've

seen where they come from right here these qk post voting uh help us inform clients about you know what permal locks replica have adopted um and peral locking is you know this mechanism to make sure that replicas would not vote for twoo uh conflicting confirmations all right any more questions about this otherwise I'll come to experiments yes when you were saying that it's a performance optimization for ethereum to kind of not switch why would you see a conflicting Branch if you if the number of bantine notes is less than one3 yes then you don't see it yes but but but but we want safety up to one right we want that basically if we tune qk up to one that

then you know unless everybody is malicious uh we will we will be safe so we have to deal with with the parameters where where f is greater than one3 okay and another question sorry so ethereum is collecting as much votes as it can possibly collect in principle it could just stop at 2/3 and yes oh that's a very good point yes so ethereum uh collects as many as possible for incentive reasons right yeah and it it that that's a very good point actually right if ethereum had done another performance optimization to not include all of these votes on Shain but stop at 2/3 then this would no longer work um yes that's a very good observation um actually maybe it would still work because these blocks these

votes don't have to be included in blocks you only have to see them right so all you have to see included in blocks are the two3 that are attesting to the finalization these votes you you can read them in the newspaper basically no matter where they come from if they're properly signed you know that they come from the replicas then you're good but but to Lara's point I mean currently you can literally just read off the current ethereum blockchain basically all the information you need for this right and that's exactly what we have done correct um so precisely all the information is on chain right we can take like the beacon chain API um and read it off our consensus uh client our yeah our consensus client

um and basically plot you know what would the logs have looked like for the nor normal Casper finality right for the Olex finality with a safety resilience of 33% right so that's basically uh qk 2/3 um and then for uh safety resilience you know 98% right uh and what we see is you know this is like a an average afternoon basically um what we see is you know on on chain participation is fairly high right everybody's voting as they should uh and we see that you know the the the logs just uh you know move along pretty much in lock step the the Casper um uh log is a little bit faster and the other

ones uh catch up because they have this extra round of voting I so basically what you're doing here is cranking up the safety and checking if liveness would have broken down is that right that's uh uh yes that is something you can do yes I feel like that's that's how I'm sort of interpreting this graph is it yeah so in in this graph I'm basically running both of these confirmation rules and I'm just interested to kind of see you know how quickly they catch up with with each other but what you could do right is you could just always run you know whenever your system is kind of in in like you know operating by itself mode right you always run with a very high uh safety resilience and then if if you if you detect that liveness has stalled presumably because participation is low

we'll get to that in a moment um then you know you notify some some operator and the operator is supposed to figure out you know is why is this is there a hard for going on um has there been you know any bugs should we you know can we basically just lower the resilience the safety resilience in order to get liveness or should we stick here and you know not finalize for the moment or not super finalize for the moment there's another plot uh yeah the the source code of this proof of concept uh is is on GitHub if you want to check it out uh this is another plot where we basically uh tune the safety resilience uh of the Olex confirmation Rule and we're plotting the mean latency uh against Casper finality and what you basically see is that you know Casper finality uh

has an average latency of 15ish minutes um and because of the extra round of voting that we need for Olex uh you know we need about four minutes more and then once we paid for the four minutes no matter how much uh how much safety uh we want uh we basically don't incur much loss uh in in latency anymore uh there's a little bit of a spike back here those are basically the cases where you know participation drops quite a bit and then uh you know the higher resiliences start stalling and we see that in in this uh plot here uh so this plot is uh from during the Shanghai heart fork and so what happens is you know participation initially is high then the fork happens the participation drops because not

everybody has updated their valid datas and one participation drops the the high quorums the high safety resilience rules they start stalling right uh the low uh like fairly low still higher than Casper but like fairly low safety resilience rules they quickly start catching up because participation is still fairly high right and eventually you know participation stabilizes again everybody has updated their validators everything nice uh and then uh even the high safety rules catch up again so this is kind of you know this doesn't happen very often it happens when there is like client bug we have another plot from this recent finality stall it happens during heart fork with like the very very high safety

resilience uh things but you know usually uh the plot looks like this right uh almost all the time this is just to give you a sense and uh yeah that's pretty much uh all I had uh you know in a summary in one slide uh you know we are interested in building these kind of optimal flexible consensus protocols where we can support you know the maximum set of safety Liv resilience region right pairs in one protocol at the same time right it turns out it's actually possible we have a bunch of constructions you know one very generic one where uh you know the the three key ingredients you add them basically to literally any protocol uh that you pick off the shelf um and then more specialized ones uh where you need to do

you know less changes to the protocol uh for chain pbft style protocols uh and for ethereum it turns out you don't even have to uh change the replica logic at all and um yeah you pay a little bit in latency because the extra on of voting uh but most of the time uh it just works all right thanks [Applause] again