Sum-check and zero-check protocols

Verifiable computing allows a computer to offload the computation of certain functions. For example, running transactions on the Ethereum EVM can be costly. With verifiable computing, one can outsource the computation away from the EVM—generating the proof that transactions were correctly executed elsewhere—leaving only the verification of the proof to the EVM.

The sum-check and zero-check protocols form the foundation for many verifiable computing algorithms, such as LatticeFold (opens new window) and HyperNova (opens new window).

Two essential building blocks for the sum-check and zero-check are multilinear extensions and the Schwartz-Zippel lemma (opens new window).

Multilinear extensions

A multilinear polynomial is a multivariate polynomial of degree at most one in each variable. For example, the polynomial $3xy + 4y - 2z$ is multilinear, while $3x^2 + 4y - 2z$ is not.

The following is Lemma 2 from Verifiable Computing for Approximate Computation (opens new window).

Lemma (Multilinear Extension): Given a function $V: \{0, 1\}^n \rightarrow \mathbb{F}$, there exists a unique multilinear polynomial $\tilde{V}(x): \mathbb{F}^n \rightarrow \mathbb{F}$ extending $V$, i.e., $\tilde{V}(x) = V(x)$ for all $x \in \{0, 1\}^n$. We call $\tilde{V}$ the multilinear extension (mle) of $V$ over $\mathbb{F}$.

The existence of multilinear extension $\tilde{V}$ is guaranteed from the following construction:

$\tilde{V}(x_1,...,x_n) := \sum_{b = (b_1, ..., b_n) \in \{0, 1\}^n} V(b) \cdot \Pi_{i=1}^n ((1-b_i)(1-x_i) + b_i x_i)$

Schwartz-Zippel lemma

The Schwartz-Zippel lemma is a tool commonly used in probabilistic polynomial identity testing. Suppose we have a polynomial $f(x_1, ..., x_n)$ with a degree of $d$. Let’s assume that the field has $S$ elements.

If $r_1, ..., r_n$ are chosen uniformly random and independently from the field $F$, the probability that $f(r_1, ..., r_n) = 0$ is $\leq \frac{d}{S}$.

If $S$ is much larger than $d$, this probability is very low. Therefore, if we find $f(r_1, ..., r_n) = 0$, the probability that $f$ is identically equal to $0$ is very high.

For intuition, let’s consider the case where $n = 1$. Suppose we have $f(x) = a_0 + a_1 x + ... + a_d x^d$. There are at most $d$ different values where $f$ evaluates to $0$. Therefore, the probability $f(r_1) = 0$ is smaller than $\frac{d}{S}$.

Suppose we have two polynomials, $f_1(x_1, ..., x_n)$ and $f_2(x_1, ..., x_n)$, with coefficients in the finite field $F$. What is the probability that these two polynomials are identical? This probability is the same as the probability that $f_1 - f_2$ equals $0$, which is the case we had above.

If it holds $f_1(r_1, ..., r_n) - f_2(r_1, ..., r_n) = 0$ for a random $r_1,..., r_n$, the probability that $f_1$ and $f_2$ are the same is very high.

Sum-check protocol

Suppose there is a function $f(x_1, ..., x_n)$, and a subject wants to prove that

$H = \sum_{(x_1, ..., x_n) \in \{0, 1\}^n} f(x_1, ..., x_n)$

for some value $H$. Let’s refer to this subject as a verifier.

Of course, the verifier could simply compute all the values $f(0, 0, ..., 0, 0)$, $f(0, 0, ..., 0, 1)$, $f(0, 0, ..., 1, 0)$, $f(0, 0, ..., 1, 1)$, ..., $f(1, 1, ..., 1, 1)$, and then compute the sum of these values.

But it turns out this can be done more efficiently. Suppose there is another participant, called a prover, who can assist the verifier in checking the equation above. The prover will do some of the computations, allowing the verifier to quickly verify the statement. However, the protocol must also ensure that the prover has performed the computations correctly.

The protocol that does this is sum-check protocol (opens new window).

Let’s consider the sum-check protocol for a three dimensional case. So we have $f(x_1, x_2, x_3)$.

The prover computes the following univariate polynomial:

$f_1(x_1) = \sum_{(x_2, x_3) \in \{0, 1\}^2} f(x_1, x_2, x_3)$

$= f(x_1, 0, 0) + f(x_1, 0, 1) + f(x_1, 1, 0) + f(x_1, 1, 1)$

The prover sends $f_1$ to the verifier. The verifier then checks whether

$H = f_1(0) + f_1(1)$

If this condition holds and if the function $f_1$ has been generated correctly, the verifier can be sure that $H = \sum_{(x_1, x_2, x_3) \in \{0, 1\}^3} f(x_1, x_2, x_3)$. And the verifier has performed only minimal computation in the process!

But wait! How can the verifier be certain that the function $f_1$ has been generated correctly?

Yeah, the prover and verifier are not finished yet. The prover still needs to prove that $f_1$ has been generated correctly. To do this, the verifier generates the challenge $r_1$ and sends it to the prover (this can be made non-interactive using the Fiat-Shamir transformation).

The prover then computes the following new univariate polynomial:

$f_2(x_2) = \sum_{x_3 \in \{0, 1\}^2} f(r_1, x_2, x_3)$

$= f(r_1, x_2, 0) + f(r_1, x_2, 1)$

The verifier checks whether:

$f_1(r_1) = f_2(0) + f_2(1)$

Note that:

$f_2(0) + f_2(1) = f(r_1, 0, 0) + f(r_1, 0, 1) + f(r_1, 1, 0) + f(r_1, 1, 1)$

But wait again! Isn’t $f$ defined only on the set $\{0, 1\}^3$? How do we evaluate it at some random value $r_1$? This is where the multilinear extension comes into play. We use the multilinear extension of $f$ instead of $f$. However, I will abuse notation a bit and simply continue writing $f$.

When the verifier checks that the equality $f_1(r_1) = f_2(0) + f_2(1)$ holds, the verifier can be confident that $f_1$ has been generated correctly. Well, if $f_2$ has been generated correctly.

The prover receives a new challenge $r_2$ from the verifier and computes the following new univariate polynomial:

$f_3(x_3) = f(r_1, r_2, x_3)$

The verifier checks whether the following equality holds:

$f_2(r_2) = f_3(0) + f_3(1)$

Finally, the verifier chooses the third challenge $r_3$ and verifies:

$f_3(r_3) = f(r_1, r_2, r_3)$

Where is the Schwartz-Zippel lemma used? Suppose the prover chose a function $g \neq f_3$ such that:

$f_2(r_2) = g(0) + g(1)$

The prover knows $f_2(r_2)$, so this is something the prover can compute. However, will the following equality hold?

$g(r_3) = f(r_1, r_2, r_3)$

According to the Schwartz-Zippel lemma, the probability of this occurring is very low. If it holds, it implies $g = f_3$.

Implementation detail

You never really need to compute the function:

$\tilde{V}(x_1,...,x_n) := \sum_{b = (b_1, ..., b_n) \in \{0, 1\}^n} V(b) \cdot \Pi_{i=1}^n ((1-b_i)(1-x_i) + b_i x_i)$

Even when you need to fix a variable, such as when you fix $r_n$

$\tilde{V}(x_1,..., x_{n-1}, r_n) := \sum_{b = (b_1, ..., b_n) \in \{0, 1\}^n} V(b) \cdot \Pi_{i=1}^n ((1-b_i)(1-x_i) + b_i x_i)$

you only store the $2^n$ values; you don’t actually compute the expression above. How can this be done?

Let’s use $n = 3$ again. Initially, we have a table where the following values are stored:

$\begin{pmatrix} f(0, 0, 0) \\ f(0, 0, 1) \\ f(0, 1, 0) \\ f(0, 1, 1) \\ f(1, 0, 0) \\ f(1, 0, 1) \\ f(1, 1, 0) \\ f(1, 1, 1) \end{pmatrix}$

Then, we would like to have:

$\begin{pmatrix} f(0, 0, r_1) \\ f(0, 1, r_1) \\ f(1, 0, r_1) \\ f(1, 1, r_1) \end{pmatrix}$

Note that

$\tilde{V}(x_1, x_2, x_3) = f(0, 0, 0) (1 - x_1) (1 - x_2)(1 - x_3) +$

$+f(0, 0, 1) (1 - x_1) (1 - x_2)(x_3) +$

$+ f(0, 1, 0) (1 - x_1) x_2(1 - x_3) +$

$+f(0, 1, 1) (1 - x_1) x_2 x_3 +$

$+ f(1, 0, 0) x_1 (1 - x_2) (1 - x_3) +$

$+ f(1, 0, 1) x_1 (1 - x_2) x_3 +$

$+ f(1, 1, 0) x_1 x_2 (1 - x_3) +$

$+f(1, 1, 1) x_1 x_2 x_3$

If we want to compute $\tilde{V}(0, 0, r_3)$, we observe that all terms will be zero except for the first two. From the first two terms, we get $f(0, 0, r_1) = f(0, 0, 0) (1 - r_3) + f(0, 0, 1) r_3$. To compute $f(0, 1, r_1)$, we similarly use the third and fourth terms ...

Zero-check protocol

What if we want to prove that function $f$ is equal to $0$? That is, we want to show that $f(x_1, ..., x_n) = 0$ for every $x \in \{0, 1\}^n$?

We can use sum-check for this. Let’s define:

$g(x_1, ..., x_n, b) = \Pi_{i \in \{1,...,n\}} (x_i b_i + (1 - x_i) (1 - b_i)) f(x_1, ..., x_n)$

where $b = (b_1, ..., b_n)$.

Let’s define:

$h(y_1, ..., y_n) = g(x_1, ..., x_n, y)$

where $y = (y_1, ..., y_n)$.

We can see that for $x_i \in \{0, 1\}$:

$\sum_{y \in \{0, 1\}^n} h(y_1, ..., y_n) = f(x_1, ..., x_n)$

So, if we prove that $\sum_{y \in \{0, 1\}^n} h(y_1, ..., y_n) = 0$, we have proven that $f(x_1, ..., x_n) = 0$. And we can prove $\sum_{y \in \{0, 1\}^n} h(y_1, ..., y_n) = 0$ by using the sum-check protocol. And because we have shown this for some random $(x_1, ..., x_n)$, it’s highly probable that $f$ is identical $0$ over the boolean hypercube.