Variants of KZG: Part IV, Multilinear Commitments with Gemini

This is Part IV of a five-part series on different variations of the KZG protocol. The original appeared on the ZK Security blog.

In Part II and Part III, we studied PST and Zeromorph, which construct multilinear polynomial commitment schemes based on the multilinear quotient identity. In this post, we explore a different route based on split-and-fold techniques. Similar techniques are also used in FRI, Bulletproofs and Sumcheck. Building on ideas from the previous posts in this series, we will study Gemini.

Notation. We continue to use the notation from Part III. We write $\mathbb{F}[X_0,\ldots,X_{n-1}]^{\preceq 1}$ for the set of $n$-variate multilinear polynomials and $\mathbb{F}[X]^{ < d}$ for the set of univariate polynomials of degree at most $d-1$. Univariate polynomials are denoted with a hat, while multilinear polynomials are denoted without a hat. We write $\vec u=(u_0,\ldots,u_{n-1})$ for a point in $\mathbb F^n$ and $\mathcal U_m$ for the univariatization map on $m$-variate multilinear polynomials.

We will now study the split-and-fold techniques used in Gemini.

Splitting and Folding Multilinear Polynomials#

Consider an $n$-variate multilinear polynomial $f(X_0,\ldots,X_{n-1})$. Suppose we want to prove

Gemini reduces this multilinear evaluation claim by partially evaluating one variable at a time. The verifier checks consistency between consecutive partial evaluations using a univariate identity, which we derive next.

Define the $i$-th partial evaluation $f^{(i)}$ by fixing the first $i$ variables:

Here, $f^{(i)}$ is multilinear in $X_i,\ldots,X_{n-1}$ and independent of $X_0,\ldots,X_{i-1}$.

Thus,

At step $i$, $f^{(i)}$ is obtained from $f^{(i-1)}$ by setting $X_{i-1}=u_{i-1}$. Since $f^{(i-1)}$ is linear in $X_{i-1}$, it is determined by its evaluations at $X_{i-1}=0$ and $X_{i-1}=1$. Therefore,

Setting $X_{i-1}=u_{i-1}$ gives the next partial evaluation:

We refer to the two restrictions of $f^{(i-1)}$ obtained by setting $X_{i-1}$ to $0$ and $1$ as its even and odd parts, respectively:

Equivalently, when $f^{(i-1)}$ is represented by its evaluations over the remaining Boolean hypercube, $f^{(i-1)}_{\mathrm{even}}$ consists of its even-indexed evaluations and $f^{(i-1)}_{\mathrm{odd}}$ consists of its odd-indexed evaluations. The even indices correspond to $X_{i-1}=0$, while the odd indices correspond to $X_{i-1}=1$. Using this notation, the next partial evaluation is

The identity above is still between multivariate polynomials, whereas Gemini uses univariate KZG commitments. To express the folding identity in a form that can be committed using univariate KZG, we apply the univariatization map from Part III.

Since the univariatization map $\mathcal U_{n-i}$ is linear, we get:

where:

• $\hat f^{(i)}(X)=\mathcal U_{n-i}\left(f^{(i)}\right)$ is the univariate polynomial whose coefficients are the evaluations of $f^{(i)}$ over the remaining Boolean hypercube $\{0,1\}^{n-i}$;
• $\hat f^{(i-1)}_{\mathrm{even}}(X)=\mathcal U_{n-i}\left(f^{(i-1)}_{\mathrm{even}}\right)$ is the univariate polynomial whose coefficients are the even-indexed evaluations of $f^{(i-1)}$, corresponding to $X_{i-1}=0$;
• $\hat f^{(i-1)}_{\mathrm{odd}}(X)=\mathcal U_{n-i}\left(f^{(i-1)}_{\mathrm{odd}}\right)$ is the univariate polynomial whose coefficients are the odd-indexed evaluations of $f^{(i-1)}$, corresponding to $X_{i-1}=1$.

This is exactly the univariate form of the multilinear partial-evaluation identity. The only remaining issue is that the prover does not commit to $\hat f^{(i-1)}_{\mathrm{even}}$ and $\hat f^{(i-1)}_{\mathrm{odd}}$. The prover only commits to the univariatization of the full previous partial evaluation $\hat f^{(i-1)}(X)$. Therefore, we will now express $\hat f^{(i-1)}_{\mathrm{even}}$ and $\hat f^{(i-1)}_{\mathrm{odd}}$ in terms of $\hat f^{(i-1)}(X)$ and substitute them into equation $(1)$.

By definition, the coefficients of $\hat f^{(i-1)}(X)$ are all the evaluations of $f^{(i-1)}$, with the even- and odd-indexed evaluations appearing alternately. Suppose

and

Then the coefficients of the full univariate polynomial are interleaved as

Substituting $X^2$ into $\hat f^{(i-1)}_{\mathrm{even}}$ places its coefficients at the even powers of $X$. Similarly, substituting $X^2$ into $\hat f^{(i-1)}_{\mathrm{odd}}$ and multiplying by $X$ places its coefficients at the odd powers. Therefore, these polynomials are related by

Replacing $X$ by $-X$ in the above relation gives

Adding and subtracting the relations at $X$ and $-X$ gives

and

Evaluating the univariate fold identity in equation $(1)$ at $X^2$ gives

Substituting the even and odd parts into this equation gives the following identity for $X\neq0$:

After the prover commits to the intermediate polynomials, the verifier samples a random nonzero point $r\in\mathbb F^*$ and checks the following identity for every $i\in\{1,\ldots,n\}$, using the claimed evaluations at $r$, $-r$, and $r^2$:

We will now look at the final construction of the opening protocol.

End-To-End Protocol#

The public inputs are the commitment $C$ to $\hat f^{(0)}=\mathcal U_n(f)$, the evaluation point $\vec u=(u_0,\ldots,u_{n-1})$ and the claimed evaluation $v$. The prover’s witness is the multilinear polynomial $f$. The complete end-to-end protocol is as follows:

1. Compute and commit to the intermediate folds. The prover sets $f^{(0)}=f$ and, for every $i\in\{1,\ldots,n\}$, computes

   $$\begin{aligned} f^{(i)}(X_i,\ldots,X_{n-1}) ={}&(1-u_{i-1}) \cdot f^{(i-1)}_{\mathrm{even}}(X_i,\ldots,X_{n-1})\\ &+u_{i-1} \cdot f^{(i-1)}_{\mathrm{odd}}(X_i,\ldots,X_{n-1}). \end{aligned}$$

   For every $i\in\{1,\ldots,n-1\}$, it computes the univariate encoding

   $$\hat f^{(i)}(X)=\mathcal U_{n-i}\left(f^{(i)}\right)(X)$$

   and sends its univariate KZG commitment

   $$C_i=\operatorname{KZG.Com}(\hat f^{(i)}) =\left[\hat f^{(i)}(\tau)\right]_1$$

   to the verifier. No commitment to $\hat f^{(n)}$ is needed because $\hat f^{(n)}=v$ is the constant claimed evaluation. We write $C_0=C$ for the original univariate KZG commitment.

2. Sample the evaluation challenge. After receiving all the intermediate commitments, the verifier samples a random nonzero challenge $r\xleftarrow{\raisebox{0pt}{\textdollar}}\mathbb F^*$ and sends it to the prover.

3. Evaluate the folded polynomials and prove the openings. For every $i\in\{1,\ldots,n\}$, the prover computes

   $$a^{(i)}=\hat f^{(i)}(r^2),$$

   where $\hat f^{(n)}(X)=v$. For every $i\in\{0,\ldots,n-1\}$, it also computes

   $$b_+^{(i)}=\hat f^{(i)}(r) \qquad\text{and}\qquad b_-^{(i)}=\hat f^{(i)}(-r).$$

   The prover sends all these claimed evaluations to the verifier. Along with them, it sends a batched univariate KZG opening proof for the claims

   $$\hat f^{(i)}(r)=b_+^{(i)} \qquad\text{and}\qquad \hat f^{(i)}(-r)=b_-^{(i)}, \qquad i\in\{0,\ldots,n-1\},$$

   and

   $$\hat f^{(i)}(r^2)=a^{(i)}, \qquad i\in\{1,\ldots,n-1\}.$$

   These claims are combined using the batched univariate KZG opening protocol from Part I.

4. Check the folding relations. For every $i\in\{1,\ldots,n\}$, the verifier checks

   $$a^{(i)} \stackrel{?}{=} (1-u_{i-1})\frac{b_+^{(i-1)}+b_-^{(i-1)}}{2} +u_{i-1}\frac{b_+^{(i-1)}-b_-^{(i-1)}}{2r}.$$

   It also checks that the batched KZG opening proof is valid and that the final fold equals the claimed multilinear evaluation:

   $$a^{(n)}\stackrel{?}{=}v.$$

Each accepted folding relation connects the evaluation of one intermediate polynomial to evaluations of the preceding polynomial. The final check $a^{(n)}=v$ therefore links the original commitment $C$ to the claimed evaluation $f(\vec u)=v$. We now look at the efficiency of the protocol.

Complexity of the Protocol#

For an $n$-variate multilinear polynomial with $2^n$ coefficients, the major costs of the opening protocol are as follows:

• Proof Size: The prover sends $n-1$ intermediate commitments, $O(n)$ claimed evaluations and a constant-size batched KZG opening proof. Assuming each group element is encoded by a constant number of field elements, the total proof size is $O(n)$ field elements.

• Prover Cost: The sizes of the intermediate folds form the geometric series $2^{n-1}+2^{n-2}+\cdots+1=O(2^n)$. Therefore, computing the folds and the batched opening proof requires $O(2^n)$ field operations. Committing to the intermediate folds and computing the batched KZG proof requires $O(2^n)$ group scalar multiplications in total.

• Verifier Cost: Checking the $n$ folding relations requires $O(n)$ field operations. To verify the batched KZG opening, the verifier forms a linear combination of the original commitment and the $n-1$ intermediate commitments. This is an MSM of size $n$, requiring $O(n)$ group scalar multiplications. The final KZG check uses two pairing terms.

Equivalently, the opening costs can be summarized as follows:

Conclusion#

Gemini reduces a multilinear evaluation claim by partially evaluating one variable at a time. The prover commits to every intermediate fold, giving linear prover work and an opening proof whose size grows linearly with the number of variables.

In the next part, we will study how Mercury folds multiple variables at once and reduces this opening proof to constant size.