A Survey of Proof-of-Stake (PoS) Blockchain Designs with Valeria Nikolaenko | a16z crypto research

Transcript

All right, everyone. Welcome to today's research seminar here at A16Z crypto research. We're excited for today's talk. It's by our very own Lera Nikolenko. She's going to give a two-part survey about proof of stake blockchains. So, the first one is now, and the other one will be Thursday at the same time, so at 11:00 a.m. Eastern. So, definitely check that out as well. We're excited to We're excited to hear about this on the one hand, very central topic in Web3. On the other hand, I think still fairly poorly understood. So, Fantastic. Thank you for this introduction. Uh so, this talk here will be a survey of proof of stake blockchains. So, the main purpose of this talk will be to map the landscape, to kind of get a view of the land so

that you know how it all looks like, and we'll be able to map new consensus protocols into this landscape. Um this is a very vast topic, and can easily substitute a semester course. So, I will be touching the tips here. Um but hopefully, you'll get a a general sense. So, I was trying to balance the talk between academic papers, white papers, talks, blog posts to make it a little bit more lively and interesting and less academic. Uh but of course, if you're interested in specifics of any protocols that I'm going to describe, please look at the papers for more like rigorous analysis of why this works.

Uh so, this tutorial will also help understand somewhat a little bit a deep dive that I will give on Thursday about mitigating the long-range attacks for proof of stake blockchains. So, this is the outline. The talk will be subdivided into a few topics that are somewhat independent. So, if you lose me on one, you can always catch up on the other. Uh roughly, I'll start with some pathway into the proof of stake by comparing it to proof of work and sort of motivating why we want to move to proof of stake and what are the new properties that these blockchain systems uh give us.

Then I'm going to describe two most popular approaches to designing proof of stake blockchains, which is Nakamoto protocols, very similar to proof of work. They are sometimes called longest chain consensus protocols or fork choice rule consensus. And also BFT protocol is another popular approach. Um I'll then focus um on leader election strategies or committee election strategies and blockchain randomness. This will be somewhat a little bit more technical. Um and then uh finally I will overlook at different possible attacks that the proof of stake design enables that were not possible with proof of work blockchains. Okay, so let's start with proof of work versus proof of stake. Hopefully this will be easy.

Proof of work blockchain you'll probably know. It starts with the genesis block and the blocks are built on top of uh other blocks forming a tree. And so each miner it needs to pick one uh path through this tree um to extend uh this path with another block. So it exercises a fork choice rule to select a path in the tree. And to extend to get the right to extend uh the chain with a new block it needs to solve a computational puzzle that's hard to solve but easy to verify. And solving the puzzle what allows them to extend uh the chain by one more block.

So you notice in this consensus we get total ordering of all of the transactions. So transactions are ordered within a block and then the blocks are ordered. So everything is uh has total order at the end. It doesn't have to be this way. Some transactions actually independent so potentially can be run in parallel and we'll see some consensus some modern consensus protocols are trying to do partial ordering but not total ordering. But proof work is doing total ordering. Um and another interesting thing to note about the proof of work system is that the miner who joins um it needs to figure out what's the longest chain. It needs to verify all the cryptographic puzzles along the along the way to to figure what's the latest uh block to build on top of unless it's willing to trust a

centralized checkpoint. So, with proof of work, minor uh spends a lot of money on the infrastructure, paying electricity bills, and also buying special mining hardware. So, you can envision as if the money are kind of leaving the protocol into the physical world. Uh and this infrastructure allows the minor to participate in in um building the blockchain. And the reward that the minor gets is proportional to its computational power. So, if it doubles on its infrastructure, then um his reward will double.

So, the more money he spends on the infrastructure, the larger is his reward. And the whole idea of the proof-of-stake blockchain is why don't we eliminate this physical component altogether and can circle this money just directly back into the protocol uh by just locking the same amount of money as stake. Uh and then the reward that we give to good miners that honestly participate will be proportional to the stake that they uh has locked to participate. Okay, so that's a high-level idea.

Um So, to compare proof of work to proof-of-stake roughly, so a bit of terminology, we call miners in proof-of-work the nodes who help build the blockchain and validators in proof-of-stake. The reward is proportional to computational power in proof-of-work, but proportional to stake in proof-of-stake. And then what the miners are doing um in proof-of-stake is they're validating and executing transactions same as in proof-of-work, except they're not solving these expensive uh computational puzzles. So, that's why proof-of-stake blockchains are very energy efficient.

um, Byzantine threshold that the blockchains can handle is roughly the same. So, to attack the proof of work, you need to compromise some significant portion of computational power, and for proof of stake, you need to compromise some significant portion of stake. But, uh, the world is still, uh, despite all the benefits of proof of stake, is still mostly proof of work. So, if you look at the cryptocurrencies by market cap, about 57% of them are still doing proof of work. So, Bitcoin is the largest, and Ethereum is the second largest. But, Ethereum plans to move to proof of stake somewhere this year, hopefully. So, this will be the largest proof of stake cryptocurrency after they make the merge. Um, and we'll be focusing on this right

rectangle of protocols, including the, uh, Ethereum consensus layer. Um, so, just a little bit more about, uh, electricity consumption and how bad it is. So, some of the latest numbers, that Bitcoin is consuming at 5 terawatts an hour, and Ethereum 112. That's comparable to the size of the Argentina, which consumes 130. But, uh, to be fair, it's still less combined than mining gold, uh, which is 240 terawatts an hour. And also, if you look at how the hash rate climbs up of the Bitcoin network, and hash rate is directly proportional to electricity consumption, is it climbs up very, very rapidly, especially in the last couple years. So, if it continues climbing up this way,

uh, you can start to worry about sustainability of this whole blockchain. If it doesn't worry you now, maybe it will start to worry you uh, sometime soon. Less electricity loss with, uh, proof of stake is, I guess, the major selling point, but not the only one. Also, mining becomes cheaper. So, if you look at the numbers, currently, Ethereum is paying 2% of the total supply of coins to its miners annually, and Bitcoin is paying 105, oh, sorry, 1.5%. So, that's a lot of, uh, a lot of stake and a lot of rewards going to miners.

With mining becoming cheaper, this rewards can probably be made lower. Um another good thing about proof-of-stake blockchains, some proper some protocols have much faster finality and larger throughput. So as you all know, Bitcoin and Ethereum are not so good in terms of finality and throughput. You need to wait like for example, this is a coin-based number so you need to wait three blocks on top of your transaction in Bitcoin and 35 blocks in Ethereum. So that makes the finality times about 30 minutes for Ethereum or so 30 minutes for Bitcoin and 9 minutes for Ethereum. And then the transaction throughput is also really low. With proof-of-stake potentially, you can have finality in seconds and be able to do thousands of transactions a second.

Um then we'll look what which protocols are achieving that uh performance. It's also arguably easier to launch new projects with proof-of-stake consensus because you don't need to acquire a lot of miners um to support your chain. So it's still challenging but it's somewhat easier than proof-of-work. Yes. I guess uh one could just increase the block size of the proof-of-work chain. Yeah. Absolutely. I had a slide on that but I removed it for the sake of time but you're right. There are um research directions that are trying to improve the proof-of-work blockchain by increasing the block size or decreasing the frequency at which the blocks are allowed to be produced like decreasing the difficulty puzzles.

Uh the problem with that is that when you start growing your block size, it takes longer to propagate through the network and so it's more likely that other miners will find blocks at the same height and the fork will chain will fork the chain will fork more as a result. So the worry I guess the main worry of the people who are at who are opposing increasing the block size is the fact that the chain will be less reliable. Um but also there are other research directions trying to improve the proof-of-work. For example, instead of solving this useless computational puzzle of finding preimages of the hash function, you can do maybe something useful. And there are some ideas around help fold proteins or help figure out transportation and such. So,

as an interesting research direction, like substituting the puzzle for something useful. Because if you think about it, the infrastructure is already built and we have all this kind of hardware, people figured out the logistics with electricity. It's kind of a waste that they're having all that there, kind of wasted in solving stupid kind of hash puzzles. Instead, why don't we maybe re-purpose them to solving something useful? It would be kind of nice. So, that's another approach of maybe improving the proof of work. On the on the topic of block size, that Justin mentioned, I feel like it's almost like an orthogonal dimension compared to like proof of purpose, proof of stake, I feel like.

Because proof of stake blockchains, you also have to worry about is the block rate is the block size bigger or smaller, how do you feel about propagation delay? And so, I guess but so, a different thing is just kind of like what is the minimal uh computational requirements just to like validate the chain, right? Yeah. So, that's something that comes up, I guess. So, like I I one thing that's maybe to Bitcoin and Ethereum, I feel like both of them want to make sure that it's very easy to be to be able to just sort of follow along, so that you don't need like a crazy super computer. And I I feel like that's a completely orthogonal design dimension to like the choice of proof of work.

Mhm. Is there any connection between these two or does that seem Yeah, especially those proof of stake protocols that mimic proof of work, they will have the same problem. Yeah. Yeah, good point. Think so. Um So, let me mention the desired consensus properties of blockchain properties that we want before we kind of see the designs of these blockchains. So, of course, you want safety, so miners need to agree on history, on some common prefix of the chain. You want to have liveness, so every valid transaction should eventually get added to the chain and you should have no censorship ideally.

Um you should be able to tolerate some percentage of Byzantine miners, adversarial miners who are trying to disrupt the protocol. And finally, uh you would want to have some minimal network assumption for safety and liveness to hold. Um and uh Andy has given uh has given great seminar talks about uh all of that in more detail, but I want to mention it here so I just so that we are able to map the consensus protocols I'm going to be describing into this uh um into this uh properties um see what the what properties they have. So in terms of network assumptions, um people usually look at three different models. First, the synchronous. Um it's the best for academics because it's easy

to design protocols in this model. There is a known bound delta on network delay and a shared global clock. Um so if you think for a bit, it it from a from first glance, it doesn't seem like this model the internet very well because sometimes you have very large delays between the nodes or there are network partitions and such. But uh since we have the protocols are typically designed to tolerate uh some number of Byzantine miners, you can hide, you know, the network delay that's larger than delta inside your Byzantine assumption. So maybe in practice, sometimes synchronous network is still a good model because if two nodes have delay larger than delta, you

can just assume they're Byzantine. As long as uh you you don't violate the threshold of Byzantine nodes, you're good with a synchronous assumption. So it's like for example, so you're saying like suppose 10% of the nodes really were Byzantine and 20% of the nodes just had a crappy internet connection. Exactly. be fine. Yeah. Yeah okay. Right. Another the better model is partial synchronous where we know there exists a bound delta which is no no don't know what it is. And also shared global clock again. So, nice thing about these properties is that protocols designed in this model they cannot uh depend on delta. So, they cannot have any forking based on delta. They cannot do uh any action based on how much time has passed compared to delta. But, the

properties we can reason still about for example finality in terms of delta. So, we can prove properties about this consensus protocol in partially synchronous model uh based on delta. So, the better are the delta, the better are the consensus protocols. Um and finally asynchronous protocols. These are the best because they make no assumptions about the network. Um and they also set zero network partitions. And actually, it's very active area of research right now building a consensus protocols in asynchronous network. I'll explain why this is possible in just a in just a second.

Um so, I wanted also to very briefly mention possibility and possibility results because we start feeling the bounds of what is possible to do with consensus in different network models. So, in synchrony it's possible it's possible to achieve both liveness and safety with any Byzantine threshold even if everyone except one uh node is Byzantine, you can still achieve consensus. Uh but, the consensus becomes particularly efficient linear time when the number of Byzantine threshold is less than half.

And partial synchrony also know how to build great protocols with Byzantine threshold under um a third. And in a synchrony, unfortunately, there is there was an impossibility of looking impossibility results showing that you cannot achieve neither safety nor liveness even if you have a single Byzantine node, but there's actually a way around this impossibility result uh if you build a common randomness source, if you build a common coin for the nodes. Yeah, so um this involves just involves some cryptography. And this is being done actually maybe this year or last year.

Some protocols uh start being practical for um building common randomness. We will touch a little bit on how they look like. Um but asynchronous protocol synchronous consensus kind of becomes possible. So, typically we're fine with synchrony or partial synchrony in most and most of the protocols will be using one of them. But typically people worry about network partitions. So, what if there's some disastrous event and two countries get disconnected maybe uh transatlantic cable gets broken or something or maybe a large country builds a firewall around it around itself. Uh then you have a network partition and large portion of nodes start being disconnected from another

portion. Um that's kind of a variant of asynchronous network. But turns out you can um have in this particular restricted asynchronous network, you can still preserve one of the two, either liveness or safety. And we'll see which protocols prefer which one. Uh so, our goal will be to design protocols for this network for partial synchrony that will prefer one of this um safety or liveness uh but work um have both when the network doesn't have a partition.

Cool. So, the proof of work that I was describing fits into the synchronous model. At least it was only proven to have to be live and safe in synchrony and can tolerate up to 50% of Byzantine nodes. And in in the event of a network partition, it prefers liveness. So, that's how proof of work fits into the picture. Okay, so now I will describe two popular approaches to proof of stake consensus. Uh Uh, one is Nakamoto consensus. It was pioneered by Peercoin um and sort of extensively studied from academic standpoint in family of Ouroboros papers.

It is very similar to proof of work in that it has a fork choice rule similar to proof of work. So, finality is uh eventual or probabilistic. You need to wait some key number of blocks to be built on top of your chain to be sure that your transaction has been finalized. And the larger the scale, the um higher is your assurance that the block will not be reverted. So, you used to have Ouroboros, so that's that's in Cardano, is that Yeah. Uh, communication though in this consensus protocol is really low.

Um usually linear, but uh even better than linear. I'll explain in just a second. The number of nodes that you can handle is limitless. You can uh this consensus can work when the number of validators um is 100 or 1,000 easily. And in the event of network partition, it favors liveness over safety. So, it will continue finalizing transactions, it's just that two partitions will diverge and be building two conflicting forks. So, what do you mean when you say the number of nodes can be limitless without Uh, well, let me explain the other and then you will you will see uh what what it means. Maybe it will be more clear. So, the other uh approach is BFT consensus

protocols built on PBFT. Although PBFT was not a blockchain protocol, it was adapted to be a blockchain protocol by Tendermint first. And then HotStuff sort of conceptualized Tendermint um and also built a responsive protocols uh protocol from Tendermint. So, these are the most notable uh protocols. But, there are also others that have been published and known. So, finality with BFT consensus is immediate. Sometimes it will longer to get finality if your network conditions are bad, if you start seeing delays, um or if the network is under attack, but once you turn but if the conditions are good, your finality will be extremely fast. And once you get assurance that your transaction is

final, there is no way it's going to get reverted. So, finality is deterministic. Um communication is very high because each validator needs to be connected to every other validator, so they need to form a clique. Uh to answer your question um so um the the higher um the the number of validators, the heavier the protocol becomes. Um so, typically the protocol will limit the number of validators by about 100, like 20 to 40 is a good number for um a performance system. So, the more nodes you have, the slower is the consensus.

And in the event of network partition, this protocol favor safety over liveness. So, if there's network partition, the protocol will just halt and not produce any new blocks until the network is restored. At least it will not be finalizing conflicting transactions. So, safety is preserved. And um on the communication um side, in the Tendermint consensus, you can have flexible network topology. So, one node can be connected to some constant number of other nodes and they can be connected to constant number of other nodes. So, um typically the when a node announces something to the network, it sends it to its peers and the peers send to the peers, etc. So,

uh although it takes longer to propagate through this whole network, you have kind of longer network delays this way of of from reaching the periphery, uh still the burden on each uh node is lower because you're only sending something uh to constant number of peers and you're listening to a constant number of peers. Whereas in BFT consensus where everybody's connected to everybody, you know, first of all, you need to open channels. So, there's a lot of channels to maintain. Uh, but the good thing is that these channels don't have to be authenticated. Just by the by the nature of this BFT protocols, all the messages are signed. Um, so you don't need to additionally open TLS connections. You don't need to

additionally MAC or do message authentication codes on these messages. Um, so in that way, you you know, maybe you can build a more efficient network layer uh, if you if you don't need authenticated channels. So, with the BFT, you could do more or less like the shortest path between some of the like the shortest path between each pair of honest nodes. I mean, like Yeah, you're right. Maybe. Yeah. As long as Yeah, you need to be sure Yeah, it's well connected, but definitely you can do the kind of the gossip style as well.

So, like logically, that's what the network should look like. Yeah. Right? And like maybe each of those edges maps down to a physical path of multiple hops, I guess, right? Right. Yeah. Yeah. Yeah, so BFT can be ported to this topology. I guess that's most frequently people do this kind of communication. Um, but yeah, you're right. So, the other way is not true like the like a Nakamoto consensus. It can work also with this network topology, but it doesn't do the same thing. None of the proto- protocols do with this topology for Nakamoto consensus.

But indeed some of the protocols BFT protocols can adopt this flexible. Right. It's cuz maybe one way to think about these two pictures like longest chain, right? Basically, just whoever created the block has to tell everybody else. And everybody else doesn't have to talk to each other at all basically about that block. Right. Whereas like BFT, everybody's like voting and everybody has to know where everybody's votes to make progress. And so, the communication pattern looks kind of all to all. Is that Is that reasonable or Yeah, that's reasonable assumption. Although um like the thing you were saying, if you can tolerate larger network delays, you can wait for, you know, the consensus uh decision to reach you through multiple hops.

Right. I guess that I'm I can I can interpret those graphs actually as a sort of like the communication patterns, I guess in some sense. right. I can interpret the the sort of complete graph as a kind of everybody needs to keep track of what everybody else is doing. Mhm. Cuz they're building capital and stuff. Yeah. Oh, yeah. Yeah, that's a very Yeah, that's a very good way to phrase it. Uh so, I thought it would be fun to kind of look at the blockchains by market cap and see what they are. So, um I took uh 30 blockchain projects um ordered by market cap and let's remove the ERC-20 tokens that don't have their own consensus.

Um and see what the rest are. So, this is my best effort. I really apologize if I messed something up here. Um sometimes the the projects they incorporate their ideas both from Nakamoto consensus and BFT consensus, so it's a little hard to say what what exactly they are. Uh some of them also don't document their consensus that well, but um but this is my best effort. Uh correct me if you see any mistakes. So um you can color code them um as well also.

Uh the yellow ones are the proof-of-work blockchains, so Bitcoin, Ethereum, Dogecoin, Litecoin, Ethereum Classic, Monero, Bitcoin Cash. The green ones are BFT protocols or BFT style. So, Binance, um XRP. Although Ripple is not quite BFT style, it's a a little bit different, but has a BFT characteristics. Uh Polygon, Cronos, Cosmos are BFT. Algorand is sort of BFT, but it's so different from the rest that I I going to focus on Algorand a little bit more later on.

Um and the purple ones are Nakamoto consensus, also Cardano, Solana, Polkadot, uh Tron, Near Protocol. You notice there are three that are not colored, and those are, as I said, different consensus protocols that are harder to map to this paradigm, Avalanche, uh Stellar, and Algorand. Uh but roughly speaking, most of the time you can you can classify the consensus protocol in the three in one of the three categories.

So, just to clarify something, when you say BFT, you also mean proof of stake? Sorry, yes. BFT is proof of stake, and Nakamoto is proof of stake. Yeah. So, BFT So, BFT is proof of stake BFT And it's proof of stake. Also proof of stake. Yeah. Yeah, sorry, it's a little confusing cuz proof of work is also Nakamoto style consensus. But yeah, the the green and the purple ones are all proof of stake. So, Solana, I have to say, I think it is BFT more. Yeah, so I spent quite some time trying to figure out, and they actually have some fork choice rules that they define in their protocol. So, it definitely has some uh Nakamoto style component to it. Maybe some of the other parts are more BFT

style, or maybe they combine the two. Um yeah, we'll be Yeah, nice to figure out um what exactly they do. I I guess they're in the process of documenting um what they do somewhat better. Um And then, Polkadot is also sort of a hybrid. And they have I think we'll we'll talk about this later, but now we can Finality gadgets, yeah. Yeah, it's Thank you. Yeah, we like at the purpose of the next talk, probably Thursday. Uh but yeah, some of the protocols combine the BFT and Nakamoto together um and run BFT on top of Nakamoto.

All right. So, the first approach is Nakamoto consensus. Um I'm going to describe it in a little bit more depth. Um so, typically in all of these protocols, the time is divided into epochs, and epochs are divided into slots. So, some fixed number of slots constitute an epoch. And validators stake for for an epoch. They indicate their willingness to to run consensus nodes. Um So, I I focus on two approaches, Ouroboros and Ethereum 2.0. Um there are other protocols that are doing something else, but uh I think it's important to understand at least these two.

Uh so, here I will explain the Ouroboros design. So, the leader is selected per slot from uh the validators who have staked for this epoch. And the leader is selected with probability probability proportional to its stake. Um So, leader at a slot, it exercises the fork choice rule to figure out which chain to extend, and creates a block on top of it, and proposes it to the network. So, quite similar to proof of work. Uh but an honest leader um should not be proposing two conflicting blocks for the same slot. So, it should only pick one chain and and propose on top of that chain. So, for example, um here in slot three, the leader was probably just

faulty or failed uh to announce the block correctly. Or maybe there were network delays. Um and network partitions. Leader at um slot four was clearly Byzantine cuz it created two blocks at the same height. And then it causes the chain to fork. So, leader at slot five, if if it was honest, it probably uh heard about the top block first. Uh so, it built on top of that. Leader uh slot six, if it was honest, it heard about the bottom block first and built on on of that. So, then you have to switch ties or introduce figure out which chain to to choose to build on top of.

Um but eventually, one of the chains will win. So Ouroboros proof of fork choice rule is pick the longest chain, the chain that has more blocks in it, and does not fork deeper than K blocks from the local chain. This K is the parameter of the protocol, but it introduces some stickiness property in that if you already know a good chain and you've been following along, you're less likely to switch to a fork to a deep fork or deep re-work. So, interesting. There is a notion So, it's So, this assumes that we have a global shared clock. Is that right?

Mhm. Yes. Okay. Whereas like in proof of work, you don't really need to assume so much, right? So, that like Bitcoin doesn't really need it. Yeah, great question. Actually, the proof of work, I think the difficulty kind of depends on how frequently the blocks are generated. So, if frequ- um difficulties adjusted if the blocks start to appear more frequently, so in a way, it kind of judges by the time steps in the blocks how frequently they arrive. So, there is still some notion of time that's required. So, you still need to keep track of like a 2-week period, roughly.

Whereas here, you need to have a notion of time on a certain much shorter time scale, I guess, the time scale of a single slot. Is that right? Right. I agree Right, you're right. But Ouroboros Genesis, um like a follow-up to the Seroborus paper, it was getting around this assumption that you need global clock, and they were building a protocol that doesn't need that. And to follow up on that, the aside from defining like what is slot one, what is slot two, do they do they actually need like synchronized global clocks, or are they just like do they use it They don't use it in any of the tie-breaking or chain selection?

Or do they just need like some definition of Like like what like like what are they actually using the block for other than deciding what is time slot one, what is time slot two, what is time three? Yeah, I think just deciding what the slot number they it is. Oh, let's see what else they need the block for. Hmm. Yeah, I don't know. I I don't think they need it for anything else. just corresponding to the number of blocks on the chain then? Cuz there's one block produced in Well, roughly speaking, you know how quickly the chain grows, you should not be synchronizing to like an old state.

So, roughly speaking, you should understand that what slot is the full system right now. Um and how many blocks have been created rough roughly at least, so that you know if you're really synchronizing to an old chain or if it's a more up-to-date. What is the local chain in the Oh, local chain is the one that they really built on top of previously. Um maybe following up on that, do you have a sense of what K is in practice? Is it like single digit or hundreds? Oh, great question. I didn't look into that. That's a great great question.

And then I was also going to ask the way that they um choose proportional to stake, is that still just like they have a pseudo random number generator and it's just like everyone knows right now who's going to mine in slot A, everyone knows who's going to mine in slot B? Oh, that's a fantastic question. So, I have a whole section on leader election process, so we'll discuss it there. And then I want to also explain the Ethereum um fork choice rules, Ethereum consensus. It's different in that not only the leader is selected per slot, but also a committee is selected per slot, and the committee is supposed to attest to what the leader is proposing. So, the leaders and this um validators from the committee, they do fork selection according to a different fork choice

rule um to select a chain to build on top of and this fork choice rule uh is called LMD Ghost. It was originally proposed to improve Bitcoin. Um the idea there is that um at a slot you you look what were the latest votes that the validators in the committee casted and these are the circles. Um what blocks they voted on and so the whole tree that you know about from which you need to select one chain um gets weighted. So all of the blocks gets weighted by the amount of validator votes that are um in their subtrees. So eight votes total, five votes in this subtree, three votes

in this subtree. So uh and then there is a greedy selection algorithm of a fork. So you select nodes with highest weight. So anyway, um there's an interesting design choice that along you also select a committee. Cool. So enormous amount of academic work as well as well as white papers on the Nakamoto consensus. Ouroboros papers, I guess, is the most prominent from the academic side, especially since those protocols have been published in the best crypto and security conferences, Crypto Eurocrypt CCS S&P.

Um and have been of course reviewed by great academics. On the other hand, there are great ideas also in the white papers and um I think the white papers also deserve to be looked at and maybe analyzed from more academic perspectives trying to prove actual consensus properties about them. Uh so to fit into that table that I showed proof-of-stake Nakamoto consensus is same as proof-of-work Nakamoto consensus is that you It properties in synchrony, it can tolerate up to 50% Byzantine nodes and prefers liveness over safety in case of network partitions.

Uh so, the other approach is BFT consensus. I'm going to look at next. Uh BFT consensus timewise, the time is divided into epochs and fixed number of epochs constitute a slot. You have a fixed number of validators per epoch and 2/3 of validators are assumed to be honest. So that Yes. You said 100, but 100 is just kind of empirically Empirically. Yeah. Right. I think that's what people think in practice is roughly a good number. You can always grow this to be larger, but then your consensus will be somewhat slower cuz you need you need to collect more votes.

Um Right. So, that's just empirical. It doesn't have to be. It can be larger easily. In each slot, you also have leader election process. So, you elect the leader from the validator set and the leader proposes a new block and validators then work collectively to try to finalize that block and they either arrive um at a consensus decision to finalize the block or they drop the block on the floor and uh the slot is unoccupied. But, finality is deterministic. So, you will know exactly when it should occur, at which slot.

Um if the network conditions are good and everybody is honest. So, um different protocols take different routes, but roughly, you can either finalize in a single slot within a single slot or within uh one to four slots depending on the protocol that you use. Uh so, I'm going to This is my attempt to describe Tendermint in one slide. You should definitely I recommend checking out Tim's lectures on Tendermint with a lot more details. Um but roughly speaking, the Tendermint consensus was the was the first blockchain protocol that was adapting the BFT ideas to the blockchain world.

And the BFT ideas BFT protocols are have been studied for decades. So, they're based on very uh long line of academic work. So, in Tendermint consensus, you have three phases: pre-prepare, prepare, commit. So, when the node is selected as a leader, it broadcast it creates a block of transactions and broadcasts it to the rest of the network. And then the nodes vote on this block by signing it and uh send it to each other. Um Then uh each of the nodes after prepare forms a a quorum certificate. A quorum certificate is a collection of 2/3 of signatures from other validators. Then

they sign this quorum certificate and broadcast it to the network. So, that's roughly the communication pattern in original Tendermint. Um then everybody independently can arrive to the consensus decision. It's guaranteed that um uh good fraction will arrive at the consensus decision. Then they proceed to the next leader broadcasting a block. So, as you see, the communication is quadratic cuz everybody is sending something to everybody else. Um and then HotStuff was kind of an improvement to Tendermint in two ways.

So, first of all, they observed that you can use aggregatable signatures and you can squash um this uh signatures af- collected after the end of prepare step into one signature. Uh or you can use threshold signatures. And you also can reroute the communications through the leader. So, instead of everybody sending to everybody else, you can achieve linear communication using aggregatable signatures and rerouting through the leader. So, everybody will So, the leader will send to everybody, everybody will send to the leader, and the leader will sort of be this re-broadcasting point of re-broadcasting the QC. But this QC quorum certificate um is now constant

size because of aggregatable signatures. So, the second great idea of HotStuff is to pipeline block production, and you can run kind of you can make the next leader proposing block in parallel to the first leader proposing a block at a certain stage. So, you can make the network kind of send messages in parallel for two for parallel kind of consensus processes. It's not that simple. Just a picture to have in mind. It's not as simple as that. That's a rough idea of how this works.

So, the leader will collect the quorum certificate, and will after broadcasting it to the rest of the network, the next block created will include this quorum certificate inside of it, and will already kind of link to the work that the first validator has done. And with this approach of linking, you can actually get rid of the rounds after the QCs form and broadcasted. So, you can kind of have this chaining of QCs at the end.

Um and that's roughly the idea of HotStuff. And your block will be finalized after some number of QCs have been built on top of it, or some number of blocks have with QCs, yeah, have been have been absorbed on top. So, HotStuff, you can think of it having a single chain rule. So, the block B1 will get committed um after that there are three blocks with QCs built on top of it. So, that's how HotStuff kind of conceptualized this block creation process in BFT.

Um very generally, if the consensus like in the current epoch, if you have like more than 2/3 of the validators in the epoch being like Byzantine, does everything still work even like outside of like epoch? Yes. So no. You need to to compromise more than 1/3 actually. So, it's a little less. You need 2/3 honest and then one at most 1/3 can be Byzantine. So, if you compromise 1/3 of Byzantine, they can disrupt liveness of the protocol.

So, the protocol will stay safe and will not be finalizing Wait. I'm not saying it wrong. Right. Yeah, exactly. Sorry. They will be able to screw up the system. Yeah, sorry. Yeah so if you compromise more than 1/3, the system is compromised. So, you need to guarantee like in each epoch you have less than 1/3 Byzantine not just like All right. So like I see you guys have my concentration bound of like even if like maybe like 2/3 of all the validators being honest isn't enough.

You need something like a bit stronger. Oh, yeah, like some probability like I guess that even if you have less than I guess one Byzantine node in total, there's some probability in each epoch they'll get selected, right, to be leaders for that. So, you think you need to put this on random set of my stuff? Yeah. Like in the random set of my stuff, if you get very unlucky and that is you get tons of Byzantine people in the epoch, then that could be bad. So, that's why it's all right to have these big committees to do that. Yeah. Yes, for what I think what Larry said when she just did like 200 almost 100 people period.

Oh yeah. In case there's no random set. I mean, I obviously you can have another wrapper around it randomly sample down. But I think for what Larry is talking about, it's just like there's 100 nodes. Hopefully 67 are doing it correctly. I see. And then if not your nodes, then so is that Is that all right? Yeah, that's right. Yeah. If you're doing sub-sampling of committees, then you need to make sure with high probability you will not have more than a third of Byzantine there in your sub-sample. Okay. So, I guess that will require a somewhat stronger assumption on the overall number of Byzantine nodes.

So, a quick question. So, what is the limit these pictures are super helpful for visualizing that stuff. I think really good, yeah. Um for the aggregatable signatures, like what's the most sort of practical um instantiation? Like what would you actually use if you wanted to do that? Oh, fantastic question. I would use BLS um but there is a caveat if we're exploring in Miranda is that BLS signatures um are not actually aggregatable to constant size signatures. You still need to provide the bit vector who have signed in order to be able to verify. And that bit vector, although in practice is super small, maybe you can assume it's constant and insignificant, still it's linear size vector.

So, technically speaking, BLS is not aggregatable to constant size. Um HotStuff paper is proposing but it's good in practice. I think it's for all purposes, it's fine to use BLS. And that's what I see Ethereum, by the way, is using BLS for signature aggregation. Ethereum consensus layer. Uh HotStuff is proposing using threshold signatures. And for threshold signatures, to create a signature, you can do it in one round. You can do it with EdDSA signatures, which are relatively popular.

Uh but you need to have some pre-processing round of generating the distributed key jointly. So, that complicates the protocol quite a bit in practice. Um and I don't think people kind of like it for their consensus layer. And so, are there any deployed projects which actually use threshold signatures? No, I haven't seen the BFT projects employ that. Um by the way, still research is very active in the area of threshold signatures and how especially in distributed key generation of how to do that efficiently.

Um the simplest protocols also evolves involves somewhat heavy machinery of NIZKs, non-interactive zero-knowledge proofs. Um so, uh to make it efficient, you need to introduce another assumption, which is comes from Paillier cryptosystem, and starts being a little more uh scary maybe. probably going to get more practical. Yeah absolutely. Soon yeah. Yeah. Um, but many many projects, by the way, built the threshold signatures for other purposes, not just underlying the consensus protocol, but on top of that, have, for example, for custody, if you want to split your key between parties, and make them uh, jointly create the signature for you, such that,

you need but but large participation of to sign your transaction. So, I think that's what try These are the projects that are right now driving this research in threshold signatures. Yeah, good point. Uh, academic works on BFT. So, these are the four that I want to highlight. So, PBFT is from '99. It has nothing to do with blockchains, uh, but it was surprisingly very easy to adapt to the blockchain setting. Um, the Tendermint was an adaptation of PBFT. So, as I said, the protocol is quadratic. We haven't covered the case of a malicious leader.

Uh, it's somewhat more involved to explain on the slide, but, um, in leader failure, uh, there's something else you you need to to add to the protocol to handle that. So uh Tendermint was doing switching of the leaders in also quadratic time. The Tendermint consensus, unfortunately, is not responsive, and that's why HotStuff was built, is criticizing Tendermint for not having responsiveness, which means that, uh, the protocol cannot proceed with network speeds.

Uh, and HotStuff can. So, if your network is fine, everybody is honest, you can just finalize uh, you can finalize faster if your network becomes faster, uh, but with Tendermint you have some lock steps that don't allow you to move to the next round as quickly. This PBFT protocol, PBFT, Tendermint, HotStuff, they work in partial synchrony, and interestingly, sync- research in synchronous protocols also continues. So, I was saying maybe synchronous assumption is not that bad in practice, and synchronous PBFT is just 3 years old, very nice protocol with a linear communication that's also responsive.

It looks like HotStuff that rolled dominates strictly synchronous BFT, but they're like the same year. Are there any benefits of synchronous BFT over HotStuff? Uh great question. I think this protocol is simpler. And that's the main benefit just from implementation purposes. But, yeah, you can go well with HotStuff then. All right, so to map it back to our table, this is the kind of protocols typically work in partial synchrony, can tolerate up to 33% of Byzantine nodes, um and in the event of network partition, they choose safety over liveness, so they completely

halt and are not finalizing any blocks. Um great, so going back just to the picture, just to reiterate that finality is probabilistic in the commodity consensus and immediate in BFT. Um and yeah, depending on which properties you would prefer, liveness or safety, you choose one of them. Um peop- more of the recent protocols, they prefer, I guess, at least the trend that I've observed tend to prefer the BFT style consensus just because the finality is immediate and you can also scale um kind of

um the protocols are better understood, so it's in this protocols it's possible to have really fast finality and really large throughput. Especially if you don't have too many validators. Right. And also BFT protocols are somewhat more accountable. So, if there is a safety violation or there is some problem with the protocol, it's kind of easy to see why if you observe the history of how everybody voted in the BFT system rather than kind of analyze these more permissionless systems. Where a lot depends on network delays.

Especially in case of network partitions, you know, how safety. I wanted to dedicate one slide to staking design choices. Just maybe to have something for later discussions. Um, So, validators in all of these protocols, they stake coins as in somehow indicate that they're willing to run the nodes. And the required staking amount can be either fixed. That's the Ethereum approach. You have to stake 32 ETH to become to be a validator. Or it can be variable. And you know, the more you stake, the more likely you are to be elected as leader and the more rewards you get.

Um then um, I also wanted to highlight the delegated proof of stake. It allows stakeholders to delegate their stake to validators. And you imagine in practice there will be um, participants in the system who have a lot of stake but just don't have the technical capability to run nodes. So, it's likely they want to want to lend their stake to validators who can run nodes and then they can split the reward. So, this kind of delegation would probably happen naturally in any system. It just is more accountable and more safe if it's baked into the protocol somehow.

So, that you don't purely trust your validator uh, to use your stake correctly and to give you back the reward, you actually can revoke this right. etc. So, many systems have this delegation mechanism in place. Okay, is there an ethereum or sort of unique in not having it? Yeah, yeah, but in a way they do they separate kind of the consensus key and the withdrawal key. So, if you're a validator, you can have withdrawal key that allows you to withdraw from the validator set and get back your stake with the withdrawal key, and you can keep it to yourself. And then the consensus key, you can you can embed the nodes key as a consensus key, and it will be signing on

your behalf. Um so, in a way they kind of allow this separation for the But yeah, indeed the fact that they have fixed stake um doesn't quite naturally kind of fit into the delegated proof of stake model. Um some protocols um as you were mentioning want to limit the number of validators, and then they will need to do some random selection of a subcommittee, and make sure there are enough good nodes in the subcommittee. Um or they can also take a more centralized approach like the current committee can decide who joins and who leaves.

Um and I wanted also to show this table of how much stake how much is staked in different cryptocurrencies right now. Um and this is ordered by the market cap of the stake amount. So, just 10% of ethereum is so big that it dominates the rest. Um but it was surprising to me that these amounts are super high. So, ethereum has 10% of its total supply staked. Solana has 75%, Cardano 71, Avalanche 58, etc. So, I don't know. I'll leave it to the economists to kind of figure if this is a good thing to have or not, cuz the stake is typically idle, not transacting, just sitting there.

Uh great. So, that's on staking. And now I will move to more technical um part leader election strategies and also the two tips you committee election strategies. Um So, what are the goals of the leader election? So, yeah, again, we have this epochs and slots and the leader is elected per slot to propose a block. And the leader is rewarded for proposing a good block. And if um typically in the protocols if the leader uh violates um the protocol and it is absorbed by someone, this can be presented as a proof to the protocol the leader will get slashed.

Um So, the leader election properties, leader election can either be public or private. A public means that the outcome of the leader election process is visible to all participants at the same time, including the leader. So, the leader learns that he become a leader at the same time everybody else learns. And private leader election is the leader checks herself whether she was elected or not and she can then prove to the network that she was elected. So, she has this a little bit of a delay and she can take this time to prepare a block and then announce herself as a leader together with a block. And it's nice for DDoS protection as we will see because once the the leader announce so the the adversary will not know whom to

attack, who the leader is until the leader reveals itself. But once the leader reveals itself, it also has already broadcasted a block, so there is no purpose of attacking it. It's already done its job. And the leader election properties that we want is typically fairness. So, the leader election probability should be proportional to their stake. Although different uh protocols define fairness in different other ways. Um some favor leaders who were good leaders in the past. Um like the MBFT for example, it has the reputation system.

Um, or you can maybe not be willing to lay to elect the leader that has the most stake too often and make it a little bit more decentralized. So, fairness is typically easy to achieve if you define it well. Unbiasability is somewhat harder to achieve as we'll see. So, unbiasability means that nobody should be able to influence the leader election in its favor. So, if I'm the current leader, I should not be able to make myself a leader more frequently in the subsequent slots. Um, and unpredictability basically means DDoS resistance. So, for an attacker observing the leader election process, should not be able to predict who the leader will be at some future slot uh so that it cannot

prepare DDoS attack uh on it. It's surprising that this um leader election pro um leader election uh can be generalized to solve um more general, more interesting problems. So, if we design a leader election um process that's public, unbiased, and unpredictable, these three properties will give a randomness beacon. Um, the randomness beacon um is this common coin that the synchronous protocols need in order to be built.

Uh um and this can also provide randomness API for smart contracts, not just in a synchronous and any consensus. So, you smart contracts can would if you have a randomness beacon in your protocol, they can have um an access to random bits. They can have get random API. And for example, that's useful for lotteries if you want to figure out who the leader is randomly. Uh randomness beacon will allow you to do that. So, the problem Although we'll be focusing on leader election here, the problem is more generic. So, when you say I should interpret this what is wow in science.

Sorry. Uh so So you you you would assert that if you can actually have all of these properties then you may as well use it as a random beacon. Interesting. Is that Should I interpret that as a positive statement or a negative statement, right? Like it's like a reduction, right? So random speaking is reduced to good public leader election. Does that mean random speaking is reduced to public leader election is like part of the higher Higher. Yeah.

Uh well, we'll see protocols for random speaking, so they have been built. Okay. So there are positive results on that uh side, but also you'll see this protocols are not simple. Uh so maybe you can interpret that as a negative result. Cool. Um so we'll start with the more straightforward leader election process, which is round robin. So the leaders are chosen one after the other in some lexicographical order, or equivalently, this is deterministic leader election. So the leaders are chosen as a function of the slot number.

Um this leader election process is public, of course everybody knows who the leader is together with the leader. Um it's easy to make fair. Um it's also unbiasable because there's no way you can bias round robin, it's predetermined. Um but unfortunately this is predictable. So um if the validators are not don't have good DDoS protection, you can figure out in which schedule to take them down in order for for the consensus to halt and not be able to make any progress. But before we kind of discard this design, it's actually good for leaders with good DDoS protection. And for the M blockchain, for example, we um reason that this is good enough because there

the validators were known entities with very good infrastructure, and they could afford being DDoS protected. Um so that was not a problem. This leader election was fitting there perfectly fine. But for more permissionless systems, this of course um needs to be enhanced. There's another thing which if you do longest chain consensus like Matt's written papers saying how like things like selfish mining get worse if you have predictability.

Mhm. And but if you're doing I think at D and you're doing PBFT type for a cause so it may not have mattered. But for longest chain there are other issues. Interesting. That's Yeah, that's correct. I see. I see. Can I also ask you if you have public versus private? You're saying private is better if the leader learns they're leader in advance of the public? Yes. Okay. Cuz it has this time to prepare a block. Cuz it typically takes a few seconds for it to pack transactions together to make sure you execute them they're all um executing correctly. So typically there is some delay you want before um

you announce yourself as a leader um to to be able to prepare this block. Um that doesn't sound like a like a public versus private issue though. But like here it's public but like I know now that I'm going to be the leader like 15 years from now and I can like it sounds like I can prepare my block very well in advance if it's private. Oh yeah, it's not solving the problem of giving you more time to prepare a block. It's only the problem of shrinking the um DDoS uh window. Got it. Okay, that makes sense. Yeah, got Um then I was thinking it was on time to look at leader election approach in Ethereum consensus layer

um that's running right now. It's called Randao mechanism. Um so there So this is a picture from their specification. Leader of the previous epoch contribute verifiable deterministic randomness. If you um if you know how BLS signatures work, think of BLS signing epoch numbers. Um Um So, they contribute this verifiable deterministic randomness to the next epoch. So, randao reveal kind of mixes their randomness into randao mix.

And then randao mix is used to elect the leader elect all the leaders in the next epoch. So, the epoch is 32 slots. So, you see here that uh the randao mix from slot n plus 96 is influencing leader election of slot n plus 128. So, that's exactly 32 slots in advance, one epoch in advance. Leader schedule gets known one epoch in advance. Um it's also public, so the leader learns they're going to be the leader at the same time the public learns.

And there is unpredictability is one epoch in advance, so the adversary will have one epoch of DDoS window to try to prepare the attack to take that leader down. This protocol is biasable. The last leader to reveal randao mix to to add to randao mix can choose just to drop out of the protocol instead of revealing his randomness contributing his randomness, and that way he gets one bit of bias either dropping out or contributing. It cannot contribute different values cuz the process is deterministic. It's deterministic randomness.

This is where the leader chooses to sign and contribute their contribute their signature. Yeah. And there is only one signature possible. Uh cuz uh BLS signatures have this nice property of uniqueness. You only can generate one signature on a message. Um Yeah, so it Maybe I didn't hear you well, but um so if one attacker has many different accounts and can choose to reveal any subset of them, does that mean they have more than one bit or is this somehow prevented?

Yeah, absolutely. Sorry, great question. Yeah, if you have some key number of Byzantine leaders in succession, you can influence uh the output by key bits. You're right, absolutely. So yeah, it becomes larger than one bit if you have more um Byzantine leaders in a row. But they still argue that small enough to work. Um Keith our question you mentioned like the last leader, is this BLS signing is a sequential protocol that orders people or everyone signs at the same time and last just refers to whoever happens to speak last?

Uh no, so the leader schedule is predetermined, so you know who will be signing for each slot. Um so last means is that just the last leader of the epoch has a little bit of bias on the randomness uh in the future and you and maybe you're asking about uh how we're how the leader is chosen. So leader is chosen from the validator set that's also gets fixed a little bit in advance. Um so when you seed your randomness and your validator set through some random selection, but as an output you get um your committees, uh your schedule of leaders.

Uh yeah, shard chain proposals they don't do right now, but uh does that answer your question? I think I think you answered the question. I'm still confused, so so this this is the protocol they use to select the leader for like the next block or the next epic or they select a sequence of leaders for the next epic. Yeah, they select a sequence of leaders for the epoch next to the next. Okay. And then in addition to being a leader who proposes blocks, the leader also has the option of contributing to the randao or randao is just completely parallel completely

disjoint. No, it's exactly the same leaders that are contributing to randao and proposing blocks. Okay. And then you said that when you So So you said basically I can propose a block. So does it mean I have to provide or not propose a block at all? Mhm. Or propose a block and contribute my BLS signature. Exactly. I propose a block and contribute my BLS signature, then that will mix in with the randomness and then at the end there's some deterministic function that takes as input everyone's BLS signatures and says, "This is the seed that this determines the leaders for the entire next epic."

Yes. Yeah, so the leader can either propose the block and his randomness reveal or propose nothing. You know the block, no randomness. So it's either both or none. And then the leaders for the next epic are fully known the moment that epic begins. Yes. Even one epoch in advance. Got it. And then how like roughly how many Oh, you already said. Never mind. So So an epic is like six Okay. 6.4 minutes.

And that corresponds to like a hundred 32 slots. Each slot is 12 seconds. Got it. Okay. Thanks. The fact that this is biasable doesn't qualify this leader election as a randomness beacon. So you cannot use it in lotteries, for example. But as we'll see Um they're still using longest chain to determine the blocks so they have some consensus protocol. Yeah, great question. Yeah, they use longest chain and BFT on top of longest chain. So, they have somewhat complicated fork selection rule that takes into account the fork choice rule as well as what the BFT layer would say.

The fork choice rule you mentioned earlier, right? You talked about having a Yeah, LMD Ghost. So, that's the fork choice rule. That's the fork choice rule and then I didn't explain the BFT layer. That will I explain on Thursday. But on Thursday you will, right? Yeah. Key is to say is if you have the layer happening within an epoch or the BFT layer if the BFT layer is like multiple epochs long or Um, yeah, it's multiple epochs long so still your time to finality is about two epochs, 12, 13 seconds. So, so that's fair to think like roughly within an epoch it's longest it's or not exactly longest chain but then it's the fork selection rule.

Mhm. And then every epoch or two epochs they do BFT to sync up. that's that's a good way to think about it. Cool. Uh, great. So So within an epoch they're still using a fork selection rule and the leaders are fully known in advance so they would still be vulnerable to these like predictable selfish mining attacks because within within an epoch all the miners are known and they're using some they're using something like longest chain.

Well, I'm not sure about selfish mining. You should discuss this offline. The basic issue is that the proof of work selfish mining whenever you try to do something clever there's always some risk that you're going to actually lose the block you would have gotten otherwise. Right? You do some sort of like private mining then if honest honest would succeed before you extend your private chain and then you lose. So, this is non-trivial like cost-benefit analysis. I see. Whereas, if you knew in advance exactly which rounds were going to be the leader, you just do all of that in your head. And you just like, you know, so it's just it makes it sort of riskless in that sense. Is that Is that right, Ben?

Yeah, or basically like anytime you know that you are going to mine two blocks in a row, that is an opportunity to cancel someone else's block and get more revenue for yourself. Yeah, exactly. If you can compromise leaders in succession, but hopefully at some point there will be an honest leader. So, it's not like you can you you only have a few bits of bias here to make yourself more likely to be a leader for next Yeah, so it it doesn't So, the I agree with you. Liveness and safety should be fine, I would think.

I agree. But the fairness of the reward distribution is also a story. Okay. And then So, these are the designs that are both unbiasable and unpredictable, but are public and these are our protocols for randomness beacon construction. And as we were saying, this is also good for leader election uh for public leader election. But it's more generic in that it can also power random lotteries, give randomness API to smart contracts, and also help boost bootstrap asynchronous consensus. And the star here means that your underlying random beacon protocol should be asynchronous as well in order to bootstrap asynchronous consensus, and not all of them are asynchronous.

So, this is good for leaders um that are hard to DDoS within the time it takes to create and broadcast the proposal, usually a few seconds. So, I will um briefly highlight you these two approaches, the VDF one and the threshold signature one. This will be as technical as it will get, sorry. Um for but the the VDF-based leader election, and I encourage you to watch Joe's talk on VDFs uh to understand that better. Um VDF is a verifiable delay function. The idea is to pass your randomness through a VDF to make it unbiasable. So, a verifiable delay function um is roughly speaking the setup will output a single public key, and the evaluation will take

this public key and an input X, output the result of the evaluation Y together with a proof that this result is correct. Evaluation is taking very long, but it is very fast to verify that the result is correct. If somebody has spent a lot of time computing Y and the proof, it will be able to show you the Y and the proof, and you will be able to quickly say whether that's correct or not. So, that's why a delay. Long time to verify to long time to evaluate. And some VDFs require trusted setups, some do not. Um there are different constructions for VDFs.

And to make your uh beacon unbiasable, you just apply uh the VDF on top of it. So, roughly speaking, when a party the party can have some bias window in which it can pick randomness from a set and hoping that figuring out which one of them to pick will influence will help them become a leader more frequently later on. So, there is a little bit of window between the party knowing the set already from which it can choose um and revealing the randomness. So, the the bias is that interval. If you pass your randomness through a VDF and a VDF where VDF takes longer to evaluate than your bias interval, then you make it impossible

for the party to predict the randomness uh before revealing it. Right? It will have to reveal the randomness before it knows what it will be. So, it cannot it can definitely try to run the VDFs on every member of the sudden parallel, but it will need to reveal the randomness before the evaluation is complete. So, yeah, that way you can get an advisable uh uh leader election from advisable ones if you apply VDF.

A great another approach, I'll go fast here because I think it may be harder to understand if you haven't seen threshold signatures before. Um So, the setup in threshold signature based leader election collectively generates a secret key. A secret key has this property that it can be reconstructed from any threshold subset of shares. Uh so, each party holds a share of the secret key, any two-thirds of them can get together to reconstruct the original key, and it will be the same key regardless of which subset gets together.

Uh parties can will collectively sign a slot number by submitting signature shares. So, um there is a signing process that allows you to sign with a share of the secret key, not the full secret key. So, your message will be the slot number, um and your secret key will be a share. You produce a share of the signature, and then they will um be able to reconstruct full signature from the shares. And the hash of the signature is your randomness beacon. Uh so, of course, communication doesn't have to be that uh um that big um that uh you can always pipeline your

communication through a leader. And there is a I think only one uh scheme we know in the that you require to have unique signatures for this to work. And there's only one unique signature that's friendly to traditional thresholdization, which is BLS. And there's a uh notable project Um right, so this threshold signature randomness beacon powers D Rand project. Um it's a very interesting project. It's all open source. And basically, League of Entropy is a collection of uh companies that get together to run this distributed protocol and generating randomness beacons. And you can go to their website, you have a hexadecimal

string that gets updated every few seconds with fresh randomness. Um and as long as you know, threshold of them stays honest, this you get verifiable unpredictable and unbiasable random numbers as a service. So, they're not using a VDF, right? No, they're using BLS. So, so do they have this last last person problem? Oh, sorry. You last person problem. Well, like like the last person that can decide whether or not to contribute a signature or Well, that kind of protocol is totally like in parallel to your consensus protocol.

Um so, it doesn't quite fit into this round down mix paradigm where you have a leader contribution. But definitely, you're saying maybe um Well, there are issues like that inside the construction of this protocol itself. Uh but the protocol has a way to deal with that. Which is not a VDF, some other material. Yeah. Yeah. All right. Um is it the same signature that's reconstructed regardless of whether it's like 2/3 n + 1 or like 2/3 n + 2 people signing?

Yeah. Because then in that case, it seems like the last person to sign doesn't have an influence beyond like deciding whether it fails or deciding whether it passes. Yeah, fantastic question. Yeah, it does independent of who have signed or how many of them have signed. Um and that's because the signatures are unique. So, there can only ever be one signature, full signature, for any message. So, if you were able to reconstruct the signature, it's guaranteed to only depend on the secret key that's independent of the sub-slot and the slot number. So, So, if for some reason you were able to if you knew there was exactly 2/3 of the other people and you knew what they contributed,

then you could cancel the randomness if you wanted I guess. That's like the one thing you can Yeah, that's one you can stop before it goes. Yeah, threshold of Byzantine fault is the same as BFT. I'm just going to If you go over the threshold, I see. you break Then Uh so, why does Ethereum not use this since make them susceptible to the last whatever problem? Yeah, great question. I think the argument that they make is the leader needs to prepare, which I'm not sure why, but they think that it's a desirable property actually to have a little bit of window um

between the leader knowing it's going to be the leader and it becoming a leader. Um so, for that reason they see it as a benefit to have um this window. Although, they're of course making the leader uh subject to DDoS probably attack. And on on other hand also as a random mix, it also uses BLS signatures just not threshold version. Um and this is very involved protocol. Like, this is especially the distributed key generation part. So, it's just Maybe they will eventually do that. It's just a lot of stuff to implement. Very quickly, I want to also highlight the VRF-based leader election that um makes the leader election private

solving the last desirable property. VRF, don't confuse with VDF. These are two very different cryptographic uh schemes, protocols. Although their name are roughly the same, VRF stands for verifiable random function. Um The It also has three algorithms. The setup outputs the secret public key pair. The evaluation takes the secret key. The VDF that I showed you didn't take the secret key, but only the owner of the secret key can evaluate the VRF, get the output and the proof, but anybody can verify the output and the proof that they match X. So, the resulting Y should be

indistinguishable from random, hence verifiable random function. And they can be instantiated from unique signatures like BLS or RSA. So, each leader will use this primitive to determine whether he is a leader. He will take his secret key, assuming that his public key is known to everybody else, and it will evaluate, basically, X being a slot number, um with his secret key, and will get Y and the proof pi. And if his Y is less than some threshold, the leader he's elected as a leader. Um So, the leader creates a block and broadcasts it together with the proof pi. There is no DDoS window, as I was explaining. The leader has already fulfilled its

responsibility, also revealing itself. But there is a kind of major problem where this approach is difficult to implement just as a building block into your consensus protocols that multiple leaders can get elected, or sometimes none of the leaders can get elected. So, you can imagine few several leaders will have their value less than threshold, or maybe none. And so, your consensus protocol needs to to be able to handle that. Needs to be able to handle multiple leaders or uh no leaders. Algorand, I guess, was the first protocol to be to design be designed to deal with that.

Just to go back um to the properties that all of these protocols achieve. So, round robin, deterministic. Um it's unbiasable, but unfortunately predictable. So, DDoS window is really high. The randao of Ethereum is a little bit biasable, couple of bits of bias. It's somewhat unpredictable. You can predict the leader like 6 minutes in advance. So, your DDoS window 6 minutes. The random beacons ones are better, and the DDoS window is couple seconds that it takes for the leader to propose a block. Um but they're not private, and if you really don't want any DDoS windows there, then you should use the VRF-based approach that satisfies all these properties.

Uh great. So, in the last couple minutes, I just want to highlight a few interesting consensus protocols that I didn't color code. Um this is Algorand, where you can have multiple leaders per slot. So, they also make other interesting design choices. In particular, they don't make um nodes lock their tokens. So, there's no slashing, so it's really safe to be a leader. You only get rewarded. Uh user registers The user user still needs to indicate his willingness to run consensus node, so he need to register a participation key.

Um each node runs a VRF twice. Um similar to Ethereum consensus layer, wants to figure out if he was elected as a leader and the other um time to figure out if he was elected as a member of a committee. And the committee um will be voting on leader proposals. Um so, there could be multiple leaders per round who are proposing block, and the block start propagating through the network. And so, there's this fork choice component in that you need to choose one of the blocks. And the way they choose one of them is just the lowest block by hash.

Um you choose that block, and you get that block propagated. And then in BFT style consensus, the committee votes twice on a block to get it finalized. The other interesting choice they make is making their keys forward secure. So, we'll discuss this more on Thursday, but uh the leaders and validators, they rotate their keys, kind of discarding the old keys to invalidate the possibility of long-range attacks. Um, and uh yeah, Algorand is also network partition resilient.

It but it resumes when the network is restored quite efficiently. The other uh protocol I want to highlight is Avalanche. It doesn't have leader election process altogether. It's a leaderless consensus protocol. It's very nice idea. There are consensus protocols called Snowball, Snowman. Um, it's was originally described in the UTXO model. Thus, transactions form a DAG, directed acyclic graph, and this consensus establishes partial order transactions.

So, roughly it works as follows. Each node accepts a valid transaction TX1 um, when it hears about it, and sends it to other nodes, like re-broadcasts to peers, until it sees a conflicting transaction TX2, in which case it needs to figure out which one to choose, either TX1 or TX2. Um, and then it asks its peers what do they think is a transaction that they that they that they will to include. If TX2 gets more votes, then it switches to TX2. If TX1 gets more votes, it switches to TX2 and re-broadcasts it also.

Uh if it didn't get too much many votes, you stick to TX1. So, the finality is probabilistic. Uh, eventually kind of the full chain uh collapses to believing either transaction one or transaction two. Okay, so that's Avalanche. And finally, uh this is my last slide. I want to show different attacks on proof-of-stake consensus. And this is rather a glossary. Like, I'm sure you can figure out this attacks yourself because they all are consequence of costless simulation. Basically, you don't need to solve proof-of-work mining puzzles, which are very expensive. It's

very easy to create alternative forks. Um just for the glossary kind of because the the projects have settled on these terms. Um so, nothing at stake is relevant to Nakamoto consensus. One irrational validator validator will work on all possible forks trying to maximize him being elected as leader on all of these forks and eventually kind of hoping uh to collect more reward. Um this is typically mitigating by slashing for double voting. So, voting for two conflicting uh forks at the same height constitutes a slashing condition that

can be presented to the protocol and the le- this validator will get his stake revoked or some substantial amount will be deducted. Stake grinding attack is exactly biasing leader election by manipulating the randomness. Um it's also mitigated as we're seeing by good and biasable leader election strategies. Um there's also risk of centralization. So, if the code base is correct, everybody is behaving honestly, then kind of uh wealthy individuals will become even more wealthy because they will the rewards since the reward is proportional to stake, they will grow even uh more stake from block rewards.

So, there is this centralization uh that will be happening in a good behaving system. And I guess uh people are proposing mitigating that with some proper incentivization or taxation of wealthy nodes. And then uh Thursday we will discuss long-range attacks. So, what if you compromise historical consensus keys or you compromise nodes who were very wealthy in the past and then you get the ability to completely influence the fork that gets built from that point onwards cuz you will be controlling uh the majority of the stake or some necessary um fraction of it.

Um and we will see how the ways to mitigate that on Thursday. And stake bleeding attack is also um a form of long-range attack where the attacker can collect meeting rewards in his alternative chain that he doesn't reveal to anybody else, but he gets wealthier there until at some point he gets enough stake uh so that it violates the Byzantine threshold and then he gets full control of the fork. There is a very nice survey I recommend and kind of reading more about this attacks and also different consensus approaches, not just the ones that I described, but there are also proof of authority, for example, proof of elapsed time, proof of history, proof of uh

uh wealth, proof of storage, etc. So, it's very interesting also to check out this other protocols. I recommend the survey from IEEE. Okay, that's all I have.