2024-06-28

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 \in [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 \cdot 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$

https://zfnd.org/conclusion-of-the-powers-of-tau-ceremony/ https://medium.com/aztec-protocol/aztec-how-the-ceremony-works-9f021cf190d0

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) \cdot (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 \cdot G + r' \cdot H + a \cdot b \cdot 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