EthCC 2: Robert Habermeier

good evening hello hi how are you nice to see you all here today on this day good hi my name is Rob I am a co-founder of poccadot I've been working a lot in the implementation part of that is consensus stuff so I want to talk about today I want to talk about consensus and finality in polkadot so what kinds of consensus algorithms we're using what sort of challenges we're facing how the implementation works in practice I would say from our perspective we're a very practically minded team we've done this before with consensus algorithms especially we know what kind of implementation challenges are likely to pop up yeah so polka dot employs a hybrid consensus model so this is a consensus model where you have some kind of eventually safe block production mechanism you know like proof of work like aura like Ouroboros Ouroboros is a big inspiration of our design so this is something that's synchronously safe it's not asynchronously safe maybe there's an argument for partial synchrony but this is combined with an asynchronously safe finality gadget that gives accountable safety so I'm sure you've seen this sort of model before most notably aetherium is trying to use this kind of model as well so you have some kind of block production system coupled with Casper FFG so that's not how Casper CBC works but that's how he theorem 2.0 is research talks have been pointing to so far so we're adopting this similar kind of design namely because it gives sort of the best of both worlds what you have with this kind of eventually safe block production is you can produce blocks really fast and relatively fast you know once every couple of seconds or so or maybe a bit faster than that even and under good network conditions that's fine under non adversarial conditions that's fine whereas traditional Byzantine fault tolerant consensus that's not probabilistic has to do a lot of work you're sort of optimized for the worst case you're jumping straight ahead to like let's get 2/3 and then let's get 2/3 again to vote on the fact that they saw 2/3 consensus that's a lot of messages to go around that's a lot of overhead before something like adding a block to the chain so if you run a finality gadget which is inspired by these traditional consensus algorithms in the background you can get the best of both worlds you're adding blocks quickly which are optimistically correct and optimistically final in the background you have that pure academic non probabilistic actually final safety so that's the design methodology we've gone into from a very high level so the technologies we've come up with are called babe and Grandpa so babe is it's four new blocks and grandpa's for the old blocks that makes sense from the names so I'll talk first about grandpa because it's a bit easier to slot in exactly what we need from the block production algorithm if I talk about grandpa first so grandpa it's it's an acronym a lot of people don't know that it's a big acronym it stands for go space recursive ancestor deriving prefix agreement that's that's a picture of grandpa so grandpa is a round based two-phase commit finality gadgets so that's you know two-phase commit is what we've seen from pbft that was their big innovation you you get two-thirds sign off and then you get two-thirds sign off again so we do that it's a lot like tenorman but instead of voting on a single block everybody votes on what's the best chain that they've seen more or less in practice what we do is what is the block 3/4 of the way from the last finalized block to the head of the chain and that means that it's more likely that the chains overlap with what your peers have seen and the way that we make this safe because what you need the reason for rounds in these round based consensus systems is basically after you've done that first phase of 2/3 of people sign off on something there's a chance that it might have been committed actually finalized but there's also a chance it might not have been so what rounds are for and what you really need that or is a way to sort of back out of your votes so the way that grandpa works is you know we've got these votes on chains how do you back out of a vote on a chain the answer is that we use something called an estimate so while you're collecting all the votes that people have made on chains so you know one guy is voting on chain a another guy is voting on chain B and you have this meeting in the middle you want to finalize that but there might be you know some blocks that are higher that might be finalized in some books that are lower that might be finalized depending on where the common ancestor actually ends up being we use an estimator to figure out what's the highest block that could have been finalized what could potentially based on more votes that I see actually get a supermajority so once this estimate starts to move backwards that's when we can actually move on to the next round and start to finalize something so that's sort of a picture of expected outcome of grandpa like you see there's a few Forks here so one node thinks that the fork in the middle is his best chain the other nodes haven't seen that chain they've seen some different chains but the fact is that they have all seen Block C in the middle there so that block is a common ancestor of all of these these nodes as change so they can actually finalize that so that's pretty nice because you can actually the property that we get here is that you've actually finalized the thing that everybody agrees upon the way that we like to think about it is this this is what bitcoins common prefix agreement is supposed to do if you would chop off the last six blocks say of the chain they the nodes are all supposed to have a common prefix so that's probabilistic in bitcoins case in our case it's deterministic and accountable safe so I'll just go through the process of what Grandpa voters are actually doing in a specific round we'll call that round R that's a round number so it is ghost based finality gadgets so at the heart of this this thing is the two-thirds ghost function it essentially takes a set of votes which might be pre votes or pre commits and it tells us what's the highest block that has a supermajority that's two thirds plus one support so that's sort of the heart of our consensus algorithm then here's the formal definition of the estimator which I talked about before so we've got a voter's estimate of what might have been finalized in around R and that's given by the last block in the chain that has the the head of that chain is the the two-thirds ghost of the Prevot two of that round where it's possible that the commits not that we've seen those commits but that there could maybe be commits that come in later including equivocations which are like double votes like what if I vote on two two chains some peers might see one of those votes first and some peers might see other those votes so we actually have to account for those in the estimator and essentially we're just accounting for you know what votes could we see that might make something finalized that's that's what the estimator is so yeah we've got this ghost function that gives us the best chain the super majority set and we've got this estimate in more plain English terms there's also this parameter T which is an expected time for messages to travel through the gossip network but this is at least partially synchronously live it's not asynchronously live which means that under real like bad network conditions we've got an adversary that's dropping messages that never get delivered ever and it's it's arbitrarily bad you don't have liveness you do have safety so if this T parameter actually is way lower than it does take for messages to go through the gossip network that's completely fine but it does guide our our voting times so the cycle goes something like this you start around you wait two times this time T you cast your pre vote you wait for time to T to pass again you or if the round is complete a ball that you've seen enough pre commits already that happens when you're a little bit behind everybody else you cast your own pre-commit then you wait for the round to be complete Abul if it's not already and then you start a new round so grandpa voters are just always moving this cycle of round to round to round and they just vote forever basically so it is possible for grandpa voters to end up on different rounds but only really one or so rounds apart once you've got enough voters that are stuck behind so you won't end up with progress happening unless two-thirds plus one of voters are all in the same round just by nature of the fact that that's the quorum required for consensus so the first thing that happens when you start is that the primary broadcasts the estimate of the last round the primary is like just an arbitrary node that's you can do this round-robin it doesn't really matter we only use this for liveness to break a certain kind of vote splitting attack so there's a special adversarial attack where you can sort of split all the audence nodes between one option another the reason we use the primary is to break that that's necessary because of it's sort of a loophole that lets us get partial asynchronous liveness you can't get full asynchronous liveness without some kind of randomness so this is sort of like almost like that but it doesn't quite get us to asynchronous liveness the real important part is the pre voting so we do that after waiting a certain amount of time we vote on the best chain containing the last estimate or whatever block we got from the primary and then we'll Pat cast a pre commit once one of those conditions holds so that's the voting loop in a bit more depth we for primary that lected round-robin style they shoot out whatever block they think might have been finalized everybody else is voting on whatever they think the best chain is and then you get like a agreement on on what that is and the last part is a commit message so this is not critical for consensus but it is very useful for catching up so once you've seen two F plus one pre commits from a from a round of consensus you can combine those together into a commit message was essentially a digest of what has happened in that entire round so those can actually end up being really compact this is a tool that we use in a few places BLS multi signatures essentially that lets us take a bunch of votes even on different values different messages and combine those all into one signature so those commit messages can actually get super super compact so to talk a bit about liveness so liveness I guess I didn't go over this before but liveness is the property that we continue to finalize something right so this is a finality gadget it doesn't actually create blocks so clearly we're dependent on some kind of block production system to actually achieve liveness if nobody's adding blocks to the chain we can never finalize anything new so with Grandpa we can go sort of one step further than Casper FFG Casper FFG so shows plausible liveness which is not exactly liveness is just like yeah probably we can finalize something with Grandpa we actually managed to nail down the exact properties that a block production system has to have in order for us to achieve liveness so the the constraints are pretty simple actually for the block production system you basically just have to build on top of the best finalized block or show that eventually it will build a chain extending that and then you can finalize that so that's that's pretty simple and I'll go into exactly how we are achieving that blog production system in the next section but first I'll talk a bit about accountable safety so this is the property that actually lets us build proof of stake on top of this consensus algorithm so the way that I like to think about consensus algorithms in proof of stake is that you sort of have two parts you have the consensus which depends on an honest majority and then you have some kind of economic games that actually keep rational actors honest that align their incentives the most common way to do that is with flashing so in a regular honest majority consensus engine if you would have a fault but you wouldn't have a fault because you have an honest majority in a rational consensus system you can have false but you need to be able to detect them so we need to be able to actually figure out who it was that misbehaved and how they did it so this is a bit complicated because grandpa is pretty complicated but basically what it boils down to is we've come up with a synchronous procedure for basically you track down validators who have appeared to have finalized something conflicting and two chains and you sort of beat them over at the head with queries until you figure out who did what wrong so the two kinds of queries are let's let's assume that we have two blocks right so B and B - they're on two different chains they you know one is not a descendant of the other they've both been finalized so B was finalized in round R b2 was finalized in round 2 and round 2 came after round R so the first query is a bit more complicated so I'll break it down why was the estimate of round 2 - 1 not greater than B not a child of B or including B when you voted for B - in R - the reason that this you should always be able to answer this if you're honest because the voting rule for a round is that one you're only voting when that estimate starts to move backwards and R 2 is after R 1 so B should have been contained inside that estimate or sorry actually it doesn't have anything to do with the vote moving backwards that's a bit later on it has to do with the estimate always being an over estimate so it should have always contained B if it was possible to finalize B so the other query is a lot easier it's which promotes have you seen for round R so as long as you're keeping those around for reasonable out of time you should always be able to answer these so what you would do is you would start in R 2 and you would just work backwards and you quiz all the nodes and eventually you'll start to see contradictions you'll see equivocations you'll see nodes that are double voting you'll see notes that are voting without justification that can't answer those two queries honestly and that lets you slash them you can do that in in all histories so in practice the way that we're going to do this is to issue queries on chains so somebody notes oh this this block was finalized on this other chain that's not a descendant of our finalized block and isn't in our finalized blockchain so we can just dispatch this on chain signal that says hey grant validators what's going on tell us tell us what you did and from that we can begin this recursive approach to figure out actually who did something wrong so that's the theory the practical considerations I think that this is this is a super interesting section as far as I know we're the first team this is I guess this consensus algorithm is in the category of like Kasper CBC it's where you have chain based consensus algorithms and as far as I know we're the the first implementation team to actually implement one of these consensus algorithms that operates on chains instead of on blocks so we got to be made aware of these engineering issues well before anyone else was and the truth is that synchronization of many different chains when you only end up finalizing one when those chains are short that's easy when they're long that's more difficult so one thing that's important to consider is ok if we have a long network partition and we end up with two forks that are a million blocks long sure in theory you can finalize that when that partition resolves but you'd have to sink both Forks which are a million blocks long when you run to things like state pruning or just plain old availability and peer set cultivation that's actually pretty tricky so the way that we we actually handle this is an extension of Grandpa where when you vote on a block you cast log 2 of n votes so if I vote on block 1 million I'm also casting a same block for block 500,000 to that same chain and 250,000 and 125,000 and so on until I get back to you know some reasonable thresholds like 64 128 blocks and I just cast all of those books votes together and that means that you know when you have these long Forks in the network partition has eventually resolves you're only going to finalize one of those chains so really the only vote that you need to actually figure out the common ancestor is of on the first block in the side of the fork that didn't get finalized so that's essentially what we do you know if you're not going to finalize both Forks there's no reason that all voters should need to download a million blocks from each side of the fork that makes this actually practical so now I'll get into the next section of the talk which is about babe so that's blind assignment for blockchain selection actually Jeff is in the audience who did a lot of the design work on this so track him down after he's gonna teach you about crypto and so this is inspired by Ouroboros Prowse there's a lot to draw on that so Ouroboros Prowse is essentially sampling people using a vrf in proportion to the amount of steak that they hold assigning them to slots of time having them build a block in that slot and essentially proving safety on top of that so the nice thing about building on top of this work is that they've done a high degree of formal analysis of their protocol which means that we can build on top of those security proofs but we also address some of the other practical issues that you encounter when implementing consensus protocols and deploying them in the real world so one question we were trying to answer was how do we maintain block production liveness with a large set of low staked producers like what if we have 3,000 or 5,000 or 10,000 people whose job it is to produce blocks they're all really low staked you're supposed to have a block every four seconds but I mean if they're really lowly staked then probably they might just skip their slots and with those traditional vrf based consensus engines like Ouroboros it's hard to tell when somebody has skipped their pro their slot because what they're supposed to do is just publish a proof that they're vrf key actually just produced a value below some some threshold that gave them the slot so if they don't publish this vrf signature you don't know that that slot was actually assigned to them so the way that we've approached the problem is a bit backwards so proofs of not winning you have a fixed global rate parameter and some random value R sub e for every epoch e this factors into the the vrf that we use so at the beginning of each epoch every block authorship node is supposed to use a system of nested or recursive V ahrefs to figure out exactly when their slot is that they're actually going to author something so I know 24 hours or 48 hours in advance I have to be online at this time so the good news is you know ahead of time when you're supposed to be online to issue your block at the same time for all the nodes that don't issue their blocks in that time period they can prove that they were not assigned a slot by their vrf which means that you can actually start to detect which block producers are offline and prune that set another problem that we've addressed is relative time so the way that we're thinking about babe is that in the beginning probably we're not going to have this massive set of block producers we are focusing on this research question in the beginning we're going to be running block production with the same set the same validator set as is running grandpa further on we're going to separate them so if you're using the same set as you do for grant but that's a compact very highly staked set of nodes so you don't have to worry about them being offline that much then the main consideration that we try to address is relative time so what baby comes then is is sort of a tweak of Ouroboros with just with relative time in that situation so what relative time is is this idea that clock drift is a huge practical problem for slot place slot base block production a lot of consensus papers especially the ones in this sort of sphere of slot base block production they'll say okay assume all nodes have a clock that's synchronized to the global time in practice that doesn't really happen clocks drift they get out of sync they're not all sync to the same NTP server if they would be that would be a massive vulnerability there are attacks on all kinds of when we were looking into this issue we could see you know if enough people are synced to the same NTP server you can break a lot of the security proofs that have been done on on some of these consensus protocols and basically what clock drift boils down to is you might have two notes or you know partitions of know it's like a1 and a2 where they both have different views of what's lauded is at different times and that can break down the assumptions that you have on when something is finalized or when something is is safe so that that's coming from a paper it's pretty good paper about applying proof of stake the CIP theorem to some permission blockchain algorithms so what we do instead of that is we know what the expected slot time is going to be but we use a relative time method where you know instead of just saying oh the time stamp is 5 and the time per slot is 4 so it must be slot 2 we just say well it's been the last the highest slot message that I saw was slot 5 and it's been 4 seconds so it's probably around slot 3 but you average this out over a period of slots so you can figure out this larger interval where the slot actually starts and ends so a node when joining the network is doing exactly that so they watch for incoming messages that say okay I'm signing a block for slot 10 I'm signing a block for block a slot 11 I'm signing a block for block a slot 13 and then they can basically do this where they know that okay slot 1 is supposed to be 5 T behind slot 6 slot 3 is supposed to be 3 T behind slot 6 and they could figure out this rough time interval that includes slot 6 so then they take the beginning of that time interval add T to it take the end of that time interval add T to it and then they can compute overestimating endpoints of that time interval and that means that we don't have to worry about this problem of clock drift so the last thing I'll talk about is data availability so what we're doing in polkadot is this is this is sort of how we all tie it together so what we're doing in polkadot is we've got this system of many chains and those state transitions of those chains are being validated by subcommittees of the validators of polka dot they're being attested to by those committees and they're going to be put on chain so our overall assumption of honesty and dishonesty is that less than one-third is dishonest but if you randomly sample that you can obviously end up with nodes which what we're committees which are majority or fully dishonest so what do we do when they've committed to saying a state-transition with this block data proof that's the data that's supposed to prove that the state-transition is valid they've committed to that hash of the data but that data either doesn't exist or isn't good so data availability is a big problem in in polkadot it's also a big problem in a theorem 2.0 or any other sort of sharded or partition blockchain architecture so we need to keep that block data available what we do in polkadot is we have n validators and we assume that F of them are malicious with N equals 3 F plus 1 and we have this block data so for every single pair of chain candidate in every single block we do an erasure coding with n pieces so one piece for every single validator where any F plus one of those pieces so that's one more than the number of malicious validators can be used to reconstruct that block data and that block data in turn can be used to reevaluate the state transition function and see if that state transition was actually good so obviously if the block data it doesn't exist you can't create the erasure coding of it so the question is really how do we figure out and slash somebody if it doesn't exist what we are doing in practice for the erasure coding is a reed-solomon code over the Galois field 2 to the 8th squared which is the same as 2 to the 16 but that's how we're implementing it is with to 256 element tables instead of a bigger one it turned out to be more efficient in practice but we are looking into repairable fountain codes and Raptor codes and that sort of thing as well so each piece of the eraser coating gets distributed to one corresponding validator the amount of space that that takes up is proportional to the number of Perich Eanes times three because each erasure coding is roughly three times as big as the amount of data that was actually in the block tail right so in the cases where the pieces aren't available we run an attestation game so somebody says this piece isn't available and we use some kind of non influenceable randomness to select which validators we start to ask about this the reason being that we don't want the adversary to know well in advance who's going to be asked and that means that they can't be corrupted ahead of time as easily so essentially what we do is we pass around a petition and this petition is a bit field so the bit field has one bit per validator and if they think that that vowed that piece of data isn't available they'll add their bit to the bit field and they'll sign a message that that there with with just their bits set then you can pass around a multi signature that proves all of the bits in the bit field so the petition gets super super compact with this once you have 2/3 plus 1 a validator signing off on a petition that a piece of data isn't available you can pass this in and and slash people for it the people that you would want to slash are those who were assigned to the para chain committee when that piece of data was meant to be evaluated or to have existed so the way that we tied this all together with babe and Grandpa is custom voting rules essentially we want this guarantee that or a rough guarantee this is not a perfect guarantee but this is a heuristic we guide our block production by saying block producers should not produce blocks unless for every block in that chain ignoring a few recent blocks just because of latency if for every block in that chain you have received one piece of the availability erasure coding so that means that the longest chain because block producers will tend to only build on chains where the block date is actually available that means that the longest chain will tend to be available this is you know it's not a it doesn't technically at protect you from any more adversarial attacks but it's a nice heuristic that makes synchronization much more reliable and similarly we have a custom voting rule in Grandpa as well except it's exactly the same except grandpa voters don't ignore the recent blocks they only vote on chains where they've seen a piece of the availability erasure coding for every block in that chain that means that if you actually do have this onerous majority you won't finalize something where the data actually isn't available whereas if you do have this Oh F plus one or more malicious if you have this super Byzantine fault condition it can also be be gamed and you would have to do a bigger fallback either by a governance as you would often have to do in case of a safety violation or via yeah automated chain restarts are similar and that concludes it so I'll be taking questions thank you very much [Applause] anyone [Applause]