Can we use snark for data availability proofs?

Author: @ Date: 18th march 2022

Protocol 1 (with incorrect encoding fraud proofs, Al Bassam et al)

1. block producer encodes the data D (size k) with a ReedSolomon code, gets a vector E of size 2k;
1. take a polynomial p of degree k-1, such p(i) = D_i for i = 0, 1, ... ,k-1
2. E = (D || p(k), ..., p(2k-1))
2. block producer commits to E, gets comm(E);
1. we can use a Merkle tree over E
3. block producers sends comm(E) to the client;
4. client asks for s random positions in E, gets the positions and the opening info and checks those against comm(E);
5. client also gossip the positions to all full nodes;
6. as soon as a full node has k+1 positions, it reconstructs D and E and checks if E = Enc(D); if something is wrong, sends a incorrect encoding fraud proof to the client;
1. In this case a fraud proof means sending D, so this solution is not efficient (clients download O(k) to verify k data)
2. There is a simple trick to get a proof of size O(sqrt(k))
1. arrange the data D in a matrix, apply RS to rows and per columns
2. commit to row and column
3. if the full node sees an error, it can send just the row (or the column)

PROBLEM/QUESTION: can we avoid the incorrect encoding fraud proof using a SNARK?

Protocol 2 (no incorrect encoding fraud proofs, but requires many evaluation witnesses for KZG)

1. block producer encodes the data D (size k) with a ReedSolomon code, gets a vector E of size 2k;
1. take a polynomial p of degree k-1, such p(i) = D_i for i = 0, 1, ... ,k-1
2. E = (D || p(k), ..., p(2k-1))
2. block producer commits to E, gets comm(E);
1. use the KZG commitment to commit to p
3. block producers sends comm(E) to the client;
4. client asks for s random evaluation of p, gets the values and the evaluation witnesses and checks those against comm(E);
1. PROBLEM/QUESTION: this is expensive! How much? More or less than a SNARK prover?
5. client also gossip the values to all full nodes;

Protocol 3 (no fraud proof, no evaluation witness for KZG)

1. block producer arranges the data D in a matrix L x k 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 2k
• H = hash(h_1, ... h_k) is the block header sent to clients
2. client asks for a random position i in {1,...,2k}, gets the column c_i and block producer sends h_1, ... h_k to client (k elements!), checks
• Local consistency check: KZG.Commit(c_i) = RS.Encode([h_1, ... h_k ])_i
• header = hash(h_1, ... h_k)

TODO: what is L in practice??

Comparison (WIP) k = data size

k’ = sqrt (k)

s = constant