> ## Documentation Index
> Fetch the complete documentation index at: https://mintlify.com/a16z/jolt/llms.txt
> Use this file to discover all available pages before exploring further.

# Sumcheck Protocol

> The interactive sumcheck protocol for efficiently verifying polynomial sums

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 $v$-variate polynomial $g$ defined over a finite field $\mathbb{F}$. The purpose of the sumcheck protocol is to compute the sum:

$$
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(r_1, \ldots, r_v)$ for a randomly chosen vector $(r_1, \ldots, r_v) \in \mathbb{F}^v$.

From the verifier's perspective, the sumcheck protocol **reduces** the task of summing $g$'s evaluations over $2^v$ inputs (all inputs in $\{0, 1\}^{v}$) to the task of evaluating $g$ at a **single** input $(r_1, \ldots, r_v) \in \mathbb{F}^v$.

## Protocol Description

The protocol proceeds in $v$ rounds as follows:

### Round 1

The prover sends a polynomial $g_1(X_1)$ and claims that:

$$
g_1(X_1) = \sum_{x_2, \ldots, x_v \in \{0,1\}^{v-1}} g(X_1, x_2, \ldots, x_v)
$$

If $g_1$ is as claimed, then $H = g_1(0) + g_1(1)$. The polynomial $g_1(X_1)$ has degree $\text{deg}_1(g)$, the degree of variable $x_1$ in $g$.

The prover specifies $g_1$ by sending the evaluation of $g_1$ at each point in the set $\{0, 1, \ldots, \text{deg}_1(g)\}$. (Actually, the prover does not need to send $g_1(1)$, since the verifier can infer that $g_1(1) = H - g_1(0)$.)

### Round $j > 1$

The verifier chooses a value $r_{j-1}$ uniformly at random from $\mathbb{F}$ and sends $r_{j-1}$ to the prover. We say that **variable $j - 1$ gets bound to value $r_{j-1}$**.

In return, the prover sends a polynomial $g_j(X_j)$ and claims that:

$$
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 $g_{j-1}(r_{j-1}) = g_j(0) + g_j(1)$, rejecting if not
2. **Degree check**: Verify that the degree of $g_j$ is at most $\text{deg}_j(g)$, the degree of variable $x_j$ in $g$

### Final Round

In the final round, the prover has sent $g_v(X_v)$ which is claimed to be $g(r_1, \ldots, r_{v-1}, X_v)$.

The verifier performs a final check:

$$
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 = g_1(0) + g_1(1)$.

## Complexity

**Prover complexity:** $O(2^v)$ - The prover must compute the sum for each round polynomial.

**Verifier complexity:** $O(v)$ communication and checks, plus one evaluation of $g$ at a random point.

**Soundness:** If the prover cheats (i.e., $H \neq$ the actual sum), the verifier will catch the deception except with negligible probability (roughly $v \cdot d / |\mathbb{F}|$ where $d$ 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:

* **Chapter 4** of [Proofs, Arguments, and Zero Knowledge](https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf) by Justin Thaler
* Original exposition in [Thaler13](https://eprint.iacr.org/2013/351.pdf)