Sumcheck Protocol
The Sumcheck protocol is an efficient tool to develop succinct arguments.
It is relied upon by many proof systems, such as Lasso/Jolt by a16z crypto, HyperPlonk, Binius, Spartan, and GKR.
Sumcheck was first proposed by Lund, Fortnow, Karloff, & Nisan in 1992.
The sumcheck protocol is an interactive protocol working over multivariate polynomials, that is, polynomials in many variables, such as p(x1,x2) = 1 + x2 + 5 x1x2 + x1^6.
The prover tries to convince the verifier that the sum of all the evaluations of the polynomial over some set is equal to some number.
For the previous polynomials, we could try to evaluate over (0,0), (1,0), (0,1), and (1,1) and sum the results (the answer is 13).
This reduces the amount of work that the verifier needs to do to check the statement.
Using the sumcheck protocol, the verifier can check the correctness of the result in O(n + cost to evaluate the polynomial at one point), where n is the number of variables, (whereas computing over all possible values takes O(2^n)).
This enables many interesting protocols, such as the zero check.
On a high-level overview, the verifier will ask the prover to sum over all variables except the first one, obtaining a univariate polynomial.
The verifier can then check the sum by evaluating the univariate polynomial over the set and summing.
To ensure that the prover didn’t give a false polynomial, the verifier will select a random point and will apply the sumcheck protocol to the n - 1 variable polynomial.
The Sumcheck protocol proceeds in n rounds, where the prover and verifier exchange messages:
The verifier can check (for the Boolean hypercube) that g1(0)+g1(1) = S0 and that g1(x1) has a degree bounded by the maximum allowable degree.
The sumcheck protocol is complete and has a soundness error equal to n d / |F|, where d is the maximum degree for each variable and |F| is the size of the field. The proof size consists of O(nd) field elements.
If you want to learn more about the Sumcheck protocol, you can read Proofs, Arguments, and Zero-Knowledge by Justin Thaler, and Ingonyama’s super sumcheck.
Stay tuned: 🐦 Twitter | 🗨️ Telegram | 👾 Discord | 🌐 Website | 📝 Manifesto
