Last edited

Mar 21, 2022 10:59 AM

Project

Author: @Irene Date: 18th march 2022

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

- block producer encodes the data D (size k) with a ReedSolomon code, gets a vector E of size 2k;
- take a polynomial p of degree k-1, such p(i) = D_i for i = 0, 1, ... ,k-1
- E = (D || p(k), ..., p(2k-1))
- block producer commits to E, gets comm(E);
- we can use a Merkle tree over E
- block producers sends comm(E) to the client;
- client asks for s random positions in E, gets the positions and the opening info and checks those against comm(E);
- client also gossip the positions to all full nodes;
- 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;
- In this case a fraud proof means sending D, so this solution is not efficient (clients download O(k) to verify k data)
- There is a simple trick to get a proof of size O(sqrt(k))
- arrange the data D in a matrix, apply RS to rows and per columns
- commit to row and column
- 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)**

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

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

- 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
- 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
KZG.Commit(c_i) = RS.Encode([h_1, ... h_k ])_i__Local consistency check:__- header = hash(h_1, ... h_k)

TODO: what is L in practice??

**Comparison (WIP)**
k = data size

k’ = sqrt (k)

s = constant

Protocol 1 | Protocol 2 | Protocol 3 | |

block producer computation | 2* k’ * FFT (2k’) + 2*k’* MT(k’) | ||

client computation | s*(1 + log(k’)) | 1 KZG commit
FFT(L) | |

client communication | s*(1 + log(k’)) | 2*k |