The sumcheck protocol was a landmark development in the early 1990s. The protocol led to Shamir’s proof that the space of interactive protocols was the same as PSPACE (the set of problems that can be solved using a polynomial amount of space). The sumcheck protocol has been used in subroutine for a variety of protocols such as GKR [Delegating computation: Interactive proofs for muggles]. More recently, Scroll’s zkVM, Ceno, uses GKR (and thus sumcheck).
Sumcheck is an excellent protocol to learn, and understand.
The sumcheck protocol addresses the following question: can a Prover convince a \log-time Verifier that
~~~~~~~~~~~~\displaystyle\sum_{h_1,\dots,h_{v} \in H} f(h_1,\dots,h_v)
\stackrel{?}{=} c
for a known v-variate polynomial f, set H and constant c.
We note that the Verifier cannot simply compute the sum as the sum consists of H^v terms. Instead, the Prover and Verifier will interact in v rounds.
Briefly, each of these rounds can be summarized with the following steps:
- The Prover sends the Verifier an univariate polynomial g that is a partial sum over a subset of variables over H and evaluation of other variables at random values.
- The Verifier sums g over the set H to verify that g matches with the previous step.
See the Sumcheck slides from the ZK Meeting call for more details and an example.
In practice, the set H = \{0,1\}. This is often used as statements concerning arrays can be extended to multilinear extensions that have inputs that are binary strings.
The sumcheck protocol has the following properties:
- Completeness (the probability that an honest Prover convinces a verifier): 1.
- Soundness (the probability that a malicious Prover can convince a verifier): vd/|\mathbb{F}|*
- Communication complexity: O(v(d+1)) where d is the maximum variable degree of f.
- Verifier complexity: O(v(d+1)|H|)*.
\vskip .15in
*: dependent on the polynomial commitment used.
The sumcheck protocol assumes the use of a random oracle for a single evaluation of the polynomial f at a random point. Concretely, this can be done with polynomial commitments.
Visit the IFT ZK Meeting notes for additional resources on the Sumcheck protocol.