# Polkadot's Data Availability and Validity Scheme by Alistair Stewart (Devcon5)

- Channel: [Devcon](https://streameth.org/devcon)
- Date: 2020-10-09
- Duration: 15:24
- Topics: blockchain, smart contracts, distributed ledger, ethereum
- Watch: https://streameth.org/watch/yt-Ex_1XXF29Yo
- YouTube: https://www.youtube.com/watch?v=Ex_1XXF29Yo

## Description

Visit the https://archive.devcon.org/ to gain access to the entire library of Devcon talks with the ease of filtering, playlists, personalized suggestions, decentralized access on IPFS and more.
https://archive.devcon.org/archive/watch/5/polkadots-data-availability-and-validity-scheme

How can we make blockchains secure at scale? We suggest a data availabilitty and validity scheme that make sharding efficient in terms of the number of validators and validating resources. We first describe the Polkadot data availability and validity scheme and consider its applicability to other sharded systems (e.g. ETH2.0). In Polkadot we tie an erasure coding data availability scheme with consensus, where we can not finalise an unavailable block. Moreover, reports of unavailability or invalidity trigger extra checks. The aim is that, with high probability, we do not finalise an unavailable or invalid block provided that there are enough honest actors to report. The key advantage of this scheme is that we need fewer validating actors per shard and in turn less total computational and especially networking resources. This softens the trade-off between scalability and security.

Speaker(s): Alistair Stewart
Skill level: Intermediate
Track: Consensus layer
Keywords: polkadot, dot, technical

Follow us: https://twitter.com/efdevcon, https://twitter.com/ethereum
Learn more about devcon: https://www.devcon.org/
Learn more about ethereum: https://ethereum.org/ 

Devcon is the Ethereum conference for developers, researchers, thinkers, and makers. 
Devcon 5 was held in Osaka, Japan on Oct 8 - 11, 2019.
Devcon is organized and presented by the Ethereum Foundation, with the support of our sponsors. To find out more, please visit https://ethereum.foundation/

## Transcript

so I'm here to talk about the data availability and validity scheme in polkadot now this this talk is probably a bit technical for the main stage in 15 minutes at 9 a.m. you end up going to sleep it's still fine but I'm sorry I'm gonna try and explain this so what do we mean by data availability and validity so in particular what we're talking about about blocks in a chartered system so if you have a single chain like a theory 1.0 or Bitcoin if we have a header and the block doesn't exist then like that people people will ignore it if they download the block full load and it verifies it tries to run it it doesn't succeed it would ignore that block and of course four modes include the miners and if you have made 51% it if if 51% of our miners are honest then they won't build on a block that doesn't exist was implied and so it'll never be in the longest chain eventually but if you're in a shard system like s 2.0 like polka dot then only a small number of people check the block that the set of violators we which form the content consensus for the entire system they don't know if the book exists if anyone has it the data or if it's valid if it makes sense it's not going to sort of explain a bit how polkadot works so the rest of this makes sense so polka dots a multi-chain system we have a relay chain the pair of chains and these are secured via a set of validators and the way hurricane blocks work is some Claytor produces it and there's some random subset to validators to all the set of bio-datas and we sort of divide them between para chains and this random subset checks the block say it says it's fired and available they sign this header the header goes on to the relay chain and then it's in the relay chain we count it is happening in particular when the relay chain is finalized which we do by you finalized by a finality gadget get Byzantine agreement then it's final so you compare this with at 2.0 so what now happens is that so shell blocks it produced and then we have a random subset of violators which we divide between all the all the shards they call the cross link committee and they periodically they all sign a cross link which says that these blocks happen that they're Biden available and then that goes onto the beacon chain if two-thirds of those sign it and then the block it happens because it's in the beacon chain its final when the finality gadget Kaspar FFG finalize it so this is basically the same you just change a few words as far as this talk is concerned there's a few important differences things like the cross links aren't every blocked the chains are different it more para chains are different in polka dots but the only thing that's important here is how many validators this is the big difference for this talk so in aetherium 2.0 you're going for you know one hundred to a thousand validators and a shard and in polka dot where we're looking at like ten and this is a sort of a bigger problem for her and basically this is this will be fine as long as we can guarantee that the blocks are valid and they're available any any fool can download if that happened it's fine so so how do we guarantee this well so this is the reason why we wanted a thousand hydatid per shot so well f1 2.0 plan insist it's to have sort of 16,000 initially to a million validators or the week sort of have every 32 ethers of our data and [Music] it's like if we say 3/4 of those are honest and we select say 100 then with overwhelmingly high probability you know one-third of those will be honest and so if two thirds of people sign to say it's bad and available so I'm on this person will keep it bad and available probably a whole load of them and then it will carry on being available and valid but it's still sort of a small fraction of the entire system that that's backing that is giving us this guarantee and so the question is will we be able to get a million validators I don't know so if I have well maybe but only if some people run a lot of other data stripe so if I have a thousand death then I should be running 30 validators but what we really you know what sort of a design goal was to make these runnable by someone on a laptop in their bedroom or but that doesn't really work so well if I have a thousand death you see and I'm not sure how all this is going to scale but there's like sort of there's Network and computing limitations and the networking is probably a problem so like how many validators got about a one well kind of depends on how many peer-to-peer networks I can connect it can i connect you 30 networks instead of to be reversed by getting 30 connections each thousand connections I can do that with a server in a datacenter probably if the code is good but probably not in my bedroom they would crash my reader and this is why we kind of worried in polkadot that we won't get this many validators that we're trying to design the system with less but I'd like to sort of point out that because SD Point area has a very similar architecture almost all parts of our solution would just apply so you could use any of them so what does polkadot do so they said before we only have ten by a day to prepare Jane it means we only need sort of five to seven signatures on this on this block and the basic idea for validity was to rely on fisherman so every collator will be a fisherman there will be no shortage of fishing whenever you fool no can just production stage they don't have to lock anything beforehand they can just run it and then when they discover a bucket invalid that they're running they'll report it and then people check it and if we discover someone was lying one of these five to seven signs in a banded block will will slash them we'll take away their stage and we can allow sort of fisherman just take themselves we can band them together a fisherman lie that they get slashed it's like if you're in there a fisherman and you want to convince all your friends to join in and say this is true and this will ensure that we recheck it enough and if you're correct you will get a reward but the problem is you can't buy a datum clock you never see and validators don't know that the full nodes never saw it and even if the pool nodes say they didn't see it and instead of subjective we have no way of verifying that all we can do is after the day to ourselves which point if everyone has the data we're not scalable anymore and maybe when we ask for it when the validators aspirated shows up and it's correct but we don't know we can't slash anyone it's a kind of the reason this wasn't the problem with it with the theorem Rob Quintero his Bitcoin was because the people responsible for the entire set of the consensus were the same people who kept the data available and you know at least all the miners keep the data available as do all other full nodes so what we really would like is to sort of do that again and we can kind of do this there is a solution everyone kind of it's an old solution for a busty storing data all nice you do use of radio coding so you sort of had some redundancy to your data and then you divide it into four pieces and even if a large number of these pieces go missing you can still reconstruct it from the remainder and so we can use this to make the that the whole set up validator is responsible for the availability of every data with all the data without overloading any of them so with the way we do this hurricane validators send the pieces of the data to every other of our data and one third of bio-datas it pieces belong to a third of our data - enough to reconstruct and then we make voting the consensus particular in the finality gadget which is the Byzantine agreement our than we need two thirds of people to sign conditional on having all the pieces you supposed to have and what this means is that if we finalize a block and we're two-thirds honest then the block is available in principle right we can reconstruct it so the data if we work with we are two packs of two thirds on it and we'd really like to be rational that we can do that as well then it's available but there is a problem here which if you launch an attack are we going to catch you in the end you know it's these 10 validators sign in the ballot box we're going to catch them we're gonna slice them ideally that'd be sort of a hundredth of the state in the entire system but that isn't good enough so what can happen is that these guys can send signed invalid both make a sender transaction to a Bitcoin bridge that owns a lot of external things Bitcoin and tells them to pay the Bitcoin and this means that if that's more than one hundredth of the stake in the system they make a profit and it we can't revert it on our chain because we're not Bitcoin but we can get around this if we have a protocol to catch people quickly so if 99% of the time we catch this before they pay you the Bitcoin every 1% of the time you succeed the expected cost an attack under the state want and at the time they all the stake in the entire system it's cheaper to attack the the the main chain and the entire system than is any one component but we need a protocol for this so what happens is that we take reports of invalidity or this time on availability and we get extra people to check it we choose the extra people at random this is this is important I will use a to user verifiable random function so the protein the people validating with the shard were chosen at random but everyone knows who they are so the bad guys can just wait until they own enough attack the rest and they're fine but if random people checking they don't know on the other hand of vrf everyone can knows who's responsible you know who we should be checking this after the fact we know which reports we should pay attention to and we can even pay them and then if anyone claims it in behide everyone downloads it in checks now the other things you could do you could do random text without reports there's this this great idea for doing fraud proofs and this is this paper that buy the stuff robust and metallic and Sonia had which I saw Mustafa talking about Def Con last year where we do some range coding but we sort of arrayed your code sub-blocks and then we can check only a sub block and it gives us a small proof and if we have a small proof we don't need this escalation or we can use succinct proofs to come into every one of the validity and reduce the only problem then is availability and so any of these could could be used in F 2.0 if you want do the same thing so that one of the nice things about finality gadgets is but you don't have to find my sink straightaway so what we do is we delay on voting on finality until we have all the array decoder pieces and if till we leave some time to get reports and if they don't show up they do show up then we have to wait for checks and then we never find lice and invalid or unavailable block except with small probability as long as we get enough reports or we had you know enough random checks and that doesn't slow block production there's a bit of an issue with networking we can't gossip all these pieces but never mind that we can solve that and the result is that we can secure polka dot with only ten bio-datas comparator and still have that secure and I think if they Liam could use a similar thing to get we use the number of violators thank you