Distributed Data Storage, DAS, and Danksharding with Valeria Nikolaenko | a16z crypto research

Transcript

all right uh welcome everyone to this afternoon's a16z crypto research seminar uh very happy to introduce FIA niceno a research partner here at a16z crypto um Lara will probably tell you she's a cryptographer but she actually knows an amazing aad about amazing number of topics which those of you um who know her of course have already experienced and in particular she's recently been doing super exciting work on a very important problem data availability which she'll tell us some about today so Lara uh fantastic so I would talk about distributed data storage data vity sampling and D sharing and if you've heard none of these terms before it's somewhat new developments in the blockchain space uh so those ideas are being pioneered right now by ethereum

and ethereum foundation and those effectively come to help sharp the blockchain help sh uh make the blockchain more scalable so let's just take a little bit of a step back and kind of understand what is the the problem that we will try to solve with this new protocols um and let's look at how blockchains scale today so you probably all know or heard this for many many years now is that natively the blockchains uh the two largest ones Bitcoins and ethereum are only supporting very small number of transactions per second so your Bitcoin is just seven transactions per second and ethereum is 15 so it's confirming about 1 Megabyte blocks every 10 minutes for Bitcoin and about 4 megabytes for

ethereum just because ethereum transactions are a little smaller but this is super low numbers yeah compared to Visa that's handling tens of thousands transactions a second um we see blockchains natively they don't scale very well and you can't uh really make them scale naively you cannot just make the blocks appear faster make the block larger there is some bounce um for why those are the parameters that the block blockchain can sustain because otherwise it will start forking too much and you'll be running into security issues so you can't really naively go and scale them um you can scale them a little bit but not by much and the reason we kind of focusing on the two blockchains of course is that those are the largest by the market capup if you

look at ether at Bitcoin I think it now at 45% and ethereum is kind of on par with Bitcoin if you also include all of the tokens built on top of ethereum all right so that's kind of the problem that we will be addressing um and the fundamental reason for uh why blockchain struggled to scale is because everybody is doing everything in the blockchain and the reason is that initial thinking when the blockchains were designed is that the blockchains should really survive catastrophic scenario so when everything disappears uh uh and only one node is left to sustain the blockchain it can still

still keep going so if everybody else except one crash faulted um this since everything is fully replicated all of the nodes um have all of the transactions and are executing them in replication this node will just keep keep going keep sustaining the blockchain so it it seems like they were designed for this um scenario catastrophic scenario of all except one crash failing but in fact we know that blockchains uh fundamentally so survive only up to 33% sometimes it's 50% of bantine faults so you can't really hope to have a secure blockchain if you have more bantin faults than that so we really want a blockchain that can

sustain not just crash faults but bantine faults and if you want to sustain Byzantine faults you have to assume that you have a large percent of honest nodes that help you sustain the blockchain so at least 66% of the nodes and here comes an idea of why we do full replication maybe instead of doing full replication we can replicate to the 66 % of the onus nodes that we know are there uh so maybe we can do some savings there so instead of full replication do some partial replication so that each of them each of the 66% is doing some subset of the work not replicating each other okay that's the idea we're going to be heading towards and if we look into what kind of work the node is doing um well I'm abstracting a lot of things away

here say as consensus but fundamentally it kind of stores a lot of it notes stores a lot of transactions and it processes all of these transactions so stores transactions and executes and we're going to look into solutions that help us will help us scale those two uh those two modules of the node uh we'll look at the distributed storage for storing transactions and then we're going to look at the rollups that help scale the execution so the overall uh kind of question we're going to be asking is how to make each file there do less work do subset of the work not replicate it each other all right so uh this is kind of um I I'll start with motivation because otherwise I feel

like the the protocols they're going to describe next will not make um a lot of sense but you first need to understand how we scale the execution and then we will see how to scale storage um to help um the scalable execution so let me explain you very briefly what are rollups and how they help scale execution so right now without the rollups all of the accounts uh and users are submitting transactions directly to the chain and the validators here they work to put this transactions order them put them in the block and append this block to the chain so the validators are working on finalizing lists of these transactions and all the users are submitting transactions to the validator

set like if you look semantically what's happening if we assume just simple money transfers uh then those users are sending coins to each other so every list of transactions kind of induces this redistribution of coins between accounts so let's look at a cluster um of the users who are transacting between themselves as well as outside so let's call this green transactions that are happening within this cluster inner transaction so inner transaction list let it be green and then the transactions that are going out of this cluster let's call them TX outer and pull them in purple Okay so let's keep in mind those two kinds of

transactions that are happening inside the cluster and kind of going outside the cluster so what those users can do is they can designate a central party uh we'll call it a rollup and instead of submitting their transactions directly to the chain they're going to submit it to the chain through a rollup so rollup going to relay those transactions to the chain for them and kind of packing them into something smaller than the collection of these transactions so what rollup exactly is um is doing rollup is a smart contract on the blockchain and it um has its state is the commitment to the account states of all of those users okay so we put account balances of all

of the users we um compute a moral tree and the mor root hash is a commitment to account States that's stored in the rollup smart contract so the rollup is only allowed to transact the only valid transaction that the rollup can submit will have to prove the knowledge of a valid set of this inner transactions within the cluster that will result in the transaction that go out of the cluster to other users other than the rooll of users and U such transactions also update the state route accordingly so this transaction inner has to satisfy two conditions this has to result in

those outer transactions that are transacting out of the rollup and it has to update the state route this s um to another valid State according to the transaction in list another way so when you say in I should think of that as like L2 transactions the in trans exactly out transactions yeah okay and then and then this is an L1 transaction that actually hits the chain so the chain never sees these transactions only sees kind of an update to the state route and uh a proof it it can be zero knowledge proof can be fraud proof I can not differentiate here what kind of proof that is uh okay so there are two components a

smart contract and a service so the fundamental uh benefit of the rollup why it's not actually a centralized party why you're not introducing a central point of failure because the whole point of using the blockchain is it's very decentralized and you're not relying on any Central party to to help you do the transactions so why rollups actually is not a rollup is not a point of centralization is because it cannot steal your funds so every time rollup submits a transaction it has to prove that it knows a valid set set of transactions that will result in this effect on chain and since rollups cannot fake valid transactions they cannot fake user signatures even from users of its own cluster they will not be able to

come up with a valid list of transactions to use in the so rollups really can't steal funds but they can do a couple nasty things first they can censor they can just ignore transactions from one of the users completely um maybe this is one of the suctioned addresses maybe they just don't like the user and rollups have this additional uh component in the smart contract built in that allows the users to go directly onto the chain and transact out of the rollup so if if the service is not cooperating with you you can always go on chain and transact out of and you know keep keep going with the L1 blockchain so it's an additional functionality of the smart contract

another um nasty thing that the rollup can do it can go down and you'll just lose liveness so uh the service is not doing anything and the mitigation to that again you can go directly on chain uh to transact out but that's going to be an unpleasant event because uh noway rollups handle large vast amounts of users so if every if rollup goes down and all those users suddenly want to transact on the blockchain could cause a lot of congestion very high gas fees so there is a better motivation which is anybody should be able to restore the state of the rollup and resume the service so the smart CCH will stay intact but everybody will be able to act as a rollup service in case this rollup

this current rollup goes down it's kind of another uh U safety feature that's built in but what's important here is that in order to restore the state of the rollup you have to get it from somewhere and rollups um you know the are distracting the state away they're only the smart contracts are storing only the hash commitment to the state so where do you get the state from so you need um to get it from somewhere so there will be has to be some solution that stores all of the past transactions of the rollup so that you can reconstruct it state so here we come to the uh storage problem is how do we store transactions uh plus

transactions of the scrollup how do we make sure they are available to users and that validators can agree that they store all of them uh in order to kind of help rollup be secure and this transactions if you notice the blockchain only needs to store them the blockchain doesn't need to execute over them so execution so we can scaling execution with the rollup but for data availability storage we still we still have to uh use the blockchain uh and I'll show you how to do storage in a much better way than um just storing directly on the blockchain and replicating again on all of the nodes and by the way you also need the state in order to allow the clients to go on chain because they need

to prove their mer Miracle uh to provide a miracle proof for their account state in order to show you you have that much balance uh on your rollup um on your state in order for the rollup to ow you to transact this balance out on L1 so for both of these problems we need some reliable storage for past transactions I think of this is kind of this extreme model where you know the the rollup goes down and somebody just wakes up and was like oh no I hadn't been paying attention this whole time and I want to reconstruct from scratch like from Genesis right the state and so that's why you need like the full log of transactions to available like The Other Extreme would

be imagine you yourself were just for whatever reason like maintaining the state yourself locally right at which point you could just immediately exhibit that and like it would hash to the right commitment every be like oh thank God you just had the state saved right yeah but so then you need someone who's online all the time exactly so should I think of where you're going is kind of like how to interpolate between those two extremes or a little bit Yeah well essentially what we're going to look into is how to store this transaction in a distributed way so that um we still submit all of those transactions on the ethereum blockchain um but uh those are special transactions they only need to be stored so those special transactions ethereum validators are going to store

in a distributed dispersed way so not everybody will store all of those kind of transa rollup transactions but only um in encoded way Only Store fragments of them but for now I should be thinking of them storing them permanently so not all the transactions but a that's what rollups are doing today they're just submitting their um doing some clever packing techniques to squeeze as much efficiency as possible they're packing all of those transactions into some TI state but they're only so much you can pack it's still very expensive for them to store them on ethereum but that's what they do today they store them on ethereum directly and that's where the bulk of the gas cost come from uh right so just to be a little bit more precise so when the rollup submits

a transaction that the this transaction looks like the outer list of transactions that are kind of going out of the rollup to um L1 uh accounts the updated State root yeah so we go from State root S to State root S Prime updating the inner account balances of the rollup users and um is a commitment to the inner um transactions that the Roll Up is kind of masquerading from the blockchain and then the proof P will just prove that all of that is correct that this the trans transaction iner under the commitment corresponds to the valid State transition and to the valid transactions going out of the rollup so the transaction will only be

accepted if it has a valid proof and also if the commitment transaction iner under um so transaction iner under the commitment is available and we're going to look uh into what that means in just a second but um the way rollups operate right now is that a submit transaction in directly in the clear into the ethereum and ethereum recommits to the transactions that's how valers make sure those transactions are there uh cool so just having a bigger picture we'll now have a lot of different rollups and those rollups are kind of abstracting away their clusters so only few transactions hit the chain so but in fact there are many more transactions that are happening just that those

rollup transactions that never hit the chain and those the transactions that hit the chain they are much easier and cheaper to execute compared to all the transactions that happening within the cluster so you see kind of within this 15 transactions per second that the rollups and other users uh produce in fact under the hood many many more transactions are happening so we're going have scaling the execution more transactions actually happening but only this 15 transactions per second hit the chain let's look at the rollup a good indication to see that the rollups indeed help helps scale ethereum is to see how much it cost to transact on those rollups because the cheaper the

transaction cost it means the easier it is for the validators to handle this load um so the lower the cost the more scalable is the solution so rollups indeed have 2 to 30 a lower gas cost so if you if you look at s simple ether on ethereum it's going to be uh about $1 but say an optimism it's only 0.2 uh only 22 cents so indeed rollups already help uh scaling but if we look deep into kind of what fees you pay this is from optimism dashboard so 90% of the fees still go to storing data storing these transactions so 90% of fees go to data fees and only

you know a small portion goes to execution fees this will be a little larger for zero knowledge rollups because you need to verify Zer knowledge proofs but still I one data fful be substantial portion there so if we make this cheaper you know we have a good chances of dropping uh the transaction fees by 10x so we'll be only left with a small fraction so we'll now focus on how to make a data fees lower how to make the blockchain store on this slide and on a previous one you seem to be taking the position that rollups have to store the data on ethereum or on the blockchain they're working on as opposed to they just need to store it somewhere

right yeah right so I guess uh like offchain data availability would be another option right yeah true and some of them do data availability committees and do offchain data availability yeah we'll be looking into monolithic kind of design but true you can um maybe look into other option it just that this uh this proof that transactions are available uh if you are going to another chain to store those transactions it should give you some something to show here as a proof that you're storing those transactions elsewhere like a certificate of storage or something like that um and this is tricky right

because uh you will have to do a bridge effectively to another blockchain um maybe you will even have to verify partial consensus here I don't know it's kind of tricky to piece those two chains together yeah but for for this talk we'll look into single blockchain trying to do everything here cool okay so how to make validator store data distributed so let's jump into now the main topic um of the stock so we'll be looking into solution for distributed data storage um those have been started from the '90s um and those are two protocols dispersal protocol and the retrieval protocol so

dispersal protocol um distribut UT a block of transactions to end validators and then the retrieval protocol reconstructs this block back from any subset of n minus F validators where f is aior bound on the number of faulty validators so bantine validators so here we have five validators two can be Byzantine you no matter which ones a Byzantine you still have to uh be able to reconstruct the original block from them and uh the techniques that we're going to be using are eraser codes I'll uh kind of hint at the design but then we're going to go more in depth into all of the steps and it will be make more

sense uh at the end but at the high level what we're going to do is we're going to take the block we're going to pack it into a matrix and we have some flexibility and picking the dimensions of this Matrix but anyway we'll we'll pack into the Matrix B so all of our data that we want to disperse um those will be roll up inner transaction ction lists so but let's just call it block and we're going to apply Erasure coding techniques so we'll take this Matrix for B and we're going to append more rows to The Matrix uh kind of expanding it uh and those row additional rows will help us reconstruct for erasur in this Matrix so we apply Erasure coding then we um

give each validator one row of the result resulting Erasure coded Matrix e so E1 through E4 E5 and then when we are reconstructing and this only works so far for crash folds when we are reconstructing some of the validators might have crashed as long as there bounded number of them crashed you can still and there is enough data that you're recovering you can apply eraser coding and kind of correct for those erasers and piece the block back together okay so let's look into eraser coding oh yeah the uh fragment size here has to be well will be uh it can be larger than that but it cannot be smaller than the size of B divided by n minus F because when you

will be reconstructing here you will you will be receiving data from n minus F honest nodes f is number of 40 nodes n is number of total uh total number of nodes so you'll be Recon you you'll the the data that you reconstruct has to be at least of size B and that's the optimal you can hope for yeah CU we don't have generic data compression so the the amount of dat the yellow data here has to be at least the size of B in order to be able to reconstruct and this algorithms will achieve this kind of optimal fragment size cool so let's uh dive into quick tutorial on raia codes this is going to be super simple codes you don't have to take uh a class to understand how they work those

are uh pretty straightforward so just explain um let me just explain them in couple slides so let's treat our block as a vector of integers modular P so so um just a simple case we pack our data into this Vector B1 B2 through BM and then we'll need a special Matrix G uh the size of G is going to be n by m so m n is small is larger than M with a special property and the special property is that if you take any M rows of the Matrix G you get a full rank Matrix so any subset of M rows will give you an invertible Matrix matx so let's

assume we have the Matrix with this magic property then our rati coding will simply multiply our Vector B by this Matrix G and you get back uh an expanded Matrix uh sorry an expanded Vector e so reconstruction for E uh which is a larger Vector yeah it has n elements more elements then in the original block um to reconstruct e you you will have to have any M elements of e and the way you're going to uh it's going to work is you you you have you take the elements of e that you have and from this Matrix G you leave um out only the rows that correspond to the elements that you get

so here you have M by m Matrix but this property of this um G it's invertible and so you can multiply by here by an inversion so let me work you through an example for simple error correcting code where n is equal 5 and M is equal 3 so the block here only has three elements H and when we raas a code it we expand it into a larger Vector with five elements okay so you have a 3 to five expansion then what happens is if you lose some of the elements of this Vector e so those are erasur those are have been held by validators that uh crash fault that crashed and you don't have them anymore

so um we will kind of ignore the corresponding rows from The Matrix G let's just forget about them and then the Matrix that you have is a square so it's 3x3 by this property it's invertible so you can um inverted let's see so we're piecing this things together and now we need to find B that will satisfy this relation but that simple solving of linear uh system you invert the m matx and multiply e Prime with this inversion to get the Block B back okay let's now look into the examples of this Cotes how to pick the Matrix G what

with this magic property so a property again is that any M rows of G should constitute an invertible Matrix and surprisingly a random Matrix will just work if you if your uh Prime uh Q everything works modular Prime here so if your Prime p in this case p is large enough then any random Matrix will have this property the problem is that it's expensive to invert a random Matrix so if your Matrix is of size n byn inversion is n to the 2.37 or something so it's more than square and the better choice is another Matrix I'll show you in a second it's called vandon Matrix and it gives rol monia codes I let this words not scare

you because this is really simple this matrixes of this you take consecutive integers 1 2 3 4 5 and you compute powers of those integers so this is called a vmon matrix and you can see how to to extrapolate it into more Dimensions so what's happening here is you want when you multiply your vector B by this Matrix and in fact you're doing polinomial evaluation so you can treat this Vector uh as coefficients of the polinomial a0 A1 A2 and when you multiply by matrix you're producing this Evolution at points 1 2 3 4 5 yeah for four it's um a0 + 4 * a 1 + 4 Square * A2 so you're getting evaluations that's

basically polinomial evaluation and the backward transformation is polinomial interpolation and turns out that you don't need to do any inversions of the Matrix uh for this Wonder Matrix you can just do it all in your head and the transformation back and forth is quas linear so it's um linear with some Pol logarithmic factors so that's assuming that you're not using consecutive integers but powers of the root of unity it doesn't really matter it's a technicality this kind of method works as long as you have any distinct evaluations here so both directions is really efficient to encode and decode for this code you said the the N log in needs

like a fft like par of kind of exactly right that's an fft um so R coding is going from coefficients to evaluations and decoding is going back uh we will have we will use a related code um it's very similar but it goes from evaluations to evaluations so it's also can be represented as a with a linear Matrix and the reason we want this is we want to preserve the code word inside encoded block so we want to preserve this um Val vales inside of our encoded um coded string and that's just in a happy path when no no no validators are faulty you

can just you know query the top three and very quickly you don't even need to go through reconstruction happy path you already are getting the ve the vectors that you're interested in uh back from the validators it's not just that you said as long as everybody's non faulty but actually it's even as long as the top three or nonf yeah cool that's cool uh cool yeah so and this is kind of doing um interpolation and evaluation so it's kind of combining the two steps uh basically the top square Matrix is just identity just because you're translating the top Vector to itself and then the bottom ones are some lrange coefficients

but this is also linear so to get y4 it's just a linear combination of these three elements uh cool so this is the Matrix that we're going to um use and Transformations back and forth are also very efficient okay so how do you so I showed you how to encode like really dummy vectors uh but how do you encode really large blocks like if you if blog is super large but you still want to encode it say to five validators uh what you do is that you put it into just Matrix that's a little um a little bit wider and depending on um the size of your data you're going to pick kind of the size the width of the Matrix yeah so um but you will still be encoding

into five rows if you have five validators so the way it's going to work um is the dispersor is going to eras a code The Matrix B uh just multiply um it by G on the left by this our fancy Matrix or doing some ffts to make it more efficient and it will give each validator one of the r rows of e and then decoding uh from the errors is uh multiplying by the inverse or again doing the fft if you want more efficient algorithm and this only tolerates crash folds so if those validators are feing you bogus data you know this method won't work you either need to go to error correcting instead of rasure

correcting but this will result in parameters that are much worse but you can still do it with error correcting tolerating some small number of buting folds but we'll do much better we'll augment this method uh to have the same kind of efficiency but um to make it tolerate Banting faults uh by the way there is a um a parameter that you have some freedom of choosing which is the number of rows in the vector in the in the Matrix B so when the data when the disperser wants to disperse a large file it can choose into how many rows it subdivides this file so it has this ability kind of free

parameter V that it will choose to kind of um to make it smaller or larger as long as that's less than n minus half so there's an upper bound that you cannot go above but you can make it smaller but making it smaller kind of increases this Dimension the width and when you increase the width it means each valat will store more data so uh when you make V smaller you make validator store more but at the same time you um the number of pieces that you need in order to reconstruct the block is also V so making V smaller allows you to talk to smaller number of validators so with smaller V validators store more but you need to talk to few of them so there is a interesting tradeoff think you can

play with okay but how to protect against mici servers and here we'll need to do to use a little bit of a heavy machinery we'll use to we'll have to use cryptography and the cryptography that we'll need is homomorphic Vector commitments so commitment um this commitment scheme can commit to vectors so those are K length vectors modular or prime P the result in just like backing up and talking through why what you've said so far doesn't work for Byzantine FS why it doesn't work for B yeah so the reason is that you you can correct for errors in this codes it just

that you will be able to correct for twice two times smaller number of errors and erasers so you'll be able to correct for one B Val instead of two um right so that means your f is smaller um yeah basically the parameters of the scheme degrade a little bit is just that to to handle two the two validators you have to use a larger code so you have to add two more rows here if you still want to uh to handle two validators you have to grow validator set right this solution is kind of not optimal just

because it can handle fewer errors than erasers uh but if you're fine with that if um actually I have some I the decoding procedure has to change right I mean decoding also becomes much I think rer coding as like coding where you know where the bit flips were basically like you know right whereas exactly if two of the five rows are bogus you don't know which ones yeah but you kind of you would need to find the right three to invert you don't know which ones those are exactly yeah so you have either to know who are the the valers ab buting or kind of correcting for smaller number of rasor just more expensive it's not as simple for that you need to take a course just complicated algorithms to

correct and but we will augment this scheme with homomorphic commitment so commitment to a vector is something short we will use deterministic commitments or you commit to the same Vector twice you get the same thing and the commitment should be binding for this to work so you cannot commit to two different vectors um getting the same commitment out so you cannot find any collisions with the scheme so HH function is a good commitment so if you just hash your vector it's short deterministic and binding but it's not homomorphic and uh there are schemes that um are more complicated but they are homomorphic so by homomorphism I mean it's that you take two commitments that you add them

together you get exactly the same commitment as if you added the vectors first and then committ it so homomorphism means that you can kind of move this addition operation inside the commitment right and then here is what we're going to do we're going to commit to this um to the vectors row vectors in the um in our Block B creating this kind of column Vector H so each element of H is the commitment to the row of B and this Vector commitment we're going to replicate to all of the validators so we're not replicating B but we are replicating this H and this H is something much smaller than b so that's okay to

replicate um and then we do same thing as before we raas a code B into e and split and give each f one row of e so because of the homomorphism of this commitments uh if you multiply the vector H by G you magically get back the commitments C that correspond to the commitments of the expanded Matrix e and that's because the the H homomorphism of the commitments means that you can compute linear combinations of these commitments and they will correspond to linear combinations of the vectors so since this is multiplying by G is a linear

combination the commitments will satisfy this equation so G * H will be equal to C so it doesn't matter how you compute C whether you recommit uh e to get C or whether you just take H and multiply it by G both ways you get C right so how the retriever is now going to work is I'm going to talk is going to wait to receive 50% of replies and I'm going to check that it gets consistent age so it's kind kind of verifying that valers are consenting on what age they store it's kind of um consensus on the user side so to speak so as long as when it gets 50 50 plus Epsilon per of replies with

consistent H uh it will then um request all of the fragments and it will check that the fragments correspond to the commitment so the way it's going to check is it's going to expand this Vector h with this Matrix G getting C and it will check um kind of recommit each Vector to check whether this um matches C or not and for fragments that got corrupted they will not match the commitment so those are just they can um the retriever can safely uh filter those out and treat those as erasers and only left with correct fragments they can then apply

Erasure coing eraser correcting here so same same thing it just we we added this additional filter that filters out um fragments that were altered in a Byzantine way and don't conform to the commitment anymore is it 50% so if you talk to less than that uh and say disperser is malicious it can maybe disperse one file to one half and another file to another half and if you're only talking to less than half you will not be able to figure out that the other half thr something else and then another retriever that shows up and talks to another half um will retrieve a different file uh so

two3 why not 2/3 you can make it 2/3 oh wa not two3 yeah um well why 2/3 you can do one 1/3 plus one you can do um but then you have to make them run consensus guess I worry that I get exactly half of the replies exactly half of those are from Byzantine notes and the other half are from honest notes and then there is no majority strictly more than 50% strictly more than 50% yeah there can still be a

tie right shouldn't I have more than 2 f+ one replies so f is less than 50% the number of B faults um but don't I need 2 f+ one to make sure the majority is you have to wait I think the the 50% of the replies have to be consistent like 50% of you with the same so if half of half are inconsistent then you reach 50% that yeah it's not quite kind of a Forum thing from the consensus it's a kind of non interactive check for the consistency um uh is it that you wait

for if there are 10 valid 10 noes you wait for five replies that are consistent with ag yeah well six like 50% plus one mhm yeah and then if if you if you have those and they they're consistent you're reconstructing against that age and you know that any other retriever will either reconstruct the same file or fail to reconstruct for some reason so you don't want the in consistency that different retrievers reconstruct different things it's either they all those who reconstruct reconstruct the same Okay cool so this feels kind of like a sort of General result it kind of feels like you're saying through

homomorphic commitments you can reduce eror correcting coding to eraser coding is that okay right even all right yeah was that was that known before or yeah yeah yeah this is a long line of work okay I have a slide to the and also um because we're talking about eraser codings like you know where the errors are and that's like exactly what the C gives you right so yeah exactly yeah yeah so some of the more efficient commitment schemes just maybe came out the last decade but before that people were thinking of using homomorphic fingerprinting those a kind of information theoretic objects uh so you can build this thing

from that so or Universal hashing but but but only recently kind of we got this homomorphic commitments that are super efficient and easy to use making that possible and that I think kind of the latest work by um uh yeah by Stanford people um that kind of explains how to build that with our modern commitment schemes but yeah the the concept was known is it is it known you can't do this well without assuming existence of commitment schemes so like purely information theoretic like does this overcome some information theoretic limit by having the by assuming that you have these commitments that you can't find collisions and

stuff um I'm afraid to be mistaken but I think you you can build this with information theoretic objects just not going to be it's it's going to be similar to error correcting that it's not going to match the same efficiency uh but it's an interesting question I I I need to look more carefully to to give you an exact answer there but I I suspect that you you definitely can't build this with the um information theoretic techniques is just I don't think it's going to match the efficiency of this uh great okay so this is how you distributively store the data so let me just recap what we've covered um we first kind of started with why

blockchains fail to scale and the reason they fail to scale is because everybody's replicating each other's work um we then try to explain how rollups help scale the execution and kind of motivate why we need good solutions for distributed data storage um and then we just looked into how to build distributed data storage resilient to crash faults using Razer coding and how to make it resilient to bantine faults using uh some of the heavy cryptography using homomorphic commitments so the um right now I'm going to skip to the next topic and the next topic is how to make validators agree on whether they store the data

behind the commitment or not and just going a little bit um a step back with how this fits into the rollup uh story as the rollups are going to be submitting this inner list of transactions to the blockchain and they're going to disperse this blocks to the validators so validators will store all of this in a transaction list in a distributed way instead of full replication so that's how we're going to scale storage for all ops okay so now how do we reach agreement so the protocol that I showed you it's only disperser sends some messages to the validators and then retriever kind of retriev something back validators are not talking to each other uh so let me just redraw this picture

and of course when we want agreement we have to make validators do some interaction um in order to kind of come to the decision of whether they store all of the necessary data or not and there's traditional ways to build agreements through reliable broadcast kind of BF protocols that are studied for decades now it's multiple rounds of interactions where every validator is talking to every other validator um you can you can make it three rounds you can do this in two rounds it depends also on your network assumptions and such but largely speaking I will not go too much into depth you can if you're interested look into the slide later on um but the valers um as a result of this

interaction they will produce some certificate that can in principle serve as a proof of storage that they are storing this data so first of all they will all come to agreement if they indeed store if they didn't store all the necessary fragments for reconstruction and there will also come up with a proof of storage um that they can later on show to the client it's kind of an aggregate signature and the client can then maybe go bridge to another blockchain and show it there uh okay so I'm not going to focus about uh on that you can uh read entire given entire lecture on how to build reliable broadcast and consensus here but it's well known how to do uh

consensus on this type of systems so that's black box right any protocol for liable broadcast you just plug in okay mhm and we just make sure I'm on the same page the problem you're talking about now is just making sure that among the validators they're storing all of the different fragments that the disperser didn't like send the same thing to everybody and they don't actually have all the information Yeah Yeah so basically this agreement this agreement guarantees that um at least f plus one Hest notes a storing correct fragments that are consistent with ag so you know that there should be enough fragment to reconstruct back the block and they themselves know that fact right yeah exactly yeah they they themselves

get to be convinced in that and they can also prove it outside yeah okay uh cool and another kind of beautiful idea that I think etherum Foundation was the first to try to make it work um I haven't I I haven't heard them explain this um the idea this way but it's effectively trying to build an alternative consensus mechanism around data availability through data availability sampling so so who did you attribute this to ethereum Foundation D sharding I think it's is the first to kind of suggest this idea so alternative way to build consensus around data availability so instead of bft style they do longest chain style consensus

it's kind of surprising that you can do this for data availability but let me explain first the mechanics of data availability how it works so data availability Ling is a protocol uh that helps the client make sure that the validator set is storing the data that um and underneath the commitment so it allows a client to request random fragments uh fragments from random notes to Pro probabilistically check whether the data is available so the client what it does it um it uh gets the commitment uh to the data it has the commitment to the data and it's trying to understand whether there are enough fragments that are stored by the validators so having that commitment it will the assuming

there are many many validators the client will pick a random validator uh get it fragment uh and check that the fragment is consistent with h and if so it will um so say so there here are some parameters that are tweakable but say there are two sort of fragments or enough to reconstruct the original data to kind of piece uh to do a correct ing or rasure coding to get uh back the original data so if oneir of the fragments is enough then the block is only unavailable if two3 of these fragments are absent or missing so the probability that those many fragments are missing yet you get a valid fragment

is only one over thir that's a probability of your false positive of you thinking that the data is available when in fact it's not when in fact that much of it is missing so you just was lucky to hit the existing less than one3 and then you can repeat that you can uh query another run the validator get back the fragment if it's correct you know that probabil probability of the data being unavailable is 13 squared And So It Goes Down exponentially with t tries um and you can amplify it really quickly to get it to negligible so that's how you can and the amount of data that you'll be downloading here will be much smaller than it's not intuitive to see but will

be much smaller than you need in order to reconstruct the full block so the kind of communication here um you you will ensure that the data is available with much less communication than you need in order to reconstruct the block so those algorithms are efficient to making sure the data is there um so what the valers will do when they will try to agree on whether they store the data behind the commitment is that each of them will sample uh every other so the valid number one will independently request and verify fragments from randomly selected file ders to get assurance that the data is available so we'll kind of locally get

this assurance and assume that um the data is available and everybody doing that will eventually come to agreement that the data is there so I'll not go into the details explaining how longest chain consensus works but it essentially allows validators um to do long exchain style consensus now I need to say that this is very much new and ethereum Foundation is still trying to figure out uh how exactly the protocol is going to work espe especially the networking aspect of it how exactly you query the validators uh which validators are connected to which ones Etc so they even have some call for proposals and they gave out

some grants for people to research this problem but that's what fundamentally they're trying to do build longest chain style consensus Based on data availability sampling great and in the remaining uh five minutes let me quickly explain the D sharding it's a future upgrade to ethereums um named after danr Feist who came up with the idea um it's a proposal for distributed data storage for ethereum um The Proposal is to run to do consensus through data availability sampling and it has some other CL ever ideas the RoR coding that I explained to you uh was kind of easy but they have an extension to that uh they do 2D eraser coding and

for that you need some special commitment polinomial commitments to make it work so we were expanding the block down we were kind of appending more rows to the block but they're also expanding the block right and kind of expanding in both directions creating a larger Matrix as a result to make it work you need some more constraints on your commitments you need them to be polinomial commitments to make them work another interesting aspect that they combine rep application with the rure coding just because the number of validators on ethereum is so large it's like half a million right now you cannot possibly you know expand your small block to half a million validators it's just too much work uh multiplying by this Matrix or doing fft it's still very expensive so they're kind of trying to

look for tradeoffs and eraser code to some larger set but then have validate since the the um number of encoded fragments will be smaller than the validator set smaller than 500,000 some of the voltages will be storing the same fragments so very interesting kind of maybe research to be done to exactly analyze uh what are the guarantees here with the change in number of validators if you combine replication and rure coding and then the another beautiful idea is locality of reconstruction and that's why they have this 2D design em missing fragment in this scheme in D sharding can be reconstructed without reconstructing the full block so if you're a poor validator who didn't get

um the fragment you can only talk to a small number of other validators and they will help you reconstruct your fragment you don't have to go through full block reconstruction uh great and then Charing will add a new transaction type uh so those are going to be transactions that rollups will submit they will submit as data blobs they're going to submit this inner transaction list that you need to store so each transaction has this giant data blob it's of the size of around 130 kilobytes and a small commitment signed commitment to that blob so this yellow part is going to be rasure coded uh and distributed split into fragments and

distributed to validator so none of the valers will store this replicated they only store fragments of eraser coded data but they will store replicated commitments so commitments will persist on the Chain but this data was kind of will be distributed and N is 256 right now the thinking is that should be enough to satisfy the needs of the rollups yeah the last slide I have is conceptually what D shining will allow to do is to increase the block size so right now the block size on ethereum is 0.1 megabytes on average um the St trades a little bit but not much and then we with d charting the blocks are going to be massive like 300 times larger

blocks but this additional data that will get added into the blocks will not be accessible to execution it would just be distributed distrib stored in distributed way it's not going to be uh replicated so the volunteers will not be able to execute on this data they will be able to execute on the commitments if they want through zero knowledge proofs but not on the data itself so this additional data that will get added uh will be just stored by the network and this will add about half a terabyte per validator which ethereum thinks nowadays is kind of cheap to store half a terabyte on a hard drive so they still leave up to their premise that validators can run out of uh laptops um and that's about 30 x less

than full replication if you are to replicate this 30 megabyte blocks all of the validators you're going to incor like 30X uh blow up in the store but this additional blob data also has an expiry that what caps it it's 500 GB so the current thinking is that it's going to expire in one to two months but that's optimistic so none of the mechanisms there incentivized the Vol is to keep the data for that long the only they only incentivized to distribute it during the data availability sampling when they're actively working on achieving consensus and that's if you really want to to download this data that's the moment you need to connect to

the VOR set to uh to be able to get those transactions and then for they're going to store it for one to two months but that's altruistic the protocol doesn't guarantee they're going to keep up with that so you really have to be there in the moment in order to download this data for example if you want to restore the state of the rollup if you're a very active user uh you have to you know actively be downloading this data um at the moment when the data is being uploaded by the rollups later on you'll likely be able to download it from archival noes but you know it's going to be altruistic uh so no access the data is not accessible to execution only commitments are accessible main users

are rollups and another interesting thing is that it's going to have a different fee market so this blob data is going to be priced at one gas per bite but this is a different gas than uh the current gas fees so how how much it's going to cost compared to e is yet to be seen um and compared to cold data is 16 gas per bite but that's again a different that's execution gas and there a storage gas so it's not very clear how they're going to compare long term cool okay that's all I have so uh actually could you page back one slide thanks so uh this data doesn't have to

be propagated to validate the block that it's included in or or does it like can a block be kind of validated and confirmed before the Dank sharding data is actually distributed well you have to achieve agreement that you store the data before you finalize this commitment so it's um the this commitment will not persist unless the validators figure out that they indeed so is there some concern about like block confirmation latency then with the much bigger blocks um you mean with this additional interactive protocol for well it's just way more I mean if the the blocks are

uh seems like they're like you know 300X the size you just said so I mean that's much more latency to to propagate the block right yeah well okay so the ethereum plans to do this proposer Builder separation so the Builder is going to eras a code the block and then split it in the fragments and send to the validators so it has to do all of that in like less than 12 seconds that's so that's a lot of work for the Builder but they expect the Builder to be beefy in any case because the builders are were doing M extractions and such like stuff like that so they're outside of the validator set um they can be run running

on kind of uh good and fast machines so that's not a concern on the dispersion side and because they assume that the builders are powerful to distribute that but it definitely adds some rounds of communication when they try to consent on the data availability because of this data availability sampling so it's maybe a little bit of a delay there I my other question was uh so like all validators have to be dank sharting storage nodes there's no concept of validating but not storing data or doing yeah that also seems a bit weird yeah in the future they could they could unbundle that maybe yeah or locally you can maybe

partner with another validator who will be storing for you and you'll be executing well that's my concern is that Val like in the short run a lot of validators will just put all their dank sharting data on AWS or wherever and it won't actually be that decentralized if a lot of them don't have a you know two 300 gigaby whatever sitting around yeah but at the same time 300 GB is like I don't know probably under $100 to store to to buy hard drive to store uh I don't know but you you you need for for consensus at least you need fast access to this data because notes are

requesting the fragments from you and so I don't know if storing it on AWS will um um is too slow because you'll have additional delays there but yeah good question I think the whole um idea is that ethereum hopes this numbers slow enough that the valers will store this locally and I I think if they realize that the valers are starting off floating this data to AWS they they're going to probably change the parameters to make sure others can still keep them local that's my guess I just seems weird that it's like a one siiz fits-all parameter

for every validator rather than validators sort of opting into how much storage they want to do especially since they have a floating gas cost per bite of data stored here right yeah at the same time I think they figured out right now it doesn't cost that much it's still cheaper than buying a laptop so if you're already executing transactions you should be fine storing starts touching on the H da kind of vision right sort of opt in through reaking kind of stuff yeah yeah Lara could you talk a little bit about your recent work with Dan in the context of this of the talk you just came yeah yeah I I figured it's a lot to cover so um my work with Dan is going

kind of in the width of how rure cing is done um an expansion so ethereum kind of proposed doing um a two-step expansion so you take these vectors and um you treat them as Pol as polinomial evaluations and you evaluate at more points you expand this block this way and same wayse you expand the columns down uh so you treat those vectors evaluations of the polinomial of degree n and then you evaluate at n more points so that's how you do the expansion of the block kind of two-step process expensing right and then expansion down and we realize that that's equivalent to

doing by variate interpolation so instead of doing this two steps you can just directly construct a by variat from this um from this block so it's going to be has X and Y it's polinomial of two variables and then you evaluate it at more points so overall this is just evaluations of a large bivariate polinomial and if you look into um right so if you're not um if if you don't know this is a b variat then the way to do eras reconstruction is to do row and column wise reconstruction because every row and every column is a polinomial of degree well n say if this a square and then um you can find a row

that has at least 50% of elements and then you can through interpolation U you can figure out the missing erased elements in it just because every row and every column is a polinomial of degree n and you can substitute for n misses in your 2 N Vector of evalation um and in order for that reconstruction rowwise and columnwise reconstruction to succeed you need 75% of the elements in this Matrix so you can only substitute for 25% of erasur as kind of a pigion hole argument for why this is true but if you do by VAR interpolation turns out you can um reconstruct from more

erasers um and in fact in principle we're trying to argue that you can reconstruct from 75% of erasures so with column wise reconstruction you can only reconstruct from 25% but with byar full byar interpolation you can reconstruct from 75% and that drops that helps you drop with this when you do data probability sampling the probability drops uh quicker um so you have to do fewer samples and making the protocols more efficient but the the algorithms that do by VAR interpolation they're kind of expensive so we're still in a search of a good um and fast algorithm to do by VAR

interpolation um you can always go through solving a linear system because every time you need to do interpolation you can always invert a gtic matrix um to reconstruct your coefficients of the polinomial but that's too slow for the parameters n is and the Order of uh 200 200 or even thousands so the Matrix is just G gentic you cannot do this through through gas elimination school book methods you have something more clever and so we're trying to figure out it now becomes a pure mathematical problem kind of how to do efficient by VAR interpetation it's

very interesting somehow it's understudied I it's really puzzling for why mathematicians didn't look into this problem seems kind of obvious if you figured out good algorithms for Univar interpolation there are many of them but no good algorithms for biar and probably this problem wasn't motivated very well um maybe it's just a hard problem so um but it has nothing to do with the blockchains or cryptography it's just pure math so uh yeah that's what we're working on right now they're coming up with better algorithms there and then you would also me the commitments to byari K no you can still keep commitments to the roles so

um well actually that's an interesting question like instead of instead of commitments to the role can you do a one one commitment to the whole Matrix that's an interesting problem um maybe you can we don't know we don't know how to do it that's an interesting problem definitely so each row is a Univar polinomial each row yeah each row of the byar is a univariate polinomial so because you fix one of the variables say this is y you fix y to be 1 2 3 or n and then you kind of reduce it to the univariate and you commit to that but the whole Matrix is a huge two VAR two variet yeah yeah you yeah still need to be homomorphic too right yeah those commitments yeah not

only have to be homomorphic in order to do the expansion kind of down to help you verify this roses but also be polinomial commitments because when you're expanding here you're Computing more evaluations you want the commitment to this expanded Vector to be the same yeah and so I guess if you even if you manage to capture all of it in one commitment you somehow need that one commitment to also be homomorphic yeah exactly yeah yeah so it's a little more tricky than yeah but I I I think yeah yeah that's a good we should talk more about that interesting um is there any proposal of like how you compensate builders for doing this eraser

coding or like what's incentivizing Builders to like even do this in the first place like why would they just send a normal block That's not including any blobs and then that's cheaper for them well same as they're incentivized to include the transactions they getting some portion of the gas fees right um so okay so for proposer build separation is kind of a little trickier of how they get paid it's kind of a relationship that they establish with the validators validators are the ones collecting the gas fees and the data fees and then they're kind of paying back to builders oh um maybe one way what I'm saying is like you already mentioned that now we're going to have these like two different floating prices right for the data and the execution right and so

one interpretation of pronouns point is that like um so one thing that could drive up the sort of data prices would just be like excess demand you know for the 48 blobs or whatever but his point is like it's also kind of lower bounded by the marginal cost of you know just you know communicating that data to other people so if that's like expensive that's going to put a certain price floor on the on the gas price for the data I think so yeah mhm right I it's like a failure you can imagine is that like the Builder is spending just more computation on like extracting me or something um makes it so that it's more profal for them to

just kind of ignore this like doing this eraser coding and I don't know that might affect things in different ways but I don't if anybody's like thought about what the CTIC would look like I think I think if you had these blocks that had no data blobs then the price would sort of go up if they I think they do like a 1559 style price adjustment So eventually it's going to get high enough the builders are going to be like okay sure you're will to pay me that okay I'll send your data around so yeah yeah but if if the builders are leaving off only off extracting me then indeed it requires some analysis to figure out if if those types of transactions give you any me on on yeah see I I don't know interesting probably

research that in the intersection of M and this stuff all right thank you Lar [Applause]