sumcheck

Sumcheck is a family of interactive proof techniques used to verify sums of evaluations of polynomials over the boolean hypercube. The most well-known variant, the Sumcheck Protocol, was introduced by Lund, Fortnow, Karloff, and Nisan as part of arithmetization in interactive proofs and PCP theory. The protocol enables a verifier to check a global sum efficiently by reducing it to a sequence of univariate checks, with the prover and verifier exchanging polynomials and random challenges.

In the usual setting, f is a multivariate polynomial over a finite field F, and the goal is to verify the sum S = sum over all x in {0,1}^n of f(x). F is typically large enough to ensure soundness. The prover claims S and provides a sequence of univariate polynomials g1, g2, ..., gn. Each gi encodes a partial sum obtained by fixing previous variables to random challenges and summing over the remaining ones. The verifier checks that each gi has bounded degree and that the claimed sums satisfy the appropriate consistency relations, using fresh random field elements ri at every round. After the first round, the verifier validates that g1(0) + g1(1) equals S. The verifier then samples r1 and restricts f to a lower-dimensional polynomial by fixing the first variable to r1. This process repeats for the next variables, each time reducing the dimension by one. After n rounds, a final single-variable check confirms consistency with the previously claimed value; if all checks pass, the verifier accepts S.

Key properties include completeness (honest provers are always accepted) and soundness (a cheating prover is unlikely to convince the verifier). The soundness error decreases with the number of rounds and the size of the field used. Sumcheck is foundational in interactive proofs and arithmetization-based constructions, and it underpins many PCP-based protocols and modern zero-knowledge proofs. Variants extend the approach to different domains, degree bounds, or zero-knowledge settings.