ZK Paris: Panel - DAS with Tom Walton-Pocock, Benedikt Wagner and Dankrad Feist

Transcript

okay moving on to our panel on Das with our moderator Tom Walton pocock and panelists um Benedict Wagner and dank red Feist [Applause] y I can never hear me great so we're here to learn uh the latest in the state of data availability research

on ethereum um so very excited to be joined by Benedict and dunkrat both of whom will introduce themselves and they'll do it in a slightly broken fashion so we're going to have a 10 minute introduction uh from Benedict who's kindly prepared some slides about the research that he's been doing uh formalizing um uh sort of security reasoning about around EAS and and then we'll get to Dan crowd about 10 minutes in so over to you Benedict yeah so I'm Benedict I did an internship with ethereum Foundation to to do this work on data availability sampling and uh when I'm not doing this internship I'm a PhD student at cispa in Germany doing cryptography

I'm Dan cut I'm a core researcher um with the SIM foundation and yeah I've done things on data availability statelessness and some other things okay so do I have a clicker okay yeah so what I want to do in the beginning is I want to uh say some words about this this work and get everyone on the same page about data availability sampling so this is a joint work with Matthias and Mark and the short version is we did some theoretical foundation for data availability sampling so we gave a cryptographic security definition what is this what does it mean and that's what I want to quickly motivate so ah I see so this is PDF not key okay so

so you have to imagine that there are animations right so so uh what is data availability sampling so typically we assume we have some peer-to-peer Network that is running a blockchain and now we have a party uh Alice the proposer here that has a block along with the corresponding header and now this block should be sent to the blockchain um and yeah that that's the basic setting but now we also have parties that we call clients or light clients and these parties don't download the entire block they only download the header so if there were an animation the header would now go to the client and um they still want to take part in the

protocol so they want to verify that the block Associated to that header is correct and it turns out that you can reduce this problem sort of to the the question of whether the block is available in the first place so these clients want to make some queries to the network to find out whether the data or the block is available okay that's the setting so in some sense this client acts as a verifier for the statement that the data is available and now this this phrase the data is available is not really precise so that's sort of the motivating question for our work um what does it mean that data is available how can we formalize this and when we have that how can we construct such schemes efficiently

okay so I want to give an introduction to how how you could do this by looking at two examples so the first one is a very naive way of doing it let's say Alice has her K chunks of data now she she commits to them using a Merkel tree and the root will be the block header that is then downloaded by the clients okay now the slides are really broken so what happens is the data is sent to the network and the clients query random positions of this data okay and then they get back not only the data itself but also the um corresponding Miracle path and this ensures that two different clients get

consistent responses okay so this is the basic scheme you query random positions but this is actually not a good scheme and yeah so so the reason is if I if I were to just delete one chunk of this data then the probability that you see this is one over K so if you want a constant probability of detecting this you need to download as much data as you would have if you just download the entire Block in the first place so that's not a good scheme and the reason is really that we didn't add any redundancy so if I delete something on the network then the data is no longer fully available and that's the second construction that we that we look at so

here I add redundancy to this by encoding the data using a read Solomon code so what does that mean I evaluate a polynomial F that is defined by this data and I evaluate it not only at K points but at let's say 2K points so I added some redundant C and now this the rest is still the same the clients query random positions now you replace the Merkel tree with a kcg commitment because we are dealing with polynomials here so that kind of makes sense and now it turns out that to make the data unavailable you need to delete half of it right because from every K points I can interpolate this polynomial and get back the data and so this is a much better scheme because now if you do one

query you already have a probability of one half of detecting this that the data is unavailable okay but actually if we look at this then the question is the secure Still Remains and from a cryptographer's perspective this question doesn't even make sense if we don't have a good security definition so we need some definition of what is data availability sampling precisely and what does it mean that it's secure in particular we need to specify what the attacker is allowed to do for example if the attacker controls the network can it respond adaptively or non-adaptively to these queries of the clients and then once we have that we also want to see I mean this is a better system than the one

before but can we quantify that can we have sort of a parameter that tells us how much better is this this is sort of what we do in our work so our work focuses on two questions and that's where we started so first what is a data availability sampling scheme like cryptographically and then formally and how can we construct it in terms of the definition well we came up with a I would say quite clean and simple definition what is the syntax of a data availability sampling scheme what are the security properties that you that these schemes should satisfy and how do you compare these schemes what are the parameters that are interesting and then we looked at constructions and

this is quite interesting we looked at the constructions that were already proposed for example the the two that we that we saw in the previous slides and also the one envisioned by by ethereum and we saw they all follow a common Paradigm and this Paradigm is basically you can summarize it as data availability sampling from Erasure code commitments so Erasure code commitments are a generalization of polynomial commitments that we defined and once we had that this sort of compiler taking an Erasure code and an Associated Erasure code commitment we looked at concrete constructions and proved them secure and also came up with new constructions so this includes the read Solomon based construction that we

have seen on the previous slide but also the sort of two-dimensional version of it with the tensor code and the sort of row wise commitment this is what ethereum wants to use but also we have some new constructions for example a construction that is purely based on hash functions and does not need for example a trusted setup yeah so that's a quick summary of our work and now I'm happy to move on to the panel if you want to look at this this is on ePrint and you can either ask questions about it today or just send me an email I'm happy to talk about it [Applause] great thanks Benedict

um okay so maybe to kick this off and before we go deeply into the cryptographic derivatives that underpin these kind of um these proposals which I guess have started to surface well it's from what I was aware of maybe three years ago on the ethereum research Channel could you maybe take us through the the principal research challenges of implementing DS at a very high level to start with and then we can then we can dig into the derivatives um sure so yeah so what I mean data available is something uh fundamentally changes the way we think like we we used to think of data availability as a given

like it was always um like in in ethereum or Bitcoin everyone just downloads all the blocks and so there was never any questions about it um so when we uh when we think about Das it's really a technique to sample that guarantee that currently exists and make it so that we can apply it to much larger amounts of data um I would say by now the like the cryptography of it is very well solved like since since basically I mean like four years ago or so uh polynomial commitments were very difficult to compute there were a lot of questions about how to compute

um so many proofs and all that and we've made huge progress on that so like I think back in 2019 when I first looked at this it was like oh yeah this is cool but it's never gonna work like nobody can actually compute the stuff now that's like completely different it's like completely practical and almost uh trivial and so I would say like from the cryptography side we've pretty much solved it with some exceptions which I can come to later um and the difficult part right now is the other thing that changes completely with dis is that so far um everything we do in blockchains is basically broadcast like we always gossip blocks to all the nodes on the network dis fundamentally changes that

because for the first time we have a construct action where nodes will have to request specific things that only they want and nobody else or few other people are interested in and so getting the kind of networking techniques such as this with hash tables to the security levels that we require in blockchain is currently the biggest challenge and you mentioned uh in that so when you first started looking at this the the the the the proof the sort of the proofs to construct these polynomials and these polynomials were too too long can you just go a little bit more into I think there are two key Concepts here one is this concept of Erasure coding and then

the other is the sort of the constructions these polynomials in case of G schemes I wonder whether you could just explain how we are compiling them how are we putting these these things together to what extent we are and uh and and could you maybe put some numbers on you know what were the sizes of these polynomials going to be if we had sort of these sort of staying in the 1D setting what how big were these things going to be and how uncomputable were they going to be right so okay so to quickly go back to that um Benedict already made an intro to that so what we fundamentally need um for dis is um is we need to Erasure code the data and um the simplest some of the simplest Erasure codes are read Solomon codes

which are based on on polynomial polynomial interpolation and so that is very lucky in some ways because we have this really elegant cryptographic construction which is KCT commitments which allow us to commit to polynomials um so um yeah so the way okay so and now the way to think about this so basically we want to currently our goal is to have about 32 megabytes of data in each ethereum block once we implement this um and like practically like I mean yes like a few years back I think the expectation was that it would take like minutes to

compute these commitments but especially like the the more the more difficult part is now you have all these tens of thousands of samples that you want to pick and each of these comes with a proof and that proof is essentially as difficult to compute as a commitment so that's what made the made it very daunting and the big progress that was made is actually it was uh like a breakthrough by dimitry and then I refined some parts of it which by Dimitri covertovic which basically allowed us to compute all of these proofs together very efficiently and that made it about like a thousand times more efficient and actually made it practical and Benedict so when we were preparing for this panel

um you alluded to um the they're being sort of some interesting subtleties in the application of error correcting codes to Da I wonder whether you could elaborate a little bit on that yeah so I mean what Dan Kratz said is that you can take the read Solomon code and use the kcg commitment right and what the kcg commitment guarantees is that whenever sort of an adversary opens this commitment at some positions then whatever he does is always consistent with the read Solomon code so whatever he does it will always be on a degree K polynomial let's say and now if you look at look at our compiler the one that I mentioned where you're taking Erasure code and and a racial code commitment

and get data availability sampling then you need to have a similar property you need you need to let's say I have a better at some point we may have a better Erasure code than read Solomon just hypothetically then you need a new commitment and that constructing that commitment is challenging because you need to have a similarly strong property as what you have for kcg right so in our new construction for example uh making that work just from hash functions was a bit challenging but yeah got it and so um just I'm probably most people in the room will be familiar with this but a commitment as you say being the the sort of a a binding

representative quote unquote of a polynomial and then an opening being an evaluation yes along with a corresponding sort of opening proof that convinces you this evaluation is consistent with the commitment um so uh then I guess uh and you'll have to remind me of dates here but I guess a couple of years ago maybe a bit more uh there was this introduction of the notion of 2D schemes so um I I guess is this maybe one more for dunk red um but could you explain what are these 2D scheme first of all can you give us a can you give us a picture in our minds can you give us a grid where chunks and where are blobs and where are the

polynomials can we can we have a sort of a like a mental a mental map of where all this data is and how is it advancing on 1D schemes um yeah so this is really um a subtlety which comes from ethereum's very strong desire towards a decentralization so when you think about um the scheme that we presented where we have like we sample some uh some chunks of data and like if enough of them available we know enough will be available to reconstruct all the data now there's one problem with that which is yes you know the data is available but who's going to take the data and actually reconstruct the whole thing

reconstruct the polynomial and give everyone all the samples because ultimately we need agreement right like in a blockchain at the end everyone should agree whether a block is available or not that means when a block is available we need to get all the chunks so that everyone can get all of their samples being available okay so here comes the subtlety which is like it might be so much data that is just nobody out there who can do that step and if we don't want to require on some uh some sort of altruistic super nodes doing that then we need to put that into the range of like the kind of nodes that normal people are running and this is where the 2D scheme comes into play which is that we want the property that

much smaller amounts of data can be locally reconstructed so we want like a an eraser code that can that allows locally with some samples to reconstruct some part of it and if enough people do that then the whole thing can be reconstructed so this is why we need 2D schemes or other schemes that are locally reconstructable so there are other ideas out there but but so far like for for several practical reasons it still seems like the simple 2D scheme where you just have many many rows of polynomials that you commit to with kcd commitments seems to be the most elegant one can I just tease this out a little bit further so so in that mental grid of the chunks and the blobs and the polynomials

how because I think it's sort of it's it will be uh maybe sort of obvious why we need to sort of first of all reduce down data into smaller smaller pieces and then sort of make sure that there are more people available to sort of construct those into larger pieces um but can we be sort of a sort of a bit more concrete about um what are the bits of data I know that the definition of chunks and blobs kind of has a lot of the content taken out of the out of it and I guess that's one of the hard things because we have is there a worked example you're able to to to to give to sort of explain here's a bit of data it's held by this node it's requested by this other node I mean that that's like

it's kind of irrelevant for data MLB sampling um but uh I think so I mean concretely like that that are like basically engineering parameters that needs to be worked out but yeah so like the way we're thinking about it is that um that um validators will be responsible for like uh rows and columns in some ways they will distribute them they will fill in the gaps if there are any and then all the samples will be put into some big networking structure probably a DHT but that's like also something that's like currently like active research and then like everyone can sample from that

big DHT yeah so just to add in in that spirit so in our in our formal model we don't explicitly model where which part of the encoding is stored so we just say this is the network you somehow have a way to have random access to the encoding and then we analyze sort of starting from there um so I guess the question to uh to both of you um is what are the um I understand obviously Bendix be spending a lot of time on on sort of Shoring up the um sort of security sort of guarantees the formalisms of these systems

um what are the future research Avenues uh currently that will likely be available to you after 4844 um where's that likely to to go in the future yeah so just to talk for my co-authors and me we have we have some sort of open questions because when we when we looked at all these constructions what we found is that there are many techniques from uh so-called proximity testing that you could that you can use and our hash based construction also uses these techniques and um now the question is really what is the what is the relation between proximity testing and data availability sampling so they are not exactly the same but we have sort of the

feeling that there is some relation and if we can if we can understand this relation formally then we can also take advantage of of the rich literature and all the knowledge on proximity testing and use that and proximity testing being sort of showing yeah so so the the idea of proximity testing is you have a you have a a long string and you want to show approver wants to show to a verifier that this long string is close to a codeword and that's exactly sort of the difference to data availability sampling so what I said before is whenever you you open some positions when you have the these clients query them you have to make sure that it's a hundred percent

consistent with the code otherwise our analysis doesn't go through and these proximity tests only ensure that it's somewhat close to the code and so there there is some relation but really making this formal uh is left for future work and downgrad uh where's where are you seeing some research yeah after the the upgrade yeah I think what Benedict mentions like a very interesting point like what um basically I think like we have a very good solution uh in the pre-quantum world right now with kcg commitments they're just amazingly elegant um we don't have a very good solution

post quantum I mean there's the obvious one which is you just um like use a Stark and Stark like a big local tree um it's might be possible might be good enough in the end then we don't have a problem if that's not good enough then currently yeah we have thought a lot about using fry which is like this proximity testing we haven't found a full solution it's like there's they are exactly like some little niggles about you never know you know exactly that you're not polynomial and only know you're almost on it and that's in many ways often not quite good enough alternatively we can think about other other kinds of post Quantum polynomial commitments or commitments to any kind

of um uh yeah eraser code so yeah that would be that would be good things to think about for the future another very interesting thing is like are there better locally reconstructible codes for our purposes like right now we're using this 2D code it has the disadvantage that it has like a very high Los loss on the encoding coding rate so we are like extending by a factor of four but we actually need three quarters of the data to guarantee local reconstruction which is like a bit of a loss there um so yeah that would be interesting like crypto cryptographic Avenues to explore in addition to what I mentioned earlier about the networking yeah maybe

to add to that so one construction that is post Quantum is our hash based construction right but it's in terms of how large are the how large is the the chunk of data that I have to send to the clients it's much less efficient than than kcg it has some other advantages but that's definitely one way to to explore this and this local reconstructability I think this is something we first have to formalize as well right so our our definition and I mean our definition is already quite General but this is some aspect that is not yet captured by our definition so that's also interesting for future work so I'm actually I'm going to now given

in the interest of time we are running slightly behind but not not as badly behind as we're budgeted for so that's good news um but I think we'll open it up to the floor for questions this question might make no sense because my understanding of dank charting might be off but you have this two-dimensional uh table now to try being uh end data Blobs of size d for instance and you do the the kdj extension um on uh horizontally so basically like you trade you take a deep pointer into two D points you do this uh end times and then you uh yeah and then you extend vertically as well I guess my question is is this

might be totally wrong it's like you do the commitments both on the x-axis and the and the y-axis why is this this fourth quadrant the the 2D points also on the same polynomial polynomial of like d degree in the very last between quadrants two and four what I'm saying like why is this also a polynomial vertically because you constructed it like this and like this up if you think of it as um like if you think of the first quadrant as a two-dimensional polynomial in X and Y then there is only one polynomial that extends into the fourth quadrant so it doesn't matter which way you extend it gray panel uh congratulations on your

research as I recall originally when this proposal was published it required some form of PBS is that still the case that you would need PBS to implement something like this or could you do it without proposed or built or separation so I think practically we will need PBS anyway so it is best to Simply think about like it's by far the easiest if you implement it that way because you will simply like um get someone so we have we have for example like in our GPU implementation of like Computing the encoding that takes about five seconds to do that on

like a moderate consumer grade GPU like that costs a thousand dollars um we want to get that down to one second and we're fairly happy with it um so this is completely fine to require of a builder to have this this would not be fine to require this of like an a general validator to have it um but anyway I wouldn't want a validate to have all this data so that doesn't even matter they wouldn't even be able to compute it anyway so basically your problem becomes quite different it's not impossible like we there are definitely ways to solve this with some more like um networking techniques and there are people who want to work on this I think we don't want to think about it from the

protocol perspective so what I would say is like I assume that the proposer has to do this but they can use a different distributed technique to compute it if they want to but it will probably be slightly riskier can you talk um probably really naive question um is there any penalty associated with being unable to serve a data availability proof and is there some kind of time limit on it like are we always querying the latest block so there's no such thing as a data availability proof they're only sounds PCG proof no the kids Jeep the kcg commitments are part of the blocks so they will be

distributed by everyone will have them the samples have the kcg proofs but you cannot punish someone for not having a sample because you don't know why they don't have the sample you can potentially like the best you can downgrade them as a peer you can say if you know that the data is available like if everyone else has the data but one peer doesn't have their sample you could say well there might be a bad peer but that's about what you can do like there's no way to slash them or anything like that foreign this is also probably a undergrad level

question but can you expand on why there's no such thing as a proof like why doesn't Fiat shmir work maybe the answer is just it's a network but can you uh expand them why we can't make it not Interactive I can barely hear that question can you can you just expand on why we can't make it a proof why it has to be interactive why why do we have to like query the network repeatedly why you can't make what the the data availability is sampling into a data availability proof so what are you going to prove that that sufficient portion of the network has access to the block how do you prove something about the network

I don't know that's that's my question I guess like that's the thing you can prove that you have some data you can have someone else sign let's sign off that they have some data but we don't want to rely on any honest majority guarantees so that's not good enough so ultimately we need to we need nodes to be themselves able to formula to have an opinion on whether the data is available so yes like if you want to rely on an honest majority assumption data available is very easy it's trivial like anyone can do that you just you don't even need to do encoding you just sample let every validator sample some parts of the data vote on whether it's

available if everyone votes is available yes honest majority trivial like but the guarantee that's not good enough for a blockchain you want that the valid data set cannot fool the other full nodes even if they all collude so that's that's why it's more difficult is that it I think we're done thanks very much thank you thank you