The Multivariate Sumcheck Protocol is an important PIOP (Polynomial IOP) component in zero-knowledge proofs. It mainly proves the correctness of the following equation:
\[ c = \sum_{\vec{x} \in \{0,1\}^n} f(X_1, ..., X_n) \]
Here, $c$ is the sum result, and $X_1, ..., X_n$ are $d$ variables, each taking the value 0 or 1.Unlike traditional univariate polynomial operations, multiplication of multivariate polynomials does not require complex FFT operations — only pointwise multiplication is needed. We will now introduce the basics of multivariate polynomials, including their representation and operations.
Let $\vec{g} = g^0, g^1, ..., g^7$ be an order-8 multiplicative subgroup in a large prime field, where:
\[ g^8 = 1 \]
We can encode position $i$ in the Boolean domain $g^i$ as its binary representation $000, 001, ..., 111$ to construct all evaluation points for a multivariate Boolean function. A univariate polynomial $f(X)$ can thus be represented as a multivariate polynomial $f(\vec{X}) = f(X_0, X_1, ..., X_7)$:
\[ (f(g^0), f(g^1), ..., f(g^7)) = (f(0,0,0), f(0,0,1), ..., f(1,1,1)) \]
Each value corresponds one-to-one, effectively flattening the high-dimensional Boolean function into a vector.
The multilinear extension can be stored as a vector in little-endian order:
\[ E[1] = \tilde{f}(0,0,0,1), \quad E[5] = \tilde{f}(0,1,0,1), \quad E[8] = \tilde{f}(1,0,0,0) \]
This is similar to storing point values using their binary representation in decimal indexing.
We want to extend $f$ from Boolean points to a function $\tilde{f}$ over the whole domain $F^n$.
Definition:\[ \chi_w(x) = \begin{cases} 1 & w = x \\ 0 & \text{otherwise} \end{cases} \]
The multivariate polynomial\[ \chi_w(x) = \prod_{i=1}^n [(1 - x_i)(1 - w_i) + x_i w_i] \]
is analogous to the Lagrange basis for univariate polynomials and is usually precomputed during system setup.
To convert from evaluation form to coefficient form, more generally for multivariates:\[ \tilde{f}(x_1, ..., x_n) = \sum_{w \in \{0,1\}^n} f(w) \cdot \chi_w(x_1, ..., x_n) \]
Here, $\tilde{f}$ is also known as the Multilinear Extension (MLE).
The multilinear extension can also be stored in vector form using little-endian ordering, e.g.:
\[ E[1] = \tilde{f}(0,0,0,1), \quad E[5] = \tilde{f}(0,1,0,1), \quad E[8] = \tilde{f}(1,0,0,0) \]
If the polynomial is $f(X_3, X_2, X_1, X_0)$, then $E[1]$, $E[5]$, $E[8]$ store the coefficients for the terms $X_0$, $X_2 \cdot X_0$, and $X_3$, respectively.
Suppose we need to compute $x_1 = r$. Let:
\[ \tilde{f}(x_2, ..., x_n) = \tilde{f}(r, x_2, ..., x_n) \]
let n = 2^v;
let half = n / 2;
for i in 0..half {
let low = E[i];
let high = E[half + i];
E[i] = low + r * (high - low);
}This works because:
\[ \tilde{f}(r, x_2, ..., x_n) = (1 - r) \cdot \tilde{f}(0, x_2, ..., x_n) + r \cdot \tilde{f}(1, x_2, ..., x_n) \]
This method computes the value at $r$ directly in evaluation form, without converting to coefficient form. Both time and space complexity are $O(n)$.
In multivariate polynomial systems, MLE $\times$ MLE (Multilinear Extension $\times$ Multilinear Extension) operations are widely used in zkSNARK protocols based on the multivariate sumcheck.
Let $f,g$ be two MLE functions over the Boolean hypercube $0,1^v$ (each polynomial is linear in each variable). They can be represented by their evaluation vectors over all $2^v$ points.
Using evaluation form, we can efficiently compute:
\[ f(r_1, ..., r_v) \cdot g(r_1, ..., r_v) \]
— i.e., pointwise multiplication at the same point.
If the evaluation form length is insufficient (e.g., degree $d$ not reached), it must be padded to length $d$ first. This is because multiplication increases degree (up to double), and keeping length $d$ ensures correct subsequent IFFT or Lagrange interpolation.
This is analogous to univariate polynomial handling in FFT: pointwise multiplication after FFT, then IFFT to return to coefficient form. Multivariate MLE pointwise multiplication follows the same principle, but on the high-dimensional Boolean hypercube.
The goal is to prove:\[ \sum_{x \in \{0,1\}^n} f(x_1, ..., x_n) = c \]
Protocol steps:
The last-round verification can be done by querying a polynomial oracle or by having the Prover compute it directly in evaluation form.
The Multivariate Sumcheck Protocol provides an efficient and modular method to verify large multilinear polynomial sums over the Boolean hypercube without explicitly evaluating the function on all 2n points. By iteratively reducing an n-variate sum to a sequence of univariate checks, it minimizes communication and computational costs for both prover and verifier. Its reliance on multilinear extensions and evaluation-form computations eliminates the need for heavy FFTs in high dimensions, making it especially suitable for zero-knowledge proof systems such as zkSNARKs and GKR. The protocol’s structure not only ensures soundness through random challenges but also integrates cleanly with other PIOP components, enabling scalable verification in modern cryptographic protocols.
Subscribe to the ZKM Blog to stay updated with the latest research by ZKM.
Explore the ZKM Docs
Start building with ZKM GitHub
Follow ZKM on X
The Multivariate Sumcheck Protocol is an important PIOP (Polynomial IOP) component in zero-knowledge proofs. It mainly proves the correctness of the following equation:
\[ c = \sum_{\vec{x} \in \{0,1\}^n} f(X_1, ..., X_n) \]
Here, $c$ is the sum result, and $X_1, ..., X_n$ are $d$ variables, each taking the value 0 or 1.Unlike traditional univariate polynomial operations, multiplication of multivariate polynomials does not require complex FFT operations — only pointwise multiplication is needed. We will now introduce the basics of multivariate polynomials, including their representation and operations.
Let $\vec{g} = g^0, g^1, ..., g^7$ be an order-8 multiplicative subgroup in a large prime field, where:
\[ g^8 = 1 \]
We can encode position $i$ in the Boolean domain $g^i$ as its binary representation $000, 001, ..., 111$ to construct all evaluation points for a multivariate Boolean function. A univariate polynomial $f(X)$ can thus be represented as a multivariate polynomial $f(\vec{X}) = f(X_0, X_1, ..., X_7)$:
\[ (f(g^0), f(g^1), ..., f(g^7)) = (f(0,0,0), f(0,0,1), ..., f(1,1,1)) \]
Each value corresponds one-to-one, effectively flattening the high-dimensional Boolean function into a vector.
The multilinear extension can be stored as a vector in little-endian order:
\[ E[1] = \tilde{f}(0,0,0,1), \quad E[5] = \tilde{f}(0,1,0,1), \quad E[8] = \tilde{f}(1,0,0,0) \]
This is similar to storing point values using their binary representation in decimal indexing.
We want to extend $f$ from Boolean points to a function $\tilde{f}$ over the whole domain $F^n$.
Definition:\[ \chi_w(x) = \begin{cases} 1 & w = x \\ 0 & \text{otherwise} \end{cases} \]
The multivariate polynomial\[ \chi_w(x) = \prod_{i=1}^n [(1 - x_i)(1 - w_i) + x_i w_i] \]
is analogous to the Lagrange basis for univariate polynomials and is usually precomputed during system setup.
To convert from evaluation form to coefficient form, more generally for multivariates:\[ \tilde{f}(x_1, ..., x_n) = \sum_{w \in \{0,1\}^n} f(w) \cdot \chi_w(x_1, ..., x_n) \]
Here, $\tilde{f}$ is also known as the Multilinear Extension (MLE).
The multilinear extension can also be stored in vector form using little-endian ordering, e.g.:
\[ E[1] = \tilde{f}(0,0,0,1), \quad E[5] = \tilde{f}(0,1,0,1), \quad E[8] = \tilde{f}(1,0,0,0) \]
If the polynomial is $f(X_3, X_2, X_1, X_0)$, then $E[1]$, $E[5]$, $E[8]$ store the coefficients for the terms $X_0$, $X_2 \cdot X_0$, and $X_3$, respectively.
Suppose we need to compute $x_1 = r$. Let:
\[ \tilde{f}(x_2, ..., x_n) = \tilde{f}(r, x_2, ..., x_n) \]
let n = 2^v;
let half = n / 2;
for i in 0..half {
let low = E[i];
let high = E[half + i];
E[i] = low + r * (high - low);
}This works because:
\[ \tilde{f}(r, x_2, ..., x_n) = (1 - r) \cdot \tilde{f}(0, x_2, ..., x_n) + r \cdot \tilde{f}(1, x_2, ..., x_n) \]
This method computes the value at $r$ directly in evaluation form, without converting to coefficient form. Both time and space complexity are $O(n)$.
In multivariate polynomial systems, MLE $\times$ MLE (Multilinear Extension $\times$ Multilinear Extension) operations are widely used in zkSNARK protocols based on the multivariate sumcheck.
Let $f,g$ be two MLE functions over the Boolean hypercube $0,1^v$ (each polynomial is linear in each variable). They can be represented by their evaluation vectors over all $2^v$ points.
Using evaluation form, we can efficiently compute:
\[ f(r_1, ..., r_v) \cdot g(r_1, ..., r_v) \]
— i.e., pointwise multiplication at the same point.
If the evaluation form length is insufficient (e.g., degree $d$ not reached), it must be padded to length $d$ first. This is because multiplication increases degree (up to double), and keeping length $d$ ensures correct subsequent IFFT or Lagrange interpolation.
This is analogous to univariate polynomial handling in FFT: pointwise multiplication after FFT, then IFFT to return to coefficient form. Multivariate MLE pointwise multiplication follows the same principle, but on the high-dimensional Boolean hypercube.
The goal is to prove:\[ \sum_{x \in \{0,1\}^n} f(x_1, ..., x_n) = c \]
Protocol steps:
The last-round verification can be done by querying a polynomial oracle or by having the Prover compute it directly in evaluation form.
The Multivariate Sumcheck Protocol provides an efficient and modular method to verify large multilinear polynomial sums over the Boolean hypercube without explicitly evaluating the function on all 2n points. By iteratively reducing an n-variate sum to a sequence of univariate checks, it minimizes communication and computational costs for both prover and verifier. Its reliance on multilinear extensions and evaluation-form computations eliminates the need for heavy FFTs in high dimensions, making it especially suitable for zero-knowledge proof systems such as zkSNARKs and GKR. The protocol’s structure not only ensures soundness through random challenges but also integrates cleanly with other PIOP components, enabling scalable verification in modern cryptographic protocols.
Subscribe to the ZKM Blog to stay updated with the latest research by ZKM.
Explore the ZKM Docs
Start building with ZKM GitHub
Follow ZKM on X
