← The a16z Show
The a16z Show
How Bitcoin Rewired a Classic Computer Science Problem
00:21:35
We're excited to share a special feed drop from The a16z Crypto Show. In the first episode of First Principles: The Scientific Roots of Blockchain Technology, Tim Roughgarden and Ittai Abraham trace the decades of computer science research that laid the foundation for modern blockchains. Long before Bitcoin, researchers were studying one of distributed computing's hardest challenges: how independent machines can reliably agree on a shared state, even when some participants are faulty or malicious. Bitcoin didn't invent that problem, but it introduced a breakthrough solution in a radically different, permissionless setting. The conversation explores Byzantine agreement, state machine replication, proof of work, proof of stake, Tendermint, Casper, DAG-based protocols, and why concepts developed decades ago continue to shape the design of today's fastest and most secure blockchain networks.
Loading summary
Transcript46 lines
- [00:01]
Itay Abraham
So this was in 2007. I was at a workshop, and the goal of the workshop is kind of see whether Byzantine fault tolerance is practical or not. But there was actually two big complaints. One is that maybe nobody needs it, and the other was that the performance was horrible.
- [00:12]
Tim Roughgarden
So the question wasn't whether consensus protocols are practical. The question was, did you really need to be robust to potentially very unpredictable failures as opposed to just crashing?
- [00:23]
Itay Abraham
Satoshi Nakamoto, he kind of realized that. He said, the core technical aspect of Bitcoin is solving Byzantine agreements. I would say, de facto, all the major chains that we know are running some version of Byzantine fault tolerance. The early proof of stake protocols, they were not very efficient. They had blocks every 10 minutes. And so really, if you're thinking about serving billions of people or systems that really manage large economies, you want to have kind of a wartime mode and a peacetime mode. So in peacetime, there's no failures. And the thing is that you do want to be able to switch to wartime. So if you are under attack, then you do have a way to kind of overcome a massive attempt to corrupt your system.
- [00:57]
Podcast Host / Narrator
People often tell the story of bitcoin as if it appeared out of nowhere. But the ideas behind bitcoin stretch back decades, drawing on foundational work in computer science, cryptography, and distributed systems. In this episode, Tim Roughgarden and Duta Abraham explore the scientific roots of blockchain consensus, explain why bitcoin represented a breakthrough in Byzantine fault tolerance, and discuss how decades of academic research continue to influence the design of modern blockchain protocols. Whether you're new to crypto or have been following the space for years, this conversation offers a deeper look at the scientific ideas that under underpin modern blockchains. If you enjoy this episode, be sure to subscribe to the A16Z Crypto show for more conversations like this.
- [01:43]
Tim Roughgarden
Hi, everyone, I'm Tim Roughgarden, head of research at A16Z Crypto and professor of computer science at Columbia University. And today we're kicking off a new series called first the Scientific Roots of Blockchain Technology that explores one of the most exciting areas of research at the intersection of theory and practice today. Blockchains and where the ideas that make them possible possible come from. At their core are decades of work across computer science, economics, and mathematics. Ideas about how distributed systems reach agreement, how trust can emerge without central authority, and how computation can be verified across networks of strangers. So we'll trace these ideas from their origins to the systems running in production today. And we'll talk with the scientists and the scholars whose breakthroughs made it all possible. To start, we're going to focus on one of the deepest threads, which is distributed consensus. How many machines can agree on a shared state even in the presence of failures and adversarial behavior? Concepts like Byzantine agreement and state machine replication, developed decades ago, now sit at the heart of modern blockchain technology. So to begin, I'm joined by a 16Z crypto research partner, Itay Abraham Itay is one of the world's leading researchers in Byzantine agreement and consensus protocol. He's a founding member of VMware's blockchain project. He's also the founder of Decentralized Thoughts, one of the field's most respected and long running technical blogs. Together, we unpack the work of two pioneers, Barbara Liskoff and Leslie Lamport, whom you'll hear directly from in the episodes ahead. All right, so it's very, very cool. We get to interview both Leslie Lamport and Barbara Liskoff. A great honor. Really, really cool. We get to do this. Maybe for the audience benefit. We should talk a little bit about how the pioneering work that they did connects to blockchain technology. So the first blockchain that came out, Bitcoin, 2008, 2009, part of what it is is a consensus protocol. And so the question is like, what does that mean? A lot of the work that Lamport and Liskoff both did, it's way before Bitcoin, right? It's from the 90s, from the 80s, even earlier. What's the connection? Bitcoin is a consensus protocol, but there's also this classic working consensus. Protoc calls. Was Bitcoin reinventing the wheel or how should we think about that?
- [04:08]
Itay Abraham
Bitcoin? Well, it's not just a whole new disruption in distributed computing. It also has innovation in economics and cryptography. But here we're going to focus on the distributed computing part. It actually took quite a few years for people to realize that this is kind of solving a Byzantine agreement problem. So Byzantine agreement problem is kind of this very core academic problem that has been studied for 40 years. And in that sense, Bitcoin is kind of this huge revolution in how to solve Byzantine agreements. In fact, if you look at early emails from Satoshi Nakamoto, he kind of realized that. So he said the core technical aspect of Bitcoin is solving Byzantine agreement.
- [04:42]
Tim Roughgarden
So Nakamoto apparently knew that this was a well known problem, distributed computing. So what's the connection then between the Bitcoin protocol and the protocols? We're going to hear about?
- [04:52]
Itay Abraham
Yeah. So in a sense, both the protocols that we're going to hear about from Barbara Liskov and Leslie Lamport are byzantine agreement protocols, or agreement protocols in general. Bitcoin solves this in a much different setting, permissionless, with a much smaller setup, much more kind of geared towards cryptocurrency and crypto economics. But if you kind of think about this from the foundational perspective, they're both solving the same agreement problem. So agreement is kind of this problem where you have multiple different parties and they might have different types of inputs and they need to reach agreement, even though a fraction of the participants are behaving maliciously or in a corrupt manner.
- [05:30]
Tim Roughgarden
So, like in the Bitcoin protocol, who are the parties that have to agree and what is it that they're agreeing on?
- [05:35]
Itay Abraham
Right. So you have miners. Right. And the miners are trying to kind of push the protocol forward by generating new blocks, by solving proof of work. And it might be that not all the miners are trying to do the right thing. Some of them may try to subvert the protocol or they're behaving in a corrupt manner. Maybe they're trying to create some sort of double spend attack or some attack that will basically cause different people to see different views on the blockchain. And what this protocol basically does, Nakamoto consensus, it's called the consensus protocol of Bitcoin, is kind of guarantee that even if a fraction of the miners are corrupt, this protocol still gives you a single consistent view of the ledger. And in a sense, that's exactly the thing that has been studied 40 years ago in state machine replication, in Byzantine fault tolerance.
- [06:20]
Tim Roughgarden
And so state machine replication. So how does that compare to agreement?
- [06:25]
Itay Abraham
So in a sense, kind of the core problem is just reaching an agreement on the content of the log. So now you have kind of a log that has different commands on them.
- [06:33]
Tim Roughgarden
So a log would be an abstraction of a blockchain in this case.
- [06:36]
Itay Abraham
Yeah. So you could think about every. Every block in your blockchain as just a set of commands. And then you have kind of a chain of commands that would be kind of a log or a chain. It's kind of the same thing. But really what you want to do is not just record things, but you want to try to see what is the outcome of executing them. So this is where you have some sort of smart contract language or some scripting language like Bitcoin script. And in this case, maybe you want to verify some signatures or run some sort of a contract. So this is the Execution part of it. And so the very powerful abstraction, this is an abstraction that we'll hear about from Leslie Lamport is what's called a state machine replication. It's that clients are basically thinking as if they are interacting with a single state machine. So what is a state machine? It's simply a single system that you send it commands, and through that commands, it updates, updates its state from one state to the other to the next. And each time you kind of run the command, the state updates to the next state of the system.
- [07:32]
Tim Roughgarden
And then I guess in a blockchain context, that state would include, for example, everybody's balances in a native cryptocurrency, plus, I guess, maybe like local storage and smart contracts, that would all be kind of part of this state.
- [07:45]
Itay Abraham
Right, exactly. So, for example, in Bitcoin, maybe the state of the system is that I have a token, and maybe if I send a payment to you, then the way the state would change is that now my token's erased and there's a new token that forms that's under your public key. Right. So now you can use that token. So the state is kind of recording what are all the unspent tokens or transactions that are on the chain.
- [08:04]
Tim Roughgarden
So one thing that I think I find fascinating is, you know, you had for a while two parallel threads of research that, at least it seems to me, have converged to a large degree over the last five years. But I'm curious about your thoughts. Right, so you have distributed computing dates back again at this point, you know, 45 years or more. And we'll hear from, you know, both doctors Lamport and Liskoff about that early work. And then separately, you know, bitcoin launched kind of blockchain technology and sort of a research community around that thinking about how to build better and better blockchain protocols. And that was in 2009. So that was maybe about 30 years after some of the earliest, you know, pioneering work on the distributed computing side. And so in addition to being 30 years later, I felt like it was kind of a parallel thread for a while there. But now it seems to me that those two threads have been coming together over the past maybe five years or so. So I guess, do you sort of share that view? And if so, like, what, do you been driving that sort of convergence recently?
- [09:02]
Itay Abraham
Yeah, absolutely. First of all, I really think that Bitcoin is this kind of huge revolution. We're probably going to spend a lot of time talking about that. But in a way, when it happened, people didn't really understand what it's doing. It actually took quite a few years for the research community and for everybody to understand that this is solving kind of a very hard academic problem. Once it was clear that that is the problem that Bitcoin solves, there was this effort to try to connect that to this classical work. It took quite a few years. Around 2017 or 16 was when this change. I think the first protocols were Tendermit as an example. These were the protocols that kind of were using the classical Byzantine fault tonic protocols, but applying them on proof of stake. So really I think that this is this transition from proof of work based protocols to proof of stake ones and the realization that you can kind of mimic the same effect that Bitcoin obtained in proof of work using proof of stake protocols. So I think that was kind of this first wave of 2016, 17. Maybe the next one to mention is Casper. This is the Ethereum finality gadget that appeared around 2017.
- [10:04]
Tim Roughgarden
That's a great point. I mean, now even the theory is at the point where we understand there's a formal sense in which you kind of can't do the traditional consensus protocols in a proof of work context, which is an interesting interaction between kind of the type of Sybil resistance. Right. So if you don't know who people are and you can't do one vote per person because you don't know who the people are, so you have to do one vote per some scarce resour. That's what I mean by a simple resistance mechanism. And Bitcoin famously uses proof of work in some sense that's incompatible with the types of techniques that Drs. Lamport and Liskoff will be talking about. Whereas proof of stake symbol resistance. Well, there's a lot of other reasons you might want to use that as well. Maybe you're concerned about environmental reasons or scalability, what have you. It also actually unlocks Those techniques that Drs. Lamport and Liskoff will tell us about. So that's a great point.
- [10:52]
Itay Abraham
And it was not trivial at the time. So I remember 2015 people were saying, oh, there's this idea of proof of stake, but how do we do it? It seems impossible. There were a lot of people that said that there's no way to do something similar. So it was a non trivial advance during those days.
- [11:04]
Tim Roughgarden
Absolutely. So for example, Ethereum I know was already talking about proof of stake before they even launched their original mainnet in 2015. And then the actual transition to proof of stake wasn't until 2022. Right. Seven, eight years later. So I agree, it seems like that turned out to be a much more difficult problem than just the initial idea. So you mentioned Tendermint, which may be familiar to listeners from the Cosmos ecosystem. Among other. You mentioned Casper, which is used in today's Ethereum. So today's Ethereum has sort of two layers. It has like a longest chain, sort of lower layer, and then a phenology gadget based on top Casper. And as you say, the techniques in Casper are going to be very related to the techniques that our guests tell us about today. I actually, on a personal note, I think I first became aware of this interesting interplay. The idea that the Bitcoin protocol on the one hand was sort of solving a well established academic problem, but then doing so in a way no one had ever thought about. It was just a survey read, I think, with Dalia Malky that sort of first pointed that out. So that was maybe 2017 or something like that. That made a big impression on me at the time.
- [12:08]
Itay Abraham
Yeah. So it actually took, I think, quite a few years for this kind of prevailing, I guess, community understanding. Right, that Byzantine fault tolerance is the core thing that blockchains are doing. But that actually wasn't obvious. There were early protocols that kind of did things that were not consensus protocols or didn't solve a Byzantine agreement. And it took quite a while until kind of things settled, I would say. And today, or at least even from 2017 to the 2000 and twenties, there was kind of an explosion of research in Byzantine fault tolerance. And I would say, de facto, all the major chains that we know are running some version of Byzantine fault tolerance.
- [12:44]
Tim Roughgarden
One thing that's been wild, I'd say, about blockchain technology is it's sort of breathed a lot of new life and also, frankly, a lot of new resources into a lot of areas of computer science that have been around for quite a while. Right. So another example would be, say, the development of snarks, which for many decades was viewed as a purely theoretical construct. It was kind of something magical, which you'd never hope to implement. And now we're really seeing very concretely efficient snarks come into production. And while consensus protocols, they were always sort of meant to be practical, as I think we'll hear about today. They've been supercharged as well by having blockchain technology as a sort of extremely high value application of better consensus protocols.
- [13:26]
Itay Abraham
But let me even tell you another story. So this was in 2007, so 2007, and I was at a workshop, and the goal of the Workshop is to kind of see whether Byzantine fault tolerance is practical or not. This was really a few years after Google and Yahoo and Microsoft were using kind of the non byzantine version of agreement. Right. This is kind of Paxos type protocols.
- [13:44]
Tim Roughgarden
So the question wasn't whether consensus protocols were practical. The question was, did you really need to be robust to potentially very adversarial or very unpredictable failures as opposed to just crashing? Is that right?
- [13:57]
Itay Abraham
Right. But there was actually two big complaints. One is that maybe nobody needs, and the other was that the performance was horrible. So people kind of didn't believe that it's possible to do it any better. They said, oh, this is going to be very slow. We now have these very efficient Paxos like algorithms. Those are practical, those are used by a lot of these cloud service providers. But yeah, Byzantine faltar is, oh, that's not practical, that's too expensive. So, yeah, I think we've seen this arc of a lot of work in a space, kind of really exponentially improve
- [14:26]
Tim Roughgarden
it, say like last five years. Are there some sort of innovations in consensus, but originating from the blockchain community that you find particularly notable?
- [14:34]
Itay Abraham
So we are seeing, you know, not just a lot of systems are using Byzantine fault lines, but we're also kind of seeing a lot of innovations in this space. A lot of it is focused on getting much higher throughput and much lower latency.
- [14:46]
Tim Roughgarden
And so I guess just to make that concrete. So from the user perspective, you want high throughput because you want there to be space for your transactions and even sort of, you want it to be cheap to send your transactions. A lot of latency just means whatever you ask the blockchain to do, like do a transfer or whatever, you want it to happen, ideally close to instantaneously. Right, that would be the latency.
- [15:04]
Itay Abraham
Yeah. And maybe we can go back to Bitcoin 2009 or even 2017, the early proof of stake protocols, they were not very efficient. They had blocks every 10 minutes, if it's Bitcoin, or every kind of tens of seconds. And the throughput was actually quite small. And so really, if you're thinking about serving billions of people or systems that really manage large economies, then that wouldn't be enough for some types of use cases. So you want to have something that can serve many, many users and not only that, they can give them a real time experience. So serving a lot of users, that's going to be high throughput and giving people kind of a real time experience, that would be kind of low latency. One Type of innovation is these DAG based protocols. These are protocols that have two different layers and they really push the throughput of these systems quite a bit. We've seen this for example, in SWE and protocols like Misted seti. That's kind of one family of major improvements and the other one was a focus on trying to reduce latency. Can you kind of reach byzantine agreement with very, very few round trips? And we've seen these new protocols that kind of have two different modes. So a regular mode that maybe has three message delays and a fast path that has just two message delays. And this is the optimal thing that you could expect even in a non byzantine setting.
- [16:17]
Podcast Host / Narrator
Right.
- [16:17]
Itay Abraham
You could just think about this. It's really just a server sends it to all the replicas and gets a response back and the transaction is committed. So really you get the smallest vacancy that's really could possibly imagine.
- [16:27]
Tim Roughgarden
Yeah, and I think this is a very cool approach. This is basically just optimizing the common case.
- [16:32]
Itay Abraham
Right.
- [16:32]
Tim Roughgarden
Which is just usually a good idea. And this itself has precursors in the academic literature that predate blockchain technology. Maybe most famously with Alpenglow, which is the proposed new version of Solana's consensus protocol, which I think will be rolled out in 2026. That's really kind of in production implementation of this idea, like maybe 90 some odd percent of the time you can be super while losing little if any in the remaining percent from what you had before.
- [17:02]
Itay Abraham
Yeah, the way I like to think about this is from a systems design perspective, right. Is that you want to have kind of a wartime mode and a peacetime mode. So in peacetime there's no failures, everything's good. You want to be super fast and super efficient.
- [17:13]
Tim Roughgarden
And that's going to be most of the time.
- [17:14]
Itay Abraham
That's going to be 99% of the time or even more.
- [17:16]
Tim Roughgarden
And we now empirically can be just watching all these blockchains in production. Empirically, we know that's most of the time.
- [17:22]
Itay Abraham
Exactly. I mean there's kind of crypto economic incentives. Right. So once you make attacking it not efficient, then people will attack it less and so on. And the thing is that you do want to be able to switch to wartime. So if you are under attack, then you do have a way to kind of overcome again a massive attempt to corrupt your system. So I think these kind of dual mode protocols are fascinating and I think make a lot of sense in this world.
- [17:42]
Tim Roughgarden
One final thought on the influence of the academic literature on consensus protocols to modern blockchain protocols. I'd also say even just the language people use to talk about blockchain protocols and the guarantees they have, I'd say is deeply, deeply informed by the foundations that were laid kind of on the research side. Right. Even if it's just meant to be a purely practical blockchain protocol, still there's an expectation that you would have, for example, optimal fault tolerance, impartial synchrony, which is a bunch of academic words. I mean, it all translates to precise mathematical statements about sort of a mathematical abstraction of the practical protocol. But yet that has almost become sort of table stakes for new generations of blockchain protocols. And so to me, just, just the whole way people think about what makes a protocol good or sort of state of the art, that is, I think, very deeply shaped by the last, now almost half century of work in this field.
- [18:38]
Itay Abraham
Yeah, I mean, for us this is extremely exciting because we come from kind of a theoretical computer science and here we have something that's extremely practical. As you said, the language and the way to think about these, to reason about these protocols is actually using theory and mathematical abstraction. And this is a non trivial idea, right, that you have a real world system and you're actually using abstract mathematical thinking and you're using proofs and you're using that language in order to reason about your system. And what's to me even more exciting is that this is not a new idea. This is an idea that as we're going to see, has been studied for 40 years in distributed systems. So there's kind of this very deep and successful connection between relatively theoretical notions and mathematical models and things that are just kind of, I guess, in theory and practical systems that are deployed in real world, both in kind of clouds and the 2000s and today in basically all blockchain protocols.
- [19:27]
Tim Roughgarden
Yeah, right. The famous quote is that the gap between theory and practice is always smaller in theory than in practice. But I will say I really feel like this gap has been getting narrower thanks to the efforts of sort of lots of smart people, both on the research side and on the sort of engineering side. It's not perfect convergence, but like you say, really the theory being developed right now really is intended to usefully inform the next generation of in production blockchain protocols. It's just very exc. Exciting to sort of see that synergy between them very much.
- [19:59]
Itay Abraham
And for me I think it's because it's a two way street. Right. So it's not that, oh, there's somebody sitting in every tower and kind of writing theorems. It's actually you see what's happening in practice and you analyze that and then you realize, oh, you can. So this two way connection is extremely important and was very fruitful, I think, for both sides.
- [20:15]
Tim Roughgarden
And, you know, I would guess for both, you know, Liza Lamport and Barbara Liskoff. Right? I mean, there is, you know, anyone can see it as a really major loop between kind of the theoretical innovations and sort of the practical solutions. So I'm sure we'll hear more about that from them as well.
- [20:31]
Podcast Host / Narrator
Thanks for listening to this episode of the A16Z podcast. If you like this episode, be sure to like, comment, subscribe, leave us a rating or review and share it with your friends and family. For more episodes, go to YouTube, Apple Podcasts and Spotify. Follow us on X16Z and subscribe to our substack@a16z.substack.com thanks again for listening and I'll see you in the next episode. Episode As a reminder, the content here is for informational purposes only, should not be taken as legal, business, tax or investment advice, or be used to evaluate any investment or security, and is not directed at any investors or potential investors in any A16Z fund. Please note that A16Z and its affiliates may also maintain investments in the companies discussed in this podcast. For more details, including a link to our investments, please see a16z.com forward slash disclosures.