Before Blockchains, There Was State Machine Replication

17:02Barbara Liskov:Well, I don't know that I should talk about the practical side and how it influences theory. But in my group, I always told my graduate students they should take theory courses. You know, theoretical computer science is the backbone of our field. We always wanted to track what was going on in there. The main thing that was impacting my work was always understanding, you know, understanding what they were doing and also things like cryptography and so forth, which came to be so important in not in those days so much. but in later work. And of course, I was fortunate to be at a place where Ron Rivest was and his colleagues, you know, and so forth.

17:45Tim Roughgarden:And I was going to ask about that, actually, which was how important was the milieu of MIT for the work that you did? Do you think if you'd been in another strong department, things would have played it out in a similar way? Or is the MIT imprint very strong in some way?

17:59Barbara Liskov:Well, I can't answer that question, but I really think, you know, we have many strong places. And I think all the top institutions could have done this work. But MIT is a wonderful place. And we also took teaching very seriously. And I do think teaching and research are very closely connected because when you teach well, you teach from first principles. And when you do good research, you have to truly understand. So you're really doing research from first principles. And it's also very important in research to understand what you don't understand. I always tell my students that there's where you get the insight into where you have to move.

18:42Barbara Liskov:And you don't want to have an incomplete understanding of why something works. You know, you have to really understand it completely. And we always tried to prove the correctness of these. As we got to these more complicated protocols, you really, you have to reason about them carefully to make sure they really work.

18:59Tim Roughgarden:I'm glad to hear you say that. I couldn't agree more. You know, what you're talking about teaching and research, I sometimes describe teaching as increasing the number of people who understand something from a smaller number K to a bigger number N. And research is the special case where K equals zero, or for the first time, people are understanding it sort of deeply.

19:18Barbara Liskov:That's a good way of looking at it.

19:20Tim Roughgarden:So I view them, I completely agree with you, very synergistic activities. And, you know, that's kind of the twin pillars of the professor's role, I think, really. So returning to the research side, so view stamp replication came out in the late 80s. And then there was sort of a period where I think the focus of your group turned away from replication to some extent, still partly in distributed systems.

19:43Barbara Liskov:We finished view stamp replication. We published it at some time in the late 80s. That was when I came up with what came to be called the Liskov substitution principle. But we had put that aside. Of course, it was early days. It was not in any commercial environment yet. And also, you know, Leslie Lamport was working on Paxos. And I actually heard him give a talk in the 80s about Paxos, and I didn't understand what he was talking about. And I had certainly no idea it was the same thing. But this was a mutual lack of understanding. The story I heard was, well, in the late, in the 90s, the Google File System paper was published.

20:25Barbara Liskov:and that paper used replication and talked about using Paxos. And I was kind of peeved because one of my students was working there and I thought he could have talked about view stamp replication. But the story I heard was that Bill Weil, who had been a student of mine in the 80s, happened to be at Google and he was looking at what was going on in the Google file system and he said, oh, he said, that's view stamp replication. and they really were the same protocol developed in two different places. It was just funny how we kind of couldn't see that for that period.

21:01Tim Roughgarden:Fascinating. It's interesting how there's sometimes just moments in time where it feels like the right time for certain work to be done and often it happens that sort of multiple different sort of groups do it at the same time.

21:12Barbara Liskov:And the same idea does get discovered more than once. Yes. Yeah.

21:16Tim Roughgarden:So that seems like a great example of that. But then you did get, in the late 90s, you did get pulled back into replication, right? And the famous PBFT, Practical Byzantine Fault Tolerance Protocol. And my understanding is that was at least in part inspired by a DARPA, a BAA, you know, a sort of request for proposals. So we'd love to hear a little bit about that story. and then maybe relatedly just perhaps the importance of collaboration outside of academia, whether it's with, you know, kind of government funding agencies or industry and how maybe that's, if that's been important in your work, how that's been important.

21:53Barbara Liskov:Well, the way PBFT came about, Practical Byzantine Fault Tolerance, is I had a student, Miguel Castro, who was looking for a PhD thesis. and I suggested to Miguel that he look at the RFPs that DARPA had put out and see if anything interested him. And he found an RFP that was looking for ways to handle the malicious attacks that were going on on the internet. And so he came to me and he said, why don't we see whether we can figure out a way to do replication that handles these malicious attacks? And that seemed like a great idea. I mean, I'm not saying it wouldn't have happened anyway, but the fact that DARPA had recognized that this was a serious problem, the problem of malicious attacks, and was looking for research in that area certainly was something that caused this work to happen in my group at that time.

22:47Barbara Liskov:And I think that DARPA was a very important, between DARPA and NSF, I mean, they were the reasons that research was getting funded all those years. They are one of the very important backbones of why we have the internet that we have today. Without that research funding, it would have been much more difficult to have done all that work. So that's how we got started on Byzantine fault tolerance. And then what we did was we simply started from view stamp replication. My group all knew what view stamp replication was, and I don't think it was understood at other places. And so we had that stepping stone that other people didn't have and we used it.

23:30Barbara Liskov:It just seemed like it was a natural thing to do. We had this algorithm that worked for benign failures. Okay, let's add Byzantine failures and see what happens. And we also knew from the theoretical work that we were going to need 3F plus 1 replicas instead of 2F plus 1. But again, we're looking for a practical protocol that people will really use in practice. So we started from view stamp replication, but it's a very different problem once you add those Byzantine failures because you have to be prepared for replicas that lie. And, of course, you also have to worry about malicious attack on the content of messages.

24:11Barbara Liskov:For that, of course, we immediately started using cryptography because that was the way to make sure that messages can get from here to there and you knew who they were coming from and you knew whether they were correct or not. The bigger problem that we were dealing with was the replicas that lie. And of course, that's why you need 3F plus 1 replicas instead of 2F plus 1. And the biggest problem you have there is that the primary might lie. It felt to me like we were in a funhouse full of these distorting mirrors, and you had to really think about things in an odd way to come to grips with this.

24:46Barbara Liskov:But in the end, the solution was a protocol that was strongly based on view stamp replication. It had one more phase in the replication protocol because the way you handle the problem is you never trust an individual replica. You only trust the group. And the group has to consist of a sufficient number of replicas to be able to prove that this is what really happened. and of course we need a way that this proof can be offered at a later point in time and for that we use certificates. So a certificate consisted of 2F plus 1 signed messages all stating the same thing and that would be a proof that you got to a particular point in the protocol.

25:33Barbara Liskov:And the extra step happened because the primary could only suggest the next step. then two F plus one replicas together have to produce a protocol that says, we're doing this next and putting this next in the ledger. And then you have to do another phase to actually commit that step. And that's how you get this protocol. But, you know, it's easier in hindsight to see it than it was at the time. It took quite a bit of thinking to come out with it. But that was still, it was the underpinning of how we came up with PBF2.

26:07Tim Roughgarden:Yeah, and just for the audience's benefit, I mean, this idea of sort of certificates of two F plus one signatures, I mean, this has been a very, very influential idea. And many of today's major blockchain protocols, indeed, this is how they prove, you know, the ordering of their transactions to others.

26:24Barbara Liskov:But of course, we didn't invent certificates. They were coming out of theoretical work.

26:28Tim Roughgarden:That's right. Corriendo if I'm wrong, the PBFT to me felt like the bridge from that theoretical work to practical systems, right? I mean, my sense just, you know, from reading a PBFT paper and all of the reactions around it was perhaps there was this aha moment. It's like, oh, wait a minute. This isn't just to prove the theorems. Like, we can actually sort of build a system where this is really how it's going to work. Was that what happened?

26:50Barbara Liskov:I mean, we were just, you know, picking up stuff from theoretical computer science and using it as we needed it. But you may be right that it was thought of as this work is interesting, but, you know, who cares? of the theoretical work. And now you could see how it really fit right into a practical system. We were happy that there were techniques that people had developed that served our needs. Still, you can see the bridge between theory and practice. If we hadn't been around the theory, then we would have been really stymied in what we were doing.

27:23Ittai Abraham:Yeah, I wanted to add that sometimes good systems work that have benchmarks that show good actual practical results. They change people's minds. They say, oh, this technology can actually be used. There's a difference between having a theoretical paper saying it's possible and seeing good benchmarks.

27:40Barbara Liskov:I see what you're saying.

27:40Ittai Abraham:Saying that a file system works well.

27:43Barbara Liskov:I was never worried about that. But of course, I was just the one who wanted to find the stuff that would make the system work. And it was hard, but it was a lot of fun.

27:55Tim Roughgarden:Speaking of certificates, actually, there's been a very cool line of work in the last maybe five to seven years or so in distributed computing around accountability, which is when something goes wrong, can you tell if it went wrong and who might be responsible for it? And so in particular, like if you want to think about Byzantine fault-tolerant systems and say, well, what would happen if actually you did have too many malicious actors, right? What could happen? And you could have a consistency violation. But accountability says the only way to create a consistency violation is by signing lots of inconsistent things.

28:27Tim Roughgarden:And then through inspection, you can actually identify bad actors who double signed on different conflicting states. I could imagine this being developed maybe 20 years ago, but it's mostly been developed in the last five to seven years. So analyzing PBFT-style protocols, not just in the regime where the number of faulty nodes is small, but also where it's actually bigger than the threshold.

28:48Barbara Liskov:You know, I'm not aware of that work, but it does sound interesting.

28:52Tim Roughgarden:Yeah, it's very cool.

28:53Ittai Abraham:The other thing I wanted to ask you about PBFT, or one of the things that really was very helpful for me when I read these papers, is not only the replication protocol itself that has certificates and 2F plus 1 that we talked about, but also kind of this observation that once you have a consensus protocol or a replication protocol, you can actually run different types of execution engines. So you mentioned a file system as one example, but you could run other types of services. So maybe you could talk a little bit about kind of this view of a generic service as a replicating service?

29:28Barbara Liskov:Well, I think that's, I mean, that was there from the start. Of course, we were thinking about a file system when we did view stamp replication, but it was always clear that we really weren't the application. We were actually the piece that gave the application the right information. And so we didn't really care. We just wrote into the ledger, you know, what the operation was that was being requested, but we were not in the least bit interested in what it meant to execute that operation. So it just seemed like a good separation of concerns. And I think even in the beginning, we understood that you wanted to look at it that way because you didn't want to limit yourself to one application.

30:14Barbara Liskov:You wanted to find this generic thing that would work for many applications.

30:18Tim Roughgarden:It's another variant of the modularity principle that you were proposing earlier, perhaps. I suppose.

30:24Barbara Liskov:I think it was just sort of, in a way, obvious that you wanted, you know, you mentioned state machine replication in the email you sent me, and we knew we were working on state machine replication. And state machine replication has the idea that whatever it is that you're doing, that's just the thing, you know, and you instead just think about the order and this is operation number 25 or something like that. So I think it was very fundamental, even in view stamp replication, to what we were doing.

30:54Ittai Abraham:So, yeah, I guess today it's a very common understanding, right? This separation of different layers of consensus and execution. And it's really cool to see that these are kind of ideas that, again, evolved from these work from the 80s and 90s.

31:08Tim Roughgarden:And then even more so, I mean, I would say Turing Complete, blockchain protocols like Ethereum, Solana, etc. They're almost like literal implementations of the fully general state machine replication problem. They're not trying to be kind of a specific application of state machine replication. They're trying to actually just implement it in full so that then a specific smart contract can then be, you know, in some sense, a special case, a special instance run in the general sort of SMR protocol. So these blockchain protocols are in some sense, you know, one of the more literal embodiments, I think, of the general state machine replication problem that we've seen to date.

31:44Tim Roughgarden:Just super interesting.

31:45Barbara Liskov:I mean, it was when Miguel and I finished the work on practical Byzantine fault tolerance, we thought that at some point people would start to use this. Of course, for view stamp replication, it was a delay of about 10 years before people started to use it. And then along came blockchains.

32:08Barbara Liskov:So that was very funny.

32:10Tim Roughgarden:There was a long period of time. I mean, so, right, so blockchains were sort of launched with Bitcoin protocol, which actually looks rather different than PBFT and most of the other consensus protocols anyone had thought about to that time. And it took, I think, you know, the blockchain community a number of years to realize that PBFT and the sort of subsequent protocols in that family were exactly the right tool for a lot of the problems that they're trying to solve. But at this point, 2025, it is, I think, very well understood. among blockchain practitioners and researchers that really PBFT and protocols like it are the foundation for what those protocols are trying to do.

32:49Tim Roughgarden:One other thing I'd love to talk a little bit about is just, do you have advice for the younger generation? So let's, someone who loves computer science, loves research, you know, maybe distributed systems, maybe more broadly, thinking about computer science, you know, wants to do important work, wants to have an impact. What would you suggest as kind of a mindset, as an approach, how to get started?

33:12Barbara Liskov:Computer science is in a very strange place right now with the advent of AI and not really understanding where we're all going with this. I think that as far as research is concerned, there's huge amounts of research to be done. And I can't help but think about all the systems research that's lying under all the AI stuff and all the problems that are coming up that make for very interesting systems research. So I don't think research is in trouble. I am a little worried about computer science as a field for young people going to college and should they major in computer science and so forth. And I don't understand the limits of what AI can do.

33:56Barbara Liskov:I can easily see how AI can write a little program for you if you give it a specification. I can easily see how that program might be wrong. And it's very easy to see that we're going to need a lot of verification tools in order to make sure that program is right. There was a letter in the New York Times recently by Mary Shaw and somebody else about what's the future for coders. that made the point that the students really need to understand how to write those programs themselves, or otherwise how will they know that AI did them right or wrong. And that's correct. I think, you know, there's going to be a lot of research going on, whether this is a field that you can get a good job in and do the kind of coding work that people used to do.

34:43Barbara Liskov:What Mary was saying, you know, is you're now managing more the coding and you're working at a higher level. That's a good job. The course that I developed at MIT in the 19, starting in the late 70s with John Guttag, which was a course about how do you build big programs. And it was all about design and modularity and specifications and verification. Maybe that's exactly what we're talking about as the future for coders. They have to be working at that level, not at the how do I write that little for loop with, you know.

35:19Tim Roughgarden:Yeah. Is it a semicolon or a comma? Yeah, exactly.

35:23Barbara Liskov:So I still think computer science is a great field, and I think there's a lot to be done. And the problems that we solve will change as the future goes forward. I am very worried about all the bad behavior that we enable, but then bad behavior is enabled by most anything. So it's not really our fault, but it worries me. And I really think to the extent that we can figure out ways to modify or contain the bad behavior, that's another good research area. So what am I saying? I've said there's great research to be done. And a lot of it's in the systems area.

35:59Ittai Abraham:I couldn't agree more. I think that's a great note.

36:03Tim Roughgarden:That's a beautiful note to close on, I think.

36:05Barbara Liskov:Okay, good. I'm glad to hear it. Anyway, so, I mean, this has been fun.

36:09Tim Roughgarden:It's been an honor to have you, Professor Liskopf. Thanks so much for taking the time.

36:13Barbara Liskov:You're welcome. And nice to connect with you. Thank you very much.

36:15Tim Roughgarden:Take care.

36:18Ittai Abraham:Thanks for listening to this episode of the A16Z podcast. If you liked 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 X at A16Z and subscribe to our sub stack at A16Z.substack.com. Thanks again for listening, and I'll see you in the next episode.

37:09Ittai Abraham:closures.