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
$$ f(u_0,\ldots,u_{n-1})=v. $$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:
$$ f^{(i)}(X_i,\ldots,X_{n-1}) = f(u_0,\ldots,u_{i-1},X_i,\ldots,X_{n-1}). $$Here, $f^{(i)}$ is multilinear in $X_i,\ldots,X_{n-1}$ and independent of $X_0,\ldots,X_{i-1}$.
Thus,
$$ f^{(0)}(X_0,\ldots,X_{n-1}) = f(X_0,\ldots,X_{n-1}) \quad \text{and} \quad f^{(n)} = f(u_0,\ldots,u_{n-1}) = v. $$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,
$$ \begin{aligned} f^{(i-1)}(X_{i-1},X_i,\ldots,X_{n-1}) ={}&(1-X_{i-1}) \cdot f^{(i-1)}(0,X_i,\ldots,X_{n-1})\\ &+X_{i-1} \cdot f^{(i-1)}(1,X_i,\ldots,X_{n-1}). \end{aligned} $$Setting $X_{i-1}=u_{i-1}$ gives the next partial evaluation:
$$ \begin{aligned} f^{(i)}(X_i,\ldots,X_{n-1}) ={}&f^{(i-1)}(u_{i-1},X_i,\ldots,X_{n-1})\\ ={}&(1-u_{i-1}) \cdot f^{(i-1)}(0,X_i,\ldots,X_{n-1})\\ &+u_{i-1} \cdot f^{(i-1)}(1,X_i,\ldots,X_{n-1}). \end{aligned} $$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:
$$ \begin{aligned} f^{(i-1)}_{\mathrm{even}}(X_i,\ldots,X_{n-1}) &:=f^{(i-1)}(0,X_i,\ldots,X_{n-1}),\\ f^{(i-1)}_{\mathrm{odd}}(X_i,\ldots,X_{n-1}) &:=f^{(i-1)}(1,X_i,\ldots,X_{n-1}). \end{aligned} $$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
$$ 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}) $$Each partial-evaluation step first splits the previous evaluations into their even and odd parts and then folds these parts using the current evaluation point $u_{i-1}$ to obtain the next partial evaluation. This is why the technique is called split-and-fold.
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:
$$ \mathcal U_{n-i}\left(f^{(i)}\right) = (1-u_{i-1}) \cdot \mathcal U_{n-i}\left(f^{(i-1)}_{\mathrm{even}}\right) + u_{i-1} \cdot \mathcal U_{n-i}\left(f^{(i-1)}_{\mathrm{odd}}\right) $$ $$ \hat f^{(i)}(X) = (1-u_{i-1}) \cdot \hat f^{(i-1)}_{\mathrm{even}}(X) + u_{i-1} \cdot \hat f^{(i-1)}_{\mathrm{odd}}(X) \tag{1} $$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
$$ \hat f^{(i-1)}_{\mathrm{even}}(X)=e_0+e_1X+e_2X^2+\cdots $$and
$$ \hat f^{(i-1)}_{\mathrm{odd}}(X)=o_0+o_1X+o_2X^2+\cdots. $$Then the coefficients of the full univariate polynomial are interleaved as
$$ \hat f^{(i-1)}(X) =e_0+o_0X+e_1X^2+o_1X^3+e_2X^4+o_2X^5+\cdots. $$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
$$ \hat f^{(i-1)}(X) = \hat f^{(i-1)}_{\mathrm{even}}(X^2) + X \cdot \hat f^{(i-1)}_{\mathrm{odd}}(X^2). $$Replacing $X$ by $-X$ in the above relation gives
$$ \hat f^{(i-1)}(-X) = \hat f^{(i-1)}_{\mathrm{even}}(X^2) - X \cdot \hat f^{(i-1)}_{\mathrm{odd}}(X^2). $$Adding and subtracting the relations at $X$ and $-X$ gives
$$ \hat f^{(i-1)}_{\mathrm{even}}(X^2) = \frac{ \hat f^{(i-1)}(X)+\hat f^{(i-1)}(-X) }{2}, $$and
$$ \hat f^{(i-1)}_{\mathrm{odd}}(X^2) = \frac{ \hat f^{(i-1)}(X)-\hat f^{(i-1)}(-X) }{2X}. $$Evaluating the univariate fold identity in equation $(1)$ at $X^2$ gives
$$ \hat f^{(i)}(X^2) = (1-u_{i-1}) \cdot \hat f^{(i-1)}_{\mathrm{even}}(X^2) + u_{i-1} \cdot \hat f^{(i-1)}_{\mathrm{odd}}(X^2). $$Substituting the even and odd parts into this equation gives the following identity for $X\neq0$:
$$ \hat f^{(i)}(X^2) = (1-u_{i-1}) \frac{ \hat f^{(i-1)}(X)+\hat f^{(i-1)}(-X) }{2} + u_{i-1} \frac{ \hat f^{(i-1)}(X)-\hat f^{(i-1)}(-X) }{2X}. $$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$:
$$ \hat f^{(i)}(r^2) \stackrel{?}{=} (1-u_{i-1}) \frac{ \hat f^{(i-1)}(r)+\hat f^{(i-1)}(-r) }{2} + u_{i-1} \frac{ \hat f^{(i-1)}(r)-\hat f^{(i-1)}(-r) }{2r}. $$The construction presented here is HyperKZG, a variant of Gemini. Gemini represents multilinear polynomials in coefficient form, whereas HyperKZG works directly in point-evaluation form. This is often more practical because a witness in a SNARK protocol is typically encoded as evaluations over the Boolean hypercube.
Using Gemini with this representation requires the prover to convert the evaluations over the Boolean hypercube into the coefficients of the multilinear polynomial using an FFT. This takes $O(N\log N)$ time, where $N=2^n$. HyperKZG avoids this conversion by working directly with the point-evaluation representation.
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:
-
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.
-
Sample the evaluation challenge. After receiving all the intermediate commitments, the verifier samples a random nonzero challenge $ r\xleftarrow{\$}\mathbb F^* $ and sends it to the prover.
-
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.
-
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:
| Component | Cost |
|---|---|
| Proof size | $O(n)$ field elements |
| Prover work | $O(2^n)$ field operations, $O(2^n)$ group scalar mults |
| Verifier work | $O(n)$ field operations, $O(n)$ group scalar mults, two pairing terms |
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.