DAG Meets BFT: The Next Generation of BFT Consensus with Alexander Spiegelman | a16z crypto research

Transcript

welcome everyone to the restart of the a16z research seminar series um very happy for our first talk this fall to introduce Sasha spiegelman uh at Aptos uh who I think will be enlightening us on recent advances in dag based consensus so Sasha all yours all right so yeah thank you for the introduction and please feel free to stalk me at any point for questions I think it's much better if we do the questions through the presentation and not in the end I don't want to miss it I don't want to lose anybody Okay cool so I will talk today about dogs and how they meet well they meet bfts and how we can use them to solve like a consensus very

efficiently before I will jump into that I just thought just a single slide of like how a single child architecture look likes like usually we have these I think three main components that that each blockchain has which is a consensus execution and storage we have some more but these are the three main the three main parts and if we have a pipeline architecture for example like the one we have an optos then the your overall system performance will be as good as the your weakest link so in some other work we showed that we can execute once 160k transaction per second where by block SDM by the way if

you have ideas from the next seminars you can invite Wati to give a talk let's say I think he will be interested and magically we got the same exact number 160 ktps with novel and task when we implemented our consensus so there must be some law of physics here and with this like magic number and okay and then today I'm gonna focus on consensus and yeah and show you the duck based Outlet based approach so this is a joint walk with jobs um jobs it nearly did La Paris or dead in Alberto and we were all on in Aptos it was all started in Novi research I think George Lefteris Alberta and myself

our interns and the external collaboration with did and yeah this this summarizes our our walk we did in the last two years which published in three free venues free conferences so we started with all you need is Doug where we showed the foundations how we can use a dog in order to implement an Optimum and asynchronous atomic broadcast on top of the dog with zero overhead of communication we achieved optimal resilience in terms of complexity complexity it is post Quantum safe and it's other one latency this was the theory of this approach then in then novel and task we which was published in

US is this year we actually show how to build this duck very very efficiently and bullshock is is our latest latest protocol in which we a which has the same property as all you need is Doug in asynchrony but it also has a fast path and that reduces the latency in the common case and we also show how to practically garbage collect the achieve fairness and chain quality and it's important to note I think that this this approach is currently implemented in several blockchains um for like for example Aptos we are implementing it cello I think Mr already integrated it into Dell code base and also Somalia okay so

and what is a dog what I mean what what do I mean when I say a dog what is a dog for me so we assume a round-based dug which was first introduced by aleph in aft 19 and think of it as um it's a structure of that so we have rounds and we have in each round has as at most nodes um at most one node validator and and an important topic here that is each node and refers to n minus F nodes from the previous folder from the previous round and and I I will explain in this talk how we build the duck but first I want

to introduce what what is the dag how what do I mean when I say a dog so this is the duck we are considering and and each node each node also also carries the information of the transaction transaction information to one order so it's very symmetric protocol every validator just twice to add the node in the dug this node has either of the transaction or some metadata information about these transactions and it needs to refer us to n minus F nodes in the previous round and this is how and this is this is the dive very simple and now the our work we can divide our work into two first novel is how we how we how we build this dark very efficiently okay so this is a in a

strong and strong and way to build a dog is just to use reliable broadcast so I I have my node I broadcast it I include my transactions there then I let's say in round one this is what I do then I wait for n minus f um other value to deliver n minus F nodes by other validators and then I'm ready to move to the next round I prepare a new I prepare a new node I refer to this with a I refer to this and minus F nodes from the previous round I add my information about the new transactions and I broadcast this and this is how it works this is like a storeman solution um but I'm gonna I'm gonna talk a little bit about now and how we do it but this is just to give you intuition what what the dog is

Okay so so this was novel this is like half part of the job of the walk the second part is the protocols that we run on top of now there and we we started with dark Rider then we have tusk which is actually a practical implementation of dark Rider and the latest is bullshock and all these protocols they text they take the Dag um yeah I just want to make sure like your discussion around sort of the straw man reliable broadcast I'm just trying to connect that to like the picture on the slide so should I think about like every single validator is like making a block proposal and a round and everybody's voting on everything or how do I connect those two yeah sure so there's no vote

there's no vote processing here at all so I am I'm a validator I just prepare my node and at the library broadcast it and once you deliver it you just add it to your dad to your local view of the dog that's all think about it like with a reliable broadcast is is to guarantee non-equivocation and to guarantee that everybody will eventually receive all the nodes but they simply I I I I can simply say like I send the Doug I send the note to everybody and everybody get the node and add it to their local local view of the dog that's that's all okay yeah okay so this this protocol is done by the task bullshock we have the dog each one of us has a local view of the dog it can be slightly different from each other because of the asynchronous nature of how we build the

dug and because some of us might deliver a node While others may still don't deliver this node right everything is like asynchronous and then we the magic here is that we we look at this that we look at this dug and the duck will write causal older but it doesn't provide total loader but we look at it and without sending any extra messages no extra communication we can just totally all the all the node of the dog and the and and have all the validators will we we will achieve the same total although without any communication just by looking at the dug what we're basically do in this approach if you think about it from a high level we have the problem of solving consensus and we reduce it into into two problems so first we abstract away all communication all the

system aspect everything into just building this dug as a efficiently as possible which is a which is which is like a well-defined thing that you want to build and it is much easier than build the full consensus and then after we have this then we run some local algorithm just to order these nodes of the dug and get the full consensus that we want and yeah and today I want to focus on on bullshock I'm going to focus on bullshock today and bullshock has bullshock has like I said before bullshock has all the properties of Doug Ryder but it also had a fast path to reduce latency in the common case in the case that uh in this in the synchronous

periods so this is the full bull shark but we at some point this and this is also what is published in ccs and but at some point we realized that uh that might be very interesting and people might be interesting in just the simple version of the partial synchronous version of bull shark without the complexity of the fallback and the asynchroni so we decided to to to to to to to to provide a standalone protocol of just the partial synchronous version of bull shark and this is what I'm gonna present today just uh the the simple the simple version but maybe the most practical one so so in the step where you go from the dag to the total order uh yeah so I'm wondering how I should think about that when like different

nodes have slightly you know when some of the blocks have been received by some but not all nodes is it like different nodes are going to apply this local thing and it's guaranteed to be like a prefix one is guaranteed to be a prefix of the other or just like a subsequence yeah exactly one is guaranteed to be a prefix of the other and one I did once I deliver more nodes I will I will like increase my prefix but always the prefixes will be always like a prefixes of each other yeah yeah this makes sense I'm curious about what the Practical implications of the complexity associated with asynchrony versus partial synchrony are in this case are there uh effects on latency or others that

make the partial synchrony more appealing it just no it's it's the same it just depends it's just the in order to grasp the logic of how we interpret the dog it's a the the fallback doesn't fall back adds a lot of complexity but in terms of practical implementation it's the same it's a we build the dog exactly in the same way it's just how we look at the dog and what we I I yeah I've explained the passions in Conyers version and it's pretty simple but in order to add the fallback is just a little bit more complex but once you if you understand it if you're accountable with it you can implement it and you will get the same the same performance during during syncuni and you will also have the asiconius fallback yeah

thank you and just I think I think so far everybody who implemented it were a bit scared of the details of the fallback and uh but yeah we're inaptos we are going to do the the football shock that's that's the plan um okay so yeah let me actually describe how how we do it how we how we all do the dog so as I said before um each of the validators here is an example right each of the we have different validators they might have slightly different views of that hug so but the important property here which we which we get from live a broadcast and we also get from our novel implementation is the non-equivocation what it means that it's it's fine some

some of the validators like in existence in this example validated fall might deliver a node the validator one haven't delivered yet okay it will it will deliver it in the future but not yet however if they both if they both deliver the same node the non-occupation guarantee that they deliver exactly the nodes are exactly the same it means same transaction same information about transactions same links to previous to previous to nodes in the previous rounds and if we apply this logic recursively so the nodes they refer to are also the same but the same non communication property so when what we get is that if we deliver the same nodes then the entire causal history of this nodes in

both local views of the duck is is is is is is the same is exactly the same and this is an important property because we are going to imply deterministic rules to order the dog so the fact that we see the same the same the same causal histories will just imply that we're gonna because the rule is they will be deterministic that we will alter everything in the same order okay so so the way we are interpreting the dad is is the following each of the validators again has its local View and then we have uh we divide the rounds into odd and even and in this example I start I I count from one so that's not from zero so so in every in every odd

round we will have a predefine end call now end call you can think about it as a leader I just prefer the ankle name because this they don't really do anything they don't send messages nothing you just it's just the node in the dark so I think Encore is a better name but um it's the same same idea so each each old and around in the dark will have a predefined end call and the nodes in the in the in even rounds that these are the votes and and the goal is here like first I want to decide which which encodes I'm gonna I'm gonna commit and then hopefully not like I every all the validators will commit to the same

nodes this is the goal how to commit this so so how to commit the same encodes and then I'm gonna and we're just gonna go one by one these committed end calls and apply some deterministical to causally or to order the code to totally although the causal histories of these nodes so this is what this is like this is what we're gonna do and this is how it works so the commit rule is very simple we commit an Emco if it has f plus one votes so in this example we cannot commit MCO A1 because we have only one vote remember a vote is an is a node that have a uh have a link to the encode okay however A2 the the second encode is committed because we have three votes

and three is bigger than f plus one and in this example n is four and F is one so we can commit A2 so the commit rule is very simple now now again each validator has a slightly different view of the dog right so it's possible that even though validator one never not yet delivered the node in round two from validator 4 validator fall already delivered this node so validator force is two volts on A1 and and therefore commit to day one so when when we go back to validator one for to his logic he needs to we need to make sure that that he will all the A1 before A2 because this is what we want

we want all the validators to all all the encodes in the same order okay so this is the goal and of course what we're gonna use in column is column intersection because this is this is like the main tweak in distributed computing especially in consensus right so of course for a mental section and uh and here is in here what in here it here is how it works so yes so I didn't totally follow the right half of it so why why does validator 4 commit A1 because you can see that validated fall has two votes on A1 right the the node in of validator fall and then all the validator in one two

gotcha that's the f plus one not the N minus F gotcha okay that's the f plus one yes exactly yes so okay yeah so that's that's exactly it the f plus one so the vote is f plus one and in order to advance round we need n minus F so we'll have column intersection between this f plus one to commit and NF and f plus and N minus F to advance okay so with this exact exactly with these two properties what we get is that if an encode some MCO a say a committed is committed by some validator then all future M codes will have a path to at least one vote for a I will in a second demonstrate it with an example that but this is what we would get and and and

and as a result all future encodes will have a path to encode a so here is how it looks in an illustration so A1 was committed and now A2 it it needs to fail to n minus F in this example three nodes right this is how we advance and build the dug so in this example no matter which of the nodes it will it will refer to either idle the one from validate or four or the one for validator two it will refer to a vote to A1 and thus a there will be a path between A2 to A1 all right this is exactly the column intersection f plus one to commit and minus F to advance that's the trick here and and as a result we get this colorway

that that the opposite if there is no path from some future Uncle a prime to a then the no honest validator for me today and uh well just one second in this node I I showed you an example from A1 to A2 but you can imagine that the same applies for any future encode saying the same exact the same column into section okay so this is the colorway and now with this color already I am ready to present you the full bullshock protocol on one slide so so this is how it works this is a local view of some validators say validator one so and now I I'm validator one sees the dog and try and now he

wants to totally all the all the all the all the vertex all the nodes so it starts from MCO one can you commit and call one no because there is only one vote one and f plus one in this case is two so you cannot commit and kill one and kill two it doesn't it has zero zero volts to MK2 it doesn't have it doesn't even have mco2 in his local view of the dug so he cannot commit nk2 however encode 3 can commit oh yeah and it can commit and Country three votes more than f plus one you can commit encode three now what now what we need to do um by the by we apply the code away from before what we're doing we simply check whether there is a path between A3 to A2

in this case there is no path so by the colorway no none of the validators committed A2 so it's safe it's safe to skip A2 we are not gonna hold the way too however there is a path between A3 to A1 which means that some one of the validators might have committed A1 so to be safe we decide to all do A1 before A3 and and now after we do this um in this example round one is the first round but imagine it was some around it was there was some rounds before so we need to conclusively apply the same logic and and and try to see if there is a path between A1 to a0 and then to a minus one until we reach an encode that we already previously although in the previous prefix that we all do

so so um and and the intuition here is remember I told you that if if we all deliver A3 and code 3 that all the Casual history we all agree on the Casual history okay we will because of the non-equivocation so if when we will go and apply this logic that I currently apply to in by validator one all the validators will apply exactly the same deterministic although so they will agree on skipping A2 and they will agree to all the A1 before A3 so it doesn't actually matter if A1 was really committed by some of the validators or not it just we will all will all do a a one before A3 it's just important that if somebody might have committed it that we do to absolutely must orderly one before a

tree to be safe now now the the hard task is like we did it we all we agreed on the older the anchors now what we need to do is just to go one by one and commit the causal histories of these anchors so in this example round one is the first round so A1 doesn't have any causal history so we don't need to alter anything before they won but then we go to A3 and cause and apply some deterministic rule to causally all the all the nodes and that that yeah in the causal history of eight week so that's a good question yeah you talk about deciding on an ordering of the anchors but I mean is it the case that they're always ordered by round and you're really just deciding on the subset of anchors that you're going

to include or yes yeah yeah I'm just yeah exactly yes they are older by one I just need to decide which I which I all doing which I don't all right yeah okay okay yeah I am yeah I use the old bill to the say yeah but you got what I'm saying right you just yeah decide which to take and which to skip yeah yeah exactly okay so yeah that's that's that's the whole protocol the departure synchronous version like if you like any questions or I can can I move to the forward quick question so how did we pick the anchors and also when did we pick the anchors

yes so so the encos are predefined we all we need a to a Justin is just similar to any other postural synchronous protocol anywhere in which the leaders are predefined right so here as well and close output defined so there is some mapping known to all mapping functions between a round number to an encode I mean it's not unlike just choosing leaders in a rotating leader kind of protocol right or I'm I mean the easiest way to do is to just assume we have a mapping but we don't have we don't have any Randomness here so it's in one way or another we will need to somehow deterministically apply all they agree

on it it's the we can try to use some information from the duck to do it but it's still it's no Randomness right so are the validator rewards different for whether or not you were an anchor or it's just underlying that's that's I think that's a separate question this is like an incentivized mechanism right how to incentivize the protocol um we I I don't have an answer to this we can come up with different approaches this is actually an interesting question we haven't think about it yet here is just a protocol we assume you know and and and validators F out of which FL Byzantine and the West just follow the

protocol but yeah of course if we wanna we will need to at some point we will need to to solve the incentives problem yeah it just uh oh I think it's a it's it's autoscope here but it's an interesting program to look at So when you say order anchors causal histories you literally just mean like look back in the dag and do it like super graphically or something like that yeah yeah okay exactly yes and then and then the kind of you have enough consistency that any two different nodes that have committed to A3 will both have the same kind of history's back is that right we'll have

yeah the the non-occupation of the dark guarantee that we see exactly the same because it is too yeah cool okay thank you for very good questions I I will move forward yeah okay so let's talk a little bit about the properties what we get here so first protocol post property that we get from free for free is chain quality because every node in every round in the dark has n minus F nodes out of which at least f plus one at most F from Byzantine so f plus at least f plus one are from honest then the chain quality is that we get is at least f plus one Auto divided by 12 plus 1 which is more than half and so more than half of the

nodes are proposed by honest uh by honest validators and this is actually proven to be optimal and in partial in synchrony and asyncony and pausing syncone and if we let about film I also want to talk slightly about fairness and garbage collection so what I mean by fairness is that if we have this the slow validator in Australia that nobody ever wait for he always like came late to the party because everybody already moved forward because everybody are closed then it's possible if we don't do anything then we just move forward with the faster and minus F and it's possible that in slow validator will never be able to add this note to the dog and thus never be able to add this transaction to The Ledger so

in order to solve it to introduce weak links and this is actually we introduced it in in the first paper and all you need is Doug to solve the atomic broadcast protocol a problem so what you bring a weak link a weak link is we it is only for this purpose we never use it we don't use it for the consensus logic that I described above these links are just to um to fail to nodes that otherwise what wouldn't be included in the dug so when we go and also because stories of the ankle we also all the the the nodes that are filled by weak links that's uh a very easy tweak to guarantee fairness but the problem is with this trick is the is that if we if we in during in asynchronic or during asynchronous

periods uh if you if we also want garbage collection and we do want garbage collection because otherwise the the protocol is Not Practical then then we cannot provide we cannot provide this we cannot keep we cannot keep infinite Dive Right because we need to garbage collect so and it's actually yeah it's actually easy to see that we cannot have this mechanism this perfect fairness together with garbage collection so what we decided to do in bull shark is that we provide garbage collection always we always collect the dog we keep the memory bounded but uh but we but we guarantee fairness during synchronous periods so so we keep the weak links for a while and then if you if you are just fast enough

um if you are not too slow and the period then you will be able to will be added to the to the dog otherwise the garbage Collective so um this is the This Is The Sweet Spot that we found fairness during synchrony and garbage and always garbage collect and yeah about garbage collection so this is another advantage of the round-based dive now if you're familiar with the Olio wall contact based consensus like hashgraph one of the reason they yeah they went I think widely adopted is because they have this garbage collection problem and and in any node could refer to any node in the past and then you it wasn't clear when you can garbage collect the the graph so

here everything is round based and together with consensus we can just simply agree starting I we got which collect everything below some round and because we have consensus we all agree on it and we all do the same so it's it's safe so so very roughly on the I I can explain so every node in order to garbage collect we will add another uh we'll add the time step a validator will besides all the other information we also add a timestamp and then then when we come in all the causal history of an ampl then we will need we will compute the the timestamp for the round so the and we do it by by taking the medium of all the nodes this is a this is a

standard trick to make sure that the timestamp comes from an honest party and then every round will have a timestamp the leader will also have a timestamp from its parents and then we just decide okay we will garbage collect all the rounds with timestamp timestamp which are file more than Delta from the encodes timestamp and that that's all very simple mechanism and this Delta will also the determine how fast this slow validator needs to be in order to be not to be garbage collected and included in the in the total order um okay so just to conclude bull shark I hope I convince you that this is extremely simple protocol

it has no real change no abusing communication none of these mechanisms that add external complexity into the only one type of message just broadcast the node and that's all it's little less so it's it's allow for perfect load balancing and network utilization uh while building the dog and it provides chain quality for free and fairness during synchrony and garbage collection and if they are if there if there are no questions I will move forward to novel but I will pause for a second just to check Sasha what did you mean by fairness exactly was that similar to chain quality or what does that mean yeah so

so chain quality means that the chain quality is a safety protocol right so by the definition of safety liveness protocols so yeah we check how many how many nodes out of the total number of nodes were proposed by honest validators this is chain quality fairness means that e all the validators will have a chance have a chance to be added to the to the to the dog so if I'm slow if you find a slow validation I will be added it's not like I yeah I will not be ignored and and fairness you you are that's an optimistic property or that sort of guaranteed I miss that yeah so so yes so I probably I haven't explained it well

so so fairness we can guarantee fairness uh always and then and then satisfy the atomic broadcast protocol but then we'll need to able to sacrifice garbage collection because it will not be a lot we will not be able to garbage collect the dog in divorce case uh during a synchrony so we don't want to sacrifice garbage collections so we slightly sacrifice families so we provide fairness only during a synchronous periods gotcha okay thanks okay so I will move to Naval as I said before novel is the system that I so far explained to you given a dog how I totally order it now I'll explain to you how we efficiently build this this dog

and this is the using novel okay so if we if you look at Current Designs so monolithic protocols like hot stuff like pbft and others they're they're sharing that the transaction that as part of the consensus and try to optimize the overall message complexity of the consequences protocol what it means that if we use if we look at the typical little based protocol that we have the leader the leader sends the data to all the other replicas the replicas check just signed and signed something and send it back to the leader and then the leader will again send the send another data to the validator to the to the other

validators divided over signs send it back to the little and what we have here if we check the resources resource utilization is that the leader works very hard it needs to keep broadcasting the data while the others while the other validators are almost doing nothing they'll just sign and and wait for the leader to to send the next data so so clearly the leader is the bottleneck and the the key the key the key observation that we do in novel is that in order to scale DFT system we need or any consensus system it doesn't have to be bft we need to decouple data dissemination from metadata uh for method from the metadata all doing so um on a high level the DAC that we are

building is not will not um does not contain the actual data it can it contains the metadata what we call proof availability so so what we do what we do in a high level is that the validators the stream they stream the data outside of this process of building the dark just just one just stream allow data to each other and then they will obtain proof of availability like if I if I stream you that I stream data to everybody and then the validators they get the data they persist it and then they they send me back a message with a signature saying that I have the data I I stopped I promise to store this data now I I collect the column of the signatures and this signatures this column is what we call proof of

availability and if I take this column of signature and I show it to some other validators the validator even though e locally doesn't have the data he can be assured that he will be able to get the data later because enough honest validators store the data question no okay so and then we take this proof availability and we and we and we build the dug with them so with the couple the data dissemination from the from the from the metadata all doing so so this is the key observation and this is how it works in novel this is the architecture so each node a novel has a one primary and a number of workers and the workers they can be processors on the same

machine but they can we can also think of a cluster and then a primary as a machine and each walk here with a machine in order to this is the perfect perfect architecture to scale out we can throw in more machines and we can be able to scale out because the the expensive part is just to stream the data so we can just add more vocals more machine to stream the data all during the metadata is actually very cheap so this is how it works the workers they get transactions from clients stream of transaction and then they stream them in batches to the other to the other validators just walk your stock directly to workers then they will they will take digest of these batches and pass it to the primary and the goal is of the

primary is to build the dog of these digests and the way it works is the following this is the the algo this is the primary the prime this is the primary protocol so the primary prepares a block header the block header has a references to the previous nodes in the dark as before and it all over and but instead of having this transaction it has the it has the it has the Digest now now you will send it the primary sends the headers to all other validators the validators make sure they they persist the data behind the digest sign it send it back to the validator the validator uh aggregated into a certificate and send the certificate back to all the validators now all this

mechanism this is one round on the abstract dag that I that I used to describe you the protocol before this this is one this is one round um yeah and this is this is basically the high level idea of how of how novel works and uh yeah next I want to talk about liveness so I just pause again to see if we have some questions about another why so does it um does it change sort of the trust assumption somehow I mean you have sort of extra data availability type trust assumptions or no it's the same to us the Assumption we have invalidators F out of f out of which can be Byzantine just the the

proof of availability is you you is n is two f plus one signatures um each signatures its signature is a promise that I stole the data out of Which F is actually honest f plus one is actually honest so this f plus one are actually stalling the data so later I can just I can ask a qualum and some honest validator will give me the data I'm sorry okay and and it's not it's not like every note has to store every single thing is that right no you just stole whatever you promised to store you you get you get the sign you store it yeah okay so there'd be maybe a constant Factor savings there or something

yes yeah and but yeah and of course when we implemented we need to garbage collect it I will not store it forever but uh this is I think this is two low level details of how we implement the garbage there but yeah there is some details of how to garbage collect okay thanks okay so now I want to talk slightly about liveness so in the asynchronous versions which is the Doug Rider task the the asynchronous version of bullshock protocols and here I remember you asked me how I where I take the encos form so in the asynchronous version they are actually not very fine I actually use one we

actually use Randomness Randomness to elect them and the way it works is that we use threshold signatures and each node of the dug we can simply the validator can simply sign the round number and then once I have a n minus F nodes in the dug I can collect this signature to a threshold signature I can hush it and I it's guaranteed that no like the threshold crypto guarantees that doesn't matter which of the nodes I deliver will will we will all have the same signature and the same hash and then we will elect the same encode so and then if you're familiar with Baba then it's kind of the same argument but I'm not I'm not gonna go into that

but I do want to talk is about the the partial synchronous liveness of the of the partial synchronous version of bull shark there we don't we don't have Randomness this is deterministic protocol so so we so we need to predefine we need to predefined leaders and uh and because it's a particular synchronous lightness and because we know there isn't there is the flp results and so of course we can we have to we have to use timeout somewhere in this somewhere in the system we cannot get away with it this isn't this is an impossibility result and we we consider two options and we evaluated to the two options of wealth how to use these timeouts and uh we ended up what we

ended up doing is using the timeouts directly on constructing the dag so I told you before that when I Advanced to to a new round I first need to deliver n minus F node in the current round this is still this is the same but on top of it we need to add something so if one of these nodes that I deliver is the end call then I can immediately go and continue and continue to move to the next round however if I didn't deliver yet the the end call then I will wait for the timeout to see if I will delete to wait for to deliver this anchor for the timeout and when I deliver it I can immediately move forward otherwise I just move forward when the timeout expires so this is what we ended up

doing and what we compare to is the we actually we actually thought of separating the physical duck from The Logical dug from a fermented intuitively when we thought about it without weights is a very neat and very clever idea because we will be able to build the physical dog same network speed never wait for timeouts and then just to piggyback the piggyback the virtual dug on top of the physical dug so each node will have one one extra bit saying am I it might belong to the virtual duggle notes and then the same logic we can Implement on the virtual dag once in a while let's say okay this is the virtual dug and this is and we will all the the consensus that I explained before will

use the virtual attack to do it and then and then each everything else is the same it's just piggybacking the virtual lag on top of the physical deck so yeah as I said before we thought it's a good idea it's a clever idea but when we implement it and compelled then then we saw it's actually a bad idea but probably we couldn't we couldn't think about it before we implemented so and and the reason is that is the following this is uh so we we we we separate the data discrimination from the from the older wings so even though we slightly we may we might slow down slightly on the construction of the duck because once in a while we wait for the timeout the data we keep streaming in network

speed the data is is like orthogonal to building the metadata so the only difference here is that if we if to build the duck slightly slower then every node will have slightly more um proof availability slightly more metadata but the data behind it will be the same so the the actual amount of data that we order will will still be the same so we are not losing throughput but on the other hand when we use this uh virtual dug on top of the physical dug so say I I missed I missed but I missed the physical load by by by little I I just my timeout expires like one millisecond after already I broadcast the physical dug so now I need to wait for the next round in order to piggyback

my logical my logical node and I lose this latency this is one this is the this is one and the second in general what we like um what the Insight that we launched on implementing it is that um building the duck too fast is not good we actually want to back pressure a little bit the the the the dug because because then we need to then the data structure is smaller we need to um they're in memory memory is smaller than less thread in the system are busy less networking so it's actually it's actually good to back pressure it a little bit um okay this was a note about likeness and now I wanna I wanna talk a little bit about the implementation and show you some graphs the question yes sure

yeah so the so the like this vava kind of trick that you use in the asynchronous case is should I think of that as just like a theoretical interest or is that also kind of practically relevant a it is practically relevant because um because we this is how the the Dustin Conneaut fall back walk so it's because everything is local right so it doesn't have any practical complexity just the local algorithm that you use so if yeah if you ask I can describe in like two one and two sentence so the trick is that we we only the randomness we apply from around the randomness we use the round four for a for Randomness to elect

an enco around one so this is already after the adversary we already committed to the structure of the dog so this is some simple combinatorial argument we saw that before we before we choose the randomness there are n minus f um enco potential nodes in round one that if we elect them the commit rule will be satisfied and it doesn't matter like the adversity can no matter what the adversary will do there will be this n minus F uh nodes the adversely can choose what n minus F Knows by like choosing the choosing the order of the delivery but no matter what it does there will be this n minus F nodes that will satisfy the commit rule so first we wait till the adversary to commit on

some sets and then we apply the randomness so we saw ability two over three we will elect an anchor which is in in this set and then the committer will be satisfied and we will be able we will be able to commit in all the one in order one rounds that's that's the rubber tweak and and it it and for for the for and it really doesn't matter because it just it's all it's all local we don't send any messages it's just the way we interpret the the dog so so you guys are going to implement this because like why not is that what I'm hearing or yeah exactly yeah why not yeah it's the system is the same it's just what is the it's instead of like 200 lines of code on top of now we will have 300 300 lines

of code on top of Novel so um why not yeah okay so is the threshold signature overhead uh negligible I guess like how often do we have to do like extra overhead to have this Randomness for anchor selection yeah that is actually a that's actually a very very good question because every time we change the validator set we'll need to do a new a new setup and um yeah and we we have some ideas of how to do it but uh it's we didn't implement it yet so we actually yeah this is actually a theme

for all your question as well if we were if we think it's gonna work but if it doesn't gonna work so we'll not be able to do this in Colonials fall back this is a this was a very very good question yeah so but we think we know how to do it to rotate the keys every every time we really configure and uh yeah if it's gonna work then we use then we will use the Aston continuous version otherwise we will not be able to yeah yeah thanks for the question I actually forgot about it yeah thanks hmm yeah okay so so let's talk a little bit about implementation so we've written everything in Rust we are using a real networking real storage real cryptography and you can find everything uh in Alberto's GitHub

we use the geode distributed setups and on AWS and this is this is this is a latency if we put a graph now for which of you and each of you that is not familiar with the latency throughput this is how we measure the peak the peak throughput the Peak Performance the peak throughput so we're keep increasing the the load and then we keep increasing the throughput until the latencyx explodes like this is the new point this is the point we can we cannot increase the load anymore we and this is actually the point that we are interested in this the sneak points is actually the the perform this is the Peak Performance of the of the protocol so we compare We compare the task and bullshock to two versions of hot stuff

first the vanilla hot stuff here we can see the the the the food put is 18 18 000 transaction per second then we are we actually implemented the um our version of hot stuff to improved version where we where we decoupled data dissemination from the metadata um and then the the hot stuff only only proposed digest of the data that we stream and then we improve performance by a lot but still not as good as task and bullshock and we can see the task has slightly better throughput but bullshock improve latency because like um less less rounds and for we also evaluated the performance under false and here we can see that hot stuff even our implement

the improved implementation of what stuff suffers while Tuscan bullshock are still performing pretty well yeah and just to to conclude this talk so so everything I just I described today is available the papers are available if you wanna if you want to read then extended version extended summary of the papers we have I have a blog post in a decentralized folds I I want to use this opportunity I think it ties on the call I want to say that this this blog is amazing and um yeah and you can you can check the blog post there so yeah that's it thank you again thank you very much for having me today so Andy Lewis pie who couldn't make the

talk but he he sent me a question kind of asynchronously he was wondering about transaction repetition so he was saying how you know as a as a user you might want to broadcast your transaction to f plus one different servers to to avoid sensor resistance in which case it seems like maybe you could get F copies of the transaction embedded in the dag and how do you guys think about that yeah that's that's that's again another very good point um so this in this work it was out of scope we did not address this problem in the none of these papers but we do have some photos of how to do it some how to solve this duplication so one one idea one idea we think is

like a Content addressable storage so um we will not will not store everything we'll just store that every just just think that we need and but it's it's not really baked idea yet it's yet another thing that we need to solve yeah that's yeah very good point all right sounds like me oh go ahead it's a good question do you feel like uh eventually all the projects gonna move to this dog based consensus Sunset has since it's faster It Gets Better Properties or leader based consensus uh still still have some advantages I am not I'm not objective right but I I don't think I I think this is strictly

better yeah one point yeah one point that we need to remember when we implemented that we don't need that complicated a little bit the implementation which we don't need in a little based thing is that we need to implement an abstraction of reliable communication meaning that in order to advance rounds I need to receive I need to received n minus F nodes so there is no there is no notion of timeouts like in a little based I don't receive if if I have a problem in the networking and the little was good but just the messages were dropped because some disconnection in the TCP right no harm is done right we will time out we will move to the next

video we'll try again but here if we need to implement some reliable communication on top of the 250p like application Level because if we are not getting n minus F nodes from the previous round we are stuck there is no notion of moving forward fine again we need we really need to get them eventually so this is this is one thing in implementation that we need to take into account while implementing it all right well Sasha this was great thank you so much so thank you thank you for having me