Scaling Distributed Trust Through Databases with Natacha Crooks | a16z crypto Research Series

Transcript

pleased to introduce Natasha Cooks who's a professor at UC Berkeley doing a lot of great work in distributed systems. Uh just became a Sloan fellow I saw. Congratulations. Uh today she'll talk about distributed trust ledgers are just a database apparently. >> So first I'd like to apologize to Tim because apparently every time I see him I say that distributed trust ledgers are just a database and now he has to hear an entire talk on it. So what I'm going to try and uh and tell you is um convince you is that many of the abstractions that we want from a distributed ledger, we could implement we if we start thinking about it, how we've thought about database systems for the last 20 or 30 years, we could actually implement them in a much more effective way and we could simplify how um they're used in practice. Now

obviously I didn't know necessarily know the background of everyone here. So there might be cases where I'm saying things that are painstakingly obvious. Likewise, there might be cases where I'm saying things that um assuming that you know that you don't know. So feel free to ask questions. Feel free to ask for any clarification questions. I try to make it general, but it's never general enough. Now, usually I have a set of slides that talks about why application need fall tolerance and why you should care about this. given the audience hey I'm going to go um I remove most of that and I'll just say one thing instead which is I'll make the claim that every large scale application implicitly trusts a specific component of the system whether it's in software or hardware for the reliability of computing data so this fault tolerant core provides the abstraction of a

single failure-free component the data store and it's on top of that failure-free component that application logic gets implemented and so effectively applications use this full tolerant core as the root of trust to bootstrap application correctness Today I'm going to talk about distributed trust specifically. And obviously you all are familiar with distributed trust otherwise you probably walked into the wrong room but I just want to define what I mean here. So there's two ways that I think about um that people tend to define distributed trust. The first is as a deployment architecture that allows mutually distrustful parties to reliably and secure shade dedera amongst each other even as a subset of parties misbehave.

So you can think of it as you know a set of banks for example that want to exchange financial transactions without a centralized clearing how like swift that should not be um that should be obvious for the audience here. The other way is as a mechanism to replicate your data to enough other platforms such that the remain the plat the data remains secure even when one of those platform gets compromised. So in this case you might think of using a distributed architecture to replicate sensitive data across several major clouds such that even if one cloud gets compromised data integrity will be preserved and I do think it's important to distinguish the two because they come with certain different assumptions. So distributed trust and spec specifically the latter is growing in popularity as a full tolerant core for several major

services. So signal for example uses it u for key recovery. So when you lose your phone while skiing and need to restore your account, this may or may not be a true story. Uh you can use um this service to recover your key. ACL the Azure confidential ledger is Microsoft distributed trust offering and is used for key transparency, code transparency, so on and so forth. And finally of course blockchains. So the particular model that I'm going to assume for the rest of the talk is looking at scenarios in which you have a well- definfined set of participants from anywhere between say five to a few hundred. They each want to offer a shared service where you can store data and perform computation on it very much like a database. And these parties want to maintain consistency and availability even when a subset of parties misbehave.

And here I'll say that misbehaving participants are called Byzantine. We can use them interchangeably. And if that sounds familiar, well then should it's usually the type of guarantees the Byzantine fall tolerance systems provide. At the heart of these penoly ledgers, there's this beautiful abstraction of a totally ordered ledger or a lock. So every participant in the system agrees on the same set of operations and the same ordering of operations and these guarantees hold even in the presence of a subset of malicious actors. So in the example here um the four banks in the consortium all agree that there's two deposit operations followed by transfer followed by overall. Now again not saying anything new here but let's try and think about why this abstraction is so powerful. The reason why I think it's so powerful is because this shared log

whose validity is attested by all the consortium participants can be reliably consumed. It can be ingested in order to materially to reliably materialize shared state. For instance, Bob here on the left can ingest a copy of the bank store of bank of the log store of Bank of America execute the operations to come to the conclusion that account A has value 10 and account B has value five. Similarly, Alice on the right can consume the copy of the log maintainer chase and come to the same conclusion. And this shared state can be queried just as you would query a traditional key value store or database.

Unfortunately, current BFT systems, I'm not going to say that they do not scale because otherwise I've just invalidated my research for the last 5 years. I am going to say that they have a fundamental scaling limit. And there's two main reasons for that. The first one is that every replica totally orders every operation. This is clearly bad for throughput because execution is both sequential and redundant across all replicas. Moreover, reaching agreement usually requires several round trip of coordination which can often result in high latency. And so the question is this fundamental and obviously this mean many many works to try and chip at this and I'm simplifying here but I would say the fundamentally yes this is a limitation a scalability bottleneck that

is fundamental in the current architecture and the root cause to me is that we're building these systems with a rockart separation between the ordering layer and the mutilization layer. The ordering layer currently is only about trust. It bas is basically saying how can multiple parties agree on how to order the same sequence of bytes. The materialization layer on the other hand is all about semantics in data. It's saying how can I execute those bytes or those operations to generate the database. And because the ordering layer does not understand the semantics of the operation, it just can't do any better. And that's a huge loss opportunity because we know that in practice most real work workloads

primarily consist of operations that access completely different object and those don't need to be ordered with respect to each other. For instance, if Alice here on the left um wants to buy ice cream and um Bob here wants to buy a Ferrari, these operations do not need to be order with respect to each other because they commute independently of the order in which they're executed. they will generate the same state and that's the point I really want to emphasize and actually you made this point earlier just a few minutes ago is that fundamentally we care about the state the materialized state not the log the log is the mechanism through which we can reliably generate the state so until a few weeks ago here I had a joke that said the this held true unless

you had a shop that sells both ice creams and Ferraris it turns out that there is such a shop in New Jersey so there goes my joke but hopefully the idea remains uh remains clear. >> I was waiting for the slide with a picture of the store that sells Ferraris and ice cream. >> I promise I'll go back and buy another ice cream to to take a picture. >> All right. All right. >> So, what should we do instead? Well, if you've got to take one point away from this talk, I want to be this. What most distributed ledgers actually try and want to build is a database. And by merging the ordering layer and the materialization layer into a single entity that is explicitly a database but a database with decentralized trust we can design a system that will scale better and we can do this by taking

advantage of the decades of research on scalable distributed databases. >> So in this picture should should I think of the materialization layer which sort of corresponds to the execution layer that we usually talk about. Should I think of that as turning complete in your case or not necessarily or >> you can think of it as in this case I'm going to say equivalent to SQL which is turning complete. >> Okay. >> Um but the expressivity is going to matter for implementation but not for any other things I'm going to say. >> Okay. So maybe have in mind for the talk applications well expressed by natural SQL queries.

>> Yes. >> Okay. when you advocate thinking about distributed trust as a database, I'm wondering what's the alternative? What's what do what would you say is the not recommended way to think of it? >> I think the over reliance on a log as an executing operation sequentially in the log bakes the ordering requirement of the log with the semantics. Whereas a database explicitly acknowledges that there's going to be mechanism through which you can achieve that equivalence to a serial order. But that's not the end goal. The end goal is instead is the materialized state that provide you some guarantee some consistency guarantees both with respect to malicious

participants but also with respect to just the ordering in which you execute transactions. That's actually the point that I I want to make here which is that the key property that allows database systems to scale is called serizability. And Sarah's burly is this correctness criterion that I'm mentioning which implements the abstraction of a total order. It guarantees an execution will remain indistinguishable from an execution in which every operation was executed sequentially but does not enforce the physical total ordering. And soability specifically breaks down highle operations in like say transfer into a set of physical um read and write operations. So multiple sub operations that even though they physically execute a small units overall they will take

they will appear to take effect atomically and sequentially and the mechanism that database systems use to enforce that is called concurrency control. So they guarantee equivalence to a serial order whereas I'll make the claim that right now in many distributed trust ledgers we are interested in the reality the physical log here we're trying to enforce the abstraction of the log. So this ability to um execute suboperations individually as long as the overall execution remains um sequential appears sequential allows for I'll say two properties that are key to scaling. So the first one is sharding.

It's now going to be easy and natural to partition the object space and a single replica is no longer needs to process all requests. So transactions that touch multiple shards, distinct shards um no longer need to coordinate and transactions that touch multiple shards obviously still need to run an atomic commit protocol. The second benefit is that independent operations even if they access the same shard but they touch different objects can now naturally be executed in parallel. So even within a sh we can get high concurrency which is something that um is challenging to implement in in current BFT systems. Now in any good system work there's I'd say three um properties that we care about.

Performance how well are you actually how many transactions are you going to execute per second? usability, how difficult is it to execute those transactions as a as a programmer, and finally the fault model with respect to what um attacks or threat am I correct against? So, we're going to want to build a scalable ledger um by building a database and what does this mean under those three pillars? Well, from a performance standpoint, we're going to want to allow non-conlicting operations to execute in parallel. From a usability standpoint, we're going to want to support general purpose transactions and arbitrary SQL queries. So, if I put my database hat, I tend to think that SQL is what people use in analytics analytics in OLTP

systems. And we're going to want to try and preserve that legacy code. Now, I realize this is not how people have gone about implementing smart contracts, and this is probably a controversial stake, but I'll say that the pillar of data management has always been SQL. And so we really wanted to preserve that. And finally, we're going to want to remain robust against um arbitrary aka Byzantine failures with respect to a specific threshold of Byzantine failures. Most database systems tend to be separated into two layers. You've got a transactional key value store that handles transactions and persistent storage. And on top of that, there's a query processing layer that handles complex queries like joins, like scans, so on. And so we did the same. We first

set out to build basil, a transactional key value store that supports, you know, general purpose serizable transactions. And then we added um a system called pesto, which can um act as a drop-in replacement for any standard database system. If you're wondering why we called it pesto, well, you know, as life gives you lemon, you make lemonade. So when life gives you basil, you make pesto. And what I'm going to do in this talk is focus the main core of the talk on basil, the transactional key value store. and then I'll touch on some of some of the challenges that you get from trying to build a complex uh SQL query processing layer.

>> You didn't of course answer the question of why it's called Basil, >> right? You derive pesto from >> Basil is an especially um malicious um Byzantine Empire like empire sorry um emperor emperor of the Byzantine Empire. >> Got it. Cool. >> It's also a cute mouse in Disney. Depending on who you ask, you get different explanations for why we chose that name. So let's start with Basil. And again, the key premise of the work is going to be database systems execute most operations in parallel.

Let's see to what extent we can do the same here when we now have to worry about malicious participants. And in database systems there two general strategies. So the first one is locking. So as you access object you're pessimistically going to take locks to guarantee that there are no concurrent conflicting accesses. If you get all the locks you can commit. Now this type of design is pretty simple but in the BFD world there's one big problem which is that clients can acquire lock and then just go get a coffee maliciously. It's not possible to distinguish a malicious client trying to acquire lock and intentionally dosing the system from a transaction that just takes a while to execute and those longunning

transactions are pretty common in large scale systems. So it's really too easy for clients to ded in the pessimistic world and we cannot hold participants accountable. The other option is to be optimistic. That is to execute without locks but validate in hindsight whether there were concurrent unsafe accesses. Now optimistic concurrency control protocols are by design client driven. It's the client running the validation sorry um running the execution. So while in log based systems the server responsible for managing safety here is going to be the the responsibility of clients. And this probably going to sound like a, you know, a really bad idea given I just said the clients can't

be trusted, but we're going to see that it provides the right um degree of flexibility to allow us to build it efficiently. So our mission in Basil is to summarize to put an together an optimistic client-driven um scheme for a sharded and replicated database and to do so in a setting where there are no bounds on the number of malicious clients. The only concession I'm going to make is that just as in all BFT protocols, the number of Byzantine replicas does not increase a bounded fraction F. Now, Basil specifically uses five F+1 replicas and just be patient to understand why normal BFT systems or the majority of BFT systems assume 3 F plus

one. We're going to assume 5 F plus one and there's good reasons for doing that which will become clear during the talk. So to pull this off, we're going to need to start with a solid foundation to work on. And unfortunately, we're immediately off to a rocky start because it's actually nonobvious what sizability even means in the context of Byzantine actors because we could not constrain how such participants will interact with the system. We we can't constrain the harm they will do. So our first contribution in this work was to introduce a meaningful notion of correctness for transactional applications in a BFT setting. This is where Byzantine serability comes in. So what we strive to guarantee is that the execution appears to a correct participants as

indistinguishable from a serizable execution that only contained operation executed by correct clients. So framed differently, we submit that it's completely okay for a Byzantine participant to wreck havoc and violate ISA guarantees as long as every correct participant observes state that could have been generated by honest folks. Just to give you some more intuition, my flight was cancelled supposedly because of thunderstorms. Now, I didn't person personally see thunderstorms, but as long as there was thunderstorms somewhere that explained the behavior of United, that's okay because there's an execution that shows United is honest.

The other way to say it is it's not a lie if you don't get caught. So, as long as there's an execution that is exclusively honest clients that generates the same data, then because I can't distinguish the two, I'm going to say that it's Byzantine. Now, Byzantine sizability talks about correctness, but it doesn't actually tell us much about progress. For example, a correct Byzantine sizable system could systematically abort all transactions. Now, that's correct. That's safe. It's just not a very useful system. >> Sorry, quick question. Yeah. >> Is it also on the previous side, every client should see the same serializable execution or like different clients could see different ones?

>> All clients will see the same execution um of conflicting operations. They may differ in the order in which they see non-conlicting operations. >> Okay. >> So, same as um a traditional serability definition. >> Yes. >> I'm just curious while you're on the slide, what does it mean? I mean, appear indistinguishable from I mean, what would be different if you just said they should see a serializable execution? There's no computational indistinguishability or anything like that here, right? >> No. So in this case we mean uh it sorry what's the difference between um say an exe uh to a correct participant should see a serializable execution.

>> What would change in that formulation if anything >> by indistinguishable here we mean uh sees the same reads uh the same uh read values and uh generates the same rights. So I think we were using the the traditional terminology of consensus um work when we use the word appear indistinguishable but you're right that there's no um computational distinguishability argument is literally the same reads and rights. So that's safety livveness wants us to guarantee that we actually make progress. Now the traditional um notion of livveness in VFT systems is you provide a response.

Here we want a slightly different notion because we want to avoid your transactions repeatedly aborting aborting aborting aborting. That's guaranteeing a response just not a very useful one. So to address this issue we introduce a sort of more general notion of um BFT correctness of BFT livveness which we call Byzantine independence. And Byzantine independence says that no group consisting of only Byzantine participant should be able to single-handedly decide the outcome of an operation of a transaction. Now achieving this property is not easy. In fact, it's not one the leader based system can achieve and that's because the leader has undue control over transaction ordering and is able to inject conflicting transactions to

influence the result. So again, we can't prevent your transaction from aborting because there might be a legitimate client that happens to access your data at the same time, but we want to make sure that Byzantine either clients or replicas can't force you to systematically abort. So now that we have sort of strong notions of correctness and progress in tow, the question becomes how do we actually realize them in practice and how do we do so efficiently? And here there's a tension between performance in the common case and robustness to the to failures. So in the common case you want to be able to process transactions as aggressively as possible to maximize system throughput. So this usually means favoring a concurrency control protocol

that is optimistic and assumes that transactions will commit will mostly commit and not abort. Now this includes protocol like optimistic concurrency control or multi version time stamp ordering for those of you who are familiar. Unfortunately, if you're not careful, this optimism can be leveraged by Byzantine actors to wreck havoc in the system, stab you in the back, and hurt through if we're not careful. So for robustness, we tend to want to actually assume want to favor pessimistic protocols. And so there's a tension here that we have to resolve. We want good performance in the common case. So we want to be optimistic, but we want robustness under failure, meaning that at times we want to be pessimistic. And this challenge is sort of reflected in Basil's architecture. So Basil consists of three core components.

A concurrency control protocol, a commit protocol, and a fallback protocol. The concurrency control protocol allows non-conlicting operations to execute in parallel. The commit protocol is driven by the client and is going to aggregate replica votes to determine whether a transaction can commit across shots. And finally, the fallback protocol is going to ensure that anonymous client can never be blocked by a malicious client from committing. Intuitively, think of an honest client waiting for a lock to be released forever or waiting forever for a dependency to commit. The fallback protocol is going to ensure that an honest client can always can always proceed. So to execute transactions, Basil offers a fairly classic begin,

read, write commit interface. So in Basil, a client starts a transaction and begins executing individual read and write operations in parallel with other clients in the system. transactions are what we say interactive meaning that clients can dynamically issue the next read and write as they execute the operation. So here the right way to imagine is not me sitting by behind my keyboard and saying read hm what will I do next right no it's um having those operations embedded in the application and then making pointwise calls to the database so you might have all written a web app at some point use something like a JDBC driver to talk to my SQL database and you'll you know do a my database start blah blah blah you'll

write a bunch of Java code or rust code whatever My database read do a bunch of code. My database.right do a bunch more Java code. My database commit. So by interactive transactions we mean general purpose transactions are embedded in the application code. And this is to contrast with store procedures which are pieces of code that you actually um upload to the database and the database executes it once. The reason for why we want interactive transactions is the database administrators really do not like store procedures because it requires two different languages. It's complicated to upload and manage. This is usually where people tell me no blockchain would ever want that. That's usually the key distinguishing factor in our model and

the smart contract model that people tend to tend to challenge me on. >> Sorry for clarity which is which maps on to which? So the general purpose interactive transactions is how people like to use database systems where store procedures are much more like the smart contract model where you upload a store procedure that will be executed server side only. >> Okay. >> And this is there was a study um a few years ago that said the database administrators really do not like store procedures um because of the lack of generality and uh having to maintain multiple versions of the code and having to use a different language. So in Basil um writes a buffer locally until execution ends and the concurrency control mechanism is going to detect at commit time any concurrent conflicting operations um that happened on that

replica during the validation phase. So I won't spend um any time on this but for those of you who interested the concurrency control that we use in Basil is something called multi version timestamp ordering that we adapt to be robust to Byzantine um actors and it strikes the right balance of optimism and pessimism. Now, don't expect if you know what it is. Won't talk about it more. You won't need it for the rest of this talk, but I'm happy to talk about it in the in the next week. Instead, I'm going to focus the majority of my talk on the commit protocol, which is once a transaction has finished executing. The role of this commit protocol is going to determine whether a transaction can commit based on the result of the validation check. Now, the validation check determines whether committing a transaction would validability. That's

multi version time stamp ordering. And the commit protocol is going to somehow aggregate all those votes from the different shards and replicas to determine whether the overall execution is still sizable. Now the commit protocol and this is true for all distributed databases consists of two main phases. So in the prepare phase it must ensure that all shards agree to commit a transaction. And a shard is going to agree to commit a transaction if a majority of replicas in that shard agree to commit the transaction. At a very high level, a replica can commit a transaction if no concurrent conflicting transaction has already committed. The rightback phase is then going to aggregate uh these um shard votes and either vote to commit a transaction or abort. Now in Basil, the commit protocol

is client driven meaning that the client drives a commit and there's no intermediate transaction manager. And the reason why we chose this approach is because we want the client to be responsible for its own destiny. We don't want the client to hand over responsibility to a transaction manager that could potentially be malicious. So since the rightback phase is basically just aggregating uh votes across shards, I'm just going to simplify my example to say that there's a single shard in the system, but you know we um it works for every it works for multiple shards. A shard consists of several replicas. In this case, we have five F+1 replicas. So let's set f equals 1. One malicious replica gives us a total of six replicas.

And let's say now that Mr. Bob here wants to figure out whether it can commit transaction T. Now in the simplest simplest case, all replicas vote to commit a transaction on this shard. So Bob gets six votes to say I can commit. Great. Fantastic. That's the simpler case that kind of shows you the the naive case. There's no concurrent transactions and there's no concurrent conflicting transactions and there's no other uh participants, malicious participants. Let's look at where it gets more complicated.

So the first challenge in deciding whether to commit a transaction in this setup has nothing to do with BFT. Replicas can legitimately receive conflicting transactions in different orders just because of the internet. the internet and so could legitimately disagree on whether to commit a transaction. So for example, assume that you have a concurrent transaction T prime that conflicts with T. If a replica receives T first and then receive T, well, it might vote to abort T because it says, hang on, I've already voted to commit a conflicting transactions T prime, so now I can't commit T. But a different replica could not have received T prime yet, and so be completely fine with committing T. And

you can end up in a situation where half of the replicas vote in favor of committing t prime and half vote against committing t prime. And this is just through benign reordering of transaction um because of the speed of light being different across the world. Sorry leading to different roundtrip times across the world. The second challenge is obviously that Byzantine replicas can lie. They can either vote to commit a transaction even though they've already voted to commit a conflicting transaction. So in this example here, replica 2 could say, "Yeah, sure. I've already voted to commit T prime, but I'm still going to vote to commit T." And that would violate Byzantine sizability,

meaning that we would end up in an execution that could not have been generated by honor clients executing their transaction. And they could also vote to abort a transaction even though they have no grounds for doing so. So replica one here could vote to abort T even though it hasn't seen any reason any conflicting transaction and that would violate Byzantine independence. Now the final challenge is that clients can be malicious. They can either crash halfway through running the protocol or they can intentionally delay sending the commit message or potentially even send different messages to different people.

And at that point, it becomes necessary for an honest client to finish committing the transaction of the malicious of the faulty client. And we need that because we want honest clients to be to have their own destiny in their hands. So we never want them to be blocked by other clients uh failing to finish. And there's a challenge here. So in any BFT system for livveness if you have n total replicas you can never wait for more than n minus f responses because f of those people might have died they might be crashed. So if you want to make progress the maximum you can only ever wait for is n minus f. So in this case here let's say that Bob

waited for n minus f equals four replicas. So the first four it saw three commit and uh two abort. So Bob says, "Okay, I've got a majority of commit. Let me commit. Let me tell my users I've committed and send an asynchronous write back to notify the server." For whatever reason, the writeback messages gets delayed. Bob doesn't send it. So Alice says, "Well, I want to commit my transaction, too. I don't want to wait forever for Bob." and it tries to finish a transaction for Bob so that it can execute itself.

But again, Alice can only ever wait for N minus F responses. And so Alice happens to get responses from the bottom four replicas. And now Alice has three votes to abort and two vote to commit. Now the key issue is that we don't know whether Bob already sent the final writeback message to other shards. So Bob could have already decided to commit and so Alice somehow needs to come to the same conclusion as Bob. So based on that let me take you for the next you know five or six minutes on how we went about designing the commit rule and the abort rule. So the what I'm going to focus on meat of this talk is what does this look like um in the system and specifically how do we guarantee

Byzantine independence and Byzantine sizability given the challenges that I've just outlined. So the first thing that we have to worry about is how to maintain Byzantine independence. And as a brief reminder, Byzantine independence says that a Byzantine replica should not single-handedly influence the outcome of a transaction, which we're going to rephrase as a Byzantine replica should not single-handedly cause the transaction to abort. What does this mean? Well, it means that to abort a transaction, we need to ensure that at least one honest replica wanted to abort that transaction. If we have a majority of F Byzantine participants, this means that in order to abort a transaction in a way that always guarantees Byzantine

independence, we need at least F plus one abboard votes. That tends to be a magic number in BFD systems. So, we have our first requirement. We can only abort a transaction when we have at least F+1 votes to abort. Now the second requirement that we have is Byzantine serability and Byzantine serability says that if TNT prime conflict they should not both commit. Um that's the necessary to guarantee equivalence to a serial order. In order to enforce this we're going to rely on some help from honest replicas.

Honest replicas follow the protocol. So we know that if you're honest, you will never vote for T and T prime to both commit. So what we're going to do is we're going to force every quorum, every commit quorum to include to intersect in at least one honest replica. Why? Because if every transaction needs a commit quorum to commit and those commit quorums always have to intersect in one honest replica, that honest replica will never vote to commit both T and T prime if they conflict. Right? So if you know that T conflicts with T prime, then I'm going to really hope that if I make my qums

large enough such that they intersect in whoever is honest in this room, then we'll never commit both in T and T prime if they conflict. >> Should the word intersection appear on the slide somewhere? >> Yes. >> Oh, okay. Um and again because we have only F uh misantine participants as long as our quorums intersect in F+1 replicas we know that one of those replicas will be honest and so that replica will never vote to commit TNT prep second requirement.

Now the final challenge was linked to failures. Specifically, if Bob saw the first N minus F responses and crashed or intentionally delayed sending a message and Alice tried to um finish Bob's transaction, we wanted to ensure that Alice can never come to a different conclusion than Bob did. In other words, if Bob vote to to abort the transaction, come to the conclusion he wants to abort, Alice should also abort. And if Bob said commit, Alice should also say commit. Meaning that the voting decision should be deterministic. Now, this is where unfortunately I don't have a great solution for you in that we can prove that if you get fewer than 5 F+1 commit

votes or 3 F+1 abort votes, we're going to need an additional logging phase to record the decision. And so we end up in a situation where our transactions commit in a single round trip in the majority of cases, but occasionally we'll need a second round trip to finalize the decision before telling the client commit or or abort. So we end up with these three requirements for our commit rule. Requirement one, you only abort when you have more than F+1 abort votes. You only commit when you have sufficiently many votes that your commit quorum intersects with all other commit quorums in at least one honest replica.

And finally um if you get fewer than a specific threshold of votes you need an additional round trip to record your decision such that other clients will always come to the same conclusion as you. Now you might notice that I haven't actually told you the size of requirement two the size of the commit order. And the reason why I haven't told you that is because we're talking about intersection that size depends on the total number of replicas in the system. So at the start of the um talk I said most BFT systems use 3F plus1 replicas. That's kind of the standard threshold.

So let's see if it works for us. Well we want our commit quorums to intersect in at least one honest replica. So we have 3F plus one. This means our quorum size has to be at least 2 F+ one. Why? Well, if you have two F+ one, you have two F+1 here. If you if you do the math, if you sum of sum them together, that gives you um 4 F plus2. Well, we only have three F+1 replicas in the system. So, F+1 must be counted twice. That's kind of the rule usually to figure out quorum intersection. If you have two F+1 and two F+1, you overlap them. they need to overlap in at least F+1 replicas. Now, unfortunately, in a system with three F+1 replicas,

we're only guaranteed responses from n minus f people. Namely, we're only guaranteed responses from two F+1 nodes. And so, we can end up in a situation where we happen to get two fit votes and one abort vote. And there we get stuck because we get stuck. We cannot commit because our 2F is smaller than 2F plus one. So we're not guaranteed that this commit quorum will intersect with another commit quorum in an honors node. But we also can't abort because this abort vote might be from malicious node.

So we're stuck between either risking violating Byzantine serability or we're stuck with risking violating Byzantine independence. Let's up the number of replicas. 4 F+1 you end up in the same situation as the 3F+1 case. But now let's look at 5 F+1. With five F+1 replicas, you need a commit quorum of size 3 F+1 in order to guarantee the F+1 intersection. Again, 3 F+1 plus 3 F+1 equals 6 F plus2. But we only have 5 F+1 nodes. So F plus one of those must be counted twice. In a 5 F plus one system, we're guaranteed a response from N minus F nodes from four F+1 nodes. And so we end up in a situation where

we're guaranteed to either have a commit quorum or no quorum. So either from our four F+1 responses, we're going to get three F+1 commit votes, which case we're good. Or if we don't get three F+1 commit votes, then we're guaranteed that the number of aborts that we get is at least F+1. And so we have the guarantee with five f plus one nodes that we either have a commit quorum or have an abort quorum. And that's what enables us um that's what why the requirements of 5+1 commit because we want to guarantee Byzantine independence. There's also few few other reasons for why you might want to have 5F plus1 namely we have the ability to commit transactions in a single round trip. You lose that with 3F plus1. Um and that matters if you're

contention bottleneck in the system. Um, and so even though the number of replicas may appear higher, if you actually count the throughput that we can get, like the throughput per machine, um, 5F plus1 ends up being cheaper than 3F+1. >> You saying because it's one round trip instead of two. >> Yeah, >> that's the difference. Okay. >> So, I'm just curious, is that like a provable statement that that you cannot do one round commit with 3F+ one? >> Yes, that's a pretty well-known result. >> Yeah. >> Yes. There's many okay there's many results that suggest this is not possible when you have uh no leader and a fast path. I haven't yet seen and we were actually thinking about that at some point a form of proof that phrases

it in exactly that way >> and I guess the same for 4F plus one as well. >> 4F plus1 we actually looked at the the Byzantine dependence part. So I'm less sure about the 4F plus one result. The 5F plus1 99% sure that this is an impossibility result but I haven't seen it phrase in that way. you seem to be >> in the BFT case this has been written down um a few times but I'm not quite sure whether in the database setting is is different because the intuition you give is actually very different from the um BFT one round commit >> so in the BFT case we haven't seen leader list plus um one round commit >> leader list I mean I I think we can but we can prove even with a leader you

cannot do uh one round of voting commits so leader list is even only harder Oh, sorry. This is not one round always. This is the existence of a fast path. >> Sure. Sure. >> With a with a two-phase >> fallback. Yeah. Even whatever good things happen, you cannot do one round commitment. >> For context, it just so happens that several people have been spending a lot of time in the last three to four weeks specifically about fast one round fast paths. >> Yeah, for one round fast path, you end up needing three fus one replicas um like all of them. So this is a disa work you or like um other others just this is the first one for in for the 5 plus1 leader list we you the fast path needs 5 plus1 but I'm be surprised because I haven't seen a proof expressed in our

way because we're actually looking at it at some point >> we should chat offline >> yeah there's there's a lot of good conversations to have about this yeah >> the last part is that we want to we know that clients cannot abort their own transactions or cause serviceability violations but clients can always store and so the fallback protocol is the mechanism that we use in basil to allow ow any client to drive the commit protocol but not to change the outcome of the transaction. So we want clients to have the tool to drive the decision themselves but we don't want them to have the power to either change the decision or um come to a different conclusion than other clients. I'd say that the fast path is actually probably my favorite part of the protocol, but it's, you know, relatively involved. And so, um, it has

nice properties. In the common case, it requires only a single additional roundtrip to commit the transaction, which limits how harmful Byzantine clients can be, um, generally. And the other um benefit is that it only affects contending transactions. So, in a traditional BFT system, you have when you have a view change, when you have a leader election, the system stores. Here the forback protocol only affects transactions that happen to conflict with the transaction that you currently store. Now there's a number of challenges that we had to address. Um client equivocation multiple clients live locking but in the interest of time um learning about this is hopefully one of the many pleasures you get if I could convince to you to read the paper and instead I'm going to give you some

indication of how we do about performance. So we implemented basil and evaluated it using three common online transaction processing systems. So TPCC which is a standard database benchmark that does um shopping cart transactions. Small bank which emulates a small banking application in retwist which is a clone of a simple um social network and they experience varying levels of contention and we ran um taper against three additional baselines. So the first is taper which is a crashful tolerant distributed database that like basil merges concurrency control and replication and the other two are BFT systems that follow sort of the standard modular approach of how you might go about designing things today which is that you layer a two-face commit protocol and a concurrency control

protocol on top of a blackbox consensus protocol. So here we picked hot stuff and BFT smart which is an efficient implementation of PBFT and we picked those those two to be representative of state-of-the-art consensus protocols. So let's first look at the throughput for our workloads in a failure free setup and here higher is better. So on the left we found that basil is within 4x of taper so four times slower than a crash tolerant database and that's a good result. That's something we were happy about. The main sources of overhead that you get is the need for signatures and larger quorum sizes to tolerate Byzantine uh failures. And signatures, I mean, they they've gotten a lot cheaper, but they still take up space in your CPU. And so there's a lot less work that

you can do. Uh whereas Taper gets to use those extra cores to to process additional transactions. >> How many replicas? Um, so we have a total number of of of shards and so basil uses fewer shards because it uses more replicas whereas taper uses more can can take advantage of those extra replicas to to do more throughput. >> No, I meant how many replicas are in these experiments. >> I'll have to check but um I think it was three shards um with Basil uses 5 F+1, Taper uses 2F plus one and hot stuff and um BF using 3F plus one. So the standard replication factor and I'm pretty sure I'll have to check in the paper but I'm pretty sure you use three shards for basil and scale it correspondently for taper hot stuff and BFT smart

>> but like what was f >> sorry f was one >> f was one okay >> so the the good news is that um we were able to get higher throughput than um the baselines built around the traditional BFT systems so between 5x and 3x respectively for TPCC and the reason for why we're able to get better performance is that basil achieves much lower latency which in a contention system translates to higher throughput and this is because it has the ability to execute transactions in parallel and the actual time it takes to commit a transaction is in most cases about 97% of cases a single round trip in basil whereas it takes at least two round trips um in the other systems now of course the so good performance is great in the failure-free case but if it comes at the cost of catastrophic performance

in the failure case that's not good and so we wanted to evaluate also what happens when clients misbehave and when replicas misbehave behave. So clients can try to fail in two ways. They can stall, they can start but not finish the transaction, the commit process, or they can try to equivocate, meaning that they can lie and send different decisions to different replicas. So I won't go into a huge amount of detail here about the results. I'll just give you a sneak peek. When clients stall, specifically when when 10% of clients stall, then we're going to see about a 10% throughput drop. And the reason for why we see about a 10% throughput drop is because other clients have to finish the work for them. So they have to spend an extra round trip executing the fallback protocol and it goes pretty linear. So if you have 40% of clients stalling, you

end up with a 40% throughput drop. The interesting result to me was the equivocation part. So in the equivocation part, we were really scared. We were like, okay, now the fallback is a lot more complicated than the equivocation part. Are we going to submit this paper? Is it catastrophic? And it turns out that with 40% faulty replicas, faulty transactions, sorry, we see less than a 5% throughput drop. And that was a really surprising result for us. And the reason why we have this is that it's actually really really hard for clients to get enough conflicting votes from replicas so they can actually send conflicting decisions to people. So in most cases, replicas tend to be pretty much in agreement in order. And because of that, it's actually really

hard for clients to generate enough conflicting information to perform the equivocation successfully. Now if we artificially allow clients to equivocate by you know then obviously performance become catastrophic but in the real case like in the realistic case there's usually enough consistency between replicas and not enough um contention that clients can actually equivocate successfully. So this is all I'm going to say about basil. Obviously I'm here for the week and you know this was a quick overview but you know I'm very much happy to to talk in more detail and it's also the paper's available online.

In the last few minutes I'm instead going to move on to what we built on top of basil namely pesto. And the reason for why we built pesto is because so far I've been talking to you about point queries. Bob may want to withdraw some money. And to process this request, the Tomkins Bank or the Ithaca Bank or the Blah Bank who manages Bob's account is going to simply look up Bob's balance. Going to do a get request. Now, these are day-to-day operations that make up the bulk of transaction applications. And you know, for the database folks here, this is when you access a primary index, for example. And database want you to do that. That's what they're geared for. That's what they are implemented efficiently for. But applications also usually want to perform range queries that should stay

range queries on top. Sorry. So for example, you know, Bank of America may want to know how many customers it is serving in Berkeley. So using a key value store interface becomes really expensive to do that because it must first read the entire database then perform the additional aggregation to the client and you know the client has to read all the intermediate data and then perform the computation to get the results. So implementing this range query is cumbersome for application developers if they only have point queries because they need to manually specify the computation process and it's also inefficient because we are going to issue many many read requests when the result might just be two or three um rows at the end and that's especially

expensive in a BFT setting because of the fact that you need some proofs to validate the correctness. So you know each get that you do comes with validating a signature. So if we had a choice, we'd much rather execute such queries through an expressive query interface like SQL and rely on the back end to execute the query. Now this looks easy to use. This is efficient. The problem though that in basil Bob he's trying to execute his SQL query here has no way of asserting the validity the integrity and the freshness of any one result because without retrieving the reset itself there's no trivial way to confirm that a given replica's computation is correct and even if we're using some fancy

cryptography to validate the correctness of the result there's no notion of freshness between two possibly different results based on a different state. So it's not just the correctness of the state, it's whether or not we're reading from like if we're given two different results, whether or not those replica like which one is correct, which one we should use because those replicas might have processed transactions in different order. So the intuitive way to solve this problem is just to simply collect enough matching repries to guarantee at least one correct replica has sent it. Right? So if for example I get uh six responses and I have at least two replicas telling me that the result is two of my query then I know at least one honest replica is telling me to and that's good enough. The problem though

is that our inconsistent design where replicas can process transactions out of order comes back to bite us. Even correct replicas in basil may genuinely have different state. So here on the slide the you know the first key um could have the the first replica could have processed for key one red red blue and may still be waiting for light yellow whereas the state two could have already seen um light yellow and be waiting for red red blue. That's perfectly okay. And this means that we can't actually guarantee we will ever um see matching results and that's going to kill livveness. Now, the alternate strategy is obviously to return to a total order where we order every transaction. But I've just spent the

last 45 minutes telling you that we want to not have a total order. So, it' be kind of a sad way to end the talk if we just say, "Well, we'll go back to a total order." So, what can we do instead? Well, instead, we're going to cheat. And as any good cheater, I'm not going to reveal all my secrets, and I'm just going to give you the highle idea and tell, you know, please do check the paper or talk to me afterwards uh for for the details. In reality, we don't care for the state to be consistent. Instead, we only care for the state to appear consistent to clients. So, we only require consistency for the query that we are currently making, not for any arbitrary query that we could possibly be making. And individual queries don't normally touch the same state, the whole state, sorry.

So, it's much cheaper to bootstrap consistency for just the query that we're making than it is to synchronize all replicas all at once. And there's a bunch of challenges in doing so. Let's say that Bob sort of sends the queries and waits for responses. If we're lucky, replicas already match and we have nothing to do. And it turns out that that's the case the majority of the time because in practice, again, most operations commute. And so, replicas don't diverge a whole lot. you have to get unlucky to catch a point where they diverge. When replicas don't match, however, then once again, we're going to double down on our client-driven ethos and basically allow the clients to create their own luck. We're going to have Bob propose a consistent state for

the query that he's making himself. Replicas can then synchronize on the missing data and materialize the particular state on demand to guarantee um consistent execution. You know, at a high level, this solves the freshness problem because we now have the guarantee after this potential extra round trip that replicas will be in a consistent state. But obviously, the devil is in details. So, specifically, we're going to need to ensure that the client will always be able to propose a valid snapshot, aka one that'sable as well as fresh, okay, not a snapshot is infinitely far in the past, as that can cause abort. So specifically, we don't want replicas to be able to trick or the client to be tricked into proposing something that is too stale or that does not represent a consistent state.

Second, we're also going to need to revisit how we do concurrency control. So one of the main problems we faced and we were surprised by that actually is that range queries and optimistic concurrency control typically don't play well together. Optimistic protocols have a validation phase like the one that you know we use in Basoin that says that no writes should interfere with the reads that I just did. And they do this by sort of tracking the rows and the versions that we access and importing if we miss something. But if we're doing a range query, then we we logically read literally everything. We might have filtered a bunch of stuff, but we logically read everything. And so now it means that literally a single write can invalidate our read of, you know, 2,000 3,000 transactions.

We don't want to acquire a giant lock on this because this would kill performance and locks are bad for reasons I said before. So we need a new way to reason about concurrency control for range queries in the optimistic setting. Now the way that we approach this is by a technique called an adaptation of something called precision locking which I'm happy to talk about offline. Instead I'll just give you a very quick snapshot in the last minute of the numbers that we got. So the thing that we were really excited about is that we were able to run um complex SQL benchmarks unmodified. So we took again some standard um uh SQL benchmarks something like auction mark and season and those have fairly complex joins fairly complex query results and we were able to run them on modified

with decentralized trust our system our BFT system you know could take existing code run it and so it's fully SQL compliant where fully is the work of PhD students you please don't run this in production yet so the big asterics is obviously I'm sure there's corner cases that for doesn't work fully The good news is that we were able to get continue getting three to fivex better performance than the prior layered approaches again because we're able to get much more concurrency scale the size of the the latency down so that we could get higher throughput.

What was promising is that depending on the workload we were actually comparable to a commercial database like posgress. So in cases where we had um high contention we're able to actually almost match posgress performance whereas in cases where we um posgress was a CPU bottleneck again we were limited by the fact that we had to do a lot of cryptography and additional replication but we were actually within 2x of posgress which to us was a was a very um promising result. Now this is all going to say for for Basil and Pesto. Obviously I want to acknowledge that the the people who have done most of the the low-level work um are my PhD students specifically the um Pesto and Basil is primarily the work of Florence Feraya uh

his PhD thesis and he was um supported by Neil Geredaran in the in the Pesto work who did much of the engineering uh work related to taking an existing SQL query engine and adapting it to the BFD setting. Before I finish, I just want to highlight a couple of other projects that I think uh will be of interest to hear. Specifically, we've done a lot of work on looking at how consensus protocols interact with realistic networks and how we can improve the robustness um of consensus protocols in that context. We've looked at how to design distributed trust protocols where you do use trusted enclaves because they're pretty good most of the time, but you are wary of trusting them always because they can stab you in the back and vulnerabilities can be found. And

finally um we started revisiting how we think about failures to begin with. So you know failures are inherently probabilistic. I have a 3% failure rate on my disk. I trust you with about 15% probability where 15% might be determined by some risk analysis somewhere else. How can I express this notion of probability into consensus? And how can I refine my fault model such that it's smarter than just fals 1 fals 2. Whoops. We had fals 3. We're toast. So with that I hopefully I've you know convinced you that append only ledgers are just databases and if I haven't got a whole five days to do so. So thank you. Any questions?

>> I think a lot of the room is probably trying to map this to kind of like you know consensus stuff that you know rewritten out. So what I'm trying to think about is around like timing models which right which you know partial synchronous kind of stuff which I often think of it's the most common origin the 3F plus one. >> So how should I think about this more from a database? This is all in the partial synchrony model. There is no difference to the partial. >> So is that and then in distributed database applications is that should I think of these shards as building historically in the same data center and this is what I'm trying to think about why partial synchrony here >> um why partial synchrony because we need livveness and in order to do that there is a one point where we need to elect a

leader. we have a view change. We need to elect a leader to get around live lock. And so you need enough um you need enough um people to be in the same view in order to um have the leader decide. So in order to have livveness, we end up deep down the stack having to elect a leader to get away from live lock. The leader doesn't get to decide and order transactions, but it does get to finish other transactions. And so that's why we're we get back into the partial synchrony model. Maybe a different way would ask the question. I does does anyone ever look at the synchronous model in the distributed database context or that's just like timeouts are just out of the question or >> I think it depends on the systems that you want. So for example there are

systems that are based on train replication. There are systems that are based on primary backup those effectively assume a synchronous model. >> Okay. >> Um the systems that are that use Paxos at some point. So if Cockroach DB has a raft implementation, TIDB has a raft implementation end up inheriting the same limitations. >> Yeah. um and benefits of the partial security model. >> Okay, >> this is more like me trying to understand the protocol uh better. But like so if you have a 3F plus one quorum saying uh this is to be committed and then an F+1 abort certificate for it like uh in this case how would it be resolved if the client is honest? This cannot happen because F+1 abort certificate cannot happen. Like an

honest person won't see a conflicting transaction by an honest client. But if a malicious client sending like one uh award message to the one honest and then to F plus one honest is sending a commit. Then how is this resolved? >> So this is why you need a second phase because it is so what would have happened in this case is that you had two F+1 people say commit a transaction. F plus one people say a border transaction and so that that node in the middle that happened to see was able to trick uh the client into forming both a commit quorum and an abort quorum. Um at that point both are safe as long as you do a um extra round to ensure that whatever decision you the

first client comes to other people will also come to the same decision. So in this case there's one like your commit quorum is large enough that you know that other people will it will intersect and your book quorum is also large enough that you're vi not violating Byzantine independence. The key thing here is ensuring that subsequent clients will come to the same decision as you. And so in this case, we're going to force the client to do an extra logging phase to say, hey, look, I am going to I have decided commit. And that logging phase is going to intersect with all future commit and abort quorums of other clients and that's what's going to ensure the determinism.

>> Who is uh committing in the system? Both clients and replicas or just the clients? Um clients commit replicas when they do the fallback can finish a transaction on behalf of a client that solicited it. >> So replicas commit one round later than the client. Is that right? >> Yes. So the way that the fallback works in our casing is that the client is going to try and finish a transaction. It's going to wait some point. It's going to say well they've got something that I'm blocked on preparing transaction. Um and is going to trigger a fallback. Um, in the easy case, it's just going to get matching results. Um, in the more complicated case, it's going to get

responses from replicas that um, suggest there's been some inconsistency or maybe there's been a previous fallback or maybe there's been equivocation. And at that point the system is going to elect a fallback leader internally where the fallback leader is going to aggregate the votes and based on the votes that already take place is going to finalize the decision before responding to the client. >> The questions for that? Thanks.