Shoal: Improving DAG-BFT Latency and Robustness with Alexander Spiegelman | a16z crypto research

Transcript

really glad to have Sasha spigelman speaking at our seminar today I know I've known Sasha for a long time Sasha did his PhD at techon then he worked at VMware with Dalia Maly and N Abraham and then we met at uh Novi research where we worked on the DM blockchain at meta and Sasha joined Aptos as a co-founding team member I remember Aptos was just four people and Sasha was one of them and now up is about 100 it's a big company with a with a big uh uh fantastic research team welcome Sasha thank you Lara thank you for the introduction and thank you all for inviting me I actually don't remember the last time I was nervous

before a presentation but this setup is like very serious to me so yeah excuse me it will take me probably a few minutes minutes to get into it um yeah so yeah last time I presented I gave a token i6z it was last year I presented bullsharks today I will I'm going to talk about SCH of bullsharks and I hope the name will explain himself during the presentation yeah let's start so this is a joint work with balati and zikun from upto slabs some backgrounds before I jump into it um this is at least at least my journey in the dark based consensus there other works but uh this are my journey like started in poy 2021 we

presented like Theory how we can make to take a dog and order it with zero zero over it completely just by looking at the dog then now at in narvel we demonstrate a system how we can build this duck very efficiently then bullshark we improved latency by taking advantage of the parture cio's Assumption and now the new work I'm going to talk about today is sh which improves this latency even f let's start with novel so just some a reminder the two um or not a reminder if you never heard about it's also fine like I'm not assuming anybody know nothing about it but this as I said novel is a system to build the dug and the two main like key points to take out of narvel is that

first that we made the observation that decoupling the data dissemination from the metadata metadata ordering is the key for performance meaning that if previously like data was like disseminated as part of the consensus protocol here we made the observation we can we can disseminate the data on the side provide some proof availabilities into the consensus and then the consensus ho has to deal with the metadata this allows this unlock a very high throughput and also allow like to scale out scale out architecture if you throw more machines and the other machines take care of the data dissemination all theing metadata is very cheap so this is like one key observation the second the second contribution of narel is actually how to take and really build this like very

efficient round based dog okay so once we have this dog we have these three protocols DG Rider task and bullshark you look at this round based dog and the the cool thing about all of them is that you can out of this structure you can com you can have like a total order with no with zero communication overhead like you everybody are just like there is a protocol there is an system to build the dog but each of the validators has a loc local view of this dog and completely locally the validator can look at this dog interpreted the Ed Ed edges and the nodes in a way in a in some way that like represent consensus logic and completely locally no no no overhead no no extra communication you just aler

everything so this is like very cool about Dougs and uh here come here comes the motivation for this work so this takes this is the this is a graph from the narvel paper we compare here like a narvel with a different implementation of Hot Stuff This is a latency fut graph so the vanilla hot stuff it they roughly about like 1800 2,000 transaction per second can support then if you if we implemented this idea of the coupling data dissemination from the cons consensus logic we improve the frut quite a lot but if but if when we use tasks like directly building the dug and ordering the duck directly we were able to actually achieve a very very much higher throughput and so this is very

nice because we want high throughput but if you look at the latencies the Hot Stuff latency was better so uh the task I mean if we want both of them right so frut okay good but what about latency and this was the motivation for the bullshark work if you see here it's kind of the same graph and this is the bullshark is going to be in in blue here compared to Tusk um we saved like quite a bit like 33% close to the Hot Stuff latency now almost there the goal in upos was to implement this bullshark and narvel we already currently have narvel we call it quum store this is our local implementation I mentioned it one time in the end again and when we started implementing bullshark we I mean realized that the latency is going to be works because

what we use we actually not use hot stuff in in upos we use joltin and and joltin reduced one round trip from hot stuff so increase reduces the latency um by 33% compared to hot stuff so then it's actually somewhere here on the graph so we we pay quite a lot in latency and it was we didn't want to accept this so we are started this research and thinking how can we improve it and this is the motivation for shw if I need to summar it in like one sentence so sh is the general framework to take any of these protocols and to add pipelining leader reputation and the ability to get rid of timeouts completely and I mean DG Rider and Tas synchron doesn't have timeouts but

bullsh is partial synchrony bullsh has timeouts so we're able to completely eliminate timeouts and um yeah and this is how like with these three two feat three three features we are able to improve the latency of bullshark by a lot um theoretically we could apply to any of them but we are interested in bullsharks so we have we we will have a sh of bull sharks I know I already talked about bullsharks previously last year but it was last I I wanton spend a lot of time about it just some overhead I can explain Shaw in a self-contained manner but just you know it's I'm going to spend 10 minutes just to give better intuition so otherwise it's going to be a little bit out of context so I spent some time to explain like roughly what we're doing in bullshark and then it

will give better intuition about like the sh paper so this is the dog it's round based meaning that it advances in rounds in every round we have at most one node per each validator and the important property one of the important properties is that each node refers to n minus F nodes in the previous round we're going to use it for quum intersection this is the this is the property another important property is that uh this duck can can grow completely asynchronously because all you need is in order to advance around you need to like in order to advance around here and to broadcast this node I need to receive I minus F noes from the previous Round And by the bft Assumption we have n minus f are always honest so I will eventually receive their nodes and

I will be able to publish my next node and this is how it's going to grow the Hest part the honest parties can always can always grow the dug even during a complete asynchrony so this is like one of the features I will also talk about it more when I will talk about eliminating timeouts so one another property of this um is non ubication this is part of how we implement the duck so we can think about it each intuitively you can get this property if you take each node and your library broadcast it then the Rel Li broadcast give you this property of non ubication one of the properties of Library broadcast that everybody are delivering the same node uh in practice that not this is a bit costly so this is not exactly what we are doing but we we can say you can have some sort of reli

efficient reliable broadcast implementation in terms of the obstruction how to think about it you can think about the library broadcast just to understand how we get this non accuration so what non accuration gives us is that we build the Daga synchronously and everybody every validate each validator has its own local view so this can be a local view validator one this can be a local local view validator four you see that one four already has this node one doesn't have this node because of the asynchronous manner of the network right this can happen but um but if they both like in this example have the node right no validator SEC the second valid validator to round two they both have the node the node has to be exactly the same similar everything is exactly the

same the same references the same metadata for transactions completely everything and then if you apply this logic you can you actually have uh the same causal history by causal history I mean all the nodes that can be reached from this node like by by by a puff right so the same causal history this is a critical property of the Doug and it simplifies a lot when you're reasoning about like the consensus logic of the Doug so when we when we come to we have this local view we want to aler everything that's that that's our goal we don't want to send any extra messages we don't want to look at it and all do it so the way we do it is this this is validator one local view we're going to interpret the Doug and we're going to take U the first round is going to be an

anchor round the second is going to be the votes round again enor votes enor votes and for every enor um for the synchronous version of bullshark which is the one I'm explaining here where we will have a predefined uh for every round for every sorry every every even round we will have a predefined Anor everybody a prior agree on this two uh in the randomness and dark Rider and the other and task you need to like elect it in retrospect not in this one this is simple you just upor agree and then uh the goal is going to be to just decide which Enos I'm going to be I'm going to aler which I'm going to skip and then the one that I and then after I order this I'm going to go one by one and order the causal history by the some

deterministic Rule and since uh there is no equivocation we will come up everybody will all validators will come up with the same order we say that a node in a voting round votes for the enor if there is a puff and in the commit rule that we have a direct commit rule the direct commit rule requires F plus1 votes to commit an enor so in this example validator one looks at this Doug this is the first ancle can I commit it can I directly commit it the answer is no I only have one vote and f+ one in this case require f is one f+ one is two I don't have enough votes to directly commit however I can commit A2 I have three votes I can commit right there the direct commit rule requires f+

one where is the subtle part the subtle part is that okay this is what I see this not see not I validator fall this is what it seees directly commit A1 now we remember the we can validators can see slightly different Dougs because of the asynchronous like manner of the network so validator one actually didn't commit A1 committed A2 and validator 4 committed a committed A1 because it so it show the it so the node that validator one didn't see so we need some mechanism to make sure that even though validator one didn't directly commit one he will be able to commit it indirectly yeah you need to order A1 before A2 and we are going to use Quorum intersection of course for this

so um we have f+1 rows required for direct commit and on the duck construction each node refers to n minus F nodes from the previous round so together what we get is that if if an anchor a is directly committed all future enors will will have a puff to at least one uh V for a I will illustrate it in a second and then all future enors will have a puff to a so here is an illustration uh validator for directly commit A1 remember from the previous example and then validator one didn't have this node but um when we will continue building this Doug since a every node including A2 has to refer to n minus F nodes in this example three so um it it has to

have an intersection with other this other this or this one of them it has to have an intersection so f+1 to commit and then three f n minus F in order to build the dug so there will be and there will be a puff between a A2 to A1 and we can of course apply the same logic going forward so this is the kind of main qualum intersection here on this graph construction and then uh and then we use we will use the opposite direction if there is no path from a prime to a the no honest validation directly committed a so here is the protocol in one slide what we're going to do we're going to this is our this is our local view of the dog and I'm I I think I'm running a bit fast here because I already gave

like this specific talk here so I'm assuming there is some knowledge but again like stop me if it doesn't make any sense to you okay um yeah so okay so we this is validate this is like one some local view of one of the validators A1 we cannot commit there is only one vot A2 we can A2 we cannot commit though we don't even see this is it like a round based thing here yeah fine fine okay I mean the DG goes there's only one validated whose block I care about in round one there're being committed is that is that right so sorry there's only one validator who whose block I care about in round one they're being committed is that right yes we we all try to this is the enco right we all try to commit this so there's one guy yeah yeah and it's predefined but

then after we commit this we're going to commit the all causal history together with it yeah okay so um A2 we don't go there's of course no zero votes right and then A3 finally we can directly commit we have enough votes now the the trick is what I'm going to do is that I need to check remember the previous example somebody might have Commit A2 somebody might have committed A1 right and the logic to check it is is exactly what we saw in the previous slide if if there is a puff between A3 to A2 then we need to commit it uh because it means uh somebody might have directly committed because we said if if there is no puff then then nobody directly committed it's okay it's okay in this case it's okay to skip and there is and as to A1 there is

actually a puth so we need to commit A1 before A3 because you know if we had this node and somebody else saw this node had had a direct link here he would committed it right and so if we have a puth it means that somebody could have committed it we need to order it before now it's also true that if we if we have a puff maybe nobody committed a one right this does never exist for anybody but this doesn't matter because everything is deterministic and all the causal history is the same so when all the only goal is to make sure everybody agre on the same total order so everybody will when when some other validators will see A3 he will also every it will also see a PA here because like the same cause history for

everybody from A3 so everybody will agree uh on the order okay and then and then once we do that we need to recursively apply the same logic for A1 going back in this example this is the first round so we don't need to do it and so this was like the main goal the the challenge how to decide which um enors to order which to skip so we decided to I mean the all validators agreed first a one then we skip A2 and then A3 and then we are going to go and deterministically order their causal history so in this example A1 doesn't have causal history is the first um so nothing but then for A3 we're going to go and order there by

some deterministic rule say we go like up down and aler them like here and we put them here um yeah and that's going to be that's going to be the entire bullshot protocol again I'm sorry I I feel it was a bit fast but I I assume there is some some knowledge about it I didn't want to bother you so but if we have any questions like I'm happy to happy to answer yeah te soind me so like the the green blocks is there a designated leader of that round to suggest that block or yes yes so this is the end call and we can say that the the validator that proposed this end call we can call him a little but if you there is it's not a lader in the classical sense in when we build a dog the ler

doesn't have any any specific rule it's just we we interpretate his node as the end call that's the only thing yeah um so is it true that like until A3 is committed to nobody knows total ordering of any other blocks yes yeah we will only order the we will only knew the order of this once we commit a three yeah yeah that's true yeah so when two blocks are committed in the same round which could happen right and in this case we CA order them but now suppose like in the causal ordering I first select the top block and then the bottom block but I see the bottom block being committed first and then at the top block so in my ledger output like how does this how does the Pres save like I

can you can you repeat the scenario because I mean remember every all the all the validators agree first on A1 and then first on A3 and when I come to enter see A3 causal history we also see the same causal history so we can apply the same deterministic rule we will we will depends on what the rule is we can decide to start from here or decide to start from here but this is like all agreed upon from before it's the same code we running right of how to determine the causal holder does it answer your question yeah okay what NZ was asking for round five the top white blocks um can they have a chance to be inserted and not here no not here it's a good question I in sh we

actually try to address some of these issues yeah what was can you repeat the question what about these two when are they going to be committed because they are not they cannot be committed as part of A3 because their history right they're on the same round they they need to wait for the future ankle to be committed yeah and and now it's if this is the current picture it's still possible that later A2 will be confirmed it it it might be but not as an anle um it might I mean it depends so here yeah here I didn't introduce the notion of weak links but we all um it's we can we can use weak links and then say that I I can I can refer to n minus F in the previous round but I can also refer and

we call it strong links the links that we use for this logic but we can also have like the notion of weak links and you can refer for example from here you can have a weak link here just to refer to this Orum nodes that nobody referred to so when in the future we will aler some endold there will this will be like part of the causal history and then we will able to aler it as a regular as a regular node not as an En anymore yeah so like if I if I'm just thinking about my own view yeah sort of this this chain is it true that like when new blocks get added to it it's always at the end or could they go in the middle too no there's no going in the middle no you only you only append uh there yeah so

just to summarize the bullshark it's it's simple um at least in my opinion there is there's there's no there's no view change no view synchronization uh you build the dog leader it's like it's it's leader in the sense that yes for your question we do know who is the validator who is supposed to propose the enor but when we build the Doug the the little doesn't me any like meaning in the system right it's not in any way we depend on him more than the others so it's little less in this aspect um I will not talk today about chain quality fairness G collection but we can all achieve it fairly easy on the on the duck construction Sasha this is this is probably one of the things you're going to skip but one of the things I I feel like in dad consensus talks people never

talk about is like how are transactions coordinated across different blocks that are being proposed simultaneously so yeah how would you suggest thinking about that that's that's a good question I think you refer to the question well we can every every validator propos is on block and we can just duplicate all the transaction this is your this is your question right so we don't tackle it on the on the consensus level uh it's I don't know how maybe if you have some ideas like let's do it but I I really don't know how and on we try to tackle it on the upper level so in upto specifically we have the notion of pfns and PF and V and like this this nobody we don't expose the the IP of the validators we have this protection so we

we try to we try to we try to um we try to solve it there so balance it through the through the public full nodes and of course in the worst case somebody can attack us but uh I mean we try to mitigate it on the system level that algorithmically I don't know what can be done like it's an open question um is also true that if I'm an anchor I can control the total ordering of blocks before me based on like who I'm voting on like we're referring to before um yes it's true because when you you know that going to be the end call and uh you can you can choose you can wait a little bit and say I don't want to refer to this guy I'm going to refer

to this guy you can do that yeah so I showed this slide again but I want to switch back to sh so I just remind you the motivation this was bullshark and we want to we want to we want to reduce the latency even more so this was the motivation we want to make it like H this is hot stuff we want to make it better than hot stuff somewhere close to jolting as much as possible because internally this was the consensus we are using we don't want to increase the latency you want to incase keep it at least keep it the same while improving the the throughput so let's talk about shw let's analyze the latency of of the dug let's start with that so for the Enos the latency is going to be two rounds I propose the the Eno in this round and in the good case it's going to

be committed uh directly committed here so we have two rounds for the for the enle commit if you think about this V the the nodes in the votes in the voting grounds they will require three because the anchor is going to link to them and then they will be committed here but if you think about to your question if you think about the the nodes in the the nodes in the enor round which are not the enor they will actually will need four rounds they because they will only be olded here with this with this anchor right so this is one source of like latency penalty that we're paying and the solution that Shaw is going to Pro provide is something that we call pipelining it's not really pipelining it's like it gives an effect

of pipeline it's not really pipelining in a way we like usually think about it and what I what I have what I mean is that we will have an enor in every round so there's no there no four in this picture right it's you're either an enor in you order in two rounds or you're going to be ordered in three rounds that's uh that's that's the first contribution on sh and I will explain the second one the second cause of latency is that in the worst case um you don't always directly commit of enor of course you would like to like keep directly committing them but sometimes the enor might be the validator which is the the leader the validator that proposed the anend call might be slow he doesn't get enough support not get

enough votes and you don't commit you have to you you have to you will you will aler it eventually but only after you get here right so uh in this case so you pay all this latency if you have a crash validators for example like here you have to skip it you cannot aler it so you you pay all these are sources of latency penalty and and and sha will Pro is a framework to provide leader reputation mechanism so the idea of leader reputation is that I can I can look at the past I can estimate who are the strong leaders and I can uh I can make sure that I exclude all the rest and the leaders that I'm going to choose in then in the future are going to be from this strong leaders so it's like um increase

the probability of the Enos to be actually directly committed so the idea the idea of leader reputation itself is like is not novel here we we're actually using it today this is like even from the DM days we were using it but it was a bit different because there if you think hot stuff jolty and the leader based protocols um you can use this like a leader mutation mechanism but it's best effort it's of like from safety point of view it's it's perfectly fine if I think that Lara is the leader but somebody else think that team is the leader we will not reach consensus in in the next round none of you will be able to get enough endorsement but nothing bad will like in terms of safety happen because next lad next round we will try again eventually we Converge on the

leader everything is going to be fine here imagine like I think that A1 and A3 are the Endor and somebody thinks that this and these are the enor like complete mess right we are just completely like going to all the complete different different things so we have to we have to agree on the leaders um in order to be able um to provide safety so the challenge here is a bit it's a bit more challenging here on the Doug uh let's see how we do it so one key property of bullshark um also true for dug Rider and tasks but uh like let's focus on bullshark remember like 5 minutes ago we saw this slide we have the we have the we have the Enos and the first goal is to decide which to order and which to skip we order this right

and as part of the safety of the block of the bullshark protocol it has to be guaranteed that we agree on the same enors and in particular we are going to agree on the first uh Anor that we are going to order right I one could decide it here one could decide it here another one could go like while in the far in the future couldn't commit any of it directly but eventually there will be some path and they will decide to order this first if if this wasn't true the entire bullar safety would be wrong so we can rely on this on this property like um we will agree on the first uh older en call and this this is like the key observation and I'm if we understand this the rest of the result is going to

be very easy because we are like just going to rely on this so yeah so this was the key property and the key observation is that we can go back and reinterpret the dog deterministically and what I mean by that if we look at this example like um if I have this local view of the dog I need to go to the Future in order to understand that this is the first AR I need to order but as long as we all like deterministically agree on this this point we can go back now in time and start re interpreting this uh the dug the dug again from here maybe in some different protocol maybe in some different way like Doug is a full information protocol this is the observation we can do whatever we think whatever we want as long as it deterministic and as long as we have

these points of consensus in order to agree to start something new that's a bit vague what I'm saying but now now I I hope it's going to become clear now so this is the pipeline algorithm a priori we have these like m from rounds to leaders H remember the leader is the is the validators is supposed to propose the anchor so the with the way it's going to work is that first we're going to start with a simple bullshark protocol okay we have the enor in the first round the enor in the third round the fifth round every other round we're going to have the Anor and we're going to and ignore these for now we're not going to use them for this uh um for for this uh for the first instance of bullshark so we're going to just run bullshark okay and at some point we're

all going to agree that this is the first ankle to be ordered right this is just an example it could be this it could be this right but the important thing is that all validators agree that this is the first um en call the bullar protocol this instance of the bullar protocol is aling doesn't matter how far in the dug I had to go in my local dug in order to reach this decision we all reach the same thing and now we like we say okay so what we're going to do now now yeah we're going to we're going to go back in the Doug and start a completely new instance of bullshark from stratch blackbox like forget about the everything you you knew previously forget about it delete just remember that you this is the end you older now

we are going to run a new bullshark instance from here here going forward right and this is completely safe because we we agreed on this point so our local code says okay we agree on this point let's start we let's start again from the next round this is what we're going to do so now the end C like remember the end C we somewhere here now the Enos are here these are the ls now we are going to Tweet these uh these nodes as the Enos and we're going to run another bullshark instance again in this example we Aller this one because I want to show you the the good puff right we're going to holder like an an enor in every round but it could be this and if it was this H the first older enor older then we would stall the next instance

from here but in this example we stall the next instance from here and this this is how U this is how it it goes cool so this is pipelining and what what we achieve is now that before we had an ankle like every second round now we have enor every every round and um it's it's a it's a complete free optimization on top of bullshark we didn't do anything we just it's just a more clever rule of how to aler the how to aler the nodes so now I think the sh of bull sharks will make more sense now why why the name because what we have here is actually a Shaw of bullshark swimming together like I didn't know the meaning of sh but I guess most of you know it's a group of fishes all sharks swimming

together so uh and I like this illustration because it's like sharks running in a real real Rel race passing an anchor from each for like for one to another right so uh this is like I think a cute picture yeah so question on the sort of this like pipelining of bull shark so in the kind of first case if you uh like in the normal case suppose bull shark was committing to Anchor in round one and round three can it happen when you pipeline it you're not doing round one and round four instead because you're doing the two4 interpretation now so it actually ends up being slower than normal bull shark so in like standard bull shark it was like one and three but now when

you're reinterpreting two four six you say I can't commit to two out to Comm into four I think I understand your question you say in the original let me know if this was the question in the original bull Shar let's say we could commit this and then we could commit this right but now with this new tricks we commit this and then we cannot commit this and we will commit this this is your question yeah it's it's possible and uh and but if you think about it what is actually mean it means that the adversary like is very powerful he can like play it in a way that that is too powerful if you can do that he could also in the original bullshark it to make sure you cannot commit This and like continue not letting you commit like yeah for some for I can think of duck structures in

which what you say happening but whether this duck structure actually make sense in the real world is it like something that the adversity can can actually make happen uh I'm not sure other than that it's just like a probalistic uh argument it can go like yeah go both ways yeah now it's a good question we thought about it and I hope I satisfied like a satisfying answer yeah um okay pipelining not pipelining leader reputation so we're going to use the same trick completely this is like another nice thing um the way we actually worked on it is that first I thought pipelining is impossible then we thought about leader reputation how to do it because practically we had to do

it like we have really a practical system this is actually very important for us today because we have little reputation today so we said we cannot deploy bullar without Le reputation and doesn't make sense so we came up with this solution and then like then we realized oh this same thing what for pipelining whether like two weeks before we were trying to solve pipelining and decided it's impossible so that's kind of was a nice like for thinking thought process for us okay so little reputation well same we have this uh we have this mapping between laders to rounds to leaders we are running an instance of bullshark we decide this is going to be the first enor to order again an agreement point before all between all validators we're going to study the ca

history of this validator apply some tics H to understand who are the strong validators who are the less strong validators simple simple like Tic you can think of is like how many nodes did you contribute or how many times in this causal history you are supposed to provide an enor but you couldn't like and some some things like this and then based on this information we are going to deterministically uh assigned a new leaders going forward so before we had some leaders and we went far into the future to determine that this is going to be the F the first ankle to older and then we are going to completely change but deterministically cross everybody the mapping between leaders rounds to

leaders and we're going to try again now to interpretate the dog with completely different Enos and it's completely safe so I yeah I find it kind of cool and uh yes so we changed the mapping we going to on another bullar conent bullshark instance now this is if we did only little reputation but the nice thing is that we can combine it with pipelining together right we can do both we older an enor we reshuffle the lers the mapping of the lers and we and we actually start the next instance from round two instead of round three and we get pipelining and L reputation with the same trick so can you tie these optimizations kind of back to the formal guarantees you might state for such a protocol so like the pipelining can you

say the latency improves by a factor of two like in all cases or no the pipelining reduce so it depends how much you pay for every uh for every broadcast here like we we do one and a half round trips but you could also do it in one round trip if you had like more but you pay more communication so depends of your implementation of the broadcast but uh um and but it's it's it saves you remember this yeah what it gives you is exactly that here supposed to be four and now that's three in every in every other round uh in every other round you you switch the fall to three so this stays the same the latency for this node stayed the same but the latency of this node improves by

25% and and so then the reput like how would you phrase the from the reputation that's going to give you a Improvement where the reputation gives you a very big Improvement um under faults if they're actually faults it gives you a very good Improvement um and yeah I'm actually going to talk about it right now like uh yeah because it it gives you even more that uh yes so I I discussed now the algorithmic contribution of SH now I'm going to talk about the system optimization and the leader reputation played an important role here I'm going to talk about it what we what we achieve here is that we completely eliminate the not completely let's say from every like a listenable scenario we eliminate the

use of timeouts and U I think that's that's interesting because first timeouts are very painful like if any of you ever implemented a distributed system like you need to think about this time outs too long too short like how you monitor them like uh it's really it's really painful and if you think about leader based consensus the timeouts are inherent like you cannot get rid of timeouts if you have a little if you have like a single point of failure yeah the the reason you cannot get rid of timeouts is that um at some point in the system you are going to wait for a message from the leader and this is the only thing that's going to twigger you moving forward you're just waiting for a message from the leader if you don't have anything else that can

trigger you do something and the leader is actually crashed you are going to just stall forever there is nothing else that can let's say okay you know let's try something else like you can just wait forever right and the timeout gives you that like if you timeout the lader it like you see oh timeout let's do something else right without it you can't and this is and and the reason why it's so inherent in like asynchron and partial synchron is that during during like synchronous synchronous asynchronous periods you have this validators they they wait for the ler so they they then they wait for some time right and they don't know whether the L crashed or simple Thea the lader is like super slow and like if they just wait another millisecond They will receive

the message and like there is just it's it's an it's an inherent problem possibility it's impossible to distinguish and this is like most of the difficulty in ason your system comes from this like uh from this point right you cannot distinguish between crashed and slow uh party in in in the system so this means that leader based protocol that works in partial synchron must use timeouts okay and what's the problem with timeouts so if you have them too short and the leader is actually good but the validators are just always impatient and move forward and time out the lader the before the next before faster than the network delay then we are going to keep like keep time outing and VI change the leader has never never

reach progress right so we cannot have two short timeouts because but on the other hand if your timeouts are tooo too um um conservative like you pick a long timeout and the leader actually crashed you will need to pay this entire latency as a penalty before you can do anything else it's just and the typical timeout is like 1 second one and a half second I think today we use one and a half second in the in jolon like before we will move to the Doug and uh yeah like think about it somebody crashed one and a half second system doesn't do anything anything just St right bad yeah shw in Shaw we we have a way to get rid of timeouts like almost completely and and what we are leveraging is two things

first is the duck construction and second is little reputation so and and the the cool thing about the the duck construction is that it advances at network speed and completely asynchronously right so remember I told you before if we have a single point like a leader and we wait for a message we just wait for the message there is nothing else that can trigger any other Behavior so the D is kind of give you this be this this clock this triggering like you keep advancing around and every time and you advance around completely asynchronously no time as you don't need nothing and this is my intuition so I share it with you and every time you you advance around that's that's an event that now you can rethink what you are doing right and this is something that wakes you up right and like am I do like

should I do anything else and uh so the Ducks give you this like kind of clock and um we we'll just keep building the dark regard this of this guy is being slow this is actually crashed and the dog is always always network speed we don't wait we just build the dog and if we can directly all the r we'll try this we'll try this and we just no never never wait okay so then let's analysis what is actually going on on the duck construction so we have three cases the first is a fast leader as in this example when I say fast it's relative to the others it doesn't mean that the network in synchron is any way the network completely asynchronous but it's just faster than the other meaning that most of them is going to actually receive this node like at the

beginning like and then they will point to it and they vote for it right so if I'm a fast validator I will get enough support never it doesn't matter the system as a synchronous synchronous eventually in network speed I will get enough support and be directly committed this is like a very nice property of this duck construction if you compare it to the leader based protocol joltin hot stuff and PBF others and you think about this optimistic responsive property they only guarante that it's not enough for the leader to be fast there they they have the they need the system to be synchronous and the reason is that even if the leader is the fastest and everything is good the leader still needs to collect votes right if the votes are not coming in the timely manner everybody else will just um will

just view change right time out and view change so this is a cool property if we have a fast leader we can provide network speed both during synchrony and during asynchrony for for a faulty leader there that's even better this is perfect we wait zero time we just don't care we continue building the dug right like this is what we do like we just don't care like if it actually fault a fault a faulty validator uh cost us zero in terms I mean not it's not really zero because it's much better to have a good a good enor here and committed directly but if you compare it to the 1 and a half second latency that you pay just by waiting before they continue the protocol we have nothing of that so we saved here 1 and a half second

U if a leader is faulty is faulty I mean what can you do right but at least we don't pay this one and a half seconds of waiting to agree on the fact that the leader is faulty we just move forward okay so this is actually this is also very good again if you compare to optimistic responsiveness faulty leader that's where you have like a proof of the the the faulty in some way no you don't need you don't need the proof right the the dog you just keep building it in network speed isn't committed yeah yeah you just eventually as in this example you will not aler it so you do pay some latency penalty but this is an algorithmic latency penalty not uh no timeout that actually stole your progress right in the okay the only the only question that we need to ask which is like question

about is what about slow leaders slow leader is a good leader but it's slower than others so he doesn't get enough votes right this wasn't fast everybody voted for him this guy is slow so if we had a timeout it could be actually good because then they maybe if this guy would just wait like five more milliseconds if would receive this node and we'll be able to vote for it right and then we'll be able to directly commit it and there is no need to wait like another two more rounds on the dug in order to commit the next anchor so um then then slow leaders it's like question about it's a trade-off whether you wait or not wait in the case in case of slow leader here the leader reputation come comes into play because what will happen is that if you're slow then you will not be able to uh like

make sure that your anchors are committed the little reputation mechanism will exclude you um this is how it works you didn't commit you you you w fast enough the little reputation will exclude you so um it will actually exclude only also the faulty nodes which is also good but uh even the slow nodes so little reputation will make sure over time that only the faster um validators will H will contribute uh will become leaders and like and Enos and we will be able to aler one interesting question that you might ask so I ask it for you what what do we do is incentives right because they want to be fair like if the validator is slow uh we don't want to punish him like and if we like let's say our Revol mechanism like pay pay leaders

like as today today our Revol mechanism pays leaders right and and here like just because I slow you don't and and slow is not absolute it's slow slow relative to the other so you're not going to pay my rewards and the answer to this question uh will be is that with the dog we don't need to rward based on the leaders there's no notion of real leers in ter leaders of um when we build the Doug it's enough just that you contribute to the node and that's already like good enough but um the the the the exact um Revol mechanism that we're going to use is still to be done um so actually if like any of you is like you are the expert here if any of you is is interesting to review it and to help us uh we'll be happy

um but this is like a this is like a flavor I thought this is like a natural question and already like a I gave you some like what are we thinking yeah this is just a summary we defined like a proper property we call it prevent responsiveness we compare it to optimistic responsiveness so if you if you think but what I explained before right during synchrony and asynchrony fast and faulty leaders we get network speed uh network speed progress where in with optimistic responsiveness you only get network speed progress fast leader and synchrony right as synchrony no guarantee at all and faulty leader even with synchrony you have to pay the timeout penalty in case of slow leader in both cases for us um without the leader reputation we need to pay like

two round penalty because we otherwise maybe we could have like directly commit if we had time out and now we need to wait to the to commit the next end call but here is the Hope is that the lead with lead reputation it will be very rare so I have to say something about flp here because I this is a deterministic protocol and how come like we don't use timeouts right where is the FP comes into play here and uh of course it comes so in theory under a very powerful adversary which I will show here we cannot avoid timeouts with a deterministic protocol because what can happen is that imagine an adversary that just controls all the network right just none of the ankors will get enough votes like every time there is an ankor there

is a little oh suddenly the adversary is so strong so it will eclipse in nobody votes right and doesn't matter you have a little reputation that's very good in practice but the adversary here is just you know all power powerful doesn't care every time it's a different no like so so in in theory this can happen yes and in order to um to to fight this and like to be on the safe side and to provide these guarantees that we like and provide liveness what we will do is very simple like um so in sh um what we do is after X X is a parameter 5 10 100 1,000 whatever your favorite number is well validator was just fall back to use timeouts and then like of course we have the theoretical liveness in partial right but in practice under all

reasonable adversarial scenarios they will never fall back to timeouts like you will you will Aller much much faster than than this adversary will be able like to tweak everything especially with like wi reputation so I I think this is very cool because we can actually uh run a partial synchronal system without the we will have timeout somewhere in the background but they will not impact anything so here is here is the number here are the numbers the evaluation first we wanted to compare all this like system improvements the timeout stuff so we has the basik bullshark is no timeouts vanilla bullshark is has two timeouts actually one timeout is on the on the leader round and another Timeout on the vote round the reason we had to

have a Timeout on the vote round is because the full bullshark protocol um the quorums there were 2 plus one uh because we had to support the fallback I didn't talk about it at all but you know just for the recording if somebody like ask this question and uh so we had to have two timeouts there but for the partial synchronous version we don't need this timeout so this is why we have the green line just just the vote just the timeout just the timer for the for the leader in in the vote uh round not for the other round sorry in the in the anchor round not for the other round so and these are the results like obviously um yeah when we have failures um Baseline bushar without timeouts is much better because we don't pay this like

long penalty every time every a failure when you when and when we check the no failure case um yeah this is latency this is the number of validators this is number of failures sorry I had to say it before but in the in the non-f failure case you see that vanilla buar is worse but the green and the the pink it's actually um there's a trade-off this is this is the thing about slow uh nodes slow slow leader sometimes it's good to have a timeout just to wait for them a little bit and we can commit them so it's not a clear with without little reputation there is no clear win here like what is better but uh for for our next graphs we are going to consider Baseline bullsh the pink one and compare everything

against uh a bullsh without timeouts because we want to evaluate the algorithmic um results and also because the pink is not strictly better but better right better strictly better here and the same here so we can we can use the pink okay so this is H throughput uh and latency uh Gra so this is Jolan and this is the the different versions of sha Baseline bullshark um the green is like the full Shaw um blue is little reput just little reputation and the pink is just pipelining and you see that throughput we achieved like 120 around 120 transaction per ,000 transaction per second uh we didn't try to optimize this

too much this result is about latency I guess we can push it like if we did some system optimization we can push it further um but uh interesting is just jolen um this is jolen not the vanilla jolen this is jolen when we decouple data dissemination from uh from from consensus we get like around 55 and and for latency you see this by Baseline bullsh is the pink and then both the leader reputation and the pipeline they both contribute to latency together show the green one is actually better than everything like they can it means that they separately contribute and they together is like even better and if you compare to jolon here so you see we started from vanilla bullshark we started even higher because we had

timeouts but this is like no timeouts vanilla bullshark and we are almost almost like closed the gap which was the goal of this work to close the gap with joltin um the thing that we are very nice here in this graph to Jolan the thing that we don't measure is that when we decouple data dissemination from the transaction ordering there is some more latency to connect this two component and we gave this latency for free to jolon so we don't measure it whether for for we don't need this latency um yeah so if we so the Gap is probably even even less if if there is any Gap okay so this was throughput and latency in the failure three case and now um the last graph is latency in the fail case question oh sorry yeah yeah so like um

what kind of a validator are we assuming here like is this a commodity laptop like what is the validator oh this these are very strong uh AWS machines y okay yeah go go replicated strong AWS machine three different regions um y I don't remember the specification by heart but can check it yeah yeah yeah okay so um and also it's just the consensus all this graph is just consensus there is no execution here right this is just consensus just to be to be clear uh okay so so this is the latency in the failure case and and uh no jolter on this graph because when

there are failur like nothing was reliable there because we actually wanted to try it with like a lot of fail so jolon was like completely useless and uh yeah and you can see that obviously Shaw with little with little reputation like is much better that's kind of kind of obvious um because it it avoid it like exclude the faulty leaders and LS without them um okay so bottom line for for the numbers for short so frut 12 20K on our consensus only upos implementation um yeah and I said we can we could we can we could push this number higher we just it wasn't the focus but compared to jolting on top of nwell we get 2x Improvement H latency

again consensus only we get subsec latency compared to vanilla bullshark is it's a 40% Improvement without failures and with failures up to up to eight 80% um and then H compared to joltin when we have high load we get much better latency and this is because when high when we have high load we cannot support the flut and then the flut start impact latency right so uh obviously if you have high load you the more fut you can support the your latency is lower otherwise you just need to wait a long time before you even can in into the system right and compareable under low under low load and yeah this is just the slide I I like to show and uh papers papers are online and I always have to I

like to say good stuff about the centralized F the ti blog and yeah we also have um a Blog there about like B Dog where bft and if you you can go there to we like the high level and for the recording this is my email and if any like any questions anything just reach out so what's deployed like right now what's like running on mainnet right now yeah so what's running right now on mainnet this for the consensus we're still on Jolan and we have our own implementation of narvel which we called Quorum store and the the way to work warm store is a very simple component I mean nothing is simple when you actually build it but I mean conceptually it's simple it's the data data you disseminate each validator or like in

parallel disseminate the data and get enough signatures back in return holds the proof of availability each signature each signature promises that if I sign to you I promise you I'm going to hold this data process this data in my local like uh database storage until the expiration time time and then the validator takes this proof push it to consensus here is this extra latency I was talking about and then joltin will order this proofs and then before execution we're going to look at this proof one by one hopefully we will have all the data locally because in the D case we just you know we determinate data to everybody we should have it otherwise we look at the proof we look who signed it and we're going to we go we'll go fetch it and then execute and uh this is this is what we currently

have is the plan is to well in the final processes of uh yeah of implementing Sha but the way it works you have to implement then you have to test it then you have to test it again then you have to test it again then to deployed and you have to test it again so it will take some time before we can actually launch it on mainnet but uh like we're on track yeah hopefully soon then later right [Applause] thanks