Direct Acyclic Graph (DAG) Based Consensus Protocols: An Introduction | a16z crypto research talks

Transcript

Um I welcome everyone to the last A16Z research seminar this for now in the seminar series. Um we're going to end not dissimilar to how we began with um Andrew Miller's talk about consensus and today we'll be talking about consensus. So Extend? Yeah. Okay, yes. So I'm going to give uh what I hope is a nice easy introduction to DAG-based consensus protocols. Um So I think most of the talk won't be that technical. Uh but this being a tutorial, I'm going to go through like a couple of proofs.

Okay, so there'll be there'll be some parts where some concentration is required. So please do like pepper me with questions. The more questions the better. Uh in fact I think I'll I'll I'll I'll finish early if there are enough questions. Okay, so don't don't worry about slowing me down. Okay, that's fine. Okay, so we're going to talk about DAG-based consensus protocols. I guess the uh the first natural question and let me just minimize that so I don't have to see the slides. Is so what is a DAG-based consensus protocol? Right? And why might might might we care about these things? Uh so I think it's safe to assume everyone knows what a blockchain is.

Okay, so obviously in a standard blockchain uh the way it works is the blocks uh at least the blocks that count right? The blocks that actually have their transactions executed is all in a sequence. So right each block pointing to the last one. Okay, uh and in a protocol let me see if I have to get that to go forward. In a protocol like Bitcoin uh forks do occur, right? But ultimately only one side of the fork ends up counting, right? In the sense that only one side of the fork actually has their transactions executed. And in fact certainly in the context of Bitcoin forks are seen as being a bad thing, right? Basically forks uh threaten security.

And so we actually have to slow things down and slow things down quite a bit, right? In order to prevent them happening too much. Okay, so on a very sort of basic level, the very sort of simplistic thought is, okay, wouldn't it be great if somehow both sides of a fork could count without threatening security? All right, if we could do that, then we could produce blocks much more quickly, right? And this would be a good thing. Okay, so that's exactly what happens in uh DAG-based protocol. Okay, so now blocks are allowed to have multiple parents and multiple children.

Okay, and the result of this structure we call the DAG or directed acyclic graph. Okay, so a graph is just a bunch of nodes or blocks uh with edges between them. Uh it's directed because it's the the edges have a direction to them. And it's acyclic cuz cuz they're all pointing in the same direction, which means we don't have cycles if you follow edges in the correct direction, yeah? Okay, so that's the sort of uh that's the sort of simplistic idea behind it. On a slightly slightly deeper level, the idea is that protocols like Bitcoin in some sense confuse two tasks. Okay, so blocks have a dual role.

On the one hand, the blocks are used for relaying uh sets of transactions. All right, on the other hand, they're also used in order to establish consensus on the ordering. Okay, and the idea is with a with a DAG-based protocol, we don't want to let a block's role in establishing consensus to get in the way with role in relaying the transactions. Okay? Okay, so the idea is that the the the DAG will just relay the set of transactions, okay? Maybe together with some sort of like minimal ordering on those transactions that's required to make sense of them.

All right, we need at least like at least some sort of order on the transactions to make sense of them cuz sometimes one transaction will load on others to be to be valid, right? Even before we start worrying about uh double spending and stuff. All right, so maybe Alice's transfer to Bob will only be valid after Charlie's first transfer of some some funds to her. Okay, so we need some sort of minimal ordering on the transactions. So, the DAG is just going to convey the transactions, right, with some minimal uh ordering information. And then the idea is that we'll be able to carry out a consensus protocol then on the on the DAG structure to totally order the transactions with after the fact at no extra communication cost.

Okay, so you're just going to lay the DAG. The DAG will tell you what the transactions are. And then after you've laid the DAG, it's each individual party is going to be able to take their DAG and run a little uh algorithm on their own to decide how to totally order the transactions and that have no extra cost right? That's the ideal. Okay, so in terms of throughput here, you've stopped consensus being a bottleneck. That's the plan. Okay, so different different sort of consensus protocols you run on a DAG might have different latencies and stuff, but you're not getting in the way of the throughput. Okay, so to summarize then, so the DAG structure, which can be very efficiently produced, all right, that just lays the transactions with some sort of minimal uh necessary information on the the

ordering there before you even start worrying about double spending and that kind of stuff. And then at no little extra communication cost, we're going to be able to carry out a consensus protocol on the DAG structure, which totally orders the transactions. Okay, and that's the basic plan. Okay, so uh so now let's start looking at uh some examples of of DAG protocols, okay? Um so to keep it simple first of all, so ultimately like in order to execute general smart contracts, we're going to be order we're going to be we're going to need to have like a total ordering on the transactions.

But for now, let's start off with a simpler task, okay? We're just going to implement a payment system. Okay, so we're just going to implement a payment system first of all. Uh and again, just to keep things simple, let's start off by considering just the permissioned case, okay? So, we have a fixed set of parties involved in the protocol execution. Let's say there are N parties. Everybody knows exactly whoever whoever else is right right from the start of the protocol execution. And maybe we'll we'll suppose we have a public infrastructure as well. Okay. And in fact, so the the payment system I'm going to I'm going to present is the one so Ed Shapiro Udi came a couple of weeks ago

and gave what I thought was a fascinating talk. Uh in that talk he he actually presented the the payment system I'm going to go over now. Uh so, if you completely understood every aspect of that, then I'm sorry for the repetition. Um I guess personally I I I didn't understand all of it until I went back and read a bit of the paper. So, I'm hoping it's worth going over again now. We have a a bit more time today, so I can sort of spend some more time going through the details. Okay. Okay, so I'm going to present uh Udi's system, which I think is a very elegant system. Um the whole thing I'm going to present will will work in the asynchronous setting.

Okay, so to remind you what that is, that means that so when you send messages, they are eventually delivered, but they can take any finite amount of time. Yeah. And so, you can sort of think of the adversary here as controlling message delivery subject to that constraint that eventually messages have to be delivered. Okay, everyone happy with that? Okay, and one other sort of slight simplification here. So, generally when we talk about blockchain protocols or state machine application protocols, there's a separation between like the the parties who are actually carrying out the consensus protocol and the clients who are producing the transactions. Okay?

So, here I don't want to worry about that sort of complication. Just to keep things simple, I'm going to imagine that it's actually that the parties who are carrying out the consensus protocol are the ones who are producing the transactions. Okay? So, in particular, that means that the blocks that each party produces, they can just be involved in like including their own transactions. That's not a necessary simplification. We We don't have to assume that. Okay, I'm just doing that to make the presentation slightly simpler. Okay. Okay, so what we have to do is we have to uh form the DAG structure in some way, and then we have to sort of think about how we prevent double spending and stuff. Okay?

Okay, so to form the DAG, it's very extremely simple. So, we just have honest parties produce blocks whenever they can. Okay, and I say one at a time in there. So, here I'm allowing that sort of different parties could produce different blocks at the exact same time. I just mean for an individual party, if they're honest, they'll produce their blocks one after another. Okay? Okay, so they produce blocks whenever they can, whenever they like. Uh the basic rule is very simple. So, what when they produce a block, it's just point to all existing leaves. Right? Like as seen by that party, obviously. Right? According to the DAG structure they've actually received.

Okay, so that's the simple rule. And that's it. Okay? So, that's that's how we form the DAG. Extremely simple. Uh there's a couple of other details I should add in there. So, we're assuming here that parties like sign their their blocks. Okay? So, you can't forge blocks and pretend they're by other people. And we're also we're not going to add a block into our DAG until we see the parents of that block. Okay? So, you're always going to You're going to imagine sort of downwards closed DAG structures the whole thing. Yeah. Okay. Uh so, a little terminology. Okay, so yes, you have to sort of memorize a few definitions as we go through here.

Uh So, so like if someone does a block with four predecessors, like you save it on the side until you also have heard about all those predecessors. Yes. Yes, exactly. Yeah. Yeah. Yeah. Okay, so when a when a block uh points directly to another, okay, we're going to say it acknowledges the block being pointed to. Okay, so here U1 acknowledges U2 and U3. Okay, with that. And then observing is just a transitive closure of acknowledge. Okay, so U observes V if there's a directed path from U to V.

Okay, so U U one here observes all the other blocks. So so columns here are the different players Yeah just Yes, exactly. Yeah, so yeah, well yeah. One column for each player just a nice way of picturing it. Uh and then we're imagining sort of time going up and it's exactly Okay, so U observes V just if there's you know if it's uh if there's a path from U to V. Okay. Uh and a basic observation here. So the instructions mean the blocks of an honest party will be in in a in a sequence in the sense that each block produced by P will observe the previous blocks produced by P.

Right, cuz each time it gets pointed to the leaves, right? So if you're honest, they'll be in a sequence in that sense. Are you happy so far? Okay, good. Okay, so if if all parties were honest, then this would be all that's required. Okay, but obviously we have to worry about uh people who might be dishonest. Might be we're imagining sort of Byzantine failures. Some people are allowed to behave dishonestly here. Uh So okay, what's the basic problem? Well, the problem is that uh a dishonest party could try to cheat, right? Or double spend by producing uh what you might call equivocating blocks. Okay, so these are incomparable blocks where so each uh neither observes the other.

So so what's So if everyone was honest, do we still have to talk about how to interpret the data, right? Well, okay. Uh No, I mean like you you could just regard transactions as being valid, right? I mean uh if nobody's cheating, then there there'll be there's no problem. We're not trying to totally order everything here, right? It's just a payment system. Okay, so what we're worrying about is just that Okay, so we have to worry about people cheating. They might try and cheat by by producing like equivocating blocks. So is there actually only possible conflicts from blocks by the same party?

In this setting, okay, because I've said that uh each party will just include their own transactions in their own block. The general setting's going to be essentially the same, okay, but uh in this setting, okay, my blocks include my transactions. I was going to mention that the conflict between my transactions and different people, I guess. Okay so how do we deal with that? Yeah. So the order still sort of matter? Like if A pays B and B pays A Well, that's the the order that's given by the DAG, right? So the DAG is giving you this this this minimal uh order. So that that you're you're you're putting them into the into the DAG in a in a in a ordering that makes sense.

total ordering or does it matter what the total ordering is? Well, no, you don't you're not establishing a total ordering, right? So if any transaction depends on others, then that those have to be included amongst the parents of that block. But you're pointing to all leaves. So that that's fine. It's like cuz they both involve B through B's total ordering and all total orderings Okay, uh so yeah, so how do we do this? It's quite simple. Um Okay, so some some more definitions, I'm afraid. Okay, so we're going to say a block U approves V, uh block V produced by P.

Okay, if it if it if it observes it and it doesn't observe any P block that equivocates with it. Okay so as an example here, it's a U1 approves V. Right, in this case actually it it it acknowledges it, but we don't require that. We require just that it observes it. Right, and it doesn't observe this other equivocating block here. Okay? Okay, so that was for blocks. Now we want to extend the definition to parties.

Okay, we're saying party P prime approves V just if some P prime block approves V. Okay, so there's at least one block produced by P prime that approves it. Okay, so this is important here. So in particular in this situation here then this means that P4 approves V, right? Even even though U2, which is a P4 block doesn't. Right, so U2 is observing both of the equivocating pair. Okay, but here P4 approves it just because there is the P4 block U1 that does that approves it. Okay, because we require one P4 block that approves.

That's all. Happy with that? So this would happen only if P4 was dishonest. No, no, no, no. But here P4 is being entirely honest. They They produced this block before they saw this one. Later on they get They're supposed to They They point to all these. Or it could even be that they're forced to because P2 has observed this one and they're forced to point to that leaf. Okay? I see. Because in this picture U2 are Yeah, so in in in So in this picture I kind of it's I guess that you have an option whether you point to it or Okay, so maybe a better picture would be if if you P2 produced blocks that have observed this one and not that one. And then P4 is forced to observe the other the other block.

Say again. Sorry. So so Like the blocks don't say I approve this block. I observe that block. They just have a list of blocks they're observing. Yeah, well, yeah. I guess well And they approve the set Yeah, okay. I guess you could phrase it like that. Yeah, okay. Yeah, so yeah. You just You just point to some parents. That defines the the set of blocks that you're observing. And then from that there's a definition of which ones you're approving. I mean, fundamentally it's just really just like a DAG in the mathematical sense. Yeah.

With a label on each and every player. Yeah. And then all of these are just the players. No, extraneous definitions on top. Right. Right. Yeah. Right. So you're you're not thinking about these definitions you form the DAG, you just form the DAG. Yeah. Yeah. Okay. Okay. So we have that definition there. Okay. So so uh one party approves a particular block just that they produce some blocks that approves it, the block in question. Okay. Okay. So now a basic observation that is an honest party uh can't approve two equivocating blocks produced by uh some party P.

Okay, why is that? Well, consider the first block by P prime that approves one of those two blocks. Again, it can't approve both at the same time cuz if it's observing both, right, then it's approving neither of them. Yeah? So consider the first block by P prime that approves one of the blocks. Well, then all subsequent blocks by P prime, like they're on a sequence, so they're also observed they'll still observe that first block, right? So they can't approve the other block. Right. Either they observe or they don't, either way they're not going to approve it. Okay. So honest parties can't approve uh both sides of an equivocating pair, only one side.

Okay. And now basically we're done, almost, right? So we say V is approved by a supermajority if it's approved by N minus F parties. Okay. So N is the number of parties involved, F is our number of faulty parties, which we're thinking of as being less than N over 3. Okay. So that's our notion of finality, that's our notion of confirmation, right? We say V is approved by supermajority if it's approved by N minus F parties. And then we're done, right? So, we're supposing f here is less than n over 3. What we have now is that two equivocating blocks produced by p can't both be approved by a supermajority.

And that's because then we if it is then we have two sets of m - f parties those two sets, just by a simple counting argument, have to have some honest party in the intersection. But that honest party couldn't approve both sides of the equivocating pair. Okay, so to recap, so right, so to form the DAG is extremely simple because they have honest parties basically pointing to existing leaves when they produce a block. A block approves v produced by p if it if it if it basically if it observes it and it doesn't approve any equivocating block.

Okay? And then a party approves a block if it just if it produces some block that approves the block in question. Okay, and then we we are easily get safety, right? So, v is approved by say v is approved by a supermajority if it is approved by m - f parties. It's established as safety because two equivocating blocks produced by p can't both be approved by a supermajority just by a simple common intersection. So, what are the properties we're aiming for since we don't have consensus?

We want that when you produce equivocating blocks, they can't both they can't both be confirmed basically. That's why it's Yeah, that's safety. Well, so liveness is is irrelevant, okay? So, but it's kind of trivial in this circumstance, okay? So, uh basically what what you want I mean so here as long as everybody's producing infinitely many blocks, if I produce a block and then when it was part not part of a equivocating pair and I send it to the honest miners, then okay, we're in the asynchronous setting, but it will eventually be delivered, right? So, they're producing infinitely blocks that will then those blocks will be pointing to all the leaves, they'll eventually uh observe my block and so approve it because it's not part of the protocol we're debating there.

Okay, so live and assistant are fairly trivial here. Okay, so I don't know. I I think that's kind of like a extremely simple, elegant protocol. Now I was kind of impressed by how simply that could be done. Yeah, and it's worth noting also here that you have this is like a deterministic protocol, right? Which works in the asynchronous setting. So that might sound sort of odd if you're familiar with a results from consensus that is famous result of Fisher Lynch and Patterson, right? Which says basically you can't do consensus in the asynchronous setting in a deterministic fashion. Like there has to be some sort of random is involved.

So here we haven't got a contradiction cuz we're not solving Byzantine agreement. We're solving a slightly weaker problem. Okay, so I don't know. I I think that's a very simple, elegant protocol. At this point hopefully you're convinced that DAGs are useful. That's my first aim. Yeah. Yeah okay.

So you okay, so the thing is okay, all of this I I've sort of simplified it slightly. If you want to do it for transactions instead, you can just do exactly the same definitions basically. And you say like one block approves a transaction if it observes it but it doesn't doesn't observe any conflicting transaction. And the same sort of proofs go through, okay? Yeah. Yeah yeah. Okay. Right. Okay, so that's the yeah. Well, so what part is it not solving? I mean I guess you'd have to sort of come up with a reduction and then see how the

reduction fails, I guess. So maybe that's the way to answer that. Is it? I mean I mean but byzantine agreement is a is a particular task, right? It's okay if maybe you if you replace byzantine agreement with with state machine replication just think of them as essentially being equivalent in some sense. So, state machine replication asks for us like a total ordering on on on transactions which we're not producing here. Yeah, I think that's an interesting question, right? And that's a fascinating question. It's kind of it's made slightly less interesting by the fact it's quite easy to get a total order.

So, so I think it would be worth really going into that in detail if it wasn't quite easy so easy to get the total order, but yeah, yeah, yeah, yeah. Uh okay. So, that's payment system Okay, if you introduce randomness and stuff. I'm saying okay, when I say it's really easy I mean okay It's not I mean say again?

Because different people are going to have see different versions of the DAG at any given time of the time. So, it's quite it's very easy to take it like a function that takes any DAG and just like stretches it out into a linear order, but different people going to see different versions of DAG at different times. If you just do that simple thing, then you're not going to have safety. They're going to they're going to see different sequences in their total order. Okay. So, is easy. Okay, it's not easy. I mean I guess we're going to go through that now, right? So, it is easy in the sense that there's no extra like a communication cost to it. Okay? Mhm.

Yeah. Mhm. Yeah, okay. I mean certainly termination is part of it. I I I I I I guess we'll see later on. Maybe it's worth thinking in terms of Byzantine broadcast rather than uh Byzantine agreement maybe it's all clearer. So, there definitely the termination is the is the the thing that's impossible in the asynchronous setting, right? So, once you remove the termination or do a weaker version of termination, which we'll see later on, then that it becomes possible in the asynchronous setting. The fact that we can't achieve a total ordering without randomness, that's that's true because we're in the

asynchronous model. Yeah, okay. Yeah, so then you Yes, exactly. Yeah, in fact. Yes. Yes. Yeah, you wait for the period of synchrony and then you'll you'll be able to extract the total ordering without randomness. Yes. Yes. Sorry. The naive protocol would just Okay, you could take any DAG and just like you can just stretch it out to sort of preserve the ordering relation just add in extend

the order. So, now you've got a total ordering. Yeah yeah. Yeah. Yeah. Okay. So, you could do that. But then you're not going to have your safety uh condition be satisfied, right? Because different people can see different versions of the DAG. I've seen this path over here, you've seen that path over here. And they're going to be producing incompatible sequences if we do that, okay? So, we have we have to go back. Well yeah. And And you don't know when you've heard of the same set of blocks and then I Yeah, so on. Yeah, yeah.

Yeah yeah. Okay. Uh so, that's I'm supposed to be the sort of the simpler elegant part of the talk. Now we want to go into total ordering part. So this part I'm afraid is a bit more fiddly. There's quite a lot of definitions involved. So again, feel free to make me to go back over definitions and stuff. I hope this part isn't isn't isn't overly fiddly, okay? Okay, so yeah, so now we want to we want to extract like a total ordering on transactions. Okay, and I'm going to try and sketch how we do that. And the basic point is as I said before is you know, or at least the the idea is that we can we can do that at no extra communication cost. We can we just because we're laying this DAG, okay, and then no extra communication cost, each individual party will just look at their

DAG, and they'll gradually form this total ordering in such a way where that we have this safety condition that everyone's always got sort of compatible versions of that total ordering, okay? Okay, so first of all, we're going to look at how the Cordial Miners protocol does this, okay, and then we'll we'll also see how DAG-Rider works in detail. Basically, it's just a fairly simple proof so it's really just one big thing. Okay, so I'm going to proceed. So uh okay, so first of all, I am going to give the DAG a little bit more structure, okay? So what we're going to do now is we're going to divide the DAG up into rounds, okay? Round one, round two, round three, and so on.

Okay, and each honest party will produce one block at each round. Okay. Okay, and we're going to say that as an honest party will produce a block in round R plus one as soon as it sees n minus f blocks in round R. Okay, we we can do that in a synchronous setting, right? Cuz you just inductively suppose that everybody's going to produce blocks in round R, then they'll send those blocks out, everyone would eventually see those blocks, right? At least the n minus f of them cuz the faulty parties might not. Okay, and so eventually everyone will proceed to round R plus one, and they'll produce blocks in that in that round, and so on.

Yeah? Okay, so that's the rule. So an honest party is going to produce a block in round R plus one as soon as it sees N minus F blocks in round R. Again, F is the number of faulty parties. And the rule is well, it's the same rule as before. So, the block produced must point to those N minus F blocks in round R you've just seen. Uh and also any other leaves from from previous rounds. Okay, so it makes it the same as if you just do all the leaves basically, right? Okay. Just make it explicit that it points to those N minus F as well. Okay. So, you got the only new data that is the round.

Yes. So, that yeah, that rounds and the rules is the way you proceed between rounds. is the same as before except that there's an extra round field. Yes. Yeah, yeah, yeah. Okay. Okay, so we go So, if party two, let's suppose say here we've got N is five and F is one. Okay, so we're waiting to see four blocks in in a round before we proceed. So, we we suppose party two here has just seen these four blocks. Okay, then they'll produce a new block that points to those, but also there's a leaf down there, so they'll point to that guy down there. Okay, so the rules for forming the DAG clear?

Great. Okay. Okay, and then as to how we're going to extract this total order, uh well, we didn't have to use a notion of leader blocks, but it's a sort of fairly sort of uh natural way to proceed. That's what we're going to do. Okay, so we're going to use a notion of leader blocks. Uh and what we're going to do is we're going to divide all the the rounds into waves. Okay, basically each wave will consist of five rounds. Okay, so wave one is one to rounds one to three to five, wave two is six to nine to ten, and so on. Happy with that? Okay, so we're dividing into waves. Each wave consists of five rounds.

And then, okay, so the first round of each wave we're going to select a leader. Okay, so in round one we'll select a leader, round six we'll select a leader, round eleven we'll select a leader, and so on, yeah. Okay? And then, blocks produced by the leader like in that round, they'll be called leader blocks. Okay. Okay, so if I'm the leader for round one, I produce a block in round one, that that that will be called a leader block. Is that crystal clear? Yeah.

We have a system of five rounds. And with the honest leader, you have one leader block. With the dishonest leader, you may have many. Yeah, so the leader block, yeah, exactly, yeah. Yeah. Okay, so here I'm not going to I don't need to worry yet about like how we're selecting the leader for each round. Okay, at the back of our minds here, we know that now we are going to come up against the FLP impossibility results. We know we are going to have to use some randomness at some point. Okay, and it's it's in choosing the leaders that the randomness is going to come in. Okay, so you can have that at the back of your mind if you like. But for now, I don't want you to worry about how the leader is selected. Okay, but they just there are leaders somehow, okay?

So the safety will be for a worst-case ordering for our leader. Well, yeah, we'll we'll get we'll we'll get safety without where it's it's for the liveness that we need the randomness, okay? So, yeah, okay, yeah. Yeah, we could we could we could choose leaders deterministically and be safe, but we we want liveness, okay? Okay, so is that all crystal clear? Great. Okay. Okay, as we we just saying before, okay, so it's uh hopefully fairly easy to see. I mean, it's it's quite easy to extend any DAG structure to a a total order, okay, if you're not worried about things like safety conditions and things, okay?

Right, so we can assume given that we're given some function tau which takes any DAG and extends it to a total ordering. Okay, so we're going to assume given a tau is that of that sort, and that will just be a tool that we're going to use. Doesn't yet suffice, right, because it doesn't have the required safety safety condition. Okay, if people just use this tau, they're going to be producing incompatible sequences, okay? But it's going to be a tool that we can use, okay? Okay, a little bit of notation, okay, so for block U, so square brackets U is it just that's the initial segment of the DAG defined by U, like below U, okay?

All the stuff that you observe, right, including you. Okay, so first of all then sort of the the rough idea is this, okay, so here I'm being a little bit vague at first, you know, I'll make it more precise later on. Okay, so for some sort of like commonly agreed sequence of leader blocks, whatever that means, we'll have to make that precise. Maybe we'll for some commonly agreed sort of leader blocks, like U1, U2, U3, and so on. What we're going to do is we're going to define the total ordering to be so tau of U1, okay, and then concatenated with tau of this remainder here, like the stuff that U2 observed that isn't already observed by U1, concatenated with this remainder here, concatenated with this remainder here, and so on.

Okay, that's what we're going to end up doing. And hopefully it's clear on some sort of basic intuitive level, because I'm I'm being vague at this point. But if there really is some sort of commonly agreed sequence of leader blocks, then this would sort of be okay, right? So tau of U2 minus U1, so I should interpret U2 minus U1 just as like set difference Yeah. Yeah. Give me a new DAG, which tau is then defined on. Yeah yeah. Okay, so that's the rough picture. Okay, we want to form some sort of commonly agreed sequence of leader blocks, and then we're going to we're going to form the total ordering in this sort of way.

Uh it's obvious here though that we we can't just like do use any sequence of leader blocks, right, because you know, that people might sort of disagree on them. Uh malicious actors might produce equivocating pairs of leader blocks, and so on, okay? So the blocks we use will have to be confirmed or final in some sense. Okay, so we're going to need some sort of notion of finality here. This would all be easy with only honest leaders, right? There'd be no problem. Uh yes, with certainly if yes, if all the leaf blocks were honest, it'd be a guess. Yes.

Okay. Okay, so to recap then, so the idea so far is that we divide in sets of rounds into waves. Each wave is five rounds. We somehow select a leader for the leader for the first round of each wave. And we call their blocks in that round uh leader blocks. Okay? Uh and I guess if we could agree on a sequence of leader blocks, then that sequence could be used as I guess described to define the define the required total ordering. Okay? And what we said just before is that to agree on the on the on the on the sequence, obviously we'll need to find some notion of finality for leader blocks. Okay? So everyone can agree on which which which blocks are final.

Okay, so now what we're going to do is define Yes. Okay? Yeah, you're just totally ordering stuff. So you're you're you're you're meeting SMR requirements. Yeah. Okay, so what I guess I said there is that we we need to establish a notion of finality for for for leader blocks so everyone agree on the the the right sort of sequence to use, right? So just a couple of definitions again, I apologize some of the definitions, it's not my fault. Okay, so by a super majority of blocks, right, we mean a a set of blocks produced by a majority of miners or validators or whatever you

want to call them. Okay? So take the set of blocks, take the set of miners who produced at least one of those, that's a super majority. Okay? Okay, and now we're going to say a block V is ratified by a block U if U observes a super majority of blocks approving V. Okay, so maybe give it a little time to absorb that. If If you're familiar with Tendermint, then one way you could think of this you could sort of think of this as being a thing of you as seeing a stage. So in Tendermint you have like two rounds of voting in each block. Right? You might get in the first round you might get a stage one QC or quorum certificate. In

stage two you might get a stage two QC. Okay? Here you could think of you as like seeing a stage one QC for V. Right? Because each of these blocks that is a is approving V you could think of that as being vote for V. Okay? So you is seeing like a stage one QC. So you can think of when when you see a stage one QC you you vote for it. So you can think of you as representing like a stage two vote in the in the Tendermint setting. Okay? If If you're familiar with Tendermint, that's helpful. If you're not, it's unhelpful. In that case, forget what I just said. Just take the Take it at face value. Okay?

Okay, and then we're going to say a leader block of wave W is final if it's ratified by a supermajority of blocks in the final round of the wave. Okay, and again, for those who know Tendermint, this is like V receiving a stage two QC. Right? Each of those Each of those blocks that ratify it, that's like a stage two vote. Now you've got a supermajority of those. So we've got our stage two QC. Okay, and again, that's hopefully a helpful way to think about it if you know Tendermint. If you don't, then just take those definitions at

at face value. Okay? Okay, so I guess yeah, it's quite helpful if you can try and remember those definitions for what's what's going to follow. Okay? Everybody happy? Okay, so we said we needed a a notion of finality. Okay, now we now we've got that that that notion, we can go back and we can make our previous I I sort of outlined how we're going to define our our total ordering. Okay, but now we can make that precise using the uh the notion of finality we defined.

Okay, so at any given point in the the execution, each each party is going to have some DAG structure. They want to extract some sort of total ordering from that. Okay, so what we're doing is we're defining a function ord which will take any DAG structure. You're thinking of being the DAG structure that a party might have at a given point in the execution. Okay, it's going to output some totally ordered sequence of of blocks. Okay? And what we said before is basically it's going to suffice to select an appropriate sequence of leader blocks. Okay, appropriate in some sense. So all we have to specify now is precisely how we define that sequence.

Okay, then we'll have defined ord. So the way we define that sequence is as follows. So what we do, we take D, we take the last final leader block in D. That's this guy here. Okay, we take the last final leader block in D. Let's call that guy U. Okay? And then so that's that this guy here. And then we ask, "So what what's the the last leader block uh in D that's ratified by U?" Not necessarily final, but what's the last leader block that's ratified by U? That's this guy here. Okay, so that's U prime. And then we ask, "What's the last leader block ratified by U prime?"

That's this guy here. Call that U double prime. And we keep on iterating. And that's how we define our sequence. Okay so again, so that's the way we define the sequence. We just take the last final leader block. Okay, that's U. And we ask, "What's the last leader block ratified by U?" That's this guy. What's the last leader block ratified by that one? That's the next guy, and so on. We're iterating in that fashion to define our sequence. Okay, and then again, so once we've got the sequence U1, U2, U3, and so on and so forth, all right, our output is just tower of the stuff below U1 concatenated with tower of the stuff in the remainder concatenated with tower of the stuff in the remainder there, okay?

So, that's just a definition. It shouldn't be clear yet why that works, okay? But, at this point, it's important that the definition is clear. Okay. Okay. Mhm. Mhm. Yeah.

Right. So, okay. So, here again again, it won't be clear why this is the right definition yet, but it's just a definition. So, we we take the the last final leader block in the DAG. Okay. Yeah. Okay. Yeah. Yeah, it's finalized. Okay. And then, we look at what's the last leader block ratified by that one. So, it could be the previous one or it could be an earlier one. Which may or may not be final, right? Okay. Then, we just keep on issuing. What's the last leader block ratified by that one? What's the last leader block ratified by that one? And so on. And then, we keep on iterating back. That defines our sequence. Then, we feed it into town. We get our our our our our Yes. Yeah. Uh okay.

Okay. Well, certainly, we'll see if it works. And then, we can also think about what will happen if that theory that as well. Okay, fine. Okay. Okay. Sorry, can I ask another question? Just to understand what's going on. So, if Um so, say that for example, things are working normally and then there is some leader in some round who for some reason wants to like no previous blocks. And then that leader does broadcast So, there's some leader in some round who points to none, but like that he can't do that. You you won't You won't be regarded as being a you will ignore the block unless he points to like a super majority in the previous round right?

Got it. Okay. Okay. Okay. So, I should move on at this point. We happy with the the basic definitions. I say uh So, now basically all we've done so far is we've defined how we extract the total ordering, right? So, now what we're going to do is we're going to prove safety and we're going to prove liveness. Okay, so let's let's see safety first. Sorry, I don't I still don't understand the proof a little bit. So, like you start from a block that's final. Mhm. Then you look at the most recent one that they ratified.

Yeah. Then you must look at the most recent one that that one ratified. Exactly. Yeah. Yeah. Yeah. Yeah. Okay. Okay. Um so, basically from this point it's going to be pretty easy to prove safety if we have the following lemma. And the following lemma will be pretty easy to prove. Okay. So, the the following lemma says say if a leader block is final, then in fact it's ratified by every subsequent leader block. Okay, so being final that you're ratified by a super majority in the final round of that wave already. This just said, okay, actually that the next leader will also ratify you and the leader after that will also ratify you and so on.

Okay? Okay, so that's a lemma. It's quite an easy lemma. We'll we'll see proof of that in a in a second. But first of all, I just want to like assume that lemma is true and see why it quickly leads to safety. Okay? Okay, well what do we have to prove to prove safety? Basically, what we've got to prove is this. So, if D1 and D2 are two DAGs held by honest parties P1 and P2, maybe at the same time, maybe at different times. Okay, then ord D1, the total ordering, you know, that corresponds to D1, and the total ordering that corresponds to D2, right? These are consistent, right?

One is a uh initial segment of another one. Right? That's what we want to prove for safety. Happy with that? Cool. Okay, and the next point, so if we want to prove that, the next observation is well, it suffices to show that the sort of total ordering corresponding to D1 is an initial segment of the total ordering corresponding to D1 union D2, and the total ordering corresponding to D2 is also initial segment of the total ordering corresponding to D1 of the union right?

Because if they're both initial segments of this common string, then they have to be compatible. Okay? So, in general then, it suffices to show that if you got one DAG held by one user, and another DAG held by another user, that could be held by another user, which and the and the first one is a super if it's a subset of the second one, then the total ordering corresponding to the first one is a uh initial segment of the total ordering corresponding to the second one. Okay, so in general it it it suffices to consider the case that D1 is a is a is a a subset of D2. Maybe that's slightly confusing notation I'm using for D2 in different ways there, but okay.

Okay, we happy with that? Okay, so we just have to show that if if one DAG is held by one user, and a second DAG is held by another user, and that that second DAG is a superset of the first, then the corresponding uh total order is uh it is an extension of the the the total order for the for the first smaller set, okay? Okay, so let's consider that case. Okay, let's suppose D1 is a subset of D2, right? And now we want to show that they the corresponding total orders are are consistent with each other. Okay, so consider the cases. First of all, if D1 has no final leader, okay, then the total order corresponding to it is just the empty sequence. Okay, so then we're done cuz that's compatible with everything.

Okay, so suppose otherwise. Suppose the last final leader block in D1 is is just this node here U. Okay? Then how do we form the total ordering on D2? Well, we take the last final leader in D2, this guy is up this guy up here, right? And then we go to the last final leader ratified by that one, the last final leader ratified by that one, and so on. And what we need to be true is at some point in this sequence we're going to hit this node U, right? We can't go past node U. But that follows just directly from the lemma we previously stated. We said if if U is a final leader block, then it's ratified by all subsequent leader blocks.

Okay, so this node here will be ratified by all these guys. Okay, so we can't go past U in the ordering, okay, in the sequence. Cuz that means the total ordering corresponding to D2 will just be the total ordering corresponding to D1 concatenated with the tower of these guys, concatenated with the tower of these guys, concatenated with the tower of those guys, and so on. Okay? So it's an extension of the total ordering corresponding to D1. Cuz it could be the same thing, right? But it's Okay, it's certainly compatible. Happy with that? So I stand up for a second. Right, so going back to the original question, if you're like waving through just one round, then this builder is still right.

Uh well you in the liveness in this proof we're going to leave waves to be uh five rounds long. Yeah, so far we're not using the other rounds of the wave at all really, right? But you we're going to need five rounds in the in the wave in order to make sure that you that the liveness happens. I'm going on? Yeah. Okay. Okay, so that all works. Um but we assume this basic lemma, right? So if a leader is final, then it is ratified by every subsequent leader block. Okay, so let's just quickly prove that. This is kind of easy. We can do this just by a proof by picture.

Okay, there are So, two cases to consider here. Is it the first case or the second? So, the first case is So, this is a a final uh leader block here. Okay? And the first case is we're considering a leader for the next round. I'm sorry, the first round of the next wave, right? Okay? So, this is the final leader block here. So, what does this picture mean? So, here we have This is the final round of the of the wave. Right? All these guys are ratifying this guy here cuz each one of these can observe some supermajority blocks approving it. Okay, these supermajorities aren't all necessarily the same, which kind of looks like they are in the picture, but it's hard to draw a picture properly, right? Okay? So, So, here this is the final round of the wave. Each of these guys ratifies this,

right? So, they're each observing a supermajority of blocks that uh approves that. Okay? So, the first case is that the the next leader we're considering is the one that that for the uh the first round of the next wave. Okay, in that case, this guy here has to acknowledge a supermajority. All right? That's the rules of forming the DAG. Okay? That supermajority and this one have to have some honest node in the intersection. Okay? But then this guy is observing a a supermajority blocks approving him. So, so is he.

Okay, so in that case, he also ratifies the block. And then, okay, the other case is basically the same. Okay, now we're considering It's not It's not necessarily the the first wave round of the next wave, but some later wave. It's basically the same argument. So, here we have a leader block here. They have to approve acknowledge to acknowledge some supermajority of nodes. Again, this supermajority and this supermajority have to have some honest node in the intersection. This honest node's block here, it's the same honest node, right? This one has to observe this one. So, again, this guy still observes the supermajority of nodes uh approving the the relevant block, right?

The final block. Okay, so in both cases it's quite a simple observation there. Okay, so we have security. Okay, so now we're almost at the end of the fiddly bit of the talk. Easier in a little bit. You know, kind of ratifying and finalization Yeah. Yeah, so I Yeah. Is that I knew you were going to ask that question. I thought about I guess it's obvious question. I mean Okay, I guess when I was giving the analogy of the first it was mainly just to help you sort of think about

remembering the definition. How precise the analogy is, I'm not sure. It's worth thinking about. Yeah, okay. Yeah. I just like in Tendermint you would say you'll never exist two stage two QCs. Yeah. I mean yeah. It's something slightly different about it. Because in Tendermint you're using locks and that kind of stuff and I don't think quite the same stuff is happening here. So I Yeah. I thought about it a bit but maybe it's worth thinking about more. Okay, so we've done um security. Now I guess have to show liveness. This part I'm going to sketch a bit more I'm not going to do full proof.

Okay, so first of all so for liveness it's first it's first to show if it's pretty clear the existence of infinitely many honest final leader blocks. Okay, because if I produce a block and I send it out that eventually it will be delivered, right? And to the all the honest parties, right? So they will they will be producing blocks that observe it. Okay, so it's it's going to be incorporated into our total order as long as they're producing infinitely many final leader blocks. Okay, so that's our task. Okay, now though we come up against this this problem that we're going to need randomness in the asynchronous setting.

Okay, so what happens? So if if we don't proceed in a random fashion, but don't use any randomness, let's suppose we just announce ahead of time that P3 is going to be leader at the beginning of the wave. Well, then what the adversary can do is they they can just delay messages from P3. Right, and as the honest parties, we don't know. So, maybe P3 is just a dishonest party. Maybe they're never going to send any messages. Right, maybe they don't know whether the message is being delayed or whether or not they're maybe they're dishonest. So, we can't wait forever. Eventually, we have to get on with something else. We have to add some other stuff into our into our total ordering. And then, okay, so so it won't work. Okay? Okay, so this won't work. So, what we can do instead though is let's suppose

we don't elect a leader initially, okay? What we do is we just let allow everybody to keep forming a DAG in a standard fashion. And if we do that, what we'll find is that we end up with a supermajority of blocks from the first round of the wave down here uh which are ratified by all blocks in the final round of the wave. And that will just sort of happen by some sort of combinatorial argument that isn't that fiddly, which I'm sweeping under the rug slightly, okay? Okay? So, then what we can do is we can toss our our our global coin, okay, in order to retrospectively select which guy is a leader for this wave.

And we have a like a a more than 2/3 chance of selecting one that is uh that actually going to produce the final final block for that wave. But the point is that every honest node behaves as if Let's see. I'm just saying like the behavior in waves by honest nodes was kind of independent of the identity of the leader. Yeah, you didn't even know who the leader was, right? So, you you you you just you just you you just proceeded. And the way the DAG structure formed, you just get a lot of blocks down here being ratified by a lot of blocks up here. And so, then you just randomly choose a leader, and it has a good chance of working out and producing a final Yeah, but that would make the common leader a little bit of a misleading terminology.

Okay. Okay yeah. Yes. I don't know. Yes, so here we got K is five. I mean it's a little bit sort of fiddly. So here K is five for Cordial Miners for Dag Rider which we'll see in a bit K is four. Yeah, I mean it's one of those arguments it's not it's not actually that hard but it's maybe a bit sort of fiddly for a for a talk. You sort of do up some like truth table you count number of ones and stuff like that. Huh?

No. Well, you need okay for this one okay so let's say for Dag Rider you need four but you can sort of cheat by overlapping the last round of this one the first round of the next ones you can bring it down to three, okay? But the basic this argument seems to require four. Okay, so that was Cordial Miners. Yeah, so at this point basically most of the the hard work is done. Hopefully it'll be easier from this point, okay? So now let's look at Dag Rider, okay? So this is I'm going to say this is it's pretty similar but now we're going to deal with the possibility of equivocating blocks in a different way. So previously we allowed equivocating blocks they were added to the DAG and then we had to deal with them. Now basically we're we're going to

just prevent equivocating blocks from being added to the DAG in the first place. Okay, and we're going to do do that using what's called reliable broadcast. Okay, so let's look at reliable broadcast first. Okay, so as we were sort of talking about a little bit earlier on so basically reliable broadcast you can think of it being like a relaxation of Byzantine broadcast where you weaken the termination condition. And the difficulty with Byzantine broadcast in the asynchronous setting is you're forced to terminate even if the broadcaster says nothing. So that's obviously just impossible because if the broadcaster said nothing you don't know are they honest or are they just waiting for their messages and like what to terminate now or are they just dishonest and so on, okay?

Okay, so we weaken the the termination requirement. Okay, so again just to find the problem so that the setup is a one party designated to the the broadcaster and they're given some input. Okay, and then the requirements of of as follows. So first of all, we have like a an agreement requirement. Okay, which says, "If any honest party terminates, then they must all terminate with the same output in V." Okay, but that's allowing that maybe none of them terminate. Right? Especially if the if the leader is dishonest and they're sending no messages whatsoever, you're allowed not to terminate. Okay, so that's the the agreement requirement. And then we have a validity requirement that says, "Okay, but if the if the broadcaster is honest, then all honest parties have to terminate giving their their input as their output."

Okay, we have the definition. So this is essentially like Byzantine broadcast, but we weaken the termination condition to to say in particular, okay, so if if the if the broadcaster is dishonest, it means you don't have to terminate. But if any honest party does, then you will do have to. Okay? Yeah, that's fine. So so the termination is like So the node should be thinking, "I'm only going to terminate if I am convinced myself that others will eventually terminate." Otherwise, for example, if that's not allowed, some honest party terminates and some not.

Right. Yes, yeah. Hang on. Okay. Okay, so this is what I'm going to show you is the sort of simplest version of this. This is Bracha's broadcast. It's very nice, elegant sort of protocol. Again, this works in the async model setting. It's entirely deterministic, etc. Okay, uh and then there are more sophisticated versions that are more efficient and so on, but this is a very nice simple one. Okay. So initially, unsurprisingly, the the broadcaster sends their value to all. Obviously, if they're honest, they'll send a single value. If they're dishonest, they might send multiple values. Okay? Okay, and then there are three circumstances in which any any party speaks after that.

Okay, so first of all, when P receives the first value from the broadcaster, they echo that value. And they send a message echo V to all parties. Okay. So if that's not too surprising, okay, you receive the value, you just echo it to everybody. Okay. Okay, second circumstance in which you speak, okay, if P receives echo V messages from N minus F distinct parties and it hasn't yet voted then P votes for V by sending like a vote for V out to all parties.

Okay, you see N minus F echoes all for the same value then you vote for that value. So, far what we've achieved basically is that honest parties can't vote for different values. All right, you can vote for two different values, that corresponds to the like two different sets of N minus F echo messages, right? The two sets of N minus F parties must have an honest party in the set intersection, right? You can't echo two values. Okay, so so far what we've achieved is yeah, honest parties can't vote for two distinct values. And then there, okay it's going to be easy to make sure that different honest parties can't decide different values, okay? So, we're in a strong position so far for that.

Okay, and the last condition in which someone speaks is so if P receives vote V messages from F plus one distinct parties right? And it hasn't yet voted and then P also votes for V by sending a vote V message to all parties. Okay, and the point of that is to ensure that so if any honest party decides V Okay, basically you're going to you're going to decide V, I haven't written it down yet, but we'll in a bit. You'll decide V when you see N minus F votes for V, so if any honest party decides V that's cuz they've seen N minus F votes for V, that means all parties have seen N minus 2F votes for V which means they've seen they've seen F plus one votes for V, which means that all honest parties will vote, which means that all honest parties will

terminate okay? Okay. Okay, we'll go through that again in a little bit, I think. Okay, and then the determination uh is specified just as I previously said. So, an honest party decides V if it receives vote V messages from N minus F distinct parties. Okay, so let's prove that works. Okay, so I've just made it smaller and put it inside the box there. Uh Okay so So, first of all, right, we want to show just I'm going to say the same thing we observed before. So, honest parties can't vote for different values.

Suppose uh they do. Right, suppose P is the first honest party to vote for V and the P prime is the first honest party to vote for some different value V prime not equal to V. Okay, in that case, each of these must receive echo V messages from N minus F distinct parties, right? If you're the first one to vote for a value, it has to be for this first reason here. It can't be for this reason because this requires there to be F plus one votes already. At least one of them must be honest, right? So, if you're the first person to vote, it has to be uh for this reason here, right? Okay? So, then P receives echo V messages from N minus F distinct parties. P prime receives echo V message V prime messages from N minus F distinct distinct parties. But then those two sets of N

minus F parties, they must have an honest party in the intersection, right? And that's a contradiction cuz they couldn't vote for they couldn't echo both values. Okay. So, that's just what we said before. So, honest parties can't vote for different values. Uh and then what do we have to show? Well, we have to show that if the broadcast is honest, then nobody's going to sort of terminate with their their input value as their output. Okay, but here that's easy, right? Because if the broadcast is honest, then they're going to send the same value to everybody. Everyone's going to echo that value and then everyone's going to vote for that value and they'll all decide on that value, right? Because Right, hopefully that that's that's clear from the protocol.

Right, they'll send it out. Everybody will echo that. So, they'll all see N minus F uh echoes for that value. So, they'll all then vote for it. We'll all see N minus F votes. Right, you could vote this way or that way depending on what you see first, but either way everyone will vote for it. All honest parties will vote for V, right? Okay, so that case is is easy enough. And the last thing we have to show is the the agreement property. Okay, so now supposing an honest party decides V well then that means they receive n minus f votes for V, right? So that means all parties receive at least n minus 2f votes for V.

Yeah? Okay, but we're we're assuming f is less than n over 3, so that means that we they all receive f plus one distinct uh votes for V. Okay, so that means all honest parties are going to vote for V either through this first mechanism or through the second mechanism. Right? And also cuz they can't have already voted for other values, right? So all honest parties will vote for V, so they'll all decide for V. Okay, so again, I think that's kind of a very elegant, slick uh protocol, you know?

That's very nice. Okay. Uh and again, note this is a simple deterministic protocol which works in the asynchronous setting. Okay? And in fact, and you might think this is interesting or else maybe you don't think it is, it doesn't even require PKI if we have authenticated channels okay? Okay, so now I'm back to Dag Rider. Uh so basically the protocol works very similarly to to cordial miners, the protocol we were we're describing before. Okay, but now we're going to deal with equivocating blocks differently. Right, rather than allowing them to be added to the DAG, we're going to stop them being added to the DAG. We're going to say for each round, each party has to go through some like reliable broadcast, right? So

either everyone will decide like on a same one one one value for them or none. So you can't you can't produce equivocating blocks, yeah? This is the case where you don't know at any given moment of time you may not know whether you're decided No, you do yeah, you do know, exactly, yeah. Okay so the outcome of this? This allows you to reduce um the number of rounds in each way by one. Okay, the cost is that rather than just allowing people to add directly, you know, blocks indirectly, you have to go through this this broadcast protocol, right? So, that's that's uh adding to the latency. Right? They've got the various rounds of the broadcast protocol to go to go through for each block.

Um an advantage you get, so I described Bracha's broadcast there, which is a very simple we can we can do some more efficient things, clever things. Can be used Each round you're doing n parallel executions of this broadcast protocol, is that Yeah. Okay, so uh yeah, but then we we can use efficient versions of reliable broadcast I'm going to describe. They can be used to make the expected amortized communication complexity per transaction order n for DAG Rider. Okay, so order n is the best you can possibly do per transaction cuz it at least has to be sent sent to all parties.

But there is a bit of a sort of cheat going on here cuz basically the way you achieve this is through some other techniques and through batching. So, batching means you basically stick lots and lots of transactions into each block in order to like hide the the communication costs like they have to the consensus, okay? So, in order to achieve that, it's not that bad. You have to add add n log n many transactions into each block. Maybe that's fine. Okay. In some of the protocols like like Honey Badger it's like n squared log n or something. So, maybe that is is more of a cheat, I think. Okay, so now uh let's start thinking about uh our DAG protocols actually good and how do they compare with your monolithic protocols where everything is in a in a row?

Uh okay, so first of all, I'm going to look at communication complexity. I'm going to preface this by saying I don't think communication complexity is a very good way of comparing how protocols are efficient. Basically, I mean I like this is the standard way it's done in the distributed computing literature, but I don't think it's a particularly um good measure. Okay, but anyway, but cuz it's the standard way we'll go through that first. Okay, um Okay, so so far we've been looking at the asynchronous setting. So let's stay there for a little bit. Okay, I was going to say later on though you have me. So we focused on the asynchronous setting. You can and of course you can define that protocols which are specialized to work in the partially synchronous or the synchronous setting or whatever, yeah.

Okay. Okay, so let's start comparing with uh some non-DAG protocols uh in the asynchronous setting first of all. Um and in particular let's think about so Veba is basically a modification of HotStuff which works in the asynchronous setting. Okay, HotStuff is is designed to work in the partially synchronous setting. Uh right where message delivery has like uh good periods and bad periods, right? You're only required to make progress when you have good communication. Uh okay, but if you we we can sort of modify HotStuff quite easily to work in the asynchronous setting. Um so how do we do that?

Well, basically we have we have the same threat to liveness as we had before. Right? So if we just select the leader in advance, right? I suppose we we we produce some K blocks. We now want to produce the K plus first block. If we just select this guy's going to be leader in advance, well then you adversary can just delay their messages. Again, it's the same thing, right? So as the honest guys, we don't know is the leader honest and their message has been delayed or they dishonest or they're never going to produce anything. So eventually we'll have to move on. Okay, so that doesn't work. So what we do is something sort of similar. So what we do is we run n instances of HotStuff through three-phase protocol for next block simultaneously.

Yeah? And simultaneously, right? Each party like acting as a leader once, right? For one of those, yeah? And then what we can do is we wait for n minus f of those to complete. Right? That would eventually have to happen. Okay? And then, same sort of trick as before, we ran we select a leader, right? And if they produce a confirmed block then we use that one. And we just discard the rest. Seems extremely wasteful, right? I mean this this trick doesn't seem very specific to HotStuff.

No. No. No. No. No. Okay. I I'm It's true. I'm I'm I'm using HotStuff rather than Tendermint cuz the the the instructions in HotStuff are the are the sort wait for A minus F then do this. Wait for A minus F then this. Whereas whereas whereas Tendermint sort of relies on timeouts and stuff. These won't work in the asynchronous setting. Okay. So, hopefully that's basically clear how we can get it to work in the asynchronous setting. Okay. So, what's the communication complexity there? Well, so for each instance it's order N. We've got N of them so that's order N squared. We imagine our blocks are of of constant size here.

Okay. So, this is order N squared expected expected communication complexity per confirmed transaction now cuz it's expected cuz now we've got randomness involved and stuff, right? Okay. Okay. Well, I mean it could be that you never produce anything, right? Yeah. Yeah. Yeah. Yeah. Yeah. Yeah. Okay. So, that gives you N squared. But okay, then there are things you can do with like batching including more transactions in blocks and some other sort of clever tricks. So, Dumbo is a modification of Vapor, the protocol we just talked about. It modifies that using batching and some other tricks that gives you order N expected like amortized communication complexity per confirmed transaction transaction. Okay.

So, again, you can get it to the optimal case. Right. So, order N as I said here is optimal because each transaction has to at least be sent to the N different parties right? So, you get the optimal case as long as you're you're happy to accept this this batching. Okay. Which again, there is a trade-off there cuz that that can increase your latency, right? Depends how fast transactions are coming in. But if you have to wait for like N log N transactions or N squared log N or whatever, then that can that can slow things down. Okay. So, if we call the miners we've got order n squared expected amortized communication complexity per transaction using batching. And again, using some sort of like slick reliable broadcast protocol for the DAG Rider, and you're order n expected amortized communication complexity per transaction.

Um A slight sort of complication here is we we we haven't worried yet about So, in a DAG structure, if you've got an actual situation where all the clients are sending in their transactions, uh right, they're they're presumably going to want to send those the transactions to multiple sort of miners, multiple validators, right? And you know, that we we can't censor them. So, then you're there's a danger of having like repetition of transactions, right? So, you you you want In order to get uh in order to make these calculations, we're basically ignoring transaction repetition here.

Okay, so there's a slight sort of complexity there. But you can get around that by sort of randomly sampling which which transactions you're using and that kind of stuff. Okay, but that that isn't specified in these protocols. It is specified in Honey Badger, for example, but it's it's not worried about here. Okay, so that was for the asynchronous setting. Uh how about for the partially synchronous setting? Okay, so Bullshark is basically it's like a it's like DAG Rider, but it's optimized in some way to work for the the partially synchronous setting. Okay, what do we find here? So, again, so looking at HotStuff, uh so HotStuff has sort of like order n complexity within views. I guess at this point I'm kind of assuming you know HotStuff a bit, sorry about that. Okay, so HotStuff has like order n complexity within views. It doesn't tell you how to

efficiently manage your view changes. Uh so, if you use my protocol, so Fever, that gives you like 2n uh messages per view change. Okay, so if you if you use that combined with HotStuff, then what do you get? So, here then you have order n communication complexity when network conditions are good and all parties are honest. That's like under good conditions. Okay, but so now it's not expected order n, it's not amortized order n, it's just order n like per per transac- per transaction okay? You have order and amortized communication complexity when network conditions are good, you have Byzantine parties.

So, the amortization is over what? Yeah, so you might have like F many faulty leaders in a row. But, uh yes, you're just averaging out everyone, yeah. Okay, and you get order N squared communication cost in the worst case, right, to produce a confirmed block when network conditions are good and with Byzantine adversaries. So, order N squared to produce a confirmed block in the worst case. If you go to Bullshark, okay, we're we're missing out this case, we're going straight to the amortized version. So, we get the amortized version again, order N amortized cost.

Um But then, when you look at like the the worst-case cost to produce a confirmed block, now it this looks massive, right? So, in the worst case, we've got like order N to the four log N communication cost to produce a confirmed block in the worst case, but when network conditions are good but with Byzantine adversaries. But, the point here is in that worst case, when you when you do finally confirm a block, we're then confirming loads of blocks, right? Everything below that. Right? Okay. Okay, so what's the basic picture there? I guess maybe that's what it sounded like. The overall picture is that so far DAG protocols are basically they're all sort of pretty similar. They're all sort of you can get pretty close to optimal if we're not worried about like

patching and if you're not worried about uh latency or whatever. Okay, then you can get sort of pretty close to optimal. It's pretty close so far. Okay, but obviously communication complexity isn't really what we care about, right? What we really care about is Mhm. So, I'm trying to So, the Bullshark, you said that was optimized version of DAG and your protocol in 2017. Yeah. To describe it, so So, why is it better, I mean? Huh? You're asking why is it better than the the other guy here? I'm not trying to like so, was the second bullet on the Bullshark, like is that How does that compare to How does that compare to the other DAG-based protocols you designed?

So, in the other ones, we we were in a synchronous setting, so there's no worst case, right? So, this this line here disappears. So, here we really talk about this is now deterministic now, so we have a worst case. And the optimization of Bullshark isn't really to change these figures by something like that. This figure exists. Right, the worst case would have been infinite. Yes. Yeah. Well, like what if like you could try to evaluate those protocols in the partially synchronous model, right? And ask about Yes. Right, so then it'll be you'll get the same figure then if you make it deterministic, okay? So, the basically the difference with Bullshark is working very similarly to DAG, but you you manage to reduce the latency.

So, now we don't need the four four rounds. Now, we only need two. So, the argument for liveness changes. Yeah, so so I'm just trying to Let me see where the end of the four comes from. So, it sounds to me like you're saying all of the DAG-based protocols you have this issue that after a long string of Byzantine leaders, you'll have to have like you'll have to like catch up Yeah. with a bunch of confirmations and Yeah, yeah. Yeah. Yeah. Yeah, so that figure will be the same. Okay, so I guess there are quite a lot of figures there, but the basic picture so far is okay, maybe it's all fairly similar for the for the for the DAG and the non-DAG structures, okay? But what we really care about is latency and throughput right?

And I'm saying I I basically there aren't really the the prevailing methods in distributed computing just consider your the main thing is look at your communication complexity. Okay, so it's it's difficult to analyze these things in a rigorous way. So, basically what we have to do is just like you know, run experiments, okay? And then when you're running your experiments, of course you have to make sure you really are comparing apples to apples, right? You mean the same thing by transaction, you have the same internet connection speeds, with the same processors, and so on right? Okay, so as an example, this is the team behind Bullshark compared the performance of Bullshark. So, Task is basically it's like DAG-Rider just with some optimizations involved, okay? So, just think of that as like a slightly optimized version of DAG Rider.

No, no, no, guys. So, DAG DAG Rider works in the asynchronous setting. As does Tusk. As does Tusk. Yeah, yeah. Okay. Okay, and we and HotStuff as well, okay? And what they found, so the following is under good network conditions. We're not Here, everybody's behaving nicely, right? Our network connection is is always is always good and so on, running as fast as possible. Okay, so for HotStuff, you get 50,000 transactions a second for 20 parties, 30,000 transactions for 50 parties, and with a latency of around 2 seconds.

This is all everybody's being good, yeah? All everybody's being honest. Okay, we're now exploring how bad it goes when people are are naughty. With Tusk, we get up to 160,000 transactions a second for 20 or 50 parties. I'm not sure why it's exactly the same. I mean, yeah, and somehow the network wasn't saturated for Yeah, when it's 20. Uh but now, okay, the latency is slightly slightly larger. Okay, and for Bullshark, we're getting 130,000 transactions a second for 50 parties with a latency around 2 seconds. I don't know why they didn't get the figure for 20 parties there. I'm not sure.

That's the figures they get. Okay, so I I don't know to what extent you can take those as being like gospel. I mean, maybe you know, one of them is coded in better than the other one, I don't know, okay? But anyway, so it seems to be the case that they they they DAG protocols are being pretty efficient. And then, were they stress tested under non-ideal conditions at all? Uh I don't think those were included in the party. I don't want to promise. I'm sorry, they weren't included in the paper. Uh I can have a look at later on if they are on the link. I think these numbers are close enough to each other other considerations might be worth using to Yeah, yeah, yeah. Yeah. No, it's just like I guess from this the my basic takeaway is that they They like they're doing pretty well, but there's nothing

definite. They're not me. Yeah, so here a transaction is just 512 bytes. We don't really care how long it takes to execute because all we're doing is because we're ordering them. That means we're like shifting the job of actually executing it to somebody else. Yeah. Yeah. Yeah. Yeah. Yeah, I think they're probably doing this cuz people are just used to talking in terms of uh you know, transaction rate, transactions per second, but yeah.

Exactly. Okay, so just to finish off with then. Okay, so we've mentioned Corda, Minnows, Dag Rider, Bullshark, Task. Basically, these are these sort of state-of-the-art protocols. Uh just go through some some maybe some older protocols. So Hedera Hashgraph, like this is a permission DAG-based protocol. Uh an issue there is it has exponential expected latency in the in the presence of Byzantine failures. Okay, so maybe this protocol is like perfectly good when people are being nice, okay, but if if people start acting badly, then you've got the potentially huge latencies there. And basically, the the reason is that uh they're not using any global coin.

They Everybody just tosses their coins individually, so you're kind of waiting for everybody to just like toss their coin everybody the same way in the same round before you finally agree, right? So you've got a uh potentially very inefficient process then. Uh well, I If you're happy with setting up a global coin, etc., maybe there are maybe there there are issues in doing that. I don't know, but I guess So again, so in particular, Aleph is a version which basically takes Hedera Hashgraph and essentially implements it with a with a global coin, okay? So then you cut it down to uh uh constant expected latency, okay? And you also achieved your your sort of your best possible amortized expected

amortized communication complexity if you're happy to accept batching, which you may or may not may not be. Okay, then Avalanche also uses DAG structure for the transactions. When you add a transaction in, right, it has to point to some of two previous transactions. Okay, and then sorry, I don't know if you're aware of Avalanche, so what you do then you decide on conflicting transactions in the DAG by repeatedly sampling the opinions of other parties, right, and the the DAG structure plays a role in that, because when you sort of vote for a particular transaction there, you also vote for all the other it's a predecessor in the DAG. Okay, so Avalanche requires 70% liveness, and the communication complexity there is order KN, right, where K is a required number of samples.

So, that depends on your security parameters and it depends on N. Okay. And again, so Avalanche provides a payment system, but no total ordering. And then we have some sort of proof-of-work protocols, right? So, SPECTRE is a proof-of-work DAG-based protocol. Again, that just provides a payment system, doesn't provide a total ordering. Uh Tangle is pretty similar to SPECTRE, but in SPECTRE you've got blocks to transactions in SPECTRE. In Tangle you're adding them in individually. Uh but okay, so SPECTRE doesn't provide you with total ordering. So, Phantom and Ghost DAG, that's an ex- extension of SPECTRE, which does give you a total ordering on top of the DAG.

So, would you say that these are actually working now or I don't want to annoy anybody, so Um no, I don't know. I mean, uh no, I don't want to go that far. I mean, I Okay. Okay thanks.