Byzantine Fault Tolerance with Dynamic Participation with Ling Ren | a16z crypto research talks

Transcript

um I'm sure everybody knows about the consensus problem we say a blockchain problem is that the goal here is to build a ledger it's also called State machine replication all these different names in the literature right but the high level idea is that we want a set of participants to agree on the totally ordered list of values like despite that a fraction of the participants are malicious and they try to create disagreement among among honest participants right and uh in this talk I'm going to focus on what we call layer one right meaning that we will focus on how to

agree on these values we're not going to care about what these values represent and what the what they mean and that's like they have different meanings in different applications like for example currency or storage smart contracts Etc okay and um so it's called State machine replication because if we can agree on these values then every participant can locally evaluate these commands or state Transitions and we will all the participants will stay in consensus in sync with each other right for example here um the nice situation would be that every

transaction is agreed upon and everybody can apply this mandatory transfers and and agree on the total balance and for each for each account and what the bad guy tries to do is to create a disagreement right the bad guy tries to send create two transactions they both coming out to have his own account and if say the two honest users A and C they decide on different transactions then this is called a double spend attack for our later one it's called the Via violation of safety or consistency and so this is a very basic introduction

about the consensus problem the first thing I want to point out is that this is a classic problem it has been around for at least four decades so what's new about the Bitcoin or the whole blockchain innovation and more importantly uh it's not just about what's new right so we can identify some new features of Bitcoin right but we should also ask um is it good is it uh is it important right so there's some new features that are may actually be drawbacks or limitations of Bitcoin right or they are nice but not as important as people think

so yeah this is not directly related to my talk right but uh I think it's a good exercise to and and make it the more engaging to ask this question like what do what do people think what do you think are good important and uh novel in Bitcoin and blockchains right proof of work permissionless yes that's uh the first thing that people know this like that the Bitcoin system allows anybody to join and uh I I would say this is a this is a novel property of Bitcoin and it is a good property right but uh I would also argue that it may not be as important as uh touted or as people

believe it is the reason I say that is um nowadays the community is kind of moving away from work towards to a mistake and in my opinion proof of mistake is permissioned just like the classic consensus algorithms proof of stake is no more or no less permission less than classic algorithms and the reason is that improved stake basically you have a voting power if you have coins in the system right and The Ledger wrote down writes down every single coin holder every single account

holder so and it if you want to participate you have to purchase some coins from others right so those people have to sell you are willing to sell you their stake and that is the permission you need to get to get in the fact that newcomers can purchase stake does not make it permissionless right because we can also Imagine for a classic fully permissioned traditional protocol I say we have 100 parties running consensus a newcomer comes and asks hey does anyone want to sell me your membership right if they make a deal and

the new person comes in and some mode member leaves like that's the same thing as stake changing hands right and um so but that's not to say proof of stake is uh has no advantage to to Classic consensus it does and there's a very important one that's uh it supports Dynamic participation in the sense that the total number of participants in the classic consensus is fixed when I say 100 participants it's just this 100 participants they have to most of them have to be participating all the time right whereas in proof of work proof stake that's no longer the

case the universe of total participants is very large but any time there's only a small fraction of actually participating and it can go up and down and this is the bitcoin's hash rate over time and we can see over the years it has increased a billion vote right and that is not to say that the bitcoin's bitcoin's participation increased the billion vote right because it's a combination of two things more participants and also each participant having better hardware and better compute power right but still it's safe to say that the Bitcoin participation also increased hundreds or thousands votes since this invention right and you can also see there are

also cases where the participation suddenly drops by half or even more than half right because the say the price crashed and many miners are no longer interested no longer profitable right or there may be government crackdowns certain mining operations and if we zoom in to um to a smaller period you will see that this sort of sudden jobs in participation or certain increases in participation are actually fairly frequent right when I zoom out it's hard to see it's the everything is uh is drowned out

in the grand scheme of things right but if we focus if we zoom into uh it's about a few a few months you can see um this the Bitcoin demonstrated a phenomenon level of robustness to participation sudden changes in the participation okay and this is a protocol I would say it's novel good and important in Bitcoin right that classic particles do not have why was everyone uh yeah I didn't really investigate okay

so first I should clarify that this bottom is not zero so it's not as dramatic as it shows but still I think these two are about 40 drop um yeah I didn't investigate this every single instance right um yeah it seems that there are just uh miners shutting down their system and opening up regularly and um since we're on the topic I'll just give one more example right that um certain properties of a Bitcoin maybe novel but not necessarily good for example it's commonly considered a new

property in Bitcoin that security kind of increases over time right when the blog First shows up you you can't finalize it yet right when it's buried deeper and deeper in the chain you have more and more confidence that it will it's gonna it's going to stay so this is also a somewhat novel property of Bitcoin um but it's not a good one like it leads to Long conformation latency if we can finalize it right away when it shows up and don't have to worry about it grows deeper and deeper like that's a better particle so this notion of uh lung latency or security increasing over

time is a property we would like to avoid if possible right and the longest chain style protocols the Bitcoin pioneered have this drawback and the classic PFT does not so that leads me to the central question I'd like to would like to ask in this work can we achieve Dynamic participation and low latency at the same time right so basically combining the best of both worlds all right so then this is the outline of my presentation today I'll first um help review the longest chain style protocol and the classic BFD protocol and we will see why they have the respective trade-offs

and then I'll give a more rigorous definitions and models and then the main part of the talk is to extend the classic PFD algorithms to support Dynamic participation if we have some time left in the end we can I can throw some open questions right what else is novel in Bitcoin that we should try to achieve or try to um try to obtain without paying for its uh prices and drawbacks all right so yeah I'll go over this um briefly all right I I think everybody knows how nakamoto's longest chain

constances work right every uh well all the time were doing some local random Lottery each node is trying to solve a puzzle at some point some node is going to solve it and uh the winner of that puzzle is allowed to append one more block to the chain and we keep doing that and once a block is buried deep in the chain and we consider it committed and or decided so the this longest chain protocol is a lottery based protocol is what allowed Bitcoin to have Dynamic participation right so suppose suddenly half of the nodes or more than half of the nodes

disappeared left to the system the particle is still going to work at some point one of the remaining nodes will solve the puzzle and become a winner right and at some point another winner is going to show up right the rate of winning winners showing up will be reduced but it will keep going so this is this is what makes the longest chain style particle um dynamic in terms of participation however it is also the reason for its long latency and the latency of longest chain particle I I put up somewhat complex formula here right there are multiple factors that

contribute to its latency right the first one is this conformation depth we say that you can only be confident of a decision if it's buried deep right how deep that is usually a security parameter in practice is six but if you want to get a higher level of security you may have to wait for dozens of blocks or even higher if you want a cryptographic level of security right okay and this is just a simple illustration right if you if this confirmation depth is set too small then there is a chance that a higher chain is going to show up and overtake the what you believed to that uh to be to be the committed decision

okay so there are other things that leads to the long latency of Bitcoin right the second one is that there is a notion of block interval in Bitcoin every block 10 per 10 minutes and this interval needs to be set to be considerably larger than the network delay right then the message delay upper bound right otherwise uh your chain would not grow nicely as as a chain and otherwise then there are concurrent Solutions found concurrent puzzle solutions found all the time and your blockchain will become a block tree and that reduces the for tolerance of the protocol yeah

I saw the higher fault tolerance you want like the higher latency it will be right so we say we approximately we always say Bitcoin tolerates minority right but it's not really 50 it's more like uh 49.7 something like that right um some follow some later systems like ethereum pushes this further by reducing the block interval and then they're sacrificing their tolerance to something like 45 46 percent right so we can't cannot push that too far right and the last term is what I'll call the actual participation level

so if you think about it in a Bitcoin style system we can't we kind of have to make a guess that how many people are around how much computation power is around and then we need to set the difficulty to make sure that the block shows up on average about 10 minutes but if that guess is off for example if suddenly 80 of the people left the system 80 of the computation power left the system then you wouldn't get one block every 10 minutes and you will have to wait for like 40 40 minutes five fifty minutes for one block to show up and so if the participation level is a

lot lower than what you expect right the latency will increase on the flip side right these two are kind of uh two sides of the same point if the participation level is a lot higher than what you expect then you would lose for tolerance all right so on the other hand we have classic bft protocols that follow in the line of work started pioneered by Lamport and uh um shock stack and piece and all the way to paxos pbft all of these protocols the

roughly speaking follow a paradigm where we have a leader once node serves as the leader the leader makes a proposal and the other nodes vote on the proposal and usually in two rounds and sometimes three rounds and at the end of the two rounds if both rounds of voting succeed meaning that uh enough votes are gathered then they will make a decision right right there and usually enough votes means one half of the total participants or two-thirds of the total participants and that's what we call a quorum threshold

right and hopefully you can see this style of classic bft protocol has very good latency it's going to make a decision in a few rounds so it's a constant amount of latency however it doesn't support Dynamic participation because it expects to receive one half or two-thirds of the total particip total number of participants to vote right and if say half of the people leave the system then you will never be able to get a quorum of votes and the particle loses its liveness okay now uh it's coming back to the central question of this talk and we

have these two staffs of protocols one have Dynamic participation but not low latency the other has low latency but does not support Dynamic participation I and the main purpose of this talk is to show you a new particle that achieves both at the same time let me just very quickly mention some related works that attempted the this the same problem but some of them reduce the latency but doesn't quite get the constant optimal latency and there's a there's one work that did get constant

latency but it's targeting a unknown static participation not really dynamic okay so now uh let me make things a bit more formal um more rigorously we have set event potential participants so this is permissioned because the list of participants is known to everybody and we have a pki everybody knows everybody's public keys for now I'll just keep the set fixed I don't anticipate any problems to extend it to a change in set to model State changing hands but we haven't done the full analysis so I

don't want to make claims there okay uh at any time t on only a small NT participants are active the rest of the participants are inactive and we do require an honest majority among the active so less than half of NT can be out of a serial okay and any participant can transition between inactive and active at any point right so this is the dynamic participation part and they can do so without giving any advance notice

and it can happen in adversaries control right the adversary can choose to say shut down this set of nodes and bring up another set of notes right without any constraint I think technically we do have a constraint that the attack attacker cannot shut down everybody right then nobody remembers what happened in the past and that's not okay faster there's one honest note staying there okay so yeah I also remarked that we currently assume that the adversarial participant never goes inactive right but this is more of a technicality

because if it's a bad note since it's Byzantine you can do anything it can give its secret key to another bad node and then goes inactive that's as if it never goes inactive so what I'm trying to say is that the protocol I'm going to show you should work fine if the adversarial participation actually fluctuates but we don't know how to model that we don't know how to how we don't know how to model and adversarial participant goes offline if it reveals it secretly either adversary can only go up cannot

go down yeah what but yeah what I'm trying to uh convey is that if we have a magic way to to say that this 100 adversary note suddenly half of the magong right only 50 remain and the other those who were gone did not reveal their reciprocy then our particle should be able to handle that case that adversary goes up and down right right it's just that we don't know how to model or formally forbid these bad notes from giving up their secret keys or giving up the future messages they would have sent if they were active I think some tech yeah so that's why I think it's a technicality

in terms of the model right not uh not the limitation in terms of the solution okay so yeah so that's a short summary of our model in total participants and only a fraction of them are active at any point and it can change at any point and the problem we're trying to solve is um is a kind of a variant of State machine replication or Atomic broadcast by participants send values and they want to agree on the ever-growing sequence of these values okay and there's one more important

assumption we need to make in the model right that is there is a known upper bound on the message delay this is the synchronous model and this has been shown to be necessary so and the end the team in the audience formalized this if there is no such Bands then essentially the network can partition the two partitions should both make progress because the protocol is supposed to support Dynamic participation right they do not know the existence of the other partition like they thought the other partition just went offline they need to keep going on their own then there's seems no seems to

be no chance in solving the problem okay so um yeah this is the oops okay yeah otherwise the dynamic participation is impossible um I think I took out that one remark that Joe was asking what's the difference between this model and the Sleepy model here we are assuming that a node if it went offline it knows it went offline right it's a it's a node when the offline by knowingly shutting down its computer the last time I talked to Elaine she said um she assumes that a note does not know

if it's online or offline um yeah I have some reservations about that model both these applicability and uh whether it's solvable that's that's why I choose not to call it a sleepy model quick so um now coming back to to the classic bft I we're going to try to extend it to support dynamic dynamic participation and here is the main challenge the main challenge is that it's based on a static quorum

so the Quorum size is chosen based on the total number of participants right for example half of n so um if very few nodes are online then you will never be able to get such a quorum so we have to extend this notion of a static quorum to a dynamic column that a quorum should be defined based on the actual participation not the total population however the problem is that we don't know the actual participation I right so

the best we can do is to define a current threshold based on the perceived participation meaning that I will ask the active nodes to send the message I am awake I am here and then we count how and how many I am awake messages there are and that is my perceived participation and the Quorum size which is how many votes I require will be said to be say half of the perceived participation and again I use begin to denote total population I use small n to denote the actual or perceived participation my perceived participation may be

different from yours that's the biggest problem we need to solve okay right so um yeah so the challenge is that malicious note May announce them partially right so I tell Tim hey I'm here but I don't tell Andy right so they perceive different amount of participation right that means they will set different Quorum thresholds okay and the issue with that is then this a set of votes which we also call Quorum certificate is no longer transferable so for example here node a perceived the higher participation level right so therefore node a require

more votes to be to be in the quorum so if they are like five volts here so node B may consider that to be a quorum right node B will be happy and make a decision however oops if node B send this quorum to node a no they will say no no no that's not enough right that's not a quorum that's insufficient number of votes I'm not going to commit and that will be a big problem so the the

Central challenge in this in this work in this talk is to restore this notion of certificate transferability in the context of dynamic columns okay so let me uh say a bit more on that right certificate transferability is uh like very important in classic bft right but it's just so fundamental and so trivial there that we usually don't think about it and um so now once we're aware of this problem we can hopefully I can give you some intuition that this notion of transferability is

routinely used everywhere in classic particles um it's very common that in bft protocols we have something like this if one node makes a move then every honest node weekly support that move it's like if you want to get a paper accepted One reviewer needs to Champion it the other reviewers need to be not against I need to be neutral or weak supporting weekly supportive right all right there are many examples in in the classic particles it's very common that we have mechanisms to ensure that if one node makes a decision then every other honest

node kind of locks on that decision you can think of it as a soft decision or if one node makes a softer decision then everybody has seen that proposal um something more concrete if one node cast the rounds to vote then we want to ensure that every other honest node has received round one votes like something like that and this can be formalized with the with the notion of a graded agreement over there in if you're familiar with the problem if you're not familiar with the problem it's okay it doesn't it's not that important but if you have heard

about this notion then it roughly says if one node outputs a value with a grade one meaning that with confidence then other node should output that value with lower confidence there are many such steps in traditional bft particle and we usually don't think don't even think about them because it's so easy to do to ensure this in classic particles right because all you have to do is to design the protocol such that a node makes a move only when it receives a quorum of votes right and then you ask that node to forward this quoruma votes to everybody else so they will also recognize that as a

core mobiles right they received it a bit later so they will not be the strong champion of that move but they will weekly support that move so all of these uh all of these things can be trivially guaranteed by this notion of certificate transferability right so uh now if we can restore this notion of transferability in terms of uh in the context of dynamic Quorum and then we can mimic the traditional protocols and basically follow their ingredients and follow their recipe and we will get the dynamic participation protocol

and the key technique is what we call a Time shifted quorum okay so step number one or if you've seen graded agreements then we'll try to do graded agreement here so step number one every node will send a pre-vote message for for the value it supports okay and also they will send a wake one this is the message that announced themselves I am participating um also yeah I'm assuming log step rounds for Simplicity now that the execution is divided into runs all the messages sending happened at the

beginning of the runs and by the end of that round all the messages sent in that round are received right so this is a kind of idealize the model we can get rid of it but I'm going to assume that for Simplicity for ease of presentation okay we're also going to uh we're also going to ask everybody to forward all the newly received messages okay so then in rounds two first we will do the forwarding right everybody will forward these messages they received in round one additionally we'll do accounting everybody will count how many pre-vote messages they received by the end of this round by the end of the second round and we'll call that

variable V1 okay all right so bear with me I'm dumping you on the entire follicle on you and hopefully the intuition will be clear afterwards right now third round they will do an every node will do another round of counting right they will count again how many pre-vote messages they received right so this is the total right so V2 is certainly greater than V1 or greater or equal than V1 then they're also going to count how many awake one messages they received by the end of the round three

and additionally they're going to send a week too right that's another round of announcement that I am still here okay now lastly uh if V2 is more than half of M2 that is the they were going to send the vote message so this is saying the number of votes meet the threshold that were perceived participation then they were going to do a proper vote you can think of this list as pre-vote as the first round of voting and the vote has the second round voting okay now lastly they're going to count yet again

the number of awake one messages received by now we're going to call that M3 and then they're going to do their this make their make their moves if V1 is greater than half of M3 they're going to make their proper move if number of votes is larger than half of number of awake two they're going to do the weak supporting move okay so why does this work right let's now bring in another node the property we want to ensure is that if one node makes a strong move then everybody makes the weak move okay

now let's first uh let me first point out some important observations so notice that the V1 of any node will be no greater than the V2 of any other node in this case let's say this node has a V1 here that's no greater than the V2 that any other node got in the next round this is because we're doing the forwarding right so if this node seeing Viva or V1 pre-votes it's going to send them to everybody else right so by the next round everybody will will see

everything this this previous node has seen okay oh that's clear the same logic the M2 of this upper of a note is going to be no greater than the M3 of any other note also because of forwarding right anybody anything that has was seen here will be seen over there okay uh now we are pretty much in business oops okay okay now if any node makes a strong move so their V1 is greater than half of V3

uh M3 right let's say this bottom node is making the strong move now because of these two inequalities if you look at any other node their V2 is greater than the sky is V1 and their M2 is smaller than this guy's M3 so if this V1 greater than M3 half of M3 holds for this one node then V2 greater than half of M2 will hold for every other node so that will make sure if one node makes

a strong move then everybody will vote if everybody votes then everybody will see that votes is more than half of a week too and so everybody will do the weak support yeah that is uh that is pretty much the key technique in this work then um we kind of get got back this property that if one node makes a move everybody is weakly supportive of that move okay now okay so yeah I'll skip the detailed protocol but from there and the time

shifted Quorum can be used to build a graded agreement the traditional bft can be viewed as a series of graded agreements usually we don't view them that that way because it only complicates things right but uh in once we're in the dynamic situation it's helpful to break down a traditional protocol as a series of graded agreements and then we plug in that previous thing I just showed you and then we'll combine that with a random leader election using vrf vdf or any other mechanism and we will get a consensus protocol with expected constant latency okay

um but the it's not super efficient concretely because upgraded agreement has seven Delta latency we need five of them and our total expected latency ends up being a fairly large constant so yeah so some future directions when can we can we get a better concrete latency then can we improve can we reduce the communication cost of this protocol right right now we're doing a lot of forwarding and everybody is forwarding every single message that is fairly expensive having said that I find the protocol very interesting right because this is the first PFT protocol that handles Dynamic participation I and achieves a constant

latency it's very short list of some questions that I think are interesting and open I am motivated by this uh like this this question I post in the beginning right what else is novel good and important in Bitcoin if we like if we can identify these properties then we can ask can we get them without paying for the proof of work and longest chain latency of Bitcoin style particles give you a few examples they're the longest chain particles likely handle a intermediate model between synchrony and partial synchrony

we don't know what it is we haven't been able to formulate such one um some examples some other examples long extreme protocols should be able to tolerate some message loss but we haven't been able to formalize them same thing for sparse gossip Network is it an ad hoc trick or can we prove that in some model it is it provably solves consensus and lastly incentives it's also a big question with a lot of open problems there right yeah that is the end of my presentation I'm happy to take questions [Applause]

extendedness or the relationship with like a communication you know like a sub linear communication model where you randomly sample this participating in every round this it seems compatible to me I I guess the oh yeah one challenge is then do you do you put a threshold do uh do you determine the size of the committee beforehand right what happens if the participation drops below the company size because it's interesting something about copper render I guess anything with vrs or uh you kind of

randomly pick who's eligible to participate in each round you end up with a random number of participants that you don't really know threshold so it's kind of interesting it's related to like you don't really know how many people are active and in that case it's not that people are asleep it's just like they didn't get a winning ticket they didn't just have some probabilistic notion about things but right I guess they could also have problems right yeah right yeah that that's a yeah good good observation but I will point out that it is a I think there is a difference in terms of how unpredictable it is right so with vrf that you have a fairly good idea

that it's going to be very close to the Target you set because of a lot of large numbers they don't want it to be so big I think algorithm usually like 100 or 200 right right but I think at that level a lot of large numbers uh some would apply right and you you may get uh like ten percent five percent uh error right but here we're really trying to Target very wild swings and sort of the steps of the protocol is it this set of active notes to stay

fixed across those um yeah that's a great question we don't need it for safety we do need it for liveness in during this period so okay yeah because the claim I made here is that if one person makes a strong move then everybody makes the weak weak move that's the safety Lemma right but it doesn't say that there will be one person making a strong move right that one that part needs to stable period right so in that sense we're kind of uh adopting the mentality of Patrick synchrony that we're going to maintain safety even this wildly

swinging but we're going to get liveness only when there is a stable period