Data availability sampling: how to check a terabyte by reading a kilobyte
ethereum
crypto
data-availability
peerdas
cryptography
I'm going to convince you that you can verify a terabyte of data is fully online by personally downloading a kilobyte of it. That sounds like a con. It's not. It's a Reed-Solomon code and a coin flip, and it shipped to Ethereum mainnet on December 3, 2025 as part of the Fusaka upgrade, epoch 411392.
The feature is called data availability sampling, PeerDAS in Ethereum's naming, EIP-7594 if you want the spec. The pitch always sounded slightly too good: a node checks a handful of random cells out of a much bigger block and from that, with vanishingly small error, knows the whole thing is downloadable. No re-execution. No committee vote. No trusting the block proposer. Just sampling.
I spent a while assuming this was some clever cryptographic sleight of hand, a zero-knowledge trick or an economic penalty game. It's neither. It's high school probability applied to a coding scheme most of us learned about from CDs and QR codes. Once you see the derivation the "magic" evaporates and what's left is just correct.
Start with the encoding, because everything downstream is a consequence of one fact about it.
Treat your original data as the coefficients of a polynomial P of degree d. This isn't a metaphor, it's literally how Reed-Solomon works: d+1 numbers uniquely define a degree-d polynomial, and you can recover those d+1 numbers from d+1 evaluations of that polynomial at distinct points, via Lagrange interpolation. Any d+1 evaluations. Not a specific d+1, not the first d+1 you happen to have, any d+1 out of however many you generate.
PeerDAS uses a 2x extension. Instead of publishing d+1 evaluations (just enough to define the polynomial), it evaluates P at 2(d+1) points and publishes all of them. That doubling is the entire trick. Because any d+1 of the extended evaluations reconstruct P, and d+1 is exactly half of 2(d+1), you get this line for free:
any 50 percent of the extended cells reconstructs the whole block.
Here's a toy version in TypeScript, over a small field, to make it concrete instead of abstract:
// toy Reed-Solomon over a prime field, illustrative not production grade
const p = 2n ** 61n - 1n;
function evalPoly(coeffs: bigint[], x: bigint): bigint {
let result = 0n;
let xPow = 1n;
for (const c of coeffs) {
result = (result + c * xPow) % p;
xPow = (xPow * x) % p;
}
return result;
}
// data is treated as d+1 coefficients (degree d polynomial)
// extend by evaluating at 2(d+1) points instead of the minimum d+1
function reedSolomonExtend(data: bigint[]): bigint[] {
const n = data.length;
const points: bigint[] = [];
for (let x = 1n; points.length < 2 * n; x++) {
points.push(evalPoly(data, x));
}
return points; // 2x the original cell count
}
// recovers the original coefficients from ANY n of the 2n extended cells
function reconstruct(cells: { x: bigint; y: bigint }[], n: number): bigint[] {
if (cells.length < n) throw new Error("not enough cells, need >= n");
const anyN = cells.slice(0, n); // any n cells work, order doesn't matter
return lagrangeInterpolate(anyN, p); // standard modular Lagrange interpolation, omitted here
}The part worth staring at is that reconstruct doesn't care which n cells you hand it. That's not an implementation detail, it's the theorem. Everything below is just this fact, restated for an adversary and then for a network.
Flip the reconstruction fact into a statement about attackers, because that's the useful direction.
If any 50 percent of cells is enough to rebuild the whole block, then an adversary who wants to make the data unavailable, who wants to publish a block header and then quietly refuse to actually serve the data behind it, has exactly one option: withhold more than half the cells. Anything less than that and honest nodes just reconstruct around the gap and the attack does nothing.
This is the load-bearing fact of the whole scheme. There's no cheap partial version of this attack. You can't withhold 10 percent and get partial credit, can't withhold 40 percent and hope nobody notices. To make data unavailable you have to commit to hiding a majority of it, in full, and that majority has to survive contact with every honest node trying to fill the gap.
That's a much bigger commitment than it sounds, and it's the reason the rest of the math gets to be so aggressive.
Now put yourself in the shoes of a single node, a sampler, that wants to check whether a given block is actually available without downloading it.
You pick a cell at random and ask for it. If the adversary is genuinely attempting the withholding attack, the withheld set is more than half the cells, by the floor above. So the probability your random pick lands inside the withheld set, the probability you catch the cheater on this one sample, is strictly greater than one half.
Pr[one sample catches the attack] >= 1/2
That's a fair coin flip stacked in your favor. Now do it k times, independently. The adversary only fools you if every single one of your k samples happens to land on an available cell, missing the withheld set every time:
Pr[fool one sampler with k samples] <= (1/2)^k
This is a geometric collapse and it's brutal. k = 20 gets you under 10^-6. k = 30 gets you under 10^-9. You are not slowly approaching certainty, you're falling off a cliff after a couple dozen coin flips.
function sample(totalCells: number, withheldSet: Set<number>, k: number): boolean {
for (let i = 0; i < k; i++) {
const cell = Math.floor(Math.random() * totalCells);
if (withheldSet.has(cell)) return true; // caught it
}
return false; // fooled, this round
}
function empiricalDetectionRate(
totalCells: number,
withheldFraction: number,
k: number,
trials: number
): number {
const withheldCount = Math.floor(totalCells * withheldFraction);
const withheldSet = new Set<number>();
while (withheldSet.size < withheldCount) {
withheldSet.add(Math.floor(Math.random() * totalCells));
}
let caught = 0;
for (let t = 0; t < trials; t++) {
if (sample(totalCells, withheldSet, k)) caught++;
}
return caught / trials; // converges to 1 - (1/2)^k once withheldFraction > 0.5
}Run that with withheldFraction at 0.49 versus 0.51 and watch the regime flip. Below 50 percent, honest nodes reconstruct and the attack was pointless from the start. Above 50 percent, your detection rate climbs toward 1 within a dozen or two samples. There is no comfortable middle for an adversary to sit in.
One honest node with a 1 - (1/2)^k guarantee is good. A network of thousands of them, each independently sampling, is where this becomes an actual security property instead of a personal one.
The mechanism that makes the network stronger than any individual sampler is reconstruction. Once honest nodes collectively hold at least half the cells, any of them can rebuild the missing half and re-seed it, because that's exactly what the 50 percent reconstruction line guarantees. So an adversary doesn't just need to fool one node, it needs to prevent reconstruction across the entire set of nodes that would otherwise trigger it. Every additional node the adversary needs to fool multiplies in another (1/2)^k factor.
function networkFailureProb(nodes: number, k: number, targetedFraction: number): number {
const targeted = Math.floor(nodes * targetedFraction);
// adversary must fool every targeted node's sampler independently
return Math.pow(0.5, k * targeted);
}The Ethereum Foundation's own analysis (see the DAS security writeups and related work for the rigorous version) puts real numbers on this. With roughly 10,000 nodes on the network, an adversary targeting 2 percent of them succeeds with probability under 10^-20. Target 5 percent instead and it drops to under 10^-306, a number so small it stops meaning anything except "don't bother." Every extra node in the targeted set is another independent coin flip stacked against the cheater.
All of the above is the theory. Here's what's actually running on mainnet, per the PeerDAS overview.
The extended blob data is laid out as 128 columns. A regular node doesn't download all 128, it subscribes to at least 8 random column subnets. Eight out of 128 columns of extended data works out to roughly one eighth of the original data, because the extension doubled everything, half of the extended columns already cover the whole original block. So a normal node is running the exact sampling game above, k on the order of 8, against real column data instead of a toy grid.
Not every node needs to be a light sampler though. Supernodes, meaning nodes backing validators with a combined balance of 4096 ETH or more, custody all 128 columns. They're the reconstruction backstop: if a chunk of the network is missing columns, supernodes have the full picture and can rebuild and rebroadcast whatever's missing, which is what makes "honest majority reconstructs" an actual operational guarantee instead of a theoretical one.
Columns and subnets versus a single random cell changes some of the fine print (you're sampling without replacement, subnet assignment isn't perfectly uniform, node discovery has its own failure modes) but it doesn't change the shape of the argument. Every column subscription is still a bet stacked in the honest node's favor, and the network still needs a majority of cells recoverable somewhere to heal itself.
A few things worth being precise about, because this is easy to oversell.
This is probabilistic availability, not a deterministic proof. The guarantee is "an adversary fools a given sampler with probability at most (1/2)^k", not "it is mathematically impossible for anyone to be fooled." That's a real security property at the numbers involved, but it's a different kind of claim than a SNARK gives you.
The clean (1/2)^k bound assumes uniform, independent, unlinkable samples. Real column-subnet assignment has structure to it, and a network-aware adversary could in principle try to exploit that structure rather than facing pure randomness. Treat (1/2)^k as the core intuition, and treat the eprint papers linked above as the actual rigorous model with the network-level adjustments baked in.
The 10^-20 and 10^-306 numbers are the Ethereum Foundation's figures under their stated assumptions, roughly 10,000 nodes, a specific targeted fraction. They're not universal constants, they're a result under a model, and the model is public if you want to check it yourself.
And reconstruction only reconstructs correct data if the cells you receive actually are the cells that were committed to. Reed-Solomon by itself proves you can rebuild the polynomial from any half the evaluations, it says nothing about whether a cell someone hands you is genuine. That's what the KZG commitments do underneath PeerDAS, they let a node check a received cell against the block's commitment before trusting it. Sampling handles the availability question, commitments handle the integrity question, and you need both.
Rollups exist because executing every transaction on layer 1 doesn't scale. But rollups still need to post their data somewhere so anyone can challenge a bad state transition, and for years that meant every Ethereum node downloading every byte of every blob, which caps how much blobspace the network can ever offer. DAS breaks that link. A node can be confident a blob is available without downloading the blob, which means blobspace can grow without every node's bandwidth growing with it.
It's also worth noticing what family of tool this is. Fraud proofs, ZK proofs, and data availability sampling are all versions of the same move, trade a full deterministic check for a much cheaper probabilistic or interactive one that's sound enough to bet real money on. Verifiable inference for AI is chasing the same shape of problem right now, how do you get confidence in a computation you didn't personally run, for less than the cost of rerunning it. Sample-and-collapse is a genuinely reusable pattern, not a crypto-specific hack.
If you build your own sampler off the code above and watch the failure probability fall off a cliff after twenty samples, screenshot it for me.
Sources: