Motivation
- Given a list of data $y_i, i = 0, .. n - 1$, commitment is a “compressed” digest of the data
- Merkle tree commitment = root hash (32 bytes)
- Prover: given $i$, generate proof $\pi_i$, $y_i$
- Verifier: given $\pi_i$, $y_i$, tell yes or no
- Cons: $\log(n)$ proof size (27 * 32 = 864 bytes)
KZG
- commitment = 48 bytes
- Single point proof size $y_i$: 48 bytes (no matter $n$ is)
- Multi point proof $y_{i(0)}, y_{i(1)},…y_{i(m-1)}$: 48 bytes (no matter $n$ is)
Applications:
- Stateless (Verkle tree)
- DAS
Polynomial
$$
f(x) = \sum_{i = 0}^{n} a_i x^i=a_0 + a_1x + ...+a_nx^n
$$
- Degree $deg(f(x))=n$
- $a_n\neq0$
Encoding data into Polynomial using Lagrange Interpolation
Given $(x_i, y_i), x_i \neq x_j, \forall i\neq j$, build a polynomial such that $f(x_i) = y_i$ and degree is $n-1$
$$
f(x)=\sum_{i=0}^{n-1}y_i \prod_{j=0, j \neq i}^{n-1} \frac{x - x_j}{x_i - x_j}
$$