Consensus Under Adversary Majority with Joachim Neu | a16z crypto Research Series

Transcript

All right, welcome everyone to the second research seminar of the summer 25 series. Very happy to introduce someone you all know, Yokam Noi, our colleague here at A6Z crypto where he's a research associate. uh today's going to answer a bunch of um confusing questions like why do some people say uh that you can do synchronous consensus with 99% adversary whereas some say you can't do it with 51%. also like what is a client actually really? So, Yoken, >> thank you. Great to be here and great to give this talk. Uh thanks for the introduction. Um thanks for spoilering the talk.

Um yeah, so I'm going to be talking about this uh recent paper of ours uh which we presented a few weeks ago at financial crypto. This is joint work uh with my uh former colleagues at Stamford, Stravatson, New Yus, and our adviser David Um, so I'm going to, you know, zoom all the way out and remind you, uh, what we're all here to do, right? We want to build blockchains. Why? Because we want to decentralize certain applications. Think for example, voting applications, um, maybe monetary applications, maybe just replicating a database, right? And, uh, the approach we take to this uh, is this idea of a magic computer in the sky that we want to build, right? is a uh sort of a a computer that arises out of

a simulation or an emulation uh by a bunch of participants that sort of run a a distributed protocol and then from that comes out this magic computer in the sky. And the magic computer in the sky is great because everybody can read its state and everybody can provide input uh to that computer and nobody can stop or corrupt the execution of that computer, right? And then within that computer we run our application logic and that's how we sort of decentralize these applications. Uh how exactly do we do that? Typically that problem sort of decomposes into two steps. Right? The first one is there are inputs to these applications. Um and we somehow need to agree in which order uh we're going to execute uh on these inputs. Um and then we're going to have a deterministic

state machine that sort of uh describes the the logic of our application. And once we've all reached agreement on uh in what order we're going to process transactions uh then since it's a deterministic state machine we'll all see sort of the the same state transitions uh of that of that state machine. So that leaves gets us to state machine replication consensus and and that's what this is about right and so the question then is okay we want to build these state machine replication consensus protocols up to what fraction of adversary participants I call them validators here does the protocol remain secure right seems a simple question and if you go and try and google this question uh you'll get a bunch of different answers for different protocols right you may hear that PBFT

style protocols such as ethere such as hot stuff or Ethereum's Casper FFG um are secure uh up to 33% adversaries. Uh you may hear that there are other protocols like these more kind of blockchain native kind of Nakamoto style consensus protocols, longest chain protocols like Bitcoin or Aborros or also synchronous BFT protocols like uh sync hot stuff. Uh they're secure up to 49% adversaries, right? And then if you look in other corners uh you may find uh people saying oh we have this uh you know these great consensus protocols over here uh that allow us 99% security.

So which of these numbers is correct right uh is there is there you know somehow you know there must be an like if we have protocols that work for 99% why would we operate in 33%. Right? Or if we have 99% why would we operate a protocol that is uh 49%. Right? And so if you dig a little bit deeper, you'll find okay the the difference between the first two columns here is easily explained right the first protocols assume a partially synchronous network meaning the network may be you know have a hiccup uh sometimes and and have very high network uh latency. um and the first category of protocols uh remain secure even in that setting whereas the second category of protocols uh require

synchrony but and okay so first category is sort of sort of out right um but then even for the second for the third uh column here uh you'll find that the assumption they state is uh all we need is synchrony right so you know on the one hand we have this blog post for example from vitalic but there's also other uh works recent works even in um in S&P for example that describe these sort of um blockchain protocols under malicious majority right and on the other hand um you know this I took from one of Link's papers uh there is uh you know impossibility proofs saying actually you know you you can't operate beyond sort of uh an honest majority

right so what's going on right how how do we clarify this yeah >> so I assume the reference one and two did not claim their protocol is SMR, right? They may say consensus or other things. >> Correct. Yeah. That that's that's that's where we're going to go. Yes. Um okay. So in order to understand this is a you know good good comment and and that's the that's what the next slide is about right. So we need to dig a little be a little bit deeper into what do we mean when we say consensus right? And so we think of a blockchain. I've teasered that a little bit on the first slide, but you know, let's be a bit more formal sort of about the setup of the kind of ordering protocol that we're trying to build, right? We have transactions.

These are inputs to to our chain. Um, and then we have a set of validators, right? And um, in the first sort of, you know, naive setup you you may want to write down, you say, okay, we want to build an ordering protocol where transactions are input to these validators. The validators talk to each other. they run the protocol and then at some point they output logs, right? They output an ordering of these input transactions. Okay. So what do we assume about the validators? We assume that basically all the validators kind of know each other, right? There's public key infrastructure uh for them. Um and some of the validators can be malicious, right? But overall we have some sort of a threshold honesty assumption, right? Maybe it's

99%, maybe it's 49%, maybe it's 33%, but that's sort of the the general setup, right? But actually this uh you know flavor of consensus is not state machine replication consensus, right? This is what we would call atomic or total order broadcast, right? And that's not what we're after. Blockchains work differently. Namely, how? Well, there's, you know, a crucial entity sort of in the system um that are clients, right? that are participants who are part of the protocol but they're not part of sort of running the backbone of the consensus protocol but rather they're interested in learning the protocol's output right think of merchants uh wallets block explorers all the sort of

uh you know sort of endpoints that in the end will output this log. Okay. So really there's a another category sort of uh uh of entity um namely clients and it's actually the clients who are outputting these logs. Okay. So and the the thing about the clients is we have no public key infrastructure on them meaning we don't know how many there are. We don't know who they are. They cannot sign messages. Right? Um and some of them may also be malicious. But in particular we don't have any sort of threshold honesty assumption. Right? for all we know maybe that all these all the all the clients are malicious or most of them okay so that's our setup that is uh what

I call state machine replication consensus okay and the question that we open up uh on the first slide or in the second slide about this uh the question of the resilience right comes down becomes clear and becomes explainable once we look at what assumption the question now is what assumptions do we make about these clients? Right? We've discussed very early on that there could be synchronous networks, there could be partially synchronous networks. That's usually about the communication among the validators. But what about the communication between the validators and the clients? What about the communication among the clients?

What about um for example uh some of you will will have seen the sleepy protocols, right? Where validators can uh can can go to sleep. What if clients can go to sleep? Okay. And it turns out that these modeling uh um differences sort of explain uh the the differences that we've seen before. And that's what the talk is about. Okay. So, concretely uh this 49% result that we've seen early on, right, assumes that clients are sleepy and silent. In contrast, this 99% result that we have seen basically assumed that clients are always on and communicating. What does that mean by sleepy? By sleepy clients, I mean there could be clients that basically um you

know are not part of they're not following the blockchain at every point in time. Okay. Sometimes maybe they only wake up like 3 years after the project has already been started or maybe they go to sleep for a few hours every now and then because they take a flight and it's on a phone or you know merchants may not be following the chain when they're not actually expecting uh a payment or something like that, right? In contrast, always on clients are ones that are they're always following the chain. Okay. Um what are silent clients? Silent clients are clients that can only receive um information from the validators, but they cannot themselves send information. And what I mean by send information in particular, yeah,

it's sort of a a one-way street, right? the clients uh for example they they get presented with sort of evidence based on which they should confirm a certain transaction but they don't have the ability to say okay I'm going to broadcast that information and I'm going to sort of relay it to everybody else to make sure that everybody else who might who may at the same time be asked to confirm something also sees this bit of information that is different in communicating clients right where the assumption is that a client whenever they see a message uh they can sort of relay it and shortly thereafter after pretty much all other clients that are online right now um or that are awake right now uh can also see that information.

>> So does communicating sort of imply a PKI for the clients or >> um good question. Um no. So the idea here is not that we have a PKI on the client. The idea is whether or not clients can forward messages basically. >> I see. >> Okay. So >> I see. So if I if I get a message from a client, I'm basically not I'm going to ignore it except in as much as validators have signed that message. >> Exactly. Yeah. You're not going to be able to say, "Oh, I got this message from this client over there." But the mechanism is basically the clients have are part of the gossip network and if you present confir like evidence to a client prompting them to confirm something then they can sort of relay it and if the network happens to be synchronous then all other clients will

soon also see that information and then maybe they can they know that you know there there exists some evidence to confirm something and maybe that stops them from confirming something else. We'll we'll see that mechanism in one of the protocols. Okay. Now once we basically go to that uh you know to to to this level right and we say okay let's model the clients right along these two uh dimensions right the sleepiness and the communication capabilities of the clients right it's natural to ask okay clearly this setting is um a harder setting than this setting right um now it's natural to ask wait what about the sort of intermediary client models right what happens when we

have always on but silent clients what happens if we have sleepy but communicating clients. And so the sort of first non-trivial result we we get from this paper is that indeed um if you have always on and silent clients um or sleepy and communicating clients uh you can't improve over this 49% uh resilience in terms of total resilience. Now we want to sort of dig a little bit deeper still. So I need to introduce one more kind of um detail of the model. Right? So let's remind ourselves what are the um consensus properties um the security properties that we want from these ordering protocols right from these consensus protocols um consensus security are these two properties right

um safety which is that all clients confirm transactions in the same order think of it as bad things don't happen where bad things are inconsistency um and livveness which is that for every sort of input transaction eventually uh the clients confirm that transaction And think of that as good things should happen in your protocol. And then we talked earlier about this this question of the resilience of a protocol, right? The resilience resilience of the protocol is the maximum fraction t of adversary validators such that these two properties um are guaranteed by the protocol.

Okay. Now we can split sort of uh the the resilience up. Right. So far we have one parameter. So, we're going to separate this in a safety resilience and aliveness resilience. And we're going to change this up here, right? We're going to say, okay, safety should hold whenever the adversary Oh, there is a typo there. Whenever the adversary is less than the safety resilience and livveness should hold whenever the adversary is less than the livveness resilience. Okay, now we get a sort of a 2D um kind of region and we can ask okay what pairs of safety and livveness resiliences are achievable in each of these client models. And now if we go back to this uh to this characterization of the of the

resiliences we see that actually once we do this decomposition something interesting happens right previously we were looking sort of at the sort of maximum value maximum achievable point on this diagonal right and that's 45 45 sorry that's uh 49 49 and 49 and 99 here right but once we do this uh this decoupling and safety and livveness resilience We see that actually the region for sleepy and communicating clients uh is bigger than for sleepy and silent clients.

>> Okay, >> sorry question. Um this is like corruptions of the validator set. What do you assume about corruptions of the clients? >> Uh the clients there's no assumption there. The client there can be arbitrary corruption on the clients. >> Um the properties hold for honest clients. >> Got it. Okay. >> So, uh, sorry, what? Yeah. Uh, because they're in a gossip network, you assume that if at least one honest client broadcasts anything that all honest clients will receive it. >> Um, yes. If one honest client uh rebroadcasts something, for example, in the communicating clients model, then it means that under the assumption we also have synchrony, shortly thereafter, all the honest clients will have received

that information. >> Do you also need all the validators to receive what the client sent? um not in the protocol that the protocols that I have here. Um the the assumption in general is that they're sort of on a joint kind of gossip network where uh the property is if any one honest party sends something then shortly thereafter all honest parties get that information. >> So your bounds took that into account. >> Yes. Um yes. Yeah. Okay. Good. So right this is the operating point that we've seen earlier right of the Nakamoto protocols and the synchronous uh BFT protocols and this is

the 99% that we've seen uh for dollar strong earlier. Now there's something interesting right which is that in the setting of sleepy and communicating clients for example and we're going to zoom into that um in a bit um we have a new protocol um which allows us to get consensus where we're always safe right up to 99% up to 100% advers well up to 99% uh validators were safe right um and we're live if the if if a majority of validators is honest and another protocol where we can achieve that we're always live and we're safe If the majority of validators is honest and then in uh the always on uh silent setting, we get the same uh behavior uh as for sleepy uh silent clients.

Because of this implication, it's kind of clear that whatever we can achieve here, right, we can run the same protocol in a sort of a a better um a better model, an easier model, right? then we would we would still be able to achieve the same uh the the same uh sort of blue region. This blue region is a subset of this blue region. Okay, good. So I want to zoom now into these two protocols here. Okay, because the these these are as far as we know these are new. So we want to talk about an always safe protocol for sleepy and communicating clients under synchrony.

Um how do we get that? So our goal is to build a protocol. Remember a protocol is this kind of ordering box, right? There's transactions coming in. There is logs coming out, right? And we want this protocol to be safe uh up to 99 like up to 99% adversary. Um and we want it to be live up to 49% adversary. Here's how we're going to do it. We start from any certifiable SMR protocol. Say say think hot stuff. Any certifiable SMR protocol that works in this 49 49% setting. Okay. We're going to give the protocol a shot at ordering transactions and we're going to output um the the confirmed logs together with these certificates of

confirmation. Uh we're going to put them we're going to gossip them. Then we're going to wait some time, right? The time that it takes for messages here to propagate. And then if we haven't heard any conflicting confirmations from that first protocol in the meantime, then we're going to assume that it's now safe to go forward and and output uh the log that we just got from this protocol. the mechanism clear, right? So, we're going to run a 40 49% 49% protocol. It's going to give us output logs together with a bunch of signatures from the validator saying, "Look, this is what you should confirm. We're going to relay. We're going to broadcast that.

We're going to gossip that to everybody uh to yeah, the clients. Yes. This is in some sense, this is what happens on the client side." Yeah. Okay. then you're going to gossip that and then whenever you get something you're going to gossip it and then you're going to say okay I'm going to hold on and basically see if the network um you know has seen anything conflicting okay I'm going to give the network some time to see if if there was anything conflicting if I don't hear anything conflicting within delta time and the assumption is that within delta time messages propagate between honest nodes then I'm going to output that lock that I just got right so why is Is that live? Well, okay. We make the assumption that the

adversary is uh uh 49%. Right? Then this protocol is live. We're going to gossip whatever comes out of it. Fine. We're going to wait a little bit. That's also fine. Now, the only thing that could stop us from outputting this and jeopardize our livveness. If there is if there is some conflicting confirmation uh that we receive, right? But we can't have a conflicting confirmation because under the assumption uh that the adversary is 49% this protocol is also safe. So there cannot be conflicting outputs. So eventually we're going to output this and everything's fine. What about the safety side? Suppose there is a client an honest client that outputs a log. Then that client has gossip that log at least delta time before. So by this point in time, right? Then that log

together with that certification has now been received by all other honest clients, right? When could another honest client possibly output anything conflicting, right? If well, if it if it outputs something before our client outputs, right? Then it would have gossiped it even before here. So our client would have received it and would not output anything conflicting. And another client can also not output after this, right? For basically the symmetric argument, right? our client has uh gossiped the um the certification of that log uh a while ago and that would have propagated to any other client any other honest client and would have stopped it from outputting anything conflicting.

>> If there is indeed a conflict um what do I do? >> You stop >> stop forever. >> If there is a conflicting output from here, right, it means that the adversary must be greater than 50%. So you don't have to provide livveness anymore. So you just stop outputting. Yeah. So that's the safety proof, right? Um and interestingly, um uh there seems to be some a somewhat similar mechanism uh going on in Cosmos. So, Sriatan and and David and Dion has talked a bunch to uh Cosmos people and asked them, hey, what happens in your protocol if there is a majority dishonest or you know more than 33% dishonest and they say no there can never be uh inconsistent confirmations

sort of on on one client uh because our software basically says whenever you see something conflicting you just stop outputting entirely basically. And so every one client is sort of consistent and they they do this kind of rebroadcasting trick. The only thing they don't do is is waiting here. >> Um but it's kind of interesting. >> So Cosmos clients by default are communicating. >> Say again. >> Uh Cosmos clients by default are >> that's my understanding. Yeah. Everybody is on the same uh gossip network and they just uh clients get the same messages as validators >> but they are assuming partial synchrony right.

>> That's right. Yes. So this mechanism correct this mechanism doesn't work in in partial synchrony. >> Can you clarify the sleepy model here that if I go to sleep and wake up I immediately receive all the messages I missed during my sleep? >> Yes. Yeah. So um the the sleepy model here is so this is sleepy clients not sleepy validators at the moment. And the idea is um if you're a sleepy client and you wake up then you receive sort of all the messages that you missed in the past. Correct. Again the that this assumption comes sort of from from the gossip network where uh you know everybody keeps sort of relaying stuff and you connect to other people and they will tell you sort of what you missed in the meantime.

>> Is that crucial for safety to receive all messages from the past because it seems quite of an overhead in terms of >> bandwidth if you keep rebroadcasting all the messages from Genesis to present. that is that is uh crucial here for the safety, right? Because it could be that somebody sort of in the past confirmed something here. Um and the only thing you know is that they gossiped it, right? And if you you know one year later sort of wake up for the first time, uh somebody could present like a dis dishonest majority could present you with a conflicting log, right? And the only thing that would stop you from outputting that log is that you know that somebody else had a conflicting lock in the past. So let's

talk about the always live protocol. Right? So we want to build this protocol that now has a livveness resilience of 100% and a safety resilience of 49%. Here's how we're going to do it. Uh we take transactions and the first thing is we we gossip them. We just broadcast them to everybody. We gossip them to everybody. Um, and then we're going to run an off-the-shelf SMR protocol for 40 49% 49% say synchronous hot stuff. We're also going to maintain a queue of all the transactions we've ever seen. Okay. And we're going to we're going to have a queue where we basically cue these transactions for delta plus the confirmation time uh of this uh of this protocol.

Okay. And sometimes we're keeping track of like transactions that that have already been in the system for a long time, right? And then we're going to we're going to look at the transactions that are still unconfirmed that are still pending after you know delta plus the confirmation time of that protocol. Okay, these are the transactions that come out of here are transactions that are you know that have entered the system long time ago and still for some reason haven't been confirmed. Right? And since we always want to be live, we need to do something with these transactions, right? But what does it happen? So then what do we do? Well, we're just going to put these transactions somewhere in our output log. Okay, maybe at the end of the output lock. And here's the argument why that's fine. That's fine because uh suppose the adversary is less than 49%.

Okay, so we're going to going to do a livveness proof first. Okay, let me let me give you the livveness argument. Okay, so suppose a transaction enters here, right? The transaction will be gossiped. Okay, good. It'll be added to that que after some time it'll come out of that queue. Either by that time the transaction has been confirmed. If yes, fine. It'll be output. If no, we're just going to put it into the output log somewhere. Okay. Uh that's fine. So livveness is clear. How about safety? Suppose the safety we only have to provide if the adversary is less than 49%. So suppose the adversary is less than 49%. Then that protocol is safe and live, right? So every transaction that we cue

for delta plus the confirmation time of that protocol will have been included in that output log because that protocol is now live under an adversary like this. Right? And so there will not be ever overdue and pending transactions. Right? There will never be transactions that uh that have entered the system long time ago and still have not been uh ordered by this protocol. And so this prefixing or this injection operation basically does nothing, right? It never adds any any new transactions. And so that's why the output is is safe. The output log here is basically the output log there.

>> Could you see a little bit about transaction dissemination? Like as a user, do I send it to a validator or do I send it to a client? The clients echo transactions they hear about back to validators. >> Yeah. The the assumption here is that everybody just uh gossips every transaction that they hear. You you are here you're relying on the fact that the assumption that the livveness of that inner consensus box is not just eventual correct right that it's uh by some deadline. >> Yep. There is a worst case uh confirmation latency. Yeah, that's right.

>> We talked about this throughput congestion, right? If there way too many transactions, your inner consensus protocol won't be able to process them fast enough. Yeah, >> that will affect this >> that will affect this. Yeah, that's right. Yeah. So here the assumption is that um exactly this, right? So the assumption is there is a worst case confirmation uh latency on this protocol, right? And the assumption is when you drop a transaction into that protocol since we're in a synchronous setting, um there is some upper bound on how long it takes for that to be to be ordered, right? and and Ling is pointing out okay that's usually derived sort of under assumptions of like okay the block size sort of here is infinite right um and so as soon as there is an honest block that gets confirmed eventually

that would sort of bring in all the pending transactions right and so I think it's an interesting question uh what you know what happens uh you know as long as you have that worst case confirmation you're fine right but what that actually looks like for protocols uh in in practice uh I'm not aware instead if I define livveness of that inner box to just be eventual. >> Yeah. Then this doesn't work. >> And then it's not clear where the upper bound, lower bound, right? Where where to worry. >> If you if you if all you know is that that protocol eventually uh confirm stuff, um then this construction will not work, right? Then you don't know how long you have to wait.

>> How about the lower bound? The lower bound certainly holds, right? Because it's now just a harder problem. Um yeah, >> but it's possible that you can prove even stronger lower, >> right? Yeah. Yeah. >> Well, I mean, intuitively, you don't even know if you've ever had a livveness violation then, right? >> Say again. >> You don't even know if you've had a livveness violation, right? If you don't have a if if you're using a sub routine that's just like eventually live, right? Yeah.

Exactly. Like you don't even know at any given time you may not have seen something because of the network or you may not have seen something because of a 51% adversary and you don't know which right. >> Yep. >> Somewhat related question. Should I think of like pi int as being run for some fixed duration or should I think of this as running forever and you're doing this periodically? >> I think of it as yeah it's running forever. I think of this uh of this diagram as basically like a um you know one of these uh block diagrams that we have in electrical engineering right there's like an in there's like a all of this is streaming basically yeah okay good so this sort of you know gives you sort of a an overview of of what happens at these two points that

we've discussed uh before um so far we've been looking at the synchronous setting right with always awake take um validators and what we do in the paper is uh we do two more dimensions uh kind of of the models that we're considering right one is we go we also include partially synchronous uh setting where the network between both clients and validators could have periods of asynchrony where you don't have a delay bound uh capital delta and the other one is we also consider uh validator sleepiness so so far we've assumed that validators are always on from the start of the protocol. Um and we uh we also consider the setting where uh validators

can can sort of temporarily crash. Okay. And again um you know this is this setting is harder than this setting and this setting is harder than that setting. And so overall you know we get this uh 16 different models um and we characterize the achievable region uh for all of them. Okay. So so far what we've discussed is uh this row here right so we've talked about synchronous and always on validator synchronous network and always on validators and we've seen the sleepy silent setting is this uh nice diagonal uh we've seen the always on and communicating setting which like covers everything and then we've seen these two uh intermediary um

regimes. So, could you say a sentence about the second row, third column? >> Uh, sorry, say again. >> Second row, third column. >> Second row, third column. Yes, I'm going to get there. Exactly. So, something interesting is happening here, right? Which is that if we have sleepy validators and a synchronous setting, um, then somehow this always safe protocol goes away. The always live protocol still works, but the always safe protocol no longer works. Why? Sorry. I'm also confused about the fourth column in the second row >> because that's usually achieved by dolift strong right and how do you run dolift strong in sleepy >> well you can just treat the sleepy nodes as crashed right

>> as the like the sleep the crashed nodes as uh within the budget right because the Byzantine budget is so large you can just lump them into there. >> Uh so why is what what goes wrong here with the always safe protocol? Um the critical thing is this verifi uh the certifiability here right so what we don't have in the sleepy setting is the fact that when you get an output lock from this protocol you also get a certificate that would prompt every other client to confirm uh that output and so that doesn't exist in in in the sleepy validator setting um and it turns out that the protocol then the the problem then becomes impossible now let's see yeah we have enough time to

talk >> if you try to run that without the certificates. >> Yeah. So then I guess some Byzantine person gossips you something. >> Exactly. And you don't know what it whether they're actually got that log from this protocol or whether they just made this log up and are trying to stop you from confirming things. Right. Yeah. Exactly. Um so there is a there is an impossibility for that, right? So we can sort of argue uh the impossibility of this upper triangle and um you know primarily for sort of educational purposes since many of you may not never have seen a proof of this kind I'm going to step uh through the details of that.

So this is one slide should take some 3 minutes or so. Um and then um you know hopefully what you will take away is maybe not so important sort of how exactly that happens in in this one result but uh sort of you will see um how these kind of arguments work. Okay. So we're going to assume for contradiction we had a protocol, right, that could do something here in this red region, right? Something that's like maybe just on the on the boundary here or just just past the boundary, right? Some protocol pi with a safety violation in a beta that is somewhere between half and one, right? And a livveness violation that sort of corresponds to that uh sort of on that diagonal, right? And then we're going to look at

like four different executions, right? And we're going to see sort of under the assumption that that protocol here has this livveness resilience and the safety resilience sort of how does the protocol kind of have to behave and that then that's going to lead us to a contradiction, right? Specifically in the first execution, we're going to consider the validators partitioned into two sets, right? One are beta and the other ones are all the other ones, one minus beta, right? We're going to put the validators in Q to sleep because we're in the sleepy setting and we're going to input a transaction into the set P. Okay. Then our honest client eventually because the protocol is assumed to be live um in this setting,

right? The protocol is is assumed to be live if one minus beta um validators are corrupt. But here actually there's nobody corrupt, right? So um definitely our client has to output that transaction TX right execution two is basically the same thing but mirrored right there's going to be another client now the nodes in P are uh asleep the nodes in Q are awake um the nodes in in Q get transaction two um and then our client for the same argument uh has to output transaction two and then in transa in execution three uh there there's going to be three clients now the guy in the middle uh is asleep for a while. Okay, in the beginning of the protocol doesn't

follow the protocol yet. The client sort of on the right here, right? And the nodes in the validators in Q are going to follow the same strategy that honest parties are following in execution two. A transaction one is entered into the nodes in P. Right now, this client has to output that transaction uh one eventually. >> So, the players in Q don't talk at all to the player players in P. Correct. Yeah. They just pretend like, you know, they're in this setting, right? They treat everybody else as asleep.

Um, and then execution four, again, we're going to mirror the situation, right? We're going to again have this guy in the middle asleep. The guys in P and and this client are going to mimic the behavior of the honest nodes over there. Transaction 2 enters into Q. Then this client has to eventually output transaction 2. And then after sort of these confirmations TX1 and TX2 have sort of happened right the adversary nodes here right now start doing sort of what happened over there okay and vice versa right and then the question is okay what should this client now be outputting right because if this client outputs transaction one first then you get a safety violation here if this client

outputs transaction two first you get a safety violation there, but it has to output something. >> Yeah. And like you say, the point is that neither of those are certifiable, right? Yeah. >> So, what can we do in the setting? Um, right. If you want to sort of get the other the other bound, right, the sort of the achievability side of this one way to do that, for example, is uh with this gold goldfish protocol with a modification of the goldfish protocol. We haven't checked whe there's probably other protocols that can do the same. >> Okay.

>> Sorry. connect the dots there for a second like why why does that solve that problem? um >> like what is it you need and that that has that? >> So good. Yeah. So um you know why this protocol and not for example Nakamoto, right? The the most kind of canonical sleepy protocol would be Nakamoto. And the reason we we can't do Nakamoto is because I need to somehow tune some sort of a quorum, right? And so that that's why sort of Nakamoto allows me to operate here at this half and half point. But it's unclear how you would get higher safety and lower aliveness in a protocol like Nakamoto >> and like a synchronous hot stuff type thing.

>> Uh that doesn't work for sleepy validators, >> right? So we need some sort of a sleepy protocol that allows us to tune the quorum. >> You want a quorum based style protocol that works in the sleepy model. >> Exactly. >> Goldfish as an example. >> And goldfish happens to be the one that I'm most familiar with. Yeah. Um and so there it happens to work. Yeah. Okay. Um yeah and back to sort of uh the the the uh you know this big matrix there is one more remark I want to make which is if we look at the bottom two rows of this right okay one thing you know we knew this already ahead of time is that under partial synchrony with sleepy validators there's nothing you

can do right and under partial synchrony with always on validators interestingly what you can do uh does not depend on your client model right so the safety and leness resilience pairs achievable are robust uh to the choice of client model under partial synchrony and perhaps that gives some you know some plausible story for why partial synchrony is such a an attractive protocol such an attractive model to to work with. Awesome. Yeah, if you guys want to know more check out the paper um for all the details and happy to chat.

>> One question I so you use the word client. I almost feel like what I really want to think about are like full nodes that are just like passively tracking like updates to blockchain state or something. How but how what do you think of like when you say clients what do you have in mind? When I say client uh I mean any party that is not themselves staked or does not have hash power and or yeah is not part of sort of the you know what we whatever it whatever resource it is that we use for the threshold assumption in uh like among the validators whether it's clients as in like light clients or whether it's full nodes um I think it holds for all of those

>> I I think in this case um so for light clients would be actually very expensive in terms of bandwidth to be um communicating. >> Yeah. >> So I didn't have light clients in mind when you were talking about clients because otherwise if they follow the entire gossiping network that's quite of an overhead. >> Yes. Yeah. Um um correct. Yeah. >> Maybe we can consider a mixed clients model. Some clients are communicating others are not. Full nodes and light clients are both clients in that sense.

that that would be interesting. Yeah, we we haven't we haven't looked at that. Yeah, we have only looked at homogeneous client populations. Yeah. Um I think in general I mean you know my personal take is in terms of these models I think being in the sleepy and silent setting is is sort of appealing um just because it's so simple. uh but uh you know given that there's something to be gained from going to the sleepy and communicating setting I think that is uh quite a plausible setting uh to be in um most of the systems we have today I think at least the public chains uh basically give us this property anyway because they're are public chains so the network needs to be kind of accessible

to everybody um I would not want to go to a client model that doesn't work with sleepy client like I think the assumption on uh clients always being on is a is is kind of a more restrictive and and and less easy to justify assumption um than the communicatingness. I think communicating but only when you happen to be uh awake I think is a fine model. >> Awesome. Let's thank you again. >> Thank you.