Frosty: Bringing strong liveness guarantees to the Snow family of consensus protocols

Transcript

okay welcome everyone today's a16z crypto uh seminar very happy to introduce Andrew Lewis P who's a mathematician computer scientist at London School of Economics um lately Andy's been working a lot on consensus protocols including given the first formal analyses for some protocols that are deployed in practice and today he'll be talking specifically about the Avalanche protocol so Andy thanks Tim so yeah so I'm going to talk about uh this recent project with aval laabs and I thought I'd start off by describing the overall aims of the research yeah and then once we describe the overall aims and I'll take a step back and fill in the the background a bit more detail yeah so I guess uh everyone's presumably familiar with Avalanche it's one of the major blockchains uh has an an interesting consensus protocol in the original Avalanche white paper they

actually describe a dag based protocol okay so again I presume everyone's probably familiar with dag protocols so dag stands for Direct a cyclic graph and the idea with dag protocols is each block no longer has to have a unique parent you can each block can have multiple parents so that gives you a directed acyclic graph of blocks rather than linear chain of blocks okay so the original white paper described a dag based protocol nowadays uh the protocol actually used a protocol called snowman which has a sort of similar flavor to it it's very similar sort of protocol but it's no longer dag based it's now monolithic right you now have a linear chain of blocks yeah the protocol has uh it's a very interesting protocol has lots of nice properties in particular has low uh communication cost um in in the good case in the case you're not um

under substantial bantian attack the protocol revolves around a probabilistic sampling process and so one sort of slight difficulty with it is that it's kind of quite hard to analyze okay so the first aim of the research is to produce a rigorous proof of consistency for snowman so by consistency I just mean that honest players don't finalize incompatible blocks another difficulty with uh with snowman as for theual D based protocol is that it is subject to to liveness attacks so particular if the adversary has more than order rout 10 nodes and it's subject to livess attacks and so the second aim of the research is just to augment snowman with a liveness module that allows you to deal with liveness attacks of that sort should I be thinking about a permissioned protocol for the moment yeah I going to

talk about it's permissions yeah obviously is actually proof of state but I'll talk about everything as if they're permissions yeah so this is all joint work uh with the team at aval laabs Aaron buckwold Ste Steven but Patrick AGR and Kevin sniki there's been lots of interest in developing consensus protocols that that scale well scale efficiently actually somewhat distributed somewhat surprising in distributed computing we don't really have very good techniques for analyzing like what is the throughputs that a protocol could handle so we tend to concentrate on some sort of metrics that give us you know some some idea about the kind of throughput that might be it might be able to handle and so one of the most important metrics is the communication complexity okay so that's basically that's just a number of bits sent by Honest processors per consensus decision so in that regard we have this this

lower bound of do live and reuk that says the deterministic protocols need n Square communication complexity per consensus decision okay so that's that's annoying because that means we so necessarily have this quadratic blowup in communication cost as the size of network grows so how can we get around that well there various different approaches we might take so one approach is to use probabilistic sortition like as employed by algorand yeah so basic idea there is simple right so rather than having all processors carry out every cessor decision instead be just sample a smaller committee and have them do the work for a while yeah and then maybe change committees so often practically speaking though uh so avoiding Banting control of committees uh already requires each committee to have a number of members sufficiently the the quadratic communication cost for

the committee is already quite large so particular if you look at the the alaran white paper okay they work out there that you need committees in the order thousands of members already so K squ there is already pretty large it's in that context that the Avalanche white white paper came along and described uh a different and interesting approach uh to limiting communication costs so the paper actually describes uh so family protocols some of them are onot protocols for B agreements some of them for state state machine replication they all sort of based on the same basic uh basic idea so to explain I guess maybe the simplest way is just to describe one member of the family okay so I'm going to describe snowflake so this is a a a one shot protocol okay for

Banting agreement okay so here's how snowflake works we have three parameters okay you got K Alpha and beta to make things concrete for now you can imagine let's say k is 20 let's say Alpha is 12 and let's say beta doesn't really matter say it's 15 or something like that 20 15 or 20 or so okay so each processor begins with initial color either red or blue okay and then uh each processor proceeds in rounds to each round p just randomly samples K other processors from the entire population okay uniformly random again asks them to report their present color Okay then if at least Alpha remember to make it concrete pi that maybe K is 20 and Alpha is about 12 or

so yeah so at least Alpha of the reported values are the opposite of P's present color then P adopts that opposite color okay and then if P sees beta consecutive rounds in which at least Alpha of the reported values are red then P decides red and symmetrically so for blue okay so maybe I'll give you a little a few seconds to think about that because the entire talks going to be based on well not this protocol we start off with this protocol we'll build on it okay so I'll give you maybe some time to think about how this protocol will function Maybe just Begin by imagining your K is 20 Alpha is 12 let's say basa is 15 or 20 and then just keep things simple start off by imagining that everyone's just acting honestly I have another observation here beta has the goal of making this uh decision safe

in a way right so that you're not deciding prematurely and then uh flipping for the wrong thing however Suppose there are some nodes out and so making beta larger should actually make you ear less often right yes that's fine yeah but then if some notes are not yet convinced of the color that will gain majority the longer you sample the more likely you're going to hit on one of those that you're still not convinced right you say well yeah there might be liveness issues I guess I guess throughout this talk I'm going to be not worrying so much about liveness we're going to be focusing on the consistency aspect and then because we have the live is module which will yeah I I'm just hinting at the other other

work that we have done on this this hits on this issue right because there is an improvement one can do there yeah okay so I guess that counts as your time to to Think Through how how it'll work uh yeah so is it hopefully it's fairly clear how how things would operate here so if everything if it starts off uh all one color then obviously they're just going to terminate an output pretty much immediately if things start off mixed then you might take a little bit of time in order for things to of tip over in One Direction but once you reach a certain Tipping Point let's say reach a point where nodes are mostly red then everyone's going to flip to Red yeah and then everyone will decide on red that's the basic sort of picture yeah okay so just a sort of informal analysis at this

point it's going to be entirely handwavy so we're going to have informal analysis now and then we'll give a formal analysis for the uh for a variant of snow later on okay so the basic idea is once the proportion of the population who red reaches a certain Tipping Point the rest are going to quickly flip and the idea is anyway for appropriate beta if you choose beta large enough basically then the chance any correct processor decides on red before that sipping point is reached you can make sure that that probability is small okay so then if that's true then once every any correct processor decize on red and they can be sure that all other correct processors will quickly decide the same way okay so the point is then the chance that correct processes decide differently can be made small through an appropriate choice of protocol of uh

parameter values yeah and as I said before so if everybody starts off the same color then everything will uh converge quickly okay on the other hand even if you start off in a situation where it's basically 50/50 that me you're requiring variance in in random sampling okay in order to push things in One Direction or another okay so that's the the basic sort of idea behind all of these protocols yes that was a a one-hot protocol for banan agreement uh we're really interested in snowman right which is a protocol for State machine replication okay but stman basically uses the same idea in order to execute State machine replication right so in state machine replication we're interested in fizzing a sequence of transactions yeah y can you elaborate on how the snowman turns uh reduces the St machine

I'm going to do that in uh not complete detail but a fair amount detail later on so I'm describe snowflake plus and that's always magic at this point of this of of the development of the protocols it's still magic because you cannot go bit by bit about the next command and stuff like this I think it's fairly simple but okay we'll describe it yeah okay okay so that's the basic approach just probabilistic sampling uh and obviously so a nice benefit of the approach is that it avoids the need for all toall communication if you think about uh what's happening each round here each process at each node just samples like a some fixed number of others the number like the K here the number of your sampling doesn't have to depend on the the population size okay so if you if you are managing to decide

in some small number of rounds then you have a small amount of uh you have a small communication cost so it's the probabilistic guarantees that let you SK escape the quadratic lower bound or yeah so yeah so snowman is the protocol presently used by blockchains and Avalanche but there are these two issues that I mention before so first of all providing rigorous proofs of consistency that turns about to difficult and also be we have this issue that is subject to livess attacks this hasn't actually been a problem in the world we haven't seen Liv attacks uh but it's nice to have formal guarantees right yeah so what we do in the paper okay basically we just address those two issues okay so we describe a variant of snowflake called snowflake plus which I'll describe you in a little bit we don't actually have

to work with different protocols than than snowflake we could just work with snowflake the point of working with snowflake plus is basically that okay first it gives better numbers and also acts as a stepping stone to another protocol called ever driven snowflake which I'll talk about as well okay so we describe this variant just a slight variant and then we give a simple proof that this the snowflake plus behaves nicely then we give a complete specification of like a version of snowman that that builds on snowflake plus and that's that's the the first foral description of the Snowman protocol and from now on whenever I say snowman I mean snowman plus okay because I yeah I will forget okay and then we give uh simple proof that resulting snowman protocol satisfies consistency right except the small error propability basically the the the proof of consistency for snowman plus just comes

from the the proof of uh uh well the proof that we'll provide for for snowflake plus it satisfies agreement okay yeah and then we also describe a Vari of snowflake plus called eriven snowflake right that can be used to give very low latency in in the common case and we'll describe that also later on so with regard to the first issue so formalizing um giving a formal proof of consistency the second issue like uh be able to deal with liveness attacks okay so yes so we describe how to org uh snowman with a livest module it can be triggered in the event of a substantial attack on liveness uh there's some cost involved in doing that because it has greater communication cost um but anyway I'll give the details there later yeah is the one uh tip or no uh no okay so basically we're working with f less than

N5 just because that gives nice numbers you could push F higher if worse numbers I don't haven't s studied how quickly they degrade but uh okay I'm choosing F less new five because it okay it's not a a sharp cut off I guess to piggyback on that question I mean do you know that it doesn't work for f like 49% times uh yeah I should be able to answer I'm I'm not quite sure no yeah okay I'm not sure how L you can push F yeah okay it won't work for 49 C well it's synchronous so it should work up to one half right but just how quickly it that's why I asked the question you would like it to 49% times out I don't want to respond though I haven't thought it through publicly but okay yeah okay so uh I describe this this variant of snowflake called

snowflake plus just basically it's very similar has an extra parameter we'll give a simple proof it behaves nicely uh and then that will move us on nicely to talk about aor driven snowflake which has low latency in aort of common case and then I'll describe uh yeah roughly not in complete detail but hopefully enough uh detail for CH uh how snowman plus uses snowflake plus to to uh to solve SMR and then to finish off with we'll just describe uh roughly anyway how the how the life this module could be imped so let's start that process so snowflake plus so this is going to be just very similar to the snowflake protocol I described earlier on but with a uh this is one extra parameter okay so this is a simple protocol for binary by an an agreement we're working the synchronous setting here standard sort

of setup so we've got end processors going to call them p 0 up to PN minus one for the sake of Simplicity I'm going to stick to a static adversary just controls a fixed set of participants okay and we're going to suppose they control at most F of them uh f is unnown bound and generally we're going to suppose f is less than over five okay so each process of Pi begins with an input value either zero or one here you think either either either 0 one or or blue or red yeah and then let's remind ourselves of the requirements for U Banting agreement okay so first of all the agreement property requires that no two correct processors output different values validity requires if every correct processor I has the same input then no correct processor outputs a different value than that that common output that common input sorry okay then

termination requires every correct processor gives an output so today though we got we're basically we're just going to be worrying about uh formally proving agreement and validity we're not going to formally worry about termination basically what we're really interested in is formally establishing consistency for uh for snowman later on okay and the consistency proof for snowman will basically depend on a satisfying agreement here we don't even really require validity but that's easy so we'll stick that in for free okay so yeah so we're going to be worrying mainly about agreement and but we'll also talk about validity because it's easy we are going to make a simplifying assumption here though okay so we we're going to describe a protocol in which instructions divid into r rounds uh and then what we're going to assume is that we're assume that correct processes proceed in lock step through the rounds

okay so we're going to assume that all correct processes carry out round one and then all correct process carry round two and then all correct process carry round three and so on okay so it's going to make that assumption because it makes things easy to analyze I'm going to promise we can actually remove that assumption okay that makes things fider okay actually we've written we're writing two P the first paper is completed and that that works with the simplifying assumption the second P paper I basically written down the proof and that this assumption okay but anyway for the for today we're just going to work with this simplifying assumption everyone proceeds in lock step through the rounds okay so that's not that's not how things work actually in the appal protocol so the way that people actually proceed is you know each node will sample a bunch of other other guys as

soon as you get those responses back as long as you as soon as you get enough responses back then you get on to the next round okay so everyone proceeds at their own pace depending on their own local message delays so snowflake plus is going to be similar to snowflake except we're now going to use two parameters Alpha 1 and Alpha 2 rather than the single parameter Alpha so we now have K rather just Alpha we have alpha 1 and Alpha 2 and then we have beta okay so alpha 1 as before it's going to be well alpha 1 as for Alpha before is going to be greater than K over 2 and Alpha 2 we're going to assume is is larger than alpha 1 each process of Pi also maintains a variable Val which you can think of being it its present value its present color if you

like okay so that's initially set to being its input okay so as before so the the parameter K just specifies the the sample size this is how many you're sampling in each round the parameter alpha 1 now is used to determine when when a processor will change color okay when they when they change the present value and now the parameters Alpha 2 and beta are used to determine the conditions uh when when people terminate okay I guess this this will all become clear when we see the protocol so here we that the protocol instructions then okay so again the instructions divide into rounds round s curs at time 2 s Delta so in rounds how do PI proceed so first of all Pi just samples K other processes uniformly random okay so we sampling with replacement here and then requests each of those processes to report their

present value their present color if you like and you wait time Delta for me to arrive and you report your present value to any processor requested it in this round okay so so far it's basically the same then you wait another time Delta for message to arrive and you consider the values youve received in this round so first of all now so if at least Alpha One of the reported values are one minus your your present value oneus the opposite your present color then you change your color yeah you set your value to be one Val equals 1 minus Val okay so this is the same as before previously we just used Alpha now we're using alpha one here okay and then that's the first condition second if if p is seen beta consecutive rounds in which at least Alpha 2 of the reported values are equal to it its present color

then you output that value your present color and terminate so what you're changing relative to snowflake is the termination condition yeah well we're using two different parameters now so we're using Alpha 1 to when you change color because that's not well it's not really a change yet I guess but we've got different name for it's Alpha 1 Al alpha alpha and then yeah the termination condition depends on Alpha 2 which we can set to be some larger value so previously alpha 1 equals Alpha 2 right previously alpha 1 equals Al and is the motivation here more because you want alpha 1 to be smaller than it used to be or more because you want Alpha 2 to be bigger than it used to be both okay it kind of makes if Alpha 1 is smaller that makes it easier to reach Tipping Point and then Alpha 2 being

large gives you some more evidence that you you've gone past the Tipping Point so they combine nicely so let's analyze it okay so as I said we're we're not going to worry about termination but we're going to be interested in agreement and um and validity to make things simple I'm going to work with uh some concrete fixed uh parameter values okay so we could work with General parameters uh but then we'd have formulas all over the place and it would be fiddly okay so I'm going to make it nice and easy we're going to work with specific numbers and we'll just have numbers to deal with rather than equations and stuff y okay so we'll work with k equal 80 alpha 1 is 41 yeah so you just begin the half Alpha 2 is 72 so like 90% And beta is 12 okay and we're

also going to make the Assumption f is less than N5 n is greater or equal to 500 okay I'm going to going to make the those assumptions those I say that I hinted at earlier that's basically just so we can give as simple an analysis as possible okay you you can work with a larger F or at least slightly larger F you certainly can work with with smaller n but then you have to give a slightly clever proof there have to be more steps in the proof okay so I'm just working for the the simplest proof possible what is n for Avalanche it's around about well State weighted so it becomes complicated but okay is at least that is that sort of order if you yeah yeah if you look at just the large nodes okay so yeah I'm going to talk in terms of colors rather

than zeros and one so I'm going to say Pi is blue in round s if it value is zero at the beginning of round s okay and say it's red in round s if it value is one at the beginning of round s okay so the argument is going to consist of uh four very simple steps so step one okay so let's start off by considering what happens when we've reached a point uh in the prodical execution where most of the uh correct or honest processes are read okay so in particular let's consider what happens when at least 75% of the correct process are read in a given round okay let me just start doing Simple calculations for the binomial distribution okay so a direct calculation with binomial distribution so the probability given correct process is read than round s plus one is greater than 0.9 555 you to a direct calculation

so this entry here that's just the the number of Trials second one is the probability of success to each trial and if the greater equal to 41 says we're asking for the probability of uh at least 41 successes okay so you just do a direct calculation for the binomial your probability of being R in the next round is really quite High okay greater than 0.955 five that's for particular node but then we can just look at the population as a whole and do another simple calculation for the binomial okay so another direct calc calculation for binomial shows that it fail the probability it fails to be the case that more than 5 six of the correct processes are read in round s plus1 is upper bounded by 1.59 by 10 to- 20 okay that's just another calculation binomial the reason we're using uh n is 400 here is

because we're worried about the the correct processes okay so we we're imagining we know at least 80% of the correct process 80% of the process are correct okay we know n is great equal to 500 so here we're worried about n is more than 400 and you might wonder why 56 comes up here actually 56 isn't really relevant to the present argument I could work with three quarters here instead uh but it'll the five six will turn out to be useful towards the end of the talk okay so sticking that in there okay so this probability is very small this is for a particular round though right okay the the argument above though requires no knowledge as to the state of each process in each in in the given round s other than the fact that at least 75% of the correct proc is a red

so then we can iterate the argument of over rounds right and uh then it becomes well so long as we bound the number of rounds we can we can suppose that if at least 75% of the correct process are read in any round s then actually that would be true in all later rounds okay so to be to be clear here right this very small probability was for a specific round so if assuming this this dagger one condition here is going to be reasonable we're going to have to bound the number of rounds okay we're going to use the union bound okay so but we can do that so let's just let's suppose we have we're going to run the protocol for at most a thousand years okay we run five rounds per second that gives us something like at most 10 to 11 rounds okay which when we multiply by

1.59 by 10 to- 20 is still small okay so we'll come back and talk about the accounting later on okay so now the basic idea is we can be it's reasonable to assume that this condition dagger one holds right so roughly what that's saying is once mostly red always red once you reach the the point where 75% of the correct noes are R is is reasonable to assume that will always be the case Okay so that's the first step in the argument and let's move into the Second Step this is even simpler okay so let's again think about the situation where at least 75% of the correct process is red in a given round yeah then we can do another direct calculation for the binomial and we can see that the probability a given correct process of Pi sbl at least 72 blue in

round s that's upper binded by 1.18 by 10us 20 okay that's EX unlikely that's even with you know that's all the time this is irrespective of bisanti action right that's even of the the bisanti adversaries helping the whole time by giving blue responses okay so that's extremely unlikely again this is just for a given round and a given processor right but if we bound the number of rounds and number of processors then it becomes reasonable to condition on this event dagger two okay so if at least 75% of the correct processes are read in any round s that no correct processor samples at least 72 blue in round s and in particular that means they can't output

blue yeah in order to Output blue you need to see at least the the Alpha 2 many blue in that round okay so if you got a round in which 75% of the correct process are red or at least 75% are red then nobody can outut blue in that round they except with very small probability okay so so far we've got once mostly red always mostly red now we have in a mostly red round nobody outputs blue okay so let's that's step two let's move on to step three okay so for step three the aim is to show that if a correct processor outputs red then we've almost certainly passed the point where correct loads are mostly red okay so let's see that so now let's suppose that at most 75% of uh correct process are red okay so previously we were assuming the

opposite at least 75% of red now let's suppose at most 75% of correct proces are red in a given round okay then we just do a correct calc calculation for binomial again okay then the probability given correct process of P sample 72 or more or more red in r s is upper bounded by 0.0131 okay irrespective of banti action even if the abers is helping them get there by saying R so that's true in uh in one given round okay but that's also true in later rounds so if some X greater equal to one it then holds the most 75% of correct process are R in round S Plus X as well then independent of previous events the probability P sample 72 or more red in round s+x is again upper bounded by

0.013 Mo so in that first calculation I mean don't you have to take into account that you might sample Byzantine nodes that tell you read just no the the adversary is helping you here right so the the adversary is yeah so that's why you've got the plus to 0.2 that's even if the adversary is helping you they they then it's uh still up banded by they say the adversary staying quiet oh that's the plus Point okay got it got it got it okay okay so now if we consider 12 given consecutive rounds and any given correct process of P the probability that at most 75% of correct process are red and every single one of those rounds and p s was at least 72 red in all those all those 12 rounds that's upper banded by 10 to minus 22 okay so again that's a very small

probability okay so now that make Again by counting number of processes bounding number of processes bounding number of rounds that makes it reasonable to condition on the following event so the correct processor outputs readed in some round s+ 11 let's say and for at least one of the previous 12 rounds at least 75% of correct processes of red in that round okay so the takeaway there is if a correct processor outputs red and some previous round is most mostly red for now step four we're basically finished we just have to put all these things we've learned together okay so what have we learned we've learned once mostly red always mostly red that was that was dagger one we've learned in a mostly red round nobody outputs blue and with dagger two and then dagger

three so the correct processor output is red then so previous round is mostly red okay so hopefully it's clear at this point how we can argue but let's see that in a bit more detail okay so according to is there like is there some irritating dependence right because you also once you go back you also know that a correct processor output read at s+ 11 you have to be careful in what you're conditioning as you go through the argument yeah but like it almost seems like you need a slightly more General version of that first statement yeah okay I promise you it's fine if you go through yeah you can't condition what's happening in future rounds when you're talking about what's happening in particular rounds you have to be careful about what how you're conditioning okay um so yeah where are so according to dagger three if a

correct processor is the potentially do first to Output let's say an output's red after sampling some some round s s+ 11 let's say then we know that at least one of the pr one of the previous 12 rounds must satisfy the condition that at least 75% of correct veres are red in that round then given dagger one we know all subsequent rounds will uh will satisfy the condition at least 75% of correct processes are read in those rounds and from dagger two that that then means actually that no correct processor can ever output blue okay because this guy was the first to Output okay so that's advices then to show that agreement is satisfied basically it's only really agreement that we we care about here um yeah so we have to be careful also doing the counting okay I

sort of like wage my hands a little bit basically you can go through the argument and count the accumulation of small ER probabilities carefully basically you suppose that at most 10,000 processors run the protocol for most A Thousand Years executing 5 a second then you can just apply the union bounds du the probability of any one of dagger one to dagger three failings at most 3 by 10 to minus five okay so that's still quite small okay so that was agreement uh for validity uh an even simpler argument works now that we've we've done some of the work okay so um suppose all nodes have the same input red say okay by the same reason above since round zero now satisfies the condition that at least 75% of correct nodes are R in fact 100% of correct nodes are read we can then condition on uh the event dagger four

which says that in every round more than five six of the correct nodes correct processes red okay and then you just it just follows again from from dagger two from dagger two and Dagger four it follows no correct processor output is blue as required okay so we we get agreement and validity and we don't worry about termination because uh yeah because ultimately we just worried about consistency for for Snowman and then we're going to add the livess module anyway to give us livess in in a different way okay basically we're trying to trying to avoid doing all the hard stuff is is our main aim here okay before we move on to to snowman though let's just extend that protocol a little bit so that was snowflake plus now we're going to extend that to another protocol which is called error driven snowflake or every different snow fake plus move

between the two names so the basic idea here is as follows so far we consider a fixed value Alpha 2 right for k80 so we just said let's fix Alpha 2 at 72 actually though it may be interesting to consider multiple values of Alpha 2 at the same time giv me are lots of different conditions for termination okay and the basic idea here is uh this might be interesting and useful in in various different ways so first of all considering lower values of Alpha 2 allows us to deal with a greater percentage of offline or like crash Vols yeah you think if Alpha 2 is 72 and if 10% of the nodes crash then that might be a of threat to liveness yeah we don't necessarily want that okay so considering lower values of Alpha 2 as well might mean that we we can deal with

a larger number of Crash faults but also considering higher values of Alpha 2 will give quick condition quick decision conditions and low lasers in the good case and maybe we see you know previously in that analysis before we needed 12 rounds when we saw 72 or more red before we terminated but maybe we see 76 a war red then we can terminate on a less round that's more evidence that we've passed the Tipping Okay so ER driven snowflake plus and it's just the same as snowflake plus except that one simultaneously considers multiple possible values of Alpha 2 okay so each Alpha 2 now goes rise to a different beta that decid to gives the condition under which you can terminate okay so the the corresponding beta in this table here so in this table you can basically ignore the second and third columns okay they're just for people who are um happy

to accept larger error probabilities okay let's imagine we're we want to remain as strict as we were before okay so we want to keep the error probabilities roughly what they were in the previous analysis then you can focus on uh this column here okay what this is saying is okay so for example if we see three rounds in which uh eight we get 80 responses all red then that's already suffice to terminate at the same time alternative we can consider all these different uh Alpha at the same time if we see six rounds in which we see uh 76 or more red that's also suffices to terminate yeah so can you elaborate on how you got this numbers so is yeah you just go through the previous argument right and you work out what's the beta in each case so evalu in just numerically complicated expression yeah

there's nothing nothing clever about it just like yeah yeah yeah simple okay so if you use multiple conditions for termination uh then that will increase the error probability because there are more things that can go wrong now but not by that much okay it's still going to be low probability of a overal and it's worth pointing out here that if you look at actual blockchain data it supports the idea actually you know the vast percentage of nodes are acting honestly the vast percentage of the time so actually these these uh entries near the top of the table here can you see my mouse yeah that you're going to see those quite a lot of the time right so actually moving over to this protocol does allow you to massive significantly reduce the the latency okay so so far that's all been one-hot protocols so now let's uh start

talking about SMR this was only agreement and validity right yeah we I said we we're not worried about uh termination because we're we're only worried about formally establishing consistency for snowman later and then we're we're going to rely on the livess module to say yeah well I mean you are going to talk about liveness later right I am going to talk about livess but okay not not liveness for snowman I'm about liveness for Frosty once you add in the module I'm gonna as I say I'm gonna cheat and avoid all the stuff that's hard to talk about so that's the basic plan okay okay so with SMR State machine replication we're looking at to finalized sequences of transactions now so um we have to able to talk about transactions and stuff so we going to consider a standard set up okay we imagine process set envir transactions

by an environment we could have them send by clients or whatever you want to do yeah okay just just to go back to that uh point one more time uh so you made this change from Snowflake to snowflake plus yeah um was that because this made the analysis simpler or made it possible it's multile things it gives you better numbers it also performs much better in if you do liveness if you in simulations and you test it actually much better at liveness as well and it open it was like a stepping stone to the aid driven snowflake which I said that gives you low latency in the good case so allows you to reduce the latency significantly as well so I guess there are multiple reasons for going to snowflake bus yeah by the way so in that table alpha 1 was the same the whole

time it was yes we just fixed alpha 1 at 4 Alp but which one I'm I going to take right the I mean in The arror Driven returning you you work with all simultaneously right so you you just look at what the results as they come in right it's an A so if if you happen to see like three rounds of 80 great when then we terminate if you happen to see six rounds 76 then great I can terminate just look any of them is satisfied yeah yeah yeah right right yeah 6565 the bottom yeah yeah okay begins to slow down yeah okay okay so we're making the move to SMR uh yeah we're considering a standard setup we have blocks of transactions Etc

all the standard format okay so we're going to assume there's a there's a unique Genesis block we're going to work with monolithic blockchain now so each block has a unique parent okay and you have to have the Genesis block as an ancestor okay so all the the standards sort of set up to make the analysis General possible actually we're going to decouple the process of block production from the core consensus engine okay so we're going to suppose there's there's some process for Block production in the background uh that's producing blocks and the valid blocks have been gossip throughout the network okay U if you don't like that if you want to makeit things concrete you can just imagine that we're we take it in turns As Leaders to produce blocks okay whatever method you want is fine okay so to implement SMR now our basic approach is

to run multiple instances of snow fake plus so let's consider first the task of reaching consensus on a block of height one okay so let's suppose the Genesis block of height zero from each consens block of height one let's suppose you know multiple blocks of height one are proposed and we have to decide between them so to turn that decision problem when we got multiple different options into multiple binary decision problems we just consider the hash value h of B of each proposed Block B of height one shy question what does this mean are proposed can anyone propose well I said we're we're black boxing it here so we we here when I'm not going to talk about that stuff if you're worried about it imagine that you the leaders are taking turns okay imagine you're just the leader happens to be the one that speaks

in slot one because we are synchronous and there's another leader for slot two because we are still synchron I don't care about the process of block production but okay yeah let's imagine you have in each slot uh slot yeah whatever every so often doesn't have to be every slot whatever just like uh every so often your Tak turn somebody's producing blocks yeah but then we have some amount of time to agree with the Snowman on whether this is a correct proposal or not and then the next SL should it won't matter it won't matter because the it doesn't matter the rate of which block are produced it right I mean if you want to produce one round one block per round that's fine no but what what if 300 blocks are produced in the same round that's fine that's fine absolutely fine yeah doesn't matter which one is going

to be chosen well that's what the consensus has to decide yeah yeah yeah so okay if you want to make it concrete just imagine that one block is produced per round and maybe by a banti leader who'll produce 300 blocks or whatever right yeah okay so the we're allowing equivocation here right so we're not we're not saying yeah so we obviously the consensus engine has to decide which block we should finalize that's the task so lots of potentially lots of blocks of height one I propose okay so uh in order to turn that into a multiple B binary decision problems we're going to consider the hash value of each proposed block of height one and we're going to run one of snowlake plus to reach consensus on the first bit of the hash we run a second instance to reach consensus on the second bit of the hash

and so on yeah making nothing to it then working above any block of any height H the same process is then used to finalize a block of highight H plus one so it's very simple you might initially think that's quite inefficient I don't want to run the consensus for each bit but that's not the case Okay so that process would be inefficient if each round requires a separate set of correspondences for each instance of snowflake right for each bit we don't have to do that right so what we do proed as follows so each processor now maintains some local values pref and final okay so basically pref records the hash Valu of the presently preferred chain and final records the hash values of the their final chain so in my presently preferred chain is B1 B2 B three take the hash of B1 conate the

hash of B2 and conate the hash of B3 as a sequence of bits that's my present value pref okay it specifies my my my preferred chain okay similarly my finalized chain is B1 and B2 take the hash of B1 concate the hash of B2 that's my my present final value okay so they yeah they record the hash values you if you're preferred in final chains so just as in snow fake Plus at the beginning of each round each processor samples some K other processors okay and now they're asked to report their their present pref value right so they don't report like you individual value for each well they no longer report a single bit they now report their pref values okay and then process a pi just uh proceeds bit by bit from its local final value but with no further communication right if it starts

with local final value and asks for each bit have I received sufficient responses to change my my next preferred bit have I receiv received sufficient responses to finalize my next bit then acts accordingly before proceeding to next bit right but with no further communication required okay with each round it can just proceed up through the bits so the bit where you say it's not inefficient to go bit by bit that's well in terms of the communication cost right so you just you just communicate once at the beginning of each round you sample K people you ask them for their preferred values and then given those preferred Valu one set of preferred values you do this iteration up through the bits determining like whether you've seen enough values to change your mind or not but they send you all the bits there 256 mons right yeah well yeah you send your

entire uh preferred chain you send this this long sequence of zeros I mean obviously you might might you might I mean a hash value is a cryptographic hash value would be 256 yeah so you're send this one hash value well no you're sending your entire preferred chain of hash values according to the simplified version obviously you might try and optimize that so you're not going to send really old stuff that's been finalized but in the simple version of the protocol you're just sending your entire uh preferred chain right we're just trying to agree on the next block right so there's not a chain of blocks yeah well no no we're working for all blocks simultaneously right we just finalized amazing a preferred one chain of blocks so when I when I ask you to report your your present value you report your your pref value which is a

sequence could be thousands and thousands of bits right you send that to me now obviously in fact that might be inefficient you probably didn't want to send old values but that's for other people to optimize me okay so like I mean in principle someone could change their entire their view of the entire blockchain since Genesis in principle right they could they could well okay but the way I Define it here is you you start each round at your final value so once it's finalized you're going to change your mind on it but there are some choices involved there right I I could do it from the beginning but I think it's yeah I see so when you say when you say change you mean since the last finalized okay okay but it might be more than one block is your point yeah yeah okay can it happen that we keep

deciding on a hash that corresponds to no block I guess I guess you have to check validity I guess if you go through the details you're going to have to first of all see a block with that hash value recognize the fact it is a valid block otherwise no one's going to start voting on it and so on so so no that that won't happen but sorry you're voting but if you go bit by bit of that hash value can can't it okay so we're running a system here where I I don't accept these hash values so no no honest player is going to start voting for stuff if they if they haven't first of all seen a block that that U is valid and has corresponds to some hash value extending what I'm what I think the worry is you have two conflicting blocks

with different hash values and people agree on the first 128 bits of the first hash value and the second 128 bits to the second hash value and then everybody agrees on that hybrid hash value no this this can't happen Okay confusing because because you have an OP an optimization that says we not approving one unless we have seen the full has yeah I'm I'm going to I'm not going to start voting for stuff andless I've seen that it corresponds to something that extends that as a valid block right through the randomness this could come in nevertheless or not well guess your job is to prove that it's extremely unlikely right I mean this is something that won't won't happen in practice Yeah and and why my job is okay and I mean there are some super wellknown other constructions that reduce like

multivalued um consensus to a binary yeah I don't know like you can do the the trick with reliable broadcast and then binary agreements or something like that so is there any reason why you're not deciding to use those I didn't Design This protocol this this the avun protocol okay so in summary then so snow man plus basically just uh employees one instance of snowflake plus decide each bit of the fin sequence of hash values and then the analysis of that that provides consistency is actually basically just uh the same as the analysis for snow fake plus Bally there very it's not quite the same you have to be a little bit careful but there's nothing much more to it moving on to Frosty then so adding the livess module so I just talk about this at high level there's of more complicated things here that I'm going to talk about but I'll

try and to F out the most important can you say again can you say again if I have two blocks why is it not possible that the output bit sequence side deci side on is some like weird mixing of the two hash sequences okay maybe I should have put the the pseudo code up here basically it's not true because you're you're not going to vote for things unless unless it's actually the beginning of a valid sequence of blocks that you've seen that's in your database as a valid sequence of blocks no one would start voting and changing their colors and accepting those things in the first place okay so is the point that you you don't really do when you do your local updates it's true you're updating every single bit at the same time but you still look at the sequence of the bits is that right you still look at the

sequence of bits your mind you do it in the first one then the second one but the point is if the only valid block consistent right so some of those may get forced right so for bit four you may say like this is going to be a zero given what I voted on in bits one through three even though the votes I'm getting from other people are for one is that right say again right it seems to me that there's still kind of an order in which you do the voting like not as far as the protocol as far as the messages you sent but as far as your internal you get everybody's full messages and then internally you do the voting bit by bit starting from the first one yes and the outcomes of those first few votes May at times force a value for the next bit without it being

a vote yeah I guess guess I guess the is that right and you in uh like logically but in terms of the actual probabilities basically this can't happen because honest players already they're renting like a valid block into their those are two that that's their initial you couldn't imagine you could imagine a protocol where was literally impossible for this hybridization to happen or you can imagine one where it's just with low probability so which is it for you so in this case I guess is it possible that you form some hybrid um yeah I guess if you're sampling enough uh if it's something Enough by anti no essentially with probability zero I guess depending on precisely how you define the soda code maybe it would be possible but then I guess you could just alter the C codes

that it's not possible so I mean I don't think there's a sort deep problem there I mean but okay in practice here that won't be an issue if it is possible that you can end up with a a sequence which is not a valid block then you could just change the cic code so you ignore that sequence yeah so we're moving on to Frosty want to add in the the liess module um so what's the basic idea here so the basic idea is we're going to run the Snowman protocol during standard operation and then temporarily fall back to a standard Corn based protocol in the event of a livess attack okay so to do that uh just a language we talk talk in terms of so we'll have instructions divided into epochs okay imagine the first Epoch Epoch zero processors Implement snow man in the event of Life attack and only in

the event of Life attack processes then enter EO one and Li the coron based protocol to finalize the next block there are some choices there you could have them stay in it until everybody's happy to move out of it or you could have them finalize one block or what and move back for now we'll do it do it this way it's easy to move between those options okay then so once that's achieved then end OT 2 and revert to snow mana and so on okay so the idea is you only enter each odd Epoch and start implementing the coron based protocol if a livest attack during the previous Epoch forces them to do so I guess there are a number of different things you have to think about here but the principal difficulty is ensuring consistency we moving from from even Epoch to odd Epoch okay basically we

know we're going to have consistency within EPO okay so we have to worry about consistency between Epoch and I guess that yeah the hardest case is we moving from an even new Epoch where you're running snowman to the odd Epoch so we'll focus on that okay first of all just to make things concrete okay so how how do we determine when when we enter the OD Epoch and start running the cor based protocol uh there's nothing C here basically just Implement a sort of standard view change protocol okay so it's standard all to all view change protocol so there are more sophisticated you could do here but it's going to do a simple version so while in an even Epoch e and for a parameter gamma of chosen to taste P will send a signed message U particular form written here is stcky final but anyway it's some message

saying that they want into the next Epoch okay to all others when it sees gamma consecutive rounds J which's local value final remains unchanged okay so you've seen enough enough rounds enough consecutive rounds without changing your final value okay then you're going to vote basically to enter the next epoch okay so that message indicates that Pi wants to enter into eoch e+1 and then for any fixed Sigma a set of messages of size at least n over five each sign by different processor and this form so you want to ENT next Epoch we'll call that an Epoch certificate for Epoch e+ one and how do we proceed okay just as I say just as a standard way you do with a like a a heavy auto view change protocol so when pi sees an Epoch certificate for Epoch e+1 basically that that tells it's okay

now to enter next Epoch what it does it sends that Epoch certificate to all others and enters +1 okay so we proceed that way that ensures that when any cor correct processor Enders e EPO e+1 all others will do so within time Dela okay so so far we're not doing anything clever or interesting here this is just a sort of a standard view change process we want to we're worried about the consistency between epochs though right so we we want to uh we want to ensure the value finalized by the Quorum based protocol during an odd Epoch + one that should extend all final values for C corep processes that they they finalized during e e let's say yeah so idea here is we going have processors send out their local pref values that records their preferred chain upon entering EPO e+ one then use those

values to extract the chain that it's safe for the quum based protocol to build on and so to be more precise then so on entering e e+ one we have P send out a message some particular form that basically says okay I'm starting EPO e+ one and this is my my present prep value okay so they're just telling everybody else that their prep values okay so I'm calling that message a starting vote for Epoch e+1 okay uh some Val obvious of terminology for any Sigma I'm going to say that that starting vote inv involve specifies the string pref extends Sigma if pref extend Sigma okay so starting vote just specify some pref value we say the starting vote extends Sigma have the pref value extend Sigma by a starting certificate for Epoch e+1 we just mean a set of 2 N over3 or at least 2 N over3

starting votes for Epoch e+1 it's a starting votes just say your breath value at least two three of those that's called a starting certificate okay here's the maybe slightly new element to the definition if s is a starting certificate for EPO e plus1 okay the set of at least two and over three starting votes then we'll set pref star of s to be the longest string Sigma extended by more than half the messages an S so pref star of s is just the longest string Sigma extended by more than half the messes s okay and the basic idea is that pre s must extend all final values for correct processes and therefore consistency we maintained if we have the Corn based protocol finalize a value extending that string so you're just saying if if it's final for

somebody it'll be in the pref for half the other guys basically yeah basically yeah if if it's final for somebody then you take any uh sarting certificate and you form the Press St s of that SAR certificate it should be should extend that finalized value if it's finalized from Hest partic okay yeah so the basic idea is that pref star of s if s is a star certificate must extend all final values for correct processes so why is that true of sketch that and I'm going to lie slightly but make it seem like it's true so let's Recall now the analysis of snow fake Plus if you remember there was this 56 that was there before that didn't really need to be there but now it's going to be useful so what we saw before in the Anis of snowflake plus was if any correct

processor Pi finalizes red in a given round then actually more than five six of the honest processors will be R by the end of that round and in all later rounds that's also something similar is true for snowman plus it also holds that if any correct processor Pi finalizes Sigma in a given round then more than 56 the onest processes must have local pref values extend Sigma by the that round and all later rounds okay so something true is similar similar is true there hopefully that's easy to believe Okay so we've got 5 six if somebody's finalized this value Sigma right that means that 5 six of the honest processes must have local prep values that extend that Sigma okay so that's the five six values here we've got at least four fifths of the nodes honest so that means at least 2third of the nodes are honest and have

PR values that extend Sigma if Sigma has been finalized by some some honest guy so then we just do a simple counting argument since s contains at least 2 over three starting votes and you just look at the intersection then more than half the OES and S must extend Sigma okay so that follows by sort of simple counting argument so I say I'm sort of I'm lying slightly because there were certain complexities involved um anyway this that's the basic idea so some final comments and in the analysis there uh we made the analis simpler just by imagining everybody proceeds in lock step through the rounds as I said that assumption can be dropped so in the in the first paper we made this simplifying assumption there's now a second paper which I've almost finished writing up and which we able to drop that assumption another point to be made here

is so the we have have we defined this Liv module that basically means that okay we can deal with Liv attacks okay so all all the ab able to do in the event of a Liv attack has basically forc you into the cor based protocol for a while so increase the communication costs hopefully that means they wouldn't bother doing it it'd be more satisfying if we had some sort of livess accountability here right because at the moment there's nothing to stop from carry on carry out such attacks so obviously be more satisfying if we had some sort lious accountability but we haven't thought about that yet so that's that's subject to future work I think you mentioned the beginning of the talk this is like kind of like a D based protocol in some sense um just curious I guess like comparing this to like other

high throughput consensus things like other dag based protocols is there the D based protocol yeah I used just asking like um comparing this to other like kind of dag based protocols in terms of like the throughput in some sense um is there any comparison you can give is this in original white paper they describe a dag based protocol they don't use the dag based protocol anymore and now using a monolithic one part of the reason for that is that the dag based protocol didn't give you a total order on transactions right so uh so in that sense it wasn't really comparable to the of I guess the Modern Wave of dag based protocols that do give you total ordering uh I guess yeah it's not PR protocol is gone that was there until last year I I see um so noways they have a different protocol let

that's the one you descri well I I guess I'm asking just in terms of like dup comparisons like is there a reason this is superior to like a dag based thing or what does this I think that will depend on the the numbers right so a lot of the Bas protocols now they do tests and maybe get 100,000 transactions a second maybe that's with 150 nodes those protocols probably wouldn't behave very well with 10,000 nodes whereas maybe this would scale better uh in that sort of scenario so I haven't seen the actual numbers for 10,000 nodes Etc but will also depend on is this better than the D based protocols which ones you mean because the D based protocols that come after all you need is St they embed normal quum structure in there they don't exploit with the POs that you can also approve transactions in POS Lo this

is not actually popular and I think the reason that I UND we also worked on this the reason we understood why they ban one reason why why they are Bandon it is that it did not produce a total order so it was faster because it did not have to produce a total order but uh the customers cannot deal with this so because one exchange could see a transaction happening before other transaction even though those two transactions have nothing to do with each other MH yeah you know because if you do just doing Bitcoin transactions it doesn't matter utxo transaction it doesn't matter which one is approved first because they have nothing to do with each other but still all the software in the supply in the systems that connect to a

chain they might be written in a way where they have to know which one came first which is a limitation in the peripheral and not in the in the engine the applications where you want the total ordering as well right so you're limiting contracts you want the total order this is why the the D base protocol was never running this on the smart contract platform which is called the C chain but it was only running on the xchain for the exchanging and the utxos so has this or do you think this will lead to any changes in the version of their protocol that's okay so so far uh so the snowfake plus introduces these two parameters rather than one so that's been implemented and tested and behaves very nicely uh has actually been rolled

out to the public yet but I think at some point that should happen the error driven snowflake which I think is nicer still that's also that's in the process of being implemented ay larger task that's been implemented the frosty part hasn't yet been implemented I guess that's a harder task because you also need to implement your entirely separate cons is protocol and so that's uh okay well okay I'm not a developer but okay apparently that's a larger task right so that that part hasn't been the question you kept dodging like if you don't have the liveness gadget right how bad is what's there well okay so I but just look at the original papers the the emission is there in the first place a Ruden adversary can can launch attacks on on livas right so I I haven't personally done any further analysis of the livas I mean because the liveness

module it's it's hard to assess right now whether it's kind of academic or whether it's really kind of essential for theing yeah for the for the protocol I I just as long as we don't see any attacks then it doesn't matter yeah exactly that's also true so actually there haven't been attack then we can just use and I guess I guess your your your point would be if there's no attacks it'll just act an exact the same way whether it has the L module or not just a bigger code base basically yeah I another question this is stake based ultimately you you present it as n noes right and square root on n and so on yeah but this is stake based selection proos selection probabilities and that's also what happens in algor and then in other stake chains like cardano right so

there's this nice idea that one does fixed selection of members suppose you have to pick a committee of 10 okay and I know one entity has 15% of the stake I I might as well put them always into the committee right yeah yeah yeah how does this change does that's something I Steven but off is on the team very keep those ideas right yeah I haven't personally thought about those those um details much by well there's a paper on this fat is the paper is from the iog group actually from the cardano folks but it's the same idea that can be applied here yeah I guess in the paper we just sort of treat it as a permission protocol uh for most of the analysis here I mean you could do a S State based

version uh and all it would do is make it more complicated but it would essentially be the same arguments just complicated yeah okay