Polynomial commitment schemes

24 July 2024 (updated 24 July 2024)

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

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) ⋅ (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