Pili-Pala Consensus by Elaine Shi (Devcon4)

I'm going to talk about the Pala consensus protocol this is giant work with the hilbert chandra file pass so in chinese pili pala is the sound of thunder it also means fast furious and streamlined okay so I will begin by explaining the problem I'm trying to solve right so in all these cryptocurrency systems the car abstraction is called state machine replication also referred to as blockchain or consensus so in the rest of the talk these terms are used interchangeably and we have a set of decentralized nodes and these nodes are trying to reach agreement and ever-growing linearly or the lakh of transactions okay there are two important security properties that we care about namely consistency and liveness consistency says that all of the honest nodes must agree on the same lock so it could be your log is a little faster than mine because network has delay but nonetheless at the end of the day we have to all agree life this says that whenever I want to buy coffee the transaction will appear in all of the honest nodes locks very quickly it's not like I want to wait forever for my coffee okay now initially the problem may seem somewhat boring right so what's so exciting about building a linearly audit log well indeed if all of these nodes were honest and they correctly followed the protocol the problem would have been trivial but what's challenging about it is when some of these nodes can be corrupt and these corrupt nodes can behave arbitrarily and deviate arbitrarily from the protocol and even in such add adversarial conditions we want to make sure that the remaining honest nodes must nonetheless satisfy these security properties so in the rest of the talk we are always going to assume that less than one third of the nodes are corrupt okay so I will tell you a very simple consensus protocol that satisfies these two properties consistency and lightness and to begin with I will first explain somewhat of a strawman scheme a protocol that's very natural it works by single round of voting and this is actually Sounders fast path consensus protocol the previous version if you are not familiar with the Sounders protocol it doesn't matter because entire talk is going to be self-contained okay so let's start with this very simple voting place protocol and before I talk about the protocol I will very quickly explain the block format we are going to assume throughout the talk right so in the talk we are going to assume every block contains the parent hash basically it's a cryptographic digest of the entire prefix of the chain it has an epoch number so we are going to assume every epoch is one second and whenever honest node sent a message the message is going to get delivered in let's say a quarter of the second so in one epic you can have four round trips for simplicity in this talk I'm just going to assume the synchronous model basically every honest message will get delivered very quickly but at the end of the talk I will mention it's actually very easy to extend the approach to partial asynchronous setting to okay so now of course the block is going to contain the transactions you want to confirm okay to make it more fun this is the scenario we are going to work with Vitalik acts as the proposer and everyone else is a voter right so some of these notes can be corrupt like in this case low key is corrupt and the proposer can also be corrupt so here's how a very natural protocol would work step number one the proposer makes a proposal and the proposal contains a block and the block is tagged with the epoch number indicating the current epoch okay now when the voters receive the proposal they are going to vote on the proposal right and in this case Vitalik proposed an orange block so if you are honest you are going to vote exactly the proposal you have received so everyone almost everyone casts an orange vote except for Loki right Loki is corrupt and instead of voting honestly he voted for you know two blue blocks okay so now we have voted what do we do next we basically wait we wait until we collect enough votes on the same block and when there are enough votes on the same block we have high enough confidence then we can confirm that block so what is enough in this talk I'm going to assume votes from 2/3 the committee is considered enough and in fact if we have 2/3 votes we are going to cut that a notarization okay so a very important thing to remember about this protocol is that all of the honest notes are going to vote to uniquely in every epoch this means that in every epoch I'm going to wait until I hear the first proposal from the proposer I'm going to vote on that proposal and only that proposal I'm not going to vote on anything else so this invariant is very important for consistency and in fact given this invariant I can give you a very simple consistency proof ok so imagine let's fix an epoch ok so imagine for this epoch the blue block obtained notarization and the orange block obtained notarization - and what I want to prove is that the blue block must be the same as the orange block and remember as I said in the beginning we are going to assume less than when certain notes are corrupt okay so how does the proof work if you look at the blue set and orange set and remember there are only n nodes in total right so it must be the case that the intersection contains at at least one third and nodes and now because the adversary controls less than one third this means there must be an honest node in this intersection ok now remember what I said about honest nodes right they are going to vote uniquely and if this honest guy in the intersection voted for both the blue and the orange there is only one explanation right basically the blue block be the same as orange okay so this establishes the fact that with this very simple protocol for every epoch only one black can't get notarization okay and another thing to note is that this consistency proof doesn't rely on the proposer being honest the only thing it relies on is the fact that honest notes vote uniquely okay so with this in mind let's take a step back and think about this very simple protocol right as I said we are going to assume two-thirds of the nodes are honest and online and when the proposer is honest life is all good we have both consistency and liveness consistency I've just proved to you life this is all so simple because if the proposer is honesty is going to propose the same thing to everyone and because two-thirds of the nodes are honest soon enough you are going to collect enough votes and you make progress so when the proposer is corrupt what happens in this case we still have consistency because as I argued the consistency proof doesn't rely on proposer being honest right but we don't have liveness because the proposer can't just crash and fail to propose anything or maybe he can propose different things to different people and everyone will end up voting on a different block and no block will gain notarization in this case so ok so now if you look at this picture we have three out of the four properties and the only thing we need to fix is the liveness issue when the proposer is corrupt and if we can fix that we can get the four consensus protocol okay before I talk about Paulo I want to quickly mention the approach that's used by the previous version of the standard protocol right in the previous version of the time the protocol the idea is that we have the fast path and the slow chain the slow chain is basically think of it as aetherium as Bitcoin but it can also be a proof of stake slow chain right so on the first path we run this voting based protocol like I just explained but when the proposal crashes and the fast path doesn't have liveness we will fall back to the slow chain and we use the slow chain to resolve the problem and to really the next proposer and now you can reboot strap the fast path okay so this is a very simple and powerful idea when drawback is that if you use this approach to fall back to the slow chain to fix the the proposer then the proposal switch is going to take about ten minutes if let's say we use a theorem as a slow chain and that's rather slow and one implication of this is that if we want to have an if we want the proposer to be like decentralized on the fast path it's kind of impossible because every time we switch the proposer it's going to cause interruption for ten minutes and that's not going to be okay okay so what we want is the mechanism to allow us to rotate the proposer on the fast path in the seamless manner and that's what I'm going to talk about I'm going to talk about the Pala protocol paula is thunders new fast path consensus protocol it's actually a full-fledged consensus it gives you about consistency and liveness and and in fact you can't just like run Paula in a standalone fashion even without the slow chain and one question you might want to ask is you know since now Paula itself is a full-fledged consensus protocol do we still need a slow chain right and the answer is you know it still makes sense to have a slow chain because the slow Qing is a multi centralized packing you can have decentralized monitoring of the fast path through the slow chain and whenever you know under these extraordinary circumstances let's say maybe the entire committee can be corrupt in these cases you can still use the slow Qin to recover okay so again if you are not familiar with Sanders current approach it doesn't matter because the protocol I'm going to explain as I said is self-contained and the full-fledged consensus protocol in itself okay so since we are going to talk about proposal rotation the most challenging case is if every block can allow a new proposal and that's what we are going to stick to in this talk we are going to assume a very simple around robbing and in epic I note I is the proposer so if we can solve this extreme case then the other cases are simpler like for instance you can have a stability favoring policy where you only switch the proposer when the current one doesn't work ok but this is what we are going to stick to in this talk ok so let's kind of quickly recap the fast path the one round voting protocol we mentioned right and let's try to work the proposal rotation into this protocol so as I said the protocol goes by epochs in every epoch we are going to do the following very natural if I'm the proposer of this epoch I will take my freshest notarize chain and I will propose the next block extending the freshest notarize chain so very natural when people receive the proposal they are going to vote as I explained earlier everyone votes uniquely in each epoch but I'm also going to assume that when people vote on the block they are going to check that the parent chain has been notarized because if the block extends from an invalid parent you shouldn't vote on that block ok so the protocol goes by proposed vote proposed vote very simple of course it doesn't quite work yet and what I'm going to do next is to kind of describe the problems with this protocol and introduce two very simple fixes to this very simple protocol ok and then the resulting protocol would be actually provably correct ok well the nice thing is that this very simple protocol already works in ideal world when everyone is honest right if everyone is honest we should what you should expect is that you know as the epochs go by these blocks get notarized one by one and nothing will be skipped and things are all good but when some of these people can be corrupt so by the way I forgot to mention and I'm just going to assume like the committee itself will act as the proposer I'm not going to distinguish the and the proposer anymore okay because the proposer is like you know by rotation okay now when some of these notes are corrupt then you'll run into these somewhat tricky problems and I will use this as a running example to illustrate the problems and to introduce the two simple fixes okay so let's look at this scenario right so imagine this is a notarized chain that I see during the protocol what are the problems here one problem is that the block number two is being skipped there is no block number two and another problem is that the fifth block is extending from three and not extending from four right so this actually creates a fork what I really want to talk about is the second problem but let me just very quickly explain the first one right so how can plug to be skipped so if proposer two is corrupt let's say he just crashes and he didn't make any proposal I mean of course no epic two block will get notarized right so what we don't want is for a single bad guy to kill liveness and we can do this if we just basically were just going to allow skipping in a notarized chain the epic numbers don't have to be consecutive you can skip okay but this skipping behavior kind of introduces the second problem which is I would I want to focus on right in this case you may ask why does the block number five extend from three and not from four okay so let's think about it well very natural explanation is that perhaps the proposer five is corrupt although he sees block four notarized he tries to you know undo block four by extending from a previous block okay and that's not going to be okay and in fact you know in the extreme case if I'm malicious I can extend from a very very ancient block from the past and that's that's not going to be okay right so the fix is actually very natural and this was the protocol we had earlier and I'm just going to add an additional route to the voting to say whenever I vote for a block I will make sure that the parent chain is fresh enough right if this proposed block is extending from something way way way back in the past I'm going to refuse to vote on it so technically we have to specify what it means to be fresh enough and the most natural strawman kind of idea is to say I will compare the parent block with the freshest notarized chain I've seen so far and I want that the parent block be at least as fresh so this almost works but not quite so because one thing is that the proposal was made let's say half a second ago right and if I'm comparing the proposal with my current freshest notarized chain that's kind of unfair to the proposal because a lot can have happened during that half second right I could have seen new notarized blocks during that half second so what the protocol actually does is to have a slightly relaxed condition instead of comparing with the present myself I'm going to compare the parent block with myself but a second ago so the second is like a parameter it actually captures attention between consistency and lightness and the actual proof to show that this parameter works is a you know just it needs a little bit more work and but for the talk I'm going to ask you to take my word for it if you set this to be one second it'll all work okay so that's the first fix and we are almost there we just need one additional minor fix okay and I'm going to use exactly the same scenario same question to motivate the second fix so remember what we asked is why does the block number 5 extend from and not four and earlier we said you know perhaps the proposer five is correct now I'm going to ask you to erase everything from your your mind forget about everything I explained and let's start from scratch here's another possible explanation it actually could be the case that proposed a five is honest and it is proposal for who is corrupt and this scenario can also happen when proposal for is the bad guy and how can it happen here's the concrete attack so let's say Loki is our proposal for he proposes two blocks in epic for the blue block to the blue guys and the red block to the red guys now we have six and people on the committee so you need like four votes to have a notarization right in this case if you collect all of the honest notes votes it's not enough to make a notarize issue for either the blue or the red block because we have three for blue and two for red but remember that the corrupt guy also has a vote now if the corrupt guy votes for blue he can have an authorization for the blue block and the bad thing here is that the corrupt guy is the only guy who knows an authorization for blue and no one else has seen an authorization for blue yet right so now he can play it to his advantage in particular he can time the release he can let's say release the last vote to a subset of the notes first so some of the people will see notarization for this block first before others see it okay so concretely okay so this is the only guy who knows an authorization for the blue block so concretely he's going to exploit this advantage in the following way so at some instant the bad guy chooses one victim in this case spider-man and it's going to tell spider-man an authorization for the the fourth block okay at the same instant everyone else hasn't seen another ization 4/4 yet they've only seen notarization for the prefix up to three so now what's going to happen is that these guys are going to vote for the block 5 and because the you know the fifth proposer is honest and he hasn't seen notarization 4/4 yet so he's going to build this block from 3 and then this block can take notarization in this very instant okay so what is problematic about the scenario the problem here is that suppose and at the instant when spider-man sees notarization 4/4 if he hastily confirms plot for that he's in trouble because at the end of the time he'll live to discover that in fact this other fork survived to the end of time and 4 is abandoned right so he risks inconsistency with the rest of the notes at the end of time okay so what do we do now well the moral of the story is that like perhaps I shouldn't confirm a block the moment I cease an authorization form for me to confirm the block not only do I want to see an authorization for the block I also want to note that many other people have seen an authorization for the block - so I want like a higher degree of confidence okay so now to implement this idea the question we have to answer is how do I know that many other people have seen the notarization right I know when I see the notarization but how can I tell that you guys have seen the notarization - in fact we can't do this also very simply so imagine we have two consecutive blocks in this case 3 & 4 and I've seen both of them notarized so remember the honest notes are only going to vote for block 4 if they have seen notarization for 3 right I'm see the notarization for the parent before I vote for the block so this means by voting for four I'm also attesting to the fact that I've seen notarization for three in epic form so whenever I see this pattern two consecutive blocks get both getting authorized I can draw the conclusion that many honest people must have seen an authorization for three in their epic form not only have they seen the notarization they see it very fast the seating I pick four so this is very nice because for any future block many since many people have seen notarization for three very quickly they're going to insist on the prefix ending as three be included in any future chain and that's how the block is going to stick around and not be lost right so for instance I put five for any future epic if anyone makes a proposal this proposal must include the prefix ending as three otherwise people are just going to refuse to vote on it right remember people check that the parent block must be fresh enough when they cast the vote okay so essentially this motivates the second very simple fix and all we need to do is to add the following modification to finalization right so remember in Bitcoin whenever we see a chain we don't output we don't confirm the whole chain we chop off the trailing six blocks the trailing six blocks are not stable yet and here it's a little bit similar except that we don't chop up six blocks right whenever I see a notarized chain and let's say the notarized chain and at a streak of consecutively notarized blocks so basically everything except the last block is by now so if any time I see a notarized chain ending at a streak of consecutively notarized blocks I only have to chop off the last one and then the prefix is notarized but the prefix is final okay so that's basically it and just to quickly recap the protocol is very simple you go by proposed vote proposed vote and you you need to check a couple of things when you vote and then this very simple proposed vote based protocol combined with finalization rule actually gives you approval a correct consensus protocol I'm not going to go through the proof and to quickly conclude in this talk I talked about a synchronous protocol that tolerates one-third corruptions right for Santa's new fast pad consensus it's not too difficult to extend this protocol to the paschal asynchronous setting and as I said the protocol is extremely simple it's like almost the most natural protocol combined with the you know a carefully thought-out finalization rule and what's cool about this protocol is every block requires only a single round of voting to confirm okay so let me just quickly conclude and try out our test net and also sander is currently hiring and we have all sorts of positions including executive level positions like CMO and CRO and contact me if you are interested thanks