# KZG

KZG is based on paring-based cryptography.

- $\mathsf{Setup}(1^λ, 1^d)$ (One-time trusted setup, where $d$ is the upper bound of the polynomial degree):
-- Sample a random field element $s\gets\mathbb{F}_p$
-- return $ck=([s^0]_1, ... [s^d]_1,[1]_2,[s]_2)$

- $\mathsf{Commit}(ck,f)$ (Commit to polynomial):
-- $\mathsf{com}=\sum_{i=0}^d f_i\cdot[s^i]_1$
-- return $\mathsf{com}$

- $\mathsf{Open}(ck,f,x,y)$ (Given an evaluation $y=f(x)$, provide a proof that verifies this evaluation):
-- $q(X)=\frac{f(X)-y}{X-x}$
-- $\pi= \sum_{i=0}^d q_i\cdot [s^i]_1$
-- return $\pi$

- $\mathsf{Verify}(ck,\mathsf{com},\pi,x,y)$ (Verify an evaluation proof):
-- return $e(\mathsf{com} − [y]_1, [1]_2) = e(π, [s]_2 − [x]_2)$

**Advantage**:
- Constant-size proofs, irrespective of the polynomials degree
- Efficient verification (Bilinearity of pairing operations), suitable for scalable applications such as zk-rollups.

**Limitation**:
- Require a trusted setup

## Multiproofs

We can evaluation a polynomial at multiple points by altering the following algorithms.

- $\mathsf{Open}(ck,f,(x_0,y_0),...(x_{k-1},y_{k-1}))$:
-- Compute the Lagrange interpolation polynomial $I(X)$ using points $(x_0,y_0),...(x_{k-1},y_{k-1})$
-- $Z(X)=(X-x_0)(X-x_1)\cdots (X-x_{k-1})$
-- $q(X)=\frac{f(X)-I(X)}{Z(X)}$
-- $\pi= \sum_{i=0}^d q_i\cdot [s^i]_1$
-- return $\pi$

- $\mathsf{Verify}(ck,\mathsf{com},\pi,(x_0,y_0),...(x_{k-1},y_{k-1}))$ (Verify an evaluation proof):
-- Compute the Lagrange interpolation polynomial $I(X)$ using points $(x_0,y_0),...(x_{k-1},y_{k-1})$
-- $Z(X)=(X-x_0)(X-x_1)\cdots (X-x_{k-1})$
-- return $e(\mathsf{com} − [I(s)]_1, [1]_2) = e(π, [Z(s)]_2)$