Skip to main content
The sumcheck protocol is a fundamental building block in modern proof systems. It allows a prover to convince a verifier that a sum over a polynomial’s evaluations equals a claimed value, with the verifier performing vastly less work than computing the sum directly.

​
Overview

Suppose we are given a vv-variate polynomial gg defined over a finite field F\mathbb{F}. The purpose of the sumcheck protocol is to compute the sum: H:=∑b1∈{0,1}∑b2∈{0,1}⋯∑bv∈{0,1}g(b1,…,bv)H := \sum_{b_1 \in \{0,1\}} \sum_{b_2 \in \{0,1\}} \cdots \sum_{b_v \in \{0,1\}} g(b_1, \ldots, b_v) In order to execute the protocol, the verifier needs to be able to evaluate g(r1,…,rv)g(r_1, \ldots, r_v) for a randomly chosen vector (r1,…,rv)∈Fv(r_1, \ldots, r_v) \in \mathbb{F}^v. From the verifier’s perspective, the sumcheck protocol reduces the task of summing gg‘s evaluations over 2v2^v inputs (all inputs in {0,1}v\{0, 1\}^{v}) to the task of evaluating gg at a single input (r1,…,rv)∈Fv(r_1, \ldots, r_v) \in \mathbb{F}^v.

​
Protocol Description

The protocol proceeds in vv rounds as follows:

​
Round 1

The prover sends a polynomial g1(X1)g_1(X_1) and claims that: g1(X1)=∑x2,…,xv∈{0,1}v−1g(X1,x2,…,xv)g_1(X_1) = \sum_{x_2, \ldots, x_v \in \{0,1\}^{v-1}} g(X_1, x_2, \ldots, x_v) If g1g_1 is as claimed, then H=g1(0)+g1(1)H = g_1(0) + g_1(1). The polynomial g1(X1)g_1(X_1) has degree deg1(g)\text{deg}_1(g), the degree of variable x1x_1 in gg. The prover specifies g1g_1 by sending the evaluation of g1g_1 at each point in the set {0,1,…,deg1(g)}\{0, 1, \ldots, \text{deg}_1(g)\}. (Actually, the prover does not need to send g1(1)g_1(1), since the verifier can infer that g1(1)=H−g1(0)g_1(1) = H - g_1(0).)

​
Round j>1j > 1

The verifier chooses a value rj−1r_{j-1} uniformly at random from F\mathbb{F} and sends rj−1r_{j-1} to the prover. We say that variable j−1j - 1 gets bound to value rj−1r_{j-1}. In return, the prover sends a polynomial gj(Xj)g_j(X_j) and claims that: gj(Xj)=∑(xj+1,…,xv)∈{0,1}v−jg(r1,…,rj−1,Xj,xj+1,…,xv)g_j(X_j) = \sum_{(x_{j+1}, \ldots, x_v) \in \{0,1\}^{v-j}} g(r_1, \ldots, r_{j-1}, X_j, x_{j+1}, \ldots, x_v) The verifier performs two checks:
  1. Consistency check: Verify that gj−1(rj−1)=gj(0)+gj(1)g_{j-1}(r_{j-1}) = g_j(0) + g_j(1), rejecting if not
  2. Degree check: Verify that the degree of gjg_j is at most degj(g)\text{deg}_j(g), the degree of variable xjx_j in gg

​
Final Round

In the final round, the prover has sent gv(Xv)g_v(X_v) which is claimed to be g(r1,…,rv−1,Xv)g(r_1, \ldots, r_{v-1}, X_v). The verifier performs a final check: gv(rv)=g(r1,…,rv)g_v(r_v) = g(r_1, \ldots, r_v) If this test succeeds, along with all previous tests, the verifier accepts and is convinced that H=g1(0)+g1(1)H = g_1(0) + g_1(1).

​
Complexity

Prover complexity: O(2v)O(2^v) - The prover must compute the sum for each round polynomial. Verifier complexity: O(v)O(v) communication and checks, plus one evaluation of gg at a random point. Soundness: If the prover cheats (i.e., H≠H \neq the actual sum), the verifier will catch the deception except with negligible probability (roughly v⋅d/∣F∣v \cdot d / |\mathbb{F}| where dd is the maximum degree).

​
Role in Jolt

Sumcheck is used extensively throughout Jolt’s proving pipeline:
  • Spartan R1CS verification: Proves constraint satisfaction via outer and product sumchecks
  • Instruction lookups: Verifies instruction execution correctness
  • Memory checking: Proves correct read/write behavior for RAM and registers
  • Claim reductions: Reduces polynomial opening claims across multiple stages
Jolt’s implementation includes several optimizations:
  • Batched sumcheck: Proves multiple sumcheck instances simultaneously
  • Streaming sumcheck: Processes large polynomials in chunks to reduce memory usage
  • Univariate skip: Optimizes rounds where polynomials have low degree
  • Zero-knowledge sumcheck: Uses Pedersen commitments to hide round polynomials (see BlindFold)

​
Implementation Details

The core sumcheck implementations live in jolt-core/src/subprotocols/:
  • sumcheck.rs: Core batched sumcheck prover and verifier
  • univariate_skip.rs: Optimized handling of univariate rounds
  • blindfold/: Zero-knowledge sumcheck via Pedersen commitments
Sumcheck instances implement the SumcheckInstanceParams trait, which defines:
  • input_claim(): How to compute the input claim from polynomial openings
  • output_claim_constraint(): Constraints for verifying output claims
  • Binding order and polynomial access patterns

​
Further Reading

For a detailed introduction to the sumcheck protocol, see:

Build docs developers (and LLMs) love

Get started for freeTalk to us