It's All about Trust with Ittai Abraham | a16z crypto research

Transcript

All right. Welcome everyone to today's A16Z crypto research seminar. Very pleased to introduce Abraham who I've known for a very long time. You might know him as the sort of lead author of the decentralized thoughts blog. He was a PhD back at Hebrew University. Spent a lot of time at Microsoft in the Silicon Valley, which is where I first met him. He was at VMware for many years and he recently moved to Intel as a senior researcher. Today he's going to be telling us about why it's all about trust. Ittai. Thank you. Thank you for inviting me and thank you all for coming to my talk.

Yeah, so I'm going to start very high level and then slowly we're going to zoom in and then into gory details. So let's start. So really you know it's all about trust. What is trust and and it's kind of an elusive thing and that's kind of the reason why I'm really interested in looking at it from different angles. Of course the most important angle here is is cryptography and this is this kind of phrase I took from Boaz Barak which is that uh kind of a cryptography is is a way of transforming trust with with mathematics.

And this is one area obviously that we're all interested in and the other one which I care deeply about is a distributed computing. And kind of the intersection between distributed computing and and cryptography. And really there the the interest is how do you kind of replace a centralized model of trust with a decentralized one. Okay. And and these are two really really kind of fascinating topics. I think there's a lot of interleave between them. But obviously kind of the third thing that I'm I'm really interested in is is the economics of things. And and the way I think the way at least I interpret the how economics thinks about about trust.

Again if I had to just do it in one one sentence, it's kind of replaces the assumed model of trust of good guys and bad guys with this kind of question of how can we incentivize cooperation, right? And so this is I guess the reason I'm excited about this area is because of combination of all these three and I would say you know more recently what I've kind of come to realize it's not just these three, it's also this topic of governance. And and I guess to me you know it's governance about how we as a society make decisions and make sure that these decisions are kind of upheld over time.

And in a sense at least my opinion is that a lot of the disruption of the intersection of these three things is going to also go into governance. And here's again one quote I really like from talk that Vitalik gave he says Bitcoin and Ethereum really are digital nations. And so kind of makes you think about you know what are nations and and how kind of in this new world how will they evolve and become. Okay so yeah here's this again and and you know these these four things cryptography, distributed computing, economics and governance.

And I guess my thesis here is you know where where do blockchains you know we talked a little bit about trust. So where do blockchains kind of come up and at least my my high level view is that blockchains are kind of mechanisms for trusted coordination. So you know it's a mechanism. It kind of tries to incentivize things. It creates this coordination. So this is the the way of replacing trust. And really for it to be viable for for a large population actually has to work at scale. And so what we'll talk about you know today is is how to do this at scale I guess.

But before we do I kind of want to start with a little bit of more high level overview. So this is some quotes I really like from Yuval Noah Harari from from his you know very famous book. It's basically you know if you think about what a blockchain is right as a mechanism for coordination. Well it's a story that a society kind of builds right is some fiction that a large group of people believe in. And this is kind of from Yuval's point of view this is maybe the most important thing or the biggest superpowers that we as as kind of humans have over over other entities. Right it's the ability to have kind of a a joint common story.

And in a sense at least I think that that blockchains are kind of a way of providing a much more robust story around trusted coordination. In particular you know Yuval talks about this notion of money right and and money as the only trust system created by humans that can bridge almost any cultural gap. Thanks to money even people who don't know each other and don't trust each other can nevertheless cooperate effectively. And I think that's a really kind of an amazing feat of of of humans how how we can kind of collaborate and and and work together and again at scale.

Okay, so what's this talk going to be about? So this talk is basically going to be about these four three parts right? So there's going to be an introduction about mental model about how I understand blockchains specifically in the context of how to do scale them. How to make them scale and work with you know high throughput and so on. And what I'll talk about is this amazing flywheel that I'll call this decentralized flywheel where where you have ideas that are coming from both theory basically mathematics right and systems. So so academics are building systems and and real systems and and blockchains and they're kind of contributing each one to to the other. And some of the reasons I'm I'm super excited about this type of model um

is you know it's completely permissionless. So so you'll see contributions from many different people with many different types of backgrounds. You don't have to have a PhD. You don't have to be a you know a super engineer. There can be many different types of contributions in this kind of process and that's to me really fun about it and secondly as somebody who spent a lot of effort also looking at the theory side this is really like a fun area in the sense that theory matters here quite a bit. So if you look at say you know how databases work or how operating systems work or how the cloud works. Well there is a little bit of theory and mathematics into that.

But in this case there's a lot more and then that's really exciting for me. Okay, and what we'll do is we'll start with this mental model for for blockchains and then we'll talk about these three separate or you know they'll be they'll be connected and depending on the amount of time and how much questions you have we'll kind of move through them. But one is about consensus and the other one is about kind of DAG-based protocols and finally we'll talk about layer two solutions. Okay, there's a kind of this obvious flywheel I won't talk about which is zero knowledge proofs but it's again it's a huge you know kind of way where theoretical ideas, systems and and real systems are kind of helping each other. And and again it's really important to to note

it's not just a one directional path right? It's you know theory is helping systems and systems helping theory and blockchains are helping systems and and systems are helping. So this is a really fascinating in that sense. Okay so yeah let's start and and before we start I'll just give you kind of a very high level overview of how how you see this whole area of a blockchain technologies. You've probably seen this many times kind of this layered view. The bottom layer is basically doing state machine replication. If you know this picture raise your hand. Good good good. And you know the second one is is about execution. This is where your smart contracts are running. This is kind of the the engine. You probably know this picture right?

The third one is basically the applications themselves right? So what type of applications you want to run. And the fourth thing is basically everything that's off-chain right? And so in this talk I'm going to focus on the two bottom layers kind of the core aspect but it's really important to understand what are the use cases and what is actually the workload because you can't create high scalability in the air. You want to understand what is your workload right? So this is actually we're going to go a little bit back to thinking about these layers. But anyway our focus going to be on these two bottom layers for today. Let's start with with some you know semi-formal definition of Byzantine fault tolerant state machine replication. And and we'll kind of go over this and

you know if you have questions I'll kind of give you a little bit more but but I will you know not do it completely formal right? So I guess the high level idea here is that in the ideal world we'd like to basically build a system where you have clients and these clients are just talking to some ideal system. This ideal system never fails, never has any problems, it's always online, it's always honest and there's absolutely no problems about it. If you think about it that's how you treat say um your laptop or the cloud or your bank account presumably right? So so you know something that never fails right?

The problem is that more and more in this kind of in the world that that doesn't doesn't really adhere to to what happens. In particular there's these three problems that that happen right? So one is lack of safety. So sometimes you know these systems don't give you a consistent state or don't give you consistent state relative to other people. That's kind of one big problem. The other big problem is liveness right? Denial of service. We've talked about kind of you know purely safe couch right? That doesn't make any any changes. So so so that that that also is something that we don't want to do. And more more often or not we actually want think about state machines that actually have some sort of private state.

And these are kind of secrets that are held inside the state machine and we also want to make sure that those don't get leaked out. So so in some context we'll do that. And this is essentially what you know the the holy grail of of of this type of technology state machine replication does. It allows you to build systems through replication. So that even if there's an adversary and this adversary is controlling some fraction of your of your servers. Okay, let's say particular this number F here and there is some fraction of these servers that are compromised. So the adversary can control some of them but not all of them. Again it can be 1/3 1/2 it depends on the kind of the type of model and protocol.

You still want to build a system that from the client perspective looks like an ideal system right? So, they get safety and liveness and privacy. Uh and kind of my my thesis here is that providing this type of service is essentially this mechanism of trusted coordination. So, this is essentially what um you know, if you want to create a a mechanism for trusted coordination, this is kind of what you need to uh provide. Um yeah, so so this is kind of the uh a high-level overview of how I think about um uh a blockchain and its scalability challenges.

So, there's basically four phases. Um and you can see I've kind of played around with the names of these phases and I'm not Maybe you have better ideas about about some of some of these names, but roughly speaking, you know, the first phase is just the phase where the clients have to send whatever they want, the transactions or the operations to the system. So, we'll call all this phase the input phase. Okay, so all the problems of uh making sure that these requests are persisted, right? So, the data availability are here. The the problems of um what happens if there is a you know, two requests and I can sandwich in between them. So, uh MEV, this is all inside kind of the input phase.

Uh the next phase, you know, once we get uh this this input, we want to order these transactions. Uh and and the reason we want to order these transactions often is because we're replicating the system. And in a replicated system, it actually is pretty important that we all agree on the same order. Okay, the reason I you know, I used to write here that this is a kind of a consensus box and not an ordering box um is because kind of consensus implies total ordering. That we're just going to order all the transactions. Um but more recently, you know, we're seeing systems where you just need to order the things that that need ordering. And let's say there are two transactions that can commute between them, it's fine to you know, not completely order them. So, so that's kind of why I'm I'm calling this an

an ordering phase. And and you know, once we do that, now we're actually doing uh the actual you know, business logic, right? This is the value that we're creating. So, the value is actually executing these transactions, right? So, this is the the execution phase. And again, it's a nice way of separating between these these uh these parts. And finally, once it's kind of executed, then you want to uh store it in in in some in some way that's persistent. So, if somebody wants to read it again, it the out the output exists. So, in particular, we talked about kind of some of the challenges here. So, uh the nice thing is that you can really separate out your systems and and think about these as four separate challenges, right? And and by kind of optimizing each one of these things, you can look at your system and see where are your

scalability bottlenecks, right? What part is is blocking you? Uh and try to kind of fix each each one of these in the same sense separately. Um so, this separation of concerns has been kind of very very valuable. Um yeah, so so we we talked about kind of the input phase, the execution phase is is again uh you know, very important. There's a lot of work on different programming languages and and uh you know, how to run things in in a in a efficient way. And what we'll see in the third part of this talk is really that in some sense the biggest challenge of of uh scalability is is getting better execution. And so, we'll focus on on that in the third phase.

The fourth phase is basically about uh uh you know, recording the information and and recording it in such a way that's that's authenticated, right? That people can get a a response that is trusted. And so, all this work on on authenticated data structures and and Merkel trees and so on is all going kind of into this uh uh fourth fourth space. Okay, what I want to start with is is actually just the consensus problem um because uh in in a way, you know, if you kind of ignore this consensus problem, then you just have a regular computer, right? That it just you know, transactions arrive, you have to execute it, and they have to kind of record it back. And so, this is kind of the part about uh consensus. And if you ask people about consensus in particular, the Byzantine fault tolerant version maybe you know, in 2015 or 16, they

would say, "Well, yeah, you can do it, but it's very very slow, right?" And there was kind of this perception that it's not scalable um and very inefficient. And I guess, you know, now there's kind of uh maybe an opposite understanding that it's it's actually in in some sense if you do the right things and the right choices, this is not going to be your bottleneck of your system. Uh and okay, why is that? So, the first thing to to kind of uh talk about is this latency versus throughput trade-off uh when doing consensus, right? So, in a sense, consensus is this distributed protocol that that requires, you know, some sort of agreement between all the servers. Um however, you don't have to do this on each and every transaction. So, you can batch things.

Okay, so if there's a lot of requests coming, then you can basically decide that let's say every 10 minutes you'll batch another block. Or every 17 seconds you'll batch. Or or every you know, 20 milliseconds. And by batching this, what you're doing is you're basically trading off higher latency, right? Because when you're batching a transaction, then it's actually not being committed immediately. It's being waiting It's waiting for a few seconds a few milliseconds. Um but the hope is that now you're actually going to spend less effort because you're doing consensus less often, right? So, if you had to do consensus every 10 milliseconds, um that would be maybe expensive. If you're doing it once per second, it's it's not that expensive. And so, what you're doing is you're basically reducing the amount of times you're running consensus um and you're increasing uh your latency, but the good

side of this is that now you're kind of uh increasing throughput as well, right? By basically doing less consensus. The extreme version of this um which is basically somebody says, "I have amazing throughput." Um and here's how to get amazing throughput. You basically do consensus every hour. Right? I mean, and you will get amazing throughput. And yeah, maybe once an hour you have 100,000 people that have to run a protocol that takes 2 minutes. It's It's still not that bad. I mean, that it's 2 minutes out of your hour. That's not going to take a lot of effort.

Um and basically, your throughput is just going to be bottlenecked by how fast you can input data, how fast you can execute it, and how fast you can output it and record it. Okay, depending on how that that works. So, so in a sense, yeah, be very careful about just talking about throughput because then it's very easy to get very very high throughput. Um however, if you really want to say you know, run consensus every few milliseconds, then yeah, then it then it uh uh then it's expensive. And obviously, the expense is is a function of the the number of of replicas that we want to do, right? And there are again lower bounds and we'll talk about them.

But roughly speaking, you know, the amount of messages that need to be sent is kind of quadratic. At least that's that's the worst case, yeah. I can think of two versions of the separation. One is that there's one system and you're just thinking of the all the aspects separately, but another is like there's just literally different systems. There's one system that does the storage, one system that does the input, one Many of the modern systems that have very high throughput essentially have queues between these systems and they do work and they move it to the other system. And so, you can really think about them as as a you know, a factory, right? And you finish you finish this thing and it goes to this other factory. So, it's like a you know, a pipeline of things that you're doing. Can you think of consensus as a

service? Like take me Yeah, yeah, yeah, all of this exists. All of this exists. So, all of these these are all narrow wastes. It's very easy to you know, replace this consensus and put something else, replace the execution. This is why this is a very nice architecture, yeah. So, all you can definitely you know, say you build a different you know, the these the APIs in between here are very narrow, right? So, if you have a better data availability solution, you can kind of you know, replace it and put it back, right? If you have a better execution engine that runs a you know, a better smart contract language, you can do that as well.

Can you comment on the trade-offs between having this kind of modularity versus a monolithic design that tries to do all of them at the same time? So yeah this this monolithic versus uh is maybe loaded. Um so, I would say you know, there's there's the software architecture, right? And I think that uh from a software perspective, yeah, you can build amazingly good monolithic stuff. Uh and also, you can argue that it's very it's easier to build these things separated, right? So, if you have separate teams. Um so, yeah, I would say it's nice to understand that there's a

logical separation. How you build it uh is not necessarily physically separated, right? I mean, I've seen amazing systems where everything is built together uh and amazing systems where everything is separated. And I use amazing in a good way, but you know, you can also take it as a uh other ways of seeing amazing. Uh yeah. Any more questions about Okay, so so what we'll kind of do is um in in this in this first two two phases is um is talk about the uh the this this uh consensus part and and why it's kind of you know, not so bad as as people think it is. Again, uh sorry, yeah. I forgot I remember I

forgot one thing I want to say. So, the really important part here related to kind of separation of concerns is that when you're running consensus, right? Even if you have a a day's worth or an hour's worth of uh of transactions, what you really are doing consensus on is just a digest of all that work. Right? So, you're agreeing on a cryptographic digest of all that work. In particular, this implies that this input layer gives you kind of this data nice data availability property. Right? So, you know that if you have this uh digest, you know that that you can for sure access the data, but the consensus itself doesn't need to see the data. It just needs to look at the digest. Right? And that's what makes it uh sorry, I should have said that earlier, right? That's what That's what

makes it really uh scalable in the sense that even if we're taking a a day's worth of transactions, we're running consensus on it, it's still just just on one hash. Okay, before I talk about uh anything else, you know, we have to mention Bitcoin and Nakamoto consensus. So, I'll do this really really quickly. You've probably heard me talk about this uh in other contexts. So, and this is not kind of the core thing I want to say, but you know, there's kind of this important separation in my view about you know, who gets to vote and and and how you take these votes and and decide about consensus.

In particular, you know, in Bitcoin, the decision about who gets to vote is is proof of work and the the decision about given these votes, you know, what's going to be the winning transaction, that's that's longest chain based Byzantine fault tolerant protocol in the synchronous model. And and you know, that's very different than modern many modern blockchains where the way that you decide who gets to vote is typically through proof proof of stake and the way where you when you take these votes and you aggregate and decide how things are committed, you typically use kind of quorum based Byzantine fault tolerant systems in in partial synchrony.

And and so, you know, for me at least when I use this type of language then kind of saying comparing between proof of work and and quorum based protocols, I know what that means, right? And and but for me these are like two incomparable things, right? So, proof of work is a way to decide who gets a vote and a quorum based is basically how those votes get translated. In particular, you can run, you know, a quorum based protocol with with proof of work if you really really insisted on it. And then similarly, you know, longest chain versus BFT from at least from my perspective, you know, a longest chain protocol is a Byzantine fault tolerant state machine application protocol. But again, I I understand kind of the the way this is you know, not used using these days.

Okay, and and so, you know, I just want to say one word about why this talk is going to focus on kind of the quorum based BFT and before I just have to say you know, the amazing thing from my perspective again in hindsight about Bitcoin and from my perspective at least, first of all, it solved Byzantine fault tolerant state machine replication, right? That's kind of a in the synchronous model. So, you know, it does everything that we wanted it to do. And the really really amazing thing is it does this without a public key infrastructure and without authenticated channels. And if you think about that, that's for me at least you know, a mind-blowing. Right? The fact that you can reach you can do this thing without having any trust assumptions, without having any previously set channel, without having any public key set up in advance with a

very minimal setup and that's amazing and and in some sense unfair to compare this to these high high throughput low latency other systems because they're kind of assuming a little bit more. And so, they kind of get get more But anyway, to me this is kind of an amazing thing and and the amazing power of having mildly hard cryptographic puzzles and that's where I'm going to stop about talking about Bitcoin and talk about quorum based Byzantine fault tolerant. Yes. Do you think of like the hash ideal hash function as a weaker assumption than the other cryptographic assumptions?

I you'll see that in in all these protocols you do assume there's a public key infrastructure that there's a public key for each of the replicas. So, that's the important part. The important part is how do you build a public key infrastructure? No, but like Bitcoin assumes like an ideal hash function. I I know I'm yeah, it's important I mean, sure that's another nice really cool thing about how much cryptography you're using but from my perspective, like this is the mind-blowing part. The fact that you can do it without any without these assumptions. Like if if somebody would ask me, I would say no, it's probably impossible. So, in other words, it's not really when you talk about PKI, it's not the cryptographic assumptions you're emphasizing. It's the setup assumption.

So, the fact that somehow and who knows why, somehow this work was done before the protocol even started. It happens to be cryptography, but that's not the the main point, right? Exactly. Exactly. Yeah, you could have imagine in some sense um you know, from a even from a kind of a trust liability perspective, right? You just don't have to set up anybody with a public key. And in all these other systems, well, you know, you start with some set of 100 validators. Okay, that means there was some initial set that started the system. Okay, there are other things I can you know, I can say about about why this is also centralizing, but but not for the setup assumption.

Okay, so I'm going to finally start with kind of part one um and uh and and talk about quorum based BFT and you know, let's talk about some hard things about about consensus. So, the first thing is obviously, you know, in in asynchrony, you don't know if you're not receiving a message you don't know if if the problem is that the server is down or that the message is delayed, right? And this is kind of the the hard part and in partial synchrony you kind of have this case where you want to maintain safety always and you want to make sure that you're making progress during phases where the system is kind of synchronous and the problem is that you can't tell between each each of these.

And there's this kind of amazing result by by Leslie Lamport in the in the in 1988 showing how to solve this. So, solving state machine replication in partial synchrony with emission failures. Raise your hand if you don't haven't seen Paxos before. Okay good. So, so I'm going to go pretty quickly, right? So, it's view based and every view there is a there is a elected leader. And basically, what you want to do is you want to maintain safety. And the canonical problem that we're worried about is that there is one leader that basically sends us some value and for some reason this leader, you know, sends the value to some parties and then stops working. That may happen. And then then

the next leader coming in will kind of try to commit a different value. And that is the canonical problem that Paxos tries to solve. Okay, so what is the why isn't this trivial? Well, you know, basically the idea is let's have a leader and the problem is that this leader may fail. If this leader may fail, now the next leader comes in and it might make a different decision. And so, to overcome this, basically what Paxos does is two really really simple things. The first thing is this idea of lock commit, right? So, instead of committing by just sending a message as a leader, I first kind of make sure that my what I intend to commit is being recorded on the network. And that's going to be kind of a lock certificate and the way I do that is make sure that there's at least n minus f people that

receive this lock message before I decide to commit on something. Okay, so this is kind of the idea. Before you commit, you lock, you get n minus f locks and that's your confirmation and we'll call that the the lock quorum. And the second part of this solution is what happens when a new leader wakes up. So, when a new leader wakes up, it actually needs to check whether the old leader did something, already tried to commit or not. So, it doesn't know if the old leader succeed to commit or not, but it wants to be you know, very cautious. If there was any chance that the old leader committed, it wants to kind of use that same value in order not to break safety.

And so, the way it's done is very similar. The new leader also reads from a set of n minus f. Okay, and then what the new leader basically is is hearing is all the previous locks of the previous replicas. And what you're getting here is kind of this quorum intersection property, right? That you know that if you kind of hit two different sets of n minus f, there's there's going to be at least one one replica in the intersection and therefore you're going to you're guaranteed to listen to the to one of these locks.

And then you know, this is kind of where the tricky part comes in. So, this is kind of the the the you know, the only tricky or hard part about about the Paxos is that when you're sending these locks, you have to send the view number of these locks. And if I read from different replicas different locks from different views, I have to choose the lock that has the highest view. Okay, we'll we'll kind of go over why that's the case, but this is the you know, the one thing that Paxos does which is you know, not completely trivial.

So again, you hear you you listen to n minus f different locks and you have to choose the highest one. And anytime anytime you have a protocol that uh tries to do state machine replication and it doesn't have this aspect, it doesn't have you know, it doesn't have to have signatures and and Byzantine fault tolerant, even the emission model, even the simplest case, it has to use this property. It has to somewhere embed this this this protocol. And here's kind of a quote from from from the Casper. This is basically the consensus protocol that Ethereum is using.

So, you know, they say that they construct a novel correct by construction fork rule, follow the chain containing the justified checkpoint of the greatest height. Okay, so the Paxos you know, way of saying it is here is choose the lock with greatest height. So, you know, the lock is basically what a justified checkpoint is in in kind of the Ethereum language and and the highest view would be the greatest height. Okay, so this is kind of you know, a trick if you want to look at at a consensus protocols and see whether they actually are safe or not, the first thing you should look at is whether they're at least doing you know, at least solving consensus like as as Paxos does.

And so, it's nice to see that that this is always the case. I'll kind of just Again, very quickly draw this Can I interrupt with a historical question? Yeah. If this is too far afield, like feel free to ignore. Lamport, like how does that What's the context with that versus Dwork Lynch Stockmeyer? Yeah, so so 20 1988 was this amazing year where Dwork Lynch Stockmeyer was was published, view stamp replication was published and part-time parliament was published.

Um They all kind of you know, so Leslie didn't actually define partial synchrony, that was in DLS, but his protocol actually works in partial synchrony. View stamp replication is is Barbara and Brian's work is very similar to Paxos. So, yeah, there's kind of you know, this often happens in science where there's a a lot of different groups coalesce on very similar thing. But but I would It's enlightenment. Yeah. I see see the protocols themselves are fairly similar. No, okay. So the the protocol this is really this protocol um So DLS doesn't have a a clean Paxos version, I would say. Um and view stamp replication maybe has

something similar but but had some maybe had something that they had to fix later on. So so I think the the Paxos version is is cleaner in that sense and um Yeah. Like what what property of the view are using? Do you need monotonicity of it or just like that there's something we all know and there's some some condition we all know about how to compare Like would it work if we just put a hash random number on each one of them compared Yeah, no. So you you really need some sort of uh uh Think about it as monotonic numbers. You can also do it with bounded timestamps, but uh yeah, just think about it as as monotonic numbers. You you want to know who's early and who's late and you want to use, you know, the

the the latest one. So here it's I'll call it the highest view is the latest and here it's called the greatest greatest height. And synchrony So Synchrony makes makes time meaningful. No. So let So let me let me let me give you the canonical I'm not going to explain the algorithm today. By the way, on Friday we're going to do this, you know, from scratch from zero. So if you want to uh you know, you're very welcome. But but here is like the canonical thing that you should always keep in mind about why this is why we even need this type of of uh right? So So again, we're kind of in this um uh uh partial synchrony mode and and basically there's, you know, n equals three and and f equals one and this is really just about omission failures.

And we're going to have uh let's say three views. So this is view one and and view two and view three. And again, think about these for now as as um some sort of logical views. Maybe there is some way of timing of deciding how they start and end, but let's let's for just for a second ignore that. Uh and so here's here's kind of the leader of of view one. So there's some some leader. Um and it, you know, even though in the first view it doesn't really have to listen, it it it listens to let's say, you know, two different uh it receives two different things and they basically say, "Well, we have nothing cuz we just started, right? We're just we're just waking up." And and this leader maybe, you know, is sending some value. Let's say it's sending the value x.

Okay, so that's that's kind of what it does. And let's say at this point it crashes. Okay, so so uh that's it. Uh and now we have a different leader. So here's, you know, different leader in view two. And it also kind of does a does a reading and let's say, you know, it it reads it it it needs to read n minus f, so that's just two. Two out of three is n minus f. Uh and so, you know, it gets a bottom here and it gets a bottom here because this third one it didn't didn't see this x, right? So this was just sent to and and since it receives, you know, no no locks, it basically uh sends the value uh sends the value y to everybody. But let's imagine that it, you know, doesn't succeed to uh send the value to everybody. It

crashes after two. Okay? All right. Now we're finally in view three. Uh and and here we are and this is the leader of view three and it again needs to read from two parties, right? And so it it it's basically reading uh you know, let's say it's reading from from these two. And it What does it hear? Well, it hears this old value x. Right? This is kind of the the only thing it heard cuz it cuz this this one didn't hear the the new value. So here's this x and also hears the value y. And it kind of needs to say, "Well, it it actually wants to send the value z."

Right? So So but the question really is like what is this leader three do? And so what what Paxos says, right, is that this is not enough information. What you need is not just saying that this is y, but this is y from view two and this is x from view one. Okay, so now we've attached the lock includes the view number. Okay? And now once we've done that, then now we basically look at these two locks. And what we do? Pick one. Pick one.

We We Yeah, exactly. We pick the highest one, right? So we're going to send the highest one. Uh and uh and and this is kind of the uh you know, the one that we're sending and and maybe after we send this the way Paxos works is that we finally get confirmations. Uh and this is when this is when we know that we can commit. This is when we know we can commit y. And then we might even tell this to everybody else. Okay? So So that's kind of how how Paxos works and and these kind of two old views is kind of an explanation of why um sorry, I mean this is kind of uh uh um not yet the explanation. This is just how the protocol works, right? And the thing is that it could have actually been the case

that I I've continued this protocol here to actually commit y. Okay? And that's the reason why it was very important for us to to choose a y over here. Okay, so I stop I stop this execution at this point, but it would it could actually continue on to commit y. And basically in view three I have no idea whether there was a commit of y or not. Okay? And and again, for those who are kind of more uh into this into these points and kind of this point essentially where where there's two locks, this is the point where the system becomes univalent.

And and this is the point where there's a commit certificate. Uh And this is the point where there's enough people that learn. So basically, you know, there's kind of these three phases of a consensus protocol. In the end everybody learns about the decision or enough people a quorum learns. There's kind of a middle phase where somebody learns that happened to commit. But there's actually an even earlier phase where every execution from this point onwards will have to choose y. Okay? And this is kind of the point where the system becomes univalent. We don't know that yet. You You Somebody Not everybody knows that.

Yeah, yeah, you know, it's it's unobservable, but but it's basically, you know, if you're if you're the safety proof kind of goes through that. Yeah. It says, "Let's show me the first view where there was n minus f people that received the lock." And basically you can prove by induction that if you're following this rule all later leaders are going to have to choose y. Because the maximum between all of these is going to be y and every new one is also going to show y, right? So that's kind of the proof by induction. Okay, so that's that's Paxos and and in a sense I want to say uh you know, this is uh what I call uh law of hardness preservation. Right?

Uh no matter how you're going to solve this problem of of Byzantine fault tolerant state machine replication, you're adding Byzantine failures, you're adding cryptography, you still have to, you know, fight this problem. And uh and we, you know, there's not a lot of ways to do that. So this is basically the Paxos way of doing it from 1988 and and uh um Okay, but we still want to look at uh um PBFT and and uh and now we're there's like two new challenges that we have to deal with. Uh one is that the we're equivocating in a view. So So we're kind of uh this is like really about you know, the the 1980s and now we're moving to roughly the year 2000.

And I want to say all the Byzantine fault tolerant state machine replication protocols in partial synchrony or almost all of them uh basically follow this PBFT path. And what PBFT does is takes Paxos and adds kind of fixes to handle malicious or Byzantine behavior relative to omission ones. Okay, that's kind of what it does. And it does that by doing two more things, right? So the one thing it does uh is it handles kind of the fact that maybe if I'm malicious instead of sending y, I will send, you know, y and y prime. So I'll send different values.

And the way that's kind of solved is by having one more round of exchange. So, you know, I'll probably show that on on Friday. Um And uh and this is maybe, you know, what why uh you you see, you know, Casper for example have like two rounds of n minus f of two thirds. Right? So the first round of n minus f is kind of dealing with this equivocation problem causing, you know, making sure the leader is only saying one value. And the second round is basically solving this problem. It's making sure that if there was a commit in view two then in view three we're going to persist that commitment.

Okay, so that's kind of the reason why there's these two rounds and there's their lower bound shows that this is kind of the best you can hope for. And the second problem that you have to you have to fix is you actually actually force the leader to say the truth and choose the maximum lock. If If I'm a If I'm a malicious leader, I might see all the locks and and choose a different lock, right? Ignore the kind of the the the Paxos thing that I'm supposed to do and do something else. And basically, you know, we know of only two solutions, roughly speaking, to this type of problem. One is basically the PBFT approach where I take all the locks and I just send them over.

Okay? And then you can basically check. This is kind of, you know, verifiable computation. Uh I did some work and then you can just check the the same work that uh that I've done. And you can imagine you can compress this, of course, if you need to. That's kind of one approach and and the second option is kind of uh and and the big problem there, big, uh is that now I have to send a message that contains, you know, n different things, right? So it's kind of a linear cost message to send these locks. So in terms of the amount of bits, it's maybe potentially large. Uh and the the the second approach is this is this Tendermint uh approach and again, this is a um uh uh really surprising from from my perspective coming up with kind of this new view change approach.

Uh where instead of uh uh the leader sending all the locks, the leader just chooses, you know, decides what what what is the maximum lock. So does what what Paxos tells them to do and just sends it over. And what each replica does is it just says, you know, "I'll accept this lock if I haven't seen a larger lock before that." So, you know, it seems like a less safe solution. Um but it you know, surprisingly it's actually safe and and we'll we'll see maybe the problem is slightly less life. Why Why can't you fake fake the lock number? It's all cryptographically signed.

So, there's two Yeah, so so this lock this this round over here of equivocation, which I didn't do because I'm not running good at time, is is basically getting you three n n minus f signatures that we're all agreeing on the lock and the view number. I'm missing why you need the n minus f for the first but not for the second like cuz wouldn't they need the n minus f signature to prove that I'm not kind of making up my lock time? Yeah you um part of what this this this protocol allows you to do is to say that when you have a lock certificate you can't invent it because three you know n minus f parties signed on it.

And so if you're worried about faking a lock then it's it's very hard to fake a lock cuz you have to have n minus f out of which at least f plus one parties are honest, you know, work with you. But the only mistake I can do with just hash fun pointers. You you can't change the the they they all have to agree they have to they all have to be in that view to sign on it. Right? So, if you if I'm in view two and you give me something in view four I'm going to say I'm sorry, you know, I'm not I'm not going to sign on it. Yeah. And everybody knows the leader is the view, right? So Yeah. Yeah.

Yeah. Two questions. The first one is in Tendermint they have to wait delta, right? As this is a caveat basically to get it off that thing. Yeah, that's why I just said here maintaining safety and I didn't talk about liveness. That's next slide. Yes. And then the second one is in the omission fault model the lock is basically my what and then the certification is like just a one round of votes whereas in this Byzantine one lock is a two-third votes and next certification is two phases of two-third votes. One What Yeah, one n n minus f signatures.

Yes, absolutely. Yeah, you're right. Yeah. Yeah, it was kind of a planning to do this on a whiteboard but realized that I don't have enough time. So Come on Friday and you'll see it in kind of in the in its gory details. Okay, so I guess this is PBFT. It's amazing. It also has three different versions, you know, the thesis version, the journal version, and the conference version. So, this is the conference version, which is the more practical one. If you're reading the thesis version, it's more complicated as information theoretic. But really, you know, all modern or almost all modern protocols are following this path and doing this. And so again, ask yourself, you know, first of all, are they solving this problem? And then, you know, are they solving the equivocation problem in a round? And then ask yourself, you know, are they actually making sure that

the view change is not being manipulated? So, these are the three things you have to verify to check that that it is working. And And so you know, here's kind of some of the things that happened after that and and I'll tell you a little bit about about this HotStuff work where basically what we tried to do is kind of be eclectic and take the best ideas of of of all these previous protocols. And so we started with PBFT. That was kind of our our base protocol because that's the only base protocol that you can choose in some sense. And then we kind of this very nice uh paper by by Mike Reiter actually showing how you can move from quadratic message communication to linear through through a leader.

And so we kind of used that as well to show that you can take PBFT and make most of it linear. Okay? The only part that was kind of not working for us in terms of linear is is this phase where you have to send all the locks. When you're sending all the locks, you have to send a linear size message. And if you're sending a linear size message to n people, that's kind of a quadratic amount of bits. And so we kind of again took this idea from Tendermint of using the the view change there and just sending, you know, one lock instead of n minus f locks. And and then, you know, the the two other things that that were really important in this protocol is we took these ideas from from from Bitcoin. So, the first is that in in PBFT there was

kind of a stable leader that stayed until we found some fault in it and then we kind of threw it away and and replaced the new leader. And here what we kind of did is said, let's actually replace leaders all the time. So, this is kind of this leader rotation. This is, I guess, epitomized by by kind of Bitcoin protocol where every round there's a new proof of work winner. And the second thing kind of we did, again copying Bitcoin is is is taking a chained approach where we're not just reaching agreement on one decision but on kind of a a a chain of decisions. And so the top hash is actually committing to all the bottom ones. And again, if you kind of are in the weeds of PBFT, they used what I will call array instead of a linked list. And that actually matters. The

details here matter. The final thing that we did is then looked at at this kind of Casper FFG work. And and there there was this really nice observation that you don't really need to have two different types of messages. So, in PBFT there was like a message doing the non-equivocation and then the other message doing the I guess the the view change part. And there was this really nice observation that you can pipeline these and and use the same same message. And so in a sense, at least from my perspective, what HotStuff did is like take all these ideas that were out there and kind of just you know put them together into one one cake and and and bake them.

And so that was kind of the this thing and and and I didn't mention liveness and indeed liveness is still is still a challenge. And uh And here's a sort of a a separate story about responsiveness, right? Again, this is a very nice work by Rafael and Elaine. And and there was kind of a side flywheel about synchronous protocols and about responsiveness. But I guess seeing that paper also made us realize this problem also with with Tendermint and and this with the Tendermint view change, which is that this two-chain type protocols they're good but in a some sense there are cases where an honest leader doesn't make progress. Right? This is this hidden lock problem.

And so to overcome this we kind of came up with one with adding one more round. This is so this is the the three-round HotStuff protocol. And so this is where you get responsiveness and linearity and all these nice properties. I didn't mention of view synchronization here. I do kind of want to say a few words about kind of the short-term hindsight. So, you know, given this work was done maybe five years ago, I would say, you know, there's kind of these two separate types of contributions. Right? So, the first type of contribution is really about you know, the fact that it's linear and responsive. These are kind of theoretical measures.

It would be a it seems to be a good property that if you have a good leader and we're after synchrony that this good leader will manage to commit. And unfortunately, again, there was this hidden lock problem, which I can, you know, we can do on on Friday, where there are some cases where that doesn't happen. And so and so this is kind of this protocol that got linearity and responsiveness, which from a theory side you'll see in the next slide was was very nice. But from a practical side it seems that if you're kind of handling uh you know, maybe 100 validators or a few hundred validators, then then linearity isn't such a big problem. Right?

For for that scale. And and responsiveness also there are so many problems with partial synchrony where you don't make progress just because of asynchrony that like, you know, extracting the maximum amount of liveness isn't it's not clear that that's kind of the the breaking point of these protocols. So, question So, on the responsiveness point so an honest leader may make progress but it still may be committing a block that was proposed by a Byzantine party, right? Yeah. Well, in these pipeline protocols you commit but you're also kind of pushing your own proposal for the next guy. So, making progress is like it's a dual thing. Okay.

I see. Good. So, you're not stuck with some proposal by a previous Byzantine person. You're you're kind of making progress in some sense. You're pushing the system forward. And then this is like like responsiveness shows up twice on the right hand part of the slide. They're very they're different or no? When you say optimistic responsiveness is important, that's the same one. Yeah, I'm hiding here some There's there's like There's other notion where they just like you automatically speed up to the network speed, right? Yeah. So, here's what I'll say and and you'll see this in the next slide. There are like subtle definitions of what responsiveness means and optimistic responsiveness.

What I will focus on is just that using this property you can actually build asynchronous protocols. And I'll and I'll show that in the next slide. So, from a So, I guess my what I wanted to say here is that these two properties were really like great theoretical advances. It's not clear that in practice as of now they're they're they're like the main advantage. And the opposite is that the things that didn't change the asymptotics of the theory. Right? The fact that we're doing leader rotation, the fact that we're doing chaining, the fact that we're doing pipelining. I mean, it improves constants, right? But it didn't change the asymptotics.

So, from a theory perspective, you know less astounding. Those are actually mattered a lot in this space. Right? And so these ideas were actually, you know, used and are used in in many systems today. So, it's kind of, you know, this flywheel where some of the ideas are actually using systems and some of the ideas are used are used in in theory. Um Yeah. Not great. Okay. So, the next thing that happened is is yeah seeing how you can actually use this these responsiveness protocols to to use partial synchrony protocols and build out of them protocols that work in in asynchrony.

And so this goes back to this, you know, beautiful paper by Cuts and Koo 2006. I don't know. I have maybe eight or 10 papers that basically extend the ideas there. And wherever I'm kind of stuck, I just read this paper again. I figure out something else I didn't understand and then it's like, okay, you know, maybe I can you know, do some other things based on my new interest. So, anyway, amazing paper. And and here's some of the things we've done from this work. And so one of them is basically if you have a distributed key generation, then you can actually solve asynchronous Byzantine agreements or asynchronous state machine replication.

Uh and and you can do this kind of, you know, with the optimal message complexity, which is kind of again the theory contribution. Uh but from my perspective, the really important conceptual contribution here uh is that it shows how you can take a partially synchronous protocol and kind of massage it into an asynchronous one. And that was actually something that people didn't know previously to that. Previously, you had like the asynchronous island, which was like strange and using these binary agreement protocols, and then this partial synchrony which seemed more practical. And and the nice thing here is that this actually allows you to take these relatively practical partial synchrony protocols and kind of massage them into an asynchronous one.

What do What do you mean by asynchronous? Like you need to do something, right? That you get you you get liveness even in asynchrony. Like how do you not get FLP? You FLP only says that there is kind of there must exist infinite executions. Um but but their measure can be zero. So in particular, these protocols are using a strong coin, that's your randomness. And what this guarantees is that the time to commit a transaction is in expectation a constant. Okay, so these are constant expected round protocols.

Um that's kind of the best you could hope for. And so in a sense, like FLP is a is a non-problem, right? And given good randomness. Okay, maybe I I should have mentioned this. This is maybe another type of misconception, right? That FLP says you can't do asynchrony. That's not that's not not the case, right? Um Yeah, and and then, you know, on top of that this goes kind of the the this flywheel, right? So we start with these systems and and and blockchain and Casper and then this goes to kind of theory. Uh and and you have these even more amazing results showing that uh again asymptotically you can kind of improve and and get kind of what I'll call free broadcast or or free consensus. You have a message of size order n and takes n squared to commit it. Right? So just sending this message

of size order n is n squared bits. So, you know, if all your work is is order n squared, that's kind of asymptotically free, I'll call it. So that's kind of the one side of using a strong coin. And then there's this side of using a weak coin. And and here I'll even be more hand-wavy, but you know, we have this this very nice work about the no waiting HotStuff. So it's another version that uses a weak coin, again using these ideas of Cuts and Koo, solving asynchronous Byzantine agreement this time without a strong coin. It's a harder thing to do. So you need like verifiable secret sharing and so on. And from that you can build the this distributed key generation. I think Sarah talked about that a while ago.

Uh and and you know, those ideas also kind of brought us these information theoretic versions of HotStuff, and that gives us kind of, you know, information theoretic versions of agreement on a core set. And this actually, you know, in the end actually helped for MPC problem. So a lot of amazing kind of theoretical things actually depended on, you know, using some of these taking ideas from say Tendermint and Casper and and applying them. That's kind of really cool in that sense. Yeah, I I wanted to show you how this works on the whiteboard. I'm not going to do it. So I'm just going to say very high level about how this this connection between partial synchrony and synchrony works. Um and you know, the the problem with with adversaries they may just if the leader is is faulty, you don't

know if it's faulty or or delayed. And so the way partial synchrony works is usually you just give it some timeout. You say, well, you know, if you if I don't hear from you in 5 seconds, we're going to throw you away and start the next view. That's essentially what it does. And the idea in in kind of this new protocol is is different. It's basically saying we're all going to be leaders. So each one of us is going to run a partial synchronous protocol. Uh and each one of us is going to be a leader in its separate bubble, right? So we're just going to run n copies of this protocol. And after a while, we're going to basically choose a random leader in hindsight. So choose that one of us was the actual leader. Pop all the other bubbles and say those didn't matter, those were

decoys. And the only thing that mattered with this with this one leader that we chose. And this is really, you know, a blueprint of how this algorithm works. You run n instances of a single view. This is your partial synchronous protocol. It can be Paxos, it can be PBFT, it can be your favorite version of HotStuff, or whatever partial synchronous protocol you want. Um the the thing that you do need is this kind of strong version of responsiveness, right? In order to get this to work fully in asynchrony. So it's black box if you have that property? Yeah. Yeah. Yeah. Uh And yeah, and that's what you do. You basically run these n versions. You wait until n minus f of them finish and and, you know, that that will always happen because eventually you do have n minus f good leaders. And so this is where you're

using responsiveness to say that you can always wait for these instances. Um and then you choose in hindsight one of these. Um and it's really kind of this magical transformation. Uh you thought that asynchrony is impossible, and you actually just say, well, if I solve partial synchrony, I can just do this and get asymptotically optimal results for for asynchrony. Right? And that's kind of kind of nice. Okay, I want to do this on a but I'm not going to do it in more details. Yeah, sorry. So one more thing is that, you know, about partial synchrony is is really about I would say, you know, at a very high level, I think if you just need to get some system, then any version of these uh two-chain versions, right? Doesn't have to be HotStuff, can be PBFT or

whatever, is kind of good enough. Uh I will focus on mention the Ethereum use case where for them they actually care about this fact that you you have a in every round a leader that's secret, right? So it's hard to bribe. Uh and this leader is only going to speak once. And again, the advantage of speaking once is that it's harder for an adaptive adversary to attack because you know, until I see you speak, I don't know who you are. And after I see you speak, it doesn't matter if I can corrupt you because it's already done. Uh and so again, amazing work done here on on both of these fronts.

But the problem is that when you actually combine this with these pipeline protocols, uh you you kind of end up needing this consecutive honest leaders in order to make progress in order to commit. Okay, so you get all these nice properties of anti-bribery and and good protection. But now in order to commit, you actually have to have, let's say, three or four honest uh parties or leaders uh consecutively. And so the obvious question is, you know, can you actually do this without this consecutive property? And and there are several ways to do this. So one is kind of to build a reputation system where if somebody crashes or doesn't make progress, then we're just going to move them away from the rotation. So that's kind of I think one approach which has its advantages and

disadvantages. And the other one is this new work that that that we have that basically removes this need for for uh um consecutive honest leaders. And I guess, you know, in hindsight, the technique is pretty simple. If you look at all these protocols I just mentioned, you know, they look at commit certificates. They look at n minus f signatures. Uh and so in this protocol, we actually look also on these quorums, but also on single votes. So if you kind of look at more information, you can maybe do more, you know, smarter choices. And and then you can actually have a protocol that you know, even if you have holes in between your honest parties, every honest party is actually making progress in the system. You don't have to have, you know, three of them together to make finality progress.

Okay, so this is what I plan to do in uh less time. And so we'll talk about this this DAG flywheel maybe pretty quickly. So reliable broadcast is this amazing um uh asynchronous protocol. And and these are the properties. And if we had time, I would show you the the protocol. It's it's just this really simple four-line protocol. It's beautiful. If you ever are in this field, you have to, you know, you have to know it because uh when you try you make mistakes and you figure out why why it's wrong. And and there's a whole flywheel here, by the way, as well. So there are systems and and real systems and and a lot of new theoretical results, amazing theoretical results, just about improving this protocol.

Um I'm not going to talk about. Anyway, that's reliable broadcast. And what does this have to do? Well, now we'll talk about how this asynchronous protocol is actually connect to these uh uh directed acyclic graphs. And so again, this is an idea that started with the blockchain space. And from this idea from Hashgraph from 2016. And you know, there were mentioned this idea of virtual voting and and zero message embedding of any protocol. And we looked at it and we kind of didn't really understand why it's interesting and what what should we do with it. Um but but it kind of seemed like a fresh new way of thinking about these protocols, which which looked kind of surprising. And then this next thing that happened is this work in 2019 by the by this Aleph Aleph Zero group.

Uh where what they basically did is they said, well, instead of just building kind of this directed acyclic graph of messages, let's make sure that every time I'm sending a message, I'm actually sending it through reliable broadcast. Okay, so I'm not just going to run a regular message sending, but I'm sending it through reliable broadcast. And the only thing I want you to to see is I'm just going to draw a cartoon of how reliable broadcast looks like. Um so so basically, the leader sends messages to everybody. And then everybody sends an echo.

So this is the echo phase. And after we receive enough echoes, let's say we receive, you know, n minus f echoes, uh we basically send a vote message. This is the vote vote message. And if you receive n minus f votes, that's when you basically say I received a reliable broadcast. Okay, so roughly speaking, again, I'm missing here like an important part, which is if you receive f plus one votes, you also send a vote, but let's ignore that for now.

When I'm sending a message to you, that would be just a direct message sending. But here, I will say I received your message when this happened. I received n minus f votes of people that received n minus f echoes of people that saw my message, right? So this is a There is some non-trivial thing happening here. Uh and and anyway, so the idea here is that we'll use this protocol and build a graph of these things. Okay, what does that mean? That means that if I'm sending one message, here's the message I'm sending I'm sending, right? So this this block basically represents the fact that I sent ran this whole protocol.

Uh and and now, you know, there's if there's n minus f people that that heard this this block, then each one of these blocks is actually a reliable broadcast that says that they heard this previous reliable broadcast. Okay, so this is like a a a graph of reliable broadcasts. And in a sense, that what the protocol says what what this protocol says is just you you build your new block after you hear from n minus f previous blocks. Okay, so you run your reliable broadcast after you heard n minus f other reliable broadcast. If you think about it as as a DAG, it looks really clean. If you try to open it up, actually each one of these things is is doing some

non-trivial thing, right? So so that's kind of a uh and uh um yeah, this is a a total you know, it's a it's a bit heavy operation. It's it's it's n n power three operation. And um and I guess, you know, the amazing thing is that you can do a lot of a lot of protocols inside this abstraction, right? And then this started with this work of of DAG Rider that basically showed that you can embed this uh previous protocols and you know, in particular gather and verifiable uh asynchronous Byzantine agreements, you know, the one that we talked about earlier, you can actually embed this inside this type of behavior.

And you know, the the uh really surprising thing is you can embed this and kind of keep an asymptotically constant costs. So you're not kind of paying too much costs on it. And and this kind of continued and and this work by Narwhal and Tusks showing that not only can you kind of build consensus protocols inside it, you can also do the data dissemination part very efficiently inside that. Uh and you know, this goes on with with with Bullshark which shows that uh not only you can kind of do that, you can build a very nice version of PBFT essentially.

Um uh which all it basically needs to do is to look at f plus one votes in this DAG. And again, I was hoping to show you a little bit more about that. Um but I guess what I My point here is that there's all these new algorithms um that are still have they have to solve these these old problems, right? So they can't they're not doing something completely new, um but they're looking at consensus in a different way by basically looking at this uh directed acyclic graph of reliable broadcast. And that gives them, you know, a lot of abstraction and and and power in that sense. And the cost to do that you know, seems seems a little bit high and there's you know, some work now trying to improve the latency. So it's not completely free doing that. And it's actually a good question, you know, can

you actually take down all these constants and make it make it extremely efficient. Um but you know, the other aspect that I want to highlight is that this is kind of a a scalability bottleneck in the data availability part. Right? So it allows you to kind of run the data availability availability part irrespective of the consensus protocol. And I think in that sense, going back to the separation of four parts, this was kind of uh from me, you know, one of the big advantages of of these DAG rate protocols that they were really cleanly separating the data dissemination part uh from uh from the consensus. I mean, they do it in a way that you couldn't have done with previous paradigms or I mean, everything could have been done, but but hasn't been done, I would say.

Um so the fact that you're doing this the observation that you look at this uh DAG of reliable broadcast and you realize that what it allows you to do is to kind of make a lot of progress in in data availability even if you're not doing consensus. Um you know, that that is explicitly known implicitly known in a lot of I guess PBFT systems, but I haven't seen it you know, explicitly said or used. I see. So you're just saying like piggyback on the reliable broadcast for the data availability basically for data dissemination. Yeah, and doing that and and since it's asynchronous, you don't have to deal with anything, right? So so it's it'll just it'll just run.

And the fact that you're doing this with n minus f means that you're kind of locking everybody's messages together, which is another nice thing. Uh you know, there there are caveats here. Did I have here the caveats? Yeah. So I said here, this is like the caveat here is that it's not directly for clients. So uh if I had more time, I would kind of try to explain this comment. Um basically it this gives you really good throughput uh assuming that every replica has its own set of messages it wants to push. But in the real world, you know, you have clients that want to send messages. And so if each client has their kind of rep- representative, then that would work really well. Otherwise, you know, maybe my representative doesn't work, so I have to send it to all the replicas.

And so now the client is sending the transaction to all the replicas. Now each replica is trying to push it. So now it's getting replicated n times in the system. It's not clear. So in some sense, it's a happy it's a good it's a very good happy path. Yeah. Okay, quite a bit more to say. I'm but I'm going to run and just talk a little bit about kind of the layer two problem. And And why am I talking about that? Because in a sense, I guess my hope is that what you what I want to convey to you is that consensus should not be your bottleneck, right? We have today so many tools, right? To do this in in partial synchrony and asynchrony with a DAG, without, with two rounds, with three, with responsiveness.

And again, it's all inside, you know, it's it's it's doing consensus on the hash. We understand this latency throughput trade-off. So it's still not it's not easy to do, right? And and but but but at least from a architectural perspective, we know about a lot of solutions. And that shouldn't be your your uh scalability bottleneck. I mean, this is assuming you're happy to make data availability assumption, trust assumptions on top of the consensus trust assumptions, right? Uh Well, I mean, going back to the This is going to be maybe next slide. There there are these three other parts, input, execution, output. You have to solve those. So I basically I'm saying, okay, yeah, so you're you're you're you're arguing execution. Yes, I agree.

So so maybe this is the controversial part, right? Uh maybe, you know, you're saying input is also a a hard problem. Uh I'm just saying like I mean, like the old the old school approach of L1s was to actually um kind of reuse the L1 also to solve the data availability problem, right? So it means like a common set of trust assumptions gets you both the consensus properties and the data availability properties you want. Whereas I think in the architecture you're describing, they're kind of I'm going to I'm going to talk exactly about that. Exactly about that. Yeah, so that's good. I'm going to talk exactly about that. And and I'm going to give you a a brief history which is initially, at least from my perspective, how historically Ethereum has thought about this or you know, some some of

what I've heard from from from Vitalik and and crew is, you know, initially they said, let's just build sharding inside our L1. Uh and the problem was, you know, it seemed too complex. There were kind of security problems that we can talk about and maybe, you know, centralizes a lot of the lot of the work. And the next phase of evolution was like, okay, Plasma's going to save us. Uh you know, extend kind of uh uh lightning or payment channels to kind of generic execution. And what they realized at that point is that what what is really a challenge there is data availability. So by pushing both the execution and the data availability outside of L1, you're now kind of creating a problem where if I want to complain against this uh you know, Plasma operator, I don't have the data. And so that was the that

was the problem. And this is kind of where uh rollups came into play where the idea is that we're just going to push the execution off-chain and keep the the uh data on-chain, right? That's kind of the the high-level idea. Um and uh you know, the the good thing here is that uh it kind of creates an ecosystem of competition between different rollup providers. Uh and it kind of solves the main bottleneck of execution, right? Which is as an L1, you don't have to do the execution yourself. You can have somebody else do the execution. Um but you're still kind of doing the you know, the input uh and the you know, the the recording of of the data. Uh and and that's something that you still have to solve, right? This data availability thing. But

uh again, there are nice ways of making sure that an L1 can actually scale to quite large amounts of data availability. Okay, so here's kind of, you know, in in in a few pictures how these schemes work. And I think there's a lot of uh interesting design questions and improvements that can still happen, right? So this is like the caricature version of of what a sharded system looks like uh in you know, if you have basically large machines, right? So this is like you have a large machine, it has, you know, 128 cores or or whatever. And uh and now what we're going to do is we're just going to do input and ordering, but when we come to execute because that's our bottleneck, we're going to split our workload into a lot of cores and we're going to try to run that.

Okay, obviously as you know, the the the problem there was uh uh you know, now you have these heavy validators and maybe you want to have uh smaller validators to you know, to uh make it easier for more people to audit the system. And so that's a that is a trade-off, but I think it's a this is an interesting uh design spot that maybe uh you hasn't been completely um covered. And maybe the evolution of that is to use uh optimistic concurrency control. Right? So one of the problems in this design is you have to make sure that everything runs in the same amount, right? Because in a sense, you have to wait till everything is executed. So if you have even one thread that's very slow, you're going to be as slow as the slowest one.

Uh and so kind of in this design of optimistic concurrency control, what you can do is actually uh choose uh you know, to optimistically run until you get some some point in time, and then you can stop it and you can order all these things. And And then sure, the execution has to do a little bit more, has to check that there's no conflicts between these separate threads um or do some you know, more smarter thing like re-execute some of these transactions. Um but that's going to roughly speaking the the idea of uh vertical scaling with with optimistic concurrency control. And obviously, you know, the next phase of that is is horizontal scaling. Uh that's done by just simply having, you know, several systems. Uh but you can actually think about one system that is designed in such a way, right? That has basically multiple subsystems. And

And now you have this problem of now where do you take your security, right? So you have n parties, you have to have each party be in one of these shards, not in all of these shards. Uh okay, you want to move them around cuz you don't want to make, you know, each one of each of these shards now has less security and so these are all these challenges in in in horizontal scaling. Um and so, you know, the next phase that came in is kind of these payment channels and this is kind of again the caricature of a payment channel where the only thing that's happening in the layer one is basically exiting and entering, right? Roughly speaking again, unless there's a a complaint, then basically, you know, you just enter and exit here and all the work is done in layer two.

Um and and as I mentioned earlier, the problem was that since data availability is happening here, when I want to complain against this operator, I have to show proof that this happened and since all the data is happening inside this operator, this is kind of a somewhat of a challenge. But but, you know, again, maybe this ideas can be revisited and and re-looked at. Yeah, and so this is kind of how how rollups look today. Yeah. Data availability in L1 is easier because I can become a node and then I can access to the data. Yeah, so presumably this the L1 security is much higher. So, the risk of of like a complete failure in the L1 is is is small, while in in the L2 you

don't you know, you're willing for it to be completely failed and you still want to maintain uh safety even if L2 completely fails. Right? That's kind of the, you know, I guess high-level view of how rollup is viewed from a layer one perspective. So, from a layer one perspective, uh layer twos are basically optimistic executions, but if they fail in terms of safety, then there is a way of recourse. And here the problem was that there was none because I didn't have the data. And so, that's kind of the next evolution of this thing, which is to basically make the data be available on

L1, but run the transactions on on layer two. And okay, depending on whether you're doing fraud proofs or or zero knowledge to to make this execution this validation very cheap. Okay, and that's kind of the roughly speaking the the idea. And what we're seeing here is kind of this evolution and and part of this evolution is is happening because of the the time it takes, right? So, this goes back to the throughput latency challenge that we talked about earlier. So, this gives you a lot of throughput cuz you can just, you know, if you want you add another layer two, you get more throughput, but the problem is is um latency here is kind of recent comment by by Vitalik basically saying, you know, that for fraud proofs it actually takes a week, right? To to reach finality. And today in zero knowledge proofs, you

know, even the best ones take a few hours, right? Maybe it'll improve over time, but you know, if I'm buying an ice cream or something, then it's hard to say, you know, just wait a few hours, right? Um so so you really want to to, you know, there's kind of a motivation for a layer two operator to say, I want to provide you some immediate response. And so, the dynamic that is happening is that these layer two providers are actually now becoming full a full blockchain, right? So, they're saying, well, maybe we'll also do some data availability, right? We'll provide you data availability. Um so, if there's a problem, you know, you can go and check it and we'll also maybe do some sort of consensus so we'll decentralize the sequencer. And this is kind of an interesting dynamic happening and I guess what I want to

comment to this is I guess the comment that I'm going to skip just because of lack of time. But but about, you know, what are the security properties of of layer two from a layer one perspective. So, from a layer one perspective, you know, I I don't need you to do data availability or consensus, right? Because I'm just going to do it, you know, I'm going to take care of that myself. Um but, you know, maybe this layer two operator is saying, I want to let give my clients, you know, better service in some sense. And this is kind of my point about asymmetric trust. So, I guess what you know, this is again beautiful area of research and this nice flywheel around asymmetric trust.

I won't go into detail about these this work. There's work early work in MPC and then Stellar and this very nice work by Christian Cachin and Tackmann showing how you can basically build systems even if we don't all agree on who we trust, right? Let's say, you know, I I assume that some some of these some some some of you are trusted and some of you think that other groups are trusted and so on. If there's a a good enough core, we can actually do some things. And and at least in my view, something around that is happening also between layer ones and layer twos. Right? So, they're basically saying some clients will say, no, I just trust layer one.

So, I'm going to wait either a week or a few hours. And maybe some other clients are going to say, no, you know, my trust assumption is that if it's actually final on your layer two, I'm going to trust that that's okay and then, you know, here's here's the ice cream. You can go and eat it. Okay, yeah, and I'm going to skip that and and say thank you. So, about the layer two um kind of think of banks are kind of layer two in a way. Like money is held by the Federal Reserve. Like but when I use my bank account in Bank of America, like, you know, I just have some something for them.

But I think of this is probably okay cuz like, you know, they they tell me something, I can go to court or whatever and get So, why can't I What am I missing or why can't I just do something? are systems that are designed without having a fallback court mechanism. And so, the problem is what if your bank says, you know, you said you had a bank account? We're sorry. We looked and you don't. There is none. And so, what do you say? Like you say, hey look, you you sent me this by mail. They're like, no, we didn't sign this. This is like you made this up.

So, this is the data availability problem, right? The data availability problem is you you go and you say, I have an account. They're like, we don't know what you're talking about. So, the idea here is that, you know, you're going to post the the fact that you have an account or the fact that you're making transactions on layer one, but the actual running of the execution, that will happen in your, you know, what you call a bank, right? And that's kind of the layer two approach. The way that I would take it to the layer two space is like somebody will open the layer two and say whenever I process something, I won't give you the my full state or anything like that, but I will give you some signed message that you can take to a smart contract on layer one and take your money back or

some kind of guarantee. Yeah, yeah. So, you're trying to solve like things that that plasmas That's kind of lightning network. So, so yeah, so so it's good until you're managing like a million people and I mean or you have a lot of customers and then yeah, maybe I lost these messages or so on. So, now I have a now like data availability is dependent on me and I need to be able to prove something relative to everything you did in the bank. It turns out to be non-trivial. I mean, that's the reason why this plasma approach was kind of uh unpreferred. And I guess it's also because layer ones realized that it it is not so hard to get very scalable data availability, right? So, this is a feature that they can provide. Maybe this was kind of the one slide that I missed here.

There's is actually interesting question here where will the value be captured between layer one and layer two, right? What what's the kind of power dynamics there? And in some sense, that goes back to the workload. If the workload such that there's very little cross L2 transactions and you can like live very happily inside your layer two, then maybe you can argue that most of the value is going to be captured there. If a lot of what you're doing is actually moving between things, then the layer one is actually going to allow you to be the superhighway of moving between different different layer twos. And then presumably a lot of the value is going to be captured there. So, it's it's an interesting question. I mean, I don't I don't It's hard for me to predict where how the dynamic will go.

All right, thank you.