Vitalik Buterin | Data Availability Proof | CrossLink Taipei 2019

okay so so today I'm going to have talked a bit about some of like one particular piece of a new very a theory I'm 2.0 relevant technology is that and I've been working on along with some other people have been working on over the last couple of years which is mcdee de availability checking and fraud proofs and how to use these things to improve scalability so start off by talking about the problem right so first of all chain blockchain so are increasing in capacity even the ethereum blockchain just increased it's a gas limit from 8 million to a 10 million about one month ago the change capacity increased by about 25 percent and guess what before the capacity increased the chain was full after the capacity increased the chain was still full so there was a lot of demand right lots of people love etherium and wants the use of thorium after the Istanbul fork the the data capacity of the blockchain is so not the computation in capacity but the data capacity will increase by another factor of 4 and you can guess that the etherium blocks will get even bigger and the chain will still be full and there are other block chains saying so there's the chain of our good a good friend craig right that goes up to a bit under a million bytes a second i mean and with eath - of course we plan to be if it more ambitious so to avoid to go up until we're gonna have a several megabyte per second range so when you have more chains that have a new very high capacity then you get a problem which is that individual computers are not powerful enough do not have enough bandwidth do not have enough computation do not have enough of everything to be able to actually fully verify all of this data read another challenge is quote verification of history who here has synced in aetherium full node in the last month hmm why are there not more hand um what about who here has synced an aetherium full nerd in the last year okay so some people but not everyone right so why not basically because there's a lot of data the ethereum blockchain is over about 100 gigabytes the state is now about 50 gigabytes thanks to some really heroic engineering by the Goeff team also by another mine team and other people it's like sinking and eath client is actually continues to be a pretty tolerable experience so I think never mind about three weeks ago and it managed to get the entire state in about 12 hours and and 2 years ago when I did all synced all the nodes it took maybe about 4 or 5 hours so even despite huge increases in engineering efficiency it's I mean clients are still taking longer to sync right and so you want we wants to ideally have some mechanism to kind of verify years of history but also not just to get the state but also actually verify that the history of the blockchain is correct right he wants to verify that the coin supply hasn't been tampered with that your favorite smart contract hasn't been illegally tampered with unless there was a heart for core everyone agreed to it um so but it would be nice if we could actually verify that like everything that happens in the past is valid without actually checking everything in the past cuz that's called an archive node and that now takes over a month so what's the goal here right so basically in direct validation so I mean in kind of many parts of the crypto space there is this kind of religion that says that to be a real citizen of a blockchain you have to basically verify everything yourself right you have to be a full node you have to sync the entire chain personally process every transaction personally verify that every transaction is valid and there is like good reasons behind us it creates a I know very strong force that makes it very difficult for even colluding miners and 51% attackers to add changes into the blockchain that create invalid state transitions so if you do a 51% attack you can revert some transactions but you can't actually create more more coins than there are supposed to be coins you can't steal other people's coins you can't give yourself free coins and like full validation basically a kind of gives us this right because a chain that does any of these they'll invalid things is just kind of by definition and valid and nobody accepts it the problem is full validation does not scale and so the goal here is can we get most of the benefits of full validation without actually doing full validation and the approach is indirect validation so basically you come up with mechanisms where the set of a kind of client nodes together and if somehow collaboratively verify blocks I verify a little piece you verify a little piece someone else verifies a little piece and together we verify everything and ideally we want to mechanism that is not honest majority dependence right that that continues to work even if there are 51% attacks so the eath to sharded design for example right now it's very heavily dependent on committees so basically you randomly select some small number of nodes to verify this thing you randomly select some small a number of validators to verify that thing but comity is definitely our kind of honest majority of rational majority dependent and if there is either a global 51% attack or some kind of highly targeted attack on one committee then that the committee mechanism by itself doesn't protect you and so we wants to have a mechanism the dust protection so if it's not honest majority dependent and what security models are we okay with one example is fraud proofs right so fraud proofs basically say well you come up with a mechanism where there is computation that's being run but by defaults not ever runs it instead you have a few people run it and if any one of them discovers an error then they can publish a proof of the error broadcast a proof of the air and everyone else once they see this fraud proof know that this piece of computation actually is not actually correct right so this is a kind of collaborative validation and fraud proofs require a one event honesty assumption you need at least one honest participant and subjective Network synchronous so if a network latency is too long then you're not going to receive the fraud roof another one is a date availability sampling that I'll talk about today and this one instead of requiring one honest client it requires a somewhat higher number of honest clients could be 500 could be a thousand somewhere around that range but it's not a 51% honest or even a 10% honest assumption rated it can handle any number of dishonest clients as long as there are enough honest ones so fraud proof so let's talk about fraud proofs so here's the kind of basic model here you have a malicious miner or a malicious validator publicness of luck in let's say there's a 51% attack happening right so they get away with it the long is chain now contains invalid blocks all of the block data is present but some of the block data might be invalid and so the goal here is basically to try to and if designed the protocol so that no matter how the data is invalid and if the data is invalid there's some specific piece that needs to be done that's got to be the kind of the first piece that is invalid no matter what it is you can make a reasonably short proof a reasonably short and if set of merkel branches sort of set of portions of the state that can be authenticated with hashes and you can use this to prove that wait something inconsistent happened over here so you need a full clients different so create one of these proofs but once one of these proofs has created the proof can be broadcasted and another client can download a proof they can verify the proof and it it works right so if they verify the proof they real de blacas invalid now fraud proofs even by them by themselves they have one huge weakness which is what if data is missing right so what if a block maybe correct maybe is incorrect but you can't tell because the entire block data has not been published maybe only the header and 3/4 of the block have been published the block could be invalid but because you don't know what the rest of the data is you can't really tell whether or not the block is invalid now you could have someone noticed that that particular part of the block is invalid and then they publish a message saying hey look over here I can't find this data but then this is attackable right because if someone publishes this kind of message then whoever published that block and just published that little piece of data and then you raise the alarm on another piece the publisher of a block clinic can just publish that data and so basically if you try to use a fraud proof like mechanism to verify availability you just created denial service attack and everyone ends up having to download everything now this isn't always a problem right so for example let's say you have an environment that's a very computationally constrains but not data constrained such as you're running a Python client so if you're running a Python client then what you can do is you can just download every block and downloading every block is still just as cheap as it was before but computation is expensive and so you don't actually do the computation until you get Santa fraud proof and if you do this then the benefit that you get is basically they aren't if conditional on the security model of a fraud proof which says that messages hand fly around the network and fast enough that if there is something wrong you'll find out about it you basically get the benefits of full validation without having to do pay the cost of doing full validation yourself which if you have a Python the client like are extremely hot right Python like literally take some longer than the block time to process it's a process blocks in many cases so frontiers find themselves are useful optimistic roll up his dependence on fraud proofs and optimistic roll up can achieve scalability of up to a few thousand transactions a second even on the current aetherium chain but they have a limitation so data unavailability attacks right so the block header is present but some or all of the data is still missing so we can think of the data unavailability problem as a kind of separate problem to the catching fraud problem right so the problem here basically is suppose you have a block and you're a job right now is you don't care about fraud you just wants to prove that some particular merkel root represents a piece of data where all of that data actually is available all of that data actually is kind of floating around the network and for every chunk of data that chunk is held by at least one honest node somewhere and so if for any specific piece of data you were to ask for it you could get it so the question is how do you verify availability right the trivial way to verify availability is to download everything yourself but the problem is that we're talking about block chains that are processing multiple megabytes a second and despite what Internet service providers advertise internet connections are not going to be fast enough for many people to actually continuously download all of this data every day so how do you verify the data is available without downloading it um so let's consider one kind of strong mian protocol right you have a your mark over it you have your little hash that's at the root of a moral tree and instead of trying to download all the data you're gonna do it just select a tea random positions you're gonna select et random indices in the tree and you're just gonna ask the network a network I wants to learn a proof that shows me what is chunk number 74 hey network I wants to learn what is chunk number 235 hey network I wants to work and what is number Chunk number 612 whatever set of indices you choose you only accepts the block when all of those indices have been responded to right so you pick a set of indices and you wait until you get proofs for all of those indices and when you get proofs for all of those indices and you accept that the data is there so a big problem with this is that it does a good job of proving that more than half the data is available because if if less than half the data is available then with extremely high probability any particular nodes check is going to fail it you ask for data and at least one piece of data is going to turn and turn out to be not available but what if 90% of the data is available right so maybe 90 or even 99 percent but not a hundred percent what if in the worst case only one piece of data in a block is missing but maybe that one piece of data is very important maybe that one piece of data is a transaction and you have a block claiming that that one transaction withdraws five hundred thousand ether from the etherium foundation wallet so Beast this kind of scheme can prove that half the data is available but it because it's a useless random sampling it cannot cover the case where 99 percent of the data is available where only one chunk is missing so how do we handle this erase your coding so basically suppose there exists these mathematical protocols where you can take a piece of data that has some number of chunks so it has n chunks and you can extend it to two n chunks such that any end of those 2n chunks can be used to reconstruct the whole thing and from there we construct the original data so you know this is basically done by kind of event pretending that the original data is a set of evaluations of a polynomial you figure out what the polynomial is you evaluate the polynomial at a bunch of other points and if you have enough evaluations you can reconstruct what the polynomial is regardless of like what what specific evaluation you have but like regardless of kind of the lower level details of the math what matters here is that if you do this if you kind enough do this sort of low degree extension of some piece of data D to a piece of data D Prime that contains D but also contains some other data then any 50% of the bigger data D prime is sufficient to reconstruct the whole thing and so it's sufficient to reconstruct D and so what we do what erasure coding does here is it basically means that we've converted the verify 100% availability problem into a verified 50% availability problem right if if you publish a route and less than half the data is available then a anyone who does one of these random sample checks anyone who does this kind of trick of asking random Oracle branches some of those checks are going to fail with extremely high probability if less than half the data is available then at least one out of eight each X is going to fail if more than half the data is available so if almost all the data is available then because of how arranger coding works the rest of the data can just be reconstructed so if we if we can do this then this basically by itself and it gives us a protocol that we can use to verify that data is available without actually having to download all of it now there is a problem with this right and the problem is basically that what if the erasure code is not constructed correctly right so what if instead of kind of correctly encoding treating the data as a polynomial figuring out like where the evaluations are at other positions what if instead at some of the other positions the data is just random John right what if the hash is hand just malformed in some way what if there isn't even data in some position now the good news is that there is a fraud proof for this right so if someone creates a block where the erasure code is and if not instructed correctly then the fraud Griffis pretty trivial if more than 50% of the data actually is available that you can just locally reconstruct the rest of the data and you can locally figure out what the morkul route should be and if the merkel route that should be is different from the Merkel route that is then the you know you can see that the block is fraudulent and you can just broadcast the entire block as a proof that the entire block is bad so this is kind of trivial right but the problem is that this is too big basically one of these entire block so it really could be huge it could be potentially many megabytes could be even more and like we want fraud proofs to be reasonably sized because if a fraud proof is not reasonably sized then well how would we even like you can't put it into a blockchain and use it inside of a blockchain protocol to take away someone's deposit for example right or or even just clients can't even download it so what do we do there's a couple of different approaches here this is an approach from myself and Mustafa about two years ago and basically the trick here is instead of using a one-dimensional polynomial we use a two-dimensional polynomial and and so instead of a fraud proof having to contain the entire data basically the fraud proof only has to contain one particular row or one particular column of an extended Square and we can see some statistics here so for example if you have a gigabyte of data then the amount of data that you have to download for to verify availability of the whole data is only somewhere on the order of about 200 kilobytes in the size of a fraud proof is also somewhere around 200 kilobytes so the unloading 200 kilobytes to prove availability if a gigabyte it's pretty good but it's still not perfect right but so this is one solution you know there is also this really entry thing paper that literally got released about a about a week ago and the paper uses a different kind of erasure coding scheme and it also does this clever trick where instead of just erasure coding the bottom layer you can even raise your code every layer of the Merkel tree and it has some serious trade-offs so for example for this to work you need to verify that more than seven eighths of the data is available and so the amount of data you have to download to make these random checks has to be a significantly higher but the good news is that a fraud proof is very tiny so these are a kind of two Pro kinds of and have improved protocols that both do similar things and they both have depend on fraud groups right so here basically if you use either of these techniques then you can verify that some really big block is valid and available using just a header if you download a bit of extra data and you kind of combine these sampling checks with fraud proof as proofs of the it is incorrect and you have this kind of interactive verification of a block that gives you then if equivalent properties to fully verifying the block yourself conditional on a couple of extra security assumptions that basically say number one network the network is fast enough the fraud groups get broadcasted and number two there are at least some minimal number of honest clients so maybe at least 500 on this clients somewhere else in the network with you um a third approach is to bring in stars right I'm who here has heard of starts who here are sort of snarks okay so basically what a sonarak or a start is is it's this a general-purpose your knowledge proof so it's this I mean if cryptographic proof that you can generate in what this cryptographic proof does is it lets you basically say I ran a computation on this piece of data you know and this proof verifies that the here is the output of this con and this computation was all done correctly so for example if I wanted to if I computed the the number of prime numbers between 1 billion and 2 billion if I told you that between 1 billion and 2 billion there's 61 million 110 thousand and 4 prime numbers there aren't actually um with high probability um but then like if I just told you that then like you wouldn't you wouldn't necessarily believe me right but what I could do is you could musically make this cryptographic proof where I run the computation of just like going from between 1 billion and 2 billion checking every single number to see if it's prime adding up like how many numbers actually are prime and I can run this really really long computation and I could give you the answer along with a cryptographic proof and you can just verify the cryptographic proof without having to do the entire computation yourself and you would be convinced of like how many prime numbers there are between 1 billion and 2 billion now nobody cares how many prime numbers there are between 1 billion and 2 billion but there is a lot of kind of much more useful computations that you can use general-purpose zero-knowledge proofs for and one of them is well you can use them to verify blocks so basically they're kind of the really long term vision here right is that you just use general-purpose your knowledge proofs they're going to completely verify everything about a block so you just view add a cryptographic proof that shows that a block is and if completely correct that everything was computed correctly that every transaction is valid that every transaction did what it's supposed to do and then you can just download some data I check the proofs and you can be kind of very quickly verify the chain without actually running everything yourself right so this is kind of the 10-year dream and like there are projects that are quite like coda for example that's trying to do this for kind of a much more restricted kind of blockchain right now but the problem is that the technology is not really ready for zero-knowledge proving and if arbitrary a general-purpose computation right there's just a bunch of reasons why it's complicated and it's extremely inefficient and so forth but we're will week you but what zero knowledge proof SAR already really good for is structured computation right so computation that kind of has a pattern that just says it basically it's repeating the exact same step over and over again and so it is possible that you can and just basically verify that a piece of data has been arrays you're coded and kind of hashed correctly and that some piece of data actually is the Merkel route so basically just make a stark that proves that this sum were that you you make a stark that proves that this R prime actually is the Merkel route of an extended version of a piece of data and you just published us all right along with along with the more covert and then if someone downloads this Merkel brutally download this proof then they know for a fact that the proof represents or that the route represents a piece of data that has been encoded correctly and so if you have that proof then you can do the you sorry and I latency the son of the this thing is violating my synchrony assumption so leave him basically a client can just randomly sample randomly kind of verify that with very high probability more than half of the data is available and if they have that then basically what they know is that because more than half the data is available if there is even a single honest to know it verifying all of the data then that honest node convicting download more than half of the data use it to reconstruct the whole thing and it will be correctly the data will be it will be correctly formatted right so if you use starts to verify of extended worker routes then you do not need fraud proofs great and this is a general kind of pattern that as your knowledge proofs and fraud proofs are kind of in competition with each other and we've seen this already right so at for example there's ZK roll-up which is a scaling solution based on zero knowledge proves and then there's optimistic roll-up which is a scaling solution based on fraud proofs and I mean a couple of days ago there was a bit of us would've wore what were a ZK roll-up person is was Kim I mean if arguing that fraud proofs or that's the security assumptions behind fraud proofs are a really big problem so I think the two technologies are definitely kind of competitive with each other and they have different trade-offs right so the optimistic approach for the fraud proof based approach is good because it's kind of easier to implement more general-purpose and it's active I would say it's cheaper but the fraud Prue the a zero knowledge proof based approach gives you this kind of tight level of security without having to rely on Network assumptions right so there's like even if the network is unexpected or really slow look even if the network is unexpected we extremely slow but even if the Internet like some like the the two halves of the world get cut off from each other completely for four days it's not gonna break to your knowledge perps and so the technology is do you have these kind of different trade-offs to them I mean and I would argue that because of how kind of nicely structured the computation around of Merkel routes is like look it's structured like do you agree this is structured okay then like Starks are actually a pretty good fit for this right so if you have Starks then you can't basically you can view you can get the benefits of kind of fraud proof based validation now there's a kind of new idea here which is basically that you could create a architecture for a shorted chain we're kind of at consensus layer you verify correctness of the beacon chain I verify availability and correct a validity of the beacon chin but you only verify availability of the shard chains and then you use the beacon chain I kind of internally to detect when blocks in charge chains are contain incorrect computation and it's and if they do contain incorrect computation then instead of throwing away the entire beacon chain and leg-breaking Kasper in all and kind of the messiness of that you just kind of correct the faults that happen inside of the beacon chain so this is real basically what this does is it prevents high network latency from kind of reverting finality and it makes a security assumption more subjective right so you personally depending on like what you think is the risk of a network like what network latency is likely to be it you can choose how long you're willing to wait for a fraud proof you know if you want to verify that some computation and a shard happens correctly and but for availability we use so basically if Starks and it with a random sampling in Starks and random and random samplings do not depend on fraud proofs and so like the if there is high network latency that doesn't compromise the basic integrity of the chain and so this is kind of one of the kind of idea for improving the other security model and the story of what would what would happen in the etherium chain if there was a 51% attack or for whatever reason a committee were to get attacked right so there's so there's to you I guess to kind of summarized right there's two use cases for these technologies right so data availability for proofs in fraud proofs are really nicely complementary because fraud proofs basically say if there is a bunch of data and you have you know the data is there and there is computations then you can instead of running all the computations themselves just wait for a run a bit of computation and you can wait for fraud proofs and if nobody submits the fraud proof you know the computations correct indeed availability proofs let you verify that data actually is correct or a soirée data actually is available so the availability proofs catch the case for data's not published fraud proofs cache the case where data is published but there's something incorrect about the data in these two technologies kind of combined in this really powerful way to enable scalable validation that is 51% attack resistant and so basically it reduces the power of a 51% attack to the point where just like in current non-scalable block chains the only thing a 51% attack can do is they can reverse transactions it cannot like with this this what if everyone uses fraud proofs indeed if your ability proofs a 51% attack cannot force invalid blocks through it can only revert so two use cases one use case and this is a use case that could theoretically be developed now is verifying existing chains right so basically imagine you have a big long chain it could be the pic one chain it could be the etherium chain it could be the Bitcoin Satoshi's vision chain it could be whatever chain and it has a lot of data the more data the better and so what you do is you connect your node and you ask for the network please give me a merkel root of an erasure code extended version of the entire chain the entire big hulking file means whoever provides the merkel root they can also provide either a proof of work to show that they're serious and they're not trying to das you or a signature from an account that has some coins in a smart contract and so if them or if they commit fraud than a fraud proof can be used to penalize them and take their deposit away so take the blockchain serialize morkul eyes you have them work over it then now that you have the Merkel root you randomly sample for some branches you do your data availability challenges verify that enough data is available to recover the entire data and then you just go ask for the network for Brod sound note some messages that say hey guys I think this little hash over here is the morkul rude please tell me if you know about any fraud groups and you wait a long time for fraud verbs and if you see no fraud proofs then you accept the changes valid right so basically with this kind of architecture you can kind of augment existing sinking processes and even existing light clients to give a security guarantee that's much closer to full validation use case number two is scalable block chains right so in a theory m2 when your node receives a a beacon chain block in that beacon chain block contains shard data Merkle roots of shard data it's basically instead of downloading the entire thing you can perform data availability checks and you can perform fraud checks so in both of these cases right and if quick validation of existing block chains and scalable block chains we can and have changed the security model and make it one that's you know kind of gives considerably stronger gearing guarantees to clients you can also use this for plasma chains and so conclusion this is good this is good for scalability and this is good for improving security guarantees and Starks can can be used to make all of this stuff even better thank you thank you very much would you like to do some QA section we have any questions from the audience if you have any questions please raise your hand anyone any questions okay we do have a question over there yay huh can you can you use snarks to make it better uh you can yeah I guess the reason why it there's two reasons why I didn't say snart's one of the reasons why is because narcs have a trusted set of assumptions and especially like trusted setup assumptions they're evil at layer one but if you're doing alerts your thing it could be fine another reason is that this scheme is a really bottlenecked at proof generation level and so basically we're talking about doing proofs over hashes of many megabytes of data and when I did them when we did the math it seemed like one of these proofs for like even a single if you block would take a few minutes to generate so like you this is the sort of thing that already might would basically require at least somebody to run a GPU farm and smart so like make that even more extreme because everything other than Starks takes longer to generate proofs for because you have to like do a look the curve stuff or whatever instead of just an FFT and the third reason is that for data availability checking specifically you're already doing about a hundred kilobytes worth of checking merkel branches so an extra hundred kilobytes for a Stark is not going to kill you so I think you can absolutely use a snark but I feel like Stark sorry I like in this particular case a better fit three thank you do have any yes we do have one more questions on the audience uh yes rolling over to aetherium tube-like moving the etherium one system into aetherium - well 2.0 will require and the actual trends i wrote an e3 search post about how the transition all work i think if you just go on III search and you check there's something called if one to you through transition it's not technically a hard fork but it is a kind of moving of this state from the proof-of-work chain over to oprah the proof of stake chain but there will be hard work is required before this to kind of prepare that youth one chain for this for the transition hey thank you very much we have one last question do we have anybody for one last question okay question is what makes you in the middle of the night shorted peer-to-peer networking does that answer your question okay great let's give a round of applause for our two most [Applause]