# Polynomial commitment schemes

$$\gdef\F{\mathbb{F}} \gdef\G{\mathbb{G}} \gdef\g{\mathrm{G}} \gdef\h{\mathtt{H}} \gdef\e{\mathrm{e}}$$

I will discuss polynomial commitment schemes for $n$-term polynomials, so polynomials of degree at most $n-1$.

A polynomial commitment scheme for $n$-term polynomials two scheme has two operations. Given $f ∈ \F_{<n}[X]$ the operation $\mathrm{commit}(f)$ produces a commitment $c$ to $f$. Given commitments $c_i$ and evaluation points $(x_{i,j}, y_{i,j})$ the $\mathrm{open}$ operation proofs that $f_i(x_{i,j}) = y_{i,j}$.

## KZG

Let $\G_1$, $\G_2$, $\G_3$ be elliptic curve groups with the same scalar field $\F$, generators $\g_1$, $\g_2$, $\g_3$ and a pairing $\e: \G_1 × \G_2 → \G_3$. For more background see here

Kate-Zaverucha-Goldberg

https://cacr.uwaterloo.ca/techreports/2010/cacr2010-10.pdf

https://eprint.iacr.org/2020/081.pdf

https://eprint.iacr.org/2020/1536.pdf

### Trusted set up

During the trusted setup ceremony a secret value $τ ∈ \F$ is selected and the following "powers of tau" are computed for $i ∈ [0,n)$

$$\vec X = \begin{bmatrix} τ^0 & τ^1 & τ^2 & ⋯​ \end{bmatrix} ⋅ \g_2$$

These values $X_i$ are known as the common reference string (CRS). These can get quite large, for $n = 2^{20}$.

The CRS is update able. Given a new secret value $s ∈ \F$ the updated values are $X_i' = s^i ⋅ X_i$.

Note. The $X_i$ act as a monomial basis for polynomials which is convenient if the polynomial we want to commit to is in coefficient form. Often, we instead have the the polynomial in point form $(x_i, y_i)$. We can then construct a basis of Langrange functions over the $x_i$'s:

$$X_i' = todo$$

To commit to a polynomial $P(X)$ we compute $P = P(τ) ⋅ \g_2$ using the basis.

### One commitment, one value

To proof $P(x) = y$ we compute following is polynomial

$$Q(X) = \frac{P(X) - y}{X - x}$$

The proof is $Q = Q(τ) ⋅ \g_2$.

To verify, compute $Z = (τ - x) ⋅ \g_2$ and $R = y ⋅ \g_2$

$$\e(P - R, \g_2) = \e(Q, Z)$$

\begin{aligned} \e(P - R, \g_2) &= \e(Q, Z) \\ \e(P(τ) ⋅ \g_2 - y ⋅ \g_2, \g_2) &= \e(Q(τ) ⋅ \g_2, (τ - x) ⋅ \g_2) \\ (P(τ) - y) ⋅ \e(\g_2, \g_2) &= Q(τ) ⋅ (τ - x) ⋅ \e(\g_2, \g_2) \\ P(τ) - y &= Q(τ) ⋅ (τ - x) \\ \end{aligned}

Then due to the Schwarz-Sippl lemma it is cryptographically likely that $P(X) - y = Q(X) ⋅ (X - x)$.

### Many commitments, many values

Given many commitments $P_i$ as above, for each we want to proof a set of values $P_i(x_{ij}) = y_{ij}$. Define $S_i = \set{x_{ij}}$, $S = \Union S_i$.

Zero polynomials

$$Z_{\mathcal S}(X) = \prod_{s ∈ S} \p{X - s}$$

Lagrange polynomials

$$L_{ij}(X) = \frac{Z_{S_i \setminus \set{x_j}}(X)}{Z_{S_i \setminus \set{x_j}}(x_j)}$$

Interpolating polynomials

$$R_i(X) = \sum_j y_{ij} ⋅ L_{ij}(X)$$

The verifiers sends a random $u ∈ \F$.

The prover computes

$$Q(X) = \sum_i u^i ⋅\frac{P_i(X) - R_i(X)}{Z_{S_i}(X)}$$

The prover sends $Q(τ) ⋅ \G_2$ The verifier checks

$$\sum_i \e(u^i ⋅ (P_i - R_i), Z_{S \setminus S_i}(τ) ⋅ \g_2) = \e(Q, Z_S(τ) ⋅ \g_2)$$

### Variant

$\bar S_i = S \setminus S_i$

The verifiers sends a random $u ∈ \F$.

Prover computers

$$P(X) = \frac{1}{Z_{S}(X)} ⋅ \sum_i u^i ⋅ (P_i(X) - R_i(X)) ⋅ Z_{\bar S_i}(X)$$

this equals

$$P(X) = \sum_i u^i ⋅ \frac{P_i(X) - R_i(X)}{Z_{S_i}(X)}$$

The prover sends $P(τ) ⋅ \G_2$. The verifier sends random $z ∈ \F$.

$$L(X) = \sum_i u^i ⋅ (P_i(X) - R_i(z)) ⋅ Z_{\bar S_i}(z) - Z_S(z) ⋅ P(X)$$

and

$$W(X) = \frac{L(X)}{Z_{\set z}(X)}$$

$$W(X) = \frac{Z_S(z)}{Z_{\set z}(X)} ⋅\p{ \sum_i u^i ⋅ \frac{P_i(X) - R_i(z)}{Z_{S_i}(z)} - P(X) }$$

$$W(X) = \frac{Z_S(z)}{Z_{\set z}(X)} ⋅ \sum_i u^i ⋅ \p{ \frac{P_i(X) - R_i(z)}{Z_{S_i}(z)} - \frac{P_i(X) - R_i(X)}{Z_{S_i}(X)} }$$

and sends $W(τ) ⋅ \G_2$.

The verifier computes

$$F = \sum_i u^i ⋅ Z_{\bar S_i}(z) ⋅ \p{P_i - r_i(z) ⋅ \G_2} - Z_S(z) ⋅ W$$

and checks

$$\e\p{F + z ⋅ W, \G_2} = \e\p{W, τ ⋅ \G_2}$$

\begin{aligned} \e\p{F + z ⋅ W, \G_2} &= \e\p{W, τ ⋅ \G_2} \\ \sum_i u^i ⋅ Z_{\bar S_i}(z) ⋅ \p{P_i(τ) - r_i(z)} - Z_S(z) ⋅ W(τ) + z ⋅ W(τ) &= W(τ) ⋅ τ \\ \sum_i u^i ⋅ Z_{\bar S_i}(z) ⋅ \p{P_i(τ) - r_i(z)} &= W(τ) ⋅ τ + Z_S(z) ⋅ W(τ) - z ⋅ W(τ) \\ \sum_i u^i ⋅ Z_{\bar S_i}(z) ⋅ \p{P_i(τ) - r_i(z)} &= \p{τ - z + Z_S(z)} ⋅ W(τ) \\ \end{aligned}

## FRI

Let $\h_{\mathcal S} : \mathcal I → \mathcal S$ be a hash function mapping some input set $\mathcal I$ to the output set $\mathcal S$. A superscript like $\h'$ is used to indicate two domain separated hash functions.

## Inner product arguments

https://vitalik.ca/general/2021/11/05/halo.html

Halo turns the inner product argument from Bulletproofs into a polynomial commitment scheme.

Basically if we can commit to a vector $\vec p$ and proof $y = \inprod{\vec p}{\vec x}$ where $\vec x = \begin{bmatrix} 1, x, x^2, \dots \end{bmatrix}$.

### Set up

Given elliptic curve group $\G$ with scalar field $\F$. Generate a common reference string of $G_i, H ∈ \G$ random elements.

### Commit

Given a polynomial $P(X) = \sum_i c_i ⋅ X^i$, generate a random blinding factor $r ∈ \F$. The commitment is

$$r ⋅ H + \sum_i c_i ⋅ G_i$$

### Proof

To proof that $P(x) = v$:

The verifier sends a random $U ∈ \G$. Start with

\begin{aligned} \vec a &= \begin{bmatrix} c_0, c_1, c_2, \dots \end{bmatrix} & \vec b &= \begin{bmatrix} 1, x, x^2, \dots \end{bmatrix} & \vec G &= \begin{bmatrix} G_0, G_1, G_2, \dots \end{bmatrix} \end{aligned}

The prover sends $L, R$ as

\begin{aligned} L &= \inprod{\vec a_{\mathrm{lo}}}{\vec G_{\mathrm{hi}}} + l ⋅ H + \inprod{\vec a_{\mathrm{lo}}}{ \vec b_{\mathrm{hi}}} ⋅ U \\ R &= \inprod{\vec a_{\mathrm{hi}}}{\vec G_{\mathrm{lo}}} + r ⋅ H + \inprod{\vec a_{\mathrm{hi}}}{ \vec b_{\mathrm{lo}}} ⋅ U \\ \end{aligned}

The verifier issues a random $u ∈ \F$. The prover computes

\begin{aligned} \vec a' &= \vec a_{\mathrm{hi}} ⋅ u^{-1} + \vec a_{\mathrm{lo}} ⋅ u \\ \vec b' &= \vec b_{\mathrm{hi}} ⋅ u^{-1} + \vec b_{\mathrm{lo}} ⋅ u \\ \vec G' &= \vec G_{\mathrm{hi}} ⋅ u^{-1} + \vec G_{\mathrm{lo}} ⋅ u \\ \end{aligned}

TODO: Halo paper has hi, lo reversed for b, G.

Repeat until $\vec a$, $\vec b$ and $\vec G$ are a single element. The prover sends these over and the verifier computes

$$Q = \sum_i u_i^2 ⋅L_i + P' + \sum_i u_i^{-2} ⋅ R_i$$

and

$$r' = \sum_i u_i^2 ⋅ l_i + P' + \sum_i u_i^{-2} ⋅ r_i$$

and checks

$$Q = a ⋅ G + r' ⋅ H + a ⋅ b ⋅ U$$

https://zcash.github.io/halo2/background/pc-ipa.html

https://zcash.github.io/halo2/design/proving-system/inner-product.html

https://eprint.iacr.org/2017/1066.pdf

https://eprint.iacr.org/2017/1132.pdf

https://eprint.iacr.org/2019/953.pdf

https://eprint.iacr.org/2019/1021.pdf

Aurora https://eprint.iacr.org/2018/828.pdf Section 8

• Dory

• Dark

## References

https://vitalik.ca/general/2017/01/14/exploring_ecp.html

https://alinush.github.io/2020/05/06/kzg-polynomial-commitments.html#fn:KZG10e

https://arnaucube.com/blog/kzg-commitments.html

https://arnaucube.com/blog/kzg-batch-proof.html

https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf

https://eprint.iacr.org/2017/1132.pdf

https://eprint.iacr.org/2019/953.pdf

https://zcash.github.io/halo2/concepts/chips.html

Remco Bloemen
Math & Engineering
https://2π.com