Five Open Questions on the Security of Fraud and Data Availability Proofs
The 2019 paper “Fraud and Data Availability Proofs” by Al-Bassam, Sonnino and Buterin is one of the foundational works behind modern data-availability sampling systems, including Celestia. It showed how light clients can gain strong guarantees about block validity and data availability even when a majority of block producers are dishonest, as long as a small number of honest nodes exist.
The construction is elegant and has been influential. At the same time, several parts of the security argument rest on assumptions or reconstruction properties that are not fully spelled out in the paper. Below I list five concrete questions. I am not claiming these are proven vulnerabilities. I am simply asking whether the existing construction already answers them, or whether extra mechanisms or stronger assumptions are needed.
I would be grateful for clarification from the authors or from researchers who have studied the paper in depth.
1. How is correct Reed-Solomon encoding actually verified?
In the simple 1-D strawman (Section 5.1), an adversarial block producer can publish an incorrectly extended code. The only way to prove the encoding is wrong is to re-encode the whole original data, which costs O(n). The paper therefore switches to a 2-D matrix construction (Section 5.2) so that a fraud proof only needs one row or one column (size O(√n)).
Section 5.5 shows how to detect that a recovered row or column does not match its claimed Merkle root. What is less clear is the exact mechanism that guarantees the producer performed the Reed-Solomon encodings correctly in the first place. Sampling a few cells and checking Merkle proofs against row/column roots does not by itself prove that those roots were produced by a valid encoding of the original data.
Question: What precisely has changed, relative to the 1-D case, that lets light clients (or an honest full node) be sure the encodings were performed correctly without re-encoding large parts of the matrix? Is the combination of row/column roots + codec fraud proofs (Section 5.5) sufficient, or is an additional check required?
2. Selective answers under the “enhanced” network model
Section 5.4 notes that a malicious producer can answer the first (k+1)² sample requests and then stop. To prevent this, the paper invokes an enhanced network model: sample requests are anonymous (for example via a mix-net) and arrive in random order, and enough honest light clients are sampling so that more than (k+1)² distinct shares are requested in total.
Even under those assumptions, consider the following behaviour: the producer answers roughly half the incoming requests and then goes silent. Some light clients may receive all the shares they asked for and accept the block, while later clients receive nothing.
Questions:
- Does the soundness definition (Definition 1 in Section 5) still hold in this “answer-then-stop” scenario?
- How does a light client distinguish a block that is genuinely available from one that was only temporarily available to a subset of clients?
- What concrete networking infrastructure (mix-nets or equivalent) is assumed, and have the latency, cost and additional trust assumptions been analysed?
3. Why collect shares from light clients instead of letting the honest full node fetch the data directly?
Soundness (Definition 1) relies on at least one honest full node eventually obtaining the full block. The design achieves this by having light clients gossip the shares they receive back to full nodes (Section 5.3).
If an honest full node is already assumed to exist and to be connected to the network (Threat Model, Section 3.4), a natural alternative is for that node simply to request the missing data itself from the block producer or from other full nodes.
Questions:
- Why is the more complex route (thousands of light clients sampling and gossiping) preferred over the honest full node fetching the data directly?
- Are the communication and coordination costs of collecting overlapping shares from many light clients accounted for in the complexity analysis?
4. Consistency between row Merkle trees and column Merkle trees
Each share sits in both a row Merkle tree and a column Merkle tree (Section 5.2). A light client that samples a share receives a proof against one of those roots. It is not obvious how the client (or the network) detects that the value claimed for position (i, j) in the row tree differs from the value claimed for the same position in the column tree.
Section 5.5 notes that a full node that recovers enough of a row or column can generate a fraud proof of inconsistency. It is less clear what data the full node must collect to do so, and whether those costs are included in the stated complexity.
Question: What is the exact procedure, and the exact communication cost, for detecting and proving that the same matrix cell has two different values in the row tree versus the column tree?
5. Reconstruction properties of the right-hand (and bottom-right) portion of the matrix
This is the most technical point and, in my view, the most important to verify carefully.
The construction in Section 5.2 proceeds as follows:
- Place the original data in a k × k matrix.
- Reed-Solomon-encode every row and every column of that matrix (extending it to the right and downward).
- Apply one more horizontal Reed-Solomon encoding to the vertically extended portion, producing the final 2k × 2k matrix.
Theorem 1 (and its proof) claims that, to hide any single cell, an adversary must make at least (k+1)² shares unavailable. The proof relies on the fact that every row and every column is a valid Reed-Solomon codeword: any missing symbol can be recovered from any k symbols in its row or its column.
2k × 2k matrix diagram showing the original k × k block, right-hand extension, bottom extension, and bottom-right quadrant, with a red cell and green cells highlighted.
Question: Does the specific order of encodings described in Section 5.2 guarantee that a cell lying in the right-hand half (or especially the bottom-right quadrant) can always be reconstructed from the remaining symbols of its column? Or does the third horizontal encoding break the column-codeword property for those cells? If the latter, the lower bound of (k+1)² unavailable shares may not hold uniformly for every cell in the matrix.
I would be especially interested in a precise statement of which symbols are guaranteed to be recoverable from which axes after the final encoding step.
These five questions do not claim that the scheme is broken. They ask for the missing links that would let a reader confirm that the stated security properties follow from the given construction and assumptions.
If the answers already exist in the paper (or in later follow-up work) and I have simply missed them, I will be happy to update this post. Clearer statements of the precise assumptions and reconstruction invariants would also help future implementations and formal analyses.
Comments, corrections and clarifications from the authors or from anyone who has studied the construction in depth are very welcome.