~/notes / consensus and blocks
Data Availability Sampling
Checking that data exists without downloading it. The technique that makes rollup scaling work without every node storing everything.
A rollup posts data to the base layer so anyone can reconstruct its state. That only works if the data is actually available, and verifying availability without downloading everything is the problem this technique solves.
The problem
A block producer could publish a block header claiming data exists while withholding the data itself.
Without the data, nobody can verify the state transitions or reconstruct the rollup’s state. Fraud proofs become impossible because there is nothing to prove fraud about.
So availability must be checked, and checking it by downloading everything defeats the purpose of scaling.
The technique
Erasure coding. The data is expanded with redundancy so that any sufficient fraction of the pieces reconstructs the whole. This is the same idea used in storage systems and in error correction.
Random sampling. A light node requests a small number of randomly chosen pieces. If the data is being withheld, a withholder must withhold enough pieces to prevent reconstruction, and any random sample has a high probability of requesting one of the missing ones.
Probability accumulation. A single sample proves little. A modest number of samples, from a modest number of independent nodes, makes withholding detectable with very high probability.
The result is that many light nodes sampling independently collectively verify availability that none of them could verify alone.
Why this is elegant
It converts a problem that appears to require downloading everything into one requiring a few kilobytes per participant.
It also scales in the right direction: more participants sampling means stronger guarantees, whereas most scaling problems get harder with more participants.
What it enables
Rollups posting data without every node storing it.
Light clients that verify availability rather than trusting that data exists.
Larger data capacity without proportionally larger node requirements.
The requirements
Enough sampling nodes. The guarantee depends on many independent samplers. Too few and a withholder can respond to all requests while still withholding from the network.
Network connectivity. Samplers must be able to reach data providers.
Correct erasure coding. A malformed encoding can be detected with additional proofs, which adds complexity.
The state of deployment
Partially deployed. Dedicated data capacity on Ethereum is a step toward this, with full sampling on the roadmap. Some networks have shipped versions of it.
The engineering is substantial and the direction is settled, because it is the mechanism that makes the rollup approach work at scale.
For a user
Invisible, as most of this is.
The visible consequence is that rollup fees fell substantially when dedicated data capacity was introduced, and will fall further as sampling reduces the cost of providing it. That is the entire user-facing effect of a great deal of engineering.
# Corrections and technical nitpicks are welcome. Send them over. They get published with the fix.