Recent Advances in DAG-based Protocols with Kartik Nayak | a16z crypto Research Series

Transcript

Good afternoon everyone. Welcome to our next A16Z crypto research seminar. Very pleased to introduce Cartik Nyak uh who got his PhD from Maryland. Uh he's now an associate tenure professor at um Duke University, also an adviser for espresso systems which is very cool. um he's done sort of work all across security applied cryptography you know consensus lots of areas super relevant to blockchain protocols and today we get the latest update on the progress on DAG based protocols so Cartik >> thank you so much Tim for the kind introduction and thank you so much for inviting me so I'm very very excited to be here so I would mention that this is like the first time ever that you know one of my PhD advisers one of my postoc advisers and my closest collaborator are in the same room for five days in a row

so >> no there's also the first time that the Q&A session already started before your talk. >> Yes. Elen started asking me questions uh before my talk. Yes. So, uh I'm I'm very excited about uh this talk topic. I'm I'm going to talk about DAB based protocols. So, this is something that where you know there has been a lot of excitement over the last 5 years. Uh I mean I'm going to present my view and you know the progress that I have seen the progress that I have helped made uh in the recent past. So to be frank, you know, until maybe mid to late 2023, I entirely ignored the space and then I started working on uh on the space. So during my talk, you'll see some degree of chronology in in terms of, you know, how improvements were made uh uh in in

my line of work. So what is the problem of interest over here? It's state machine replication where you have a group of parties that agree on a common sequence of transactions submitted by external clients and you want to achieve this even if some of these parties are faulty. Okay. So the the party over here with the red cross that is a faulty party and and you still want the other parties to agree with each other. So you have transactions coming in one at a time. These parties run some consensus protocol and they produce the next block and they keep doing this over and over again.

There are two key properties that you want. The first one is safety which says that any two non-faulty parties do not learn a different sequence of transactions. And the second is livveness which says that a transaction that is proposed by a client will eventually be executed by every non-falty party. So generally you want safety and livveness even when some of these parties may be faulty arbitrarily faulty. We're going to call them Byzantine faults. So T out of N of these parties are Byzantine faulty and this should hold under you know different network conditions that the protocol assumes and throughout I'm going to assume partial synchrony as as the underlying network condition. Okay and under partial synchrony it is known that you cannot tolerate more than t uh

so t less than n /3 is a bound of the number of faults you can tolerate. So there are two key metrics that we typically optimize. One is latency and the second is communication complexity. So latency is the time to commit a client transaction. Okay, a transaction arrives, these parties agree on it and and the client gets a response and the total time it takes you can measure it in number of rounds, number of deltas, wall clock time. So it is the latency to commit a client transaction. And the second is communication complexity. It is the number of bits communicated by honest parties or non-falty parties. So if you look back at the history, most of the protocols under partial synchrony used a very specific way of of doing consensus and we colloquially we call them leaderbased protocols. Over here

you would have a designated leader who is responsible for proposing blocks of transactions and getting all parties to agree on them. The idea is that if the leader is honest after GST that is after the network uh is synchronous you'll have both safety and livveness but if the leader is Byzantine you can never expect livveness but you will ensure that uh the protocol ensures that a Byzantine leader cannot break safety. The hope is that eventually you will have an honest leader and eventually the network is going to be synchronous. So eventually you you'll make progress and you'll maintain safety at all times.

Many protocols follow this approach. You know I have listed some of them over here. PBFT tment hot stuff PALA hot stuff too there are many others and if I look at you know what these protocols do with respect to these two metrics they actually give you you know ideal latency ideal communication complexity so there's PBFT that already gives you ideal latency of of three rounds and there's hot stuff that already gives you ideal communication complexity so natural question is you know aren't we already done the problem though is that we typically relate communication complexity or low communication complexity with high throughput And that may or may not uh be true. In particular, with a leaderbased protocol, your leader can be a bottleneck. So there are two key ways in which a leader

can be a bottleneck. One is there is unequaling of work in a typical leader based protocol. For instance, imagine a leader is sending a 1 megabyte block to a thousand parties. then the leader is actually sending 1 GBTE worth of information whereas each of the receiving parties are only receiving 1 megabyte worth of information. So if you think of it from a network standpoint, the leader is doing a lot more work than any of the recipients. And second, typically in these protocols, if a leader fails for whatever reason, there is no progress whatsoever and this can reduce throughput. Because of these reasons, you know, despite having good communication complexity, we may or may not have good throughput. So the problems I'm raising over here are are are very wellnown and there are

approaches to actually addressing this. There is a line of work on extension protocols where you can extend from a one bit consensus to an L-bit consensus protocol for an arbitrary value of L. And the key idea over here in in improving uh communication complexity or the amount of work the leader has to do is to use is to rely on erasia coding techniques. So there's another line of work on data availability oracles which in spirit kind of does something similar. It tries to achieve balanced communication. There are other techniques systems level optimizations like narwhal where you can separate transaction dissemination from consensus.

So all of these lines of work can actually help improve throughput. >> So like Salana's turbine I should think about is sort of in those top two bullets. >> Yes, exactly. >> What do DAG based protocols give you? I would argue that they would give me, you know, similar properties in perhaps a slightly more natural way because in a in a in a very natural fashion in DAG based protocols, every party performs a similar amount of work at all points of time in a sense because everyone is doing the same amount of work at all points of time. You know, fundamentally it solves the unequaling problem.

And second, the advantage is that you know your DAC construction it does not depend on on a leader. So you'll keep creating your DAG even when when a leader fails and at whenever a leader comes in afterwards you know you can commit everything that has happened in the past. This though comes at the cost of a high communication complexity which is typically incurred by these protocols. I will mention that whatever these protocols do it is not the case that prior protocols could not do. It is just that uh these protocols kind of achieve them in perhaps a more natural fashion.

So if you look at prior DAG based protocols, they improved throughput at the expense of communication complexity for moderately sized settings, okay, for something like n equals 100. But they actually did not give you ideal latency. And this is our first foray in terms of trying to work on DAG based protocols where we wanted to improve the latency of of DAG based protocols. And this is uh a work called selfish which is published in in uh S&P 2025. Let me talk about the the core protocol that we have. You know, it it it's the most natural protocol at least that I I can think of and perhaps you can think of as as well. So over here I'm describing this for n equals four parties. So every

party maintains uh a DAG of blocks proposed by parties. So one row for each party and the protocol progresses in rounds. So this is the frontier of the DAG at the end of round r minus one. When we move to the next round, what we require is that a vertex of round R. This is a vertex that is proposed by party the first party party P1. So vertex of round R points to 2T +1 vertices delivered from round r minus one.

Okay. So every such vertex has has this constraint. So over here when I say a vertex is delivered, I mean it in a very specific sense. So it is del so it is output by a reliable broadcast protocol. Okay. And and this gives me two key properties. So the first property is is non-equivocation which basically says that if some party PI has sent me a block in some round R for any other honest party they would receive the they would deliver the same block R they or they will not deliver a different block uh for the same party in the same round. Okay. So the second property I get because of an RBC is totality and totality says that if an honest party delivers a block all other

honest parties will uh deliver that block as well eventually. So due to this every honest party will eventually build the same DA >> in the end is it required to linearize the DAG or it's not required to linearize >> so you linearize the D. So in the end you have a chain. So, so is there any like requirement on um how how fast these blocks arrive because if people have see different subgraphs of the same graph then the linearization will be different.

>> That's a good question. So over here every honest party will eventually build the same DAG. But to answer Ela's question, you know that is exactly where we need consensus. Okay. So what you can have is that at any point in time the view of party PI looks like the following where you have in round R you have delivered all vertices but not the last vertex uh proposed by party the fourth party but for some other party PK they may have a different view where they have not delivered let's say the third vortex and to agree on you know which of these vertices are delivered at any given time this is where these protocols require agreement so how do you achieve is you use leaders. Okay, so every round is

going to have a leader. So it's it's marked uh with the crown. The idea is that we will use we will commit leader vertices and based on committing leader vertices, we'll order all other vertices. Okay, so if I have to commit leader vertices, what we do is that we prioritize parties prioritize pointing to the leader vertex. For example, if I want to commit uh the leader uh of round r, everyone in round r + one, they'll prioritize pointing to the leader r uh leader of round r.

So I can only do so until a given time because if the leader is malicious, this vertex may not exist. So parties prioritize pointing to the leader vertex until some time. And if it so happens that you know there are two t+1 vertices from round r + 1 that point to the leader vertex in round r then at that point I can commit my round our leader vertex. Okay. And this is where I I I do the step of linearizing which I do in a very peculiar fashion where I first find a path to a leader vertex in the largest row lower round recursively and and apply the same commit rule recursively in lower rounds. So in this particular example, I will first when I'm

committing the leader vertex of round r, I'll first commit attempt to commit the leader vertex of round r minus one because that is the largest uh that is the leader vertx in the largest lower round. And after I have applied the commit rule to that then I order rest of the vertices. I can order all of the vertices between the the non-leader vertices of vertices of round r minus one and the leader vertex. So and and over here you can apply any deterministic ordering uh that you like. >> Is this ordering rule new for Selfish or that's a standard for >> it's what all prior works did as well.

>> Okay. >> Go ahead. >> So I guess like I I'm just wondering how does it compare with Ethereum like as Yokim told me Ethereum is like the block proposers are distributing their blocks using some um diffusion protocol and the consensus is only on the metadata already anyway. So like if the consensus is just on the metadata like does this have any advantage over Ethereum's approach? >> I think the the question that you're asking is very broad. So I would prefer to take it at at the end if if you don't mind >> because it seems to me like at a philosophical level this is just doing distributing the blocks in a distributed way and running consensus on some metadata.

>> That that's that that's >> and that is exactly what Ethereum is doing. So why is like that particularly >> that's right but I think I I would prefer to maybe I think I think the the thing is you know I think we can devolve into a long discussion on that. So I think I'd prefer to take the question at the end. What happens if your roundar leader is Byzantine. Okay. So due to RBC equivocation is not possible but it may so happen that your round our leader vortex is not delivered. Okay. If this happens, what we require is that parties send either they point to this leader vertex of the previous round or if they cannot after this timeout, then they send a no vote message to the leader of round r + one.

Okay? And what we require the leader of round r+1 to do is is the same thing. Either you point to a leader of round r minus one or you show a certificate of 2t plus1 no parties. So the two T+1 parties are saying that they cannot vote and that justifies not pointing to the leader of round r minus one. >> Can the votes be split that some people vote for no vote, others people vote for the leader and neither gets uh the threshold? >> No, I guess it will so turn out that that that's that will not happen. >> Then you do you will require some double voting, right? I even though I voted for leader, I'm going to vote for timeout.

>> Uh yeah, I think so. Byzantine parties can do that but honest parties will not do that. But then you will have split votes, right? Neither reach the threshold. No. >> So I think let me go through the safety argument. I think I I'll go through perhaps exactly that. So the core of the safety argument is the following. Let's say some party commits around our leader vortex V. Okay. Then what we going to argue is that any comet that happens in around RP prime greater than R. Okay. So that leader vertex will always have a path to this round our leader vertex V that was committed earlier. Okay. So why is this uh why does this claim you know kind of

capture safety? It's because of a commit rule. In a commit rule we say whenever I want to commit something I'm going to recursively go to lower level leader vertices. Let's look at you know the base case where R prime equals R + 1. over here observe that there are two t+1 votes from round r + one on a round r leader vertex. This implies that at least t+1 of these are honest votes. Okay, this implies that if they have sent up they have pointed to the leader vertex there cannot exist a chorum of 2t +1 vertices who do not point to the leader vertex. Okay. and hence a no word

certificate cannot form the more general case where you know r prime greater greater than r + 1 you know let's look at r prime equals r +2 over here I'm going to look at two different corums one is the cororum of parties in round r+1 that have voted for the leader vertex of round r and second observe that in round r + 2 every vertex including the leader vertex points to 2t + 1 vertices in round r + 1. So the intersection of these two columns contain t+1 vertices and this ensures that there is a path from r plus2 leader to the round r leader. So the argument for r + 3 and so on. It's a little different from this but it follows a similar pattern.

So let's look at the latency. I'm committing a round r leader vertex in round r + one. Observe that every vertex over here is 1 RBC time. So this this implies 1 RBC plus 1 RBC. But something that I did not mention earlier is that for the second round to actually commit, you actually don't need to finish off the RBC, you can actually commit this based off of the first messages that you receive in in the second round. So that's why the second RBC for the DAC protocol construction, you need it. But from the standpoint of committing something, you can do it based off of the first message of the RBC that you receive. And that's why your leader vortex can be committed in time 1 RBC plus 1 delta. So this is this was an improve. So this was the key latency

improvement over prior work uh shaw and bullshock which required at least uh two RBCs. >> So you're saying this is specific to sailfish this step? >> Yes. >> Okay. Wait, sorry. I have a question. Is this better than an like linearly order lock in terms of latency or >> so I think my talk is in three parts and the second part of my talk will answer that question. >> But the non leader vertex latency is the stays the same. So why is it useful to improve the leader >> non leader lead vertex latency is 2 RBC plus 1 delta. Earlier it was 3 RBC.

Oh, but still my question is why is it important to distinguish leader vertex latency and non leader vertex latency? >> Oh, it's it's so I think it's it's perhaps uh not again I think I think part of it you know I think this is where I guess my views have evolved over time and this is the chronology I was referring to. So this is how I I thought of it and I'll tell you you know I think perhaps when I go to the second part of my talk I will say perhaps we should just talk about the worst case latency and at that point we should only care about the non-leader vertx latency because that is the worst case that matters right that with the queueing time if I were to compare this to the state-of-the-art I mean the way we usually do it in in academia if I

compare this to prior work let's say you know let's compare protocols with the same communication complexity so if I'm if I'm looking at the the competing work uh the prior work sh so it can be instantiated with communication complexity and cube where both of these protocols use RBC and RBC over here uh that we use is the one by Dash Shiang and and Ling and this allows so this RBC is requires four delta time so prior work required 8 delta latency our R our work could do it in five delta latency for the leader vortex and then there's an appropriate addition for the non-leer vortex if I were to use the fastest RBC that exists uh in this in in in the world with signatures uh that's by Abraham

at that point uh your RBC requires two delta time and that's why our protocol can commit with time three delta okay uh comparing this with this other work uh uh these couple of works called cordial miners and mysticity which opened up the RBC blackbox to improve latency even compared to them we uh we improve upon their latency okay so they're not modular in the sense that they do not you uh they they do not rely on your RBC blackbox. How can we observe this latency advantage in practice?

So we did uh experiments we compared it to prior work where parties were distributed equally in uh five different regions you know worldwide, US East, US West, Europe North, Tokyo and Sydney. And here are the graphs that we see over here. The x- axis is throughput. Y- axis is latency. And we are comparing uh this work to prior worksh and bullshock. So you want higher throughput and lower latency. So the lower and to the right is better. And this basically confirms that whatever we showed in theory, you know, it it it matches up uh in practice. And over here the code base that we used is exactly the same. Even if so, this was an experiment with 10 parties. Even if we grow the number of

parties from 10 to 50, similar parameters hold. So at network size up to 50 that we experimented the latency improvement still exists. >> Are any of them being used in pract practice like these are real world protocols or they are academic papers? So these are academic uh papers that I I think at some point Shaw was going to go into production but it did not because I guess they they put some some other protocol uh in production. >> Which concern they was going to use? >> So at some point Aptos was going to put Shaw in production is is what uh what I thought but I guess they have an improvement over it called Raptor which I think they will put in production at some point.

>> Is it still DAG based? So Raptor is not but mysticity which is DAG based is in production uh with SUI and that is DAG based. Yes. >> Why does latency go up with TPS? >> Why does latency go with TPS? So the intuitive uh reason is that when you're sending blocks when you keep receiving more and more transactions your blocks are larger and you're transmitting more data. >> But shouldn't the like ping time dominate the like additional? >> At some point it does not. So until some point it it does and and after that it does not.

>> So so is it uh purely for network reasons during latency or is it like the compute at that TPS is what starts to dominate? >> No, I would say it's a combination of the two. Uh but the network definitely matters >> and you don't even have like an execution layer for these experiments, right? Just >> Yeah, there there's zero execution. >> And to the four uh communication is it per block or is it like in total? Uh okay. The communication in in a given round >> in a given round. I see. >> If you amortize it, you can reduce >> like n like to n to the three if it's if they're all >> proposing or something.

>> Yeah. >> But that's still higher than nonag protocol, right? N to the three. >> Uh yes. >> So here my takeaway is that you have a throughput gain, right? But latency gain seems small because latency gain should apply even when throughput is very low. Right? So are you saying that that difference between two seconds and 1.7 seconds is the delta is the effect of shaving off deltas?

>> I think that is what we see in practice. Yeah. Yeah. >> Sorry. I I I don't understand the configuration. How do you make the throughput bigger? is just is is it like you just send more make the block size larger or >> so I guess with with in general with DAB based protocols right I think the reason why you get better throughput is because you don't have just one party disseminating you have all end parties disseminating at the same time and because you have all end parties disseminating at the same time you can you're you're utilizing your network bandwidth in a better way >> and my question is about like what knob are you turning to make the throughput bigger are you putting in more nodes or are you making the block size bigger to cuz your curve is a train.

>> Over here what we do typically in these experiments is that for a given load you try to optimize your block size in such a way that you can get the best possible throughput uh in such a way that you can manage the load uh and you can keep your latency to as small as possible. >> So all of these nodes are with all of these points are the same number of nodes right? >> Yes. So all of them are with 10 nodes >> with 10 nodes and you're just changing the block size essentially >> to get these points. >> So I guess what is changing is the number of transactions that you're receiving. Yes. So your block size uh may change. Yes.

uh since there are multiple proposers uh in in the same slot or in the same round it's going to be a dirty throughput right at the end at the end of the day because you might have uh multiple proposers including the same transactions. >> Yes, I think this is I mean this is an overall drawback with with DAB based protocols where you know different parties can send the same transactions. Yes, >> that is true. Can you go back to previous slide again? So, so at some point the latence should go to infinity, right? Is there >> that is the infinity point.

>> Okay. So, that is the point that it goes to infinity. >> I see. >> I mean after then you stop, right? >> But hold on. I'm still confused. Why is the latency so long? Like is is it is most of the time on the pin latency or just the network bandwidth? It's like the network bandwidth the bottleneck here. >> Uh network bandwidth is the bottleneck. So remember we are putting it in five different regions and that includes you know Tokyo and Sydney and the ping latency over there is something around 250 milliseconds. >> But but then latency is the bottleneck not bandwidth not not >> latency is the bottleneck. Yes.

>> Wait I think that that means bandwidth is the bottleneck like it's not the number of runs. Is it number of runs or is it the time it takes to transmit this data across the network? >> So both of them play a role, right? It's it's a combination of the two that that plays a role and how does that combination really matter for that? Let me move on to the second part of the talk. Typically we write these papers and we have these fancy tables and after these fancy tables we say hey we improve latency we improve communication complexity and that is why you know these are the parameters where my protocol performs better and this is why you should be using my protocol. I mean that is how you would put it if if I were to use it in practice.

Now this is if if I'm really thinking about practice right I think this is actually a very what protocol should be used is a very hard question to answer there are many several there are several factors that come into picture so as an example you know uh Ela may come in come in and say you know why don't you use PA or P or or some other protocol because I think it'll give you the same set of guarantees right it may come in and say you know use hot stuff or use SBFT link may come in and say use my protocol because it gives you granular synchrony And if I really have to make this decision in practice, it turns out to be a very hard question on how to compare protocols. Okay. So forget comparing protocols. Let's say you know we have chosen selfish as as

the protocol of choice for simplicity. Okay. Over here I present two variants. Which variant should I pick in practice? How how do I make this decision? So for one, we optimize communication complexity and latency in terms of number of rounds. separately the way they interplay with one another is something that we do not uh think about as much. >> I'm still confused right in the previous slide when you say the cost is is it quadratic or cubic is that is that just the metadata cost or it's like are you treating the block and the metadata the same because it seems like to transmit the block that's just quadratic right

everyone sends it to everyone else. So everyone sends it to everyone else but there are quorums of messages that you're sending as well. Every party sends a linear. So every party sends these certificates to everyone else as well and there are n other parties that are doing that. >> So that doesn't depend on the block size. >> So over here I'm I'm imagining a constant block size. So at that point it is n to the four. >> Maybe you're saying every time you're pushing n square bits, right? Like basically every every proposer You can optimize the block size to get these bounds. Right? So you're trying to commit n square bits.

>> Yeah. >> And then you either pay n. >> So this is the communication complexity for a given layer. >> You're trying to commit >> which commits n square bits. That's that gives you the >> why is it n square? There are n players and each player has one bit. >> No no order n. So each player in this to make this optim these each player has like an order n message. >> You mean each block size is n. Should I think of >> I don't know what I don't know what a block size is. The metadata the metadata alone is the end. You're saying >> I mean just taking all the hashes of all the links from everybody else is an order in thing, right? >> So I mean yeah just again the metadata is ordering. Yes. Yes. Exactly. So just just the >> that's that I think we cannot we should

we shouldn't assume upfront metadata is and because there may be protocols that allow you to compress this information like the threshold signatures and stuff. >> You okay? Uh-huh. I I I think it is better to like uh >> So, so Ela, should you use threshold signatures in practice? Let me ask you that question. >> Should I what? >> Should you use threshold signatures in practice? Right. I think again I think that's a difficult question to answer. >> But but this table is like a theoretical table right? >> Uh sure. So I think so over here this table is talking about the communication complexity for a given layer assuming uh you know uh fixed size data. So so it's talking about all of the different ends that could exist. So there are n parties each of them who are sending a linear

number of uh uh linear amount of data just in terms of the metadata and you're passing it through an RBC which which at least takes n square time. >> There's something I find a little strange here. So I if I understand correctly you're saying one major motivation of DAG protocol is to balance the work in a more natural way right even though leader based particles can do that using eraser code but now you're using RBC I think that's uh my CCS paper from 21 but that RBC uses eraser code right so then >> so this doesn't right >> sure but again I think us as theoreticians that is what we would do >> right in putting an RBC that doesn't use

eraser code. >> Uh in practice, yeah, I think that is what I would want to go. In fact, you know, I think what you would want to do is you would want to think about some sort of an optimistic path where you just do a consistent broadcast instead of a reliable broadcast. So, so for example, you know, I think if I'm not wrong in the paper, I'm pretty sure in in production code as well, in Mystic City, that is what they do. They just do a consistent broadcast and if you need a message, you ask for it uh after the fact. And that is how you save complexity over there. Okay. So coming back uh I guess which of these protocols should I pick is is a hard question to answer. So what are the different things that come into picture?

One is communication complexity and number of rounds. How do they interplay with each other? A second question that you may want to ask is you know how does computation affect performance? Are there any complicated crypto operations involved? Third, how does an adversary affect performance? And your adversarial behavior can change, you know, depending on the protocol itself. And its effect on the protocol can be dependent on the protocol itself. Fourth, you know, your ideal protocol can actually change with your changing n as well as changing load or or load in terms of the number of client transactions that you receive. And finally, how much does it really cost to run these protocols in a deployment? If I were to take this protocol and go out and practice and and use it, you know,

there are so many questions that that we need to answer before we figure out what protocol I should use. And different projects, right, that that we know of, they kind of make different trade-offs in in what they think is is important. one project you know as as in the process of advising espresso systems. This is one project that uh you know I I I was working towards where uh espresso systems together with offchain labs they want to implement what is called as a decentralized time boost sequencer. Okay. So they have a very specific requirement on uh on achieving this decentralized sequencer but at its core what they need is is a state machine replication protocol. And if you look at

their goals, you know, the key goal that they want to achieve is good latency. So, so far as I can get this latency, they're willing to trade off a lot of different things to get good latency. In addition, they want uh other parameters uh like you want me protection and for that some of these transactions could be encrypted and after you agree on them, you know, you would want to run a threshold decryption to decrypt them. Okay, they require some other things as well. For example, they there is a priority lane controller which prioritizes some transactions.

Right? So these are their requirements. Let us try to see how these requirements map to the questions that I asked. So they're interested in achieving low latency and for that they're willing to go for a very small n= 13 or n= 21. They're willing to tolerate a very small load. You know, we're not talking about 200,000 transactions a second. We're talking about a thousand or maybe 5,000 transactions a second. They want to ensure that since latency is a goal, they want to ensure that failed leaders, they should not affect have an effect on your performance. And finally, they want to have support for encrypted

transactions. So actually uh yeah so for this uh is espresso system I'm just curious like they're using a dag based protocol to do this. >> So this is separate from what espresso systems is is doing uh for their confirmation network. So this is like a separate collaboration between offchain labs and espresso systems. >> Oh so uh so like um I I I guess someone told me that they're no longer working on the decentralized sequences. Is that true? I think I'm I'm happy to discuss all of this but I think uh so this is a decentralized sequencer for for uh for arbitrum potentially for arbitrum >> and they they're they're trying to use DAG or they're not trying to use >> so they they are using DAG and they are

using Selfish in fact. >> Oh okay that's pretty cool. Yeah. >> Yes. But I think for their confirmation network no they are not they have a leaderbased protocol. So these are like two separate things. So when I'm I'm given all of these options, right, the the typical thing that we do is we look at all of these protocols and intuitively we try to argue maybe this protocol performs well, maybe that protocol performs well for so and so reason and we have intense discussions and then we figure out you know this is the protocol we should implement. So our approach if you if you look at it is to say hey we want to optimize number of rounds and we want to optimize the communication complexity. That's our typical design goal. So we have protocols with O1 and rounds and poly

and communication complexity for some small poly. Once we have that we implement these protocols then we run experiments on top of it and then we hope that they give you good throughput and latency. We optimize one thing and we hope to get good guarantees on something else. And in practice this may not always yield ideal results. An example over here are DAB based protocols where at least in practice I think we can figure out why very you know at some point but at least in practice it was shown that when n is small for moderately sized settings for n equals 100 you can actually get good throughput even if your even if your protocol has high communication

complexity. So we're in this world where we are optimizing for something but hoping something else gets better. Okay. And in between this we have a lot of development cost and a lot of cloud costs in terms of running these experiments themselves. This next work it's trying to address exactly this uh this question. You know how do communication complexity number of rounds different end different load how do they interplay with each other? For this we have this new work called the pipes model for latency and throughput analysis. And this is not a new protocol. It's just a way for analyzing existing protocols.

Okay. So the goal over here is to analytically and I stress analytically compute the trade-off between throughput and latency for a given protocol that's running with a given number of processes or a given number of parties. Okay. So you have a set of n parties each connected with each other with a delay of delta. Okay. And there's a bandwidth s for every party. Over here we think of you know time as being in terms of number of time slots where you can think of time slot as as an invis infinitismly small amount of time. Your bandwidth s is in terms of number of parcels packets

chunks of per unit time. Okay. And the entire system receives transactions at the rate of some d packets or d parcels per time slot. So what we are trying to get at is you know how does latency relate to D when you fix an N when you fix a delta and when you fix an S >> sorry so S is the total bandwidth to me or per chain per >> bandwidth is per party >> per party got it got it incoming outgoing >> uh we assume it's the same thing so I mean all of those can be tweaked I mean this is like the first work that we did so we we are actually making you know many many simplifying assumptions over here we assume synchrony always holds because in the good case that is what

happens in fact we assume that there's an exact delay delta in between any two parties we assume all parties are honest as well as we do not cons consider computation time and under this scenario I think we are trying to ask what is the worst case latency that I get under the best case conditions best case conditions meaning all of these guarantees holding and worst case latency is you know from from when a when a transaction arrives until all parties have committed uh that is that is the overall latency we are considering uh for a transaction >> what is the what is the worst case over at this point.

>> So if a so I think one thing that plays in is whenever a transaction comes in it can get into a block immediately or it may have to wait for some amount of time for the next block to be produced for example. >> So it's a stochastic arrival process you're saying or >> yes so you you're getting transactions at the rate of d packets per time slot. So some transactions come early, some transactions come late and we are looking at just the worst case time. So I'm actually not going to get into the details of how we do this because you know my co-author Andy is going to give a full talk on this. But since I'm talking about Sailfish, I'll show you the result of what we get if we apply our model to Sailfish. Okay.

So we get an equation of the following form where latency is given by this expression over here. Here in this expression again n is the number of parties. S is your bandwidth. Lambda is is the size of you know a size of a vote size of a hash. Delta is is the delay between parties and d is the is the is the transaction load. >> D is what >> the the the the incoming rate of client transactions. >> Can can you go back to the model again? I'm still confused. >> So D is the rate at which client transactions are arriving at the system.

Okay. So this is the effective throughput that you're going to get. And bandwidth is like the total bandwidth to >> bandwidth is the bandwidth of one party. So if if I'm running a processor and if I'm running an an 8Gbps network then my bandwidth s is 8 Gbps. >> So c can I assume the network is everyone uh has let's say there's a trusted authority that has infinite bandwidth and every everyone has a bandwidth sink to that trusted authority. Should I think of the network as that? So yes, I think I'm assuming that you get a fixed bandwidth from if if I'm using an AWS machine and if AWS tells me it is going to give me 8 Gbps, then I'm going to trust that I'm going to get 8Gbps. Yes.

>> And uh you are assuming if I'm need to talk to multiple parties the how to divide the bandwidth between them. >> I mean for most protocols you divide it equally but you could have protocols that divide it in a in a different way. Right? So at at the end of it when I receive a machine from AWS it tells me this is the bandwidth it does not tell me how I should be using that bandwidth. If a protocol uses it unevenly they can that's okay you know that can be captured when you're analyzing it. But isn't that the just this is that different from the standard model we like when we work on linearly order log isn't that also the same model >> it's the same thing you know when you

get a machine you have some bandwidth right >> so so this is not a new model it's just the standard model >> so we're trying to capture the existing model I think as faithfully as we can while making a lot of simplifying assumptions because we are doing this for the first Go ahead. >> So in the model everybody is the same S or people of different S's. >> We are assuming the same S for everyone. Yeah, we are assuming the same S for everyone. We're assuming the same delta for everyone as well which you know in practice in a geodistributed setting that's not true because US east and US west are much closer than US east and Sydney for example. I guess my question is like under this model assuming the protocol is load balanced let's say it uses those diffusion protocols that le is talking about that then the the

bandwidth should be indicative of the throughput right the total bandwidth consumption I assuming the protocol is automatically load balanced >> yes I think that is what this I mean so after it is load so uh with with salfish it's already load balanced and when you analyze it it is uh so okay think about it in the following fashion, right? You have transactions coming in at a given rate and the protocol has to take these transactions, put them in a block and and and send them over to everyone and and run your protocol. So you want to ensure that your protocol can tolerate this incoming uh set of transactions.

That is by the time I process one block, the number of transactions that arrive in that time frame, it should not exceed my block size because if it does, then my latency shoots up. Right. So assuming that is what is happening that is we are able to we are setting the block size in that fashion. we can analyze this and you get the corresponding uh latency metric uh latency equation that that you see over here for this particular latency metric uh over here as you can as I mentioned fixing delta fixing s fixing n and fixing lambda you're you're getting a relationship between d and and latency

okay so one thing to observe over here is that if d is much smaller than s if you look at the second term there is an S over D term over there at that point S / D is very large. So that makes the denominator very large and that makes the second term tend to one. Okay. So your latency is entirely defined by the first term. As D approaches S, S over D is very close to one. If S / D is very close to one, the denominator is very large uh very small and at that point the second term tends to infinity and your latency tends to infinity which you typically expect. So if I try to plug in parameters you know in a geodistributed setting these are some arbitrary numbers that I picked you know delta equals 200 milliseconds n=

400 picked an s picked a transaction size if you plot it these this is the curve uh that you observe >> this an upper bound or this is exact in your model >> uh this is exact I mean this is like a fixed equation so I'm just plotting the equation >> right but this is I mean as far the analysis that leads to the equation is does is it an upper bound on latency in your model or is it kind of exactly what it We fix everything right. So I think we are saying it takes an exact delta amount of time for example for a trans for >> you do you do a bunch of math and like the math could be tight or the math could be have like >> oh I think it's it's tight I think we keep it tight. Yes.

>> Yeah. So what I don't understand is if D goes to infinity I think the latency should be unbounded but in your expression the latency doesn't seem unbounded when D goes to infinity because if the the rate of incoming transaction is arbitrarily large then most of the transactions will never get confirmed right so the latence should go to infinity >> so I guess in our analysis we consider so I think the way we set our block size is in such a way that you can tolerate so I think what we do is we say we're going to set a block size I mean again I think this caveat that you mentioned I think we we write it in the paper. So we set the block size in such a way that the block can be cleared and the number of transactions that arrive by that time

is fixed. So there exists so I mean in terms of the analysis technique right we ensure that there exists a time where there are no transactions uh at that party. So I think there is I mean what you're suggesting is like a trivial bound which which we do state in the paper. >> I mean to relate Ela's question to the formula I mean I think that is only well that's only defined for D less than S right? Yes. >> And then as D approaches S from below, that blows up to infinity as you were suggesting. >> Exactly. >> So as D approaches S >> S from below, >> right, then S over D approaches one. So S overd minus one approaches zero. So that last term blows up.

>> I see. So it's assumed D is less than or equal to S. >> Otherwise, this doesn't make sense. Yeah. >> Exactly. >> Right. Um so like intuitively like as long as like when D is small like latency should be only ping time and like in a certain regime it feels like it should be like flat and then at a certain point the like block size starts to defect. >> That is exactly what you see over here. >> Why is the left even the curve? Why isn't it like flat and like like actually >> because this second term is not really one, right? It it it's something a little bigger than one as D keeps increasing. It's >> Yeah. So, so I guess like it's clear from the equation, but like is there any intuition of why it's bigger than one?

>> It it's it's so the intuition is that your block size as D increases your block size has to be larger and it takes a longer amount of time to disseminate. >> I guess like as long as D fits in the pipes, it's unclear why that would be >> I mean so whenever you're sending some message right there are two there are two things that come into picture. One is the the ping latency the capital delta and one is the latency to actually send this block. So if I'm sending some x amounts x bits of data for example and if my bandwidth is s the time it takes for me to send it to uh every party is x / s right if x is large so so the total time is x over s plus delta for example right so if x is large then this total time

keeps increasing and and and that is the effect that you see in in a larger block size and and that that contributes to it >> another question what I find confusing is people typically site diag I guess improving throughput, but your your point is it's actually improving latency rather than throughput. >> I mean, it's just a trade-off. I think my next slide is going to say is going to ask does DAG really improve throughput >> or I mean does DAG really improve throughput or latency? So I mean this example over here I mean I'm going back to the question that I asked for decentralized time boost. said we want a small n= uh 13 or n= 21. If I were to take that setting of n= 13 and uh plug in delta=

200 milliseconds and s= 10 gbps over here we have a corresponding plot for for sailfish and I also compare it with a leader based protocol that actually uses a communication efficient way using erasia codes and and that is uh disperse simplex and if you look at the curves that you for both of them. Uh you can see that disperse simplex can actually do better in this particular setting. >> Why why is that not a smooth curve? Why does it shoot up like that?

>> I mean the exact equation if you see I think you'll see that that happens. So if I were to run the same thing in in a single region in a single data center at that point you know your delta is going to be small delta is going to be 20 milliseconds let's say and if you have a smaller bandwidth then the story is is is even more different where you know for until some point until some throughput sailfish is better and then simplex starts becoming better and eventually you know uh sailfish uh starts performing better So in the third part of the talk I think I I'll not get get into it but let me just tell you I guess uh what the result is uh or or what we are doing. So I think

the question that we ask is you know whether computation affects performance and you know how much does it cost to run uh a protocol in deployment. One we want blockchains to be postquantum secure and second if you look at deployment costs for you know all of these protocols they're they're very expensive. So all of these protocols are running on 32 core machines and if you look at the DAG literature newer protocols actually use more cores for for various reasons you know one of them being you know verifying signatures. So these protocols are are very expensive and the question we asked was you know uh can we run these protocols on a four core machine and our work optimistic signature free reliable broadcast and its applications addresses this question. So it has the core of it is an

optimistic latency reliable broadcast protocol and once you have that you can get you know several other protocols and we can obtain signature free sailfish. So this part is where I was about to explain you know how can you make sailfish signature free. So the first part is you can rely on bracka broadcast in fact you can do something better by going over an optimistic two round reliable broadcast protocol. And the second part where we really rely on signatures you know you can sidestep that using a simple trick where instead of having a no certificate you directly point to vertices of brown. So do signature free protocols work well in practice? You know, we ran this on uh on simple four core machines and we

observed that they can perform better compared to uh signature based protocols under specific settings. And you know there are some nuances in running regular BRAA as your RBC versus an optimistic version of BRAA as RBC because of the number of reg regions involved in these protocols. So before ending my talk uh you know a shout out to my collaborators especially uh Nesh who's a recent star in this space and look out for exciting work by him and here are all the papers uh that I spoke about uh in this talk. I'm happy to answer all questions after talk. So from talking to like the salon people in practice for things like rotor they seem to say that like the time it takes to actually send things out is negligible

compared to the ping time and that seems to be like a bit different from your models. Um so so would you say that's a good misunderstanding or >> so when you say it's negligible I mean at the end of it I mean our model captures it in in in in the cleanest way possible right there is a bandwidth and you can send data only at a given rate you can't send any faster than that right no matter what you use to send that much amount of data has to go out and it you you cannot cross physical limits in a sense right so I mean the only thing we can do is you know take that protocol analyze it and see why you know they get good latency.

>> I I would speculate that the you know rates at the Salana validators it's quite a bit higher than the ones used in these experiments. So what looks non-negligible here maybe looks negligible if you have got that kind of hardware that would be my guess. So I mean so it can be hardware, it can be the amount of data you're sending as well, right? If you're if you're looking at for example uh sending 1 kilob of information over an 8Gbps network and you know if a ping latency is 100 milliseconds at that point that is really small compared to 100 millconds but instead of 1 kilobyte if I'm sending 1 GB worth of information because I want to have high throughput that argument is is is different.

>> Can you go back to the formula for sailfish? I I mean in some sense it says that uh as the hardware gets better right you you can get better performance which is kind of what we want right if you can get better throughput for your bandwidth then you can get better performance >> so I I assume the first term um the seven lambda n square that's roughly speaking the communication complexity right you divide that by the bandwidth plus seven I assume that's the rounds right but doesn't that mean that to traditional metrics rounds and communication indeed are good indicators.

>> So again I think so I actually had this slide which I removed because I thought my talk was too long. So these are good indicators they do not completely define uh you know the performance >> but what's the intuition why like I feel like these should define the performance in your network model because I thought you have no network model but actually the network model is the same as >> so let me give you maybe some counterarguments right to what you're saying if these metrics are like indicators of good performance then hot stuff should perform better than tenderintment under all circumstances right what we show in our our paper is that that is not true.

>> But that one is not balanced, right? So if it is balanced, then >> perhaps >> what more? >> Uhhuh. >> Yes. >> So but what is the reason why hot stuff is not as performant as tender mint? >> I mean I'm saying hot stuff is not better than tenderint. >> So although it has lower communication complexity >> and if you think about it I mean the reason why it's not performant as performant is because if you have all toall communication you incur one delta. If you're passing the things through the leader then you incur two delta. So in that sense it is worse. So you're paying deltas and you're improving communication. Okay. And the communication improvement is not buying you much. But paying deltas you're you're you're worsening things.

>> When you say better there are two dimensions too. There's throughput and there's latency. Right. >> So it sounds like it should have better latency than tender me. Otherwise it seems like it's counterintuitive. I mean >> I think that that that is the point I'm trying to make right. It is counterintuit. It feels counterintuitive but you can actually reason about it. Uh so so you can actually figure it out that uh both of these metrics if if you if you plot these curves which which we do in our work uh you will see that one is better than the other >> but I think there should be a more straightforward if like if it is worse there should be a better explanation.

>> I'll try to ask Ela's question um right because she's assuming we already have balance assuming a balanced protocol. Oh yeah, I'm assuming balance. >> Yeah. Can I then just take my communication divide by s plus the number of rounds. Is that >> for for the most part? I guess that is what is happening with with uh with disperse simplex and I guess the the diff that is disperse is balanced right and that is that is kind of what is happening with uh disperse simplex and what you see over here this gap is that factor of three that you incur when you're doing racial codes.

[Applause]