J1 PAIN 06 Vlad Zamfir Casper + Sharding = ♥

all right thank you thank you so we got a long talk I've got my water over here I'm gonna try to bring it bring it bring it over here maybe it'll be a little little closer for me so we're gonna get this awesome opportunity to go through the Casper family of protocols and in some detail which I don't think has ever been done before in terms of like me giving a presentation so I'm excited I think we're good to go so let's take a look at the outline can we get the presentation mode going anyway there's like a play button there on the right is that leave sorry guys will hopefully be going through this soon but I guess I could just start so it's broken up in three kind of parts to part the first two parts are really like the meat of the presentation the first part is like an introduction to consensus and then the consensus safety proof that all of the protocols that I'm going to specify in the second part including sharding are going to satisfy so the first part is kind of the important part where all the analysis happens and where you kind of get to understand something and then the second part is protocol specifications and pictures and trying to kind of relate the proof which is kind of a quite abstract to something quite a bit more concrete like for example like actual consensus protocols like actually running so you try pressing on the limit so you see the lead I'm gonna keep going keep going keep going walk one more bomb calm all right all right settle down settle down we don't we don't have all day all right introduction what our consensus protocols well because this is protocols they allowed nodes in the distributed network to make consistent decisions even though in a distributed network out of mutually exclusive inconsistent alternatives they might screw up so if a node over here decides on something that contradicts a node over there then like they're not there no that's like not the point of a consensus protocol right the point is for them to like be consistent and distributed network and specifically normally we talk about coming to decisions on the same values but in sharding we're not all gonna be coming to decisions on the same values but we will still want to distribute a consistency property where oh you're not contradicting any of the values that someone comes up with over there even though you may not all be coming up with the same values so generally I would say that cuz its the protocols of a shorted or uncharted variety are about nodes in the distributed network making consistent decisions so if I say coming consensus on a bit what that's gonna mean is like oh we're making decisions on a 0 or 1 and so if you decide 0 and I decide 1 those are inconsistent if it both decide one or both sides zero then they're consistent so and we're so we're gonna look at a binary consensus protocol but then we're also gonna look at an integer a blockchain and a char deadlock chain and they're all going to be consensus protocols and they all basically don't have the same type of property that like oh the things that knows aside about it need to be consistent even though they're on different points that disturb your network or in the Charter case even though they're not even on the same charts so we kind of have two basic properties that are kind of traditional kind of mandatory reading safety property which says oh that knows you just the values you decide on are not conflicting and - who says oh you'll eventually decide on a value or reject it so the reason why I says this is quite hard is because different knows and it should be network don't see all exactly the same thing all the time there's delays and messages won't be propagated with Lux zero latency and infinite bandwidth on those at all times so nose will see different things and that makes it quite hard and then the order of messages might not arrive in as expected and additionally there might be like other kinds of faulty behavior so cuz it's the protocols are kind of classified by the adversarial behaviors in which they can survive and more specifically you know the where their safety and liveness can survive so we have this great result in consensus protocol research called FLP and possibility which basically says that oh look if you have an asynchronous network you can't have both safety and live in this if there's a single node that's faulting the if your protocols like deterministic and doesn't use any cryptography basically the the way this kind of works is you at any point you're trying to make a decision and you can only do it if everyone it's kind of a line with you but in a synchrony there's always gonna be one pivotal node and they managed to show this in look in the paper but for for our purposes right now all I'm saying is oh look I'm not gonna show you any synchronously live and safe because it's protocol I'm just going to show you an e synchronously safe one and that kick so that kind of leaves off the intro like just basic consensus protocol section I'm gonna take a sip alright so now what we're gonna do is we're gonna give a safety proof a consensus safety proof for protocol and then and then and then specify the protocol or then and then and then kind of specify enough of the protocol to prove the thing but the first thing I should mention is okay what is what is this approach well it's called the correct by construction approach to protocol design and instead of basically like specifying a protocol and then Pru and then doing the analysis of proving that it has all the properties that you aren't the kind of the way it works is you you specify a little something about your protocol then you say what property and proofs the protocols you satisfy and then you derive the rest of the protocol to satisfy those proofs so you kind of setup the proofs first and then you kind of pull out the rest of the protocol in order to guarantee that the priests are satisfied so we kind of try to do the analysis first and then the protocol specifications second in order to make the proof of the protocols correctness really really simple really really easy because like the whole protocol was designed around the proof and the proof was designed to be like as simple as possible so you know traditionally okay you do protocol first and now it's a second and now we try to do analysis first in protocol second this is kind of a heuristic it's not really exactly a court conviction is but it's a good it's a good way to think about it we kind of reorder the presentation somewhat to give the proofs first and then the protocol in such a way that kind of falls out of the proofs satisfy it so now I'm gonna go through this proof separate it out into two parts and the first part is gonna be a very kind of trivial and the second part is gonna be like super interesting and less trivial but we're gonna take them both in like significant detail oh yeah don't always get to do this so we have a protocol it's got some protocol states it's got some protocol state transitions I'm draw I'm representing them as these little nodes with arrows the nodes are States and the transitions are the arrows and basically they they describe how nodes involved in the protocol protocol state transitions we have like we have an identity and transitivity so if there's like a transition from A to B and a transition from B to C then there's a transition for a to C so like oh if the protocol could evolve from one state to another to a third then it can evolve from the first to the third it's kind of a some trivial some trivial properties that protocol executions happen so haven't drawn it here but for example there's got to be a line from like the one in the bottom left to the one in the the one in the middle to the one in the top even though it's not drawn so in the binary because so in the so we have a we also have something something else something called an estimator so we have these protocol states in protocol state transitions okay that tells us almost nothing right and then we well I'm gonna give you a little more we have a singleton estimator which Maps the protocol states onto values of the consensus it basically says Oh from this protocol state like this is kind of what we think the consensus is it kind of associate the states with values of the consensus so we're kind of it we have a little more in our protocol now for example in a binary considers a protocol we're gonna map the protocol States to bits in a blockchain sense protocol and wrap the protocol States to block chains I kind of correspond student watching protocol like a fork choice rule your note is that some state it's seen some blocks so certain times maybe and then it will like pick a blockchain out of them and this is like a map from like the node state which represents like like it's like the state of software at the time to like the particular blockchain that it should choose what is in that state so the estimator kind of Maps protocol states to values the consensus but it's not like they're necessarily decisions but they're just kind of like estimates right there may be revised in the same way that a fork choice rule is so we also have a kind of system of types for reasoning about consensus values what you just think of this is like propositions about the values of the consensus like oh that's one this blockchain has this block at that height because there might be a whole bunch of lock chains that have that block at that height and we want to talk about the fact that this block will always be in our block chain in the future but we can't say that oh we'll always have this block chain and so we need to talk not just so directly because there's values but also about like maybe properties of them so we're kind of able to do we have we have a type system on that cuz guys the consensus so then we have this no this this this notion not like the value of the consensus satisfies a property right and I write like C implies P if like the type P or the proposition P is satisfied by that value of the consensus so for the estimator we can basically talk about whether the estimator satisfies a property great so we have again protocol states and transitions and a map from them to put two guys the consensus and now we also have a system for talking about the values the consensus and mmm finally we have this definition here which is gonna be like the the last definition before we can really step into our proof it's called estimate safety it basically is a local notion of safety that says look some proposition P it holds for the current state and all future states so it's a as a as a function it's a function of a proposition in a state and it says that oh look that proposition holds for the estimator in all future states so anyway you can follow this these transitions down you'll only get two states which draft to value the consensus which entail this proposition P so it when something is safe it's kind of invariant over all future protocol states so I have a little example here all of those ones are safe because each of those ones they're all of their future states haven't one also the zeroes there and the the nodes in blue have future states which are not just the values that they have there and so they're like not safe now these this particular protocol state transition like object here is not doesn't correspond to a non-trivial cuz that's protocol it's very trivial the only thing you can decide is one really but it kind of shows you the idea of like okay all future states have the same value so we have this consensus safety proof basically the first part of the safety proof now that I can present basically it says it cuz composed of kind of two parts one of them one of them notice is that okay well if a proposition is safe here and there's a and we have a state transition to some other state and it's also gonna be safe there let's make sense because all future states of the first one have that invariance any future state of the second one or future states of the first by that transitivity property that we talked about and then we have backwards consistency which says like oh if i have safety here then there's nothing downstream of this thing that was safe on its negation so it can't be that there was a previous protocol state which was safe on the negation of something that is safe in this protocol state because if it was then the forward transit forward safety would mean that like in the negation of that statement would be safe which is exactly what we I mean we assume that it's the statements actually safe so basically in our in our setup here we have laser anyways in our in our setup we have safety at Sigma one on P that gives a safety of Sigma three on P and the second result gives a safety of not P at Sigma two at the bottom there so if Sigma if it's Sigma 2 not P was safe then not P would have to also be safe at the top there and we get this contradiction and so kind of our result here is basically that if we're safe at P with P at Sigma 1 then we're gonna be not safe with not P at Sigma 2 so this is kind of a little subtle so let's talk about it a little more so it's so you know if you if you are a protocol state and you're safe on some proposition P then you follow some future path to something some other state and then you walk backwards to any other state then for for that other state you're not gonna have safety on the negation of P first so basically any state that's downstream from anything that's upstream from you as a protocol state when you're safe on P is not safe on the negation of P and this is gonna be really useful because we're gonna be able to interpret this as consents of safety so firstly we can do a little bit of logic here and show that this is equivalent to the fact that it's not the case that P is safe at signal 1 and not P you say but Sigma 2 you could also think of proving that if you assume that they were both signal he was safe on single one and not P would say for Sigma 2 and have a feature date in common Sigma 3 then they're both P and not P would have to be hold which we're not allowing so in some way this looks a lot like in sense of safety it means that all things are safe they're the things that are safe here don't contradict each other they're consistent you know and and the nice thing though is that this distributed safety property isn't isn't a local property in the same way that a notes state is melot's of there's lots of other protocol states there and basically our interpretation is going to be that we're gonna make decisions only on things that are safe only on estimates that only have values that are fully covered by the things that are safe so that we can take advantage of this property so as long as nodes all run protocol states in this in this state of protocol states and transitions then they can have a common future state so before we're just think about it's kind of one node running through the thing now we can imagine now we have multiple nodes running through this protocol state transitions and if they have a state in common and they only decide on stuff that's safe then they get to have consensus safety here's all the stuff they decide on has all holds in this in their common future state and therefore is consistent so basically you're allowed to make a decision if it's a prop on a safe proposition or if it's on a value that only implies safe propositions and if you do this and if noes have a common future state then then this distributed consensus property sorry this distributed safety property is the same as consensus safety it so if two protocol states have a common future in common that means that two nodes at those states who only make decisions on safe estimates have consents of safety and that's essentially the key result and like the point of part one so nodes who only make decisions on safe estimates or that are tailed by safe estimates and who have common feature protocol States in common have consensus safety and the reason oh look if you have a common for your protocol state in common then all the things that are safe locally are going to be all safe together at that future state which means that they're consistent so this is the very that's the part one of the proof assume that knows have a common future state assume they only decide on safe stuff where the safe is this local notion and then we can show this distributed notion of safety all right so it's kind of important this is like you know if you don't get this you know it's not going to make much sense so nodes knows if they share a common future state have the property that anything that's invariant and all their future States is are consistent because those things that are invariant all hold at their human common future state so I'm gonna drink now thank you thank you so with part two we're actually gonna be guaranteeing that notes have a common future state part one we assumed it and it's kind of not that satisfying so in part two we're gonna try to make sure that as long as long as there's not more than some number of Byzantine faults then we're gonna have a common feature protocol State but first what are these Byzantine faults and why does it matter well if you have a non-trivial disaster protocol then you'll have some nodes that are safe on zero and some nose that are safe on one for example or you'll have you know mutually exclusive outcomes which could become safe on and decide on and this is kind of an issue because oh if you're a node we're going through a protocol state transitions here you end up on the left and I end up on the right then we have consensus safety failure and you know and our theorem doesn't hold because we don't have a common feature protocol statement so non triviality basically means that there are some states which are safe on mutually exclusive values and that they're accessible somehow and so that means that like it must be possible for you to get to a state we just I don't wanna and it must be possible to get two states that you decide on zero however and it must be possible for me to go to zero I need to go to one but sometimes we have to coordinate to each end up in the right place in the same place so it's just kind of not necessarily trivial we can't independently follow our state transitions we need to somehow be having some kind of signal in common some kind of interaction in order to make sure that we're following the same because or whether we're making consistent choices in this environment where we have mutually exclusive outcomes so we're gonna assume that we have named nodes that can send us messages that are signed and this and and then basically what's gonna happen now these are these are they're gonna be our consensus forming nodes and then indeed anyone anyone in the protocol is gonna know about them and is gonna watch messages from them in order to try to decide whether to go down this way or that way in order to not be kind of screwed right and then as long as these nodes are showing you kind of the same thing that they're showing me then we may have some hope to end up on the same side of this mutual inclusive branch so we really didn't even some kind of assumption here and this is the one I chose to make because it's like useful and proof mistaken so like but we could also talk about proof of work but this is you know not today right so we're gonna assume that we have and everyone knows who the nodes are they're forming consensus and they all can sign messages and they all do sign their messages and further your protocol state transitions only occur when receiving signed messages so like your note is just gonna say in the same protocol state until it receives a signed message and then it'll transition to a new state and so now we have understand that are like okay even though we were just looking this as a lattice we're gonna actually be able to have some more complicated structure here in terms of the way our protocol states look and so we were talking a little bit about Byzantine faults and it's kind of important because Byzantine faults can't screw this up pretty badly if all the nodes that are consensus forming run a version of the protocol for you and a version of the protocol for me then there's no way to guarantee that we have our that we're gonna make consistent decisions at least it's like one of the nose that we're looking at in common has to be the same showing us consistent things so if there's too many of a certain kind of Byzantine fault then we can be screwed and I'm claiming that oh look at quit vacations our kind of Byzantine faults that are fundamentally good enough for doing this cone vacations correspond to because there's a swimming node not behaving like they're running the protocol once but we're but behaving like they're running it at least once like more than once so any behavior that can't be produced by a single execution of protocol but can be produce a more than one is considered equivocation so these two green nodes here maybe you can imagine them as sign that we received a message from these nodes that said oh look I'm there and I'm there so the same node so I sent both of those green nodes now that's not an equivocation because there exists a path through the protocol space that hits both of them whereas the red ones if I received a message from a node and the red one on the left and the red were on the right those are not honest behavior that's not honest behavior at all because there's no single protocol execution that could have produced that you need to actually excute the protocol twice to get to both of those states if you're gonna execute the protocol correctly so somehow rather than considering all the arbitrary behavior we're gonna focus on this equivocation fault which is corresponds to a correct execution of the protocol but like more than once so there's more than once kind of excuses protocol is gonna allow our performing notes to tell me to go over here and you to go over there so that we're forever separated and kind of like consensus safety failure so you know that's kind of it's kind of a problem right why would like there's no there's no way for us to be to have cuz that's a safety in the context 100% Byzantine faults it should be pretty clear because we have we have to have a straight to say transition to something with P and we have to have something estate resisting with not P and we can only really count on these nodes which might be telling me to go to P and you to go to not meet so that we have to kind of assume that there's gonna be less than some number Byzantine faults for consensus to work out um but that's okay we're kind of used to that we're kind of used to fault tolerance numbers of less than a hundred percent so we're gonna we're gonna try to figure out then how to make sure that nodes have a common future as long as there's less than some number of Byzantine faults so we know we know kind of that we can't possibly be true be non-trivial and have them have a common feature if there's too many isn't if there's too many was in these vaults because if if they have a common feature even with a current Byzantine faults then it must be the case that every two states have a common feature so we need to make sure that we have a common feature but not if there's more than some not if there's more than some number of Byzantine faults well let's start let's start by counting Byzantine faults right we're gonna count these are quotations so from a set of messages from a validator we can literally just check whether there is a single protocol execution that goes through all of them and if they if there is then that's not an equivocation and if they're not equivocating and if they're if there isn't then they are equivocating if we have a bunch of messages from a bunch of senders we can tell which of them equivocate this is kind of assuming the messages say look I'm at the state look I'm at this state and if the validators have weight like they do in like some because there's protocols and then then we can talk about the weight of the equivocations not just the number so somehow okay we have this definition which we could actually use to count equivocations from sets of messages as long as the messages say oh I was at this state when I sent it I was at this state when I sent it so this is kind of like tying the knot here getting close to the punch line so we're gonna let protocol States be sets of message that exhibit less than some number of Byzantine faults so the protocol states themselves are set sets of messages that say we're on which protocol states you're at you were at but those protocols those sets of messages exhibit less than some number of visiting faults why would we do this well I mean it's quite clear but but I'm gonna like tease around a little bit so firstly like okay yeah every message says what state you're out and when you receive a message you move from a protocol state which has the current set of messages to the the current set of messages Plus that new message that you received as long as that new message doesn't tip you over the the t-phones so if the new message tips you over to faults then actually we're not going to transition to a new protocol state so because the protocol state is a set of messages you know this is adding a message receive its I'm receiving a message corresponds to taking a Union I'm just denoting as plus every arrow in this protocol state graph will correspond to receiving some sets of messages such that the number of Byzantine faults that are introduced in that set doesn't go beyond some threshold this is kind of like a little little demonstration of our protocol state transition so this is like a set of messages over there from three validators line them vertically with like different values of the consensus of those states and then and then there was like over there was like a message that was that would appeared in our view that said look oh my poor my state include my state that the second validator had in their messages like the bottom two nodes and in the state transition that we took kind of from the set of message on the left instead of message on the right didn't introduce any Byzantine faults so we know that it's actually a protocol state transition between protocol states so an interesting thing is that any message is actually an equivocation with respect to some other messages that like may or may not exist so whenever you make a message you actually drop a whole bunch of protocol states with which you used to have a common feature protocol state which you now no longer do so every time you receive a message there are states which which the this with this set of measures which this mustn't set of messages no longer has a common future protocol state namely the ones such that that message that you just received pushed you over the edge of the number Byzantine faults that we tolerate when for the for the union of those two two states it's a bit it's a it's a it's a bit hard to wrap your head around but the idea is that like by independently making a decision in this business in this protocol space you are precluding a bunch of protocol states states that have two that would only be material if you equivocate it what if you're the one making this message so you gotta make a an independent decision locally which ends up bifurcating the state space in the sense that it creates it well it deletes the common future between different states and so you can kind of locally make a decision which kind of split to the protocol space in a way that normally because protocols would try to coordinate every kind of split in the protocol space which are they all agree before we take it but this is and this kind of gives you like a little hint like what's going on the kind of in the background so basically but the main point is this right two nodes will have a common future state as long as the union of their views exhibits less than some number of Byzantine faults so if you know your view in my view if we were to send them to each other so that we had the Union of reviews and we didn't see too many visit defaults then like that Union represents the purpose of the protocol state that we can both transition to and and therefore you and I have consisted consensus safety so basically if there's not more than T faults then we have a common future it's kind of what we wanted basically if as there's no more than the tepees and defaults in the actual Network then nodes will actually only ever visit States such that their union exhibits less than T Byzantine phones and therefore will have this consensus safety due to the property of having common features and the flipside is like oh look if there's consensus failure that means the nodes didn't have a common future which means that the unions of their states exhibited more than some number Byzantine faults because otherwise that would be a protocol state and they would have a common feature so somehow by allowing the states of the protocol the states of this weird protocol States and protocol state transition and graph or to be sets of messages which say what protocol state they're at which exhibit less than some number of Byzantine faults like like allowed us to make sure that noes have a common future as long as there's some number Byzantine phones and it's kind of really quite elegant because the only thing we really know about the protocol States at all is that they say where they are so that we can measure Byzantine faults like there's an I haven't said anything else so the somehow III went through the process of like okay I set up the proof at the first part which I wanted to satisfy and then I came up with like a construction that satisfied it rolling out the specification a little bit more so first I say okay look we have protocol states and transitions this estimator definition of safety if notes have a common future state then they have cuz that's a safety and then we go and say look let's guarantee that knows have a common future state by making protocol states themselves sets of messages that exhibit less than some number Byzantine faults because the Byzantine faults were the fundamental thing that lets us that stops us from having a common features and so there the also the fundamental thing that can keep us having features because if we if we if we can detect them and no there's not too many then we can always kind of safely reemerge so that's the end of part one that's the part with the analysis in this and the kind of math the part two is more like more like protocols still some math but not much if you if you if you if you guys want to take an opportunity to leave and come in right now and let's find I mean if you have any questions also would be happy to take it right now yeah Oh Rob hi hi Rob I'll repeat your question okay great question Rob so the question is like oh look can we like is it some case to be prohibitively expensive to check equivocations because like oh look I mean if we have like an arbitrary again we have to check if there's a path between two nodes that can be quite expensive so you know I mean the answer is like yes there are and yes this is interesting research but also all of the stuff that I'm specifying here isn't design it's not it's it's more like the kind of semantics of the implementation as opposed to actually how its implemented so in an implementation we're gonna have things like sequence numbers and it's gonna help us a lot at making sure that we don't unbounded LIGO in weird directions so but the way the so the way the things are implemented so they don't blow up it's kind of a separate topic - how are the pieces of the like protocol like factored and understood in terms of the consensus safety proof so like even with you know you can so we can modify protocol states and messages to include more information and still satisfy the same proof right so somehow the benefit of this and will see this as a talk goes is that we can easily change the protocol without changing the proof because the proof kind of applies at this kind of abstract level and so we can add things to our protocol message to make actually these checks efficient and like we do in practice because in practice we can't be doing crazy things but in theory definitions can be like you know like you can do all sorts of really inefficient stuff because it's just a definition and you never actually use computer yeah great so so there's a lot of actually potential concerns that if you just look at the construction you like oh my god it's all gonna be computable like it's gonna be practical and but don't worry it'll be practical so for each of these protocols what we're gonna do is we're gonna define protocol messages and the estimator and that's pretty much about it because by defining what the messages are and define what the estimator is we basically give everything that is that wasn't specified already in the at least I'm like that the the main piece of the proof so we're gonna do we're gonna do this for the binary consensus and then for the integer consensus and then for the blockchain consensus and then we'll talk about some of the things before doing it for the char data consensus for the sharted watchin so let's go for it so the binary consensus protocol has the messages have three parts there's like an estimate which is like a zero or a one sender which is like this this name of this consensus forming node and a justification which basically is like a point a protocol state or if your implementation focused you might think of it as a fingerprint of a protocol state and and prover for us is just a set of messages namely like the set of like the state that the node was at when they met sent that message so the set of messages is quite simple basically you have a bit a sender and then another set of messages so any message has that shape and then it kind of bottoms out at the empty set so like at the message that zéro have a bit ascender andin and an empty set that message is a height one have a bit ascender and then set of messages a height zero message that high to have a bit a sender and a set of messages at height zero or one and so on and you can kind of define this set of all these messages that have bit senders and end sets of messages and then a couple definitions that we're gonna need and then we're gonna keep our using so a mess of a message is in the dependency of another if it's in the justification and you might think oh well if these sets are not really are necessarily gonna be the whole the whole state that they were in because I wasn't really required by the equations on the left even though I said I'm putting on the right you know I said on the left then you can think about going in the judge messages justifications and their justifications and kind of doing this closure but basically if a message is kind of down like causally before another it's in dependency a message is called the latest message if there's no message which it is a dependency of so all of these protocols were going to look at are going to be only a function of the latest messages from the centre because forming notes like if you see their latest messages you'll just ignore all the other ones so we need to have this notion of latest message so the binary estimator is pretty simple it basically will but first we have to define a score and the score is basically the weight of the validators who have a latest message with that estimate so if the latest message it's like three validators or the total weight of 20 have a latest message with an estimate of one in some particular protocol state then the score of one will be thirty in that particular protocol state if the and then the the estimator basically says oh look we're gonna take the one with a higher score if more latest more validators by the latest message say one then we pick one if more validate about list my latest measure zero then we pick zero so there we kind of have it it's kind of boring but we have protocol states which were these like sets of s of the form you know--but sender protocol sets of messages and then estimated which maps sets of messages to 0 or 1 depending on whether the latest messages from those sets have more weight according to the senders on 0 or 1 so it's pretty simple estimator pretty simple protocol states if there's a time I doesn't really matter actually can do pretty much anything we can throw an exception we can I use if we use propositions non-deterministic choice always return one or the other these are all various options that have tried at various ages that it just doesn't never end up ever affecting anything so this is how we might represent a protocol state for the binary cuz it's a protocol we have three senders v1 v2 v3 and they've made some messages so this is this is representing a set of messages there's six sorry six messages in this set interestingly the two messages by the first validator are an equivocation because they are there there are two messages each of which have an empty justification and you can't be at an empty state twice because after you produce the message you move to the state where you see that message and essentially this kind of shows you the messages and there are estimates so the sender's the estimates and and the justifications right the justification is any set of messages ten downstream from them the the sender is the vertical position and the estimate is the bit we can you know this looks pretty because I drew it up somewhere nice but this is a simulation a little clip for my simulation where basically it's somehow and this at this state it turns out that like zero is safe meaning that there's no way we can add messages to this state at least without any Byzantine faults in order to change the majority from going to zero from zero to one right and then somehow this local notion of safety that I can't pass around messages locally it's a closet change from 0 to 1 is is gonna is basically is like it's the local notion of safety that we're gonna use to get our distributed notion so and and basically we're gonna like watch a little simulation here and and then and these are basically nodes running this protocol whenever they make a message it's because it's the the value of the bit there is the max weight given the latest messages in the desiccation and eventually the these know start to notice that the J's are safe at which point they're not going to change their minds but they still same they still make messages if we make messages in like a round we also we get we get consensus pretty pretty quickly no this is actually so I'm using a safety Oracle here that doesn't detect safety quite as quickly as it happens but we'll talk about safety detection a little bit later also another one those things that you should worry is maybe intractable because you have to look at all future protocol states so now we can talk about the integer consensus it's very similar to the binary consensus we have some set of protocol the protocol states are sets of messages that exhibit less than results this time the estimate is an integer but we have a center in just occasionally the same way instead of using this Max weight by latest messages we just use the latest messages and do a median the median is you know just justify an estimator right you take your protocol States you look at the latest messages you have each from each of them an integer each of the validators you have a weight so you can do a weighted median and we can watch that happen to this is might be useful for something like time stamping who knows it's like a consensus protocol that replicates an integer right normal people think about consents protocols that replicate some kind of like sequential state machine but what I'm hoping to kind of show with this approach is like oh by giving different values of the consensus by different different we can generate different consensus protocols that all have cassettes of safety for even though they're replicating radically different kind of stuff cool thing here is like oh look this value 78 that we came up with was never proposed by anyone oh it was never mind sometimes they come up with values that are never proposed or anyone but not this time because of them because it's like message arrival stuff so this is like doing rounds so the other thing that's kind of nice about this whole thing is like I'm not really bound to any particular message shape any set of messages will do and I consider all possible ways that I could add messages there's no real synchrony assumption there's no restriction on doing rounds or Forks or anything like that and we're gonna see this more now at the blockchain so with the blockchain we have very similar protocol again protocol the protocol messages have estimate senders and just ocation but this time an estimator is going to be a pointer to another protocol message which is kind of understood as like the pre flock pointer so from any message you can follow the pointer down to the next one to the next one to the next one all the way down to like the Genesis block or maybe one without a pointer or the points to the empty set so in this case it's again exactly similar we don't really need to reason again about because as a safety because we know that we have to set safety because we only visited protocol states that exhibits less than some number Byzantine faults and that's enough and so let's define this estimator we have we have to define basically a four choice row the Maps this says sets of blocks that we have to a particular block chain out of there we use the ghost mines Casper the Friendly Ghost right it's the greedy greedy heaviest deserve subtree originally by like aviv Zohar and Yana found some pulovski so so here we so basically the way that the ghost 4 choice rule works is you start off at the Genesis block then you go and you look to see if there's any any any people who built on it and if there's only one you just kind of go out there and that and if you look at that block you see if there's anyone who built on it if there's only one you go there and at some point you get to the split where you have two options about which which block to follow down and and whenever you have a fork like this the greedy heaviest observe subtree rule basically says or look at the sub trees on either side and pick which one's heavier in our implementation in our spec all these all these protocols only work based on the latest messages for the validators and so we just look on based on the latest messages whether the validator is by weight are on one fork or the other so in this case the first two validators are on the left fork and the right three validators are on the right fork and so like let's assume that the right three validators have more weight and so then for therefore a four choice rule will go right at that first juncture and then the next juncture it depends on where the validator 3 has more or less weight than validator 5 but let's assume that he has more and then we well and so then our 4 choice will be this this fork that kind of goes like that and ends in the middle block so that's kind of the estimator it's basically like another one of these functions that Maps protocol states to some kind of like average or election or like a little you know in our case there's a fourth choice rule that like the validators were kind of all pick the same Forks if they look at it and the important thing about these estimators is kind of that if validator is if the latest messages all agree with an estimate then the estimator also returns that estimate or it's also kind of close to it so that we don't get unstuck so imagine if we had done say for example binary consensus but with instead of using the max weight we use the minimum weight oh that wouldn't really work because you would whenever you get to any state where a majority had the same value they would move to the other value and then you know so basically you'd have this kind of all constant a like like adoption and abandonment of values so somehow I'm comparing this ghost rule to like an average or this max weight function and it serves the same role in the protocol and this is gonna be very similar to the other protocols in terms of our visualization the messages from the same nodes are aligned vertically only now instead of having the like integer or the bit in the node we're gonna use this blue line or the story this dark gray line in some cases the dark grey line possibly blue blue if it's on the latest message dark grey otherwise to indicate where the previous previous block pointers are so the previous block pointers are the estimates associated with these messages and they everyone whose message is basically like before kind of has to have an estimate that is justified in the desiccation so like the fork the the value the estimate has to be the value of the estimator run on the justification so if you build a block somewhere you include in the justification the the proof that you you're building this on the end of the fork choice rule in your view so we kind of have a relative the high degree of accountability to where you're mining because if you mind here and we saw that you previously mined there and that and and the view there says that that's the higher score fork then like that's kind of an invalid lock you're not really allowed to make it there because every fork choice every time you make a estimate it has to be justified by the estimate in the justification so the estimator is you know Maps protocol States values a consensus in this first part of the data structure we put a value the consensus and so we want basically be estimator in the just occasion to be exactly equal to that message exactly to that value and here's like an animation of this blockchain cuz it's protocol are just kind of doing this thing randomly we're just looking around a message propagation order and eventually finding some safe blocks safety detection again is like coming up next and basically it has to do with like oh how do you actually tell when things are safe and the reason why we left it out is because like oh we're gonna have the same safety Oracle for all three of these protocols and looking at them is gonna help us a little bit here's another one if we make a we make a round robin we get to this really nice thing that always like to show off doubt where we had a really really low overhead for Byzantine fault tolerant asynchronous consensus where like every additional message at some point causes a block to jump over the fault tolerance threshold meaning that asymptotic cost of consensus goes down to one block a block assuming there's kind of nice it's in than you're able to make this nice round robin shape which may be a big if so now we're talk about our safety Oracle which is gonna tell us when things are safe but the first a little water break any more questions oh yeah questions like oh is this like a dynamical system and do I have a convergence the answer is I don't know and hopefully I'm not really dynamical systems guy I can't really but i but i but i do i do think that there are like definitely parallels of the kind of you know attraction that you needed an estimator in order to create safety but uh but but you know i can't really comment I'm not really a dynamical person yeah yeah that's right so the observation was that like oh we're not there's no non determinism so are we sacrificing liveness and basically yeah I mean I kind of said at the outset that is not gonna be asynchronously live however I have a section on liveness I'm gonna tell you about the liveness kind of of it you know it's live in synchrony and partial synchrony but there are reasons why I'm not comfortable with any of those solutions that dude news like thresholds signatures or whatever to do to get a synchronous asynchronous and I'm gonna come to that and soon how are we doing on time great or so we're still we're still doing good on time you guys awesome so we have a safety Oracle here that I'm going to share with you but first a little war it's a few words about safety Oracle's so safety Oracle's are basically what we call these programs that try to detect whether or not given proposition is safe at a particular protocol state there's some how it's it actually wasn't necessary in our construction at all that we detect safety in order to actually become safe on these propositions but you know if you don't detect it accessible vault can never actually tell you if it's ever decided on anything it's kind of an interesting thing that you can have a consensus protocol that like makes decisions all the time but doesn't know about any of them until it detects it but the things that we use to detect them are called safety Oracle's and there's there's an idea of an ideal safety Oracle which kind of does a perfect job of determining safety and we kind of liken it to executing the ideal adversary which does a strategic search of your protocol future States for one that disagrees with the estimate you're trying to say is safe so it will like like surgery protocol feature States for like specifically the ones that will and it will negate the thing you're trying to say is safe so you know and and and you know we actually implement adversaries that basically like try it I like do actually operations on the protocol state in order to try to change the estimate which is really cool but yeah computationally not the nicest and so what we look for instead is Oracle's that are kind of lower bounds to the idea Oracle no Oracle's that like whenever they say we're safe we're actually safe but which are much easier to compute and which you know in practice are like the tech safety plenty of the time so we're gonna we're gonna define the klique Oracle that's gonna hold for a class of protocols with basically these estimators that have this kind of majority agreement property or if you have like a bigger group of validators over here then over here and and like this one thinks on so I'll agree to some estimate and those ones I believe the opposite then your estimator is going to agree with the majority so there's a kind of a precise agreement with the majority estimators where we're only looking at latest messages this safety Oracle is going to this is Jeff York was gonna work with so we're gonna basically define this notion of like agreement between estimates so in integer it's pretty straightforward or a bit it's straightforward okay they're the same value but with the blockchain it's a little more complex we say that a block agrees with another if it's in the blockchain that you basically you can find it by resolving the pre block pointer so it's kind of blockchain membership so like you know I'm like you will agree with my blog if you choose a block which has a blockchain that includes my block so this notion of agreement is gonna be important for our first safety Oracle definition basically goes like this okay well we have a click of Oracle's a CLIA validators have that have the following property in some set of instead of set of messages each of them have a latest message that agrees with the with the estimate in question the one we're testing the safety of each of them see each other agree with that with that with that message and they can't see a new latest message from each other that doesn't agree so they they all see each other agree they all have and they and they can't see each other disagree with a new latest message so if I have a set of messages and you know Alice sees Bob agree but but in my set of messages there's a new later message from Bob which disagrees then that would like rule out Alice and Bob from being related in this cleaky way that we're talking here so if we find one of these clicks where all of the validators see each other agree and they can't see each other disagree then if they have more than half of the wait then they well firstly no matter how much weight they have they can't really convince each other to change their estimates because of the nature because they can only send each other messages that agree and can't see from each other messages that don't agree and if that more than have to wait then they also can't be convinced by validators outside of their set outside of the klique because they have less than half the weight you know and this is all assuming no equivocation what kind of get to co-creation in a second then like you'll be safe you'll be locked on this value because this majority sees themselves agree with it can see each other disagree with it and therefore can't be convinced by the minority because the menorah has less weight and there takes some disagreed from within the majority but the definition of the click precluded that because you can't see disagreement from inside the klique so if we have some clique with some weight W out of it so do we subscribe II with with was out of some total weight then actually we can we can reason about the fault tolerance and it's basically like not more than two times the weight of the click - the by - the total weight and this is like precisely corresponding to the overlap argument for consensus protocols but we do reason we have the reason about a slightly different slightly differently in terms of creating a larger coalition of knows which agree on some conflicting estimate so if you have some group of group of weight W here if you want to change your mind from from that estimate they'll agree on e to like naughty then you have to see some group that's bigger than that and and then and so we do this kind of overlap argument we're basically okay well we have a majority w e the minorities WT - oh we need to add to that minorities until we get something that's bigger than WWE and this was kind of equation here don't you team I so you eat plus f2 great huh no he means right I mean it's like oh look we're gonna add some number of faults to the original minority these represent equivocation faults from them from the majority and W II so that we have more weight attacking e than defending it and so and so and so that's kind of like our fault tolerant December it's like very normal kind of fault our December but the interesting thing about our click here is you it was it like the notion of our cleat doesn't have any rounds in it right it just has the notion of latest messages and agreements and leads us to our next time topic here subjective fault tolerance thresholds which is gonna help me address your aliveness question actually the first a water break I'll take another question - if anyone has one all right well subjective fault tolerance thresholds one of my favorite things in because that's the protocols which I've never sat which which I've been fighting for as long as I knew is an idea or like an aspiration but which I like can finally do like very like very lively it's basically a subjective fault tolerance threshold means like oh look the fault tolerance that I have when I'm running accessible and that you have when you're running the sense protocol are not the same I run the protocol at my level fault tolerance you run the protocol your fault tolerance and you know you won't fall out of consensus safety with more Byzantine faults than I will if you're running at a higher fault tolerance threshold it might take you longer to decide you might never decide if you're running out of photon or special that's too high however you also won't be new your you will tolerate many more consent equivocation faults for anyone else who also has that like a level of fault tolerance or more so basically if if I have once like the set of protocol messages for any these protocols is defined kind of independently of the fact that you can count faults on them and so if we if we define the same set of messages and you can count faults and exclude them if there's more than t51 faults and all count fault to exclude them if there's more than t2 then we'll have a common feature protocol state as long as there's less than the minimum of t1 and t2 faults so it it with a cousin to safety proof works kind of just the same even when people are running at different fault tolerance thresholds but you have to kind of use this minimum of their fault tolerance thresholds rather than using any one of them so the justification for the for the subjective fault horseflesh hold is mostly economic to me but also it's a kind of a elegance thing the I like when you have an in protocol fault tolerance threshold that creates focal points or cartelization so imagine you have a fault tolerance threshold of like F then like what ends up happening is like the cartel that has F has much less power than the cartel with like 2f with like F plus 1 and then the cartel with like F plus 2 doesn't really have that much power than the cartel of F plus 1 but then you go out like the cartel with like 2f and as I go the same amount of power ourselves fs1 and then you would like two of us one and all of a sudden you have this like max power cartel so when you have an empirical falter on a threshold as soon as you can meet the threshold of the you know a little more than the photons to break it or the quorum and or like or the Byzantine quorum in order to like you know like the N minus T of them then then you have really a lot more power than if you had slightly less so the the the in protocol fault tolerance thresholds like create abnormalities and step functions in this strategy space they create clear clear focal points for like you know I mean if you're if you're participating in a probe stake system and you are for example a newcomer to a cartel and they already have two-thirds of the weight in there like your value that you're contributing to the commitment of consensus values is zero assuming that they're connected and they're able to do it themselves so you don't have much clout actually you're not increasing the fault tolerance to the protocol as far as they're concerned you're not really contributing to the cartel and so like the cartels like shouldn't be stable I like just over two thirds plus one notes and and kind of like imagine for example if Bitcoin were to tell you exactly how many confirmations to wait before reverting a block I said before refusing to revert a block so say like okay after six confirmations we were refused to revert well then someone would like create a block create a bar team that's like exactly seven long you know do the minimum amount of work to cause consensus failure and like you know just and sending people with the right timing right but if people have different numbers at which they set in which they decide not to revert blocks then it's not kind of much safer because like the protocol isn't so easy to attack because the adversary doesn't know what everyone's fault tolerance thresholds are and this is also related to alive in this question around the kind of why don't use crypto for live news and the reason is like oh I've never seen a way to do that that doesn't require it in protocol fault or social so like if you can find a way to guarantee asynchronous aliveness without any in protocol thresholds in terms of number of nodes required to move you on some state of the protocol for example then that'll be really cool and I would learn a lot but but I don't really think it's possible but we'll see but but we never know so the subjective fault tolerance threshold thing something I really advocate for but is as far as I can tell impossible in round based consensus protocols any kind of protocol that says like oh look let's prepare then commit oh let's you know do one round and then another is gonna have to have some notion of oh look this round is complete which means that they hey you have to have some main protocol threshold which I don't like for mention reasons and so you know I'm actually a big fan of forking protocols with like arbitrary tags and no rounds and I think they provided an excellent alternative to commit to the two-phase commit protocols let's talk about liveness so you know somehow we want liveness in a synchrony but FLP impossibility says we can't and we kind of and I kind of know we can't because like I can I can always find a protocol state which so if I'm not safe then I can find a protocol state the opposite value which isn't safe that I could follow the finer protocol state on the on the opposite value that isn't safe so I could kind of know that I could be stuck forever if I'm allowing any message arrival order however we have kind of seen no we have actually said anything about when when knows or even trying to send messages actually all we've said is like knows have set sets of messages of states and like when they send a message they say what state they're in but they we haven't said actually when they should send messages so all of these questions about like what like what the nodes are doing when they're kind of left out of the spec which means that like a we don't have a Leibniz proof but also it means that we have a huge amount of flexibility on what the strategies are and also when all of these are independent completely of the mechanism that guarantees because that's a safety so I don't have to struggle and worry about my whether my I lose safety what I'm trying different about different liveness strategies out but you know we have seen in observations like like the simulations so far that you do kind of find and defining safe States sometimes and what this basically says is oh look there are tags which we can describe which do have liveness which in the sense that if you manage to make that shape in the future then you will decide on a new value and therefore like you well if you have a precise message rival or that what you want to target well in a synchronous network we kind of know how to do that and in a partially synchronous network also and so it's quite easy for us to construct quite trivially algorithms for guaranteeing safety the other really nice thing actually is like oh we can we can we can straight-up say look do some proof of work you know whatever you like any kind of sense of protocol that like ends up building a blockchain and can you even show we'll do it in a partially synchronous network will be kind of enough for our liveness and also won't factor at all into the safety proof so there's a lot like a big extent to which I can like literally go and like pick live in this proof sort of because out of deterministic assesses protocols and use them without thinking about the safety side so now let's talk about this whole overhead and performance thing even though it's obviously we don't I haven't said one knows make messages but I can't I can talk about like the edge cases and I can talk about this trade-off this which i think is like a really fundamental trade-off any consensus protocols basically says you know you can only have two of three nice things of low latency finality low overhead and large number of validators and I I think it's like you know really kind of unfortunate because we want all of these things right super low overhead super Larimer validators and analogy but it's not gonna happen traditional consensus protocols all kind of explore the trade-off over here on one side of the triangle or they where they kind of try to go at really low latency to finality and they basically need to choose between having low overhead and large number of validators more validators they put on there the closer I get squeaking over the because the overhead gets so high and the fewer validators the lower the overhead so if you want to have low overhead low latency finality blockchain you really have to have a small number of validators block chains oh and and and with all of these protocol this is the Friendly Ghost we can i we can we can explore that trade-off by doing this kind of rounds based approach where we have like Browns of blocks which would you lean to things being finalized really quickly but with a lot of overhead in terms of the number of blocks that are kind of orphaned and so with by doing rounds for every block oh we can get really high overhead for a large number validators or moderate overhead for a small number validators but get really low latency finality with with watching protocols we normally do something like we have something like no finality but we have the same incredibly low overhead for any number of validators like any miners can show up doesn't matter how many any state your stroke doesn't matter how many and still that overhead over the blockchain at least after difficulty or adjustment should be the same and so this invariance of overhead in terms of the number of nodes is like really remarkable and something we've seen block chains but has never ever been observed in traditional protocols but typically no finality but we see with like this kind of particular protocol execution of the same protocol is the one that we just want doing the rounds is that we can achieve the same level of low overhead for any number of validators but actually we can have we can also have finality we also have like asynchronous Byzantine fault tolerant consensus like you know decisions and the basis and so it's like quite cool because we get to have like somehow instead of being up instead of being off on the off the corner we get to like jump right on there we're and we actually have like instead of a completely unbounded latency to finality we have like Oh bounded by like the number of validators latency to finality like you know Big O the number of validators so basically Mike so and then my next claim is it like look we can we can actually try it we can we can explore the whole trade-off triangle with different and egg structures of these protocol messages and and and I think that's like pretty cool and like all I can really offer you for that in terms of visualization right now is this it's kind of a random one it's not it's not really strategically trying to minimize the amount of overhead but the number of blocks that had to be produced for this number of blocks of finality is still much less than if we were to do rounds of messages for every block and finalize them one at a time and so this represents maybe in the middle of there the of the of the trade-off triangle where things are finalized a little quicker but the overhead is higher but we still get to have a moderate number of validators and that's kind of that's kind of the goal to me right that we somehow I think that like if the middle of this triangle is way better than there and also way better than there if you can have the overhead of your protocol by reducing your latency didn't to finality by by by by increasing your Nate latency finale by a factor of two I think a lot of people would take it especially if they're running with a large number of nodes and then that's kind of the promise here great so now we're ready for some starting but first the water break any questions any questions yeah yeah so so the question is like oh why is it important - allottee rather than just probabilistic one like in proof of work and then the main reason is that the probabilistic thing works as long as there's some less than some number Byzantine faults whereas when you have like real proper finality when there's more than the number of Byzantine faults you won't revert your blocks so like when there when the mining imagine if you just decided after seven confirmations in Bitcoin like 20 confirmations there's never to revert then like mining and the cartel of miners could never revert more than 20 blocks and that's safe enough like 20 blocks like I would recommend it you know just like set your thing 20 blocks like never revert if you can because then you like okay well maybe you have consensus failure with everyone else who goes on the longer chain but like our odds are if there's a really long reorge it we it's it's like gonna be like so so it's a basically finality represents a strong defense against reversion attacks because it like this allows reversion in the context of any number of businesses faults if you're willing to assume that the network is synchronous and you won't ever have some number Byzantine faults then I think something like proof work could I mean technically does work but let me also say that like proof work is not a synchronously safe and that's like a separate issue so that it actually it's not really clear how many Byzantine faults it really takes so a whole bunch of issues associated with proof of work especially once you start thinking about economics but in terms of like the specification the consensus protocol it's really great really simple all right any more questions so you ask me how I can be more efficient or now asking about like how the protocol is being more efficient on Network overhead normally what we would the way that that's done is like oh we have we have we use a synchrony assumption and we make blocks and we make messages in a chain it turns out to be like a credibly low overhead way to do things like for all the cassettes of protocol it's like whether it's integer or whatever but it may not always be the thing that you want like for example for the integer protocol you want everyone to kind of give their initial guess and then do the median rather than to just try to minimize overhead by copying what the other person said so overhead is I mean basically the way we do it is by targeting structures that have really low overhead the interesting thing about forking though is like okay the the fact that we have a forking protocol is the only thing that allows us to get overhead this low but the fact that we have a 4k protocol also means that the overhead could get quite high if our synchrony assumption fails because you could have things revert multiple times and so we're kind of this optimism that like lets us get really low overhead it could also cause high overhead in the event of a synchronous network so it's not a free lunch but it does look and sound cool so hey all right so I guess let's talk about charting now so shorting is gonna be actually we're gonna end up following pretty much the same process as before basically because the safety proof says nothing about the which protocol states knows actually go through is this it doesn't actually it only just stipulates that they have a protocol state in common it doesn't require that they actually get there and so we never actually had any requirement in our construction at all that all nodes decide on all values or that all nodes see all messages or that all nodes you know make all the same decisions all of that stuff is stuff you normally assume as being part of the sense of protocol but didn't have anything to do with our construction in terms of the common feature protocol states or in terms of the maintaining lessons visiting me like in terms of the Byzantine fault counting and so actually we're gonna be able to straight up have a Sharda cuz that is protocol without changing the safety proof at all just by replicating a shard of data structure and not having nodes go through every protocol state so it's really just gonna be pretty much the same as before only instead of doing like an integer or a bit or blockchain we're gonna do a sharded blockchain so show double chains are actually very similar to block chains um this is the current like this is a very basic the most basic setup that I really know you basically have like block chains on these things called shards and these shards can sometimes share these things that are called merge blocks or you just call them cross shared locks but it's kind of long and cross shared blocks or merge blocks they have they have this property that they have preflop pointers on both chars or any shards that they keep that they are across and that they can be and they can be pointed to they so they can be a previous block of the chars that they merge so both they both point to charge that they merge and they can be previous blocks of chars that they merge so essentially they can you know affect the state of a shard and that shard can pick up on that written state and right on top of it so it's not so basically like they have free block pointers and so they're and they're considered blocks and I shard for this for the purposes of the pointers on blocks on that shard so essentially we have this kind of crazy long shot long block here which is on both shards and it acts as if it's a block on both shards but it's gonna do some like cross shard synchronization for us I hope this makes sense because now we got some some equations here and basically just as before we're gonna have like messages have senders some justifications but instead of writing all that stuff out I just put that in Dee Dee's the block data it includes stuff like for example the sender and the gestation and maybe one day transactions and I'm just kind of exposing the other stuff and I used to give this kind of this definition where I start off with like the messages of height zero and then to find the message I want and then and then kind of take a limit but now I'm gonna use this like more like recursive like type definition type formula so that I don't have to write a million lines and so basically it says look a block on shard X so X is like a short identifier includes like a little map from X to a block on shard X and some data or it's a merge block that is merging some set X which is a superset of the unit you know the the singleton set X or is the genisis block on shard X and then the merge blocks that merge some set of blocks basically have a bunch of free block pointers and some block data so essentially I'm just describing in kind of like math like this this type of situation where I have blocks that have pointers on multiple shards and which can be pointed to by multiple by multiple shards so there the the second line shows that oh look we have pointers to multiple shards and in the first line in that with the second term there basically says they look like a merged block that merger start X is considered to be a block on shard X which is which is enough to let you point to it in this first part of the definition somehow it's like a concise way to just to give like the minimum type definition for this charted block structure so we have a fork choice rule for the sharted thing and it's gonna return a block chain for every sharp so rather than you know like a normal block chain you just locally take some set of blocks and we get a single block which represents the block chain underneath we're gonna take a set of blocks and then we're gonna get them for every single shard under a block and like that block is gonna be in that shard and we're gonna get so basically for every shard a fork choice and this is kind of the fork choice the Charlotte fork choice rule now thankfully like you're not gonna need to evaluate it for every shard but that's the function signature anyways so you can you know you can you can you say look I can evaluate the fork choice rule for this protocol state and this shard and find this block you don't have to go and evaluate it for every single shard so we have this great product this great thing that we're gonna satisfy it's called fork choice and force atomicity of merge blocks basically says look the fork choice rule itself is going to make sure that these merge blocks are in the fork choice of both neither of the shards at their merge so like the fork choice rule itself this like thing that like did you know isn't it like that like may end up orphanage stuff and like you know it's like it's like a fork choice role so like kind of as an estimator it doesn't really isn't strictly deciding he's gonna have this atomicity property which means that like you know whether or not it's decided the the the block which is a merge block is gonna be in the fork choice rule of all of the shards that emerges or none of them so somehow the fork choice rule cares about these things called merge blocks and it makes sure that they're atomic and this is the definition right and that's gonna be useful because we're gonna do cross guard atomic operations and you know we need atomicity for that because we don't want the call never arriving or the money disappearing and never arriving or never disappearing and arriving but yeah how do you take a question I didn't know yeah so well so actually so so there's a couple things one of them is actually like oh the trickiness did do some tricky thing here we're like oh these are not actually pointers this is just straight up nesting and so we're not gonna get any kind of DAGs but you might get a situation where there's a kind of inconsistency but you know that's something that that actually is not something I want to resolve at the level of the block structure but that I resolve at the level of the fork choice basically my four choice will never choose that but I allow it in the block structure but yeah that's a good question and good observation sorry so the I guess it was somewhat complicated but basically there we have a slide a little bit later that talks about this and so I'll bring it up so we have this great definition of cross shard merge block atomicity which is guaranteed by the fork choice so this as opposed to like all the starting solutions that do a multi phase commit probably got prepare and come in for atomicity you know I really believe said this before but I really believe in for King and safety detection as an alternative to two-phase commit I don't think like I think two-phase commit to phase voting protocols are like a thing of the past and the blockchain kind of killed them with confirmations and weight of working but it's gonna take a long time for people to realize that I think but so somehow I'm really proud of the fact that this fork choice we got it's atomicity across shards and there's no phases it's just done with this forking thing now we have we actually have some some other I'm gonna share some other definitions which aren't gonna be satisfied by the protocol that I'm going to share but which are quite cool so we have this like notion of remember we had a notion of safety of a property well now we're gonna talk about the property of a block being in the fork choice below on a particular shard block is safe on shard X if for any future protocol state that block is in the fourth choice role for shard X and I use a little subscript to like denote which shard I'm looking at both for the block membership operation and the fork choice rule and the safety and the safety protection and so then we have this like work choice enforce atomicity of safety formers blocks which is a weaker notion so rather than a block having to be like in both forks or neither always for any estimator for any evaluation the estimator it needs to be atomic only if it's safe so if the block is safely included in this shard then it must be safely included in the other if it's safely excluded in this one then it must be safely excluded in the other for any shards that are merged and this is kind of a weaker definition which means they're like oh we maybe take less less overhead to guarantee it and it's still still quite quite strong but then this is kind of like the weakest I think maybe even the weakest possible cross shard atomicity or like merge block atomicity criteria and basically says if a merge block is included safely on this shard then it can't be safely excluded or in any of the shards that emerges so I'm not saying that it's necessarily going to be included might not even ever necessarily be included but very least no values that ever exclude it no alternatives could ever be decided on so it could be that like this if the short it merge block that merges my shard and yours gets in my shard and safe then what you can't safely exclude it in yours you might never include it but you can't safely exclude it and I think this is like the weakest definition of atomicity that is kind of tenable in the sense that it like it just falls short of like breaking where you have like it safely included in one shard and safely excluded in the other because then the whole point with these merged blocks is that they're gonna be at least eventually in the fourth choice rule of both shards that they merge or neither because otherwise we knock it out we're not going to enjoy the atomicity of the operations that are conducted in this block so now we're gonna getting a little closer to the spec that is going to satisfy the fork choice and force atomicity of merge blocks we're gonna restrict things a lot now we're going to only allow merge blocks between shards that are connected by an edge in this binary hierarchical structure so the brute node can merge those two the nodes in the middle can each murder three different shards and the ones in the bottom only have one one shard each that they can merge with which means that they can only have there's only one of the shards they can have a block in common with and basically the the the hierarchy is gonna work such that the blocks in the that block the shards the fork choice rule of the shards letter lower in the hierarchy our function of the fortress rule of the shards higher but not vice versa so the ones in the higher higher in the hierarchy kind of strictly dominates the like earlier one the ones lower and the lower noble shards gets you just ignore what the sorry the top of the higher-level shards get to ignore what the lower level ones are doing so basically the the the shards are lower in the hierarchy are gonna be guaranteeing the atomicity with the merged blocks that are that get into the higher chain so basically imagine that we have his parent start on the left and child chart on the right and now instead of drawing the merge block has a big rectangular thing I just drew this arrow this line which says that they're the same block sorry about that it's before I figured out the rectangle thing actually before someone told me about it so the so so imagine that the the block there the merge block is the most recent one in the fork choice rule of the parent then the child starts their fork choice rule there so like the fork choice rule the start of the child starts at the latest merge block in the parents fork choice so definitely if the merge block is in the parents fork choice it will be in the child's fork choice for the latest one and moreover if the merge Blanc is orphaned then it will also be orphaned by the child chain so the child will reject a block if it's an orphan merge block so the child has to be mindful the parents fork choice and if they in their current view haven't included a merged block then it must also not be included in the fork Cho in the for choice of the top and this guarantees the other side of the atomicity with namely if it doesn't include if it's not included in the parent then it also won't be including the child so we kind of have our oughta Missa tee right if it's included in the parent then it's cluding the child and if it's not including the parent it's not including the child and there is slight caveat which related to Daniels question so I think comes up in the next slide but firstly note that okay well the charge cards are kind of like I had a loss for when the parent Shard orphans blocks from their chain so the child shirt might have initially had those two blocks on the left in the chain but then a new merged block was created and because it got into the fourth choice of the parent orphaned those two blocks so therefore the child shard kind of strictly has less security than the orphan in the parent chart because the parent can can can orphan stuff that's after the most recent block that it has a merged parent and this is kind of related to Daniels Daniel's thing another kind of requirement was kind of super important is that like if you make a merge block with a shower that you've already merged before and you're the parent or sorry if you include in the fourth choice rule so that the parents only allowed to include in the fourth choice rule merged blocks that are later than the previous merged block that they included for the child there's a little convoluted but basically like the picture says it all if you really the the parent has to be nice and always point to a later block then then put them in the block they pointed to previously so if like I have a merge block and then another merge block in the same parent shards chain and it merges the same other shard then like it has to be that like it merges it at a later point as opposed to for example or for trying to orphan something else previously merged so in the second case here like before that top merge block the the child shard would have started as Genesis block on the right there and then and somehow like something that it took for granted and ended up and that merge block is still in the parent chain right ended up somehow being orphaned by the parent in the second case and so we don't allow that because like that kind of ruins our property right we have to make sure that like the blocks stay in there and so the parent has to always choose later blocks for the child cool so basically we have this binary binary hierarchical sharding where we have the fork choice rules a list of the chains higher in the hierarchy determining where the fork choice rules start and what they must exclude lower in the hierarchy in order to guarantee the atomicity of cross guard blocks are these merged locks and basically what we're gonna do is were going to assign validators to a branch of the tree so every validator is gonna have n so for like a single validator slot at least in this like first spec right has n has to be on n block chains like the root one at level 1 1 level 2 1 level three and then one at level n and and so you have to execute although you know you have to execute the fork choices of the parents or all of the ancestors to do the fort to actually execute the fortress choice well of the descendents but because it's like a tree you can just like kind of pick any branch and you can fully do the fork choice rule for any child by just doing the branch from the root to the child and so we have like two of the N minus 1 shards with every validator only validating on n of them and so and kind of like the neat thing about all this is like all of this is still actually defined inside the crack by construction kind of framework because the notion of an estimator is our fork choice rule which will like think about safety about which we can reason about safety on and our protocol states are like still sets a message that I said less than some number of phones the different the only kind of difference now is we're gonna we're being a little bit more specific about about what protocol states a validator can run we kind of we're gonna say it we're gonna cut we're to mention that go look these protocol states correspond to like being on these shards those protocol states correspond to being on those charts and as so like but in terms of like actual mechanics of the proof nothing has really changed at all we're just replicating a different kind of data structure one that happens to involve a bit of concurrency so that's kind of that's that's kind of the the basic overview of like a very first Charlie consents a protocol specification and it is notable that this is actually starting the consensus protocol as opposed to charting a data structure and still having a seen single-threaded because it's protocol love-in like the way that a bunch of a bunch of people are experimenting with starting today shorting consensus means that like you have actually a shorter distributed consistency property you have like a or you interpret your distributed Christy property in the started way normally we think about Oda siding on all the values now we just decide on consistent values even though we don't all decide on all of them and you took so some some some how I I'm pretty excited that we were able that I was able to do all of the charting inside the same proof framework and I'm excited for you know all of the future iterations of these protocols so let's talk a little bit or first breather and water break if you have any questions now is also the time yes Mustafa great so the question is like oh how do we do a cross shard transaction between shards don't have a parent-child relationship and the answer is well the only infrastructure that we have to provide it is through the Parent Child and so right now the way that will work is oh you literally have to wait for routing through the structure that said there's a lot of future work around making this better but this is this kind of it really I think does get significantly better in a number of ways like one of them is okay a matter like that you you you can imagine that like we're not stuck to the binary sharding we can have a dynamic tree structure so mention also a little bit and and also your load balancing and also there's there's there's kind of there is some research on like it kind of trying to do allowing merge blocks much more freely and it's totally possible the thing that becomes a lot harder when you love free merge blocks is guaranteeing this nice isolation of state transitions so that validators don't have to do more than some amount of work and so the I would say that like you know research on making like synchronous calls across all the shards with with the fork choice and force atomicity is still early stage and you know please join us you know you can do it okay so basically we got some future work just on the crack by construction kind of framework and process basically oh actually this protocol state structure of like sets of messages that exhibit less than some number Byzantine phones is kind of a crazy thing and I think that there could be a lot of research done on the structure of this like category or or graph we need to think about liveness strategies measures and proofs and and and basically there's just something there's there's a lot of room for lots of lots of flexibility there validator rotation right now I've only really done for the Friendly Ghost decided to leave it out of my talk today I don't know I don't know why I thought it was gonna be too long but so he is so way I have to try to work out how to do Valladares head rotation in the abstract as opposed to it as a function of the blockchain structure which I have I'm pretty I'm pretty pretty hopeful about and also without in protocol for tolerance towards thresholds of course and then and then basically oh we want new and more efficient safety Oracle's right now for example we don't I don't have a safety Oracle for the integer with median sorry with mean like if I use the average my safety Oracle doesn't work because like any one minority node can change the average and so my safety Oracle's assumptions or don't hold and so but but I could potentially imagine having a safety Oracle work out where I say like oh look this the the estimate is bounded between like twenty and ten even though we don't you know my oscillate forever between there so coming up with different Oracle's for different systems is kind of adjusting maybe having because it's protocol that actually does it a returning value using sense this actually does return these propositions about the consensus there that's potentially quite interesting because it like raises it to another level of abstraction I means that we can potentially talk about stuff like Oh like a real numbers like oh you know you're never really gonna give me a consensus on a real number in the sense of like give me a value but we could talk about propositions on real numbers all day for starting we basically need to like think more about like this idea of like how a validator duties separate and like what are the different protocol states that they like are transitioning to as a matter of like validation and making sure they're like oh they're overhead is always bounded there's um you know actually trying to build a protocol that satisfies the really weak merged block atomicity definitions is totally interesting and I think relatively open because um I mean I don't know that I have a solution and I don't know anyone else is working on it but definitely definitely cool thing also the dynamic shard structure stuff is really cool like the whole changing this changing the shard tree and moving shards around to do load balancing and - for example this idea of like temporarily isolated shards stars that like Oh can't merge for a while and then can merge again and then can't merge for a while and can merge again are the kinds of things that like who really lift the ceiling in terms of the scalability limits on this thing heterogeneous charting is another interesting idea that well maybe we'd want shards that make different trade-offs in this trade-off trying oh maybe want some showers to have really low latency to finality some charts maybe we want really large number of validators and how to think about maybe having different shards with different properties there's also an on research work like education and implementation there's a lot of it definitely can use the help definitely ready for help there's and so basically like we have a prototype it's in the etherium /cb co repo we've implemented the binary because it's the integer order on a list with fixed elements a blockchain a concurrent block schedule that spends UT exo's and the binary sharding with the cross chart atomicity that I just presented so we have a bunch of these things implemented as basically just different modules in single implementation because like they really are just just new specification of the protocol message and the estimator the rest of the code base just stays the same for the most part and so like you know I think you know like working on the prototype maybe one day making a test set and maybe one day going into production there's a lot of work future work and we definitely need help basically the conclusion I hope is that it's pretty cool and that you know you believe me that were able to define lots of consensus protocols without doing much case-by-case analysis by just benefiting from the correct by construction framework you know I think we can explore lots of trade-offs here without talking about the Byzantine fault tolerance or the synchronous safety at all which gives us a lot of ability to iterate fast and which i think is also related to why like our progress in this kind of research has been accelerated you know this all these terms and definitions are laid out and hopefully we're gonna become more and more well documented so that you guys can come in and contribute come up with your own consensus protocols or safety Oracle's or whatever and don't be shy so here we have some we have some we have some documentation we got some tiny URL links here to the papers and both early drafts and the code base and we have a kidder which I found out about yesterday embarrassingly enough so thank you thanks a lot and thanks ECC for giving me so much time to talk about Kasper um the course is is there a degree of like a concentration of Holdings has required perceive easy to work no I mean like the the the the I mean so so the main reason why that might be the case would be presumably we're thinking about is like oh there's only a limited number of slots available yeah and that does depend on the what we choose in terms of this am I stuck here in terms of the parametrization on the triangle right if we decide that we don't care about latency to finality at all like zero and which is happy to be on the order of the number of validators we show up then the barrier to entry could be very low if if actually wanted latency to finality that is on the order of hours or minutes then the number of validator slots that we could reasonably tolerate for any given you know without huge overhead is much lower and so it's a it's a it's a difficult question because it depends on like parameterization that I don't know about but I'm happy to say that I can make that parameterization and that like if it turns out that people care much more about the barriers to entry being low then about the latency to finality and that's conceivable that that's totally possible inside inside with the same protocol Cheers the question is how long have we been testing on the test at the sharding and how long it can take to get our main net well we don't have a test net for starting or at least this correct like instructions right we just have a prototype which is still something it's still an implementation but it's not distributed and it's not you know ready for may not yet you know when I mean soon I mean now who knows anyone else yeah sorry so you're asking about the upper bound on what upper bound on Oh overhead Oh latency latency okay so questions like oh what's the upper bound for latency of finally finalizing a transaction that affects multiple shards and then while so it depends on where so in the hierarchical sharding it depends on where it is in the tree structure because basically the brute needs to finalize merge blocks on the on the on the on its children in order to for them to be finalized and so if you're really close to the root it happens faster than if you're further down so but it's really hard to give any kind of known block count because like all of my definitions allow any number of blocks between any tumors blocks and I don't have any sense for that from like you know because there's um no no no definitely not definitely it's definitely definitely sub linear in the number of stars linear in the number of layers to the sharding if you are at the bottom layer yeah look we're thinking the numerous parts yeah absolutely yeah yeah so um it's it's it's so the question is like Oh what do I think about like chard locality and I'd the idea of like having like custom shards as opposed to like drawing everything from the global pool and trying to be as safe as possible it's it's it's quite tricky I mean basically there's a couple of issues one of them is like oh are the blocks produced by this shard like available and valid and if we can we gotta trust that they're valid and available then building them doing cross shard transactions with the rest of the system is not impossible however we do a limb to make sure that they're valid and available and if anyone can set up a shard with any nodes and just like do atomic transactions with the rest of the system and their blocks are not available or valid then we may have a real problem and so it's mostly I think about the in terms of architectures the biggest barrier to putting strange shards into the system is their validity the validity and availability of their blocks so I think it's conceivable but I would say it's like still like you know I mean you're asking about the release date you know last question and now you're asking or something even further round further down right oh that's a that's a good question as a whole can of worms how do we determine the availability of blocks yeah that's a nice metallic no no at the moment we have just like at least in this specification like the shard structure is like part of the value of the consensus there's like like and it's just fixed so there's no I have like assignment of validators to shards but I don't have like any nose able to create and destroy shards at the moment and basically the I mean ultimately you could imagine that kind of thing happening but it's definitely not short term you know we gotta take we gotta take baby steps and you know even though baby steps get bigger it still yeah they're super necessary I spent 8 months or something on the binary consensus before I had anything like all their consensus protocols so is there any way that this charity feature will interfere with Trenton Johnson's conversation and where cross-chain meaning meaning across different like different yeah well so whenever you're doing any cross chain operation you really should wait for some kind of finality on both right and so and you can detect finality when you're even doing an operation on a single shard and so it's it's very similar to normal cross chain kind of reasoning either you wait for finality or you have to like fork your application to match everything and if it's a but if you but if you're if you're trying I mean Robert hit two chains which aren't forking to keep track of each other then you really just got to wait I'm really not as a side chains yes I think Lyman is symantec accomplished with recurrent proof well the proof is a safety proof I think I could accomplish Lydon sorry oh yes absolutely yes well keeping the periphery yeah yeah I'm sure that I can accomplish liveness while keeping the current proof because the current proof says nothing about wine notes and messages at all it is completely asynchronous it just talks about sets of messages there's like it's just completely like I think the safety proof is completely independent of the liveness strategy and I love to keep it that way because it makes me really scared when like the safety of a protocol is like the same as the it's as secure as the lightness of a protocol yes Rob no so actually you can have like even like a tiny subset of the validators on the root and then like some other tiny subset on these other shards it's not there's no real requirement that there be is everyone on the route something I do like to put everyone on the route but there's no real requirement for that the the there is just it's it's it's just that you said like the the framework say like to recognize it's like okay well you don't need to worry about arbitrary reversion of blocks even if it's a small amount of weight on the route because with these cos protocols instead you worry about consensus failure which is like a different from block reversion and so you can have your Vox be safe and like you can tell that their final doesn't mean that someone else hasn't conflicted to finalize something conflicting but like the finality doesn't go away because of into some number of Byzantine faults so like it's not the case at all that like the root can revert finalized blocks from pains down the down the row it's basically like any consensus protocol that makes a decision can't have there their decision reverted by any number of faults and you can have like any set of conforming nose make the decisions that walk walk star in the route as far as Byzantine fault tolerance is concerned now if you're economically speaking like I wouldn't want to put a really small validator set in the road but in terms of just visiting fault tolerance doesn't matter it could be an independent sent that could be disjoint sets on every shard is fine just because of like the fault tolerance thing is I mean it's kind of a sledgehammer it's just like oh look at least this number of nodes are gonna behave well no matter what and so like the route won't will like so basically like you if the route is finalizing stuff then it won't revert that stuff if it's finalizing consistent stuff then like you know those inconsistent things won't be reverted but someone might have to like hard fork or you ASF to sync up with everyone else so it's like the classic kind of like trade off or like the the trade off between like always being able to have a common future with someone verse is actually making irreversible decisions you can always have a common future in something like before work because you always see the same set of block chains but you can also refer to any number of locks and so if you haven't if you imagine like doing this in approval work system then like a reversion in the route shard could lead to arbitrary reverse it in the lower charts but in like a system with any kind of finality that's not so straightforward because it doesn't revert it just that people have consensus failure sorry I think is that what right so that's a that's a that's actually good question so no no no I mean it's actually legitimate so so the question is like okay well we rather than doing reversion of blocks maybe what we do is we like do new blocks and like correct earlier state yeah it's it's it's a very interesting idea and someone I used to be a very big fan of I used to do this like for my old charting solution I would have like one I don't have like one step where we kind of just like you hug things as they come in and then another step where you scheduled them and then and then the you have a house of execution and and that I think maybe is gonna be useful but I uh I'm not ready to like say like yes or no anymore I don't I don't really use it anymore now because like I'm I'm pretty happy with the forking and I don't think the orphanage is that bad because it's at the end of the day it's relatively the same amount of work the only question is like be basically like there's there's there's like this question of kind of what order does the inclusive ghost happen where like if you if you have like a you mean you could have like something something as early on the state be executed later or earlier depending on how you set up the rules but I don't know it's complicated it's definitely like a nada not a novice question this is basically like just like play it out again you're talking about like the imagine if like the state transition function of a block knew about the like and executed the for up like a kind of fork choice rule in order to deal with the reorg some earlier stuff rather than actually or fitting the earlier stuff it's kind of like it's kind of a take on inclusive ghost protocols kind of to the max maybe all right more questions yeah sure what woman unicorn oh my god it's my favorite if they're a t-shirt ever made I don't know I didn't make it mm but I like it okay well I guess with that thanks so much really appreciate it [Applause]