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.
- Evidence
- Primary paper
- Re-measured
- No
- Assumptions
- 4
- Records linked
- 5
Code
Source, repository, and what is actually hosted
- arXiv:1809.09044https://arxiv.org/abs/1809.09044
- The source URL is not a GitHub repository. No code remote is invented.
- Full text is not mirrored. Public availability is not a licence to copy the file onto this site.
- Add to a reading list
01 Claim ledger
What the paper is allowed to say
Each row is a sentence already in the study. The status is the same on every row: a model claim, not a live measurement.
Claim 01 · Paper model
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.
Claim 02 · Paper model
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.
Claim 03 · Paper model
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.
Claim 04 · Paper model
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.
02 Three cuts
Observation, model, falsifier
A desk does not stop at the summary. Each claim is cut three ways, using only this study's own assumptions and checks. Nothing here is a new figure.
01 Fraud proofs have a precondition
Observation
What the study says
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.
Model
What has to hold
At least one honest node can reconstruct and is allowed to publish a fraud proof in time.
Falsifier
What would retire it
Is invalid execution caught by a fraud proof or by a validity proof?
02 Coding spreads the block
Observation
What the study says
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.
Model
What has to hold
Enough shares are requested, by someone, that withholding is likely to be caught.
Falsifier
What would retire it
What happens if the coding itself is invalid?
03 Sampling is probabilistic
Observation
What the study says
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.
Model
What has to hold
Light clients actually wait for the fraud-proof window when they care about validity.
04 Bad coding needs its own proof
Observation
What the study says
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.
Model
What has to hold
At least one honest node can reconstruct and is allowed to publish a fraud proof in time.
Falsifier
What would retire it
Is invalid execution caught by a fraud proof or by a validity proof?
03 Sequence
One action, as an operating tape
- 01The producer erasure-codes the block, in two dimensions in the construction that gives the short proofs.
- 02Light clients request random shares and the Merkle proofs that those shares sit in the committed data.
- 03If a client cannot get its shares, it treats the block as unavailable.
- 04If a full node sees an invalid execution or an invalid coding, it publishes a fraud proof.
- 05Clients that accepted the header on a timer reject it when a valid fraud proof arrives, provided they believe the data was available.
04 Load-bearing
The argument, and where a pitch drops it
Availability is not execution
The cut
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.
Why it carries weight
If this cut is skipped, the paper's name is being used without the mechanism that makes the name mean anything.
Where it is dropped
Samples do not tell you the state root was computed correctly unless a fraud proof or a validity proof is attached.
The honest minority must be able to speak
The cut
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.
Why it carries weight
If this cut is skipped, the paper's name is being used without the mechanism that makes the name mean anything.
Where it is dropped
Samples do not tell you the state root was computed correctly unless a fraud proof or a validity proof is attached.
05 Register
What has to be true
Model · Not re-measured
Enough shares are requested, by someone, that withholding is likely to be caught.
Cryptography · Not re-measured
At least one honest node can reconstruct and is allowed to publish a fraud proof in time.
Network · Not re-measured
The coding and the Merkle commitments are the ones the clients sample. A commitment to a different object is theatre.
Cryptography · Not re-measured
Light clients actually wait for the fraud-proof window when they care about validity.
06 Divergence
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.
A later client, parameter set, or reward formula is a different object. Cite this paper for the mechanism. Cite a primary release for the network. This desk has not re-run the proof.
07 Pre-mortem
What to check before you use the idea
- 0 of 4 marked on this browser. A mark is a reading note, not a pass, a rating, or a recommendation.
08 Anatomy
The paper, in the order a builder needs
The problem it 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 the desk 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.
09 Lexicon
Terms, opened into the record
- 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.
10 Repository
Every linked record on this page
Underlined words open a page that already exists: a concept, a protocol profile, a failure record, or another paper. If a word is not underlined, this desk does not have a record for it.
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.