Variants of KZG: Part V, Multilinear Commitments with Mercury

ZKSecurity's final part of its KZG series details Mercury, a multilinear commitment scheme that folds half of a polynomial's variables at once, reducing opening proof size compared to Gemini's one-variable-at-a-time approach. The scheme, introduced in a 2025 IACR paper (eprint 2025/385), organizes evaluations into blocks and uses a T-way decomposition to check partial evaluations via univariate KZG.

In Part IV https://blog.zksecurity.xyz/posts/kzg-4/ , 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 https://eprint.iacr.org/2025/385.pdf , which improves on this approach by folding half of the variables at once. Notation. We continue to use the notation from Part IV https://blog.zksecurity.xyz/posts/kzg-4/ . 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: $$ \vec u= \vec u L,\vec u R , \qquad \vec u L= u 0,\ldots,u {t-1} , \qquad \vec u R= u t,\ldots,u {n-1} . $$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: $$ f {i,j} = f\left \vec{i},\vec{j}\right , $$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 $$ \left f {0,0},f {1,0},\ldots,f {T-1,0}, f {0,1},\ldots,f {T-1,1}, \ldots, f {0,T-1},\ldots,f {T-1,T-1} \right . $$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, $$ \hat f X =\mathcal U n f X =\sum {i=0}^{T-1}\sum {j=0}^{T-1}f {i,j} \cdot X^{i+jT} =\sum {i=0}^{T-1}X^i \cdot \hat f i X^T \tag{1} $$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 https://blog.zksecurity.xyz/posts/kzg-4/ 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 $$ f \vec X L,\vec X R = \sum {\vec b\in\{0,1\}^t} \operatorname{eq} \vec b,\vec X L \cdot f \vec b,\vec X R $$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 $$ h \vec X R =f \vec u L,\vec X R = \sum {\vec b\in\{0,1\}^t} \operatorname{eq} \vec b,\vec u L \cdot f \vec b,\vec X R $$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, $$ \hat h X = \mathcal U t h X = \sum {\vec b\in\{0,1\}^t} \operatorname{eq} \vec b,\vec u L \cdot \mathcal U t\left f \vec b,\vec X R \right X \tag{2} $$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: $$ \begin{aligned} \mathcal U t\left f \vec{i},\vec X R \right X = \sum {j=0}^{T-1} f\left \vec{i},\vec{j}\right \cdot X^j = \hat f i X \end{aligned} $$Substituting the above expression in equation $ 2 $ gives the following univariate identity: $$ \hat h X = \sum {i=0}^{T-1} \operatorname{eq} \vec{i},\vec u L \cdot \hat f i X $$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 https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel 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 they 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: $$ \hat f X = \sum {i=0}^{T-1}X^i \cdot \hat f i X^T $$Working modulo $X^T-\alpha$ is equivalent to replacing every occurrence of $X^T$ by $\alpha$. Therefore, $$ \hat f X \equiv \sum {i=0}^{T-1}X^i \cdot \hat f i \alpha \mod{ X^T-\alpha } $$Thus, the remainder of this division is a polynomial $\hat g X $ of degree less than $T$: $$ \hat g X = \hat f X \mod{ X^T-\alpha } = \sum {i=0}^{T-1}\hat f i \alpha \cdot X^i $$whose coefficients are exactly $\hat f i \alpha $. Accordingly, the prover divides $\hat f X $ by $ X^T-\alpha $ and obtains polynomials $\hat q,\; \hat g$ such that, $$ \hat f X = X^T-\alpha \cdot \hat q X +\hat g X , \qquad \deg \hat g < T. $$Now the $t$-variate multilinear polynomial $g$ whose univariate encoding is $\hat g$ will be as follows: $$ g \vec X = \sum {i=0}^{T-1} \operatorname{eq} \vec{i},\vec X \cdot \hat f i \alpha $$The evaluation of $g$ at $\vec u L$ is exactly $\hat h \alpha $, i.e., $$ \begin{aligned} g \vec u L &= \sum {i=0}^{T-1} \operatorname{eq} \vec{i},\vec u L \hat f i \alpha \\ &=\hat h \alpha \end{aligned} $$Thus, we have reduced the check from expression $ 3 $ to the following two checks: $$ \hat h \alpha \stackrel{?}{=} \sum {i=0}^{T-1} \operatorname{eq} \vec{i},\vec u L \cdot \hat f i \alpha \quad \Longrightarrow \quad \begin{cases} g \vec u L \stackrel{?}{=} \hat h \alpha \\ \hat f X \stackrel{?}{=} X^T-\alpha \cdot \hat q X +\hat g X \end{cases} $$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 $$ h \vec u R =f \vec u L,\vec u R = v $$Therefore, the verifier must also check that the partial evaluation $h$ evaluates to the original claimed value $v$, i.e., $$ h \vec u R \stackrel{?}{=}v $$To summarize the sequence of reductions, the original claim $f \vec u \stackrel{?}{=}v$ has been reduced to the following checks: $$ f \vec u \stackrel{?}{=}v \Longrightarrow \begin{cases} g \vec u L \stackrel{?}{=}\hat h \alpha \quad \text{and} \quad h \vec u R \stackrel{?}{=}v\\ \deg \hat g < T\\ \hat f X \stackrel{?}{=} X^T-\alpha \cdot \hat q X +\hat g X \end{cases} $$- 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: $$ g \vec X = \sum {\vec b \in \{0,1\}^t} \operatorname{eq} \vec b,\vec X \cdot g \vec b $$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$. $$ \hat g X = \sum {i=0}^{T-1} g \vec i \cdot X^i $$We can also encode the evaluations of the equality function as coefficients of a polynomial: $$ \hat P {\vec u} X = \sum {i=0}^{T-1} \operatorname{eq} \vec{i},\vec u \cdot X^i = \prod {k=0}^{t-1} \left 1-u k +u kX^{2^k}\right $$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: $$ \langle \hat P {\vec u}, \hat g \rangle = \sum {i=0}^{T-1} \operatorname{eq} \vec{i},\vec u \cdot g \vec i = g \vec u = v $$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. $$ \hat P {\vec u} X \cdot \hat g 1/X $$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 $$ \hat P {\vec u} X \cdot \hat g 1/X = 1/X \cdot \hat S 1 1/X + v + X \cdot \hat S 2 X . $$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: $$ \hat P {\vec u} X \cdot \hat g 1/X + \hat P {\vec u} 1/X \cdot \hat g X = 2v+X \cdot \hat S X +1/X \cdot \hat S 1/X $$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. $$ g \vec u L \stackrel{?}{=}\hat h \alpha \quad \text{and} \quad h \vec u R \stackrel{?}{=}v $$We first reduce these multilinear evaluation claims to the following inner product claims. $$ \left\langle \hat g,\hat P {\vec u L}\right\rangle \stackrel{?}{=} \hat h \alpha \quad\text{and}\quad \left\langle \hat h,\hat P {\vec u R}\right\rangle \stackrel{?}{=} v $$Mercury batches the two inner product claims using a random challenge $\gamma\in\mathbb F$. The prover constructs a polynomial $\hat S$ satisfying $$ \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} $$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 https://blog.zksecurity.xyz/posts/kzg-3 . The goal is to prove $\deg \hat g < T$. The prover defines $$ \hat D X =X^{T-1} \cdot \hat g 1/X . $$To see why this enforces the degree bound, write $\hat g X =\sum {i=0}^{d}g iX^i$. Then, $$ \hat D X =X^{T-1}\hat g 1/X =\sum {i=0}^{d}g iX^{T-1-i}. $$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^ $. $$ \hat D z \stackrel{?}{=}z^{T-1} \cdot \hat g 1/z $$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$. - 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. - Commit to the quotient and remainder. The verifier samples $\alpha\xleftarrow{\$}\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. $$ - Commit to the batched inner product proof and degree check. The verifier samples a random batching challenge $\gamma\xleftarrow{\$}\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. $$ - Open the committed polynomials. The verifier samples a random nonzero challenge $z\xleftarrow{\$}\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} $$ - 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$. - 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 https://blog.zksecurity.xyz/posts/kzg-1/ batched-variants . 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$. Following the convention in the Mercury paper 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: | Component | Cost | |---|---| | Proof size | $O 1 $ field elements | | Prover work | $O 2^n $ field operations, $O 2^n $ group scalar mults | | Verifier work | $O n $ field operations, $O 1 $ group scalar mults, two pairing terms | 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 https://blog.zksecurity.xyz/posts/kzg-1/ introduces univariate KZG commitments, including their batched and hiding variants. Part II https://blog.zksecurity.xyz/posts/kzg-2/ extends KZG to multilinear polynomials through PST, which checks the multilinear quotient identity using a specialized multivariate setup. Part III https://blog.zksecurity.xyz/posts/kzg-3/ studies Zeromorph, which encodes the multilinear quotient identity as a univariate identity and batches the required degree checks. Part IV https://blog.zksecurity.xyz/posts/kzg-4/ introduces Gemini, which recursively folds one variable at a time and verifies the folds using univariate KZG openings. Part V https://blog.zksecurity.xyz/posts/kzg-5/ 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.