DAS, Protodanksharding, and Danksharding with Valeria Nikolaenko | a16z crypto

Transcript

so in this talk I'm going to describe and explain data availability sampling prototing trading and Link charting if you haven't heard these terms before this assigned with new developments in the blockchain space those are being pioneered by the ethereum foundation and those effectively will come to Shadow blockchains to make them more scalable but do so in a much much simpler way compared to the ideas for sharding that we had before since a number of projects are working on that availability Solutions I hope it's helpful to show how some of the best schemes work so that others could either improve on those and pick up perhaps an idea for research projects from this work or incorporate these ideas into their own projects

so I'll start with explaining what problem ethereum is trying to solve here I'll show where it fits onto the roadmap I'll explain exactly what will be achieved by this upcoming upgrade and I'll briefly explain how this is going to be done so the main goal with this upcoming upgrade is to help ethereum scale and ethereum l2s or Roll-Ups effectively already help scale the execution of transactions this l2s take some subset of transactions and process them off chain the chain only sees the post effect of these transactions so ethereum violator said effectively doesn't have to execute those transactions those executions are happening off chain gas fees are typically a good indicator of

whether we are making the blockchain more scalable so if the gas fees go lower it means it's cheaper for the validators to process these transactions so we make the blockchain more scalable so if you look at the gas fees on the l2s they're typically you know 6 to 30 times smaller compared to transacting directly on ethereum but if we dive deeper and dissect the gas costs on each of the roll ups for example if you look into optimism we will see that most of the transaction fees go to L1 data fees so those fees go to storing transactions storing data on an ethereum L1 and only a tiny fraction only the top kind of gray area shows you

how much you pay for the actual execution fees on the L2 so we can make rollups even cheaper if we lower the cost of storing data on the ethereum L1 and that's what ethereum is trying to do with this upgrade that they're going to explain in the stock so there were a number of proposals for how to make ethereum scale and how to make storing data cheaper some of the initial ideas were around full charting full charting effectively splits your large blockchains into smaller blockchains and tries to sync between them that's a very complicated design and the nice thing about the current state of ethereum is that Roll-Ups are effectively already doing part of the

split they take some of these transactions and execute them themselves and then they use the ethereum L1 in order to sync between those roll ups so l2s already kind of went into the direction of full sharding so the only thing that ethereum blockchain really needs to do for the stroll UPS to become even cheaper is to allow them to store data with lower fees so full starting was kind of replaced with another two proposals at least for now those have very similar names eip4488 and eip4844 AIP starts for ethereum improvement proposal so don't mix them up they're pretty different the 4488 was proposing to make call data cheaper but

instead ethereum decided to focus on another proposal eap4844 which suggests to add data which will have an expiry so the ethereum will now store some data blobs some data fragments that it will expire and erase after some period of time the current thinking is it's going to be one to two months of guaranteed storage EAP is also called colloquially protodin sharding so that's what ethereum is implementing right now it's mostly implemented and it should be incorporated into Syrian pretty soon so if we look into the roadmap for ethereum and where those upcoming upgrades fit in there the merge is already done so the next is hopping Roll-Ups scale so the product and

sharding will come first and the protagon charting will follow that still requires a bit of a research and there are a number of open problems still to be solved so why Roll-Ups need the blockchain to store some data without executing them that's kind of a one slide explanation of what a roll-up is and why it needs to store some data onto ethereum L1 so roll ups are processing transactions from the users of chain they're kind of taking all of these transactions executing them and instead of relaying them to the L1 they're only posting a single transaction that reflects the effect of all of those green transactions on the right so this transaction TX is gonna update the state

transition it's going to update the Merkel root hash of account balances effectively account States from s to S Prime and will only be allowed to do so if it can present a commitment to the transaction list on the left so the commitment to the user transactions and the valid proof that the state transition conforms to this transactions and then use the commitment that those transactions are valid so the transaction is really succinct because the root state is small the commitment is typically also very small this proof can be there or may not be there depending on the type of the roll up we're talking about if it's zero knowledge roll up this will be a zero knowledge proof then the size of the proof will depend of course on the type of the proof system that the Roll Up is

using if it's an optimistic roll up then the proof will not be there and will be fraud proofed based so the clients will have an opportunity to raise a dispute if they think that the state transition was done incorrectly those transaction lists needs to be made available in order for the roll up to be a fully trustless what it means is that the roll up should be replaceable anybody if the rollup goes down becomes malicious disappears anybody can replace the state of the roll-up by restoring its state in order to restore the state and get all of their account states of the users underneath the rollup this new entity new rollup needs to replay all of the transactions in order to replay

transactions you need to download them from somewhere so that's why Roll-Ups are storing this transaction list on some date availability solution and typically that's an ethereum blockchain itself so that's where most of the gas costs for Roll-Ups go and if ethereum can make it cheaper for Roll-Ups to store those transaction lists it will make the Roll-Ups fees cheaper so if you look into ethereum blocks as today it's pretty small only about a hundred kilobytes so 0.1 megabyte per single block one block appears every 12 seconds now with proto-dink charting the suggestion is to expand the block size with additional data so about 0.5 megabytes of data the main purpose of

this data is availability validators will not have to do any processing on this data they will need to make it available only so we will maintain this 100 kilobytes data for execution but we'll add an additional 500 kilobytes for storage the storage data for prototank sharding is going to be fully replicated between the validators and it will have an expiry of one to two months this data will not be accessible to execution only a digest of the data will some hash of the data and the main users for this data are going to be Roll-Ups and then what will come next is then charting it will expand the data even further and the hope is that it will grow as large as 30 megabytes which is mind-blowing so this data will have the same property as

for broader than charting it will have an expiry it will not be accessible to execution but the validators will be storing this data and will be serving it to the clients the reason why we can make this second jump from 0.5 megabytes to 30 megabytes will be the main focus of my talk I will explain how this expansion is possible without making the validator store more data so storage of this data is going to be distributed among the validators instead of replicated validators will not be storing 30 megabytes for each block they will clearly split this data and Only Store small fragments of each block so if you look into ethereum State size in order to be processing transactions each validator needs to store about 100 gigabytes of data in order to verify and

execute transactions so producting charting will throw the storage requirement a little bit since we add this additional data that the validators will now need to store for a month or two months the state is going to grow to about 200 to 400 gigabytes and then we're then charting despite the fact that we're going to increase the block size the storage on the validator side is going to stay roughly the same because the storage data will now be split between the violators instead of fully replicated so with then trading validators will still keep about 200 up to 400 gigabytes of data in order to execute transactions so let's see what prototank trading is producting trading introduces a new transaction type called

blob carrying transaction each transaction of this type will submit a long data vector and a short commitment to this Vector which is going to be signed by the user the thinking right now is that the number of these factors will be initially pretty small two three or four and the size of each of the vectors is about 130 kilobytes so that's the rough sizes I guess ethereum plans to see how the validators react to that and then maybe increase or decrease this number so this data is going to expire in one to two months so that validators will drop the data blobs but they're gonna keep the commitments so the commitments persist and bloop data will have separate fee market so cool data is

the cheapest way to store data in ethereum right now costs about 16 gas per one byte this blob data is gonna cost one gas per one byte but is going to be a separate fee market for this blob data so we don't really know right now until it's been implemented at running how this gas too compares to gas one that remains to be seen so let me explain you the commitment scheme that protesting China is going to use I was saying that we will use a commitment scheme here to commit to the data Vector now a hash is a good commitment scheme so you can just Hash a data vector and it's going to be a binding commitment but we will do something more clever called polynomial commitments and this commitment will

give us some additional properties the commitment that prototank shining is using is kcg polynomial commitment I'll explain it in one slide if you haven't seen this before this will give you a rough idea but I highly encourage you to look into the paper it's a very well written paper and it's easy to follow and see how everything works and even the proofs pretty straightforward in this paper it's a very elegant scheme so we assume that we have three elliptic curve groups G1 G2 and GT with a bilinear pairing that will operate on the groups G1 and G2 will move effectively an element in G1 and magnitude G2 to the group GT this polynomial commitment scheme requires a trusted setup that will generate a structured reference string of this form

so G1 is a generator of the group G1 so this rest is going to be of the form G1 to the power Tau G1 to the power Tau squared do you want to the power Tau cubed Etc so they're going to be n powers of Tau in the SRS and we are going to describe it you only need one power Tau in G2 but for efficiency reasons you might want to generate several of those to do batch proving which I'm not going to explain now so this arrest should be generated in such a way that nobody knows Tao and when SRS is published of course in these groups the discrete logarithm problem is hard so given G1 to the Tau there is no way you can figure out Tau unless you can break discrete logarithm

so kcg polynomial commitment allows you to commit to a polynomial of degree n and this n is the same as the size of the SRS so the polynomial is described as usual scoreboard representation you have a coefficient say 0 a 1 8 2 a n and the polynomial is the sum of a0 A1 times x a two times x squared Etc so all the usual nice stuff you can commit to this polynomial with a very short element in G1 so I put it in Gray just because I don't want to go into too much details but this commitment is effectively G1 to the power F of Tau and it's pretty remarkable because no matter the degree of the polynomial it can be as large as

you want as long as it's smaller than the SRS you can still commit to a large polynomial with a constant size element so CF binds you to the polynomial there is no way without knowing Tau to come up with another polynomial that will commit to the same C in its constant size it's just a single element in G1 now to open the commitment I can basically prove to you that the polynomial underneath the commitment evaluates the shortened value at a given point and the proof is also very short that a single element in G1 now the commuter and the opener needs to know the polynomial now the verifier know that the verify either the committed polynomial evaluates on point

Alpha to some value beta it only needs to know the short proof Pi so it's a very efficient way to convince somebody that the polynomial evaluates to a certain value with a very short proof so the polynomial commitment scheme is basically these three functions the commit open and verify now this polynomial commitment is binding so the main property is its polynomial binding and evolution binding it's not possible to come up with another polynomial that will commit to the same value and it's also not possible to open this polynomial at the same point to two distinct values so once you commute to the polynomial you can only Faithfully approve things about the polynomial

being committed there all right so that's the polynomial commitment scheme and it can be viewed as a vector commitment because effectively you can commit this way to the vector of evaluations of this polynomial f and then the prover can open selectively any elements of this Factor commitment to convince the verifier of the selective openings of this commitment so as I mentioned this scheme requires a trusted setup and ethereum is running interested setup right now it's generating four powers of Tau strings at the first string has 4095 powers in G1 and 64 powers in G2 the size of this whole setup is about 200 kilobytes then

there is a larger setup twice as much powers in the G1 so up to Tau to the 8000 that's about 400 kilobyte and then you have large and large setups those are effectively two times the lengths of the previous strings so 400 kilobytes and 1 600 kilobytes and you can participate in the setups right now it's basically every participant that shows up can re-randomize the string and add Randomness to the style and the whole process is engineered in such a way that as long as there is one honest participant who correctly contributes to the setup and completely erases and forgets the randomness used to participate create the whole setup is

secure so you can show that as long as one participant forgets the secrets in its contribution nobody would know the Tau so these types of setups really benefit from a large number of participants because an average number of participants more likely somebody will be honest and will correctly erase all of the secrets and not keep them around there is a link to participate so the week this committing scheme is used in protesting charting the data is treated as a vector of 4096 elements in zp where p is a prime it's a order of G1 group of the BLS 12381 curve so p is about 256 bits so the data blob is just

a vector of this 256-bit elements that's about 130 kilobytes we interpolate the polynomial through those values so we create a polynomial of degree 4095 such that F of I equals y i and we know that such polynomial is going to be uniquely determined just because the number of points is 4096 and the degree for the polynomial is 4095 so such polynomials are always uniquely determined and then the commitment to this data blob is the commitment to the polynomials the kcg commitment and the nice thing about kcg is I can show you selective disclosure of this data blob I can prove to you the certain points I indeed correct values of the

data blob and then they conform to the commitment that they generated in the first place by doing kcg openings on this polynomial f so at the high level we have our old transaction lists that ethereum blocks contain and then with product charting Additionally the blog is going to contain the commitment to the data blobs and the data blobs themselves okay so new ethereum block is now going to consist of two parts uh the old ethereum block commitments and then data blobs so the green is the block for execution and it's going to be fully replicated to the validator set so each validator is going to store the green block but the yellow data blobs are blocks for

storage doors are for product and actually also going to be fully replicated but those are going to have an expiry of one to two months so the ethereum block size now comprises of two parts 0.1 megabytes of data for execution and 0.5 megabytes of data for storage so that's pretty dang shining and now let me explain you the Dank charting then charting is an invention of dank red Feist from the ethereum foundation and it's even named after him so dank in dank trading stands for dankara so there it is to apply erase recording so don't be scared the series recording we're going to use is super simple so our data blob as I was explaining before is the

evolution of a polynomial at points 1 2 up to 4096 and we're gonna continue evaluating this polynomial evaluate at 0.4097 98 Etc so we're going to evaluate at 4096 more points and this is going to be an extension of our data block okay so that's called read Solomon encoding or low degree polynomial extension so you've interpolate the polynomials through the first half through the data blob and then you evaluate this polynomial at more point to extend the data block to create this extension now since the polynomials of degree 4095 it means that any 4096 elements are enough to reconstruct F so even if some of the elements of the extended data

blob get corrupted you can still reconstruct the original polynomial and reconstruct your data blob so that allows us to do the dispersion of data what we can do is we're going to take this extended Vector whether a 8192 elements and we're gonna give each validator one element of this Vector now if some of the validators go Byzantine go missing they drop their fragments as long as 50 percent of validators are honest and correctly keep their fragments we can always reconstruct all of the data from just 50 percent of it just because of those properties on the polynomial that any half of the elements

are enough to reconstruct f all right so this is an initial idea we're going to make it more efficient but for now the commitment to the polynomial f is going to be fully replicated to the validator set but the actual Vector is going to be split into fragments and each validator is going to get one evaluation of this polynomial the question is how the validators know that they got correct fragments well they get the commitment opening proofs for their fragments From the Block Builder so the block Builder is gonna do some heavy computation to not only extend the data block by evaluating the polynomial points dispersing the elements to the validators it will also

produce evaluation opening proofs to convince the validators that the fragments that they got correspond to the actual commitments so how do we apply these ideas to multiple data blobs or a block because it's not very useful for a single Vector oh it's pretty straightforward so ending sharding the number of data blobs is up to 256 so that's about 32x increase from rotor then charting so we're going to extend each data blob individually the same we explained before and then we're going to split the extended block into columns and each file data will receive a column of this extended block so as long as 50 of validators are honest they can always piece the blog back together

because every row can be interpolated and can be corrected for erasures if you only have 50 of elements in it so then trading goes a step further this game already works there is one annoying part where you might want to use some more complicated tools and that's the locality of the Reconstruction so right now if the validator is missing its column the way to get it back is to try to reconstruct the whole block effectively so this poor validator will have to talk to the whole validator set to try to get 50 of columns than it do the interpolation to reconstruct his missing fragment so that's not great

because the blocks and the index running are really large those are 30 megabyte blocks so that's gonna take a lot of effort on the volunteer side and the hope is that validators can be really light that this will not add a lot of burden on the validators so for that bank trading does another step so let me explain how ding shrouding achieves local reconstructability how do we make sure that the validators can reconstruct its missing fragment with few other fragments without going into the full valid reset without doing full reconstruction right so right now the father's Museum's fragment needs to reconstruct the whole block but to get local reconstruction uh doing charting needs two additional properties of the commitment scheme it

needs homomorphism of the commitments so the commitment to what the polynomial f plus the commitment to polynomial gives you the commitment to polynomial f plus G so you can add up the commitment and this will cause the polynomials to add up kcg commitments are homomorphic bulletproof commitments are homomorphic frag commitments are not for example so we have plenty of examples of homomorphic commitments and that's what we gonna need for this step for the entrading and the other property we will need this homomorphism on the proofs and that's a tricky property and we only know of kcg commitments that achieve both the chief homomorphism on the commitments and horses with the proofs unfortunately kcg commitments require a

trusted setup so that's an open problem of how to construct the commitment scheme with births properties without a trusted setup there's some work being done in the groups of unknown order that's pretty recent but the homomorphism of the proofs property says that you can add the proofs so you can now take the Opera proof for the polynomial F and point Alpha and you can add it to the proof for the polynomial G at Point Alpha and this will effectively be the same proof as for the opening of the sum of the polynomials okay so those two homomorphic properties are required to make Deng sharding achieve local reconstructability so here is how this property is used so

the way explained it before we were using univariate polynomials and we were evaluating those univariate polynomials at more points to create this extension on the right now you can also treat the whole block as a bivariate polynomial so you can fit a bivariate polynomial D through this left part and evaluated at more points on the right and you can also evaluate it at more points extending down now extension to the right is equivalent to the univariate case but extension down can also be done in a univariate fashion if you fit a univariate polynomial through each column and evaluated more points but it's much nicer to view it as a bivariate

polynomial evaluation so that's how it's done you basically do 2x expansion to the right into X expansion down and now with this expanded block each voltage is going to get two rows and two columns of data so let me just explain a little more detail each validator is getting from the Builder all of the commitments so C1 through c256 also commitments to the vectors of the original block now it also gets from the Builder two rows of extended block and two columns columns will be slightly larger it's going to be a Columns of width 16 this is done in order to make this game a little bit more efficient because you can do

Evolution opening proof on 16 elements and they're also going to be short so the proof size for opening 16 elements is the same as a proof size opening a single element it also is more friendly to the network because you're sending a little bit more data so your packets are more full that's just a technicality for why it's 16 bits column but you can think of it as the validator getting two rows and two columns so that's about two megabytes per validator per block now to verify the elements in the bottom half we need the commitment scheme to be homorphic because those extension is a linear transformation on the Block wherever you're interpolating the polynomial and evaluating at more points

that's actually a linear transformation on the vectors that you are doing so you can translate this linear transformation and extend the vector of polynomials to also cover the bottom half rows of this Matrix and that's how you can verify that you actually got the correct row that your raw corresponds to the commitments you can use the homorphism to extend these commitments and then check that your row commits to the extended commit but for the columns each while there is going to get the proofs from the Builder and it again for those at the bottom part it's going to just check against the commitments this green commitments for the top part and for the bottom part the commitments are going to be extended and you're going to be checking against against this bottom commitments

each validator can now locally reconstruct its missing pieces so if the validator say is missing a column it's going to ask other validators who are storing the rows and who are intersecting obviously at the column of the validator to supply this validator with fragments of his column and the moment it gets 50 percent of elements in the column it will be able to reconstruct and fulfill the whole column and that's where we need homorphism on the proofs as well because when you are fulfilling elements of the column you also want to fulfill proofs for this elements then fulfilling the proofs will require homomorphism for the proofs so that's how local reconstructability works

so again the properties that we need from the commitment scheme from during trading is from morphism on the commitments how morphism on the proofs and only kcg has both properties so the reason then trading extends the block both ways it extends right to get resilience against malicious 50 of validators because values are getting columns and half of the validators can forget their columns you will still be able to reconstruct the original block and then trading extends down in order to get local reconstruction in order to allow the validators to reconstruct the missing columns or rows without doing full block reconstruction so let's talk about reconstruction briefly the way it's proposed to be done in Deng charting is if 75 of elements in

the block are there then at least one incomplete row or column will be reconstructable we'll have at least 50 percent of elements in it so you'll find such a raw raw column and you will reconstruct it basically patching your Gap then you will find maybe a column with 50 of elements and you will patch that and you will repeat this iterative process until you reconstruct all the missing pieces now we know that we require 75 of the Block in the worst case and the worst case is here if you're having 75 of the block and this is the yellow part minus some tiny strip minus Epsilon so you're missing a little bit of this corner here

so this yellow area including the striped one is 75 minus Epsilon so given only this area you will not be able to patch and reconstruct this missing white quarter because none of the rows or columns will have 50 of elements in it and this worst case is very real because validators are getting rows and columns so it might happen that the data goes missing in exactly this pattern and you get this worst case so while exploring this with Dan Benet we wrote the blog post by the way that you can check out on the a16z website but we also had a proposal there of improving the Reconstruction by having

the validators instead of storing rows and columns store some randomly dispersed data from the blog so let me explain in a few words how it works so instead of going through raw and column wise reconstruction we can go through bivariate interpolation so instead of doing this iterative process where you're finding incomplete rows and columns you try to reconstruct your bivariate polynomial as a whole so this new method allows to reconstruct from 25 with high probability when this 25 percent are randomly distributed across a block so instead of rows and columns the validators will propose to give the validators random elements from the

block it remains an open question however how to do bivariate interpolation efficiently so let me show you a vulnerable term algorithm for bivarian interpolation but it's not good enough for us so if each father gets random elements of the block the elements from honest validators are going to be randomly distributed across the block so your task is not to patch for the missing white elements so the yellow are the elements that you have and the white elements are the ones that are missing so the polynomial that we are seeking for is a polynomial of two variables it has degree n minus 1 in each variable so it has N squared coefficients and given N squared random evaluations we need to obtain the coefficients of this

polynomial so each Evolution that we have here those elements that are present gives us a single linear equation on the coefficients of this polynomial so here the coordinates X Y you can write the equation on the coefficients of this polynomial so each element gives one equation so now we can write it as a system of equations so those are our unknowns the coefficients of the polynomial The Matrix m is constructed this way from the coordinates of the evolution points i1 J1 I2 J2 Etc so they're going to be N squared points that are present in the block N squared unknown so you should

theoretically be able to find those unknowns given those N squared evaluations on the left and indeed the solving linear system we know how to do it in polynomial time for General major sales day it takes time n to the 2.37 if you use the best algorithms in our case however n is really large it's 2 to the 32 so the size of this Matrix is 128 gigabytes so that's not a practical approach although it's kind of an efficient algorithm just for our sizes it's not suitable but we know that the Matrix is very structured so the better algorithms should exist so it would be nice to come up with a better vibrate interpolation algorithms and this will improve the Reconstruction now let me talk about that availability

assembly and how it fits into the picture for the uncharting so in being trading the blocks are reconstructible from 75 percent or possibly lower if we can make bivarity interpolation faster so to understand whether the block is available the sampling client is kind of gonna throw random darts into this block Matrix hoping to find out any missing pieces so the sampling client will request random element of the blog will send the code in an IJ to the validator set and the validator set is going to reply with the value of the polynomial d i j and the proof we assume here that the clients have the commitment to the block so it will be able to verify that it got back

the correct value so the probability that the value comes back and it is cracked but the block is unavailable is 0.75 and that matches the 75 so imagine that your block is unavailable so more than 25 percent of it is missing only 75 minus Epsilon is present so the probability that you in the present element yet too much of the block is missing for reconstruction is 0.75 the probability that you do it again so you do it two times in a row is 0.75 squared and by repeating the sampling you can amplify this probability and goes down exponentially quickly so you can make it negligible with small number of queries

and if with bivariate interpolation we can improve on the 75 percent make it 25 then the probability will go down even faster so data availability sampling allows our client to verify whether the data is available without basically knowing any information about the validator set without knowing the public use of the validators without verifying any signatures by just simply throwing as this darts into the block and verifying that it got back correct values from the set and this is also going to underline the consensus design in ethereum because data availability or dank sharding is going to be blended into the consensus protocol so each validator during the

attestation phase in the consensus will attest to the block BN only if the two conditions are met if the SWA data has sampled all the previous blocks and the sampling was successful so with good probability the validator is convinced that all the previous blocks are available so it determines availability of the previous blocks and it also attests if it received correct fragments of all the previous blocks so this green lines two rows and two columns each validator gets are for each block and it needs to verify that those conform to the commitments if those two conditions and map then the validator attached to a block b n and that's happening in addition to what ethereum consensus is

doing right now which is verifying and rewriting all the transactions within the block it will also verify that this additional data that we're adding with dink charting is available alright so that's all I have here are the different disclosures to check out hope you enjoyed this presentation and please check out the blog post that we wrote within ballet and yeah let us know your thoughts