Variants of KZG: Part III, Multilinear Commitments with Zeromorph

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

In Part II, we studied PST, which checks the multilinear quotient identity directly using multivariate public parameters. PST requires a specialized setup containing cross-products of several hidden values, and its pairing cost grows linearly with the number of variables.

Zeromorph instead encodes the multilinear quotient identity as a univariate identity. It is a generic construction that builds a multilinear PCS using an additively homomorphic univariate PCS and a degree-check protocol. It works with any additively homomorphic univariate PCS, but we will specifically look at its instantiation with univariate KZG.

Notation. We continue to use the notation from Part II. 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. For a univariate polynomial $\hat p(X)=\sum_jp_jX^j$, we write $\hat p^{< d}(X)=\sum_{j=0}^{d-1}p_jX^j$ for its truncation to terms of degree less than $d$.

The starting point of Zeromorph is the same as that of PST. Checking $f(u_0,\ldots,u_{n-1})\stackrel{?}{=}v$ is equivalent to checking the following multilinear quotient identity:

Instead of checking this identity over multivariate polynomials, as we did with PST in Part II, Zeromorph checks this identity over univariate polynomials. This requires an encoding from multilinear polynomials to univariate polynomials, which we will study next.

Univariatization Map#

The linear map from $n$-variate multilinear polynomials to univariate polynomials of degree at most $2^n - 1$ is defined as follows:

For a multilinear polynomial $f$, its univariate encoding is defined as

In other words, the evaluations of $f$ over the Boolean hypercube become the coefficients of the univariate polynomial. For example, when $n=2$,

The map $\mathcal{U}_n$ has the following properties:

1. Linearity: For multilinear polynomials $f,g$ and scalars $\alpha,\beta\in\mathbb{F}$,

   $$\mathcal{U}_n(\alpha \cdot f+\beta \cdot g)(X) = \alpha \cdot \mathcal{U}_n(f)(X) + \beta \cdot \mathcal{U}_n(g)(X).$$

2. One-to-one correspondence: Each evaluation $f(\vec b)$ is stored as a distinct coefficient of $\mathcal{U}_n(f)$. Thus, we can recover all the evaluations of $f$ by reading the coefficients of $\mathcal{U}_n(f)$. These evaluations uniquely determine the multilinear polynomial $f$, so no information is lost. Conversely, the coefficients of any univariate polynomial of degree less than $2^n$ determine the evaluations of exactly one multilinear polynomial over the Boolean hypercube. A map with this property is called bijective.

Therefore, $\mathcal{U}_n$ is linear and bijective. A map with both these properties is called a linear isomorphism.

In the next section, we will apply this univariatization map $\mathcal{U}_n$ to the multilinear quotient identity and get the univariate identity.

Multilinear-to-Univariate Identity#

Applying the univariatization map $\mathcal{U}_n$ to the multilinear quotient identity gives

Using linearity of $\mathcal{U}_n$,

We will now see how to further decompose each of $\mathcal{U}_n(v)$, $\mathcal{U}_n(q_k)$, and $\mathcal{U}_n(X_k \cdot q_k)$.

Univariatization of $v$#

Consider the constant $n$-variate multilinear polynomial defined by

It is independent of $X_0, \ldots, X_{n-1}$ and takes the same value $v$ over the $n$-dimensional Boolean hypercube.

Let us understand this with the help of the following table. The first two columns list the points on the Boolean hypercube and the corresponding evaluations of $g$, while the last two columns list the corresponding monomials and coefficients in the univariate encoding.

Thus, the univariatization of $v$ is

where $\Phi_n(X)=1+X+\cdots+X^{2^n-1}$.

Univariatization of $q_k$#

Let us understand this for $k=2$, that is, for $q_2(X_0, X_1)$, which is multilinear in $X_0, X_1$ and independent of the variables $X_2, \ldots, X_{n-1}$.

Suppose the evaluations of $q_2(X_0, X_1)$ are as follows:

The resulting table is as follows:

Thus, the univariatization of $q_2$ is

Here, $\hat q_2(X)=\mathcal{U}_n(q_2)^{<4}(X)=a+bX+cX^2+dX^3$ is the truncation of $\mathcal{U}_n(q_2)$ to terms of degree less than $4$.

For a general $k\in\{0,\ldots,n-1\}$, define $\hat q_k(X)=\mathcal{U}_n(q_k)^{<2^k}(X)$. The univariatization $\mathcal{U}_n(q_k)$ begins with the $2^k$ coefficients of $\hat q_k(X)$. This block of coefficients repeats $2^{n-k}$ times in $\mathcal{U}_n(q_k)$. Therefore,

where $\Phi_n(X)=1+X+\cdots+X^{2^n-1}$.

Univariatization of $X_k \cdot q_k$#

Let us first understand this for $k=2$. Since $q_2(X_0,X_1)$ is independent of $X_2$, multiplying it by $X_2$ makes its evaluation zero whenever $X_2=0$. When $X_2=1$, its evaluations are the same as those of $q_2$. This is shown in the following table:

Thus, the univariatization of $X_2 \cdot q_2$ is

For a general $k\in\{0,\ldots,n-1\}$, multiplication by $X_k$ makes the evaluation zero whenever $X_k=0$. The coefficients of $\hat q_k$ occur when $X_k=1$, starting at degree $2^k$, and repeat every $2^{k+1}$ powers. Therefore,

where $\Phi_n(X)=1+X+\cdots+X^{2^n-1}$ and, for $k=n-1$, $\Phi_0(X)=1$.

Univariate Identity#

Now that we have the decompositions for $\mathcal{U}_n(v)$, $\mathcal{U}_n(q_k)$, and $\mathcal{U}_n(X_k \cdot q_k)$, we substitute them into the following identity:

This gives us the univariate identity

where $\hat f(X) = \mathcal{U}_n(f)(X)$ and $\hat q_k(X)=\mathcal{U}_n(q_k)^{<2^k}(X)$.

Define the following univariate polynomial:

By the Schwartz-Zippel Lemma, if the verifier checks that $Z(\tau)=0$ at the randomly sampled secret setup value $\tau$, then, with high probability, $Z(X)$ is the zero polynomial and the univariate identity holds. However, the verifier cannot directly check $Z(\tau) \stackrel{?}{=} 0$ because $\tau$ is secret and the verifier cannot compute the following term for the pairing check:

To address this issue, the verifier samples a random point $x\in\mathbb{F}$ and asks the prover to prove that $Z(x)=0$. To do so, the prover constructs the following polynomial $Z_x(X)$, in which the coefficients multiplying the quotient polynomials are evaluated at $x$:

Note that $Z(x) = Z_x(x)$. Thus, the prover proves that $Z_x(x)=0$. The verifier can compute the commitment to $Z_x$ using the commitments to $\hat f$ and the $\hat q_k$, since the commitments are additively homomorphic.

However, only checking $Z_x(x) \stackrel{?}{=} 0$ is not enough. The KZG opening will verify that $Z_x(x)=0$, but it does not ensure that each committed polynomial $\hat q_k$ has the degree required to encode a multilinear quotient in the first $k$ variables. Without this check, the prover could use a polynomial of degree greater than $2^k-1$. Therefore, the protocol must additionally check that for every $k$, $\deg\left(\hat{q}_k\right)<2^k$.

At first, it seems that the protocol must also check that $\deg\left(\hat{f}\right) < 2^n$. However, this bound follows from the quotient degree bounds and the polynomial identity below.

If, for every $k$, $\deg\left(\hat{q}_k\right)<2^k$, then each summand on the right has degree at most $(2^n-2^k)+(2^k-1)=2^n-1$. Since $\deg\left(\Phi_n\right) = 2^n - 1$, the identity automatically implies $\deg\left(\hat{f}\right) < 2^n$. Thus, no separate degree check on $\hat{f}$ is required.

To summarize, we have reduced the claim $f(u_0,\ldots,u_{n-1})=v$ to the following checks:

• the identity check $Z_x(x)\stackrel{?}{=}0$;
• the $n$ degree checks $\deg\left(\hat q_k\right)<2^k$ for $k\in\{0,\ldots,n-1\}$.

Zeromorph batches the $n$ degree checks and reduces them to a single KZG opening that also enforces a degree bound. We study this degree-bounded KZG opening protocol next.

Degree-Bounded KZG Opening#

Let $N_{\max}$ be a strict upper bound on the degree of polynomials supported by the KZG commitment scheme. Thus, the commitment key contains

Given a univariate polynomial $\hat f(X)$ and a claimed degree bound $d$, the goal is to prove both

This protocol is a simple modification of univariate KZG. We start with the following KZG identity:

Multiplying both sides by $X^{N_{\max}-d}$ gives

The prover commits to $\hat q_{\mathrm{shift}}(X)=\hat q(X) \cdot X^{N_{\max}-d}$, and the verifier checks the following identity at the secret setup value $\tau$ using bilinear pairings:

Note that $\deg(\hat q_{\mathrm{shift}})\leq(d-1)+(N_{\max}-d)=N_{\max}-1$. Therefore, $\hat q_{\mathrm{shift}}$ can be committed using the KZG commitment key.

The end-to-end protocol is described as follows:

1. $\mathcal{P}$ sends $com_{\hat f}$ to $\mathcal{V}$.
2. $\mathcal{V}$ samples $u \in \mathbb{F}^*$ and requests an opening at $u$.
3. $\mathcal{P}$ sends the evaluation $v$ and the commitment $$cm=[\hat q_{\mathrm{shift}}(\tau)]_1 =\left[\hat q(\tau)\tau^{N_{\max}-d}\right]_1.$$
4. $\mathcal{V}$ accepts if and only if $$e\left(cm,[\tau]_2-u[1]_2\right) \stackrel{?}{=} e\left(com_{\hat f}-v[1]_1,[\tau^{N_{\max}-d}]_2\right).$$

Note that in addition to $[1]_2$ and $[\tau]_2$, the verifier key contains the higher power $[\tau^{N_{\max}-d}]_2$.

The protocol enforces $\hat f(u)=v$ only when $u\neq0$. Thus, the verifier samples $u$ from $\mathbb{F}^*$. The condition $u\neq0$ is essential: if $u=0$, then $X-u=X$ shares a factor with $X^{N_{\max}-d}$, allowing a dishonest prover to claim any value $v$ and set

When $\deg(\hat f)\leq d$, the above polynomial has degree at most $N_{\max}-1$ and satisfies the identity

even when $\hat f(0)\neq v$. Thus, the pairing check could accept an incorrect evaluation claim at $u=0$.

The protocol also enforces $\deg(\hat f)\leq d$. If $\deg(\hat f)>d$, then $\deg(\hat q)\geq d$, and hence

The prover therefore cannot commit to $\hat q_{\mathrm{shift}}$, since the commitment key supports polynomials of degree at most $N_{\max}-1$.

We will now look at the batched degree-check protocol.

Batched Degree-Check Protocol#

For univariate polynomials $\hat q_0(X),\ldots,\hat q_{n-1}(X)$, the goal is to prove that

The idea is to shift each polynomial so that the shifted polynomials have the same degree bound and then combine them using a random challenge. We can then run the degree check on this single combined polynomial.

Let $d^*\geq\max_k d_k$ and $y\in\mathbb{F}$ be the random challenge. For $\hat q_k$ with $\deg(\hat q_k)\leq d_k$, the shifted polynomial is

Note that if $\deg(\hat q_k)\leq d_k$, then the corresponding shifted polynomial has degree at most $d^*+1$. We take a random linear combination of these shifted polynomials:

If every $\hat q_k$ satisfies its degree bound, then $\deg(\hat Q)\leq d^*+1$. Conversely, if any $\hat q_k$ violates its degree bound, then, with high probability over the random challenge $y$, $\deg(\hat Q)>d^*+1$. Thus, the $n$ degree checks reduce to the following two checks:

• a single degree check on $\hat Q$, that is, $\deg(\hat Q)\leq d^*+1$;
• a check that $\hat Q$ is well-formed, that is, its commitment is consistent with the commitments to the $\hat q_k$.

The verifier samples a random point $x\in\mathbb{F}$, after which the prover computes

The prover then proves the following:

• $\deg(\zeta_x)\leq d^*+1$: This proves that $\deg(\hat Q)\leq d^*+1$, which implies that $\deg(\hat q_k)\leq d_k$.
• $\zeta_x(x)=0$: This proves that the commitment to $\hat Q$ is consistent with the commitments to the $\hat q_k$.

At this point, the claim $f(u_0,\ldots,u_{n-1})=v$ has been reduced to the following checks:

• the identity check $Z_x(x)\stackrel{?}{=}0$;
• the evaluation and degree checks $\zeta_x(x)\stackrel{?}{=}0$ and $\deg(\zeta_x)\leq d^*+1$.

In the final Zeromorph opening protocol, we choose $d^*=2^n-2$ so that $\zeta_x$ and $Z_x$ have the same degree bound, $2^n-1$. The verifier then samples a random challenge $z\in\mathbb{F}$ and uses it to combine the two polynomials:

Finally, the prover and verifier run the degree-bounded KZG opening protocol to prove that $\hat H_x(x)=0$ and $\deg(\hat H_x)\leq2^n-1$. With high probability over $z$, this single invocation enforces both evaluation checks and the required degree bound.

We now have all the building blocks needed to present the end-to-end Zeromorph opening protocol.

End-to-End Opening Protocol#

The end-to-end opening protocol proceeds as follows:

1. $\mathcal{P}$ computes the univariate encoding of $f$,

   $$\hat f(X)=\mathcal U_n(f)(X)$$

   and sends the commitment $C=[\hat f(\tau)]_1$ to $\mathcal{V}$.

2. $\mathcal{V}$ samples $(u_0, \ldots, u_{n-1})\xleftarrow{\raisebox{0pt}{\textdollar}}\mathbb F^n$ and sends it to $\mathcal{P}$.

3. $\mathcal{P}$ computes the multilinear quotient polynomials $q_0,\ldots,q_{n-1}$ and their univariate encodings

   $$\hat q_k(X)=\mathcal U_n(q_k)^{<2^k}(X).$$

   It sends the commitments $C_k=[\hat q_k(\tau)]_1, \; k\in\{0,\ldots,n-1\},$ and the evaluation $v$ to $\mathcal V$.

4. $\mathcal V$ samples a random challenge $y\xleftarrow{\raisebox{0pt}{\textdollar}}\mathbb F$ (used to batch degree checks) and sends it to $\mathcal P$.

5. $\mathcal P$ computes the shifted random linear combination

   $$\hat Q(X) = \sum_{k=0}^{n-1} y^kX^{2^n-d_k-1}\hat q_k(X)$$

   and sends its commitment $C_{\hat Q}=[\hat Q(\tau)]_1$ to $\mathcal V$.

6. $\mathcal V$ samples $x\xleftarrow{\raisebox{0pt}{\textdollar}}\mathbb F^*$ (a nonzero opening point) and $z\xleftarrow{\raisebox{0pt}{\textdollar}}\mathbb F$ (used to batch $Z_x$ and $\zeta_x$), and sends both challenges to $\mathcal P$. Using the homomorphic property of KZG commitments, $\mathcal V$ computes the commitments to $Z_x$ and $\zeta_x$ as follows:

   $$\begin{aligned} C_{Z_x} &=C-v \cdot \Phi_n(x)[1]_1 -\mathop{\Large\sum}_{k=0}^{n-1} \Bigg( x^{2^k}\Phi_{n-k-1}\left(x^{2^{k+1}}\right) -u_k\Phi_{n-k}\left(x^{2^k}\right) \Bigg) \cdot C_k,\\ C_{\zeta_x} &=C_{\hat Q} -\sum_{k=0}^{n-1} y^kx^{2^n-d_k-1}C_k. \end{aligned}$$

   Then $\mathcal V$ combines the two commitments as

   $$C_{\hat H_x}=C_{\zeta_x}+ z \cdot C_{Z_x}.$$

7. $\mathcal P$ computes the corresponding polynomials $Z_x$ and $\zeta_x$.

   $$\begin{aligned} Z_x(X) &=\hat f(X)-v\Phi_n(x) \\ & \quad \quad -\mathop{\Large\sum}_{k=0}^{n-1} \Bigg( x^{2^k} \cdot \Phi_{n-k-1}\left(x^{2^{k+1}}\right) -u_k \cdot \Phi_{n-k}\left(x^{2^k}\right) \Bigg) \cdot \hat q_k(X), \\ \zeta_x(X) &=\hat Q(X) -\sum_{k=0}^{n-1} y^kx^{2^n-d_k-1}\hat q_k(X). \end{aligned}$$

   Then $\mathcal P$ combines the two polynomials as

   $$\hat H_x(X) = \zeta_x(X) + z \cdot Z_x(X).$$

8. $\mathcal P$ and $\mathcal V$ run the degree-bounded KZG opening protocol on $C_{\hat H_x}$, with opening point $x$, claimed evaluation $0$, and degree bound $2^n-1$. This proves

   $$\hat H_x(x)=0 \qquad\text{and}\qquad \deg(\hat H_x)\leq 2^n-1.$$

We will now study the complexity of the opening protocol.

Complexity of the Opening Protocol#

For an $n$-variate multilinear polynomial with $2^n$ coefficients, the complexity of the opening protocol is explained as follows.

• Proof Size: The prover sends the $n$ quotient commitments $C_0,\ldots,C_{n-1}$, the commitment $C_{\hat Q}$ and the final opening proof $\pi$. Therefore, the proof contains $n+2$ elements in $\mathbb{G}_1$. Assuming each $\mathbb{G}_1$ element is encoded by two field elements, the proof size is $O(n)$ field elements.

• Prover Cost: The major prover costs include the following operations:

  • Compute and commit to the quotient polynomials: As shown in the complexity analysis of PST in Part II, computing the quotient polynomials and the claimed evaluation $v=f(\vec u)$ requires $O(2^n)$ field operations. Committing to $f$ requires an MSM of size $2^n$, while committing to all the quotient polynomials requires MSMs with a combined size of $2^n-1$. The same bounds apply to the univariate encodings $\hat f$ and $\hat q_k$ because they contain the same number of coefficients.
  • Compute the batched polynomials: The quotient encodings contain $2^n-1$ coefficients in total, and each batching or division step makes a linear pass over at most $2^n$ coefficients. Therefore, computing $\hat Q$, $Z_x$, $\zeta_x$, $\hat H_x$, and the final opening quotient requires $O(2^n)$ field operations.
  • Commit to $\hat Q$: Every shifted term $X^{2^n-d_k-1}\hat q_k(X)$ ends at degree at most $2^n-1$. Thus, computing $C_{\hat Q}$ requires at most $2^n-1$ group scalar multiplications.
  • Compute quotient commitment in degree-bound KZG: The polynomial $\hat H_x$ has degree at most $2^n-1$, so its opening quotient has at most $2^n-1$ coefficients. Computing the shifted commitment $\pi$ therefore requires an MSM of size at most $2^n-1$.

• Verifier Cost: The verifier receives the quotient commitments $C_0,\ldots,C_{n-1}$ from the prover. It computes the field values needed to form $C_{Z_x}$ and $C_{\zeta_x}$, including the required powers of $x$ and $y$ and the evaluations of the $\Phi_i$. This requires $O(n)$ field operations. The verifier then forms $C_{Z_x}$ and $C_{\zeta_x}$ as linear combinations of the received commitments, requiring $O(n)$ group scalar multiplications. Additionally, the final check has two pairing terms.