Of data availability & danksharding

Robert: Hi everyone, Robert Hackett back here again with another episode for web3 with a16z. I recently chatted live with some of our researchers on the topic of Data Availability Sampling and Danksharding – which is relevant to blockchain scaling, as well as paving the way for more advanced blockchain networks & user applications. While much of the discussion is especially relevant to Ethereum, some of the concepts we cover are also applicable to advances in computing and networking generally. 

This discussion involves some specific math, which we cover (and briefly explain) in the episode.

For quick context as you listen, “polynomial commitments”, which you’ll hear more about, are a tool that helps reduce the amount of data needed to verify complex computations. And “interpolation”, another term you’ll be hearing, is a way to reconstruct data from a limited set of data points.

Be sure to check out the paper referenced in this episode for a deeper explanation at a16zcrypto.com/das – that’s DAS for data availability sampling. As always, none of the following is investment, business, legal or tax advice. See a16z.com/disclosures for more important information, including a link to a list of our investments.

Robert: Okay, so today we’re going to be talking about data availability sampling and danksharding. Now, if you’re unfamiliar with those things, don’t be scared because I’m here with a couple of experts who are gonna break things down for you. We’ve got Dan Boneh, Stanford professor, eminent cryptographer, and a16z crypto research advisor, and Lera Nikolaenko, research partner at a16z crypto.

Lera: Great to be here. Thanks, Robert. 

Dan: Thanks, Robert. Great to be here. 

Robert: Thanks, Lera. Thanks, Dan. So, as mentioned, Dan and Lera recently wrote up a great post and have a proposal related to ways to improve protodanksharding, which is this upgrade that is planned for later this year in Ethereum. There is a lot of rich detail in that post, so we’ll dig in there.

But before we get into all the details, I thought maybe we could zoom out and back up and start with a bigger picture here. So let’s start with Dan. Help us understand the subject of today’s talk, data availability sampling. And maybe you could do it without breaking anyone’s minds here.

Maybe we could keep it as you know, succinct and accessible to a broader audience as you might be able to. 

Dan: Sure, so maybe we can zoom out a little bit before we talk about data availability sampling. Maybe let’s talk about the general goal here. So this is part of the efforts to scale Ethereum.

And so one of the ways to scale Ethereum is using rollups. And rollups actually need to push a lot of data on chain. So a rollup allows you to take, say, a hundred or a thousand transactions and process them all as a single transaction on the Ethereum Layer 1. And then all the data associated with those transactions basically gets pushed on chain.

And as a result, there’s a need to actually store quite a lot of data on chain. And the question is how to do that. And that’s exactly where danksharding comes into play. So it’s a really beautiful, beautiful idea. It came from the Ethereum Foundation, particularly from Dankrad Feist. It’s a really elegant construction and basically Lera and I wanted to give an overview of how this construction works and potentially look at some options in which it may be, can be improved a little bit.

Lera: Yeah. Rollups essentially allow execution to scale for Ethereum, but the question is, How do you make the data scale? And danksharding/data availability sampling basically adds this missing piece to Ethereum that will allow it to achieve full scaling. This post is kind of quite technical. Some aspects we don’t explore, like networking, which is also interesting to research and to write about, but we are mainly focusing on the cryptographic aspects of danksharding.

Dan: And I would actually even add that there’s really beautiful open questions that are still left to think about for researchers if you are interested in this area. There are beautiful questions around coding and polynomial commitments. There are really quite interesting questions. If they could be resolved, we would end up with even more efficient systems.

Robert: That’s excellent context. I definitely want to ask you about those open areas for potential inquiry in a little bit. But before we do that, let’s talk more about this proposal that would free up space on the Ethereum blockchain. So the blockchain is basically this giant record of transactions happening from the time that this system launched way back when to the Genesis block. How are developers thinking about freeing up space, making it get greater throughput, scalability, cheaper transactions, all of these things that sound great and would make the system much more usable. How do you actually get there? What is required to get these efficiency gains? 

Lera: I think the main challenge is that you cannot just ask validators to store more data. It won’t get you too far. If you want to scale the blockchain to increase the block size by several orders of magnitude, you have to split your block and disperse it to validators so that each validator only stores some fragment of the block. There’s where the ideas from error correcting and erasure coding comes in that allows you to do that.

So basically increasing the block size without putting too much burden on the validators. I would say that’s the main technical difficulty. That’s what danksharding is solving.

Robert: You mentioned erasure coding, and it sounds like that’s a key piece of this technology that enables it to work. Maybe you could provide some more detail there. What is erasure coding? How does it work, and how does it apply in this context? 

Lera: Sure, absolutely. So you basically take a block with users’ data and you expand it. You erasure code it, turn a smaller block into a larger block, and this larger block can tolerate some omissions from it. So you can lose some portion of the block.

In the case of danksharding, you can lose 25% of the block and still be able to reconstruct these missing pieces from what you have. So when you disperse this expanded block to the validators – and the validators go down because some of them are byzantine or faulty – you can still reconstruct from those validators and that’s okay if they go down and they lose their pieces, the rest of the validators who are still online and still honest can recover those missing pieces. And that’s why the properties of erasure coding are useful here, just to substitute for byzantine or faulty validators. 

Dan: And maybe we can even explain it a bit more with an analogy. It’s like, you know, if you’re watching a Netflix movie and say, you know, the Netflix servers are sending packets to your computer and you are watching the movie, well imagine 10% of the packets actually don’t make it through and your computer only gets to see 90% of the packets.

So, normally you would start to see all sorts of lossy video and degradation in performance. With erasure coding, what happens is if the movie is coded using an erasure code, even if only 90% of the packets get through the laptop has enough information to actually reconstruct the entire movie.

What’s interesting is erasure coding is used everywhere, like communication networks wouldn’t be able to work without erasure coding. And maybe again, just another example, when you have a deep space probe, it’s sending messages back to earth. There’s a lot of noise and a lot of them get either dropped or they get garbled, and yet on Earth we’re able to recover the signal and get those crisp images from Mars.

That actually also is done using a slightly stronger technique called error correcting codes, where we’re not only losing packets, but also we are recovering from packets being distorted, being changed in value. What’s interesting in the context of the blockchain is that all the data is being signed. So we actually don’t care so much about data corruption because the signature layer will detect data corruption.

So really all we care about, the only thing that a malicious node can do – someone who’s trying to prevent the data from being reconstructed – the only thing that that node can do is, in some sense, remove pieces that make up the data. So we don’t care so much about recovering from corruption of the data because that’s taken care of by the signature.

But we do worry quite a lot about pieces of the data simply missing, and as a result, maybe whoever’s trying to reconstruct the data is not able to do it. And so that’s exactly where erasure coding comes in, where we know that the only thing that can happen is that a certain piece of the data is missing. It can’t be garbled. So if we got it, we got the right one, and that’s because of the signature. But if it’s missing, we have to somehow recover. And that’s exactly as Lera was saying, that’s the idea of erasure coding. 

The way you do that is basically you take your original data – in the case of Ethereum, you would take a block and you would expand it a little bit.

Actually, you expand it by like a factor of four to get more data in the block, so that the data is now redundant in the block, and now you break it into little pieces. Now you can ask every validator, “Oh, you know, you don’t have to store the entire block – you only have to store this small piece of the block.”

And if enough validators do their job and store those little pieces – and when we need to reconstruct the block, they send those pieces back to us – if enough pieces get back, then we are able to reconstruct the entire block. In danksharding in particular – again, it’s a beautiful, beautiful proposal – the recovery rate is 75%. So if 75% of the validators respond and we’re able to recover 75% of the pieces, then we’re able to reconstruct the entire block. That’s kind of the core mechanism that’s used in danksharding.

Robert: That’s really useful. So it sounds like erasure coding is this kind of technique that enables you to apply some redundancy and backups so that you don’t lose all of the data so that you can still sort of assemble it, get access to it, see that it exists.

Dan, you mentioned that the reason for doing this data availability sampling is to prevent bad actors from doing certain things, like getting rid of some of the data. What exactly are we defending against here?

Dan: Yeah, that’s a great place to go next. So in fact, what happens is, with these proposals for solving the data problem on Ethereum, there’s gonna be a new transaction type that’s going to be introduced.

This is called a “blob-carrying transaction”, and what it would allow folks to do is basically embed blobs. Each blob is 128 kilobytes. So you embed blobs into blocks. So normally blocks are made up of transactions to do all sorts of things to the Ethereum state. So now, in addition to just the regular transactions that we know and love, there’s also going to be a blob-carrying transaction or a few blob-carrying transactions per block and as I said, each one is gonna be 128 kilobytes.

Now the long-term plan, and actually maybe Lera can talk about the transition to how we get there, but the long-term plan is that there could be quite a few data-carrying blobs in every block, which would actually make the block quite large, right? I mean, each blob is 128 kilobytes.

If you put a bunch of those together, you could end up, actually, you will end up with blocks that are 30 megabytes – and it’s just not reasonable to ask validators to store these huge blocks. Today, the blocks are only a hundred kilobytes or so, so these would be much, much larger blocks. And so the idea is to basically break up these large blocks into little pieces.

Every validator, every node will actually store only this little piece. And now the problem is, what happens if they say that they stored the piece, but in fact they didn’t? Right? What do we do then? And that’s exactly where data availability sampling comes in, which is a very efficient way to test at block creation time that, in fact, everybody received their pieces, everybody currently has their pieces, and currently the block can be reconstructed even though it was broken into many, many small pieces. And these pieces are stored, distributed across the network.

Robert: And just before Lera takes over, I just want to make sure that I understand something here. So you said blocks today are about 100 kilobytes. And the idea is that, after all these upgrades, they’re going to be about 30 megabytes. And part of the reason for that expansion of the block size is to accommodate this new type of data, this blob data, that has a different purpose than what you usually shove into blocks, which is just pure transaction data.

And this blob data is really related to helping these off-chain Layer 2 networks store some data in a more ephemeral manner. Did I get that right?

Dan: Yeah, I’m glad you reiterated that cause that’s important. So these blobs basically are gonna be used by these rollups, right? So the rollups have to store the rollup data.

And so instead today what they do is they store it as what’s called “call data”, which is somewhat expensive and not what call data was meant for. So instead, they’re gonna store this data as blobs in blocks. And what’s interesting is these blobs are actually not going to be available to the execution layer of Ethereum.

They’re just gonna be stored as blobs in blocks. The execution layer will only see hashes of these big blobs. They won’t be able to access individual bytes or elements in the blobs, which is the new mechanism. So today, the way this is stored, is, as we said, in call data, and call data, is all available to the execution layer of Ethereum.

So because of this simplification, storing blob data is going to be a lot cheaper than [storing] call data. So in principle, the goal of this is to reduce the costs of Layer 2 systems, right? Because today they have to pay quite a lot to store all their data as call data. In the future, once danksharding is deployed, or even once protodanksharding is deployed, the costs will be a lot lower.

So L2 systems will become much, much cheaper and easier to use.

Robert: That’s great. I love that we’re having a sophisticated conversation about cryptography and very technical software, and yet we keep using the word “blob”. It reminds me of the ‘80s sci-fi movie Attack of the Blob. But Lera, yeah, maybe you could chime in now and talk about this trend and how we get from where we are now to that vision in the future of expanded block sizes.

Lera: Yeah, for sure. Before I dive into that, just to add two comments to what Dan said, I want to mention that it’s important the blobs are going to expire and the validators don’t give any guarantee that they’re gonna be storing these blobs forever. Right now the expiry is set roughly to 30 to 60 days, that’s what the Ethereum Foundation is thinking about.

So after this period, during which you will have an opportunity to download all of these blobs and store it locally. You know, the network will drop them, but the commitments to these blobs will persist. And if you need, so if you have the blobs themselves, you can always resupply them to the execution layer with call data.

So as long as you store the blobs, you can prove that those are the correct blobs that you have by resupplying them, because the chain continues storing the hashes of those blobs, the commitments. I also want to mention another important thing is that the fee market for those blobs is gonna be different.

So there’s going to be another fee market. They’re gonna be priced a little differently. So Ethereum is gonna have these two pipes. One pipe, if it gets congested, you are paying larger fees, say for execution, and if a data pipe gets congested, you’re paying larger fees for storing the data. So we don’t yet know how expensive the storage is gonna be. The intuition is that it must be less expensive than call data today. But again, we have to experiment to see exactly how much cheaper it’s gonna be. And protodanksharding is actually, it’s a step towards full danksharding but it’s like an experiment that we are gonna carry out to see how validators are gonna handle this additional load and how expensive the fees are gonna be for storing those data blobs.

So on the way to danksharding, we’re gonna do this experiment with protodanksharding. In protodanksharding basically, you don’t apply any erasure coding or error correcting. All you do is you add this special transaction type that carries data blobs. And those blobs are gonna have an expiry and that’s it.

So the block size is gonna be increased by a little bit in Ethereum. So right now, as Dan was saying, it’s around 100 kilobytes. With protodanksharding it’s gonna be around 500 kilobytes or so. So it’s not that big of an increase, but we’re still gonna test like all of the hypotheses that hopefully will check out and Ethereum will continue moving to full danksharding.

Robert: So Lera, you said a number of things in there. I wanna make sure that all those points came across. You mentioned that the blob data is gonna have a different fee market. So is the right way to think about this, like you have different highway systems, or perhaps you have a lane on a highway where like you have an E-ZPass or something and maybe it’s cheaper for someone in this HOV, E-ZPass-style lane? You get lower fees to put this kind of data on the blockchain versus someone who’s just a regular commuter having to pay a toll. I know I’m kind of mixing some metaphors here, but I’m wondering if that’s a physical analogy to describe these differences in fee markets for different types of data. 

Lera: Yeah, I would say that it’s hard to imagine this new data’s fees being more expensive than what we currently have, so the hypothesis is it’s always gonna be cheaper to put your data in those blobs if you don’t care about accessing this data from the execution layer. So it’s as if opening another lane on your highway, that will just increase traffic, but for certain types of transactions, you’ll go into this lane and for those transactions that are kind of data heavy and for transactions that are execution heavy, you’ll continue going through the main lanes, if that makes sense.

Robert: Yes, it does. And it sounds like one of the reasons why it can be cheaper is because it has this expiration date, as you mentioned. I think you said that the current idea is that’s gonna last 30 to 60 days for this blob data, at which point it would simply vanish and there would just be a trace remaining – a sort of commitment as you described.

Lera: Yes, exactly. 

Dan: Maybe to add to that, basically what happens is when you submit transactions, there’s a fee market, as Lera was saying, in that if there are lots of transactions being submitted all at once, say there’s a big NFT mint, and everybody wants to issue transactions, then of course the price per transaction immediately goes up.

Well, blob data is gonna be a parallel fee market, so presumably there are fewer people submitting blobs than there are people submitting transactions. So hopefully there will be less congestion over blobs. But in principle, it could happen. Hopefully not, but it could happen that all of a sudden, for some reason, there’s huge congestion over blobs and then the fee market for blobs will actually go up.

But in principle, again, because there’s less demand for submitting blobs than there is for submitting transactions, the hope is that the cost for blobs will be lower than the cost for transactions. 

Robert: Okay. That’s really helpful to understand as well. So we’ve laid out a sort of timeline for these updates. Perhaps, people listening in, maybe you’re familiar with “The Merge”, which happened last year in the fall, this big Ethereum upgrade that basically eliminated the environmental impact of Ethereum in terms of its energy consumption. And now we’re entering this new period of upgrades, which Vitalik [Buterin], co-creator of Ethereum, has termed “The Surge”, meaning that all of a sudden, these updates are going to enable the blockchain to scale a lot more powerfully than it’s been able to before. So part of this update, one of the first ones, is protodanksharding. It’s happening later this year. 

What happens in between that upgrade and full on danksharding? What are the differences between the two and when do we get that fully formed vision of danksharding in the future?

Lera: That’s a great question. I think there are still some research problems to figure out along the way, especially around networking because when those validators are storing only fragments of the blob, they need to help each other reconstruct those fragments. If some validator falls asleep for a while, when it wakes up, it wants other validators to help it reconstruct its missing fragments.

So it’s quite an involved networking protocol that is still in the making for danksharding and there are other exciting research problems that potentially can improve the scheme, but I think so far it looks like quite a clear path to get from protodanksharding to danksharding. And the question is just maybe how to make it better, how to improve different aspects of it, make it more efficient.

Dan: Maybe it’s worthwhile adding that in the protodanksharding approach there are at most four blobs per block, which is why each blob is 128 kilobytes. Four times 128 gives us half a megabyte, which is why that’s the limit on block sizes in protodanksharding, and that’s actually imminent. That’s supposed to happen later this year.

And then, yeah, going all the way to danksharding still takes some work. In fact, there was a very big event recently with generating parameters jointly for danksharding. And so there’s a lot of work to do in preparation of getting to full danksharding.

Lera: Yeah, that’s quite exciting. I think they’re still accepting contributions to participate in the trusted setup ceremony. Yeah, so it’s still ongoing. It’s a large community effort that’s really fun to watch and people come up with lots of creative ideas to contribute. So check this out, definitely.

Robert: That’s super cool. I actually participated in some of the trusted setup ceremonies for some of the early privacy coins. Is this trusted setup ceremony as ostentatious as some of those, where you had people burning laptops and exploding hard drives and things like that?

Lera: From what I’ve seen, it’s just people coming up with different creative ways to generate entropy. Some use their pets, dogs and cats. Some are creating some sophisticated marble run machines and such. There was even one contribution done from a satellite, the highest altitude contribution there.

Dan: Actually we have to mention that. It was pretty cool actually. This company Cryptosat actually has satellites in orbit that sample noise up in space and then contribute and participate in the trusted setup protocol.

So that was pretty cool to see. 

Robert: Wow, that is awesome. Did not know there was crypto in space just yet. Dan, you said that protodanksharding is gonna have four blobs per block. What is danksharding gonna enable? How many blobs are we talking here? 

Dan: Yeah, so by the way, protodanksharding is up to four blobs per block.

They’re actually targeting two, but up to four. And then danksharding, as we said, they’re targeting at most 30 megabyte blocks. So just divide 30 megabytes by 128 kilobytes. And that tells you it’s on the order of a hundred, I guess it’s about a hundred blobs per block.

Lera: Yeah, I think the current plan is 128 blobs target and maybe up to 256 blobs per one block.

Robert: Great. 

Dan: And that’s exactly when the blocks become quite large. And then it becomes a little difficult for the validators to keep the entire blocks themselves. And that’s where we have to start breaking them up into pieces. And each validator will store one piece. 

Robert: Got it. I appreciate the basic division. Maybe some of the more technical math that you get into in your post would be a little bit harder to convey here, but that makes sense. Maybe we could talk a little bit about some of the proposals that you made in your recent post. So you did this research and you found that with some adjustments, you could potentially get even more efficiency out of EIP-4844, which is the more technical name for protodanksharding.

Lera: Yeah, the bulk of the work was just to understand the danksharding proposal in full, and then we observed some different ways to look into the mathematics – the cryptographic components of it – that hopefully unravel new toolkits that we can use there. So the rough idea, not going too much in depth, is you fit a polynomial through your block.

It’s a bivariate polynomial because your block is rectangular. And then you evaluate this polynomial at more points, kind of expanding the block. And the idea is that if you’ve used these bivariate polynomials – instead of as danksharding was doing it, as a list of multivariate polynomials – you can then apply techniques for bivariate evaluation, bivariate interpolation, and possibly even try to apply bivariate error-correcting codes to that. But it’s very much an open door for more research and exploration. So in this post we try to explain where more research can be done to improve the scheme in that direction.

Dan: Yeah. Well maybe I can add to that. I mean, danksharding is such a beautiful idea. Really. The Ethereum Foundation deserves a huge amount of credit for it. And, you know, Dankrad [Feist] in particular. It’s really quite an elegant construction.

Initially, we were just trying to understand the details and it took some time to recover exactly all the details of how everything works. And we figured maybe it’ll help the world to have another writeup that explains how the mechanism works. Initially, I guess the original danksharding, the way it’s described, is all using univariate polynomial commitments, where we take each row, we view it as a polynomial. Erasure coding is all done using polynomials.

Maybe I can even teach a little bit of erasure coding here in one sentence. Suppose you have two points in a plane and you want to do erasure coding on them. What you can do is you can just pass a line through those two points, and now you can just publish, instead of just those two points, you can publish those two points plus maybe two additional points on the line.

So now you have four points total. And you know that if two out of those four points make it to the receiver, the receiver can use the two points that it received to recover the line and then recover the original two points. That’s the whole idea of erasure coding. So of course, instead of lines, we use higher degree polynomials to achieve different thresholds, but that’s the idea.

Basically, we have two points. We pass a line. We get more points on the line. If only two points of the line make it to the receiver, the receiver can reconstruct the line and recover the original points. And so danksharding actually does this really, really quite elegantly by looking at the block as a matrix, as a rectangular set of data.

And then it basically extends, using these line ideas, both horizontally and vertically. And that actually gives the coded block – where then, pieces of that rectangle are sent to the different validators. What’s interesting is now that you have a rectangle, you can think of it as a two-dimensional object. That very naturally leads to thinking about this as a bivariate polynomial, exactly as Lera was saying.

What danksharding does is it gives a very interesting way to commit to these bivariate polynomials. So it builds a way to commit to bivariate polynomials by using commitments to univariate polynomials. And so it turns out that the reconstruction mechanism that was done in danksharding is also based on construction along lines and columns – also construction as done using univariate polynomials. And then as we were working through this, there was this realization that, hey, everything here really is about rectangles and bivariate polynomials. Maybe there’s a way in which the reconstruction can also be done by using interpolation of bivariate polynomials. 

Lera: So in fact, you take your block and you expand it to X by the factor of two in both directions. So you have 4X more points as a result. But those 4X points only encode a small quadrant.

So in principle, you only need one quadrant in order to interpolate and recover all the rest of this encoded block. So 25% of the points should be enough. But as danksharding works by doing univariate interpolations, it needs 75% of the block to do column and row-wise reconstruction.

If you do bivariate interpolation directly, you should be good with just 25% instead of 75%. So that will improve the number of elements you need in order to reconstruct, to recover the block. It will also improve communication and data availability sampling, but it’s all due to improved reconstruction.

And now the question, it becomes kind of a mathematical question of how do you do efficient bivariate interpolation? 

There is an obvious need for a better algorithm there. And we were researching this a little bit and it appears so far to be a little bit underexplored. So maybe there were no applications for bivariate interpolation before. Maybe it’s just a hard problem, or we don’t know. But that’s definitely an interesting direction to basically try and improve bilinear interpolation algorithms.

Dan: So what I love about this is just like Lera was saying, for the more algorithms folks in the audience, is that there’s been a ton of work on doing univariate interpolation. If I give you points on a univariate polynomial, like points on a line, and I ask you to reconstruct that polynomial, there are very good algorithms for univariate polynomial interpolation.

And it turns out the bivariate interpolation problem, somehow it seems like it received less attention. And what’s really cool here is all of a sudden, the blockchain, Ethereum, danksharding is creating an application for this really natural algorithmic problem of bivariate polynomial interpolation. 

We really need it here. If we had a good algorithm for bivariate polynomial interpolation, we could make danksharding better because reconstruction, as Lera was saying, would go down from 75% to 25%. So to me, this is really quite beautiful in that the blockchain, Ethereum, danksharding is creating this new area of research, or at least prioritizing this new area of research showing, we really need better algorithms, new algorithms, efficient algorithms to do bivariate polynomial interpolation.

So hopefully that will encourage and spur a lot more research on these types of algorithms and presumably they will be very useful for this problem. 

Robert: So I love that we dug into the methodology here and didn’t shy away from the mathematics. I know some of it might sound a little complicated – bivariate polynomials and univariate polynomials. But I especially appreciate how you described these in terms of geometry and shapes, cause I think everybody here can really picture a line going through some points or how a rectangle functions. So I think that really helps ground the kind of work that you’re doing.

I want to double click on this statistic that you mentioned where the current proposal as it exists would require 75% of samples in order to be reconstructed, whereas what you’re proposing would trim that down to 25%. So that’s a giant difference. 75% to 25%. But it also sounds like just for a casual observer, if you’re only having 25%, the fact that it’s just less than 50%, it sounds like, is that really enough to make assurances that this data is available and was made available?

When you go down to 25% it sounds like, I don’t know, you might be cutting some corners. So how do you assure people that in fact, just having 25% of data samples is actually enough and that things can work at that level? 

Lera: Yeah, that gets us to the topic of data availability sampling, and what it achieves, I guess, because this reconstruction threshold – 75% or 25% – basically determines how many samples you need to get high assurance that the data is there.

The way you do the sample is that you ask the network of validators to give you back one element, a random element of this encoded block. And if you get it back successfully – and you can verify also once the validators give you back the proof of the validity of this piece, and you can verify it against the commitments that the chain persistently stores – so when you get back the successful sample that makes you sure that the data is available with probability that is one minus either one quarter or three quarters, depending on how your reconstruction algorithm works, whether it requires 25% of the data or 75% of the data. 

So every time you do a random sample and it comes back successfully, basically your false positive [rate] – the probability that you think the data is available when it’s not – drops down exponentially. And the rate at which it drops down depends on how much data you are required in the reconstruction. So if your reconstruction requests 25% of the data, you do less samples and your assurance – the false positive rate – goes down quicker than if you only have a reconstruction algorithm that requires 75% of the data. 

So depending on how efficient your reconstruction is, you might need fewer samples in order to have the same assurance that the data is available. So that’s why you not only improve the reconstruction here, but you also improve the number of samples you need to do for your data availability sampling.

And data availability sampling is interesting because it’s probabilistic. So the more samples you do, the higher your assurance is that the data is available, right? And you can always amplify this probability by doing more samples to make it clear. 

Dan: I think Lera, what you just explained is really, really important.

That’s the heart of danksharding and data availability sampling. So I’ll say it one more time, just so that the audience will hear it twice, cause that’s really the heart of it. So maybe think of the block. We said the block is gonna be encoded as this rectangle, right? So somehow we go from a block to a rectangle.

The specifics of how that is done is using this erasure coding. But let’s pretend we went from a block of data to a rectangle. So now imagine this rectangle is literally a rectangle of dots. Every dot corresponds to one piece of the data that’s gonna be distributed to one validator. So now to do data availability sampling, somebody wants to verify that enough of the dots are actually available.

We know that if more than 75% of the dots are available, then the block can be reconstructed using the erasure coding method. Or maybe, if what we’re saying would be used, then only 25% of the dots are sufficient to reconstruct the original rectangle. But how do you know that 75% of the dots are available?

So that’s exactly the data availability sampling mechanism. What you do is you can kind of imagine you are throwing darts at this rectangle, right? So every time you throw a dart, you hit a random point in the rectangle and then the validator that holds that point has to prove, “Yes, I really have that point.”

Now you wanna verify that 75% of the dots are available. So imagine you have this rectangle. Maybe only 75% of the dots are there. Some of the dots disappeared for some reason. You wanna verify that 75% of the dots are available, cause if 75% are available, you can reconstruct the entire rectangle. And so what are you gonna do to verify that 75% are there?

You’re gonna throw a bunch of darts at the rectangle. And for every time the dart hits a dot, the validator that it hits has to prove that the dot really is there. And so if you throw a hundred darts and all hundred darts come back saying, “Yes, the data really is there”, that gives you a pretty good idea that more than 75% of the data is available.

Because you know, if less than 75% is available and you throw four darts, you expect one dart to hit a missing dot. If you throw a hundred darts, and all of them come back saying the data’s available, you have pretty good assurance that more than 75% of the dots are there. And so that’s the idea of data availability sampling.

You just try lots and lots and lots of random points, like a hundred of them. If all of them are there, then you have pretty good assurance that more than 75% are available and you can reconstruct the data. And you see, if you want to get 75% assurance, you need to throw a hundred darts. If you need only 25% assurance, you would need to throw fewer darts than that.

So that would basically reduce the amount of data that’s needed to satisfy the sampling mechanism. Now, maybe it’s worthwhile saying that once the data availability sampling check succeeds – so all the hundred darts come back saying, “Yes, the dots really are there” – then the validator says, “Ah, the data’s available”.

And then [the validator] goes ahead and signs the block as saying, “This block passed data availability sampling”. Yeah, and that’s used later on in consensus. So that’s what the test is. Basically, data availability sampling is a very efficient way to test that enough data is available to reconstruct the block without actually reconstructing the block completely.

So I think it’s good to hear it twice and maybe even a third and a fourth time. But that’s kind of the core idea that makes this all work. 

Robert: I love that, and I especially love the physical analogies that you’re using with a dart board and throwing darts. I think that really brings it home for people. So we’re nearing the top of the hour here.

I wanna get ready to close out. But before we do that, just maybe I’ll throw it to you both in one sentence. What is the upshot of all of this? Like why does it matter to get these efficiency gains? 

Lera: Well, I would say the ultimate goal, of course, is to scale the blockchain and these new techniques would allow it to do that, for Ethereum to achieve full scaling.

That’s a really interesting approach, I would say, because in the beginning, Ethereum was thinking about doing sharding, full sharding, and arriving at quite complicated designs. But having rollups helps scale the execution layer of Ethereum, and this leaves it up to Ethereum to scale its data availability layer. Basically, increase the space while rollups increase the execution capacity and those pieces together will give us cheaper and faster blockchains.

Dan: Yeah, Lera said it perfectly. I mean, really the scaling story for Ethereum is rollups and the way to get rollups to be more efficient and cheaper to use is by solving the data problem. And danksharding is a very elegant and efficient way to do that. So the upshot is a scalable version of Ethereum where rollups are much cheaper to use than they are today.

Robert: That’s great. And if you get cheaper transactions and the ability to make more transactions, I think that opens up Ethereum to do all sorts of new applications that weren’t possible before with high gas costs and fees. So this has been great. Thank you all for joining us. I hope that you all learned a little bit about data availability sampling and danksharding.

If you’d like to learn more, as mentioned, you can check out Dan and Lera’s post. It’s a really, really great piece, so I highly recommend reading it and checking out all the resources contained in there.

Thank you all for joining us. I’m looking forward to this weekend. I’m gonna go to my local bar and teach everybody about erasure coding at the dartboard. So thank you all and take care.

Lera: Sounds great. Thank you.

Dan: Thank you. This has been fun. Bye bye.

Thank you for listening to web3 with a16z. You can find show notes with links to resources, books, or papers discussed; transcripts, and more at a16zcrypto.com. This episode was technically edited by our audio editor Justin Golden. Credit also to Moonshot Design for the art. And all thanks to support from a16z crypto.

To follow more of our work and get updates, resources from us, and from others, be sure to subscribe to our web3 weekly newsletter — you can find it on our website at a16zcrypto.com.

 Thank you for listening, and for subscribing. Let’s <BLEEP> go!