In Part I, we studied KZG commitments in the univariate setting, i.e., the prover wants to prove to a verifier that $\hat f(u)=v$, where $\hat f$ is a univariate polynomial. In this and the subsequent parts of the series, we will explore KZG-based polynomial commitments for multilinear polynomials. A multilinear polynomial is a multivariate polynomial with degree at most one in each of its variables.
The key question we want to study throughout the remainder of this series is:
Can we construct an opening argument for a multilinear polynomial $f(X_0,\ldots,X_{n-1})$ at a point $(u_0,\ldots,u_{n-1})$, proving that $f(u_0,\ldots,u_{n-1})=v$?
Such commitments can be used with a multilinear IOP, such as Spartan, to construct a SNARK. In this part, we will study the Papamanthou-Shi-Tamassia (PST) commitment scheme.
Notation. We continue to use the notation from Part I. Write $\vec{X}=(X_0,\ldots,X_{n-1})$ and $\vec{u}=(u_0,\ldots,u_{n-1})$. Univariate polynomials are denoted with a hat, while multilinear polynomials are denoted without a hat.
Before we dive into the construction, let us study a polynomial identity for the multilinear setting.
Multilinear Polynomial Identity
In Part I, we looked at a polynomial identity in the univariate setting based on the factor theorem. If $\hat f(u)=v$, then there exists a unique quotient polynomial:
$$ \hat q(X)=\frac{\hat f(X)-v}{X-u}. $$The key idea was to check the identity $\hat f(X)-v=(X-u)\hat q(X)$ at the randomly sampled hidden setup value. If the identity is false, then it holds at the random setup value only with small probability, by the Schwartz-Zippel Lemma. The verifier performs this check using the public parameters, the commitments to $\hat f$ and $\hat q$, and bilinear pairings.
We want a similar identity in the multilinear setting. Let us specialize the variables in the reverse order $X_{n-1},X_{n-2},\ldots,X_0$. Consider the partial evaluation of $f(X_0,\ldots,X_{n-1})$ obtained by setting $X_{n-1}=u_{n-1}$:
$$ f_{n-1}(X_0,\ldots,X_{n-2}) = f(X_0,\ldots,X_{n-2},u_{n-1}). $$Now the difference
$$ f(X_0,\ldots,X_{n-1})-f_{n-1}(X_0,\ldots,X_{n-2}) = f(X_0,\ldots,X_{n-1})-f(X_0,\ldots,X_{n-2},u_{n-1}) $$vanishes when $X_{n-1}=u_{n-1}$. Thus, by the factor theorem for multivariate polynomials, it is divisible by $(X_{n-1}-u_{n-1})$, and there exists a quotient $q_{n-1}$ such that
$$ q_{n-1}(X_0,\ldots,X_{n-2}) = \frac{f(X_0,\ldots,X_{n-1})-f_{n-1}(X_0,\ldots,X_{n-2})} {X_{n-1}-u_{n-1}}. $$Thus,
$$ f(X_0,\ldots,X_{n-1})-f_{n-1}(X_0,\ldots,X_{n-2}) =(X_{n-1}-u_{n-1}) \cdot q_{n-1}(X_0,\ldots,X_{n-2}) \tag{1} $$Next, consider the partial evaluation of $f_{n-1}(X_0,\ldots,X_{n-2})$,
$$ f_{n-2}(X_0,\ldots,X_{n-3}) = f_{n-1}(X_0,\ldots,X_{n-3},u_{n-2}), $$obtained by setting $X_{n-2}=u_{n-2}$. Applying the factor theorem again gives
$$ f_{n-1}(X_0,\ldots,X_{n-2})-f_{n-2}(X_0,\ldots,X_{n-3}) =(X_{n-2}-u_{n-2}) \cdot q_{n-2}(X_0,\ldots,X_{n-3}) \tag{2} $$Adding the equations $(1)$ and $(2)$, we get
$$ \begin{aligned} f(X_0,\ldots,X_{n-1})-f_{n-2}(X_0,\ldots,X_{n-3}) ={}&(X_{n-1}-u_{n-1}) \cdot q_{n-1}(X_0,\ldots,X_{n-2})\\ &+(X_{n-2}-u_{n-2}) \cdot q_{n-2}(X_0,\ldots,X_{n-3}). \end{aligned} $$Continuing in the same way down to $X_0=u_0$, we obtain the following identity:
$$ f(X_0,\ldots,X_{n-1})-f(u_0,\ldots,u_{n-1}) = \sum_{k=0}^{n-1}(X_k-u_k) \cdot q_k(X_0,\ldots,X_{k-1}). $$Here, $q_k$ depends only on the first $k$ variables, $X_0,\ldots,X_{k-1}$, and is multilinear in those variables, while $q_0$ is constant. For the fixed specialization order $X_{n-1},X_{n-2},\ldots,X_0$, these quotient polynomials are unique.
Thus, proving $f(u_0,\ldots,u_{n-1})\stackrel{?}{=}v$ reduces to proving that there exist multilinear polynomials $q_k$ satisfying the following identity:
$$ f(X_0,\ldots,X_{n-1}) - v \; \stackrel{?}{=} \; \sum_{k=0}^{n-1}(X_k-u_k) \cdot q_k(X_0,\ldots,X_{k-1}). $$We will use this as the starting point for PST. With the basics aside, we will now look at the construction.
PST Commitment Scheme
PST is a direct multivariate generalization of KZG. The original construction supports general multivariate polynomials, but we focus on its multilinear specialization, which is more common in practice.
We need to check the following identity:
$$ f(X_0,\ldots,X_{n-1})-v \; \stackrel{?}{=} \; \sum_{k=0}^{n-1}(X_k-u_k)q_k(X_0,\ldots,X_{k-1}). $$By the Schwartz-Zippel Lemma, if the above equation is not a valid polynomial identity, then it holds at a randomly chosen point only with small probability.
Thus, during $setup$, we sample a random point $\vec{\tau}=(\tau_0,\ldots,\tau_{n-1})$ at which the above equation will be checked. The verifier performs this check using the public parameters, commitments to $f$ and the $q_k$, and bilinear pairings.
The algorithms for the construction are defined as follows.
-
$setup(n) \rightarrow pp$
- Sample $\tau_0,\ldots,\tau_{n-1}\in\mathbb{F}_p$ and let $\vec{\tau}=(\tau_0,\ldots,\tau_{n-1})$.
- Compute the commitment key $ck$ containing encodings of all $2^n$ monomials of $\vec{\tau}$: $$ ck=\left( \left\{\left[\prod_{i=0}^{n-1}\tau_i^{b_i}\right]_1: \vec{b}\in\{0,1\}^n\right\} \right). $$
- Compute the verification key $vk$ containing an encoding of each $\tau_i$: $$ vk=\left( [1]_1,[1]_2,[\tau_0]_2,\ldots,[\tau_{n-1}]_2 \right). $$
- Output $$ pp=\left(ck, vk\right). $$
- Discard $\vec{\tau}$.
-
$commit(pp,f) \rightarrow com_f$
- Write $$ f(\vec{X})=\sum_{\vec{b}\in\{0,1\}^n}f_{\vec{b}}\prod_{i=0}^{n-1}X_i^{b_i}. $$
- Compute $$ com_f=[f(\vec{\tau})]_1 =\sum_{\vec{b}\in\{0,1\}^n}f_{\vec{b}} \left[\prod_{i=0}^{n-1}\tau_i^{b_i}\right]_1. $$
-
$open(\mathcal{P},\mathcal{V}) \rightarrow 0/1$
- $\mathcal{P}$ sends $com_f$ to $\mathcal{V}$.
- $\mathcal{V}$ samples $\vec{u}=(u_0,\ldots,u_{n-1})\in\mathbb{F}_p^n$ and requests an opening at $\vec{u}$.
- $\mathcal{P}$ computes $v=f(\vec{u})$ and quotient polynomials $q_0,\ldots,q_{n-1}$ satisfying $$ f(\vec{X})-v=\sum_{k=0}^{n-1}(X_k-u_k)q_k(X_0,\ldots,X_{k-1}). $$ $\mathcal{P}$ sends $v$ and $\pi_k=\operatorname{com}_{q_k}$ for every $k=0,\ldots,n-1$.
- $\mathcal{V}$ accepts if and only if $$ e(com_f-v[1]_1,[1]_2) \stackrel{?}{=} \prod_{k=0}^{n-1}e\left(\pi_k,[\tau_k]_2-u_k[1]_2\right). $$
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 one quotient commitment $\pi_k$ for each variable. Therefore, the opening proof contains $n$ elements in $\mathbb{G}_1$. Assuming, $\mathbb{G}_1$-element is encoded by two field elements, the proof size in $O(n)$ field elements.
- Prover Cost: The major prover costs include the following operations:
- Compute the quotient polynomials: At step $k$, the quotient polynomial is as follows: $$ q_k(X_0,\ldots,X_{k-1}) = \frac{f_{k+1}(X_0,\ldots,X_k)-f_k(X_0,\ldots,X_{k-1})} {X_k-u_k}, $$ where $f_k$ is obtained from $f_{k+1}$ by setting $X_k=u_k$. Since $f_{k+1}$ has degree at most one in $X_k$, we can split it as $$ f_{k+1}(X_0,\ldots,X_k) = A_k(X_0,\ldots,X_{k-1}) + X_kB_k(X_0,\ldots,X_{k-1}). $$ Setting $X_k=u_k$ gives $f_k=A_k+u_kB_k$. Now substituting these into the quotient gives $$ \begin{aligned} q_k &= \frac{f_{k+1}-f_k}{X_k-u_k}\\ &= \frac{A_k+X_kB_k-(A_k+u_kB_k)} {X_k-u_k}\\ &=B_k. \end{aligned} $$ The prover takes $B_k$ as the quotient $q_k$ and computes $f_k=A_k+u_kB_k$. Both $A_k$ and $B_k$ have at most $2^k$ coefficients. Computing $A_k+u_kB_k$ requires one multiplication and one addition per coefficient, giving $O(2^k)$ field operations. Repeating this for every $k$ gives a total cost of $$ \sum_{k=0}^{n-1}O(2^k)=O(2^n) $$ field operations. The final partial evaluation is $f_0=f(\vec{u})$, so this same computation also produces the claimed value $v$.
- Commit to the multilinear polynomial $f$ and quotients $q_k$: Since $f$ has at most $2^n$ coefficients, committing to $f$ requires an MSM of size at most $2^n$. Committing to $q_k$ requires an MSM of size at most $2^k$. Therefore, committing to $f$ and all the quotients requires $n+1$ MSMs with a combined size of $$ 2^n+\sum_{k=0}^{n-1}2^k=2^{n+1}-1, $$ giving $O(2^n)$ group scalar multiplications.
- Verifier Cost: For each $k=0,\ldots,n-1$, the verifier computes $[\tau_k]_2-u_k[1]_2$. This requires $O(n)$ group scalar multiplications. The final pairing check has $n+1$ pairing terms: one involving the commitment $com_f$ and claimed evaluation $v$, and one for each of the $n$ quotient commitments.
Equivalently, the 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)$ group scalar mults, $n+1$ pairings |
Limitations of PST
- PST requires a commitment key containing cross-products of hidden values. It could be deployed by performing a separate trusted setup ceremony for its public parameters. However, such ceremonies are an operational burden and require significant coordination, implementation and auditing. Moreover, existing univariate KZG parameters do not directly contain the cross-products of independent hidden values required by PST. This motivates us to construct a multilinear PCS using the established univariate powers-of-$\tau$ setup structure and ceremony infrastructure.
- PST verification has $n + 1$ pairing terms. Thus, its verification cost grows linearly with the number of variables.
Conclusion
PST extends the KZG quotient argument directly to multilinear polynomials. For an evaluation claim $f(\vec{u})=v$, the prover commits to one multilinear quotient polynomial for each variable, and the verifier checks the resulting identity using bilinear pairings.
This direct approach is conceptually simple, but it requires a specialized multivariate setup and a number of pairing terms that grows linearly with the number of variables. This motivates a different question:
Can we retain the multilinear quotient identity while using univariate polynomial commitments?
In the next part, we will study Zeromorph, which constructs a multilinear PCS using an additively homomorphic univariate PCS (like univariate KZG) and a degree check protocol.