Sharded Security Model of Polkadot

Transcript

all right now we're actually going to start so I'm gonna go I end of fast because the last time I did this it took 23 minutes and I apparently have 20 minutes so interrupt me and stop me with questions if you have them going to talk about cross yard validation in polka dots so yeah really quick like what is a single charge just like some terminology we'll be throwing around here we have the relay chain just like the main central chain of polka dot if you will and then a group of validators and then there's these pair of chains that have Co laters I kind of stick with a pair of

chains and we'll talk about later but like about it is kind of roam around and talk to all the pair of chains well the collator stay like specific to a single pair of chain so yeah like one thing that's interesting about these pair of chains is like they're all charged and polka dot and we've talked a lot about like heterogeneous chars and unlike any to has like homogeneous chars where they all expose like an e wasum api so in polka dot every shard has its own state just like every charge aetherium 2.0 might but we have every chart has its own abstract state transition function and so what we mean by this is that like

they're sharing validation logic with the relay chain a really simple way would be like the all of the pair of chains are light client so the relay chain and the relay chain is a light client to all the pair of chains and so when we think about are these stars heterogeneous or homogeneous it depends on like which side you look at them from if you're looking from the outside all of these pair of chains look different they all have their own API their own runtime so they can have like all these modules different configurations of these modules they can have their own custom modules and so every pair of chain looks different from a user perspective but if you're like on the inside of polka dot like if you're in the relay chain from the inside looking out at all these different pair

of chains they actually all looked the same because one of the requirements of being a pair of chain is that you have to be able to compile your your runtime to have assembly and so basically like as part of the interface we provide or like the tools we provide everything gets compiled down to a single execute block function and so from the inside of polka dot all you see is just like you know a hundred pair of chains and they all just have an execute block function and so from the inside out it's actually a header or a homogeneous system and then from the outside in its heterogeneous so we were talking about like how we start validating this data everything kind of starts with the co-leaders on the pair

of chains so we're gonna take some data from a pair of chain and of course like the collator Zonta para tree and they're full nodes on their pair of chain they have access to the full state and we want to be able to validate this from polka dot and then make it verifiable by anybody else in polka dot even if they're not a full node on this particular pair of chain so the co-leaders are they're the ones who are going to like propose the next block for for their pair of chain so they're kind of be like validators or miners in another system where they're kind of the ones to assemble block and it's up to the parrot aims logic to decide how they select these these collator so we kind of break consensus into two roles like

part of consensus is deciding who's the next block author part of consensus is deciding which chain is actually final and so in in polka dot the method of deciding which chain is final is like whatever makes it into the relay chain but you can decide on your own or each pair changes size on its own how it wants to select collator so you could use proof-of-work to decide who has to propose the next block they just have to build that block on the chain that has already been finalized by poke it up so then we need to actually like hook up the co-leaders and validators so we're going to UM shuffle and so one of the things we want to want to do with polka dot is not require a lot of Auditors for

each charge so we Eames do this with like ten validators per shard and so we're going to shuffle them around because ten is a rather low number and if they just kind of stick around like the same group of ten all the time it would be quite easy to collude so we have babe which is our block production algorithm for the relay chain it uses a randomness beacon and so we already have this randomness beacon going on and we just use it to assign the validators to para Shan so this happens every block it completely reshuffles and so the validators and co-leaders have to go find each other and I think we're kind of working out what's the best way to do that it could be like the validators find out which parity and they're going

to and then they have to go look up some like entry nodes into that pair of chain and discover the network there the other way to do it would be like to kind of tell the pair of Shane's what the valid or assignments are and then all of the co-leaders have access to the DHT of the relay chain so they could kind of like go find their appropriate validators I don't think we've implemented it or really know which one of those were going to do but yeah one way or another co-leader outages will form connections and then once they have this little the kind of this subgroup now like all the coders on a pair of chain and ten validators from the relay chain who get assigned there and so these validators are like I said before they're like clients to this pair of chain so they

kind of know like the the previous headers they know the current state route of that pair of chain and so at this point one of the co-leaders whoever kind of however you select it is going to send a proof of validity to the validators and so just to quick like rundown on approval idit ii as this like completely new to anybody here okay so that's a state tree so approve of validity we're basically going to take the perishing block with a list of state transition to nuts and then just like a prune state tree so only the stuff that has actually been updated the other stuff we can just kind of leave the the leaves and so one of the co-leaders are going to send this big piece of

information to the validators and this is what they'll actually use they have the previous state routes they can compute the new state tree using just the updated stuff with this block and they can actually validate that this is a correct state transition given that they have this execute block function and webassembly so yeah it's just to make this more concrete there might be like a thousand validators and a hundred pair of chains and this is all happening in parallel so you could have like a hundred pair of chains and then like each cluster is doing this at the same time so you've had like a hundred of these proofs of validity none of this is good in gossips around the entire network yet this is just kind of staying within this like within these groups of tens within these groups of ten and they're gonna gossip

this stuff around like all ten voters are gonna see this privada tea and then once more than 50% of the validators and that group of ten agree that it's valid then they can move on to like start getting this into the real a chain so one problem with the approval is that it's really big and you don't really know how big it's going to be for each pair chain and it's kind of like dependent on the pair of chain and what block because you could have a block with no state transitions at all it could just be like an empty block or you could have a very big one and so these proof proof solidity kind of vary a lot based on based on what happened in that exchange so in order to get stuff into the real a chain like we don't want some

activity on a pair of chain to like slow down the activity or like clog up the network for other pair of chains so we really want something that's like a constant size and so we construct this candidate receipts and basically everything in here is a fixed size like a pair of chain ID a collator ID these can be like a you 16 or you 32 everything else is like a hash or milk merkel roots yeah like okay so yeah patch of the block state routes I think like the two interesting ones in here are the Merkel root of the erasure coding which I'm gonna cover next and then the Merkel roots of any outgoing messages we could do like a nice digression into the cross chain

message passing but the really short story is that when when a chain executes the block and almost a sense of messages to other chains it's going to have like an egress of messages so it might have like ten messages it wants to send it's gonna take the hash of all those messages Maiko Merkel read Merkle tree out of it and then it'll actually pass those messages directly like based on like full nodes or connections between the pair of chains outside of the real a chain and it's only going to put like a merkel root of this egress into the actual real a chain so so if the relighting doesn't act as a bottleneck to actually passing messages around so now the erasure coding just the fun part so the validator is most group of ten are going

to create an erasure coding for this proof ability and so what an erasure coding is is it's like you take some information and you break it up into a bunch of smaller chunks such that like some fraction of the chunks could actually reconstruct the entire message so you can actually with some like math magic make this any fraction so you could say like you know with 10% of the chunks you could reconstruct this message those chunks are going to be pretty big but the cool thing is let's you just pick like you know any 10% of them and so with polka dot we use greater than one-third this kind of goes along with normal BFT assumptions that like less than one-third of your valid error set is malicious and so we break

these racial coding cheong greater or we break these POV blocks into an erasure coding and distribute them around network so if we have a thousand validators there's going to be a thousand chunks each monitor gets its own chunk and you need three hundred and thirty four of them to reconstruct it and so we take all of these chunks again we make another miracle tree and then that's what goes into this the merkel root of that is what goes into this candidate receipts so once this group of ten validators has done that then now they have like they have like one candidate receipts and then they have a thousand erasure coding chunks and they're just going to start like sending those out over the network so like every

validator in that work will have a chunk assigned to it and then they all get the same candidate receipt and so you start like sending this stuff out to everybody and so eventually for every candidate receipts every validator should have like their unique chunk of the erasure coding and then a candidate receipts that for that pair of chain block and so now we're kind of moving like outside of the pair of chain land into the relay chain because we've started to and now we're not just in like this little like cluster of 10 voters they've started to send those parroting information out to everybody and so the voters are going to start constructing the real 18 blocks with the candidate receipts so that's what's actually going

into a relay chain block and so besides like a normal priority like you know transactions in a ball chain and they get prioritize based on like their fee or some other method of like classifying their importance and so in order to build a real 18 block with a cannon receipts you have to say like okay well there's already I'm building on a chain that has a parents to this candidate receipt in it and I also have a chunk that goes along with this candidate receipts because it would be possible to have a candidate receipt but not your chunk because like the Canada receipts get gossip through Network whereas the chunks have to go like find their specific validator so it would be

possible that like I send stuff out the one person I'm like you know he just like sends on the candidate receipt to a bunch of other people and they actually get their candidate receipt there before they've gotten their chunk so in that case they couldn't actually like if they were selected as the next real a chain of author they wouldn't really be allowed to put that candidate receipts into the block unless they have their chunk and they can and will be challenged on that in the future so before we actually make this block final in the relay chain we need to make sure that like the voters actually receive their chunks that they save them and that the blocks are valid because we still don't really trust this group of ten validators even though it's pretty small like people run multiple

validators and it's not out of the question that like if you're running twenty validators you just happened to get you know ten of them land on a chain at the same time so we still want to kind of double check that so now that like now that this candidate receives in a block the coders come back and so well first like the vow deters if a Wouter does get a candidate receipt but it doesn't have an erasure coding for it then it kind of waits like a certain grace period but after that it'll start to flag this and say like hey I got this candidate receipt but I never got I never got an eraser coating for it and if a lot of other validators start to raise that same

concern then they just discard that Canada at receipt and like it's gone but assuming that the can it receipts or that the chunks did go out the co-leader start asking the voters for the chunks that correspond to their chain and so they just like they go out to all validators don't start asking like hey I saw that this candidate receipts got into the chain can you send me a razor cutting chunk so that I can reconstruct that proof of validity and execute it and so the reason that they want to do this is because there could be like a collator attack so if you think of like a collator who it's his slot to produce a block creates a block and then immediately after submitting those proof

of validity just goes offline just like unplugs disappears and then the validator is just kind of like discards all this proof ability stuff they're like yeah I checked it out it's good now you have a problem where you have like a finalized new state route of this pair of chain which is all that's really going into the relay chain but the collator is I'm like the full nodes on that chain don't actually have the state transition to get to that proper state route and so their chain is basically stuck like they can never make another valid state transition so they need to make sure that they can actually reconstruct any block that's going out into the network and so yeah they just asked for it back and then fishermen

also exists on a pair of chains and so they're also going to like ask for the chunks of this erasure coating reconstruct it they're actually going to execute it and report invalidity and so co-leaders are kind of in an excellent position to be fishermen because they're already asking for this block back they might as well just execute it the only like the nuance here would be that like a fisherman has to have some stake of dots because otherwise you could just spam the network and say everything's invalid whereas like by staking some dots on it then you can actually slash them for that whereas collator is like a pair of chain has a slot in the reel a chain just based on like winning this auction and

being part of polkadot so co-leaders don't really have to have dots but if a coder wants to have a few dots then I could quite easily be a fisherman also and now we do some secondary checks so validators are also going to reconstruct these blocks and this is where we like really get away with having ten validators per shard instead of like over 200 so we're just going to like using this random of speaking again just randomly select some validators once once the cannon receives on the chain we're going to randomly select some powders to request it reconstruct it and verify it and then so we have this like ghost based finalization algorithm

grandpa which again don't have time to go into but it's voting on chains not blocks and so we can finalize like big chunks of a chain at a time versus like one block at a time and so until there's been enough reports that like enough powders have done secondary checks on this block then they can't even vote for it in grandpa so I kind of with a vote when you do like a pre vote or pre-commit in a round of grandpa you have to kind of attest to the fact that you've seen enough okay yeah so yeah so like there's just some like statistical analysis that if you require more than 13 check so if you're just like randomly

grabbing 13 validators around the network it would take more than 50 years in order to have like a successful attack where you like stuck something by that was actually invalid and so this kind of voting method gives us three zones to the relay chain so there's like the fishing zone when something first goes in and people are kind of like asking to reconstruct these candidate receipts are asking to reconstruct the proof so validity and verifying them sending out any like at the stations or reports and then once they've had enough secondary checks then the validators can actually start voting on them for finalization and then once they finalize then they're in the finalized chain so I think this is my last one yeah so I'm

within so just like a lot of the it's like philosophy and motivation that drives us is that in order to scale the system we want to push as much of the information to the edges as possible so block production there's one like it's not on the critical path for finality so like oops like in this we separate the actual production of a box from the finality and this doesn't like if there is a case like so we expect the whole like from candidate received actually being finalized thing to take about a minute but if there is like some hang-up where people start reporting like some doubt or say that this is invalid and some say that it's valid those keep building up

these asset stations until they get to more than one third of the validator set and that can add like a delay to this finalization but by not tying the block production like not hanging up block production we're not stalling the network here anything that goes on the relay chain whether it's like block information or cross chain message passing is always constant sighs so we shouldn't be just like putting actual transaction data into the relay chain co-leaders and fishermen increases the number of pair of chains so all the coders and fishermen are actually nodes on pair of chains not the relay chain so as we increase the number of shards in the network it's not increasing the load on the validators on the network it's

we're getting these extra checks kind of like not for free but along with the scaling like as you add these jars you're also getting these people who are checking along with it cross chain message processing like I mentioned before all the messages are kind of going note to note outside of the relay chain and not really like passing through that as a bottlenecks just state routes that are going in there and then saying like polka dot 2.0 we wanted as hermit relay chain thing where like polka dot basically becomes a pair of chain of itself and so right now we have these candidate receipt things but also you know there's like balance transfers and staking and governance and all these other kind of like first-class transactions and polka dot that are going in polka dot blocks and we want to

pull those all into parish chains so like a governance parish chain polka dot balances parish chain staking para chain and just in that case the relay chain would explicitly hold candidate receipts and nothing else so that would give us room to scale to quite a bit more just frees up a lot of block and state space so yeah I made it in time so now I can do questions yeah you mentioned quickly the that develop they just need to revalidate or we construct Kalidas inputs and wouldn't it be possible to use ZK snarks I know Koda

recently mentioned that reconstruction be unnecessary for example they use an analogy from the famous movie where a computer is computing for ages to get the result of 42 as the answer for everything but how do you prove actually that you saw the 42 in without actually we computing everything today big a bigger population to speak and have you looked into the key snacks as a potential solution for not needing to reconstruct a POVs oh yeah so I that's a big push right now in our research team is like looking at more zero knowledge research and then also like along with the zero knowledge research I guess I could have mentioned also I was like just networking stuff that like a lot of

this stuff pushes the load into the network versus like and like you're trying to like target I started like going on top of your question so yes like we are looking into zero knowledge and I think like I don't want to get this wrong but I think we just partnered with matter labs for like some of their like ZK research but don't quote me on that 100% yeah and then I guess like the like the additional scaling thing on top of zero knowledge proof like the networking stuff is that like a lot of the stuff of like finding like ok like instead of using a gossip network we're just sending stuff out to everybody like we have like these can--it receipt so I kind of targeted or the the chunks are like targeted for certain people more like certain people are trying to

reconstruct these blocks and so yeah I like zero knowledge proof and networking or like our two big research push pushes that like how can we do exactly what you just said and then also like move the information from being like in the chain to like how like being more efficient about how we pass it around the network all right its next person [Applause]