Skip to content
Blockchain LabTHE VENTURE STUDIO

LibraryScaling2018Design paperCorpus record

Fraud and Data Availability Proofs

Fraud and data availability proofs. Mustafa Al-Bassam, Alberto Sonnino and Vitalik Buterin.

Light clients can refuse a block if a fraud proof shows it is invalid, but only if the block's data was actually published. The paper shows how erasure coding and sampling let clients check publication without downloading everything.

A light client can safely rely on fraud proofs only if the underlying data was published. This paper uses erasure coding and random sampling so clients can check publication without downloading the block.

The five-minute read

Fraud proofs have a precondition

If the block producer withholds the body, nobody can build the fraud proof that would show the header is a lie. Availability is not a side issue. It is what makes the fraud proof exist.

Coding spreads the block

Reed-Solomon coding adds redundancy so any large enough set of chunks reconstructs the block. A producer who wants to hide the block has to hide more than a small corner of it.

Sampling is probabilistic

Each light client fetches a few random chunks. If many clients do this, a withheld block is noticed. One client who samples nothing has not used the scheme.

Bad coding needs its own proof

A producer might publish shares that do not correspond to one block. The paper gives a fraud proof for that too, so clients do not reconstruct nonsense.

One action, walked through

  1. The producer erasure-codes the block, in two dimensions in the construction that gives the short proofs.
  2. Light clients request random shares and the Merkle proofs that those shares sit in the committed data.
  3. If a client cannot get its shares, it treats the block as unavailable.
  4. If a full node sees an invalid execution or an invalid coding, it publishes a fraud proof.
  5. Clients that accepted the header on a timer reject it when a valid fraud proof arrives, provided they believe the data was available.

The argument, unpacked

Availability is not execution

Sampling tells you the bytes were published. It does not tell you the transactions were valid. That is the fraud proof's job, or a validity proof's job in a rollup that does not want the challenge window. The paper is about the first half.

The honest minority must be able to speak

Someone who has the data has to be able to post the fraud proof before light clients finalise the header. A network that censors those proofs, or a timer that is shorter than propagation, quietly disables the scheme.

What has to be true

  • Enough shares are requested, by someone, that withholding is likely to be caught.
  • At least one honest node can reconstruct and is allowed to publish a fraud proof in time.
  • The coding and the Merkle commitments are the ones the clients sample. A commitment to a different object is theatre.
  • Light clients actually wait for the fraud-proof window when they care about validity.

What happened after the paper

Celestia's line of work, and Ethereum's data-availability research, start from this problem: sample instead of download, then pair the samples with either fraud proofs or validity proofs. The 2018 paper does not set any current blob target, erasure parameter, or sampling count. Those are later specifications.

What to check before you use the idea

  • Do light clients sample, or do they trust a header?
  • Is invalid execution caught by a fraud proof or by a validity proof?
  • How long is the window in which a fraud proof must land?
  • What happens if the coding itself is invalid?

Terms

Data availability
The property that the bytes of a block were published, not merely its header.
Fraud proof
A short proof that a published block breaks a rule, which a light client can check.

The problem the paper names

A light client that trusts a header can be lied to about state. A fraud proof fixes that only when the client can fetch the data the proof refers to. Withholding the data is the attack.

What the design proposes

  • Encode the block so that any large enough sample reconstructs it.
  • Clients sample random chunks. A withholder cannot satisfy all of them cheaply.
  • If the coding is invalid, an honest full node produces a short proof of that.

How the mechanism is specified

  • Two-dimensional Reed-Solomon coding gives both random sampling and a way to prove a bad encoding.
  • Sampling is a statement about availability, not about execution. Someone still has to run the transactions.
  • The honest minority has to be able to publish the fraud proof before clients accept the header.

What this page does not treat as proven

  • This is the root of data-availability sampling, not a specification of Celestia, Ethereum danksharding, or any current parameter set.
  • Samples do not tell you the state root was computed correctly unless a fraud proof or a validity proof is attached.
  • A committee that withholds data and also censors fraud proofs breaks the timing assumption.

Why a venture studio still reads it

Separate three questions: was the data published, was the execution valid, and who can reconstruct the block. This paper is about the first, so that the second can be checked by someone small.

This is Blockchain Lab's reading of a public design paper. It is not the paper, not a copy of it, and not an offer of tokens, equity, custody or a partnership. Later network behaviour can diverge from the text. Nothing here is investment, legal or technical advice.

Research status: Design paper. Last reviewed: 1 October 2026. This is a reading of a public paper, not investment, legal or security advice.