Data availability for blockchain

”If a block producer doesn’t release all of the data in a block, no one could detect if there is a malicious transaction hidden within that block and produce the corresponding fraud proof”

“Reducing the problem of validating the blockchain to simply verifying that the contents of the block are available”.

• The block producer encodes the block data of size k x k with an bi-dimensional code, getting a 2k x 2k matrix E and computes the MT root on E.
• MT root on E:
• first compute rowRoot_i and columnRoot_i for all i
• root = MT root on (rowRoot_1, ..., columnRoot_1 ...)
• The light clients receives the block header and rowRoot_1, ..., columnRoot_1 ... to check that root(rowRoot_1, ..., columnRoot_1 ...) = dataRoot in the header
• The light client chooses a set of matrix entries (ie, coordinates (x,y)) and ask for those entries and inclusion paths. Each share and valid MT proof that is received by the light client is gossiped to all the full nodes that the light client is connected to;
• If a full node has enough shares to recover a particular row or column, and after doing so detects that recovered data does not match its respective row or column root, then it must distribute a fraud proof consisting of enough shares in that row or column to be able to recover it, and a Merkle proof for each share.

• The main application/motivation for this paper is verifiable retrievability of data stored off-chain (while the data availability problems considers data on-chain!)
• No need of fraud proof, they use erasure codes and homomorphic VC (KZG)

Protocol:

• Dispersal: Clients arranges the input data in a L x k matrix U and
• commit to columns of U, h_i = KZG.Commit(column i)
• apply RS.Encode to rows of U, C is the output matrix, L x n
• send h_1, ... h_k and the column c_i of C to storage provider i
• Local consistency check: storage provider i checks KZG.Commit(c_i) = RS.Encode([h_1, ... h_k ])_i and compute hash = hash(h_1, ... h_k)
• The providers sends back the client sing(Hash, stored)
• The clients collects q valid signatures from different providers (these together are the certificate of retrievability)
• Retrieval: Retrieve a file based on a certificate of retrievability P for a commitment hash, the client first extracts any q unique storage nodes for which P contains a valid signature on (stored,hash). The client then requests the chunks of C from these storage nodes. The storage nodes reply with the commitments and chunks they have stored for hash. The client first waits until some commitments (h1,...,hk) satisfy hash = h(h1∥...∥hk). Then, the client discards any chunks that do not satisfy the homomorphic property. Upon receiving valid chunks from k unique storage nodes, the client uses Code.Decode to decode the file.
• Parameters: q ≤ (n−t), 0 < (q−t) and k ≤ (q−t) are necessary.
• So given any t < n/2 and target file size |B| (in field elements), choose q = (n − t), minimize storage overhead with k = n − 2t, and set L = |B|/k.
• In Appendix A, they explain how to use their protocol for data availability proof.
• The first idea is the following:
• block producer: data input has k blocks, encode them in a polynomial p of degree k-1, and let C = KZG.Commit(p), add C to the block header
• light nodes: ask for evaluation of p at random locations
• “once evaluations at k distinct locations are available, the polynomial, and thus the block content, can be reconstructed. Any invalid transaction becomes visible and full nodes can generate corresponding fraud proofs.”
• However schemes of this flavor however require to compute an evaluation witness for each sample, which can be computationally heavy.
• So, for a more efficient protocol the block producer run the dispersal (commit to column of data and encode the rows). Light clients downloads the all the column commitments and a column c_i (L elements), they verify correctness by running the local consistency check (no fraud proofs!).