Polkadot Shard Validation – Joe Petrowski

yeah so I'm going to talk about validity and availability guarantees of poccadot shards so just to get started we have a single shard here so there's like the relay chain and then we call most of these shards pair of chains and then we have these other guys monitors and co-leaders we're gonna take part in making this happen so each shard and in polkadot has its own state and an abstract state transition function so they'll have their own state but they're sharing state and validation logic with the relay chain and so we've talked a lot about like heterogeneous versus homogeneous shards and this actually depends on like what angle you're looking at it from so like one of the interfaces the polka dot is that you have to be able to compile your runtime to webassembly and so we have like a web assembly interpreter and a compiler within the relay chain clients and so every shard if you're looking at it from the perspective of a relay chain it's just presenting a single execute block function looks like an abstract blob of some runtime behind it but if you're looking from the outside in then each shard can look different so you can put in your own modules like balances democracy social recovery or like a smart contracting environment or just create your own and so whether or not it's like homogeneous or heterogeneous it really depends like we're looking at the shard from so like from the inside all those hard look the same it's just this blob has like a single execute block function so actually like getting these blocks to finalization it starts out with the co-leaders so pair of chains have a set of nodes that are called co-leaders and these aren't really consensus related so you don't really need to have like any kind of BFT considerations or anything as long as you have at least one collator you're basically good to go and it's up to you to decide like how you choose these colliders so you could have like proof of stake or proof Authority or proof of work and so this it doesn't really have anything to do with finalization yet this is really just choosing like who has the right to produce the next block and so like if you think of it like a pure proof work chain like Bitcoin you know the proof of work is actually like who gets to add the next blocks of the chain whereas the finality is like which chain is the longest one so as far as colliders reckon concerned they're just proposing blocks for their pair of chain but it's up to the real a chain to actually finalize them so we actually like match these colliders with founders and we're gonna do that randomly so we only have like a thousand volunteers and polka-dot and say a hundred pair of chains we're gonna actually do this every single block is just based on a vrf we're going to randomly assign validators to pair of chains so if we have like this amount it would be about ten validators per pair of chain and so doesn't need to find each other we actually haven't like finalized how this is gonna happen yet but there's kind of two ways you could do it one is that all the coders have access to the DHT of the real 18 and can like find these valid errs or you kind of make the pair of chains have like a entry node or like a boot node so that Valladares once they get their pair of chain assignments they can just go like start making the connections there and then once those connections are established then the coders are going to send a proof of validity to the doubters so let's go into that like just a really quick overview like you have a state tree just all the most storage entries get hashed and then they kind of just get concatenated and hashed all the way up to a single state roots and so this is just a normal like state tree on its own so but we have this thing where like these routers got randomly assigns to one of those shards but of course like they can't be full nodes on every single shard they're basically like clients so on the all of the pair of chains they're acting as light clients to the relay chain and full nodes on their own pair of chain and then the relay chain is a full node to itself but it's has light clients to all the parish chains so basically these volunteers come along to a pair of chain and there a light client so they know it like the latest state route is and the last header of this chain is but they don't have access to the full state tree so in order to validate this block that they're gonna get from the pair of chain they need a little bit extra info so they're gonna take like a prune state tree that only has the modified balances or like the modified storage injuries and so it's that in this example from like the last one I only changed you know I like Louise sent 50 tokens to Bend so those balance has changed and then a referendum got added to the democracy like storage item we have this function called initialize that basically runs on at the beginning of every block so like in the democracy module this might check like are there any proposals that are up for a vote now and so in this example there was and so it got bumped into this referendum count and so the entries that don't get modified and we can just leave like the hash value just constant size and then so we're just passing like a block and this modified state tree and so this is all the information you need as a light client to be able to validate that this block is valid so just to like kind of put everything together because like that's just one pair of chain and this is all happening kind of in parallel so like this is a lot of information here and we're not gonna like be gossiping this all around polka dot you're going to have this in every single pair of chain within this like cluster of ten valid or so this will be unique for every pair of chain and then this just gets gossiped around like a subgroup of ten and it's not really gonna leave there for still a little while so yeah just like to back up a little bit like we could have a thousand Valladares with a hundred pair of chains ten dollars per pair of chain each pair of chain is submitted proof of validity and then they're gossiping that around that group and then once more than fifty percent of that group agrees that the state-transition is valid then they start moving on to the next stage which is to construct a candidate receipts and so like approve ability is really big and we want something that has constant size because I approve ability that's just modifies like one storage item that might not be that big but we really don't want the size of these candidate receipts that are going into the relay chain block to vary based on whatever state transition happened in the pair of chain we want them to just be the same no matter what happened no matter how big that state transition was so we're gonna put together those candidate receipts the main I'm not gonna like with stuff every single thing here because you guys can read but like the main thing here is that everything in this list is constant size so like the pair of chain ID and collator ID this might be like a you 32 signature is constant size everything else is like a hash or merkel root and so this stuff just kind of gets like concatenated together into a single candidate receipts and no matter what happened in this block this is always gonna be the same size and so the next thing I'm gonna go over is the erasure coding part so yeah before we move on like you need to create this merkel root of the POVs erasure coding and so we're gonna do this this is kind of how we get away with having only $10 per shard so like eath - I think it needs like a minimum of $111 per shard but like 256 to get about to get the finalization within one époque and we're kind of here saying like hey we can do this with $10 per shard without worrying about like collusion or anything and this is like this is how we do it right here's the erasure coding so overall I can erasure coding is a way of taking some message and breaking it up into a bunch of little pieces such that some subset of those pieces can reconstruct the message and you can kind of choose the subset fraction so in polka dot we set it to one-third because this kind of goes along with like BFT assumptions that less than one-third of your validator set is Byzantine and so we're gonna create one chunk for each valid or polka dot and then you need at least one-third of them to reconstruct it or greater than one-third so if we have a thousand validators there he's gonna get a unique chunk and then if you get any 334 of these then you could actually reconstruct this entire POV block and so we're going to create another Merkel tree with all of the chunks of the leaves and then compute the merkel root of that and then that's what's gonna go into the candidate receipt here and so now we're gonna start like actually gossiping this stuff around the network we're going to send one chunk and the candidate receipts out to all of outers so you kind of have this like too full of items that's going to all the validators the candidate receipt is the same to everyone and then each valador is getting a unique unique chunk of this erasure coding with it and so this stuff starts to like get thrown out all over the network and at that point we can start thinking about like how are we going to construct this block of the relay chain because now we're no longer dealing with like isolated shards anymore the stuff that starts to gossip like all over polka dots so your values are going to be receiving candidate receipts and erasure coding chunks from like all the other chars now and so they're going to store the can--it receipts in like some other part of memory and our sorry the erasure coding chunks and then the candidate receipts are going to go into the transaction queue and so when I start thinking about like okay I'm gonna put together a block for the relay chain how do they decide like which candidate receipts to put in that block so first every like Kennett receipt that are going to put in a new block it has to have a parent candidate receipts in a previous relay chain block which of course like you have the state route of a pair of chain block or the pair of chain before executing the block so you can go look this up and the author has to have a corresponding chunk for that receipt so it would be possible since like transaction queue stuff gets gossiped around the network that and then like the erasure coding chunks are actually looking for a specific validator it is possible that like somebody receives an eraser coding or receives their can--it receipts before they've received their erasure coding chunk and so if that vow deter is selected as the next block author on the relay chain they're just not going to include that came out receipt they're gonna wait until they have their corresponding chunk for that and that's gonna go along with the availability guarantees and then they'll actually don't only hold that candidate receipt for a limited amount of time and then after some number of blocks if they haven't received a rager coding chunk they're gonna kind of like send out alert that says hey we have an availability problem I got this can't receive but I never got a chunk for it and then like that period we call it the availability grace period and so if more than one third of the voters say hey I got this came out receipt but I never got an erasure coding chunk then we're just gonna like throw out that can't have receipt and it's done so these can receipts just stick around on the transaction queue for a little while until finally like everybody gets our chunks and they can go into a block so yeah now we can start talking about like once this can at receipt gets into a relay chain block how are we gonna actually get this to finality so we have to make sure that the voters actually received their cannon receipts to actually save them and that should actually say receive their original coding chunks my bad though they actually save them and then thought the blocks are valid so actually save them this has to do with availability and then that the blocks are valid that they're like valid so so at this point like we've been in like the router land for a few minutes here but now the coders are gonna come back and once they see that one of their candidate receipts is included in a relay chain block they're going to start asking random values around the network to give them their erasure coding chunks and report any of it and availability that they see and so this is like this is really important so like this is why we do the erasure coding and so you kind of imagine that like you have a a collator who wants to attack a pair of chain and he just comes in and submits a new block and it's perfectly valid block but as soon as he submits this proof of ability to the voters just turns off goes offline no are to be heard from again and then this candidate receipt goes and gets finalized by the relay chain well now this pair chain is like really out of luck because they have a finalized state route but they don't actually have the preimage they don't have like the actual state tree to compute that state route which means they could never make a valid state transition again so they're just stuck like forever and so they need to make sure that they can always get their blocks that are getting finalized back and reconstruct them so that all of their full nodes can stay current and so they're just gonna start asking for their tongues from about errors and reconstruct these blocks and if they can't then they're just going to flag this as this block is unavailable and should be thrown out and then fishermen which also exists on pair of chains they're also nodes that are going to ask for these POV blocks back but they're actually going to execute them and report if they're invalid so you can kind of see that like coders are in a really good position to also be fishermen because they're already asking for this information anyway but like an important distinction to make like if you don't want to be a fisherman co-leaders don't need to have like any kind of polka dot tokens or anything they can just deal with their pair of chain they just need to be able to send the POV blocks to the relay chain to get validated fishermen do you need to have some dots because if somebody doesn't have dots then they could just like throw out arbitrary invalidity reports and spam the chain so when you submit an invalidity report you have to kind of take some dots behind it that says like yeah I actually think this is really an invalid and if it doesn't end up getting finalized then you'd get slashed so if a coder is okay with owning some tokens then they could also be a fisherman and of course like a fisherman wouldn't even have to be like wouldn't have to have like its own pair of chain tokens if you just want to like run a full node and own dock tokens on some pair of chain then there's no reason you need to like own those tokens you could just be a fisherman because you feel like it so now we get to like the secondary checks that the values are gonna do and so the codes and fisherman's and will send alerts that like something is unavailable or invalid but ultimately it's up to the Valladares to decide like what's going to the relay chain and like they're the ones who are ultimately held responsible for it so besides these like ten-pounders that were randomly assigned to a pair of chain to actually go through the POV process we're just going to like randomly select other validators again from polka dot to construct this like ask for the razor cutting chunks reconstruct the POV block and validate it and so only after we've done enough secondary checks can one of these vouchers actually cast a boat for this block in Grandpa which is our final ization algorithm it's a Ghostface thing so like we're voting on chains and not blocks and so we can have like a long on finalized head and so I think my next okay I'll talk about that the grandpa's stuff in a second but so number of secondary checks like our analysis shows that if you have more than 13 checks then it would take more than 50 years to get a successful attack by getting like all these routers to not it's like incorrectly a test - something's validity and so if nobody reports any invalidity or unavailability it's just going to be like greater than 13 checks that you need but if some do that is going to start triggering like more checks all the way up until you gets like one-third of a valid or set so if people start flogging these as unavailable or invalid then there's just going to start requiring more secondary checks from the validators and if more than one third of the validators say that this is invalid or unavailable or but more than one-third say is valid or and available then it's going to be or like rejected or finalized and of course if more than one-third say both and we have a problem because that violates our assumptions of BFT that less than one-third of outer sat is malicious so yeah in grandpa like we're voting on chains not on individual blocks like one at a time so it kind of gives like three zones to the relay chain you have like the finalized chain which is everything that's been like finalized and then there's a grandpa voting zone where there's all past the secondary checks and you can start voting on these blocks now and then there's a fishing zone where we're still kind of waiting for these checks and reports to get done and so these like the fishing and the voting zone are kind of dynamic right like if everything's going smoothly we predict that like from the time you submit a POV block to the time it gets finalized is about one minute but if people start raising like flags on certain blocks then these zones can kind of grow or shrink as those as those reports come in so some final thoughts because I still have a few minutes like just some of the principles around this is in order to scale the system we want to push as much information to the edges as possible I'm like we don't want the relay change to be any kind of bottleneck so number one that lets us do like the having the different zones on the chain is that block production is not on the critical path for finality so like other pbft based algorithms they'll like do the block construction and finalization all as part of the same round but since we separate those are the two things we can kind of have this dynamic dynamic chain it has different zones in it and finalized like only only think is appropriate without actually slowing down the rest of the chain construction relay team information is always constant size or basically only putting like IDs and Merkle routes and state routes stuff like that in their careers and fishermen increase with a number of parish aims so like you have to do all these like availability and validity checks but as you add more pair of chains the co-leaders and fishermen exist on the pair of chains not on the relay chain so this stuff all scales with the number of pair of chains and it's not really adding pair of chains in this sense doesn't add any extra load on to the relay chain they're taking responsibility for that themselves and then cross a message passing which didn't really talk about here except that like the Merkel route of outgoing messages will go into this cabinet receipt but the way that works is that if two pair of chains share any full nodes like even if they're not valid there's a co-leaders since this message is going to the relay chain they can just pass this message via their shared full nodes doesn't even touch the validators at all and then if they don't share any full nodes then yeah the Valladares will kind of do like a push and pull model to get these messages where they need to go but the messages are still never going into the relay chain itself they're just being gossiped by the validators and then finally a hermit relay chain which is pretty cool so we talked about like pair of chains only here but of course we do have actual transactions as part of the polka dot like transfers governance staking all this stuff we actually want to move like all of that outside of the relay chain so there would be like a pair of chain for dot balances a pair of chain for staking a pair of chain for governance and so in that case the relay chain would literally just have candidate receipts of pair of chain blocks and it wouldn't have any kind of these like polka dot transactions and so like polka dot would be a pair of chain of polka dot which is pretty cool so yeah I think that's it so I think I have a couple minutes for questions or we started late so the next person can go yeah yeah so actually just like wrote so there's like the polka dot wiki which we've been put in quite a bit of work into and then I actually like bass Asha I don't have internet I based this talk off of a blog post that I just wrote I can hop off my phone real quick I'm throw it up here see long yeah oh here we go yeah so like everything I just talked about is part of this thing that I wrote on our blog so I guess that resolution is not very good but it's polka dot network so I kind of went did all this here so I can check that out yeah so yeah the question is like how do you decide which nose keep track of which chunks it's just like every single valador is going to have a chunk from every pair of chain so then they just get kind of random like every volunteer has a validator ID in storage so you can just like take your chunks from like 0 to 999 and then just like queue them up with validator IDs from 0 to 999 all right thank you guys [Music] you [Music]