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

Transcript

all right so I think we're ready to go so today we have uh Andy Lewis five from London School of Economics going to be talking about consensus um and I'll just remind that we do have two more seminars this week tomorrow we have uh thing Wren who's visiting he's going to talk about bft protocols and uh I believe Thursday we have Andy again yeah yeah good okay so yeah so this is going to be a nice easy introduction to consensus that's the idea uh so I'm going to start off by assuming like zero background knowledge what's actually zero background knowledge uh the idea is let's say today and Thursday I'm going to go through uh most of the most famous results from the literature with with foolproofs Okay um

so I guess okay if you already know for a map about consensus I guess the first part because I'm starting right at the beginning the first part might be a little bit slow uh but okay even if you do a fair amount I hope that it gets interesting at least like halfway through the first talk okay so hold on uh yeah and before we start but I guess okay a crucial distinction has to be made here is between uh permissionless and permissions protocols right so I guess everyone's probably familiar with this idea already okay but basically permission to Protocols are those where you know exactly Who's involved in the political execution right from the start okay so maybe there's some company they got you know five servers in different parts of the world and those servers are going to carry out some permission protocol to

make sure that they're updating data correctly between them that sort of thing okay so that's a permission protocol because you know exactly Who's involved as opposed to a permissionless protocol like Bitcoin where anybody can join in I mean you don't necessarily know who those people are and so on thank you so most of the classical Theory dating back to the 1980s is with respect to the permission to protocols right often that might be in respect to what I call bft protocols right where bft stands for Byzantine thought tolerant okay nowadays there's uh renewed interest in permission protocols um partly just because there's interest in implementing those those protocols as permissions protocols directly but also because there are there are basic methods you can use for implementing permission protocols as permissionless

protocols okay so there are methods you can use for taking a permission protocol and implementing it in a permissionless setting maybe as a proof of State protocol or something like that okay so in this course I'm going to be focusing uh and if at least on the permission the protocols okay because that's where most of the theory is but then on Thursday I'll also talk a little bit about um held in theory for permission protocols and permissionless protocols how those theories relate okay good okay so let's go uh right back to the start then so uh we want to study consensus protocols first of all I guess what we have to know so what is the problem a consensus protocol has to solve and there are various different ways you can answer that question uh maybe the

most famous uh consensus problem is the Byzantine agreement problem okay so let's start with that one uh and I'm going to start off by giving like an informal version of the problem I'm here I'm just going to State it basically exactly like it is in the original paper by a Lamport shostak and peace which comes back right back in the 1980s right so we'll start off with an informal version and then I'll make it four more later on okay Okay so we've got several divisions that Byzantine Army I camped outside an enemy City each division commanded by its own General okay and here it's basically the only the generals we care about and the message is part of the story okay uh and then the generals could communicate only by messenger okay so the generals are communicating

in pairs here right so any given point in time each General can choose to send a message to each other generals or one of the other generators right and they can do that as many times as they like okay so the generals can communicate only by messenger and they have to carry out a protocol to decide on a common plan of action either attack or retreat okay so initially each Journal has their own private opinion as to whether you should attack or Retreat you can still think of that as being their input in this scenario okay and uh they're very important opinions I feel like they're in but uh so the difficulty here is that some of the generals might be dishonest okay so they're going to carry out this protocol we're assuming the illness

General is going to carry out the protocol exactly you want them to but the dishonest generals we don't know what they're going to do okay and we want certain basic conditions to be satisfied so first of all we want to make sure uh that the honest generals terminate they actually come to some conclusion okay so obviously here we can't insist anything from the dishonest Channel what they're going to do okay but for the honest generals we can assess certain things so we've acquired honest generals have to reach the decision we're going to require that they all reach the same decision the old known as generals and then lastly we're going to require that if we'll be honest children will start with the same opinion if they all have the same input

then that common input should be their common output Okay so we've got a bunch of people here A bunch of generals each have a an input you have to go through some protocols they each have to decide on some common answer and they all start the same input they'll have to give that that common input as their output okay so yeah so this is like an informal version of the problem as I say I'll give you a formal version uh in a bit but even with this uh informal version there were various sort of things we can already say right so it starts with probably around to see what we can immediately see so the first basic point to make here so without the validity requirement it's pretty clear this would be trivial

right so without validity basically all the oldest generals could do they could just ignore their input and they could all just decide to attack whenever right okay so certainly validity is required to make this this interesting I mean otherwise have a trivial solution first observation okay so what I've done here I just restated the problem more succinctively and moved at the top of the slide after the red line about it okay uh and I've also introduced some some oil terminology here so I'm always going to use n for the number of parties the number of generals okay and F is going to be some upper bound on the number of dishonest generals here okay okay so what else can we say even with the informal version so uh for clarity

let's suppose to the honest generals no f okay they're giving us some bounds they know that bound and that's common knowledge okay but obviously they can't know well let's say they don't know like which of the dishonest terminals if they know which of the dishonest ones it makes it so trivial as well because you just ignore them right okay so they but they have some upper bound on a number of of uh dishonest guys here so next obvious uh observation so if f is zero then the problem is is Trivial right because in that situation we just do a majority vote right everyone would just you can just each General can send their initial opinion to everybody else it will end up in the same list of opinions right nobody's lying it's doing

majority vote if they're ties and break it in some arbitrary pre-arranged fashion something like that okay okay so f is zero then it's trivial okay so it's clear then that one of the basic questions we're going to be interested in is if what values are n and F is it possible to design a protocol here right so that's one of my basic questions okay the next easy observation is okay so it's it's also pretty obviously not going to be possible if f is uh is greater than or equal to n over two right if we have a dishonest majority here okay so let's take you through a simple

proof of that so let's suppose we've got uh two generals okay let's suppose they're given at the inputs attack retreat okay that's where they're starting okay and let's suppose that they're both they're going to both act entirely honestly okay in this situation they have to come up with some some common output right to satisfy the agreement property so they come to decide on something everything's entirely symmetrical here so far so without loss of generality let's suppose that he decided to attack in that situation okay I'd be happy everything's perfectly General so far because it's symmetrical I could I could decide The Retreat and it'll be a symmetrical argument okay Okay so we've got two honest generals one has initial position attack that's

their input the other one has initial position Retreat okay let's suppose they decide to attack in that scenario okay in that case fine so now let's consider another situation now again we've got two two generals and suppose they're both given input retreat but let's suppose that this guy is actually dishonest and what he decides to do is to pretend that his input was attacked and then after that to that like an honest General would yeah so then you already know what happens in that scenario right so now everyone's acting honestly after that point so then the output then is attack right that's yeah that's the output in this scenario as well but now we've got a conflict with validity right because the the this General here uh all of the UNS Generals

in fact had the input Retreat here right but they decided to attack okay so that's quite simple okay so if f is zero it's trivial uh trivially solvable and F is great equal to n over two so it doesn't last majority then it's sort of Fairly trembly non-solvable right and then I guess so the next thing you might think is okay so when when f is less than n over two well maybe then it's still like totally solvable so maybe it's truly unsolvable when f is great no n over two maybe it's trivially solvable when it's less than n over two okay in particular so you might think well why can't we just do some sort of majority vote type thing okay

so yeah the problem with that approach stems basically from the allowed form of communication here okay we're having uh the generals communicating pairs if you had a scenario where okay imagine everyone's just standing around in a circle and they're shouting out their votes right so that means that whenever any general shouts out maybe like their initial input whatever everybody hears that and they immediately they will hear the same thing so you can't say different things to different people well then it would be trivial right then you could just do a majority vote argument okay so in that case it would be trivial but that's not our setup here okay so here we're having communication between Pairs one pair of generals at a time

and then the problem now is that the dishonest generals can tell different things to different parties right okay so to make that concrete let's suppose n is three we've got three different parties involved here we've got f is one so it makes one of the General's gonna be dishonest let's suppose one honest General initially wants to attack while the other one wants to retreat okay if the dishonest General sends a retreat message the one who wants to retreat an attack message the one who wants to uh to attack then they'll both see different majorities right one who wants to attack we'll see an attack majority when he wants to retreat or see a Jeep majority okay so majority vote doesn't work uh and in fact okay you can show you basically there's no uh well no really trivial answers going to work here

because well in fact I mean you can show that there's no solution that works when f is great and we go to n over three unless you endow the generals with some extra capabilities okay okay so it's it's maybe not as easy as it might initially seem okay so that's uh it's like initial the party around the edges as to what the problem feels like okay uh so yeah so next thing we have to do is to establish our formal framework uh which may be a bit boring but unfortunately it's kind of it's really necessary to be careful with the details that the details here um I mean generally I think like consensus isn't very difficult in the sense that the the protocols aren't they tend to be

very complicated what makes it tricky is the like small little changes in the setup can make big differences to the answer I might set things up one way and you get a certain set of answers you change things a little bit you get a completely different set of answers so you have to memorize all these these different possibilities okay so we're going to formalize the framework and sort of outline what the different possibilities are that make a difference okay okay so we're gonna I guess unsurprisingly be formalize each General as a processor doesn't really matter how you do that just take your favorite model of computation uh imagine them to be interactive touring machines if you like okay then we're going to have the so the execution of the protocols we're going

to be divided up into discrete time slots okay it's going to start off at time time sort zero then we have time slot one so I'm slot two and so on and each time T each processor receives a certain set of messages from the other processes okay and then depending what those messages are it carries out some finite set of instructions okay and those instructions allowed to decide what messages sends out to other processes at that time slot yes [Music] there are a few possibilities and we'll start off simple and we'll sort of get what I'm getting here Okay so time slot you get a certain set of messages you go through some finite

sort of calculations right and then you decide what message to send out okay uh so there are end processes right and we're going to give their names zero up to n minus one might seem a bit odd to do zero up to n minus one more than one to n but it makes it easier to work mod n when you're doing talking about stuff okay uh so each processor here is told n and they're also told their own name okay so that's that's part of their input and then we have authenticated channels okay so there's like a two-way Channel between each pair of processors here okay so for each pair of processes inj we've got a channel i j okay the way that works is quite simple so only I can send messages to Jay and

only Jacobs and messages that I on the channel i j okay and when I receive messages it's aware of the channel by which the message was sent okay so if it gets a message on a particular Channel if it gets a message on the channel IJ it knows that message from was from Jay okay so each processor sitting there it's got a bunch of authenticated channels and it knows who's at the end of each channel right so a message arise on that channel it knows who the message is from yeah as I said so each time it's got the instructions for processor I determine which messages should turn along each of its channels okay then sometimes we want to assume uh public key infrastructure sometimes not

okay so if you're given a PKR public infrastructure that just means each process is given a like a secret key public key pair okay and it's told the public key of each of the other processes okay so as it looks along each of its channels it knows at the end of this channel there's process J in this of their public key okay so now we have to get to uh how reliable do we want message delivery to be because it makes quite a big difference okay so um okay so to keep things simple we're going to start off in this of the easiest setting right so I start off in what we call the synchronous setting so that means if I sends j a message at times.t then J receives that message at the next time

slot times that t plus one okay so that's the synchronous setting another version of the synchronous setting might be that you have some some finite bound Delta okay so if I if I send a message times up T then J receives it by time t plus Delta right at the latest basically for up bubbles here the distinction isn't that important it isn't very interesting because any theorem we talk about here will hold for one in the if and any of it holds the other up with the basically the same proof or an easy modification okay so just to keep things simple I'm just going to have this really sort of the simplest possible version of the synchronous setting to have in mind it could be slightly different all the same results will hold at least as far as you know the stuff we're talking about now

[Music] multiple messages at the same time yeah it doesn't really matter because you can send some sort of data if you want to call it multiple messages yes I mean okay certainly you can send multiple messages to different processes as well yeah yeah [Music] okay yeah so I can send a message to each of the other participants any given time or slot and they'll all arrive and the next time foreign okay then we also have to decide how uh dishonest generals can behave so uh we'll talk about the following way so

some of the processes are faulty okay well maybe 40. so as I said before so each process has given an upper bound f for the number of faulty processors as part of its input bill was going to suppose that's known and generally we're going to be motivated in in analyzing settings where the faulty processors can just display arbitrary Behavior okay and particularly they might be malicious right so they might be trying to muck things up okay so in that case you say the process is displayed Byzantine vaults okay so they can they can just follow some arbitrary program everything I'm talking about so far by the way I haven't been in the size we're going to imagine everything's deterministic so far okay uh you also you know you might want to

consider other sorts of faults okay from different settings different sorts of faults might be interesting so you might also consider crash faults so if you consider crash folks that means basically protesters have to follow the protocol precisely up until maybe some point where they crash and then after that point they just stop doing anything okay but mainly we're going to be interested in Byzantine faults because that tends to be one that people are interested in in the blockchains anyway uh and then a little just a little bit of info in informal terminology so often we'll talk about anniversary okay uh so if don't be convenient to think of all the faulty processes that are displaying arbitrary behaviors being so coordinated by some adversaries trying to sort of coordinate their actions so

it's to be as difficult as possible okay so sometimes it's necessary to formally just Define the notion anniversary but for all the stuff I'm going to talk about in these tutorials if not okay so it's just an informal time okay okay so that's basically the sort of uh the formal uh setup if you like uh so what's our our research program then okay so the questions we want to answer are basically so for which n and F do there exist protocols to solve the Byzantine agreement problem okay another forms of the problem Oh to find some other ones as well uh how does that depend on the various possibilities we we talked about there

so how does it depend on things like message reliability right like whether we're working in the synchronous setting or whether we're working in like settings that make weaker assumptions on message reliability okay so uh maybe I should have said before so in the sequence setting we're starting off in this thing from the setting it's a pretty strong assumption so after a little bit we'll relax that and we'll talk about other settings like the partially singular setting where message delivery might be sometimes much less reliable okay and that'll change but we'll change the set of results we get and that's a set of protocols we have to use uh how does that all depend on the form of faulty Behavior right whether we talk about Byzantine faults or crash faults again Byzantine folks just means you can

behave anyway whatsoever okay and how does it all depend on whether or not you have a public key infrastructure okay that also makes a big difference okay so that's the basic those are the questions we're looking to to answer uh and the order which we're going to do that is following so yes we're going to start off in the synchronous settings the simplest setting first of all and that basically it's going to concentrate on Byzantine thoughts I think uh right I'm going to determine for which nnf buys anti-in agreement it's possible depending on whether a pki is given okay and that makes a difference okay uh then we consider the same question for crash faults at this time and then we'll do the table the whole thing again uh for weaker assumptions about message delivery okay

okay and also we won't just talk about the Byzantine agreement problem and to focusing on that to make things simple at the beginning but we'll also talk about some other other forms of the problem okay so by his ends in broadcast and state machine replication two of them important important variants so basically State machine replication is just what like what Bitcoin solves okay in some sense okay so um right so I stated by zanted agreement before in a slightly informal way but also the version I stated before was uh like a binary version of the problem so the number two options attack or Retreat right so sometimes it's useful to have a more general form uh so let's write that down okay so we consider set of ending

processes almost F Maybe 40. and then for some set V okay uh each process was given an input in V okay obviously different processes might get different initial inputs you can imagine V is tall to all the processors and could be of any finite size greater than equal to two doesn't really matter this photo here all I care about is that V is decidable okay so so process can determine whether any given values in V okay okay then we just have the conditions we said before okay so we need termination or non-faulty processors must give an output in v okay agreement they will have to get the same output again validity the same enforce of all non-faulty processes have

the same input then that's going to be there they're common output okay so that's the Byzantine agreement problem hopefully you have that sort of memorized now because we're going to be using that for the rest of that talks good no exactly right so you have to you have to give an outbitt and B yeah yeah one note that sort of force the outcome to be what they want it to be even if like like assume it's about like everybody else started with uh so you'll talk about some album that's a broadcast version of problem it

sounds a bit like the broadcast version the broadcast from that is just like yeah the notion of like you get everybody to agree on an output that's in view that's valid but if you like if you don't want one note to just like be dictate the whole by deviating from the protocol yeah well so if you if you saw this and you know if you've got a protocol that works for large F you won't have one one node be able to dictate it you mean one honest node not being able to dictate it or any faulty no not now does it take yeah okay so you uh yeah I mean you mean okay you're gonna have to satisfy validity but uh so you're saying in scenarios where they don't have the

same input you still don't want having that much influence yeah okay they're interesting okay I'm not sure about that yet maybe okay okay so that's uh uh our first version that's Byzantine agreement uh then here's another variant which you're gonna have to memorize okay so it's a simple variant though um so in fact in the original paper where Lambert shostak and piece introduced the Byzantine agreement problem they really focus most of the time on this this variant called the Byzantine broadcast problem okay it's now called the Byzantine broadcast so the setup now is similar so we've got n processors F40 so now One processor is designated the broadcaster okay so they're given a special role everybody knows who the broadcaster is okay that's

part of your input now only the broadcast has given an input okay so the broadcaster has given an input in some set V and again V's total will approve the processes okay now we have to satisfy the following conditions so again so termination so all non-faulty processors have to give an output in v 7 to the four agreement they will have to give the same output but now the validity condition is different okay so now if the broadcaster is non-faulty has input V then all non-40 processors have to give that value as their output okay so it's kind of similar but now we've got a one particular processor with this is uh

with a distinguished from the others and the idea is that he's trying to tell everybody his value everybody should agree on that value right if these if he's non-faulty everybody will agree on that value even if he's faulty they're still going to agree on some value but obviously not necessarily his value yeah you're happy with that okay so we're two different versions the problem in byzantic agreement everyone's given an input they had to determine some common output and if they're all given the same inputs the common input has to be that output in the broadcast version of the problem uh as soon as we've got a particular node who's the broadcaster everybody has to have has to Output the same output and if the broadcaster is honest then you have to Output his value okay okay

so now you've got two different versions the problem I guess the lead the natural question is well so how do they relate are they essentially the same hopefully the same so forget about it go back to one version of the problem right uh okay so to what extent are these the same uh so we saw before that so Byzantine agreement can't be solved when f is greater than or equal to n over two whenever this majority right that was a simple argument with two different generals yeah it's easy to see though and I won't go through it but it's easy to see the same argument doesn't apply to Byzantine broadcasts and in fact we'll see if a big guy is given and if we work in a synchronous setting then there are protocols for solving Byzantine broadcast uh that can deal with any number of faulty processes

okay so they're not exactly the same problem there are some scenarios at least where you can solve BB Byzantine broadcaster not bystation agreement okay on the other hand okay if we're working in the synchronous setting this won't necessarily between other things we work in a synchronous setting and if f is less than n over two so this is the sort of the realm in which you've been solve by zenity agreement maybe yeah then the two problems reduced to each other quite easily okay so let's see that so on the other hand if you thought by example broadcast and then to solve by this anti-agreement we have all processes broadcast their inputs using the protocol for Byzantine broadcast right so you just go through like any different versions of that

protocol yes each one takes remember to broadcast that to others okay the month of values decided correspond to each processor process then decide by majority vote right breaking ties in some some arbitrary fashion so essentially what you're doing here you're just executing that majority vote protocol we talked about before but you're getting rid of the the problem that dishonest guys can say different things in different processes right they go for Via byzanti broadcast protocol these will get over that problem yeah okay so that's One Direction and the direction is also quite simple so if we can solve those anti-agreement then to solve Byzantine broadcast at the broadcast to send their input to all of the processes at Time Zero hey if we're in the synchronous setting

then that should arrive by time slot one yeah so each process then takes the value received at time one as their input value or they didn't get anything because the the broadcaster is not honest and they just make something up yep okay then we just have the process carry out a protocol for Byzantine agreement on those those input values is that clear okay so this is a fairly easy reduction in both directions so the result is okay so they're not the same problem but if we work in the synchronous setting and if f is less than n over two then they are basically they're reducible to each other uh and I guess the

consequences this is an overall so far it seems like we only really have to worry about Byzantine broadcast because if Byzantine broadcast is impossible there was Anthony agreements definitely impossible and if it's presented in uh broadcast is impossible as possible impossible the other one is about right okay so if you if you work out for which if you can do byzanti broadcast that gives you the result of his entering agreement so long as you're in the synchronous setting okay okay so now let's get on to the results okay so we'll start off with I guess the sort of the easiest one so it's easiest if you've got a pki okay so where when you think of the setting you send messages to arrive at the next time slot

we can imagine we have a public infrastructure the result here is that there exists a protocol that solves the Byzantine broadcast problem for any number of faulty processors okay so this result is originally due to Lambert shostak and peace but I'm going to talk you through a much sort of well a more elegant protocol by Donovan strong okay and as I guess said so we're uh we're talking about Byzantine broadcast here but this also deals with Byzantine agreement right so by the reductions we just discussed also supposed to show that we can solve those anti-agreement in a singular setting with pki even if even only if f is less than ever two okay because it was Anthony agreement just generally isn't possible of f is

great we've got that number two but if f is less than that over two then you can use Byzantium broadcast to solve those anti-agreement okay okay so we only have to worry about presenting broadcast that's what we're going to do uh and again maybe before we've talked for a proof maybe it's worse or thinking about why it isn't trivial so we talked about why Byzantine agreement wasn't trivial before but there's a majority of vote sort of thing but now we're talking about presenting broadcast and now also they've got a pki so maybe it's worse from thinking about it again a little bit okay so what might be an obvious sort of way to proceed so an obvious way to try solving Byzantine broadcast if you've got a public infrastructure right remember you've got one guy he's the he's the broadcaster I

mean trying to get everybody to agree on his value if he's honest right it's an obvious thing to do would be to have the broadcaster send out signed versions of their values of the versions of their inputs to all the other processes at the beginning right okay and obviously if they're if they're honest they'll celebrate the same signed value yeah the dishonest they might be sending different people different things yeah so we'll start off like that okay then the processors could just repeatedly share all the sign values they've seen produced by the broadcaster if they only ever see a single value produced then the output that value they were happy then they've all

terminated they've all they've all agreed okay and if the broadcast is honest they only were seeing the single value he's sending out so they're outputting the correct value I said we're happy other hand if they sue two different values being produced okay then they realize the broadcaster is faulty because an honest broadcaster a non-faulty broadcaster wouldn't send out two different sign values of versions of their their initial value right so in that case well they know uh that the broadcast is faulty so all they've got to do is agree on somebody doesn't have to be their value so in that case they just get some default value as their output okay that's that would be the idea right this doesn't work right yeah okay so the idea is if the broadcast is

non-faulty then they'll only produce a single sign value and all non-vaulty processes will out but that that sounds good okay under the hand of the broadcaster produces two different sign values and shows them to non-faulty processors okay then the idea is everybody eventually see those two values they'll get the default output okay in that case we're fine as well okay so that's the idea hopefully it's all too fairly clear what the problem with that is the problem is okay so when do we stop sharing values right so we share values up until time T then what the the the the Versa we can do is you can just show everybody like one particular value up until time T then at time t when it's too late to share anymore then

he suddenly shows some subset of the honest process has two different values okay so then some of them would go to the default value some of them might give another value and you've broken the agreement property yeah see that okay so the problem is when do we stop sharing values right basically wherever you put the cut off the burst we can start playing games with showing different processes of different things at that exact cutoff okay and again you might sort of think well there must be something something I could do here uh something will work out but in fact you can kind of show that nothing really simple will work because if you have faulty processors you can show you need at least f plus one rounds of communication so there's no really simple answer here okay okay so let's see the uh the nice

solution when delivers strong okay so what we need is a clever mechanism here to ensure that if any non-faulty processor let's say recognizes a certain value produced by the broadcaster okay then they all recognize that value yeah right so if you have the case okay whenever any non-faulty process is recognized at a certain value then they all do okay then what that means is that either way either way either they can they all recognize a single value produced by the broadcaster and they'll like output that single value or they'll recognize multiple values so they will give the default value okay so if we can ensure that this is true then we're happy is that clear

yeah and that's what we want okay so here's the mechanism it's quite elegant so at Time Zero the broadcaster sends a signed version of their input to each processor again if they're if they're honest they'll send the same same value to everybody if they're dishonest there might be multiple values there at time one a process has looked to see whether they've received a sign value from the broadcaster and if so this would recognize that value okay they recognize this is something a value that the the broadcaster has produced okay so now although I've been just passing on that sign that is why the processes what they do is they attach their own signature to message so now it's been

signed twice okay first by the broadcaster then by them and then they send that new version of the message to all processes okay okay then more generally we stipulate the browser is to recognize a new value at any time t then the message has got to be signed by T distinct processors okay and if they recognize a new value at time T then they add their signature to the list uh and they send that new message out without now with t plus one signatures okay so time slot zero the the broadcaster sends out signed versions of their input a Time plot one other processors like received that it's got

one signature Time Clock Was time plot one so they have to recognize that value they then add a second signature send that out time slot one if other processes received that time slot two it's now got two distinct signatures so they're happy to recognize it they might then add a third signature and so on at times not three people will be happy to recognize it if they see three distinct signatures on it okay and the signatures have to be distinct okay for different different processes okay so that one there is a generalization of that so I'm just gonna encapsulate everything the shorter description there okay so I've got some more space on the slide pretty happy with that process okay okay then finally just at the end what

we do so it's going to be a finite process we have f plus one money stages so termination will be automatic if I'm just going to terminate after f plus one round so the time a plus one we give the process is a last chance to recognize you've new values but they can't share again okay and then what they do is they either output the single value they've recognize if there is if it's only a single value or they recognize more than one value they'll go to the default option okay so there's a protocol clear first of all yeah okay okay so now let's see what that works so again so we have to show that any non-faulty processor recognizes a certain value okay then they all do

okay as long as that's the case we're entirely happy that's what we have to show you so there are two different cases to consider here okay so first of all is the the easy case let's suppose some non-vaulty processor I first recognizes some value before it's too late to share okay in that case it's quite simply basically they just have to add their signatures or share the value right so I suppose some non-faulty processes I first recognizes V at some time T strictly before f plus one but it's not too late to share okay so what does that means in that case I received a message from laying the value of V at time T which has t distinct signatures attached otherwise I wouldn't recognize that value at that time right it's going to have two distinct signatures for I to recognize the value

okay so processor I then adds their signature to form a message to T plus one distinct signatures and it's an app to all processes okay so that means all non-faulty processors will recognize V by the next time slot foreign case you've recognized the value but it's not too late to share that variable of people so next we come to what might be the tricky case right it's when you learn about it right at the end before it's when it's too late to tell other people about it see what's happens there so suppose next at some non-faulty process I first recognizes V at time f plus one right when it's too late to share so in that case I received a message relaying the value of V at times f plus one which has f plus one distinct signatures attached right otherwise they wouldn't recognize the

value of that time slot okay but if it's got f plus one distinct signatures attacks that means at least one of those signatures must be from a non-faulty processor right because we've only got F many 40 processors at least right so at least one of those signatures is from a non-faulty processor who's previously relayed the message okay and that means so let's suppose it's signed by that non-faulty processor is J that means that case one applies with respect to J it's a j it's already seen the value of some previous time slot and I shared it and now everybody knows about it anyway yep yeah so it's quite I guess it's quite slick that last little turn there yeah okay so that's the Dole of strong

protocol uh I think on the slides I wrote down a sort of formal version but maybe it's not that useful to go through the formal version let me start a little bit late so I think I'll carry on okay okay so in that protocol we used f plus one around the communication and in fact an original paper where don't live the strong produce that protocol uh they show The X plus one rounds are necessary okay so uh yeah so it's clear you can't do something that's really trivial anyway okay so that was our first theorems with pki you can basically do uh deal with any number of faulty processors so next uh very famous theorem is the following

one so consider the singular setting without bki so here no political could solved by zanza agreement all the landing broadcast when at is greater than or equal to n over three okay so again this is originally due to land but you have to compete but the the proof I'm going to talk you through here is a much nicer proof by uh Fisher Lynch and Merit and I also present it in a way that's a little bit I'm different than usual as well so maybe if you have seen the proof before maybe this will still be interesting okay so again uh so we're solving it for Byzantine agreement okay but that that gives the result also for Byzantium broadcast because they're reducible to each other my name is less than I never two

foreign Merit version of the proof okay so in order to give a nice proof where you understand exactly why all elements of the proof are there uh I'm gonna first of all I'm going to sort of change our our formal framework a little bit okay and then we'll change it back and give uh no we'll give a full proof for the full framework but the proof will be nice if this will go via modified version first okay okay so according to our formal three but the way we set things up so each processor has uh so we've got a private Communication channel to each other processors and you know right at the start like which processor is at the end of each of those channels right so if I'm processori I've got a Communication

channel to J then right at the start of the protocol execution I know that Jay is at the end of that channel yeah just briefly though to make things a little bit Sim but let's consider an alternative setup in which processes no longer begin with knowledge as to which processor is at the end of each of their channels okay so we still have one channel for each of the processors but now I don't at the beginning I don't know who is at the end of each okay so there's a fire processor execution uh if I'm one of the guys involved and I got four different channels right and only one person can write something Beyond each of them I used to know who's in the videos channels at the beginning okay okay so in this situation we can describe uh like a simple proof by

contradiction uh the approach might seem a little bit odd at first is what we do is we we suppose a working protocol exists okay let me do certain things about how the protocol must behave in scenarios like other than the intended application right which might seem an odd sort of thing to do okay but it works out because that allows us to quickly reduce that actually there are sort of valid uh uh situations in which the protocol Can't Behave uh properly okay so that sounds a little abstract okay I'll make that concrete uh right now okay so let's let's start off with the case n is three and F is one Okay so we've got let's bring three processes or a protocol for three processors where most one is faulty

okay let's suppose we've got a working protocol okay let's do something a little crazy let's imagine let's consider what happens when four processors all execute the code protocol for n is three and F is one I suppose they all execute the protocol correctly okay but they do it when we set up the communication channels and some odd fashion like that okay and I'll explain what this picture means so each each node here each node here is a different processor okay they've got this is this is a process of zero this is the processor one but this is a process one down here it's the process one zero prime a process of One Prime okay and we're going to suppose that uh if you're zero or zero point they're both

told that the name is zero whether you're one or one prime you're told that your name is one okay so we're thinking that we we know they're different processes but they don't okay as far as they're concerned they've got the same names as each other and the A and B is there that that's just their inputs okay so processor zero has input a processor One Prime has input B and process for one has them for a and so on okay so is that clear okay so this it might seem like it's a strange sort of setup but it's clearly it makes sense to consider it right you might not be immediately clear why you're considering it but it makes sense to sort of set things up like this each process has got a certain input at each stage they're going to receive messages along each of their communication

channels the protocol told them what messages to send you just like okay you can ask the question so what happens then in this odd set up right so the assumption is that they're like they're communicating in a ring it's not a complete graph yeah yeah yes I guess communicating in a ring exactly right so each of these guys you can sort of think that they're kind of unaware of what the main context is right they're sitting there I've got two communication channels I'm just following the protocol you send me some messages like I go through my instructions that determines what I send out and we can see what happens right okay okay so yeah so this is these are zero one zero Prime and one prime but as far as they're concerned right so if you're a processor I or I prime they're told

their name is I okay and again the am A's and B's are just their inputs okay so again so each process is just going to act entirely honestly here okay I'm not going to deviate the protocol at all uh okay and we're gonna wonder what happens as I say this is not a configuration which the protocols are intended to operate but we're going to analyze what happens here and it's going to allow us to do some contradictions to the idea that it's a valid protocol okay okay so what we can what can we say about how things will unfold here well the first thing you can say is that process is zero and one here okay they both have to Output a why because it's like this four

processor execution is indistinguishable as far as they're concerned from the three processor execution right in which so they're given the inputs a and there's a second processor the process of two over here is 40 and just simulates the process of zero Prime and one prime here okay so each stage versus one point sends to zero what prototype the simulating processor processor two settings to zero what process of One Prime sends in this four process of execution right and the the faulty processor the one who's simulating these two guys here he sends to processor one what protocol processor zero Prime sense in this four process of execution okay and when I say that there's like two uh

executions are indistinguishable I mean that with respect to a from the perspective of a particular processor that means they have the same input and they see exactly the same messages that each stage right so this four processor execution is indistinguishable as far as these two guys are concerned from a three processor execution in which the third processor is is falsey and simulates these two here happy with that okay so in that situation all the non-faulty processors have input a so they have to terminate an output a okay okay but then similarly and just by symmetry okay so these two guys here One

Prime and zero Prime they have to terminate an output B right because this four processor execution is indistinguishable as far as they're concerned from the three process of execution right in which the the third node is faulty and dissimilates these two processes here yeah okay so these two guys have to Output B so for me to tell me so these two guys have to up but hey these two guys have to out for B could we navigate to a contradiction okay because we've all determined that zero output's a uh one poem out for outputs B but now this full processor execution is indistinguishable as far as they're concerned from a three node execution in which these two guys are honest and this

guy is 40 and simulates these two nodes here yeah but now we've got a problem because they've given different outputs okay so we violated the agreement requirement well exactly my question when I saw the hexagon is why did you need a hexagon so that's why I'm giving you the four node version First and now you see why it is that's the right question okay so we've got our contradiction but this was all in our modified setup well I suppose we begin the the the whole thing without knowing who's at the end of each Channel okay if we now go back to the full setup try and do the same argument as a bit of a problem

okay problem now is we have to be more careful about deciding how to treat each Channel during the indistinguishability arguments okay so it's not really that deep but uh okay let's go through it so let's consider first process of zero and one so zero and one treat the channel between them as the channels are a one okay and if each processor irons everyone treats the channel between I and one minus I prime as a channel I two so if zero treats this is a channel zero two and one treats us to channel one two okay then it is indistinguishable from this this pre-process of execution in which the uh the 40 process assimilates these two so then in that situation you can conclude they both output a okay and then similarly okay uh if you reverse I and I prime there okay so if

they're both regarding this as a channel one zero and uh this guy regards this in channel one two Hebrew guys this is the channel zero two then again you can conclude that they must both out but B but then you get into a problem in the final step of the argument right because now the execution doesn't look into indistinguishable from any valid execution as far as zero and one prime are concerned because we just said to zero it has to treat this as the channel zero two and this and one prior master cheat this is the channel one two which they never would okay so it's just a sort of like a about the silly problem really with the fact that you you you're given the wrong names or you have to assume the wrong names for people at the end of your channels okay but then we

can we can solve that quite easily by doing the hexagon okay so if you've seen the proof before that's why the hexagon is there I don't think it's very clear then when you read the visual proof Okay so we've solved that just by sticking two guys in the middle that we call two and two prime okay okay so we introduce two and two prime uh we suppose each processor with the name I or I prime is told the name is I okay so two poems told the name is two two is also tall their name is two okay and they treat the channels just in the obvious way so these two this is the channel zero two these two this is channel one two and so on yeah okay so now you don't really have to think through the TD's details you they want now

basically the same argument works okay so now you can include these two have to Output uh a because this is indistinguishable this six processor execution is now indistinguishable as far as they're concerned from the three process of execution which one guy simulates these four similarly these two here have to Output B because the six process of execution is indistinguishable as far as they are concerned from the three person executions from a three-person execution which their faulty process assimilates all these four nodes over here and again now you reach your contradiction because now you have two non-faulty processors giving different outputs when that there's six processor execution is indistinguishable from a a uh a three processor execution in which they shouldn't be giving different different outputs okay

so I guess yeah don't worry too much about the details here it's essentially the same as the four node thing but now now it works out with the names okay good okay uh as well okay so that was just for the case n is three and F is one but okay basically that gives you the general case as well okay so if you suppose there's some n greater than 3 and F greater n over three for which the protocol works well then you could you could make that you could use that to get a working protocol for any three and F is one basically you just divide all the processes up into equal groups equal of equal size so they're all of size at most F and you have each of the three processors control like one of those one of those sets of processes okay

yeah okay so the proof we went through was for case n is three and F is one but that immediately gives you the general case basically right because if you had a political work for any other F and any other any other n and then they have a f but it was n over three you could very easily use that uh to get a protocol that worked for n is three and f equals one which we've just shown is impossible okay so where are we so so far so we're all still in the synchronous setting as we saw if you have a pki you can deal with any number of faults you have this sort of dollar strong type protocol uh we've seen um because they're the same thing without

pko so we know no protocol can solve ba or BB when f is greater n over three so the next thing we want to do is show that okay when f is is uh less than n over 3 you can okay so that's what ties things up so far right okay so we're considering the synchronous setting without pki we want a protocol that works uh when f is less than n over three okay okay so again it's suffice to prove the theorem for byzantic agreement that'll give us the same the result of azantine broadcast so the theorem was originally approved by Lamport shostek and peace um but I don't think that an initial proof is that sort of informative so

what I'm going to do instead is give a more instructive proof by Berman gray and Perry or adjustment of that which is known as the phase King protocol the game so yeah I think I guess this uh protocol is probably the most complicated one I'm going to talk through today or Thursday so I don't have the previous boost for easy or hard but anyways you have to maybe concentrate a little bit to follow this one but I don't think it should be too hard okay okay so I'm gonna describe a protocol called the phase King protocol right it's going to show us how to uh how to solve horizontal agreement when f is less than n over three first of all though I'm gonna uh to

explain the main protocol I'm gonna show you first of all like a simple two-step sub protocol okay it's called great cast okay so with great cast just as for Byzantine agreement each processor receives an input okay and now they have to give an output just as they did before but now they also have to Output a grade together with that value a grade either zero one or two okay and the grade is going to indicate something about the knowledge the processor has regarding other processes outputs okay okay so it's a very simple protocol so

what we're going to do basically I'm going to throw it at you and then we'll start talking about what it achieves okay okay so step one so this is the instructions for processori so processor I has their input V okay their first instruction step one is just send feedable processes okay simple enough step two okay so if n minus f distinct processes sent B to I right let's just say 2i here in Step One then I will send b to all processors okay so first step you send your value out next step you're waiting to see if there's some value that lots of people sent me in fact if it's n minus F then I'll send out that value in the next

step yeah hope it's clear why we consider n minus F here if you're expecting any more than that then well the 40 processors can just not do anything you won't say anything okay okay so first of all do you have any visible processes and then step two if n minus F distinct processor send b in step one and then you send b to all processes okay so so far I guess it might not be immediately clear exactly why that step two is there but we'll see why okay so that's that's the end of the basically the protocol but now we have to decide how to Output okay so the output is Fuller so if n minus F distinct parties send b to I that is in round so that should say step two there's a typo so in step two

venue output B with grade two okay so if a minus F to think part is sent B in round two in step two then output B with grade two otherwise if that's not the case of f plus one just thinking part is sent B in step two and output B grade one okay and otherwise output V be grade zero so I realize it might be Millions initially a bit mysterious what these grades meaning and stuff but we're going to talk through what it means okay it will be quite simple okay so that's the whole protocols hopefully you agree that it's quite a simple protocol that's what this is the sub protocol right okay okay but then we don't yet understand what that does or what is to find the way it is but

that's less to think about it okay so there's the protocol um just put up the top of the screen okay so let's examine its properties okay so first of all it's easy to see it satisfies a certain form of validity right so if all non-faulty processors have the same input value V then it's going to clear that they're going to all going to Output V with grade two right that's easy to see right because what will happen is well they all start off with value V so they all send V to with other processors right that means that in step two all every every processor gets at least n minus F distinct process is sending it that value yeah so they can send the value again yeah that's step two yeah

so then when they come to out but again each of them will receive that same value from at least n minus F to think processes yeah yeah so you just follow it through right so they all start for the particular value they'll all send that out that means they'll receive it from at least n minus F distinct processes The Next Step so I'll send it out again okay happy with that and then ultimately then they'll all output the grade two okay so if you agree that's a simple observation here okay next observation is the outputting view of grade two also implies knowledge about the outputs of other processes okay right so that's true because the following condition is uh is satisfied

okay we'll prove that in a bit but I'm going to tell you first of all satisfied so we have this this knowledge of agreement property so if any non-faulty processor outputs a value B with grade two then in fact all non-faulty processors have to Output B maybe with some other grade right but if any unfortunate processor outputs a value B grade two then all non-faulty processors have to Output B at the grade 201 okay so what that means is so the non-vaulty processor output B is grade two then it knows that all non-faulty processes are out the b okay and this is a useful sort of knowledge right so we're trying to get to agree with each other we're not quite sure where other people are in the process and so on but here we know so if

a non-40 app that's B grade two after this really simple two-step protocol then we know that all non-faulty processors have that same output yeah let me know that if they all start with the same input then they will output with with grade two as well right okay okay so so far we've got a simple process protocol means everybody starts the same input they're all going to Output end with that same value and they'll all know that they have the same value at the end yeah okay so next week what we want to do then is we want to prove this knowledge of agreement property so I've just written it up there okay so then okay so we're going to approve knowledge agreement it's a very simple proof we'll just do it in two

very small steps okay so first of all we're going to prove a weak agreement property okay so here it is so if I is done faulty and sends B in step two then no non-vaulty processor sends a different value than b okay so B's number 14 so if I is not faulty and sends a value B in step two there then nobody who's non-vaulty sends a different value as already we've got quite a strong form of agreement there right so it's not necessarily the case that they're all completely agreeing because some people might be sending a value and some people not but if any non-faulting processor sends to Value B even at that step two then nobody can send a different value why is that well it's just a sort of

County argument right it's just because f is left and then over three here the faulty guys can't come across too much trouble okay so let's see it so it can't be the case that 140 processor was sent to B by n minus F processes in step one and therefore sends to be in step two while another Ascent B Prime not equal to B by n minus F processors right why because any two sets of n minus processors and N minus F processors have to have at least n minus 2f in intersection I don't know if you can see that have I got two sets of n minus F processors the size of the intersection is at least n minus 2f right okay maybe listen to give us a picture picture that in your head okay so any two sets of M minus F processors have to

have at least n minus two F in the intersection the N minus 2f is great equal to f plus one because we're considering the case f is less than n over three okay so that means any two sets of n minus F processors have to have f plus one process in the in the intersection and that means at least one non-faulty processor in the intersection because we've only got F 40 processors okay so any two sets of n minus F processors have to have a non-faulty processor in the in the in the interception but non-vaulty processors can't send two different values in step one like they're going to send a single value okay okay so that means if any non-vaulty processor sends B out here because they've got n minus F they've

got set B but n minus F distinct processors in the first step there are no other non-faulty processor can send a different B out right so they kind of seen that that beep I'm not able to be sent to them by Emma as they have to think processes okay so that's weak agreement and then once you've got weak agreement you can easily prove knowledge of agreement so it's proven knowledge agreement so if a non-faulty processor outputs B with grade two okay then it sent B by at least n minus F processes in step two that's what the instructions say okay without this be with grade two let's send b but at least n minus F process is step two I might not have the instructions here okay but if he sent it by at least n minus F processors that means all non-faulty processes are sent B by at

least n minus two F processors right because there's only the F40 ones that can be doing making things different okay so we'll send it by at least n minus 2f so greater than f plus one process in step two so that means that anyway they're then anyway outputting B okay just to make sure things are well defined here you can't be outputting multiple B with grade one note that from the weak agreement property no uh non-faulty processes can be sent B Prime not equal to B by f plus one distinct process in step two okay so that's just saying you could only output one one value with one grade here okay okay so the point of that is if you've got this simple protocol and it sanitized this nice knowledge agreement property which says that any

non-40 processor outputs a value B grade two then all non-faulty processors output B okay so okay so where's that got us so far okay so so far yeah they said the protocol if all non-40 posters to start with the same input then it produces a nice situation which they all know that that was the case it'll end up with that same value but now they all know that's the case right that's the point of the knowledge agreement property yeah so what we haven't achieved yet there's any method for tie breaking okay so everybody just starts off with mixed inputs we've got no particular way yet of getting to agree on some some some common output okay so how can we do that well we just use a really simple method Okay so

what we're going to do okay so we're gonna we're gonna run f plus one many rounds Each of which has got a different leader okay so process to start each round with a with a certain value initially that's just their input value but they're going to constantly update their value as these rounds go on okay each round I'll just start with an instance of gray cast the simple two two-step protocol we just saw it'll just carry out great cost so what they'll do is they'll just in each round go f plus one round in each round they'll just carry out great cards they'll update their value to the output of great cast uh okay and then after grade cast leader shares their value basically inviting everyone to agree with their value

okay so the leader just shares their value the idea being that you know they're inviting people to to update their value to the leaders value so everyone now agrees to each done 40 processor now changes their value to that value suggested by the leader unless they're like really sure they shouldn't right unless the output of the grade cast sentence for that round with grade two okay so just f plus one rounds each one's very simple you just do great Cast update your value leader shares this value maybe you update to but I do update to that or you do update to that unless you're really sure you shouldn't because you output a great cast with value too okay so let's see then uh okay so if we proceed in that way okay so first of all it's easy to see that validity is going

to be satisfied right imagine everyone starts off with the same value what will happen is when you run Great Cars they'll end up they all end up with the same that same value and the grade two right that's what we decided before which means they just ignore the leader all the time right they don't you only update your value to the leader's value if you didn't output great cast with with grade two okay so it all starts with the same value you run great costs you end up the same value grade two you ignore the leader take that value into the next round you do great cast extreme value ignore the leader take that value in the next round and so on right so no one ever changes their value okay so it's clear that validity is going to be satisfied okay so what do we need here we need

termination which is automatic because it's a finite protocol that we're going to terminate we need validity which I just said is really easy because they all start with the same value then they're going to change it okay but we also need agreement right that's the last thing we need so let's see why agreement is satisfied there's also to see that after any round with a non-faulty leader okay and then all subsequent rounds all non-faulty processors are going to have the same value as soon as the lead is not vaulted they won't end up the same value why well if a non-faulty poster doesn't change their value to the to the the value suggested by the leader why is that that's because they outputted the grade class incident with grade two right but then the knowledge of agreement property says that the leader there must anyway have the same value

right if you outputed with grade two or non-faulty processes also outputed but that with that with that with that same value maybe at the same grade right so if there's any non-faulty processor doesn't update to the the leader's value when it suggested whether they didn't need to update anyway because it's the same the same value yeah okay so um I want you to remind you the knowledge of even properties of any non-faulty process out that way I can't see the edge there uh outputs of value with grade two in the gray size instance then all non-faulty processes output B right so that that's justifying a bit there okay so let's just write uh excuse to go versus the protocol down then okay so

this is the instructions for processor I so first of all they're setting an initial value which is just their input okay then we're going to do like f plus one round so from T equals zero to F the f plus around one round in each round again the first two time slots you just run an instance of grade cast in the next time slots you just update your value to the output of the grade cast okay and then if you're the leader so if you're in the sort of the teeth round of your your name is t then you send your value to all processors okay and the next time slot everybody gets updates their value to leaders value unless they they output a great starts with with grade t with grade two okay but at the end you just now put your

value okay and as I said so validity and proof of agreement we're both seeing these based right so validity follows from the validity property of great casts and the fact that each round and the grade will be two million leaders values ignored so you can just see an inductive process everybody starts with the same value of one grade cast that output that same value they ignore the leader feed that value in the next round and so on okay it's validity satisfied improve of agreement that's true because you just consider the first round with a non-faulty leader and the knowledge of agreement property or non-faulty processes would either switch to leaders value or already had that value with grade two okay okay so we're basically at the end of today's talk then so summary of where we

are so far so Byzantine agreement and Byzantine broadcast uh so they're not the same problem but if you're in the synchronous setting then they're equivalent to each other as long as f is less than n over two uh the first theorem we saw so if you consider the synchronous setting with pki then there exists this nice protocol they'll Live Strong um the souls Byzantine broadcast for any number of faulty processors uh let me consider the singular setting without pki uh so this is like two of the theorems before combined right so there exists protocols solving by his answer agreement and presenting broadcast even only if f is less than n over three okay so what we're going to do next time is consider State machine replication that's basically right and then the

protocol that blockchains protocol normally solve I like them protocols like Bitcoin solve uh I don't think we'll actually look at crash vaults uh but then we'll all do the same we'll do we'll do some similar questions for the partially synchronous setting actually basically I'm going to simplify things a bit basically what I'm going to do I'm going to show you how tender mint works and that will sort of solve everything for us okay so tender bin I think it's actually a simpler protocol than that face clean protocol yeah okay so I guess we'll do that all next time so let's [Applause]