Latency Limits of Byzantine Consensus with Ling Ren | a16z crypto Research Series

Transcript

All right, good afternoon everyone and welcome to today's A16Z crypto research seminar. Our second seminar this summer by Ling Ren, professor at University of Illinois. Um this is a cool one because as you know Ling has been visiting us for a lot of the last almost um two months and um you know I've watched his sort of thinking on this topic uh sharpen greatly over that period and we get the absolute state-of-the-art of Ling's understanding of slow pass and fastp pass and consensus protocols. So >> yeah thank you Tim for the introduction and thank you again for inviting me to spend the summer here. I really had a great time here. Uh and this talk is a good partial summary of what I've up to this past summer. Uh it is a tutorial talk on the best latency we can hope for

in Byzantine consensus. So most of the results were known to us 20 years ago. However, uh this summer really helped a lot with um interns and visitors in particular Evolve, Italy and Kardik. uh we significantly improved our understanding on these matters and we have found better ways to present uh some of these classic results. Right. All right. So um so let me start with this problem of Byzantine consensus the lamp um peace and shack uh they gave it a nice story that we have several generals lay siege to a city. So they want to agree on a common battle plan.

Either they all attack the city or they all retreat, right? The challenge here is that some of the generals may be traitors, right? So they may say one thing to some of others and say and the opposite thing, right, to others, right? And the goal here is to reach a common decision despite such malicious behaviors. Okay? And the overarching question I'd like to address in this talk is how many rounds of communication do we need in order to reach a decision in Byzantine consensus? There's some well-known results that some of you may may have seen, right? Uh one result says we need F plus one rounds of

communication where F is the number of malicious parties. Another result says we just need three rounds, right? PPFD says that, right? And uh this is indeed if I I asked this question to chatbt and he it gave both an answers right and indeed there's no contradiction because the first result is a worst case result right we should really think of it as a negative result right that because especially in the era of blockchain when we have thousands or tens of thousands nodes right if we uh and we're hoping to tolerate say one-third fraction of the malicious nodes right so uh that would mean in the worst case we would need thousands of runs to make a decision, right? But we will focus in practice the

good case, right? And I'll define what good case means in a bit, right? And in the good case, we can reach a decision in three rounds, right? That's what the classic PBFT protocol shows us, right? And in some cases, uh, two rounds are enough in a good case again. So uh this really represents um a slight different way of thinking in theory and practice and a good way to um right to categorize the design philosophy of practical protocols right that is to prepare for the worst but hope for the best right that in in the worst case we have a lot of adversaries we still want the protocol to um provide agreement right but it doesn't have to do it fast right

however most of the time in practice nobody Nobody is trying to attack right partly because we've convinced them that even if they try to attack they wouldn't be able to succeed right so nobody's really attacking then we can get much better um efficiency right so there are some famous quotes uh that um that may not be talking about BFD but captures the right design philosophy of practical BFD >> okay >> so just to clarify when you say around you mean literally one message from one person to another yeah correct >> it's not like a round trip right >> correct yeah round by round I mean one message delay right if a round trip I talk to you you talk to me back that counts as two rounds all right and we are counting uh all the rounds right so

there are some results that only count voting rounds do not count the round where somebody sends a proposal right but so there's some uh differences if you count differently right um okay so next I'll in this talk I'll show you um I think four results four protocols right that give us good case two rounds or three rounds in different settings, right? And but we'll start with the basics, right? So let's define this Byzantine general problem a little more precisely, right? So this is one variant of Byzantine consensus. It's called Byzantine broadcast. Right? Here we have n parties up to half of them can be malicious or Byzantine, right? And um out of these end parties, one party is a

unique, right? We call it a designated sender, right? That party has a input X it wishes to send to everybody, right? And the most two important properties of a Byzantine broadcast or consensus protocol needs to provide is safety and livveness, right? Safety says if two honest parties output, they output the same thing, right? Liveness just says uh every honest eventually outputs, right? Um but so far this is not a good definition right because there's a trivial solution right there's a trivial solution that says uh everybody just ignore the sender let's all output zero right so to rule out that trivial

solution we need another property called validity that says if the sender is indeed honest then we should output what the sender has to say right so this is the classic definition for Byzantine broadcast right but uh in this talk we care about the good case efficiency So add uh I will add a efficiency requirement in a good case right that says if the sender is honest then we want to output fast right in RS R is usually either two or three and that also defines what we mean by what I mean by good case right good case means the sender happens to be honest right there might be another F malicious parties among the participants but not the sender another popular variant of

Byzantine consensus is Byzantine agreement Right? This one again we have n parties up to F of them are malicious right but this time there's no special sender everybody gets an input and once again we want everybody to outputs the same thing that's safety and livveness right but validity is also a little different since we don't have a sender here right it says only in only if every honest has the same input right only then we are required to output that value right otherwise we just want to output some agreed upon value but it can be anything right um I should uh clarify that I I maybe I I'll often say everybody should do something I always mean every honest right should do that

right because we cannot dictate what a malicious party will do okay so here's a picture uh summarized the two problems right the difference is that in broadcast only the sender has an input in agreement everybody has an input and uh in this talk we're not going to study agreement right I will only use it as a black box right and uh I did not define a good case for it. I don't have any efficiency requirement on it, right? Um it can be slow. So next we need to talk about the network model, right? Uh we assume every message is signed and it's sent to everybody, right? Um but we don't I'm not assuming a peer-to-peer network. This is a pointto-point network. It's just that all the protocols I use uh in this talk, right?

It always instructs a party to send the same thing to everybody. Okay. And the most important aspect of the network model is the timing, right? And if you still remember my talk from uh two month two months ago, right? Uh I talk about this three mainstream timing models, right? Synchrony says that there is a known upper bound, right? Every message between uh from one honest party to another honest party needs to be subject to the delay bound, right? Asynchrony says there's no such bound. any message can be arbitrarily delayed. And then partial synchrony says the network alternates between asynchrony and synchrony. But because in this talk we are only dealing with

agreeing on a single value for simplicity, right? So then we don't have to think about this alternating right there's just one asynchronous period followed by uh one synchronous period forever right. Um and that boundary is called the global standardization time. Right? Before GST the network is asynchronous afterwards it's synchronous and we will start with synchrony and in synchrony it's common to think about the even more ideal pro uh model called lock step synchrony right so here we divide time in um perfectly synchronized rounds right at the beginning of each round everyone sends a message if they have a message to send right and by the end of that round all of the messages sent in

this round are received right and then we may do some computation and then move on to the next round. So first I'll show you the results in synchrony uh that says if we have dishonest minority if we have honest majority then the uh good case latency is two rounds right so I'll first show you some lower bounds right this is the lower bound I briefly mentioned earlier in the worst case we need f plus one rounds right this holds even for crash faults even in synchrony right so that basically says all um consensus protocols in all models need F+1 rounds in worst case, right? We can also >> clarification worst case means with

probability one >> uh just means um there is a chance, right? So >> yeah, so one popular um interpretation is that this only applies to is only relevant for deterministic particles, right? If you use a randomized protocol, this bound technically speaking still holds, right? But you don't care about it because you can argue the worst case happens with very small probability right you care about the average case or with high probability case right so then this bound doesn't really hurt you much >> wait so so I are you like I guess you are saying in the information theoretic model because if you use cryptography there's automatically negligible failure >> okay yeah I'm assuming crypto all cryptographies uh primitives are ideal

so we can we also have a pretty trivial lower bound in the best case right that even in the best case there's no protocol that can outputs in a single round. So this should be easy to see right because how can we output in a single round? Pretty much the only thing you can do is that whatever you hear from the sender, you just output that, right? But then if the sender happens to be malicious, then um right, that protocol is uh unsafe, right? Okay. So one round is impossible even in the best case, right? So that makes this result tight, right? That there is a synchronous Byzantine broadcast protocol that in a good case uh gives us two rounds of commit latency. I'm just

confused about the the impossibility result because what model is this result in does it allow crypto? I mean because because I I like for some primitives maybe ideal crypto doesn't exist anyway, right? So if you allow primitives that don't exist. I mean I'm sure in some model the round let's say I have just a trusted consensus functionality then this blow bound doesn't hold. >> Okay. Yeah. Sure. But uh yeah but it's uh yeah but it it's only stronger if we assume crash faults synchrony and ideal crypto right ideal signatures. So only you only allow ideal signature you don't uh >> allow any other crypto >> the other things well unless you use a like broadcast channel consensus engine

right I don't see how other crypto primitives help you right you can add MPC zero knowledge right anything you want to add it shouldn't uh help you >> the lower bound of one round also applies in the case of crash faults right of crash faults I'm not sure crash faults probably not right because then indeed I can just output whatever the sender says right because I know the sender will not equivocate right so I can output the senders what the sender sends me and then send this to other people to help them uh output right so indeed I think the u one round lower bound only works for the Byzantine case >> so but philosophically why does this negligible failure why is it important we use crypto everywhere in the real

world already and there's already negligible >> I agree I agree so right so uh okay indeed Indeed, it's common to think of this to be only relevant for deterministic protocols. If we use randomized protocols, then yeah, so then I agree. Then we only care about the expected rounds, right? We don't have to stress over worst case round. >> I see. So you're saying your is because like your upper bound is also in this talk. Yeah, in this talk. Yeah, good. Uh in this talk, I'm only using deterministic protocols, >> right? And uh I also don't see how at least I don't know a way for randomization to help in the good case.

Um okay so right since we um since we proved the one round is impossible right this two round good latency uh using deterministic protocol is um the best we can hope for >> but you could hope for it with higher fault tolerance than that potentially right >> okay yes okay that's a good point Tim is pointing out that I'm only doing the providing a good case for minority faults right um the Byzantine broadcast problem indeed is solvable even for majority false. I think Yoken gave a talk on that. Um but yeah, I we do know that there's no good case in that setting. Um the reason I'm not saying mentioning it is because um because of this client's issue, right? The minority

false is the more relevant it's the more useful setting for practical protocols. >> I mean what what how do you define the good case? Like for instance something like Cinderella is also too round in the good case. Uh the yeah the good case only says the leader is um the leader is honest but efforts can occur. >> So so I guess the point is like um you can do it with minority f but Cinderella needs a different fault tolerance. Correct. The threshold is different.

>> Correct. Yeah. Okay. So yeah. So I'm showing uh this protocol that uh from um 2017. I think this is the first Byzantine consens. So I have some special attachment to this protocol, right? Um so first round sender sends the input to everybody signed, right? Um and the second round if I receive a signed input from the sender, I will vote for it. I will also forward whatever the sender sends me. Then we can commit at the end of this round. If I see N minus F matching votes and I do not detect the sender equivocation, right? meaning that there's no other node that sends me a signed input from the sender that's different from the one

I received from the sender right then I will commit in two rounds right so and we can easily see that um in the good case this commit rule will kick in right because the honest sender will send the input to everybody will not equivocate right so we all commit the sender's value in two runs but the malicious sender may not um guarantee commit Right? We're still it may make some people commit but not others. So we need to do more work. Right? So I will define this N minus F matching votes to be a certificate for that value. Right? In the next round if I commit it a value I will send the certificate right that made me commit to everybody and then we will invoke a

Byzantine agreement um blackbox. What do I input to the Byzantine agreement? I will input X if I received the certificate for X. If I did not receive any certificate then I'm inputting this special value but you can really think of it as a don't care right I'm inputting a don't care value into the Byzantine agreement so we already argue that the good case two rounds holds livveness is also pretty obvious because I output either here or uh here I commit the business the BA box output if I haven't already committed okay and commit and output mean the same thing I'll use them interchangeably right so clearly everybody will commit Right. So the last thing I need to prove is that

safety holds, right? That if two honest nodes do a fast commit in two rounds, then they agree with each other, right? If some honest nodes do a fast commit, others do a slow commit because of the Byzantine agreement. They also agree with each other, right? Um let's see why that's the case. If there's a faster commit that needs at least one vote, right, from the honest, right? Because we need a certificate, right? Certificate is N minus F, which is at least F+1, right? Because our N is at least 2 F plus one, right? So if there are conflicting commits, that means some honest voted for X, some honest voted for X prime, right? But they when they vote they will each forward the sender's

signed input that will help everybody detect equification. Right? So no no one would have fast committed. So fast commits must be consistent. Now next if some honest did a fast commit right then we already showed that a certificate for a conflicting value cannot exist right and that honest will send the certificate for X to everybody right and according to our businessing agreement input rule everybody input X to BA right and BA says if every honest input X then the BA output will be X right so the BA output will also agree with the fast commit If any that's the first protocol

uh I'll show you >> if you replace the BA with some something that allows randomization can you get what's the you you can can you get like what is it called good case two rounds and and what's the smallest number of rounds for the worst case assuming >> if I use a deterministic box here this is likely going to run in order f rounds uh if I use a randomized thing this will output in expected constant rounds Uh what's the smallest for that concentr? >> Uh I think I know a protocol that can do expected eight. I that's the best I know >> in the synchronous model. You need eight eight rounds.

>> Yes. Because uh the best protocol I know you have four rounds per iteration and you need inspect expectation two iterations, right? Um >> wait is eight rounds just for that box or the whole thing is eight rounds. >> If I do this in a black box, this is expected eight rounds. I can open the black box and try to do a code design to make the whole thing expected eight rounds. >> But aren't there like a basantine agreement with fewer rounds? Wasn't like cartic talking about something with smaller number of rounds? >> Uh expected that's the best I know. Um there's early stopping where you can do um but early stopping at least I haven't seen a good protocol that uh also

incorporates randomization right so yeah I I >> what about hot stuff >> hot stuff is improio synchrony I think uh maybe it's uh better that we take a look at it in a bit okay so that's the full situation in synchrony right so now we'll move on to pio synchrony pio synchrony slightly more complicated um because the good round latency actually depends on your fall tolerance. Okay, so in pajio I'm still going to use a lock step round model but before GST some of these messages can take more than one round to arrive right after GST uh this messages arrive in the round they're sent. I also need to revise the good case for our Byzantine broadcast

problem, right? To be that not only the sender is honest, but I need this GST to be zero, right? Meaning that the network is synchronous the whole time, right? So why do I need to do that? It's because in patch synchrony I cannot distinguish an honest leader who has a bad network from a malicious leader who just doesn't speak, right? So if the network is not synchronous then I I cannot hope to get the sender's input. I also cannot hope to take advantage of the sender to do a fast commit. So we also know that uh in pio synchrony I at least need n to be greater than 3f for the problem to be solvable right if n is less than that uh just forget about the efficiency good

case right the problem is not even solvable um right because of this split brain attack. Now if n is larger than 3F but at most 5F minus two right then we can show three rounds are sufficient and necessary right and sufficiency is established by PBFT and many follow-up works right but the necessity result are relatively recent if n is even larger than that right at least 5 f minus one then two rounds are sufficient and necessary so this um minus one may be a little unusual Usually it's 3F plus one, 5F plus one, 12 FF plus one. Right? Okay, so indeed this is a little subtle right for this talk uh I will ignore that part

right we will I'll show you a two- round protocol assuming 5F plus one right and that would be um pretty old result right from 2005 by JP Martin and Lorenzo obvious but let's first look at 3F plus one right and uh where we do three rounds this is the protocol that uh roughly speaking like resembles PBFT tending hot stuff right all of them Right. Um but closest to simplex, right? The way I I I'm do I'm going to do it. Okay. First round still sender sends the input to everybody, right? That's the natural thing to do. Second round, if I receive the input from the sender, I'm going to vote for it, right? I'll call that vote one because we have a second

round of voting, right? If I receive enough votes one for the same value x, then I'm going to vote for um send a round two vote for that value x. Right? I'm also going to define this uh matching vote one to be a certificate for x and I'm going to send that along with my vote two. Now here this is a a new trick in simplex, right? That uh usually it's just this this logic, right? uh additional I'll do one more one more thing here right if in this round I did not have a value to vote for I will vote for that special value bought you can think of this abstain and we will commit at the end of the round

three if everything looks good right uh in particular I commit based on n minus f vote two for x right and again we can check if the sender is honest and our network is good then sender they will send every honest will do vote one every honest will do vote two for the sender value right so we will commit in three runs okay so again uh I will need to rely on this bizantine agreement as a black box right if we did not do our fast commit and uh we will input to the bizantine agreement using this rule right if I have a certificate for x which means n minus f vote one for x then I'll input x to my BA box,

right? Instead, if I see N minus F vote two for abstain, then I'll input don't care, right, to the BA box, right? And I'll keep waiting until one of these condition holds, right? So, if the network is good, it's not guaranteed to hold in this round four, right? Unlike the synchronous case, right? But uh I'll show you that uh one of this will hold eventually, right? It's actually pretty obvious because uh either some honest is sending this certificate of X, right? In which case this case will eventually trigger when that message arrives or every honest is sending bot, right? In which case this will eventually trigger.

So, sorry. In all the protocols that you described, uh, it seems like you always do BA like is there how do I know when I should not do BA because otherwise it's not a three-run protocol, right? >> Okay. Yeah, that's a great question. Uh, so yeah, I think the what I should should have clarified is that when we say we have a good case output, right? Um, I mean we make a decision commit, right? But I do not mean halting, right? So even if I um committed here I will do a input send the input to BA to help others right um in in this particular case I think there is a way to halt right I can send this uh matching votes two to others and then

I can halt in one round right but uh in general that's not what I'm trying to do >> I guess that kind of also resolves my earlier question in the sense that if if I'm allowed to hold early then there is a lower bound for one round crash fault broadcast. >> Uh yes. Yeah, that's yeah. >> But now if I can continue to help others uh confirm the same decision as me, then there is no such lower. >> So the good case three round latency it should be pretty obvious, right? So moving on to safety again there are two things I two steps I need to do to prove safety. One is that fast commits agree with each other. The other is that fast commits agree with the BA output. So the fast commits safety is a standard quorum

intersection argument right that a fast commit requires a certificate right. So if there are two conflicting values that are both fast committed right that means there are n minus f voting for the red value n minus f voting for the yellow value right so then the intersection of that right is the sum of those two columns minus n which is n minus 2f which is at least f plus one right so for that to happen right that means some honest node in that intersection needs to equivocate right needs to double vote right but on this note never do that right so there cannot be conflicting fast commits so moving on to this uh

safety between fast commit and ba if one honest fast commits then there are n minus f vote one for that message for that value and n minus f vote two for that value using a corum intersection on vote one right that like what we did before there is no conflicting certificate right for a conflicting value then I again I'll invoke quorum intersection on vote two that means there are not enough vote two for abstain right because there are many vote two for that committed value right so there are not enough vote two for abstain right so then look at our BA input rule then this cannot trigger

right there's no conflicting certificate right then the only thing that we can input to the BA K is uh X right so again everybody input the same thing to BA BA will guarantee us that's the output right so our fast commit agree with our BA okay so this is a good case three round partially synchronous protocol so now let's move on to try to do two rounds right um >> wait hold on what's the total number of rounds the >> in this particle >> yeah the the >> yeah that also okay what is the total found in this protocol that again depends on how good that Byzantine agreement box is. I think again uh I can see how to do it in deterministically in

three f plus three times f plus one rounds right so basically we do we repeat this >> I I I don't want it to be deterministic >> oh you uh okay so then I think I can do three round per iteration and then just expected however many iterations which I think 1.5 iterations right because this is in one/ird malicious right uh yeah so I can see uh overall 4.5 5 expected round protocol >> but also in that BA there's like uh view synchronization things that come into effect because not all correct parties will start the BA at the same time I have to wait to receive either the CX or the N minus F v2 stuff right >> Mhm. And then like in this lock step partial synchrony uh I can see 4.5

rounds >> 4.5 is the whole thing or is just that box. So okay if I do it this way then it will be worse than four 4.5 right but um this is just for simplicity right if you if I really want to go for that I I wouldn't use a blackbox ba I would uh co-design this whole thing right to be basically right repeating repeatedly run this three rounds right so um total expected 4.5 is doable so now let me move to try to do two rounds Right.

Uh so I'll first give you some intuition why two round is impossible if n is smaller than about 5f. Right. Um >> hold on. Sorry. I'm still confused the four 4.5 rounds. What about how does it compare with the best protocol that doesn't worry about the good case? >> Yeah. Even if you don't worry about good case, I cannot think of a better protocol on top of my head. >> So So what was the lower bound? you you said there's some lower bound for >> so I only have lower bound on good case and lower bound on best case uh good uh on worst case um I do not know any lower bound on expected case right it seems a little hard to do right um >> there is a result from the 80s that says

that any randomized protocol that halts in RS needs to be wrong with probability at least one over r to the r >> yeah but that's still not expected right if you take the expectation it's probably just not very useful bound So you're saying there's no known >> Yeah, I think it's a big open problem. >> You match the best known upper bound without a good case. >> Correct. And there's a big gap, right? In synchrony, the best expected I know is eight. I don't think I even have a expected three round lower bound. Um in asynchrony yeah again um okay. Um so yeah I won't be able to give you a rigorous proof but I'll give you some intuition why roughly speaking 5F

is needed right and I'm not going to worry about plus one minus one. This is just intuition because I'm going to assume this is how the protocol works, right? But it's a good intuition because really there's no other way to design the protocol, right? I will assume that basically the leader makes a proposal, everybody votes, right? That's pretty much uh the only thing we can do in a two- round protocol. Now the tricky case is that it's possible that some honest node J receives N minus F v one, right? So it looks like a good case. it has to commit. But immediately after it commits, it experiences network asynchrony. So it cannot talk to us anymore. Now the rest of us, we cannot wait for that party J indefinitely,

right? Because J may have crashed, right? Or may be malicious, right? So we will have to move on, right, without it. And we have to move on but still commit X, right? Because J might have committed X. What do we do again? The pretty much the only natural thing to do at this point is to ask right let's exchange what we voted right what everybody voted so we can collect n minus f vote one messages possibly for different values right we cannot wait for more than that right because the bad guys may never vote right so this n minus f threshold you see them a lot so now I want you to think about right I invite you to think about if j committed based on n minus

vote one for X and we collect N minus F vote one total for whatever message. How many vote one for X are we guaranteed to see? >> N minus 3F. >> Okay. Yeah, correct. The answer is N minus 3F. Right. Might be obvious if you have seen this, right? But why is that? Right? Because first they're Fyzyantine, right? who voted for who sent their X vote X to J but send a different vote to us. Okay. Then there are F honest who honestly voted for X but we're not waiting for them right because we said

we can only wait for Mus F then we need to move on right so the F honest are too slow to send their votes to us and F Byzantine who um equivocates right so we can we only guarantee receive N minus 3F vote one for X okay now how many vote one for a conflicting value X prime May we see 2F, right? Why is it 2F? >> Because N minus F minus N minus 3F. That's all that's left.

>> Okay. So there F honest who legitimately voted for X prime, right? Because their N minus F voted for X, right? The remaining F might have voted for X prime, right? And we have this F Byzantine, right? Who is equivocating? They send X to J but send X prime to us, right? So now in order to have a chance to solve this we have to require that 3 minus n minus 3f to be larger than 2f right because the only natural thing to do here is to prefer the most voted value right so if that's flipped right then there's no reason that we prefer x overx prime right and then we will have

a safety violation right and that implies n is at least 5f F. So next I'm going to assume we do have 5F plus one and I'll show you how a two round protocol works. So once again first round sender send the inputs. Second round if I receive an X from the sender I will send vote one for X. If I don't if I do not hear from a sender I will vote for the abstain. And we have to commit at the end of this round if it's a good case right? If I have M minus F matching vote one I will commit. So then we will invoke the Byzantine agreement.

Uh that is our input rule to the Byzantine agreement. It's actually the exact intuition we just gave. Right? Everybody we wait for N minus F vote one messages right for whatever value they vote for. Then I'll check is there a value that has gathered N minus 3F votes. If there is such a value, I will input that to BA. Otherwise I input don't care. Right? So we proved that if somebody indeed did a fast commit then all of us are guaranteed to see n minus 3f um vote one for that value and no other value can get that many votes. Right? So we will all

input the committed value to BA. Right? So fast commit agrees with BA output. Sorry if this is a very silly question, but for the running BA at the end, you're doing that to handle the potential worst case to make sure it's still correct. >> Correct. >> If you're only caring about rounds, could you not just like run some other good worst case protocol in parallel and then just say like everyone send messages for both protocols and if the first one doesn't work, if you haven't, you know, if the first one doesn't work by the time I'm hoping, then >> just do the second one. Um okay so the question is uh can we run this BA box in parallel to this right so my um

>> isn't a non blackbox one just in parallel it's kind of in parallel you said there's a non blackbox way to coales them >> no even okay even if I open the black box I'm going to put it here after those two rounds right but >> that's kind of in parallel because that that's how you get rid of those rounds right >> um >> you must really more like I'm collapsing I'm merging in the first step in this with that. Okay. Okay. Fine. >> Like like you don't even need to use Byzantine agreement. You could do the sender sends. >> But but yeah, but my my my intuition is that it wouldn't help you, right?

Because you anyway we cannot improve the best case, right? A good case, right? We already proved that's tight, right? If you move this earlier, um you're trying to improve the worst case from whatever rounds to whatever round minus two rounds. >> Sorry, I wasn't trying to make it better. I was just wondering if it's conceptually simpler. Oh, if uh >> to just say if you you know do whatever you want to do to be optimistic and just run a worst case protocol in parallel and then you don't have to worry about >> uh no I think it's tricky to to make that work right because now you have to everybody needs to decide do I take the BA output or do I take the fast uh output right and in this case I'm I'm most of the care went

into making sure that if there was a fast commit Right? Then the BA will agree with it. Right? If we run the BA too soon, then I don't know how to make the BA agree with my fast path. >> Sorry, I don't know if I'm asking the question. Like say I just have any worst case protocol for the real problem you have. So like forget about trying to do well in the good case. I just have some worst case protocol when there's a Byzantine center. I'm just going to literally run that protocol. >> Mh. >> And now I'm just going to run two protocols in parallel. >> Yeah. And I'm asking sort of like you say, okay, if the the fast protocol is done by round two, everyone go with that.

>> But okay, but it's possible that you think it it's done. You think the fast path succeeded? I don't think it's it succeeded. >> Okay. Okay. Okay. Okay. Yeah. Thanks. >> So, so for this one, can you also make the total number of runs match the optimal the best? I mean, you don't you said there's no lower bound. So, can can you match the best? I don't know how to do that. The best I can see is um like 2.4 or something like that, right? So um >> 2.4. >> Yeah, because I I I just keep repeating these two rounds, right? And then in iterations, then I I basically ask how many iterations do I need, right?

Because my n is 5F, I think I need on average 1.2 iterations, right? Something like that. Um but but I think the but um I think the main challenge over there is that I don't know how to prove expected round lower bound, right? I've never seen uh such a result. >> So what's the best known if you don't care about the good case for the total number of rounds? >> This is still the same thing, right? That uh I'm basically getting a good case for free. If you don't have the good case requirement, I still don't know how to do better. >> But you you can match the best node, right? >> Uh yeah, this matches the best node. >> The total number of runs matches the best node.

>> Correct. Yeah. So for the randomized upperbound, you're literally just like rebooting over and over again until you get a good leader or >> Yes. Yes, that's the that's the best I can think of. >> Okay. >> Okay. >> And then then the the good case is optimal like you said you have some lower bound for the good case. >> Yeah, this good case rounds is optimal >> and then the the three F plus one is what's the lower bound? >> Uh three. >> In both cases you both the good case is optimal. But is your good case lower bound also worst case? Like if it's randomized do do those good case lower bound still hold >> yes >> okay so so that lower bound is even for randomized protocol >> correct >> and then even like to constant failure probability what's the failure

probability >> the two round one I the two round bound holds for randomization >> up to constant failure probability >> yes the three round um I don't think the proof holds but my intuition is that uh if the the lower bound holds. I just I don't know how to prove it. >> So So the the 3F plus one that you're saying the lower bound is right now is for deterministic. >> Yes. >> There is a paper from 2019 that that proves the type of lower lower bounds that you are looking for here. The there's a paper from 2019 that proves the type of lower bound that you want or at least makes progress on them.

>> We randomize >> for randomized lower bounds. Yes. >> So yeah. So this is uh one part of the safety proof, right? The other part is even easier, right? because my n is even bigger. So that intersection is even bigger. Okay. So uh that's the good case rounds for partial synchrony. Right? And now things may get slightly um more involved, right? And turns out you can also do a concurrent two round and three round protocol. Right? By that I mean if I'm not willing to go all the way to 5F, right? But I'm willing to sit in between 3F and 5F, right? What can we do? Uh we can get three rounds in good case and two rounds in a better

case. More precisely, this is uh what it means. There's a long line of works that go for that type of uh protocol, right? Uh as before, we will have safety and livveness against Fyzantine vaults, right? We will have our three round good case if the sender is honest, the GST uh the network is good and up to F40. But in the even better case, I'll get two rounds, right? If sender is good, network is good and we have fewer than maximum allowed faults, right? That P is a parameter between zero and F. So let me quickly uh show you how to do that, right? So yeah, so there there are many

protocols in the past two decades that try to do this. most recently Solana's open glow um right is um providing this type of guarantees right um but I think in the summer we worked out a protocol that I feel is more natural right I feel better captures the essence of this result yeah >> I'm just wondering like if you use this in a blockchain protocol and does that mean I can just move on to the next block if I finalize early so so like if you use it in a blockchain you you would be seeing the good case latency >> yes If you use in the blockchain and everybody happens to be honest then we'll do two run to run two runs uh yeah and per decision >> and then then it doesn't matter if like

some people haven't started the next instance yet because it could be I think I start the next instance but other people start later >> you need some synchronization when you start you need to send the proof that um others can also start this instance you need to be able to prove your the result of your previous instance >> okay so this is a stronger property you So you're saying your protocol comes with the stronger property that will be >> needed. Yeah, I did not show it but uh all of these are certified committed. >> Okay. Um >> so just so understand the trade-offs. So like previously you showed us the first something with the first two bullet points.

>> Yeah. Uh without this part, right? >> Yeah. Yeah. No. So so right. So so um I'm trying to interpret what the new part says. Basically you are giving up some on fault tolerance to get the shave off the round. Uh we okay yes we are >> if I take f equal one over three I have to set p equals zero for your bound to hold right >> correct yeah that's a good that's a good exercise right we can take a look at the extreme case if I set p equals z then I'm not sacrificing my fall tolerance but then my better case two round only kicks in if everybody is honest right in the very best case right if I set p to be somewhere in between then my two

round better case is less stringent But then I sacrificed my overall for tolerance. >> I I still am kind of hung up on Matt's question. It seems like what he's trying to say is that like if you designed a protocol that was good for f less than 10% you get like two rounds. F less than 20% you get three rounds. F less than 40% you get four rounds. Yeah. >> You could run them all in parallel. Maybe you won't be able to halt early but you'll be able to commit earliest. >> It's it's uh Okay. Yeah. So I think the question is still about parallel >> doing parallel protocols right but the challenge is that each of these give me an output now which one do I take right then we need to run an agreement to agree which product which result to take right so that's uh even worse than

>> uh so there's no proof that you can do there's no simple way to say that like honest parties will always get the same output across all of >> no right because in two or three rounds you cannot get that right we prove that in order to get uh agreement there is a possibility that you need f rounds to agree. So two or three round is just optimistic, right? In a good case, we agree. In a bad case, we disagree whether that finished or not, right? Whether that succeeded or not. >> Oh, so when I commit as an honest party, that doesn't really mean that. Okay, >> correct. Yeah, >> got it. Thanks.

>> This is tight. This uh >> plus one or >> uh this is tight. Yes. >> Mhm. Okay, without the minus one plus one. Uh, this is tight. Okay, so the way I would get this result is by literally merging the two previous protocols I showed you, right? Um, one of them is 3F + one, the other is 5F plus one, right? So, I need to first adapt them to this 3F plus 2P + one uh number, right? How do I do that? Right? So, this is our three round 3F plus one protocol, right?

What can we do if uh we have additional 2P nodes? I can reduce all of these threshold by P. Why is that? Because what's important is the quum intersection. Right? It used to be that two corums with N minus F intersect at F plus one. Now because I have these two P parties, I can afford to reduce my quorum a little bit. Right? So my quorum size is smaller. Okay. So this is uh the three round protocol. Now the two- round protocol I started with 5 F plus one right now I need to reduce it to 3F plus 2P plus one. This may be a little unintuitive, right? Because I showed

this is the best we can hope for, right? So I will sacrifice livveness here. I'll change this n minus f to n minus p. That means I no longer enjoy livveness against f um bizantine nodes. I only have livveness against p faults. But that's okay because later we're going to merge it with a three round protocol. Right? This is exactly what I hope to get. Right? If we have P then two rounds. If I have more than P then three rounds. Okay. And uh you can quickly check that number is just whatever that is minus 2F right. So uh like this is the number of uh right this is n minus 3f. This is 2F. It changed to these but this is the number that makes the that

inequality holds. This is my three round. This is my two round. I'm literally merging them. Right. The two round protocol has a fancier second round. So I'll take it second round, right? It doesn't have that third round. So of course I'm going to take the third round of the three round protocol, right? And we literally do that merge. This is the merged protocol. This input to BA I haven't done yet, right? I'll do that fairly soon. >> And so to tie this into the previous discussion, like the two round protocol, you have a lot of control over the way in which it can fail, right? Like the only thing that could go wrong with the two round like you're not gonna have people disagreeing after the two rounds, right? It's just going to be a livveness issue. Is that right?

>> Uh I don't quite get that question. >> Suppose you had more than suppose the fault tolerance was worse than P, right? >> So this is a question of like why can you merge when you just said you couldn't do parallel composition at a high level. That's kind of >> Oh, okay. Yeah. Because I I do need to prove it, right? So now uh let without worrying about BA, I already have a lot more things I need to prove. I need to prove if the three round commit agrees with any other three commit. Two round commit agrees with any other two round commit. Two round commit agrees with any other three round commit. Right? I need to do all of those things. Right? So first three round this is uh what we already showed two three round fast commits agree with each other because of

corum intersection. Right? In this protocol the way I merged it it's pretty easy because two round commit uses a even larger quorum. Right? So if this two small quorums intersect a larger quorum is going to intersect with the smaller quorum right two larger quorums will also intersect right so all of the fast commits to run three round all of them agree with each other so this is uh just because these two particles can merge it doesn't mean I can merge uh any blackbox particles right so now uh let me merge this uh BA input rule right this is my three round rule this is my two round rule they look fairly different the way I'll merge this is by doing this

right so what I'm doing here is that I'm giving priority to the three round input rule right if the three round input rule wants to input X let's go ahead with X if the three round input rule says I don't care only then we're going to look at the two round right and the we'll input whatever the two round wants to input right if the two round also don't care then let's input don't care right so when I do this uh I don't have to worry about three round right because if there's a three round fast commit we are using its input rule right so the earlier proof we did still holds what I do need to worry about is that if there is a two round fast commit and we're

using the three round input rule which can happen right we need to make sure we're inputting the right thing but what is the argument it's once quum intersection right if there is a two round commit that's a large quorum of n minus p vote one messages right if this three round input rule uh kicks in there's a n minus f minus p v one for that value right we just showed that even two smaller quorums intersect so that larger and smaller quorum intersect right so this shows if I had a first if I had a two round commit and I use the three round commit uh input rule they agree with each other

right but this is the tricky part right that some of the old protocols from um 2005 2007 have been found to be buggy because they got this flipped right they prioritized the two round input rule right that wouldn't work right because the um three round commit has a smaller quum the two round input rule has a even smaller quorum right that smaller quorum and even smaller quorum won't intersect and so that will be wrong let me just very quickly show this is uh what uh openlow and long line of work achieves right optimistic two rounds right but uh guaranteed three rounds uh sorry not

guaranteed but um then you can I think you get what I mean right what is was little confusing that even I got confused at the beginning of summer is that there is another result that also has the 3F plus 2P plus one result right that says you can get not only Fyzyantine fall tolerance plus but additionally P crash tolerance I thought at the time that Alpenlow achieved both of these results right and I tried very hard to figure out what they how do they get it I tried to design a protocol to achieve it I couldn't succeed right until uh like Kardik visited and told us that's not uh what they claim to achieve right in fact you cannot achieve them both right you can either go for that

right or go for the bottom one but not simultaneously okay so I think that's uh yeah >> so that's the same that's that's for the same n either way you're saying the same inequality >> using that 3F plus 2p plus one you can either get this set of results okay or get this set of guarantees >> but no protocol can get both at the same >> no protocol can get both right and the intuition is that because the the proof intuition I gave is very tight, right? There's no wiggle room anymore, right? So, we cannot hope to um get more beyond that.

>> But the work by Cartic has 3F + 3 P + one right? >> Yes. If you do want to get both of these, then you need 3P, not 2 P. >> So, I I just want to get a better understanding in practice what is actually the main challenge for consensus today. So like like for instance for this kind of results I my understanding is that in comparison with something like streamlit or pala uh so it's not like streaml or pala like every instance needs to run for more runs and then you you stack them together. It's it's more like in in like in something like in those streamline blockchain every block still only takes two messages. It's just after sending these two messages you just wait longer. You don't have to send more messages right.

So it's like streamlined. Yes. >> So is this weight time really the the main pain point in practice or also Karthik talked about something else which is like some DA >> like what do you think is the main challenge in practice? >> That's okay. Yeah. What what metric should the consensus protocols uh prioritize optimize? I that's a very big question. I don't think I have a >> I'm not even asking about metric. I'm just trying to understand what's the practical pain pain point. >> So the salana does care a lot about latency. So they do care about three rounds versus two rounds, right?

>> You mean the human weight time, not the actual >> human weight time. Correct. Yeah. >> Which which blockchain did you say? >> Salana. >> Salana. >> Yeah. Salana. At least they they they went for they decide to went for they decide to go for that concurrent protocol, right? To get their um >> And is it because their users can tell the difference between one millisecond and five milliseconds? Uh >> well I mean it's more like 250 milliseconds and 750 milliseconds. Those are more the order of >> Why is this 700? Depending on the roundtrip time, right? Yes. Are there servers like that?

>> I think the round trip time is maybe 100 milliseconds and then >> so there are servers are very far apart from each other >> some of them. Yeah. >> Yeah. Yeah. >> And then then the main main bottleneck is the latency and not the the bandwidth. Um >> I don't want to I'm not a salon spokesperson. >> I think if you >> they care about both I would say >> I just want to understand is it for marketing purpose or is actually there is a need for this difference. So we can take that discussion offline once we stop recording. Um and um right so but uh on the high at a high level right if you have few nodes then communication should not be a bottleneck but if you have many many nodes then essentially quadratic communication I think will become

>> how many how many nodes does the line have >> um it's hard to say because they do some I think they do some sampling right they they have a committee I I don't know the details but I believe it's on the order of a thousand >> a thousand then it sounds like the bandwidth should be the bottleneck not the pin latency >> I think thousand is around the point where um quadratic is still manageable >> and I mean users clearly do care about response time right I mean I think that's not controversial right so >> no no yeah I just want to understand like to what extent is this this difference perceivable like whether it's three rounds or four rounds like what does it that have to be that optimal or is the other thing I would say more important >> I don't know but I do think it's

noticeable as an end user I do think >> between three and four >> I think each round you do notice a little bit as an end user >> and and I also say that all of the blockchain systems right now. I I think they are hoping that there are there are future applications, right, that they haven't anticipated, right? Maybe there are applications in the future that require that have a stronger latency requirement than the ones. >> It's hard to imagine because when we do credit card transactions, it's the we are talking about on the order of 7 seconds confirmation delay. So, so it's like >> my understanding is there's been plenty of user studies around like just traditional web two applications that show that a couple hundred milliseconds can make a pretty big difference as far as user engagement. So, >> so, so is because they're trying to beat

credit card because I mean because for credit card people are used to >> or just like you're loading a web page and it doesn't load fast enough, you go do something else instead, right? So, >> yeah, for for normal web page, but for payment is like for my credit card for PayPal and stuff, it's also not instant, right? There's like for me to go through PayPal, I need at least one minute to click through everything, right? Like if I'm already spending this one minute, does like 100 milliseconds actually matter is I mean you have to enter all this information, right? To to to to go through the payment thing.

>> Uh yeah, I think uh yeah summaries uh same set of things uh we I showed you, right? I'll just very briefly mention that so far we haven't talked about users, right? If you care about user, you need to add more rounds. If you care about censorship resistance, you need to add two rounds. And that's a new result um that uh that's proved this summer at A6Z. >> Is Salena using one of these protocols you mentioned? >> Uh yeah, Salana is one that's cool. >> Not as not the way I presented it >> and not yet, right? Uh so they yeah so they they they start with this three rounds and they

try to add the two round to it. Yeah. So there's some non-trivial logic there. Right. I I believe what I showed you is uh conceptually simpler way to get the same thing. um we're like trying to pitch the this idea to them and so still in >> what about something like Ethereum like are they also trying to change >> as far as I know does not have a two round path >> but are they planning to also do so >> uh not that I know of >> so they don't care about >> Ethereum shouldn't care about it Ethereum have have too many nodes right they have hundreds of thousands of nodes right and indeed their com their consensus their finalization layer is very slow I think run every five minutes or so, right? So over there you wouldn't

care too much about uh rounds. But now that I >> they're using PFT to for the finalizing some notion of some variant of tandem right from what I know >> is there any high level intuition you can give about the censorship resistant >> so yeah this is our business agreement right so if we add clients uh if transactions originate from clients right the leader doesn't magic magically have them then we need to add this one around from client to leader right but now leader can censor right the way to get around censorship right is that clients need to send their transaction to everybody, right? Then these parties will forward to leader, right? And they will refuse to vote for the leader

unless the leader includes everything they have personally sent to the leader, right? So this is the intuition why you need two extra rounds, right? Are you considering an a well-known fixed number of clients or >> any it can be as many as >> so so which company you said is using DAG again? >> DAG um yeah I'm not too sure I think after wrote papers on DAG I think they eventually may move to it. I don't know if the reason to use D is >> so we use uses D. Okay. So the reason to use stack is because of like the bandwidth being bottleneck or what's the the consideration choosing >> in the camp that uh I do not see a

compelling reason to use stack. >> So you you you believe everyone should just use this type of protocol. >> Yes. >> And that that doesn't help. >> Uh okay that the the main benefit I can see is um balance the workload without eraser code. But I believe we can get that without using that. Oh, because last time you said it's the factor of three. The deck improves it by a factor of three. >> I think so. Yeah. >> I I I see. >> Thanks again, man.