Week 2: Understanding The Sumcheck Protocol

Sumcheck

Sumcheck is an interactive protocol where a prover convinces a verifier that a multivariate polynomial has hypercube evaluations that sum up to S. Since we are using Sumcheck for Zerocheck, S = 0. This protocol proceeds over n rounds.

The prover first computes a univariate “round” polynomial, Rₖ(X), defined by:

Rₖ(X) = ∑ (for v ∈ {0,1}ⁿ⁻ᵏ⁻¹) D(r’₀, …, r’ₖ₋₁, X, v₀, …, vₙ₋ₖ₋₂).

After that, the verifier checks if Rₖ(0) + Rₖ(1) = Sₖ. Initially, S₀ = S. If the verification is passed, then the protocol proceeds to the next round.

To transition to round k+1, the verifier sets Sₖ₊₁ = Rₖ(r’ₖ) and sends a new random challenge r’ₖ₊₁ to the prover.

If the prover passes all n rounds, the verifier can be confident that the multivariate polynomial sums up to S on the hypercube.

Security

The security of the Sumcheck protocol relies on the mathematical guarantee that a cheating prover cannot convince the verifier of a false claim. This guarantee is based on the Schwartz-Zippel lemma.

Suppose a prover wants to cheat and provide a fake polynomial. In the first round, the cheating prover is forced to invent and send a fake polynomial R’₀(X) of degree d that satisfies R’₀(0) + R’₀(1) = S₀.

After the prover commits to this fake polynomial, the verifier samples a random challenge r’₀ from a large finite field F. The target for the next round is set to S₁ = R’₀(r’₀). For the prover to lie successfully and continue with the protocol, the fake polynomial must intersect the true polynomial at this exact random point, meaning R’₀(r’₀) = R₀(r’₀).

However, the Schwartz-Zippel Lemma states that two distinct polynomials of degree d can intersect at a maximum of d points. Since the verifier selects r’₀ randomly from the entire field F, the probability of accidentally picking an intersection point is very low:

Pr[R’ₖ(r’ₖ) = Rₖ(r’ₖ)] ≤ d / |F|

Because the protocol runs for n rounds, the probability that the prover succeeds is thus:

Pr[False Proof] ≤ (n · d) / |F|

Since we will use a very large field (e.g. F over 2²⁵⁶), it is extremely unlikely that the prover is able to fake a proof. Thus, we can be confident in the security of this protocol.