Impossibility within Dynamically Available Protocols

Thank you. Okay, so hello everyone. I really appreciate all of you coming here today to listen to this talk. And in this talk, basically I want to talk about the state of dynamic availability. The state of basically what has been going on in the industry and what I have been working on for the past few months on this.

So basically, I started the fellowship by basically understanding consensus algorithms and looking into single slot finality, but as the time went on, I basically focused more on dynamic availability in particular. So for starters, definitely the question is what is dynamic availability? So it is basically any protocol that is live under what is called dynamic participation, which means that basically nodes can come and go into the protocol and, you know, it still works. It's not like a static validator set where, you know, the protocol is already aware of what nodes there are. So, like, this dynamic participation.

A few examples is definitely the Nakamoto consensus, like Bitcoin, LMD Ghost that is used in Ethereum currently, and a few other protocols, you know, that I will be talking about today, like Goldfish and our LMD Ghost. So, a little bit primer about LMD Ghost, if anyone is unaware. It is the folk choice rule that is used in Ethereum. It basically uses the weights of votes to decide the tip of the blockchain. So like if there is a block proposal and it wants to propose a block on top of previous block, it calculates all the votes that basically any particular tree has.

And as you can see in this diagram, perhaps that the block F has 20, E has 25. So when you are at A, you're going to take a step at C because it seems to be the heavier subtree. And then you can take a step at E, and that way you can decide which block to choose as a tip. Now, currently, LMD Ghost as it exists has some problems. It has problems with dynamic availability in particular and it has a problem with reorgs.

So, a particular attack vector that I want to talk about is an X-hand attack. So, how to execute it? So let's say you have a block at slot N, and then it's time for slot N plus 1. Now the validator here is malicious, and it proposes the block, but it does not release it into the network. And it has control over a set of malicious attesters that attest to the block privately.

So for the majority of the network, they think that the slot is empty. So in the next slot, when a new block is proposed, they tend to vote to that slot. But as you can see that in the next slot, the malicious proposer then releases it to some of the network. And then some of the attesters might see block n plus 1 before the block n plus 2 and then attest to that. And then this cycle can continue for as many slots as the malicious proposer wants, if it has some sort of control over the network delay.

And then it can release the entire thing to the network. And as more and more slots, as more and more slots, like a part of those slots attest to this malicious block, it gets more and more weight. So if it then releases a new block that is tied directly on it, you can see that the weight of the n plus one block would then be more than the other blocks. So the chain will then reorg. And that's how basically honest proposers blocks will not be included in the canonical chain because the chain has reorg.

And that is obviously an undesirable property. So how do you solve this? Well, there is one approach, and that approach is basically Goldfish. So Goldfish is a protocol which, as you can see, like whenever a slot is, someone proposes a block, they vote, the attesters basically vote for that block, and all those votes are then aggregated, and that's what the tip is. What Goldfish basically does different from LMD Ghost is what's called vote expiry and vote buffering.

Vote buffering is basically whenever you see a blog, whenever you send a message into the network, that, you know, network messages are called like vote buffering. And it's also called view merge. So like by view, you mean like you view, you view something in your local view, and by merge, you mean that, you know, you merge what you see into what you think is the current state of the network. Because you as an individual validator cannot know the state of the entire network. You only know what your local view is by the nodes that you're connected to.

The thing that it introduces, it's vote expiry. And that basically means that it does not use the votes from the previous slot. So it only uses the votes that are casted in this particular slot. So previous validators basically if they vote on something, if know, if there is some sort of, if they're trying to withhold votes and they publish it later, then it will not be, you know, counted. So that way, you know, nobody can withhold votes and they will not be counted, they will be discarded, so you don't have attacks anymore.

But it does raise another problem, and that's the problem of asynchrony. So what if there is a network delay? Because if a validator basically votes for a block, and the vote does not reach in time in the particular slot duration, then that attestor's votes will not be counted, and that is not the fault of the attest. So it's just some network delay, it's just a period of asynchrony, right? And the goldfish protocol would just not work in asynchrony.

So that's a particular problem that it faces. Another way to think about the reorg attacks is to think about subcommittees. So subsampling or subcommittees is basically crucial in the success of these reorg attacks. And because, you know, it is easier to, like, have a control of, you know, a small set of validators and easier to have, like, control over the network delay. You know, if there is, like, a committee, a committee has, like, 30,000 validators, but, like, the entire set of Ethereum has like a million.

So like, you know, you cannot have control over the entire network. But, you know, it's practically like somewhat possible to have, what about, let's say, 30,000 nodes. So like if you just remove subsampling completely and, you know, you just have like the entire million validator set, you know, a test in every slot, then the problem of reorg attacks will be solved. But obviously that's not practically possible in 12 or 13 or so seconds. It's going to take a long time to get all those votes, aggregate the signatures and stuff like that.

So RLMD Ghost, which is a version of this protocol that I'm describing, introduces a concept of relaxed vote expiry. And that is basically what I mean by relaxed vote expiry is that in Goldfish, you remember, the votes expire after just one single slot. But in this, you can basically balance between asynchronous resilience and dynamic availability. What that means is that you can basically to the votes from the most recent n slots can be considered. And the reason I say that it's balanced is because dynamic availability basically means dynamic participation.

Like validators can go in and go out. And if a validator is part of the network, votes, and its votes are either withheld or through network delay, it's stuck. And then the validators go offline. The vote can still affect the protocol, which is not a property of dynamic availability. So like Goldfish is a perfectly dynamically available protocol, but through RLMD by choosing this parameter, you can balance between both these factors.

But as you see that it also has a problem of not having subsampling. So is there like an impossibility between these three properties? Reorg resilience, sub-sampling, and asynchronous resilience. And the answer seems to be yes. Like, I didn't get a chance to work particularly on a formal proof of this relation.

But based on what I have studied and researched so far it seems to be the case because if you think about it from a view of a validator if you do not receive an attestation from another validator there could be two reasons for that either that validator is malicious or adversary and it's withhelding the vote or there is just a network delay. And you as a validator cannot differentiate between the two. So is there a way to basically combine all these properties together in a fashion that can be useful for the protocol? And a disclaimer, this particular slide needs a lot of academic review and a lot of validation from people much smarter than me. So just take it with a pinch of salt.

But a possible solution could be that we can use Goldfish as our fork choice algorithm and we can try to figure out a way to deterministically identify a period of asynchrony. So let's say that a committee has 30,000 votes, everyone votes for a particular block, so there are around 30,000 votes per slot and if let's say the number of votes drops suddenly that could be a condition of async need. When the protocol will dissolve the committees and shift to an RLMD model where the vote expiry period get relaxed, it will expand and the votes from previous networks will then be allowed to be considered into the folk choice rule. Then, based on how quickly the votes are coming in, we can determine if synchrony has been achieved again. And then we can reestablish committees and the protocol will be back to normal.

So that is roughly it about the talk. I want to thank the Ethereum Foundation and Mario and Josh for giving me the opportunity to study about this. And I also want to thank my mentor Francesco who's doing consensus research at Ethereum and also Lincoln who was the Ethereum fellow in the last cohort. He also worked on single slot finalities. So yeah, that's it about my talk.

Thank you. All right, thank you, Yash. Any questions for Yash? So I'll raise one. It's just, if you're swapping between modes, do you think that that increases the complexity of your vulnerability and attack surface analysis?

so you switch from one mode to the other, etc., so that they can take advantage of that situation, etc. And amongst other things, that just makes it much harder to reason about it and people forget, you know, can forget that actually the network's not always operating in this mode. They need to consider that it changes. Yeah of course.

So like the basically the model that I talked about is obviously like if you know we do more research on it it's going to be incredibly complicated and switching between like basically consensus protocols on the fly is going to be very difficult. The reason for my research is just exploring what are all the possible designs that can be implemented into the consensus. And of course, Ethereum itself is moving more towards the single-slot finality model. So it would be interesting to just see what are the properties of dynamic availability and how it could be. Obviously, this is not something that I would propose to actually put into Ethereum, but it's still interesting to research about it.

All right. Thanks, Yash. Thank you, guys. No more.