# SUMCHECK Quickie

# 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 be a finite field and be a multivariate polynomial of degree over . Consider the sum defined as:

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

The protocol advances through 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:

The verifier ensures that the degree of is less than , checks if , and issues the challenge .

**Round 2**

The prover computes and shares the univariate polynomial:

The verifier ensures that the degree of is less than , checks if , and issues the challenge .

**Round **

The prover computes and shares the univariate polynomial:

The verifier ensures that the degree of is less than , checks if , and issues the challenge .

**Round **

The prover computes and shares the univariate polynomial:

The verifier ensures that the degree of is less than , checks if , and issues the challenge .

**Final check**

The verifier evaluates and confirms that it equals .

# Why does it work

Below, I present an intuitive proof for the efficacy of the SUMCHECK protocol, assuming a large field . For this explanation, the Schwartz-Zippel lemma is essential.

## The Schwartz-Zippel Lemma

The Schwartz-Zippel lemma states: For a non-zero multivariate polynomial with a total degree of at most over the field , when evaluating at random points from , the likelihood of being zero is less than .

In large fields (like the scalar fields of elliptic curves often, which are cryptographically secure with field sizes around ), 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 polynomial can have up to zeros.

A common application of the Schwartz-Zippel lemma is comparing two univariate polynomials, and , to determine their identity. By generating a random number and checking if , we can determine if they are the same. This method is *correct*, but is it also *sound*? What’s the likelihood of erroneously claiming and are identical when they aren’t?

Claim: If , then the probability of the check being successful is at most .

Proof: Let’s set . Given that , isn’t the zero polynomial. As per Schwartz-Zippel, the chance of is at most .

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 .

**Round 1**

The prover needs to send a polynomial with the property . Any other choice would make the first check fail immediately, so there would be no point.

Since , the prover cannot send the honest polynomial . Recall that this means that the polynomial they will be sending is different almost everywhere from ; more precisely, it is the same as on at most points.

The verifier then sends the challenge .

**Round 2**

In round 2, the prover needs to send a polynomial with the property that .

Now there are two possibilities:

- . In this case the prover has hit the jackpot: He can simply send (the “honest” answer) and continue the protocol honestly to the end. He will succeed at cheating. However, the probability for this happening is only .
- (which is overwhelmingly likely). In this case, the prover is in the same situation as before: He cannot send the honest , but only a malicious with , which can coincide with the honest answer on at most points.

This repeats every round:

**Round **

In round , the prover needs to send a polynomial with the property that .

Again, two possibilities:

- . Prover wins (probability of this happening ).
- . Prover needs to send with

**Final check**

Finally, in the last round, the verifier checks if . Assuming the prover didn’t “win” in one of the rounds before, he send a malicious which coincides with the honest on at most points, so the probability that the final check will pass is .

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 is large, the probability for this is small. Since there are rounds, at best, the prover can succeed with probability .