The SUMCHECK protocol

I won’t delve deeply into its introduction here, but the SUMCHECK protocol (Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan. “Algebraic Methods for Interactive Proof Systems”, 1992) serves as a foundation for many “verifiable computation” primitives. If you’re reading this, you likely already know its significance.

Let \(\mathbb{F}\) be a finite field and \(f(X_1, X_2, \ldots, X_n)\) be a multivariate polynomial of degree \(d\) over \(\mathbb{F}\). Consider the sum \(S\) defined as:

\[S = \sum_{x_1\in\{0, 1\}} \sum_{x_2\in\{0, 1\}} \cdots \sum_{x_n\in\{0, 1\}} f(x_1, x_2, \ldots, x_n) = \sum_{(x_1, x_2, \ldots, x_n) \in \{0,1\}^n} f(x_1, x_2, \ldots, x_n)\]

The SUMCHECK protocol provides an \(n\) round interactive protocol to verify the correctness of \(S\), using only a single evaluation of \(f\) (i.e. the verifier only has to evaluate \(f(X)\) once, rather than \(2^n\) times).

The protocol advances through \(n\) rounds. In each round, the prover sends a univariate polynomial to the verifier. In response, the verifier conducts a check and responds by sending a single field element challenge.

Round 1

The prover computes and shares the univariate polynomial:

\[f_1(X) = \sum_{(x_2, \ldots, x_n) \in \{0,1\}^{n-1}} f(X, x_2, x_3, \ldots, x_n)\]

The verifier ensures that the degree of \(f_1\) is less than \(d\), checks if \(f_1(0) + f_1(1) = S\), and issues the challenge \(r_1 \in \mathbb{F}\).

Round 2

The prover computes and shares the univariate polynomial:

\[f_2(X) = \sum_{(x_3, \ldots, x_n) \in \{0,1\}^{n-2}} f(r_1, X, x_3, x_4, \ldots, x_n)\]

The verifier ensures that the degree of \(f_2\) is less than \(d\), checks if \(f_2(0) + f_2(1) = f_1(r_1)\), and issues the challenge \(r_2 \in \mathbb{F}\).

Round \(i\)

The prover computes and shares the univariate polynomial:

\[f_i(X) = \sum_{(x_{i+1}, \ldots, x_n) \in \{0,1\}^{n-i}} f(r_1, \ldots, r_{i-1}, X, x_{i+1}, x_{i+2}, \ldots, x_n)\]

The verifier ensures that the degree of \(f_i\) is less than \(d\), checks if \(f_i(0) + f_i(1) = f_{i-1}(r_{i-1})\), and issues the challenge \(r_i \in \mathbb{F}\).

Round \(n\)

The prover computes and shares the univariate polynomial:

\[f_n(X) = f(r_1, \ldots, r_{n-1}, X)\]

The verifier ensures that the degree of \(f_n\) is less than \(d\), checks if \(f_n(0) + f_n(1) = f_{n-1}(r_{n-1})\), and issues the challenge \(r_n \in \mathbb{F}\).

Final check

The verifier evaluates \(f(r_1, \ldots, r_n)\) and confirms that it equals \(f_n(r_n)\).

Why does it work

Below, I present an intuitive proof for the efficacy of the SUMCHECK protocol, assuming a large field \(\mathbb{F}\). For this explanation, the Schwartz-Zippel lemma is essential.

The Schwartz-Zippel Lemma

The Schwartz-Zippel lemma states: For a non-zero multivariate polynomial \(P(X_1, \ldots, X_n)\) with a total degree of at most \(d\) over the field \(\mathbb{F}\), when evaluating \(P\) at random points \(r_1, \ldots, r_n\) from \(\mathbb{F}\), the likelihood of \(P(r_1, \ldots, r_n)\) being zero is less than \(\frac{d}{\lvert\mathbb{F}\rvert}\).

In large fields (like the scalar fields of elliptic curves often, which are cryptographically secure with field sizes around \(2^{256}\)), this probability is minuscule. This is because a polynomial can only have a limited number of zeros. For a univariate polynomial, this is immediately evident from the “factor theorem”: Every zero of the polynomial corresponds to a linear factor, so a degree \(d\) polynomial can have up to \(d\) zeros.

A common application of the Schwartz-Zippel lemma is comparing two univariate polynomials, \(f(X)\) and \(g(X)\), to determine their identity. By generating a random number \(r \in \mathbb{F}\) and checking if \(f(r) = g(r)\), we can determine if they are the same. This method is correct, but is it also sound? What’s the likelihood of erroneously claiming \(f(X)\) and \(g(X)\) are identical when they aren’t?

Claim: If \(f(X) \not= g(X)\), then the probability of the check being successful is at most \(\frac{d}{\lvert\mathbb{F}\rvert}\).

Proof: Let’s set \(P(X) = f(X) - g(X)\). Given that \(f(X) \not= g(X)\), \(P(X)\) isn’t the zero polynomial. As per Schwartz-Zippel, the chance of \(P(r) = f(r) - g(r) = 0\) is at most \(\frac{d}{\lvert\mathbb{F}\rvert}\).

A succinct takeaway from Schwartz-Zippel is: Over large fields, two “low-degree” polynomials are either identical or different almost everywhere.

SUMCHECK protocol proof

The SUMCHECK protocol harnesses this property to convert a sum with a potentially large number of terms into a singular evaluation. Let’s see why it works, by trying to create a prover that attempts to cheat the protocol, attempting to prove a sum \(\tilde S \not= S\).

Round 1

The prover needs to send a polynomial \(\tilde f_1(X)\) with the property \(\tilde f_1(0) + \tilde f_1(1) = \tilde S\). Any other choice would make the first check fail immediately, so there would be no point.

Since \(\tilde S \not= S\), the prover cannot send the honest polynomial \(f_1(X)\). Recall that this means that the polynomial they will be sending is different almost everywhere from \(f_1(X)\); more precisely, it is the same as \(f_1\) on at most \(d\) points.

The verifier then sends the challenge \(r_1\).

Round 2

In round 2, the prover needs to send a polynomial \(\tilde f_2(X)\) with the property that \(\tilde f_2(0) + \tilde f_2(1) = \tilde f_1(r_1)\).

Now there are two possibilities:

\(\tilde f_1(r_1)= f_1(r_1)\). In this case the prover has hit the jackpot: He can simply send \(f_2(X)\) (the “honest” answer) and continue the protocol honestly to the end. He will succeed at cheating. However, the probability for this happening is only \(\frac{d}{\lvert\mathbb{F}\rvert}\).
\(\tilde f_1(r_1) \not= f_1(r_1)\) (which is overwhelmingly likely). In this case, the prover is in the same situation as before: He cannot send the honest \(f_2(X)\), but only a malicious \(\tilde f_2(X)\) with \(\tilde f_2(0) + \tilde f_2(1) = \tilde f_1(r_1)\), which can coincide with the honest answer on at most \(d\) points.

This repeats every round:

Round \(i\)

In round \(i\), the prover needs to send a polynomial \(\tilde f_i(X)\) with the property that \(\tilde f_i(0) + \tilde f_i(1) = \tilde f_{i-1}(r_{i-1})\).

Again, two possibilities:

\(\tilde f_{i-1}(r_{i-1}) = f_{i-1}(r_{i-1})\). Prover wins (probability of this happening \(\frac{d}{\lvert\mathbb{F}\rvert}\)).
\(\tilde f_{i-1}(r_{i-1}) \not= f_{i-1}(r_{i-1})\). Prover needs to send \(\tilde f_i(X)\) with \(\tilde f_i(0) + \tilde f_i(1) = \tilde f_{i-1}(r_{i-1})\)

Final check

Finally, in the last round, the verifier checks if \(f(r_1, \ldots, r_n)=f_n(r_n)\). Assuming the prover didn’t “win” in one of the rounds before, he sends a malicious \(\tilde f_n(X)\) which coincides with the honest \(f_n(r_n)\) on at most \(d\) points, so the probability that the final check will pass is \(\frac{d}{\lvert\mathbb{F}\rvert}\).

As you can see from the above analysis, the prover has a small probability of “winning” and cheating the verifier in each round: If his polynomial happens to have the same evaluation on the challenge field element as the honest version, the prover can continue the protocol like an honest prover and the verification will succeed.

However, assuming that the field \(\mathbb{F}\) is large, the probability for this is small. Since there are \(n\) rounds, at best, the prover can succeed with probability \(\frac{nd}{\lvert\mathbb{F}\rvert}\).