# Variants of KZG: Part V, Multilinear Commitments with Mercury - **Authors**: Varun Thakore - **Date**: August 17, 2026 - **Tags**: educative, zk ![KZG-V Header](https://blog.zksecurity.xyz/posts/kzg-5/top.png) 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. $$ \hat f_i(X)=\sum_{j=0}^{T-1}f_{i,j} \cdot X^j $$ 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: $$ \begin{aligned} f(X_0,X_1,\ldots,X_{n-1}) ={}&(1-X_0) \cdot f(0,X_1,\ldots,X_{n-1})\ &+X_0 \cdot f(1,X_1,\ldots,X_{n-1}) \end{aligned} $$ 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. $$ \hat h(\alpha) \stackrel{?}{=} \sum_{i=0}^{T-1} \operatorname{eq}(\vec{i},\vec u_L) \cdot \hat f_i(\alpha) \tag{3} $$ 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: $$ \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 the quotient $\hat q$ and the remainder $\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$. - $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$. 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. **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{\$}\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 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. $$ 3. **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. $$ **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. $$ 4. **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} $$ **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} $$ 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$. **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](https://blog.zksecurity.xyz/posts/kzg-1/#batched-variants). The verifier accepts if the division check and the batched opening proof are both valid. **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$. Assuming that a group element is encoded using two field elements, the proof size is $O(1)$ field elements. **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. **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. **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. --- This article was published on the [ZK/SEC Quarterly](https://blog.zksecurity.xyz) blog by [ZK Security](https://www.zksecurity.xyz), a leading security firm specialized in zero-knowledge proofs, MPC, FHE, and advanced cryptography. ZK Security has audited some of the most critical ZK systems in production, discovered vulnerabilities in major protocols including Aleo, Solana, and Halo2, and built open-source tools like [Clean](https://github.com/Verified-zkEVM/clean) for formally verified ZK circuits. For more articles, see the [full list of posts](https://blog.zksecurity.xyz/llms.txt).