Introduction to Consensus (Part II) with Andrew Lewis-Pye | a16z crypto research talks

Transcript

all right good morning everyone let's go ahead and get started um so today we have again Andy Lewis pie one of our faculty fellows uh he'll be giving the second part of this two-part introduction to consensus thanks dude right yeah so uh let's start by just quickly recapping like where we are what we talked about last time uh so we we had this uh we set up a formal framework right and so let's just remind ourselves how that went this Joe's just coming in Okay so we've got a set of end processors I'm recording them from uh giving them names from zero up to n minus one at F of those maybe 40 we don't know which okay every processor knows n and they know F okay so then a

number of processes involved uh they know some upper bound on the number of faulty processes uh and they also know their own name right okay let's give them to them as part of their input uh we're considering an execution which is divided up into discrete time slots you've got time slot zero there's time plot one time two and so on at each time slot each processor receives a set of messages they carry out some finite set of instructions and then that allows them to decide what messages are going to send at that time slot okay and then you move on to the next time slot okay between each pair of processes there's some authenticated Channel okay so for each pair like inj there's some challenges between those two only those two those two uh processors only those two guys can send messages on that

channel and each processor knows exactly who's at the end of their Channel usually each of their channels right so if I'm if I'm I and that's J with it and then I've got a channel to Jay I know Jay's at the end of that channel okay let me decide uh how reliable do we want uh to think of message delivery as being uh so last time we were focusing the entire time on the synchronous setting okay so the simplest version of that is just that when if I send a message it's time T it arrives at time t plus one slight variant would be that you have some some bound Delta if I sign it send a message to time T it arrives at least by time t plus Delta okay but for our purposes here we don't have to really

worry about the difference between these two because every single theorem we're going to talk about holds for one and if and only if it holds the other with like a very slightly modified proof okay so we get focused on the the simple one you send a message of time T it reminds me time t plus one uh yeah that's a like a strong assumptions later on today we're gonna uh consider that the partially synchronous setting where message delivery might sometimes be less reliable okay but for now at the beginning when I stay on Signal setting for a bit okay then we also have to decide how our faulty processors can behave uh so basically we're focusing on uh Byzantine failures okay so they can just behave arbitrarily and think of them as being nasty

and then what's the the overall research programming we're going through okay so what we're interested in is which n and F remember f is the number of 40 processors for which LF do there exist protocol to solved by its engine agreement another variance of the problem how does that depend on our assumptions regarding uh the reliability of message delivery right whether we're in the synchronous setting or partially synchronous setting which I'll introducing a bit uh well how does it depend on the form of faulty behavior in fact we just we're focusing on Byzantine faults and then how does the the answer depend on whether we're given a public key infrastructure okay so those are the basic questions we're interested in uh

and then last time so what did we do so we introduced by his answer agreement and Byzantine broadcast if you remember what they are so representing agreement every process has got an input okay all the honest processes have to give an output the same output as each other and if they're all given the same input they will have to give that common input as their output okay that's by the end of agreement who abandon Byzantine broadcast you've got a single like one one of the process processes like a designated broadcaster everybody knows who that that guy is only the broadcast has an input okay now it's got a fairly similar all the honest processors have to terminate and give an outputs and the same output as each other and if the broadcast of his is is honest then the the common output has to be

that guy's input okay so he has to successfully tell everybody about his his value okay okay so that was answered agreement where's Anthony broadcast uh and so what we saw is that they're not the same problem there are some contexts you can solve one and not the other but if you're considering the synchronous setting and if f is less than n over two if you've got an honest majority then they're kind of they're easily reduce to each other okay so some of the Diane who can sort of think of them as being the same problem okay okay uh and then we add these sort of two main theorems so um yeah all the time working the circular settings so first of all the easiest cases you have a pki public infrastructure so in the singular

setting with the public infrastructure then you can solve Byzantine broadcasts for any number of faulty processors okay that's just the doliv strong protocol we went through and note that that tells you everything you need to know about by his anti-in agreement as well okay because we saw but as an agreement can't be solved if f is greater than n over two but if f is less than n over two then you know you you saw you can solve Byzantine broadcast okay so this tells you can solve Byzantine broadcast and therefore you can solve Byzantine agreement if f is less than n over two and then f is like greater than over 2 right you know you can't yeah will be that okay so that's the first one and then this one we also saw but it was broken down into two parts right so we had the

impossibility result and then we had the possibility result so okay now we're still in the second setting but now we don't have a public public infrastructure uh so first of all okay you can't solve it if uh f is greater than over three now either of the problems if f is greater than over three but you can if f is less than n over three yeah okay okay so we're gonna do this time then so we're gonna move first of all but so we're going to stay in the singular setting for a bit and we're going to set a state machine application which is basically what like blockchain protocols do okay and then we'll do then we'll introduce the partial singular setting and we'll basically do this whole whole thing again but I'll sort of cut it a bit shorter this time because basically what I'll do is I'll just I'll show you

tender mint and that'll sort of do most things for us okay and then okay so so far we've just been talking about permission protocols the whole time uh right at the end uh we'll talk a little bit about how this stuff Compares with uh permissionless the permission the settings okay like Bitcoin in particular okay so State machine replication so as I said roughly the state machine replication is just what blockchains protocols are supposed to do okay so you've got a bunch of clients they're sending in a sequence of transactions right they're choosing what transactions they want to send in uh and then the process is implementing the SMR protocol the state machine replication protocol they just have to agree on an order in which to implement those those transactions

okay I guess everyone's familiar with that uh it's like a word of warning so often like as opposed to Byzantine agreement uh and byzanti broker so SMR is often treated like somewhere informally in the literature so you're not quite sure exactly what formulation formalization you're using okay so sometimes I think that leads to things being a bit confusing okay so I was going to write down a sort of a particular formalization here but there are other approaches you could take okay and sometimes things will be sensitive to exactly how you set things up okay so later on we'll talk about like does Bitcoin satisfy SMR and you'll see it's a bit sensitive to exactly what you mean by ASMR okay uh as a previously okay we were interested in is there a PK is there

another pki here I'm just going to focus on the the setting where we have a public key infrastructure okay because generally I think people normally consider SMR protocols in the context of a pko okay okay so uh right so I'm going to write down a sort of formalize a formal version a little bit but first of all just at a high level so two basic differences between SMR and the one hand and ba and BB was Anthony agreement Byzantine broadcast on the hand are uh as follows so first of all SMR protocols involve like a second type of protocol participant okay we're calling them clients so roughly the idea as a clients don't actively participate right in the

process of reaching consensus all they're basically doing is they're sending in these transactions sometimes they're also called requests one they have unnamed they send in these transactions so the process is actually carrying out the consensus protocol okay and the clients have to be reliably informed by those processes when transactions have been implemented okay so they should be playing a sort of a passive role here one basic difference the second biggest difference so SMR uh unlike bambb doesn't require processors to give a single output right but rather now they have to produce like a continually growing output sequence okay that grows in lengths as the clients submit more transactions we have to gradually confirm more and more transactions okay so yeah so now I'm going to write

down one possible sort of way of uh one possible for formal setup I guess some of this is going to be like a little bit arbitrary but I just want to write something down something concrete so we have a particular detail a particular version to talk about okay Okay so we've got a set of end processors again recording them zero to n minus one uh so we can talk about things mod M and because of M clients okay 0.10 minus one uh I'm gonna assume given a pki for the set of all clients and processors okay maybe that's not entirely necessary but again just make things simple I was going to start off that way okay and again we're going to have authenticated channels they work the same as before

again all the processes have each pair of processors has an authenticated Channel between them okay so it's basically the same time as before but okay I'm going to assume for each client it just there's at least one non-faulty processor that it has a channel to okay and again you can maybe set these up slightly differently but okay that seems like a minimal requirement okay okay so that's all clear uh and then okay so we want to somehow formalize the idea that the the clients shouldn't they should only be able to play like a passive role they want them to be able to sort of participate in the process of reaching consensus into a sneaky way basically because we want to answer like for what

n and F is consensus possible and if the clients can sort of get involved in some way that might sort of screw up that analysis somewhere right okay so we want to formalize the idea that they really are passive here as opposed to like masquerading yeah maybe they can sort of like you know change the number of processes involved by you know are they honest they're not honest and so on right so you have to yeah oh no I'm not worried about whether the the note well I mean okay I think you can sort of separate their their roles here okay so in their role as clients they basically they could they could only send transactions and we've got to imagine that because they can send arbitrary transactions and the the protocol has to be able to deal with

that right and then I guess to give their role as processor as being like a separate role okay have the same question then why do we need this uh exemption there uh well again if they're about for that reason right so if I want to sort of separate out the fact that the the clients are sort of passive right so if the clients can send any any message they like they can just participate in the in the consensus protocol I want to know if what nnf you know can we solve certain problems if the clients can really like start joining in then I have to start answering questions like other clients honest they're dishonest like and so on right it's going to confuse things okay okay so I'm going to say I'm going to say they can only send transactions uh yeah for now I'm going to assume

they're all signed every every time you send a transaction it's signed okay I'm gonna suppose clients can send arbitrary signed transactions on their channels okay and the idea is that the protocol isn't able to tell the clients what what transactions they can send they can send arbitrans out you could think of that as being controlled by the adversary right okay the protocol has to be able to deal with arbitrary sets of transactions sent by the clients okay and then uh okay so a confirmation for a particular transaction TX is just it's just a transaction signed by one of the processes okay we're going to think of that as bingo is about my formalization and formalizing the notion of a message from the process that says this is confirmed

happy so far okay so what are the requirements then yeah okay but we will require more than one confirmation to be happy it's been confirmed I think it kind of has one confirmations yeah okay so uh what are the requirements so basically the requirements are there so the the processors have to keep a log of transactions right uh and so we have two requirements of consistency and liveness I think if it will everybody's familiar

with these ideas basically consistency says that the logs don't disagree with each other right and liveness says that so if a non-faulty uh processor receives a transaction then eventually that's included in the blockchain yeah foreign regardless of transaction is confirmed once the transaction enters its log okay so roughly the the consistency in life is condition so the all non-vaulty processors must agree and confirmed transactions although maybe not exactly the time same time I'm going to be slowing the other uh and any transactions received by non-faulty processor must be eventually

confirmed okay so again I think everyone's happy with basic idea is the word distinguishing between a transaction known to some non-faulty processor versus known to all online quality process well I mean okay so here I'm requiring the diamond you can just propagate them because they're they're signed by these guys over here so you can't be making up the transactions so you can just propagate them I guess yeah okay okay and then a last condition which you can sort of like uh be interesting later on maybe when I think about uh Bitcoin and other stuff so there's a there's an idea that these clients should be uh lazy in some way right so the final condition is um

to require the client should receive f plus one confirmations for a given transaction right signed by distinct processes even only if the transactions are confirmed by a non-faulty processor okay obviously we need f plus one because otherwise the the the digital on this guys could be misleading okay so what we're trying to capture here is just the idea that uh okay so not only the clients not very passive they're not participating they should be able to they don't even really have to listen to what's going on so they should be able to go away come back later on they don't even have to really pay very much attention at all okay if I've got f plus one confirmations great then I don't know my transaction's been confirmed okay so here we're trying to formalize idea

of a really like a a passive and lazy client okay so the nodes are actually speaking back to the clients yeah yeah so well they send confirmations messages back to the clients and upside so I need f plus one because the the dishonest guys could lie about when things are confirmed but if I get a plus one that I know has been confirmed I didn't really have to pay any anyone the person that I can okay so we set things up that way and obviously there are certain aspects of that we can we can play with right then uh it's an immediate concept of that is the lazy client condition is so SMR can't be solved then when f is greater level down over two because I need f plus one confirmation so the these honest guys could just sit

there and never send confirmations and never get anywhere okay okay again though so it matters exactly how you set up SMR because that doesn't need to be true if we set things up a slightly different way right okay okay okay uh so for which nnf is it possible then so well so first of all okay I'm just gonna we'll see it like a Slicker Slicker protocols later on but first of all let's just see we can sort of do it quite easily using Don't Live Strong okay so if f is less than over two it's easy to modify the dollar strong protocols to give a protocol for SMR okay so basically it's going to run repeated instances of dollar strong okay uh so we have a processor I mod n acting as broadcaster in the ith instance right

the ice version of Taylor strong it had like a fixed number of rounds right so you can just replace one instance after another one in the quite a simple way okay when process I as leader okay basically they form like a block of new transactions I think it should be confirmed right they broadcast that sequence of transactions as their value for agreement okay all right so they're acting as Leaders they suggest a new set of stuff to be confirmed when I say broadcast I've just been sending that to all processors right okay okay I know but see okay still Manisha so the process ignore suggested values for agreement that uh you know look like they're obviously wrong okay but they're

not in the right form or if they can involves transactions they've already made to log and so on okay Okay then if they don't live strong protocol decides uh false or bottom where we want to call that symbol right which is one of the possibilities if the leaders is dishonest then the non-faulty processes don't extend their log if it agrees on a particular value T that set of transactions then they append it to their log okay so there's nothing complicated so far just to wrap it up that we have to worry about the the clients getting their confirmations right and each client's only got a channel maybe to let me know uh one honest uh processor or maybe more but then at least one so just a failure of an obvious little thing with some gossip uh confirmations

okay so on a non-vaulty processor adds any transaction to its law it produces confirmation for that transaction and sends that to all processing or clients but then that might not be enough because they don't I might not have a channel directly to a specific client so they also resent all transactions and confirmations received so when I first used a confirmation for a particular transaction produced by some other processors J okay it sends that confirmation to all processors and all clients which has a communication Channel as well okay that just nothing complicated all clever happened there let's just make sure that the client's getting enough confirmations okay okay so now we know SMR can be solved quite easily using uh Don't Live Strong obviously that's not a particularly sort of slick way of doing it maybe maybe we

can have a nicer way so later on we're going to see tender mint which actually operates that works in the pastry synchronous settings so therefore it works in the singular setting uh and it's sort of Slicker in in various ways thank you everybody happy so far good okay okay so there we used uh dollar strong to solve SMR just to sort of keep it clear now what's easily reducible to what uh select next see so a solution to SMR in the synchronous setting can also be used to solve uh by his anti-broadcast and therefore byzantic agreement right because we've got all these different forms of problem so this one only I

think it's useful to keep in mind what's easily reducible to what right okay okay so if we want to solve uh Byzantine broadcast okay so that means you're given some set V right you've got to give an output in V right that's what V is here so we're going to let bottom there uh the default element of V that's what we do we just want an instance of SMR in which the number of clients is equal to number of processors okay image clients have channels to all processors you just have a nice simple complete graph there okay for each eye we have processor I also control try and I right it might seem sort of Fairly trivial what we're doing here but no formally the SMR protocol it's the

clients who have to send transactions in so that's why we're sending things up this way okay then in the first time it's like we had the broadcaster let's say that's I he sends a single transaction from client I to all the other processes right which is a signed version of his input okay in the second time slots okay so if they're honest I'll do that for they're just not honest they're dishonest they might not right they might not send a message and so on so the second time slot each non-faulty J sends a signed did not receive transaction uh from the client that they control they didn't receive a transaction from client I okay and then basically just run SMR so

we wait until the SMR protocol confirms a sign value well either confirms the signing value from the broadcaster in which case everyone agrees on that value or else we confirm f plus one that did not receive transactions right signed by different distinct processes in which case we all output the default value false yeah I believe that yeah so if they'll certainly all agree on some value because we've got liveness here on our protocol and we've also got consistency so everyone sees the same values right uh and if the if the the process if the broadcast is honest then he's going to send out these values and they'll they'll agree on his value of the clients well the role of the clients here is just kind of like a sort

of Fairly silly formal role it's just if you have an SMR protocol it's the clients who are supposed to send in transactions right so I'm just I'm just giving them that formal role I mean like there's nothing clever happening right yeah would you say that uh so to what extent is like in all the settings that we normally talk about when should regard all three is equivalents interesting like I realize there are cases where there are these differences but I mean okay if f is greater than n over two for example like then you know you can't do Byzantine agreement yeah like I said I know there are cases where you did distinctions

well so in the past the sigma setting you can't solve the way I stated it here anyway you can't solve byzanti broadcast either because they did the broadcast of mine I just might not send anything okay so I think that they are all uh they're all the same aren't they I think I mean yeah I think yeah but it's still a strong effort is the exception okay yeah in all other cases yeah that's true yeah okay

okay okay so that's uh we're done then uh with the synchronous setting so now we want to move on to the partially synchronous setting once the idea is the sigma setting is nice and tidy but maybe it's not that realistic sometimes you know you might want to be able to deal in real life sometimes the network goes down you should be able to deal with that right okay so in the past you synchronous setting the rough idea is that processors are told a bound Delta which will hold when Network conditions are good okay sometimes though Network failure might happen uh and messages might be delivered delayed for like arbitrarily long periods okay so now again the rough idea so I'm going to formalize this so protocols now have to like survive extended periods of network failure and produce outputs when

Network conditions are good okay so if you're thinking about an SMR protocol and you should know that maintain consistency when there's Network failure yeah but then you can only you can't be expected to like confirm new transactions when the messages aren't being delivered because you're not even hearing about them right so you have to maintain consistency boilers Network failure but then the liveness and the confirmation of new transactions Could Happen should happen whenever Network conditions are good okay so how to be formally Define that so normally as a standard way is to use a little sort of technical trick okay uh so we formalize this by positing the existence of some unknown Global statement Global stabilization time okay GST so it's unknown and sensitive gas so

it's not given as an input the processes they don't know what it is but it only exists okay let me specify that okay so the bound Delta holds after GST but you know who knows what happens before GST okay so any message now if it send it time T is received by time uh at least a maximum T of GST and Delta like by that time could be before yeah right so in other words if you're saying before look at the global stabilization time it could be delayed right until the global stabilization time has happened but if you sent after that then then the bound Delta holds okay so that might initially a bit

confusing because we wanted to formalize a situation where you know sometimes Network conditions are good the network conditions were bad and they were good again and they're bad again and sort of continual fashion like that right so why should it be the case there's some point after which Network's conditions are always good is that really formalizing what we want okay well uh you see in some like a intuitive rough argument that this does uh suffice to capture the more General notion okay so we can give uh an approximate sort of argument right because okay here we have a formal definition I guess the the more General version I didn't formally Define so I can't give you like a formal proof but uh okay so here's a intuitive uh idea of these two ideas that doesn't capture the more General Ocean too right

so any protocol which functions under the Apparently easier GST model right will also function under the the more General conditions when we maybe sort of just continually oscillating between good and bad Network conditions um right to see that let's make it concrete let's considered a protocol for Byzantine agreement okay what are the protocol ever violated agreement or validity under the the more General model hey then it also do so on the GST right you just have to choose GST to be opportunity sufficiently late okay so that way is round is fine on the hand if the protocol satisfies termination under the GST model okay

then for any choice of n any choice of inputs any choice of behavior for the faulty processors and any choice of GST there exists some t such all non-faulty processors terminate within that time GST plus team okay so the protocol also terminates under the more General model so long as Network conditions are good for sufficiently long right wherever you are basically if you then make networks conditions good for sufficiently long you have to eventually get some uh whatever it has to terminate him okay so this is just uh I guess it makes it a nice sort of uh easy with that's a nice little trick in terms of giving us a simple way of defining that the partially synchronous setting okay so I guess maybe that's the most

standard uh formalization of the partial singular setting in fact there's another one which is uh this one okay so in this one we suppose that the the bound Delta now always holds okay not just after GST it always holds but now we don't know what it is okay so the protocol has to has to function even though if you don't know what the bound Delta is foreign Delta setting okay so now it might be annoying because you've got these two different definitions we don't want to have more cases to deal with uh but basically guys as long as all we care about is like you know when can we make a working protocol like for which nnf will a protocol work you can see that these two uh

definitions are equivalent okay okay so first of all if a protocol works for the the unknown Delta model then it works under the the GST version right because of Any execution the protocol messages will always be delivered within some some some bounds uh Delta Prime which is just GST plus Delta right yeah so there is some bounds such as the messages will always always be delivered within that within that bound no matter how long we go we go on for yeah any other direction it's also like fairly simple maybe a little bit more tricky okay and let's suppose we have a protocol which functions under the GST model

now I'm going to turn this into the protocol that functions under beat the unknown Delta model so what do we do well we've got to break all the functions on a GST but also we have to give them some value for Delta okay that's one of the the inputs in that model so let's just give them the the input Delta is one okay then what we do is a simple trick so then we insert increasing intervals between the time slots of which processors execute their instructions okay so right so maybe processes might Implement their instructions for time T actually at time two t so we're actually getting the same instructions because we're spacing them out so there's a bigger and bigger gap between them okay and obviously then at time two t before pretending it's time T right as far as our instructions

if we do that then they don't know the actual value Delta okay but eventually the time between the you know the points at which you actually carry out the the uh the instructions for different time slots would actually eventually be longer than that Delta right so we don't know when that is but it would eventually be longer than that Delta so we'll eventually reach a point where Whenever I send a message it arrives before the next point which I actually execute my next instruction the Achievers of GST in effect after some point yeah model is allowed to completely depend on

the known Delta you can imagine there are like two different protocols for our adult books that one and two right and like they don't talk to each other uh well no you have to work for any Delta right so you're given Deltas if I'm given a protocol here I can feed it the the input Delta is one and it has to function yeah yeah you're not allowed to design it as well difficult backwards for all yes yeah that's crucial yeah okay yeah okay I guess the Jeopardy might really matter I mean you just be the same thing but you space it out I right we've dealt with five or adulterers ten normally happens like a second

um well okay so here we're giving it a particular Delta though right so we're giving it the value Dodge was one but like there's no guarantee that protocols for Delta equal to Y and protocols per decimal to two to talk to each other at all like I can't give you my GST protocol that I'm not required any protocols to talk to if you're just running a single protocol with Delta was one right and we're spacing at the point at which we execute the instructions so all that matters is what what am I maybe I'm missing the question so just every node independent of what else like you just send the first

message of time step one then two then four then eight then sixteen yeah so okay you're sort of you're just waiting longer before you execute exactly the same instructions so when it gets to that that point foreign you're pretending you're at times like tea and you're exactly executing exactly the same instructions it's just changing you're just waiting for longer so the messages will actually will arrive right or repeating every instructions no no no because when the protocol ones right in the protocol wants I'm just okay imagine I'm just running the product on a normal way I'm just like on the side imagine I'm actually spacing out the point to which we actually

execute the instructions so suppose I construct a protocol for the GSD model uh what it does is it will explore every message with the value of delta that is a lot to know right well okay so it takes the value of the Delta's input and it literally yeah and then it will extra every message so like if two machines are running that's for different Deltas like the messages don't mean anything yeah but hey they're not they're all running out for the same Delta right they're all just running it for Delta is one

yeah yeah it's the same sort of thing they're just proceeding through because running exactly the same normal protocols they've got the input Delta as one it's just like unbeknownst to them let's imagine I'm good I'm controlling them I'm actually just like squeezing out the time between which their executing instructions so that things are getting delivered fast enough right so as far as they're concerned they're just like yeah it's just one protocol they're executing with one value of delta yeah you did is there a concern that this knows make the wrong decision and terminate too soon before hitting GST running the standard protocol when they're running a normal protocol which

is spacing at the time in which it works so if it works normally then I have to work here so long as there is a GST right and here there will be a GST there'll be a GST there'll be at some point after which Whenever I send a message it's delivered before the next time which we actually execute instructions okay who is an exponential blow up yeah this is a rubbish thing to do I mean it's just okay formerly these two uh basically I want to I want to work with the GST model and I want to throw the other one away so we're going to have two things to think about so these are formally equivalent in some sense but okay this is not obviously an efficient thing to do right I mean you don't have

to you don't have to double you could gradually increase it I guess even that's not going to be easier okay so next operation okay so we want to know uh for now so what can we do in the partial segment setting we're going to concentrate on the GST model uh surprise in agreement and SMR so first of all so Byzantine broadcast isn't possible if the leader might be uh faulty right this is very easy to see I mean simple proof okay so towards the contradiction the space we've got a working protocol okay we've got these two processors okay let's imagine first of all these on faulty okay and let's suppose all messages delivered like at the next time so after

after sending okay except that we're with whole delivery of messages from the broadcaster okay with the delaying GST until some other processor terminates can we do that there's got to be a GST in the end okay but we can do that as long as some other processor will eventually terminate some other honest process it should say non-40 process of terminates that yeah okay well some processor well everybody everybody's honest here so fine some processor other than the broker master of HD terminate because this execution is indistinguishable as far as they're concerned from one in which GST is zero but the broadcast is faulty and doesn't send messages right they don't know which one are we in it's GSD passed and he's just faulty

or not okay and that basically where where we're done right so let T be the first time topics to processor iron the broadcaster terminates I need to find GST equals t plus one okay now that's he's terminated without knowing the broadcaster's input right so we have to be in trouble that way yeah vbi is output now we've got a contradiction because where he's terminated without knowing the broadcasters inputs everything you could certainly help with the wrong thing right violating the validity requirement okay so the execution such as that one which the broadcasters input isn't V all right of course there are because he hasn't even be able to say what he's in but it's you know okay so boys engine broadcast uh uh is

impossible in the settings you can weaken it so it is right so we could say instead okay rather than requiring everyone to terminate let's say if one or nice guy terminates and all on this guy's terminate and if the leader's honest then uh the honest guys must terminate and then it become possible okay but for now let's just leave that to one side we've got rid of Byzantine podcast okay um okay so now then we're interested in by that agreement in SMR okay so for which nnf can we do that uh and here again there's a really sort of simple similar proof it says you can't do it if f is more than n over three okay uh it doesn't matter right when you have a public key infrastructure

okay so we're gonna approve for by standing agreement okay you can easily modify it for as well okay so let's suppose n is three and F is one can I get rid of can you see I could uh okay it's n is three if it's one let's suppose we've got the processors zero on one here they're honest they're non-faulty and they've got input A and B respectively okay so A and B they're their inputs and they're called zero and one an expose processor 2 is 41. okay let's suppose any message sent at time T is received at the next time slot okay except we're going to work withhold messages between zero and one okay until after GST

so we're basically not going to allow these two guys to speak to each other okay okay so 240 is what they're going to do so let's suppose so in determine the message it sends to zero I suppose posters are two simulates a non-faulty processor with input a that doesn't receive any messages from one yeah so he's pretending that he's got input a he's pretending he hasn't got any messages from one so he doesn't have to worry about like you know forging messages from him from one or anything like that okay and I suppose in and determination it says to One processor two for

symmetrically simulates a non-faulty processor with input B it doesn't receive any messages from zero okay well processor zero has to eventually terminate in output a right because this execution is indistinguishable as far as they're concerned with an execution which GST is zero but one is 14 isn't sending messages right so they eventually have to terminate an output a in that case and similarly one's got eventually got to terminate an output B okay so now we've got our contradiction because they've terminated and given different outputs Okay so nice easy proof okay okay so now basically what we want to do

is so if f is less than n over three sorry f is greater than n over 3 is not possible we want to show it is possible if it's if it's less than over three um just to deal with with ba Byzantine agreement and SMR at the same time first of all I want to show you that you can solve uh by zanted agreement if you saw SMR okay okay suppose we've got a protocol for solving SMR and we can solved by the engine agreement uh fairly simply okay so we run an instance of SMR which the number of clients is equal to number of processes okay well imagine clients have channels to all processes okay and getting some symptoms before for each eye we have processor I also control client die

okay at Time Zero each non-40 processor I sends a single transaction from client I which is a signed version of its input again it sends that to all the processors okay each non-faulty processor then just carries out the SMR protocol until it's confirmed n minus f sign values from distinct processes at this point it outputs the majority value right breaking ties this arbitrary fashion okay and that basically the majority argument work because f is less than n over three right so we we'll still get their converter we'll still have the majority amongst the the a minus F values okay so the main point there is it's

quite easy to if you've got a protocol for SMR it's quite easy to see you can solve Byzantine agreement okay okay so all we've got to do then sort of wrap everything up is just uh uh solve SMR right okay so now we want to show The Following thing so in the poster single setting right we've got we've got a pki why is anti-volts okay so now we can solve SMR when f is less than n over three uh basically what I'm going to do is sort of describe like a sort of like tidied up version of tender bit it's basically it's basically 10 demand but made slightly easier to present I think okay okay uh so I had a tender bit work so I

guess what we're it's a rough idea first of all kind of General picture so process is basically they're going to take it in turn to act as leader okay put a goals to be divided into round each round has has one leader okay in each round the leader is going to propose like a new block of transactions and then the other processors are going to vote on it okay so it's a simple sequential process so one one process leader they propose a new block everyone's going to vote on it then someone else proposed a new block everyone's going to vote on that and so on that's that's a basic fallback right okay okay so if we're having uh processes

vote on blocks then it's natural it's naturally arrive at the idea of a quorum certificate okay so if n minus F processors produce signed votes for a particular block in a particular round of voting and they'll call that set of votes a quorum certificate for that block okay so hopefully it's clear we're asking for a minus F here because we can't ask for more than that because the 40 processors might not give anything to us okay okay so an object around voting if everyone's voting on a block if you get n minus votes for Block we'll call that a quorum certificate okay it's an easy observation and so if

non-faulty processors only vote on one block in each round of voting right they're only producing one vote then two different blocks can't both get two C's in the same round okay it's just a simple County argument why is that well if you've got two two C's that corresponds to two sets of n minor F votes okay so that follows easy then because so for two sets of n minus F processors two sets of n minus corresponding to two sets of n minus F votes well they've got at least n minus two F in the intersection yeah I guess you can see that in this little picture down here that bit there that's the size at least n minus two F yeah okay so any two sets of n minus F they've got at least n minus two for the

intersection we're in the case f is less than n over three right so n minus two f is greater than equal to f plus one okay so any two sets of a minus F have at least f plus one in the intersection so in particular then they've got at least one honest processor in the intersection because we've only got F many 40 processes okay but we said a non-faulty uh processor won't vote twice so that's a contradiction right they can't be voting for two different two different things so basic fact okay so non-volume processes only vote once uh in each round we can't get two different blocks getting qc's in the same round

okay okay so now that's a basic idea what I want to do is like put forward uh a really simple idea that doesn't work and then we'll tweak it a bit so it does work okay okay so first of all the housekeeping to keep things simple okay I'm gonna suppose that whenever a processor sees a block they have automatically seen all these predecessors of that block right in in the chain okay so if you want to you can achieve that just like whenever you send out a block you what is the same with it the rest of the the previous chain or we think that's ridiculous and efficient you can imagine there's some sort of like uh exchange of information protocol where if someone sends me a block and I don't know the pizza assessor I say can I have the predecessor please and I

don't listen to The Block until I've heard the people say something like that okay okay okay so here's our sort of well a very simple plan so we're going to order the qc's by round number okay that's like I said we're going to proceed like round one round two round three round four and so on I'm gonna order the qcs by round number so not necessarily according to like the the height of the block that corresponding to anything like that just by round number okay in this simple version we're doing first of all so each round is of length to Delta okay so round R is going to start at time two R Delta

around R is going to be very simple so a Time uh to our Delta when the round starts it's about r the leaders are going to produce a new block okay they're gonna do that in a sensible way so they're making a look at the the block with the highest QC that they've previously seen produced and they're going to extend that okay so they produce a new block and they can send that to all processors then that's that time T at time t plus Delta right when we hope that everyone else has heard about that if before GST they might not have done but after GST they will okay a Time t plus Delta then basically they're gonna uh vote on things okay so each processor checks whether they've received a Block B from the leader

if so and if it looks sensible okay then they're going to send a signed vote for that block to all processes okay so really simple basically the leader proposes the block everyone Waits turned out to them they vote on it okay I mean a block is confirmed in this simple version that doesn't work if it receives a QC okay okay so that's very nice and it's simple but doesn't work I guess it's quite easy to be simple if you don't work but no okay so why doesn't it work so a Block B okay so I block b might be confirmed a particular round R before GST the fact that it's confirmed doesn't

mean any of the blocks uh know that it's confirmed they're like they all produced the votes for the block but they haven't necessarily seen that Q scene yes they've produced all the relevant votes but they don't they don't know it's confirmed and then at the next round right so Block B Prime another block which is incompatible with B might be proposing confirm to the next round yeah so the problem here is blocks could be confirmed although you know because basically because when it's confirmed you don't necessarily see the QC involved okay okay so that didn't work but now what we can do is just a really simple little tweak and it'll work okay so what happens instead if we put in two stages of voting okay so now it's going to be the case that the leader proposes a block we have a first stage of voting and another

stage of voting before the next leader proposes a block okay so in more detail as follows okay let's suppose uh so the leader proposes the block we have our stage one voting same as before but now uh if each processor sees a QC on the Block produced in stage one of the rounds right in the first stage of voting okay then they produce a stage two vote okay and it's accusing stage two now that means confirmation not the the juicy in stage one doesn't count for confirmation yet it's the QC in stage two that counts okay so it's still hopefully very simple it's the same thing we just added one more round here okay so now the time yeah

okay so just to make that concrete let's write it down okay so again we're all in accuses by round number yep yep so each round is length three Delta so round R now starts at time three R Delta okay so at time T at the beginning of the round the leader just produces their new block time t plus Delta we do our stage one voting right same as before time two plus Delta now each for each process of checks would receive a stage one QC for the block okay uh and now it sends a sign stage two votes tool processors okay now a block is confirmed when it gets a stage two QC okay so I'm just repeating what I said before but if I take it down again a slightly formal way so you have more time to think about it

basically okay okay so we're all right now so does this work well but basically it basically does right we just have to find a title tweak okay so why well so the problem with the previous protocol right was that the block might be confirmed but non-faulty processors might not see the relevant QC okay so have we now improved in that situation well now if B is confirmed okay well then that means in the stage you get like n minus F stage two votes okay so that means at least n minus 2f equivalent f plus one non-faulty processors must sustain the stage one QC right because they wouldn't produce the stage two vote until unless they see the stage one QC that's when you produce a

stage two vote okay so these n minus 2f non-vaulty processes must have seen the stage one QC for the block right because we need at least n minus two F non-vaulty processors to vote in the second round to produce confirmation because you need a minus F round two votes so you need n minus two F honest votes so it's n minus two F must have seen the stage one QC otherwise they wouldn't produce that effect okay so we're in a slightly better situation right they haven't necessarily seen the blocks confirmed but they've at least seen quite a few of them have seen the stage one QC is the point okay back there so previously a block might be confirmed and no one's seen it doesn't seen the fact that it's

confirmed but now we've got something a little bit stronger okay if a lot's confirmed that at least a fair number of the the non-40 processors have seen the stage one and QC for it so now what we can do is a little trick so as we know in stock posters have seen the stage one QC to lock on the Block B what does that mean that means they don't yet consider it confirmed but they'll now not vote for blocks incompatible with B while the Lock's in place okay so they see the stage one QC they lock on that it's not yet confirmed but uh they won't now vote for incompatible blocks while that lock is in place if we do that it's immediate it's easy to see we we get the consistency right so what do you want consistency in liveness from that we're automatically

going to get consistency why so now the Block B is confirmed around r right then as we're saying but above then at least n minus 2f non-faulty process has become locked on B right there's a minus two of the F of them have to have C in the stage one QC and that means they learned they look on B it'll be now since at least n minus 2f non-40 process is required to produce anyqc in subsequent rounds and take like a stage one QC hey this makes it impossible for only blocking compatible would be to get a QC in subsequent rounds okay so once they've locked on that no subsequent block no incompatible block can get even a stage one QC and become confirmed okay so this is a simple little trick

we've we've definitely got consistency okay so we're happy okay so we see we have two stages of voting if we consider blocks confirmed when they see a stage QC uh but already have processes look on a block when they see a stage one QC they're more satisfy consistency and that's where we are so far the slight danger now and it's not too much of a problem but uh we can sort of easily solve it slightly dangerous but we might satisfy it we might uh threaten liveness okay so now what could happen was so for example to a single non-faulty processor could become locked on some some block maybe they see the stage one QC but no one else does maybe it's just them that gets locked right in the next round a single non-faulty

processor J might get locked on some incompatible block that kind of they're just locked on those things we're now we've split the honest processor so now we can't confirm new blocks because we if the if the 40 processors do nothing then you need all the uh non-faulty processes to be voting to get anything confirmed right you need a minus F signatures so they're now split then it seems like we're in trouble okay so now it's not possible to confirm new blocks if faulty processors do nothing if those gonna be it's going to be easy to fix so after basically after GST these qcs will be seen right so we just have a process of uh release their lock on some b if they see a higher QC for an incompatible block so this one here who's stuck on the first block there if they see this second QC

here right we're gonna but they say at a particular point in execution in the way they're going to release their lock when they see the higher QC okay and this sort of make things work out now if you do that the important thing is that this doesn't like spoil our previous consistency argument at all okay we're releasing a lock in that situation it doesn't spoil the previous consistency argument so let's go through again so if the Block B is confirmed around R then at least n minus two F non-40 process has become locked on B and since at least a minus two F non-40 process required to produce any QC I mean you can't no subsequent block and can get a QC if it's in compatible with B okay that's still true right there's no situation here where we Loop

mum here the context doesn't arise where we we release a lock because we see a different QC right okay so sorry so far before we just write down the protocol uh so we have two stages of voting each round if our process is lock on a block when they see a stage one QC if they release the lock when it's an incompatible block with a higher QC and they can sort of block on it uh confirmed when it gets a stage two two QC they're more satisfied consistency and I'm saying it's going to get easier to show you that we satisfy live this as well so we'll see that after you define the protocol uh okay so first of all the sort of boring polymerase uh okay so processes begin with a lock set to the Genesis

block okay ah corresponds to round zero or blocks and votes contain their round and stage number I guess you can sort of ignore most of these points if you like um okay we considered like the obvious order on QC so I said that they're ordered by their round number but okay we also had two stages of voting now right so we ordered them by the round number and then the stage number within the round okay this point it's maybe more significant okay so I'm going to assume each message has attached the block with the highest QC seen by the sending processor together that QC so it's just going to make it sort of convenient in the liveness argument so if I'm sending out a vote I sent out together with that vote I

guess I take the highest QC I've seen and I attached that I pen that to the message okay together with the corresponding block okay okay and that the highest core and blower block is kind of what you think it would be is the highest QC corresponding to any block amongst being its ancestors okay predecessors okay okay here's the protocol then so this is basically just the same protocol we wrote out before all of that again is the the business with the locks okay so it's basically what you saw before and tiny bit added so each round is like three Delta so right now starts at times three yard data round oh has processor r model as leader okay time the start of the round the the leader produces uh a new block

time t plus Delta we do our stage one voting okay so each process objective is received a block from the leader if so and even extends their lock or else at the highest QC below B is as high or higher than they've previously seen and in that case if that's true then they release their lock then they send the stage one vote okay so basically I have to extend their lock or it has to be a situation where they're happening there's even a higher QC than they're locking that they should release their lock okay then time uh t plus two Delta we do stage two voting okay so each process of checks if it's seen a stage one QC for B and if so then it sets b as it's locked and sends a stage two vote tool processes okay as before our block is

confirmed when it sees a stage 2 QC here the highest cases that don't as a high stage well I just said highest is that we order by round and then stage within them with that yeah Okay so we've already improved consistency like the same proof works yeah oh it doesn't matter no you're right I mean yeah it doesn't by the way okay um okay so we want to prove consistency uh so liveness isn't that hard either let's go through liveness proof okay so because we're around uh just consider any round with a non-faulty leader that begins at time t

which is at least like GST Delta after GST okay okay let B with the highest lock so that the worry is that they might propose a block and honest process won't won't vote for it because it doesn't extend their lock right that's that's the worry but it'd be the highest lock I know I'm the greatest greatest round number amongst all the non-faulting processes at time T minus Delta that's last time they could have set their lock okay well basically they'll they'll send a vote at that time which the leader will receive so he'll have seen all of those uh all those qcs right because we've seen this corresponding QC okay so the non-volted leader will see

the corresponding QC by by time T and they'll they'll they'll propose a block to all the the honest processors are going to be happy to vote for yep okay all non-vaulty processible then because they're happy for it they'll produce votes for the Block in stages one and two and then we've got to confirm block okay so that's a simple library's argument okay so that was like a while a version of a 10 minute light protocol uh I guess before we leave it behind I'm gonna uh we can make it even simpler okay so there we started off with this idea of like a one round thing where we

had like the leader proposed the block and everyone voted right and they said that doesn't doesn't work it's better to be put in two rounds in fact you could make the really simple one work as well if we now take off the ideas we've developed a game basically by by chaining things Okay so what we can do yeah we get a simple protocol with a single round of voting uh if we apply our new notion of confirmation together a bit locking so I won't describe this informally or completely but here's the basic idea so rather than having two stages of voting in each round we have a single stage but we have votes for that stage count in two ways okay so first of all they said they can as a stage one vote for that round right the block of that round and if that

block it stands at like a round R minus one block with the QC we also consider them as like a stage two vote for the previous round right so now playing two different roles okay so now obviously QC is corresponding to two compatible locks and two successive rounds are an R plus one then we consider the block around are confirmed okay so we basically managed to make that initial really simple political work uh well see when you see one block convert okay yeah you should see two successive blocks with qcs then you consider this one confirmed I had I

don't know it's affecting a finality but yeah it's not really impacting latency either because you had to have two rounds before right so it's like yeah okay okay so uh just to summarize where we are so that's the results so far okay it's got a presented agreement was anti-broadcast SMR synchronous with pki synchrist no pki synchronous I've written psych pki okay uh yeah so if secret setting with pki uh we know Byzantine agreement can't be solved if f is greater than over two greater than or equal to a number two but it can if it's less but as anti-bru cost Naf and SMR if f is less than n over two but again it's set up their precise definition of SMR matters a

little bit for that to happen uh if you have no pki so we can do it even only if f is uh less than n over three and the partially signature setting okay so we can't do Byzantine broadcast but we could do the other two if it's less than another three okay so to finish off then let's just compare uh those results with like what happens for permissionless protocols and specifically what happens with Bitcoin okay so in what sense does Bitcoin satisfy SMR well first of all because so far we've been talking about deterministic protocols on differences so Bitcoin is probabilistic um as I guess you're probably aware so Bitcoin only works in the synchronous setting okay it doesn't doesn't work in the partial singular setting

we still have to ask the questions does Bitcoin actually satisfy SMR and maybe that depends on how you Define SMR right so we also had this like lazy client condition right so just remind you what that was well some particularly the way we Define SMR was a client should receive f plus one confirmation for a given transaction even only if it's confirmed Okay so we obviously haven't had good we don't yet have a definition that makes sense actually the permissions setting right because that's that doesn't work under permission setting but the idea behind that definition was that be one of the the clients to be like passive and also lazy so the idea was they could sort of go away pay no attention come back and they know accurately when when uh whether when transactions are confirmed right

okay so uh does Bitcoin satisfy that condition so if you're you know you put your transactions in you go away and you come back it could be the set of miners has changed entirely you don't know who they are he doesn't the longest chain is okay if you can connect to someone who's an honest Miner then you can learn what the longest chain is ETC but how do you know who's honest right so you can try and connect into lots of different people but uh you know the pledge there could be a civil attack which they just have loads and loads of different miners with low computational power how do you know whether people are honest or not right so you can ask so does Bitcoin really give a salute like permissionless solution to SMR a defense against civil attacks and it depends on your definition of SMR

if you require that lazy client condition then it doesn't but okay maybe it's not that serious because it does allow clients to go away and come and come back and learn like correctly what's happened so long as when they they come back they connect to at least one uh on this processor right but still like strictly speaking if we're being a little bit difficult about it that's not a uh no it doesn't provide a permissionless defense against civil attacks right [Music] by connecting to f plus one I know I'm connecting someone who's honest there's

a simple way of doing it and also I'm not worrying about sell attacks so here I am writing about civil attacks I'm the god in that as being a problem you see what I'm saying I mean you can say that that's fine and I'm not I'm happy to go along with it right there's a claim made isn't it about Bitcoin the idea is this provides a permissionless solution to SMR that defends against civil attacks right so in in the previous setting okay fine we had to connect to an honest guy but we weren't worried about civil attacks that wasn't really an issue here I'm saying that's supposed to be an issue right um and then you can say by the way if

you're in the permission setting with no f a strategy the community is doing that is that plus one people whereas in permission settings I think that's a more positive way of putting it finally okay okay okay yeah okay okay so anyway maybe maybe we're happy with that anyway it might seem to seems to work uh it's fine okay so we're now let's suppose we're happy okay assume clients can connect to at least one honest node maybe that's not too much of an issue anyway so then how do we compare that with uh results in the permission settings so I guess the natural thing you might do is

you won't compare it to this so bitcoin's working without a public public infrastructure okay so you might it's working the synchronous setting not the public partially service I think so you might want to compare it with this result here right you might say well Bitcoin uh uh works whenever f is less than n over two which is definitely better than F being less than n over three that's good but if that's it's more better than that uh why well because proof of Bitcoin don't normally assume uh authenticated channels so I don't really need authenticated channels for that in some sense so process is just like broadcast messages to all in some sense because I don't assuming they spread across the network so the permissions are setting without pki and with broadcasts in a sense that if I send a message of time T everybody

has to receive it within time t plus Delta then it isn't possible to handle even a single uh faulty processor okay so in that sense Bitcoin is Raising ethical zero to F less than a half so they're making a big big Improvement okay so let's finish a little early but thanks for listening okay [Applause] slide each result says that you know permission setting without pki and we broadcast yeah there are a couple of papers and

then there's one with I forget all the authors from uh 2005 or so I think I can also show you some simple proof later one as well well basically imagine the setting okay imagine we're doing broadcast there's no private channels between each of us if I'm the adversary I'm the bad guy whenever you speak I can just be annoying I say the opposite of you and I can simulate all of you right if there's no restriction on how I can stimulate people so whenever you speak I can say the opposite and then how could anybody else listen again distinguish between like no but what's happening right do you want to comment if you go one slide back but it almost looks like there's a

mathematical contribution like [Laughter] a second how is it box right uh so you're saying how does Bitcoin overcome that you're saying yeah okay so I guess it overcomes it by so right so if you look at the the proof we did that proved that result okay there was um so we had this six node version we had the four node version it's crucial to that that that proof that the adversary is able to simulate a certain number of processes right so in the sixth node version actually that's less relevant here right the four no version the one that matters it was necessary there that the the adversary could simulate like uh half the processors in

that proof right so if you change their ability to do that if they can't if you restrict their ability to produce hashes and stuff then that proof falls apart and that's another reason why I think the four new version is interesting I think it shows you exactly the point of which it falls apart as well so the six day version was what the in order to be getting a version we talked about to simulate like two-thirds of the processors to cause a problem in the Fortnight version they only need to be able to simulate half the processes to cause a problem right so as long as you uh so if you strict them to being able to simulate less than half the processes if you take like f less than a over two then then it's fine um

right okay but you'll your general requirement is that the adversary has like less than half these of computational power right so they can't sort of simulate more than the rest of the guys there right so if you expect those two proof secondly I think the the N equals four the the four node proof is more sort of uh informative than that in one in that regard right [Applause]