00:06: Anna Rose: 


Welcome to Zero Knowledge, a podcast where we talk about the latest in zero-knowledge research and the decentralized web. The show is hosted by me, Anna.


00:18: Fredrik:


And me, Fredrik.


00:26: Anna Rose:


Before we start on this week's episode all about Consensus Algorithms, I want to say thank you to this week's sponsor, Matter Labs. Matter Labs is the company behind the first zk-Rollup prototype, as well as the team behind zkSync, a user-centric Ethereum scaling solution secured by zero-knowledge proofs. zkSync can be used already today to transfer high volumes of Ether and ERC-20 tokens at low cost, with no trusted party involved. Soon, smart contracts will also be possible on zkSync. This is made possible by Zinc, the Rust-based zero-knowledge programming framework developed by the Matter Labs team. The zkSync testnet is live, and they invite you to try out its simple and intuitive user interface at zksync.io. We'll add the link in the show notes. Security audits are currently underway, and once completed, zkSync v1 will launch on the Ethereum mainnet. So thank you again, Matter Labs. And now here's our conversation with Ittai Abraham, all about consensus algorithms.


01:35:


So this week, we dig into consensus algorithms. And we have a guest, Ittai Abraham, from VMware Research to help us chat about modern distributed consensus systems. So welcome to the show.


01:48: Ittai Abraham:


Thank you so much for having me, Anna and Fredrik.


01:51: Anna Rose:


Cool.


01:52: Fredrik:


Hey, hey. Yeah, excited to dig into this topic and talk about some of the work that you've been doing. As a primer, we have had a couple of episodes on this in the past, and most notably with  Robert Habermeier from Parity talking about sort of basics of proof of state consensus algorithms, sort of modern consensus algorithms like PBFT and Ouroboros and whatnot. So if you want sort of pre-listening material to this episode, you can go listen to that. So let's dig in with you, Ittai. What is the work that you do and what got you into this field? What got you excited about it?


02:33: Ittai Abraham: 


Yeah, so I'm a computer scientist, and I do work in algorithms and distributed computing. Been working in the area of distributed computing and consensus protocols for over 20 years. What I really am fascinated about, especially in the area of consensus protocols, is that this is such a simple problem. It was formulated back in 1978 by Leslie Lamport and co-authors. And you'd imagine that such a simple problem would just be solved, and then people would move on. But what it seems to be happening is that every decade there's more and more work on this fascinating problem. And in some sense, what we're seeing now is that consensus is kind of the backbone for all these blockchain technologies and infrastructure.


03:17: Fredrik:


There's something that we've never really dug into, which is the original formulation of that problem. So if we talk about consensus, there's obviously, like you and I can agree on something, but there's a global consensus and then we have Raft-like consensus, which is not Byzantine fault tolerant. And then we have Byzantine fault tolerant consensus, which I think many people's first time hearing about this concept at all is proof of work, and how that supposedly achieves that. But like you said, it's an old formulation and the Byzantine thing actually comes from like a Byzantine generals... Imagine there are these generals and they need to agree on who to attack, maybe do you know that formulation by heart? Because I think it might be interesting to just set the set as a primer.


04:11: Ittai Abraham:


Sure. So you can think about the simplest type of Byzantine agreement where there's a bunch of generals that have to reach a decision. You can think about this as a binary decision. So they have to attack either at 8:00 or at 9:00. And some of these generals are actually controlled by a malicious actor. And if all the non-faulty generals succeed to attack at the same time, then the attack succeeds. If the malicious generals manage to create disagreement, then some generals attack at 8:00, some at 9:00, and the attack fails. So really it's about these very simple properties. The first property you want is that everybody agrees on the time of the attack. The second thing you want is that actually people reach agreement. This is the finality property, right? You're seeing some systems that just never reach agreement. So that's bad too, because then, it'll be past the time to attack. And these two things together are actually quite easy to do. We can all kind of default to decide that we always attack at 8:00, we never attack at 9:00. So the third property is this validity property, which basically means if all the non-faulty generals want to attack at 9:00, then that must be the decision. So the validity property is basically that if everybody wants to have the same starting time, that's going to be the starting time.


05:27: Anna Rose:


In that original concept, is there a percentage that one must reach, or is that sort of dependent on the system?


05:35: Ittai Abraham:


Right, so in a sense, reaching consensus, if there's no failures, is easy, right? We all just say what our value is, and maybe we take the maximum value or the majority value. So really, the problem is reaching consensus in the face of failures. And this is where you introduce a failure model. So whether it's, Fredrik, you mentioned Raft, where the failure model is just that some machines can crash or misbehave in terms of missing messages, or this Byzantine model. So in the Byzantine model, the assumption is that some of these parties can act maliciously. They're trying to... They can send different messages to different people, they can cheat and lie in order to cause disagreement.


06:16: Anna Rose:


So in that sentence, Byzantine fault tolerance. So the fault is this failure, I guess. So Byzantine is the generals, fault is the failure.


06:26: Fredrik:


Yeah, when we typically, when we say a Byzantine fault, it typically just means that it can do whatever it wants. It can... You know, it can lie. Whereas in a, like you said, in a Raft type of fault, the server goes down, but it can't say something that it... Like it can't lie, basically.


06:46: Ittai Abraham:


Right. So the first thing you do is you define the question, right? Consensus. And then you define what is the power of the adversary, whether it's Byzantine, malicious, or just omission or crash. And then it really depends on your network model and how large your adversary can be. So if the adversary can be, let's say, more than 50% of your world, then you have this split-brain attack. If the adversary is more than half, then you will never know who to believe. You're gonna probably believe that the adversary controls more than half of the world. So there has to be some limits on the size of the adversary. And this is where this ratio comes into account. So in different types of network models, there are different ratios of how many Byzantine failures you can withstand and tolerate. This is where the Byzantine fault tolerance comes into play.


07:38: Fredrik:


So as you said, this has been an area of research for many decades. I think PBFT was published somewhere in the 90s… Late half of the 90s. How have you seen this space evolve over time?


07:53: Ittai Abraham:


Yeah, so I think there's definitely been two phases. One is a phase where theoreticians, people who do theory of distributed computing and theory of cryptography have published papers in this area. And indeed, I think it's 1999 that PBFT was published. And this was a kind of major milestone because it was not just another amazingly good protocol. It was also a system that was built. It was built by Barbara Liskov and Miguel Castro. Barbara Liskov is a Turing Award winner and her Turing Award was about software abstraction. So the Turing Award is kind of considered the Nobel Prize of computer science. And so this was a very well architected system in the sense that it had very clear separations between layers. There was a clear layer of consensus and a clear layer of state machine replication.


08:47:


And so I think after 1999, there was this surge of systems research into Byzantine fault tolerant systems. I remember in 2008 being in a workshop that was focused on Byzantine fault tolerant systems in the real world. As you all know, this was the same year that the Bitcoin white paper was published. And the high-level theme of this workshop was we don't have any use for the Byzantine Fault tolerant State Machine Replication. So this was essentially after 2004, where the Raft and Paxos type protocols, so Raft wasn't invented then, but Paxos, which is essentially a very similar protocol, was used in many large companies. So Google, Yahoo, Microsoft, Facebook, all these companies use Raft and Raft-like protocols, Paxos. And this was a conference trying to say, well, let's use it for the next thing. And this was 2008, I remember that the conclusion was we don't know what the good use case is.


09:51: Anna Rose:


That's wild. Because I mean, when we talked to some of the zero-knowledge researchers, we hear similar stories about the early 2000, not years from when they had this really cool thing, but there were so few use cases at the time.


10:04: Ittai Abraham:


Yeah. I mean, to me, I think it's this realization that consensus is kind of fundamental to disruption. So there's this famous saying by Marc Andreessen that software is eating the world. And we've been seeing software disrupt a lot of industries, retail and artificial intelligence today is another example of how software is changing the whole landscape. With this COVID pandemic, you're seeing that education and a lot of things are moving online. So software is even more important in that sense. But what we really are seeing now is that software is eating the way we are governed and software is eating how money is defined. I think this is the disruption that we're living in, where even though technology has made a lot of changes in the last 50 years, I think the way we're governed, the way that nation states operate in this first quarter of the 21st century is pretty similar to the last quarter of the 20th century. Not a lot has changed. I think what we're seeing here is that this technology is making this change and consensus is kind of the backbone of a lot of that. It's an enabler for trying to disrupt these new areas.


11:16: Anna Rose:


Did you already see its potential when you started researching it, even though there weren't these big use cases? Or like, why were you interested in it?


11:25: Ittai Abraham:


Yeah, so I remember in 2014, I read this article from the New York Times. Again, this is Marc Andreessen, Why Bitcoin Matters. And in this article, he's actually saying that Bitcoin is the first practical solution to the Byzantine agreement problem. And I remember reading that article and saying, this is what I do. I do research in Byzantine agreement protocols, and here's a VC writing in the New York Times telling me about something that I've never known about. And I read this thing, I said, he's obviously wrong. And it took me actually a while to realize that this is indeed a huge disruption and a major breakthrough in Byzantine agreement protocols.


12:07: Anna Rose:


But what were you into before? What did you see it for before?


12:12: Ittai Abraham:


Oh, I think I had basically a passion for mathematics, for algorithms, and I believe that decentralized and distributed algorithms are important because they give you the fundamental ability of fault tolerance. So as you know, the world has failures and so handling failures seems like a critical thing to do. But it was for me more a mathematical curiosity, at least early on in my career.


12:39: Anna Rose:


And then at this time though, so once the Bitcoin puzzle piece clicked for you, that was when you maybe realized that this work wasn't just cool math. I mean, I'm sure you thought it was more than just cool math, but like...


12:52: Fredrik:


Kind of almost goes from foundational research to applied research.


12:57: Anna Rose:


Yeah.


12:58: Ittai Abraham:


Yeah, I think it took me at least another year to kind of understand that Nakamoto Consensus, which is the Byzantine agreement protocol that Bitcoin and Ethereum and all the proof-of-work protocols use, is one instance of this larger field of Byzantine agreement protocols. And you can use... You can add finality gadgets to them or you can build other systems that use different types of Byzantine agreement protocols. And I guess these different types of Byzantine agreement protocols are the ones that I was more interested in and I was studying for a while.


13:30: Fredrik:


I just wanted to shoot in a question here as well, talking about applications and use cases. And that is that you're working for VMware Research. And I can imagine why VMware would want consensus protocols because it deals with orchestration, distributed systems and VMs potentially. But why Byzantine agreement protocols? Yeah, I don't know how that fits into VMware's roadmap.


14:01: Ittai Abraham:


Yeah, so if you think about VMware, VMware is IT infrastructure provider, right? So technology infrastructure provider. So it typically provides enterprises with compute infrastructure, with storage infrastructure, and with networking infrastructure. And the high level belief is that in the future, people will need a trust infrastructure. So just like today, kind of your basic compute is compute storage and networking, in the future it will also be trust and decentralized trust in particular. Pat Gelsinger, my CEO, he said that he believes that Bitcoin blockchain technology is as important as public key technology. Right, and just like today, you couldn't imagine the internet without a public key infrastructure. I think in the future, it'll be hard to imagine kind of the future of the connected world without this decentralized trust infrastructure.


14:58: Anna Rose:


So let's dig in a little bit to consensus algorithms. Maybe a starting point would be to talk about like, I think we can now talk about consensus algorithms in the context of blockchain. I think we've understood now like where that lands. But you've said in the past in sort of other talks and in articles about you've talked about this layered view of blockchain. Maybe we can talk a little bit about that. I'm curious to hear if your layered view is similar to other layered views that we've talked about with other guests on the show.


15:30: Ittai Abraham:


Yeah. So, I think this is kind of a realization that we had around 2016 that this blockchain space can be separated into layers. So the bottom layer is consensus, a state machine replication in particular. That's layer one. The second layer is a smart contract layer. That's where you have either Bitcoin script or EVM, WebAssembly, and so on. Zero-knowledge technology can also be inside the second layer. The third layer are these applications that are using smart contracts. And we're now seeing fourth layer. Fourth layer is kind of a user interface. So this would be your wallets or your apps on the phone. You can think about them as a secondary client that talks to this third layer, and this third layer is talking to layer two. And yeah, I mean, I think what we realize is that this abstraction is essentially following Barbara Liskov's vision of how state machine replication should look like. So in that sense, this is work from the early 2000 of Barbara Liskov, Miguel Castro, Rodrigo Rodrigues, showing how you can view state machine replication as kind of a layered abstraction of technology. And what's quite amazing is that any type of project that I meet in this space, I can usually map it to either one of these layers, or I can separate the technology into each one of these layers.


16:55: Anna Rose:


I'm going to throw a little extra point in there because in our episode with Dan Boneh, we actually talked about Layer 1.5, which is the layer that works in between the smart contracts and the consensus level. And what goes in there are some of the scaling solutions using zero-knowledge proofs like rollup.


17:14: Ittai Abraham:


For sure. Yeah. So, I agree. There is kind of an additional technology and we'll be happy to talk about how consensus and state machine replication, even though it's fundamental, it causes these huge problems for a system. And then you really need zero-knowledge techniques and technology to overcome some of the problems that essentially consensus brings you. And I guess that would be kind of a layer 1.5. So in that sense, I think Dan and I definitely agree.


17:43: Anna Rose:


Cool.


17:44: Fredrik:


So as we're talking about consensus, I think one of the most important things to have clear in your mind of what a consensus algorithm does and how it works is what are its synchrony assumptions. So there are synchronous consensus algorithms, asynchronous ones, fancy partial synchrony models in newer algorithms. What are these concepts and sort of how do they work in consensus?


18:09: Ittai Abraham:


Right. So again, the goal in these protocols is to get fault tolerance. And so fault tolerance against an adversary that can cause harm to both the parties in the protocol, but also to the network properties of the protocol. And so these network models basically try to confine how powerful the adversary is relative to the network. And so the most extreme model is the asynchronous model. So in the asynchronous model, the adversary can basically delay any message between any two parties any amount of time. So this is kind of the extreme denial-of-service adversary. It can do whatever it wants and delay messages. You can send a message and it can delay it for a month.


18:55: Anna Rose:


Why is that even a model then? Like it just sounds like a really dangerous setup in the first place.


19:01: Fredrik:


But that's what you want. You want to model things, like that's the goal, right? Is to be as tolerant as possible.


19:08: Anna Rose:


Oh yeah.


19:09: Ittai Abraham:


Exactly. So people said, what is the worst thing I can imagine? And I want a protocol that actually works well in this model.


19:16: Anna Rose:


Ah, okay, okay.


19:17: Ittai Abraham:


And so it turns out that there are fundamental lower bounds. So for example, you cannot solve consensus in the asynchronous model without using randomness. So deterministic protocols will always fail. So asynchrony is actually a pretty hard model to work with. Even today, we don't have good asynchronous Byzantine agreement protocols that work well in practice. I can tell you a little bit about some of the cutting edge research in asynchrony, but I guess, this is kind of the reason why people looked at the other side of the spectrum. So the other side of the spectrum is to say, instead of assuming the adversary can delay messages arbitrarily, there's kind of this fixed known bound. Let's say this bound is two seconds. And so basically the adversary can delay messages, any message, but no more than two seconds. So it can send the message immediately, it can delay it by a second and a half or at most two seconds.


20:12:


So that gives you some control over your world. You know that if a message didn't arrive after two seconds, then probably the other side didn't send it. And so this is kind of this assumption of synchronous protocols. For example, if you look at Nakamoto consensus, this is the consensus protocol that Bitcoin and Ethereum and all the proof of work blockchains use, they assume synchrony, right? They assume that once you have a solution, then this solution will arrive in a bounded time so that everybody can use this hash solution. And so there are these protocols that use synchrony. Traditionally in the enterprise world, people try to avoid assuming synchrony. And so they try to come up with a model that gives you kind of the best of both worlds. On the one hand, you don't have to always assume that you're working in an extreme version of asynchrony. On the other hand, if the system is relatively stable, then you can get reasonable types of performance.


21:14:


And so this is this third model of partial synchrony. And partial synchrony is a famous model from 1988. Dwork and Lynch Stockmeyer, a great paper, which already has their Byzantine agreement protocol for partial synchrony. This same year, 1988, was a huge year for the theory of distributed computing. It's the same year that Leslie Lamport published Part-Time Parliament. This is the famous Paxos Protocol. And it's the same year that Barbara Liskov and Brian Oki published Viewstamped Replication, which is another protocol like Paxos, and it's a precursor to PBFT. Back to partial synchrony. The partial synchrony model basically says that there are two phases in the world. In the first phase, everything is asynchronous. And then there is kind of this unknown point in time where the system becomes synchronous.


22:07: Anna Rose:


Is that dependent on how many are participating or is it just like a timeframe, like an arbitrary time frame that's set but not shared?


22:16: Ittai Abraham:


Yeah, so it's basically a promise in the adversary model that eventually something good will happen. What it's trying to model is the fact that you may have bursts of asynchrony, but most of the time your system is synchronous.


22:31: Anna Rose:


Is the partial.. Like on that scale where asynchronous is the most difficult to make safe, is partial on the other end of that or is synchronous on the other end of that? Like what does partial end up in the middle? I'm kind of curious how that falls.


22:49: Ittai Abraham:


Great. Yeah, so in a sense, you use the word safe and that's exactly the right term to think about, because as you remember from the single-shot consensus, there are two properties you want to maintain. The first is safety. The fact that we never decide on different values. And the second is liveness, is the fact we actually reach a decision, right? There is finality. And so what partial synchrony says is that essentially safety is always maintained. So safety will be maintained even if the system is asynchronous. But you're only guaranteed liveness, you're only guaranteed finality when the system is synchronous. And this turned out to be a very good trade-off in practice. So basically says, even if there is this extreme denial of service, we're gonna be always safe. And when the network kind of reaches some sort of reasonable state, then we can try to make progress.


23:43: Anna Rose:


But does that put it on the other end of that scale that I'm thinking of, or is it sort of, there's three different levels and each one of them offers different benefits to one of those levels? Like I'm just curious if you can think about it along a spectrum or if you should be thinking about them as separate things.


24:01: Ittai Abraham:


Partial synchrony is definitely in between synchrony and asynchrony.


24:05: Anna Rose:


Okay.


24:07: Ittai Abraham:


Right, asynchrony says the adversary can delay messages arbitrarily, and synchrony says that it always be bounded, and partial synchrony says, well at the beginning it can do whatever it wants, and later on it is bounded.


24:19: Anna Rose:


Got it.


24:20: Ittai Abraham:


So I think in that sense, it gives you a good middle ground to model protocols. 


24:24: Fredrik:


And I think what's important to keep in mind is it's not at a fixed point along that axis. If we see the opposites as asynchronous and synchronous, partial synchrony is somewhere in between, but not necessarily always in the same spot in between. So like you said, the model is sort of let's assume a spike of asynchrony. What does that mean? Well, it probably means that someone is DDoSing your system. You're being... You're under attack and under attack you are asynchronous and you're supposed to survive that attack. But the assumption is eventually you will survive that attack. The attacker will eventually stop attacking, and then you're back to a synchronous model and you can continue. So it's not like you're right there in the middle or you kind of, it depends on the network conditions on the attack scenarios and everything else.


25:15: Ittai Abraham:


Right. And the fascinating thing are the lower bounds. So in a synchronous Byzantine agreement, you can handle any minority. So 49 percent malicious actors. But in partial synchrony, you can only withstand less than a third. So 32% malicious actors. And so this is kind of this trade-off of saying you either can handle a lot more malicious actors, let's say 49%, but denial of service, a complete denial of service might cause you to lose safety or you're saying, I'm willing to say I'll never lose safety, if there's a denial of service attack, but then I can only withstand a third malicious actors.


26:00: Anna Rose:


And it's interesting because some of these percentages or ratios that you're sharing start to sound like some of the consensus protocols that we've heard of coming, I guess we're going to talk about coming from those.


26:13: Ittai Abraham:


Yeah. So I think you're absolutely right. Traditionally, both for crash failures and for Byzantine failures, people have used partial synchrony. And examples of those protocols are PBFT or new ones like Tendermint, Casper, HotStuff.


26:32: Anna Rose:


Cool.


26:33: Ittai Abraham:


Always can only reach one third failures, right? They can't do better than a third. So the difference here is, that is between synchrony and partial synchrony. Now what partial synchrony allows you to do is it allows you to make progress at network speed. So every time you reach consensus, you don't have to incur a timeout. You can reach consensus as fast as your network allows you to. And so that can give you much better rate of doing multiple consensuses per second, versus these synchronous protocols. And proof of work is a good example, but I think DFINITY is another example of a blockchain project that is trying to use synchronous Byzantine agreements. These protocols at least have to incur a delay, a fixed delay every time they reach consensus.


27:24: Anna Rose:


You mentioned you used the term single-shot just before. What was that? What does that mean? 


27:30: Ittai Abraham:


Yeah. So in consensus protocols, in the theoretical frame, you can just think about reaching agreement on one decision, which is, do we attack at 8:00 or at 9:00? But if you think about these blockchain technologies, you really have to reach multiple decisions. And so you're basically agreeing on a shared log of commands and you're not only agreeing on the shared log of commands, you're actually executing these commands. So there's kind of these three layers of technologies. First one is just doing a single-shot consensus. The second one is actually transforming that to multiple consensus instances. And there's a lot of cool new ideas that you can use, for example, pipelining, where one instance of a consensus can actually be running the next instance of consensus and so on. You can get efficiencies through that. And the third layer is that it's not just about reaching consensus, something that's also about executing the commands of the state machine. And so these are kind of three layers of technologies that build state machine replication protocols.


28:32: Anna Rose:


So we sort of just hinted at this, but I kind of want to go back to the difference between something like a proof of work system and a proof of stake system in the context of what you've just shared. Maybe we can talk a little bit more about that.


28:45: Ittai Abraham:


Yeah, so in the traditional distributed computing setting, you have kind of this fixed set members. So n nodes, right? That's kind of this quintessential n number in theoretical computer science. And in a sense, if you think about a consensus protocol, a consensus protocol is all about reaching a decision. And the thing that you should ask yourself is, who has power to reach the decision? So it's really about distributing power to voters that have to reach a decision. If we have to decide whether it's 8:00 or 9:00, who makes that decision? Is it you? Is it somebody else? And so in the traditional computer science approach, you just assume there's n servers and each one has one voting power. So they get to decide on... They get to raise their hand once. If you think about proof of work, then in proof of work, Bitcoin whitepaper says this very nicely, it says one CPU, one vote. So proof of work, basically what it does is it gives anybody who has the ability to compute hash voting power proportional to the ability to compute hashing power. So obviously it's not one CPU, you buy these huge machines that can do enormous amounts of hashing per second, but fundamentally it's a way to distribute voting power to people that can compute or to entities that can compute hash.


30:14:


The beauty of this way is that there is no PKI, there's no public key infrastructure. Anybody that can compute hashes can basically participate in this consensus protocol. It does create a different type of power distribution where if you have a better way to compute hashes, maybe you have cheaper electricity or you have access to better hardware, then you get an advantage. But it's a way to give voting power in a Byzantine agreement protocol. Proof of Stake is another way to give power, which basically says one coin, one vote. So you build some sort of coin, in this case, many times cryptocurrency. And what you do is you say, let's say if somebody has 32 ETH, then it can lock this and get one voting power. And so again, it's a way to distribute voting power in a consensus protocol.


31:08: Anna Rose:


But in the case of the PoS system, it's not one CPU, one vote. Like it is, one could collect a lot of votes in a different way. I guess you can also collect votes in a proof of work system. You just have to invest in the hardware.


31:23: Fredrik:


Well, I mean, you could... It depends on what you mean by collecting. If you're thinking about someone getting power to vote without locking up their tokens, that's pooling resources into one person, almost all mining activities into mining pools. Most people actually delegate their voting power to mining pools. So it's not any longer one CPU, one vote. It's one CPU, one delegation to a mining pool who gets a vote. But I don't think that detracts from the idea, from the fundamental concept, right? It's you're basically just saying through other means, through social means or political means, I can get someone to vote for me and I vote on behalf of them.


32:10: Ittai Abraham:


Yeah. So these are two important things. The first is there's this macroeconomic theory that this power can be essentially abused by money. So if I have a lot of money, I can buy cryptocurrency and get voting in a proof of stake system. If I have a lot of money, I can buy mining hardware and get a lot of voting power in a proof of work system. So one of the open questions, I don't have a good solution for that, is how do you make sure that you have a more equalized system that doesn't kind of create this effect where people that have a lot more money have a lot more voting power.


32:44: Anna Rose:


And that is at the heart of a lot of systems' attempts to have good token distribution, like they want better token distribution, so that they're not in a state where like a small group of participants can easily own more than a third or more than a half of the network.


33:03: Ittai Abraham:


Exactly. And the problem is, even if you distribute it equally, maybe people who have more power can then go and buy some of these tokens and centralize more voting power. And that's kind of related to the notion of delegation that you mentioned, where this is how we today govern, right? We delegate our vote and we kind of vote for a smaller set of people who govern us. And so delegation also has both centralization risks and advantages of specialization, where you have somebody who's specialized in governing or in this case, specializing in staking. So I think finding the right balance is a challenge. But to me, what's important is understanding the fundamental. The fundamentals are that it is about distributing power. So it's about how you distribute votes in a consensus protocol, essentially.


33:51: Fredrik:


To bring it back to more like foundational consensus research, there's this concept in many consensus algorithms of a leader. And many of the blockchain algorithms that we talk about are leaderless. You don't elect a leader who gets to pick the block and then... Is there a practical thing that you have to think about when designing algorithms to go from a leader, leaderful to a leaderless algorithm?


34:18: Ittai Abraham:


Yeah, that's a great question. So if you think about proof of work, then whoever wins and produces the first solution to the hash riddle, you can imagine... You can think about that solver as a leader.


34:29: Anna Rose:


For a second.


34:31: Ittai Abraham:


For a second. And if you think about protocols like PBFT. So PBFT works in this primary backup approach, where there's always one node that's leading and everybody else is a backup. And then there is a view-change protocol that allows you to move from one leader to the other. Really from a foundational perspective, the question you should ask, again, goes back to the model, is how adaptive is your adversary? This is the fundamental question. Okay, what is an adaptive adversary? An adaptive adversary is one that can look at the system and decide who to attack based on what's happening. And so the problem with many of these protocols where there's a leader that's known and exists for more than a second is that as an adaptive adversary, I can find who this leader is and attack this leader.


35:22:


Maybe in Bitcoin, the advantage is that by the time I know who this person is, the hash message has already been propagated through the whole world. There is still kind of a small point in time where an adaptive adversary can succeed. So formally speaking, you can imagine very strong types of adaptive adversaries. And so against them, you have to do something more complex. And really what we're seeing, and this is work that started from theoretical cryptographic protocols, and appears in consensus protocols like Katz and Koo's protocol from 2006, and in some of my work is this idea where instead of designating one leader in advance, we kind of try to spread the role of leader among everybody in the population.


36:10:


So the idea here is that if you have a leader and there's an adversary, then this adversary is gonna attack your leader, right? So you choose one prime minister. So the adversary attacks this one prime minister. And so the trick is to basically say, we're all gonna be prime ministers. So each one of us is gonna be a leader. And then maybe after a while, let's say after 10 seconds, we do a random leader election to decide who in hindsight was the actual leader and everybody else is actually a decoy. So, on the one hand, we did a lot more work because now instead of having one leader, we had a lot of leaders. On the other hand, if you're an adversary, you have no idea who to attack because you don't know who is going to be important in this protocol. It's only in hindsight that you learn that. But in hindsight, you can't go and... Go back in time and attack whoever was actually chosen.


36:55: Anna Rose:


What does the P and PBFT stand for?


36:59: Ittai Abraham:


So P is for Practical Byzantine Fault Tolerance.


37:02: Anna Rose:


Okay, there's another one, SBFT.


37:05: Ittai Abraham:


Right, so this is Scalable Byzantine Fault Tolerance.


37:08: Anna Rose:


Okay. Are there any others that we should know about?


37:12: Ittai Abraham:


There's a lot.


37:14: Fredrik:


I think everyone else kind of came up with their own name and didn't go with the something BFT naming scheme. But I find it funny that PBFT being like, as you talked about earlier, it was this big thing and finally there's a system that someone has built and it works is called the practical. Like it's just the practical system.


37:38: Ittai Abraham:


Well, I mean, here's why it was a revolution back in 1999. At that time, it was almost like the zero-knowledge revolution of the last five years. People thought of Byzantine agreement as kind of this math or theoretical computer science, and it can't actually be used in practice. And so for the first time, Miguel Castro and Barbara Liskov, they actually built a system. And there's this amazing effect, when you actually show somebody a system that works, that's a huge difference between that and just talking about something in theory.


38:12: Fredrik:


Yeah, we've definitely seen that revolution, both in like practical zero-knowledge and practical MPC, and like we should have the first thing to actually build something should be called the practical thing.


38:24: Anna Rose:


Yeah.


38:25: Ittai Abraham:


And you know, the next phase after practical is boring.


38:29: Anna Rose:


Oh, yes. Boring is what we should all aspire to. Right?


38:33: Ittai Abraham:


Exactly. So we should have boring BFT. Right? It should be kind of... What I do is all the cutting edge exciting consensus protocols. But that should not be what people use. Right? So.


38:49: Anna Rose:


I think you might be the first guest, by the way, who just comes on and says, this is what I do, don't use it. But anyway, keep going.


38:55: Ittai Abraham:


Yeah. I mean, look, there's this gap between what innovation is and what a quality world scale enterprise scale solution should be. Right? This is why when you use a TLS library, there is actually a library called boring TLS, right? Because you want it to be vetted. You want to have a lot of years of very good engineering and tests and verification, you don't wanna live on the cutting edge. It's similar to, you don't want to roll your own crypto, you also don't wanna roll your own BFT protocol. Unfortunately, I've seen too many people do that. So I really hope that one day there'll be kind of this boring state machine replication protocols and people will just use them.


39:38: Anna Rose:


BBFT. Yeah.


39:40: Ittai Abraham:


Yep.


39:41: Fredrik:


Speaking about these different kinds of consensus algorithms, VMware has published this HotStuff thing. I assume you've worked on that too. And it was something that came to the scene relatively recently for me. It really... I really only like opened my eyes to it with Libra and then picking that, but I'm curious what HotStuff is and how it compares to those that we've already talked about.


40:10: Ittai Abraham:


Yeah, so in fact, I'll start with a precursor work, which is SBFT. So when we started the blockchain project inside VMware, we basically looked at PBFT and we said, this is a wonderful protocol, but it's from the 20th century. And we asked ourselves, so what is kind of the new things that we can do today? And we realized, well, there's better cryptographic tools. We can use threshold signatures. And the second thing that we realized is that we really want to create a protocol that scales for more replicas. So PBFT was optimized for 4 or 7 replicas. And we wanted to kind of scale for 200 or 300 replicas. And so the first thing we realized is that PBFT as a protocol inherently uses a quadratic number of messages. What does that mean? It means if you have 7 replicas, so roughly speaking, 7 squared, so 50 messages every round. That's not a lot. That's not a big problem. But if you have a system that has maybe 300 replicas, now 300 squared is actually quite a big number. And so we wanted to avoid that. And what we did is we realized that you can change some of the protocols to get a linear communication pattern. So this is the second thing we did.


41:27:


The first thing we took modern threshold cryptography. The second thing we did is have this linear communication complexity. And the third thing we realized is that you really want to use optimism. Right? So you can design systems that are always at war. They always feel that they're being attacked or you can design systems that actually have this kind of optimistic path that says, well, if things are good, I'm going to try to do a little bit better. And if I'm under attack, I'm going to switch to kind of the second mode. And so we added this optimistic fast path. And so these are kind of the three components of SBFT, Scalable Byzantine Fault Tolerance. So this is the first system that was tested in an academic setting for 200 nodes. And so this is kind of a BFT system that runs for 200 nodes.


42:14: Anna Rose:


Does this... Is this also a... Is this a partial synchronous model? Like I'm curious... What you just said sounds like what you just described before, where like it's ready to handle bad times, but it kind of assumes more good times.


42:29: Ittai Abraham:


Yes, you're absolutely right. So it is a... It follows the PBFT path, and PBFT is a partial synchrony consensus protocol. Byzantine fault tolerant partial synchrony protocol. And so, yeah, this work on SBFT is kind of following the same path of partial synchrony. Even in synchrony, there is kind of a worst case assumption and a best case assumption. And so we kind of get better latency in the fast path. The thing that we couldn't get in SBFT is reducing the complexity of the view change from quadratic to linear. So remember these protocols have kind of two phases. One phase, a leader sends a lot of commands and the other phase is that we change from one leader to the other. That operation is called a view change. And so we didn't know how to reduce the message complexity of the view change from quadratic, which was in PBFT, to something better than that. And this is kind of where Tendermint comes into play.


43:31:


So Tendermint was published in 2014. And we learned about Tendermint basically from talking to Vitalik in 2017 when he was explaining to us how Casper works. So Casper is kind of an adaptation of Tendermint as a finality gadget for proof of work systems. But essentially, Tendermint had this amazing breakthrough where it showed how you can do the view-change protocol in a linear amount of time. And so that's how we took the ideas in SBFT and we took this idea of the view change in Tendermint and combined it together to the first version of HotStuff.


44:15: Anna Rose:


Ah, interesting.


44:15: Ittai Abraham:


So the first version of HotStuff essentially has linear complexity, both in the normal case and in the view change, and it also uses kind of, again, modern threshold cryptography. It doesn't have a fast path. It just has kind of a regular flow. So this was kind of the first step in HotStuff. And what we realized is that the protocol itself is actually very simple. So it has kind of this very simple two rounds for reaching consensus. Roughly, roughly speaking, the first round guarantees that the leader cannot send two different messages of two different values. And the second message in this protocol basically guarantees that if somebody receives a message that will cause it to commit to a value, then the view change will be safe. The view change will make sure that the next leader will also see this value. That's the role of the second round. What we then figured out is that this two round protocol has still a problem. And the problem is that the view-change protocol itself is susceptible to a sort of denial of service attack that can happen even in the synchronous model.


45:30:


So in a sense, you're forced to wait a timeout between changing leaders. This is this notion of optimistic responsiveness. So optimistic responsiveness is this property where you can do a view change and you do not have to incur a delay during this view change. You can run as fast as the network speed. And so this is kind of the final version of HotStuff where we add one more round. So instead of two rounds, it's a three round protocol. This third round basically guarantees that the view change can proceed as fast as the network allows you to proceed, and you're guaranteed that this new leader will be able to make progress.


46:10: Fredrik:


I'm really curious to hear how you reduced the communication to linear, because I mean that that's one of the most known problems with something like Tendermint..


46:20: Ittai Abraham:


Yeah, so this is actually a folklore solution in distributed computing, where instead of sending a message from every replica to every other replica, you can basically use a collector. And obviously, this uses the idea of having a public key infrastructure. So now everybody, instead of sending the message to everybody else, you spend two rounds. Everybody sends the messages to the collector, and the collector can gather all these messages and send them to everybody else. If you're using threshold signatures, this collector can actually take all these signatures and combine them into one signature. So really what you're doing here is you're changing this all to all pattern to a pattern where everybody sends to a collector and the collector sends to everybody else. So you're spending two n messages instead of n squared messages. It creates a little bit more delay.


47:10: Fredrik:


But does that then require basically like a super node to exist in the network at all times? I mean, even if they don't really have power to do much. What happens if that one goes down? Does it become a single point of failure?


47:26: Ittai Abraham:


It is. And in a sense, from a liveness perspective, the leader in PBFT, in SBFT, in Tendermint, in Casper, these leaders are a liveness point of failure. So if the leader fails, you have a liveness violation and you have to replace the leader with a new view change.


47:43: Fredrik:


And so in HotStuff's case, it is essentially one of the participants that are the collector.


47:51: Ittai Abraham:


Right. So what HotStuff does is it actually does a rolling change of who is the leader. So every round, a different leader is being chosen. And so the message communication is basically everybody's sending to the leader 3, leader 3 sends to everybody. Then everybody sends to leader 4, then leader 4 sends to everybody. Then everybody sends leader 5 and so on. You basically rotate through all the leaders.


48:15: Fredrik:


But then you don't have that opportunity to make it leaderless and sort of only elect them in hindsight because you need to know at the time who to send your message to.


48:25: Ittai Abraham:


Yeah, so this is actually a new work that some of it has already been published in 2018. This is work with Sasha Spiegelman and Dahlia Malkhi and myself. It actually shows that you can take a protocol like HotStuff or like PBFT, and basically what you do is you run multiple worlds. So instead of running one instance, you run n different instances. So think about these as different bubbles, where in each bubble you have a different leader. And then after some stage, you can do a random leader election to choose which one of the bubbles was the real leader, and all the other bubbles, you basically pop them, and they're just decoys. And what you remain is the one leader that was the actual leader. So you essentially have to run multiple instances of say HotStuff or SBFT or PBFT in order to get kind of this stronger notion. In fact, you can do that and then get liveness even for asynchronous models. Right? This is kind of the highest level of guarantees that you can get. So you can take protocols that are built for partial synchrony and there's kind of a generic reduction that takes them and transforms them so that they are resilient even in asynchronous model.


49:40: Fredrik:


Yeah.


49:40: Ittai Abraham:


Right? This is kind of the cutting edge of where theory is at. We still haven't seen systems that build this or we're starting to see systems that are building this type of approach.


49:51: Fredrik:


That's super interesting. I guess you're like in... If used in a proof of stakes setup, you're kind of reducing your security, like your stake at risk, because you would have to distribute your stake across these different bubbles, but only one is actually the real one. Only one of these bubbles have their stake at risk. No one knows in advance which one it's going to be, but you're not putting all of your stake behind the decision that's being made. But as long as you have enough stake in the system, that's fine, basically.


50:27: Ittai Abraham:


Yeah. I mean, you could either decide to split it between worlds, or you can imagine that it's as if you're making a bet on all of these worlds together and your actual bet is the world that is not popped.


50:39: Fredrik:


Okay, yeah. Cool.


50:42: Ittai Abraham:


It's really a game of fighting against an adaptive adversary. So what you want to do is you want to be able to fool an adversary that can see the system and decide who to attack. So you want to hide who's making decisions in some sense.


50:57: Anna Rose:


Maybe just to wrap up on sort of the HotStuff stuff, what is your actual role in that project?


51:04: Ittai Abraham:


Yeah, so I was one of the co-authors of both the SBFT work and of the HotStuff paper.


51:09: Anna Rose:


Cool. And it was... Was it sold to Libra? Was it given... Like what was the relationship? Like what happens to HotStuff? As an open... It's an open source protocol or?


51:20: Ittai Abraham:


So at the time it was just an academic paper, and my colleague, Dahlia Malkhi, she's my colleague, but also my PhD advisor, my mentor, she left VMware and moved to Facebook. And so I don't know what Facebook, I have no knowledge about what Facebook is doing other than what I read from the web. But it seems that their consensus protocol, LibraBFT, is using a lot of the ideas that HotStuff introduced.


51:52: Anna Rose:


Cool.


51:53: Fredrik:


So I'm curious to compare these two other protocols that are similarly sort of optimistic or they have this happy path and slow path. And one is Avalanche and the other one is Thunderella. And they're like the two primary ones in my mind that pop up to who really talk about these two different paths as explicit things. We have the same thing in Polkadot where, I mean, we call it eventual finality because it'll eventually get there, but we don't really talk about it so explicitly as like a property of the system. But in particular compared to those two, because as far as I know, they're relatively novel as well.


52:35: Ittai Abraham:


Yeah so I'm going to start with Thunderella, because that's an example of a protocol that works in the synchronous model. So this is synchronous Byzantine agreement. And one of the major breakthroughs that happened in the synchronous Byzantine agreement, and this is Rafael Pass and Elaine Shi, was this realization that even though you're running a synchronous Byzantine agreement, there is an optimistic path where if you receive more than three quarters honest responses, you can actually run at network speed. So this is kind of a protocol that has a slow path, which depends on delta, the synchrony delta, and a fast path, which assumes optimism, as you said, which assumes 3 quarters, and allows you to move at a faster rate. And so we actually have a new work that tries to optimize these constants. So if you think about Thunderella, then I think the... Relatively speaking, there was a large constant in terms of how long you needed to wait for this delta delay. And so we have new results. This is with my colleagues, Ling Ren and Kartik Nayak. These are two different protocols, 1-delta and 2-delta. So the 1-delta protocol gives you kind of optimal latency for synchronous Byzantine agreement. And the 2-delta protocol gives you optimal latency with optimistic responsiveness. So you get 2-delta in the slow path, but you also get at network speed if you receive three quarters.


54:10: Fredrik:


And what about Avalanche?


54:12: Ittai Abraham:


Yeah, so Avalanche I think is so new that I don't yet fully understand the Byzantine fault tolerant model behind it.


54:20: Fredrik:


I hear that a lot.


54:21: Ittai Abraham:


Yeah, so I'm gonna... There are so many protocols, right? And every time there are new ones. So it's on my list to try to understand that, and it does seem that they have a very natural and seemingly very fast way to reach consensus. I need to understand exactly what are the limits of the adversary, right? How adaptive is it? How much it can control network delays and so on. I think over time, you're going to see more work that tries to analyze this in a more traditional framework of Byzantine agreement.


54:52: Fredrik:


Yeah. I think it was actually pretty recently that they even published what it is that they're doing. I think it was closed source for a really long time and it's only as of a couple of months ago that it's now public.


55:05: Ittai Abraham:


You know, what I've learned over these... I mean, this is, consensus protocols have been around for 40 years, but definitely the last 10 years, there are a lot of different groups that are suggesting new protocols. And on the one hand, I say, don't roll your own BFT, but on the other hand, I'm always amazed by how much I learned from people that seemingly come out of nowhere or not part of the kind of traditional distributed computing community and bring amazing new ideas, right? And Tendermint, I think, is a great example of that.


55:39: Fredrik:


I think, I mean, this is something that we've talked about quite a lot in their knowledge space, especially with the Zcash people, this interplay that's been happening in the blockchain space between research and engineering, where now for the first time in a long time, they're actually working well together. And this cooperation between engineering and science actually is pushing things a lot faster than if it was just academics alone. 


56:09: Ittai Abraham:


Absolutely. I mean, I'm now working quite a bit with engineers and I'm learning a lot from them. And I realize that even though it's important to have the right protocols, building the right software abstractions, using the right tooling, building all the tests, all the good engineering practices is very, very important. You can't just have good protocols, good theoretical protocols. That doesn't help anything, right? This goes back to the difference between an academic grade Byzantine fault tolerance system and an enterprise grade BFT. And what I wanna reach eventually, which is a boring BFT, right? Where everybody's saying, just download it and use it because it's foolproof.


56:56: Fredrik:


In a recent episode with Sean Bowe, he was talking about, how they'd built a new system and it was kind of slow and so he was going in and profiling and figuring out why it was slow and then we just kind of went, I'm just going to play around a bit here, remove this thing... Oh, it's way faster and still produces the same results. And then he went to the researcher and said, hey, can you prove that this still works? That this is still safe? Have you ever had that happen? Where innovation comes from that direction?


57:27: Ittai Abraham:


Yeah, a lot. To me, I think it has to be a two-way street. So this is how I learn about what are the real-world problems. You can't kind of just sit and think about theory. You have to work with practitioners, understand what are their pain points. And sometimes they explain to you things and show you things about protocols that you realize then that you have to change how you're thinking about how to design these things. So I always try to learn from people who do real work.


58:01: Fredrik:


So unfortunately, we're about at time. It's been a great episode and we've covered a lot of ground. There's still a ton left to cover as usual in these episodes. But maybe to tie it all together, bringing it back to the topic of the show or the namesake of the show, how do you see zero-knowledge proofs interacting more with consensus? Because we touched on this a little bit briefly, and there's problems that ZK proofs can solve that consensus algorithms bring. And what is the interplay between these and what do you see in the future for that interplay?


58:41: Ittai Abraham:


Yeah. So definitely zero-knowledge has a role to play independently. This is an amazing piece of technology, amazing feat of 20th century theoretical computer science. But in a way, if we go back and think about consensus as kind of this fundamental building block for a decentralized trust infrastructure, then it brings these two huge problems. So the first problem that consensus brings is that all the information is written in a public way on all the replicas. So think about basically a whiteboard where the whole world is writing all the information on this public whiteboard. So that's a huge problem and a huge inhibitor for use of this technology. The second problem is that when you think about not just reaching consensus on some hash, but actually executing some transaction on a state machine, then since you're replicating now on a bunch of different replicas, every time you run a transaction, you actually have to run that transaction on all the replicas. So again, this is a huge scalability bottleneck. And so this fundamental breakthrough technology of zero-knowledge helps save consensus from these two horrible things that it does, right? It makes everything public and it makes everything so slow because you have to rerun everything. So the first part is the fact that zero-knowledge proofs can hide things from the public.


1:00:07: Anna Rose:


And yet prove their validity. So like, you know that it's done correctly, but still be not public. 


1:00:13: Ittai Abraham:


Exactly. So I can send a transaction and I can prove to you that I own a token, I can prove to you that this token hasn't been spent. And I can prove to you that this token is now written in a nullifier, and I can do that all in a zero-knowledge statement. So the only thing you learn is that this token transaction is valid in this sense. And this is exactly what Zcash is doing. And we're seeing more and more advanced notions of that. And the second problem is this just mind-blowing effect that there is this huge gap between running a transaction and actually verifying it. So if you have a transaction... Somebody has to do work. So if there's a billion transactions, somebody has to actually execute those billion transactions. But if I have to verify what is my account value at the end of this billion transactions, I don't need to rerun those billion transactions. I can give a succinct proof that you can verify for what your account value is. And so this is kind of this, again, amazing ability to have succinct proofs that can summarize say a billion transactions into just a constant or a logarithmic amount of work that you can then verify. 


1:01:26: Anna Rose:


And our listeners will know this as rollup, ZK-rollup or any of these sort of ZK-enabled scaling solutions that we've seen at layer 1.5-ish.


1:01:38: Ittai Abraham:


Yeah.


1:01:38: Anna Rose:


Okay, so I wanna say thank you for coming on the show. What's next in consensus algorithms?


1:01:45: Ittai Abraham:


Yeah, so I think there's two big things that are coming up on the horizon. Once you have consensus, you can kind of go and build even more complex distributed systems. In particular, you're going to see this multi-party computation as the next wave of technology that's going to evolve. Once you have a stable broadcast and consensus protocol, you're going to have new multi-party computation protocols on top of that. The second thing I think that's going to happen in the next 10 years is more and more use of formal verification. So we've seen a lot of bugs and problems and challenges with software today, and formal verification, I believe, will help a lot with automating and streamlining some of the problems that we're seeing with today's software.


1:02:27: Fredrik:


Cool. Well, thank you very much. It's been a great show.


1:02:30: Ittai Abraham:


Thank you.


1:02:31: Fredrik:


And to our listeners, thanks for listening.


1:02:33: Anna Rose:


Thanks for listening.