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} $$