Variants of KZG: Part V, Multilinear Commitments with Mercury

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

In Part IV, we studied Gemini, which recursively restricts a multilinear polynomial one variable at a time. The prover commits to each intermediate partial evaluation, resulting in an opening proof whose size grows with the number of variables. In this final part of the series, we study Mercury, which improves on this approach by folding half of the variables at once.

Notation. We continue to use the notation from Part IV. Univariate polynomials are denoted with a hat, while multilinear polynomials are denoted without a hat. We write $\mathcal U_m$ for the univariatization map on $m$-variate multilinear polynomials.

To understand how Mercury performs this large fold, we will first look at how to organize the evaluations of a multilinear polynomial into blocks.

Organizing Evaluations into Blocks#

For simplicity, assume that $n=2t$, define $N=2^n$ and $T=2^t=\sqrt N$. We split the evaluation point into two halves:

We represent the multilinear polynomial $f$ by its $N$ evaluations over the Boolean hypercube and index this evaluation vector using two indices $i,j\in\{0,\ldots,T-1\}$ as follows:

where $\vec{i},\vec{j}\in\{0,1\}^t$ denote the $t$-bit binary representations of $i$ and $j$, respectively. The first index represents the assignment to $\vec X_L=(X_0,\ldots,X_{t-1})$, while the second represents the assignment to $\vec X_R=(X_t,\ldots,X_{n-1})$.

We treat the first index as the least significant index. Thus, the evaluation vector is ordered as

For each fixed $i$, define the vector $\vec f_i=(f_{i,0},\ldots,f_{i,T-1})$ and its corresponding univariate block polynomial $\hat f_i$ as follows.

Since the first index is the least significant, the evaluation $f_{i,j}$ becomes the coefficient of $X^{i+jT}$ after univariatization. Therefore,

With this block representation in place, we can now see how Mercury extends Gemini’s single-variable fold to several variables at once.

From Gemini to Mercury#

Now recall that Gemini (Part IV) splits a multilinear polynomial with respect to the first variable $X_0$ as follows:

There are two parts because $X_0$ can be set to either $0$ or $1$. Mercury instead groups the first $t$ variables and splits the polynomial over all $T=2^t$ Boolean assignments to these variables. The corresponding $T$-way decomposition is

where, for $\vec a,\vec b\in\mathbb F^t$, $\operatorname{eq}(\vec a,\vec b) = \prod_{k=0}^{t-1} \left(a_kb_k+(1-a_k)(1-b_k)\right)$. Here, $\vec X_L=(X_0,\ldots,X_{t-1})$ denotes the first $t$ variables, while $\vec X_R=(X_t,\ldots,X_{n-1})$ denotes the remaining variables. This is the multilinear interpolation expression over the first $t$ variables. When $t=1$, the two equality weights are $1-X_0$ and $X_0$, so this expression reduces to the two-way Gemini decomposition.

Mercury folds the first $t$ variables by computing the partial evaluation

The verifier must check that the partial evaluation $h$ is consistent with $f$ using the above identity. But the above identity is over multilinear polynomials, whereas we want to use univariate KZG. Therefore, we reduce the consistency check of the above multilinear identity to that of its corresponding univariate identity by applying the univariatization map. Since $\mathcal U_t$ is linear,

Now index each $\vec b\in\{0,1\}^t$ by $i\in\{0,\ldots,T-1\}$, where $\vec b=\vec{i}$. By the definition of the block polynomial $\hat f_i$ from the previous section, we have the following:

Substituting the above expression in equation $(2)$ gives the following univariate identity:

Ideally, the verifier would check the above identity at a random point $\alpha\in\mathbb F$. If the identity is invalid, then by the Schwartz-Zippel lemma, it agrees at a random $\alpha$ only with small probability.

However, the verifier only has the commitment to $\hat f$ (the univariatization of multilinear $f$) and does not have commitments to the block polynomials $\hat f_i$. Therefore, the verifier cannot check the above identity. A naive approach would require the prover to send the $T$ commitments to $\hat f_i$ and their claimed evaluations at $\alpha$, making the proof size depend on $T$.

Can we pack all the values $\hat f_i(\alpha)$ into a single polynomial that is directly related to $\hat f(X)$?

The block decomposition of $\hat f$, from equation $(1)$ of the previous section, suggests how to do this:

Working modulo $X^T-\alpha$ is equivalent to replacing every occurrence of $X^T$ by $\alpha$. Therefore,

Thus, the remainder of this division is a polynomial $\hat g(X)$ of degree less than $T$:

whose coefficients are exactly $\hat f_i(\alpha)$. Accordingly, the prover divides $\hat f(X)$ by $(X^T-\alpha)$ and obtains the quotient $\hat q$ and the remainder $\hat g$ such that,

Now the $t$-variate multilinear polynomial $g$ whose univariate encoding is $\hat g$ will be as follows:

The evaluation of $g$ at $\vec u_L$ is exactly $\hat h(\alpha)$, i.e.,

Thus, we have reduced the check from expression $(3)$ to the following two checks:

However, the above checks alone are not enough. The verifier must also check $\deg(\hat g) < T$, because without this degree check the quotient $\hat q$ and remainder $\hat g$ are not unique. The check $\deg(\hat g) < T$ makes $\hat g$ the unique remainder of division by $X^T-\alpha$ and ensures that its $T$ coefficients encode a $t$-variate multilinear polynomial $g$.

Up to this point, we have only checked the consistency of the partial evaluation $h$ with respect to the multilinear polynomial $f$. Our goal, however, is to check the full evaluation $f(\vec u_L,\vec u_R)=v$. Using the partial evaluation expression $h(\vec X_R)=f(\vec u_L,\vec X_R)$ and setting $\vec X_R=\vec u_R$, we get

Therefore, the verifier must also check that the partial evaluation $h$ evaluates to the original claimed value $v$, i.e.,

To summarize the sequence of reductions, the original claim $f(\vec u)\stackrel{?}{=}v$ has been reduced to the following checks:

• Two multilinear evaluation checks, which are batched together and proved using an inner product protocol. - $g(\vec u_L)\stackrel{?}{=}\hat h(\alpha)$ connects the partial evaluation $h$ to the remainder $g$. - $h(\vec u_R)\stackrel{?}{=}v$ checks that the partial evaluation $h$ is consistent with the claimed value $v$.
• $\deg(\hat g) < T$ ensures that $\hat g$ is a valid remainder modulo $(X^T-\alpha)$.
• $\hat f(X) \stackrel{?}{=} (X^T-\alpha) \cdot \hat q(X)+\hat g(X)$ checks consistency between $\hat g$ and $\hat f$. The prover first commits to $\hat q$ and $\hat g$. The verifier then samples a random point $z$ and the prover uses a KZG opening to prove the following. $$\hat f(z) \stackrel{?}{=} (z^T-\alpha) \cdot \hat q(z)+\hat g(z)$$

Now there are only two missing pieces: the inner product protocol to prove multilinear evaluations and the degree check protocol. Next we will look into each of them.

Multilinear Evaluation as an Inner Product#

Consider a multilinear polynomial $g$ in $t$ variables. We can express $g$ using the equality function as follows:

For $\vec u \in \mathbb{F}^t$, the goal is to prove that $g(\vec u) = v$. Mercury reduces this multilinear evaluation claim to an inner product between coefficients of univariate polynomials.

We have the following univariatization of $g$, where the $T=2^t$ evaluations of $g$ over the Boolean hypercube are the coefficients of the univariate polynomial $\hat g$.

We can also encode the evaluations of the equality function as coefficients of a polynomial:

The product form allows the verifier to evaluate $\hat P_{\vec u}$ using $O(t)=O(n)$ field operations.

Then, we can reduce the evaluation claim $g(\vec u) = v$ to the inner product of coefficients of the univariate polynomials $\hat P_{\vec u}$ and $\hat g$ as follows:

Mercury has an elegant technique of proving such inner products. Observe that $\langle \hat P_{\vec u},\hat g\rangle$ is the constant coefficient of the following function.

Therefore, the claim $\langle \hat P_{\vec u},\hat g\rangle=v$ is equivalent to the existence of polynomials $\hat S_1$ and $\hat S_2$ such that

Here, $\hat S_1$ contains the negative-degree terms, while $\hat S_2$ contains the positive-degree terms. Checking this identity directly would require commitments to both $\hat S_1$ and $\hat S_2$. Mercury instead symmetrizes the expression:

Thus, the prover only needs to commit to one polynomial $\hat S$ and the inner product claim reduces to checking the above identity at a random point.

We now apply this observation to the following two multilinear evaluation claims from the previous section.

We first reduce these multilinear evaluation claims to the following inner product claims.

Mercury batches the two inner product claims using a random challenge $\gamma\in\mathbb F$. The prover constructs a polynomial $\hat S$ satisfying

We have reduced the two multilinear evaluation claims to checking the above identity. Finally, the verifier checks the above identity at a random non-zero point $z \in \mathbb{F}^*$.

The last remaining piece is the degree check protocol, which ensures $\deg(\hat g) < T$. We examine it next.

Degree Check Protocol#

The degree check protocol used in Mercury is different from the degree check protocol that we studied for Zeromorph in Part III.

The goal is to prove $\deg(\hat g) < T$. The prover defines

To see why this enforces the degree bound, write $\hat g(X)=\sum_{i=0}^{d}g_iX^i$. Then,

If $d < T$, every exponent is nonnegative, so $\hat D$ is a polynomial. If $d\geq T$, the term $g_dX^{T-1-d}$ has a negative exponent, so $\hat D$ is not a polynomial. A dishonest prover could still commit to an unrelated polynomial $\hat D$, so the verifier must bind the committed $\hat D$ to $X^{T-1}\hat g(1/X)$ using the following identity at a random nonzero point $z\in\mathbb F^*$.

We have all the pieces required to describe the complete end-to-end protocol.

End-To-End Protocol#

The public inputs are the original univariate KZG commitment $C=\left[\hat f(\tau)\right]_1$, the evaluation point $\vec u=(\vec u_L,\vec u_R)$ and the claimed evaluation $v$. The prover’s witness is the multilinear polynomial $f$.

1. Commit to the large fold. The prover computes

   $$\hat h(X) = \sum_{i=0}^{T-1} \operatorname{eq}(\vec{i},\vec u_L) \cdot \hat f_i(X)$$

   and sends its univariate KZG commitment $C_h=\left[\hat h(\tau)\right]_1$ to the verifier.

2. Commit to the quotient and remainder. The verifier samples $\alpha\xleftarrow{\raisebox{0pt}{\textdollar}}\mathbb F$ and sends it to the prover. The prover computes

   $$\hat f(X) = (X^T-\alpha) \cdot \hat q(X)+\hat g(X), \qquad \deg(\hat g) < T$$

   and sends

   $$C_q=\left[\hat q(\tau)\right]_1 \qquad\text{and}\qquad C_g=\left[\hat g(\tau)\right]_1.$$

3. Commit to the batched inner product proof and degree check. The verifier samples a random batching challenge $\gamma\xleftarrow{\raisebox{0pt}{\textdollar}}\mathbb F$. The prover computes $\hat S$ such that

   $$\begin{aligned} \hat g(X) \cdot \hat P_{\vec u_L}(1/X) &+\hat g(1/X) \cdot \hat P_{\vec u_L}(X) + \gamma \cdot \left( \hat h(X) \cdot \hat P_{\vec u_R}(1/X) +\hat h(1/X) \cdot \hat P_{\vec u_R}(X) \right)\\ &= 2\left(\hat h(\alpha)+\gamma \cdot v\right) +X \cdot \hat S(X)+1/X \cdot \hat S(1/X) \end{aligned}$$

   and $\hat D$ such that

   $$\hat D(X)=X^{T-1}\hat g(1/X).$$

   It sends the commitments

   $$C_S=\left[\hat S(\tau)\right]_1 \qquad\text{and}\qquad C_D=\left[\hat D(\tau)\right]_1.$$

4. Open the committed polynomials. The verifier samples a random nonzero challenge $z\xleftarrow{\raisebox{0pt}{\textdollar}}\mathbb F^*$. The prover sends

   $$\begin{aligned} g_z&=\hat g(z), & \bar g_z&=\hat g(1/z),\\ h_z&=\hat h(z), &\bar h_z&=\hat h(1/z),\\ S_z&=\hat S(z), & \bar S_z&=\hat S(1/z). \end{aligned}$$

   From these values, the verifier computes the expected evaluation of $\hat D$ at $z$ as

   $$D_z=z^{T-1}\bar g_z,$$

   and recovers the expected evaluation of $\hat h$ at $\alpha$ from the batched inner product identity:

   $$\begin{aligned} h_\alpha =\frac{1}{2}\Big(& g_z\hat P_{\vec u_L}(1/z) +\bar g_z\hat P_{\vec u_L}(z)\\ &+\gamma\big( h_z\hat P_{\vec u_R}(1/z) +\bar h_z\hat P_{\vec u_R}(z)-2v \big)\\ &-zS_z-(1/z)\bar S_z \Big) \end{aligned}$$

5. Prove the division identity. The prover computes

   $$\hat H_z(X) = \frac{ \hat f(X)-(z^T-\alpha)\hat q(X)-g_z }{X-z}$$

   and sends the KZG opening proof

   $$\pi_z=\left[\hat H_z(\tau)\right]_1.$$

   The verifier checks

   $$e\left( C-(z^T-\alpha)C_q-g_z[1]_1, [1]_2 \right) \stackrel{?}{=} e\left( \pi_z, [\tau]_2-z[1]_2 \right).$$

   This checks the division identity at the random point $z$.

6. Prove the remaining evaluations. The prover sends a batched univariate KZG proof $\pi_{\mathrm{batch}}$ for

   $$\begin{aligned} \hat g(z)&=g_z, &\hat g(1/z)&=\bar g_z,\\ \hat h(z)&=h_z, &\hat h(1/z)&=\bar h_z,\\ \hat S(z)&=S_z, &\hat S(1/z)&=\bar S_z,\\ \hat D(z)&=D_z, &\hat h(\alpha)&=h_\alpha. \end{aligned}$$

   These claims can be combined using the batched univariate KZG opening protocol from Part I. The verifier accepts if the division check and the batched opening proof are both valid.

Complexity of the Protocol#

For an $n$-variate multilinear polynomial with $N=2^n$ coefficients and $T=2^{n/2}=\sqrt N$, the major costs are as follows:

• Proof Size: The prover sends a constant number of commitments, evaluations and KZG opening proofs, independent of the number of variables $n$. Assuming that a group element is encoded using two field elements, the proof size is $O(1)$ field elements.

• Prover Cost: Major prover costs involve: - Computing the quotient $\hat q$ and remainder $\hat g$ requires $O(N)=O(2^n)$ field operations. - Computing the commitment to the polynomial $\hat H_z$, which has at most $N$ coefficients. So computing the commitment $\pi_z$ requires at most $N=2^n$ group scalar multiplications.

• Verifier Cost: The verifier evaluates $\hat P_{\vec u_L}$ and $\hat P_{\vec u_R}$ and computes the required powers of $z$ using $O(n)$ field operations. Since the number of commitments is constant, it performs $O(1)$ group scalar multiplications and two pairing terms.

The opening costs can be summarized as follows:

Conclusion#

This final post concludes the five-part series. We studied how KZG commitments extend from univariate polynomials to multilinear polynomials through quotient-based and folding-based methods.

• Part I introduces univariate KZG commitments, including their batched and hiding variants.
• Part II extends KZG to multilinear polynomials through PST, which checks the multilinear quotient identity using a specialized multivariate setup.
• Part III studies Zeromorph, which encodes the multilinear quotient identity as a univariate identity and batches the required degree checks.
• Part IV introduces Gemini, which recursively folds one variable at a time and verifies the folds using univariate KZG openings.
• Part V studies Mercury, which replaces Gemini’s sequence of single-variable folds with one large fold and reduces the opening proof to constant size.

Together, these constructions illustrate two broad approaches to multilinear KZG commitments and the different trade-offs they make in setup, proof size, prover work and verifier work.