> ## 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.

# Batched Sumcheck Protocol

> Reducing verifier cost and proof size through sumcheck batching

Jolt uses **batched sumcheck** to combine multiple parallel sumcheck instances into a single protocol execution. This optimization dramatically reduces both verifier computation and proof size.

## Overview

Instead of running N separate sumcheck protocols, batched sumcheck:

1. Takes N parallel sumcheck claims
2. Combines them using random linear combination
3. Runs a single sumcheck over the batched polynomial
4. Verifier checks one combined claim instead of N individual claims

## Protocol Details

### Batching Technique

Given N sumcheck instances with claims `claim_1, ..., claim_N`, the batched protocol:

1. **Prover sends all claims** to the transcript (standard mode only)
2. **Verifier samples batching coefficients** `β₁, ..., βₙ` from the transcript
3. **Combined claim** is computed as:
   ```
   batched_claim = Σᵢ βᵢ · claim_i
   ```
4. **Batched polynomial** for each round is:
   ```
   H(x) = Σᵢ βᵢ · Hᵢ(x)
   ```

### Handling Different Lengths

Sumcheck instances may have different numbers of variables. For instance:

* Instance A: `claim_a = Σ_{x ∈ {0,1}^M} P(x)`
* Instance B: `claim_b = Σ_{x,y ∈ {0,1}^M × {0,1}^N} Q(x,y)`

To batch these correctly:

```rust theme={null}
// Scale shorter claims by 2^(max_rounds - num_rounds)
let scaled_claim_a = claim_a * 2^N;
let batched_claim = β_a * scaled_claim_a + β_b * claim_b;
```

**Why?** The batched sum is:

```
Σ_{x,y} β_a · P(x) + β_b · Q(x,y) 
  = β_a · Σ_y Σ_x P(x) + β_b · Σ_{x,y} Q(x,y)
  = β_a · 2^N · claim_a + β_b · claim_b
```

### Dummy Rounds

When an instance has fewer variables than `max_num_rounds`, it contributes a **constant polynomial** during "dummy" rounds:

```rust theme={null}
if round < offset || round >= offset + num_rounds {
    // Dummy round: H(0) = H(1) = previous_claim / 2
    UniPoly::from_coeff(vec![previous_claim * two_inv])
} else {
    // Active round: compute real sumcheck message
    sumcheck.compute_message(round - offset, previous_claim)
}
```

This ensures the batched polynomial always has degree ≥ 1 for every round.

## Implementation

### Standard Mode (`BatchedSumcheck::prove`)

Location: `jolt-core/src/subprotocols/sumcheck.rs:33`

```rust theme={null}
pub fn prove<F: JoltField, ProofTranscript: Transcript>(
    mut sumcheck_instances: Vec<&mut dyn SumcheckInstanceProver<F, ProofTranscript>>,
    opening_accumulator: &mut ProverOpeningAccumulator<F>,
    transcript: &mut ProofTranscript,
) -> (ClearSumcheckProof<F, ProofTranscript>, Vec<F::Challenge>, F)
```

**Key steps:**

1. Append all input claims to transcript
2. Sample batching coefficients
3. For each round:
   * Compute individual univariate polynomials `H_i(x)`
   * Combine: `H(x) = Σᵢ βᵢ · Hᵢ(x)`
   * Compress and append to proof
   * Sample challenge `r_j`
   * Update individual claims: `claim_i ← Hᵢ(r_j)`
4. Cache polynomial openings for batch opening proof

### Zero-Knowledge Mode (`BatchedSumcheck::prove_zk`)

Location: `jolt-core/src/subprotocols/sumcheck.rs:197`

**Differences from standard mode:**

* **No cleartext claims appended** — polynomial commitments provide binding
* **Pedersen commitments** to round polynomials instead of raw coefficients
* Stores commitments, coefficients, and blinding factors in `BlindFoldAccumulator`

```rust theme={null}
let blinding = F::random(rng);
let commitment = pedersen_gens.commit(&batched_univariate_poly.coeffs, &blinding);
transcript.append_commitment(b"sumcheck_commitment", &commitment);
```

BlindFold later proves that these committed coefficients satisfy sumcheck equations.

## Performance Impact

### Verifier Savings

| Aspect                  | Without Batching | With Batching    |
| ----------------------- | ---------------- | ---------------- |
| **Fiat-Shamir hashing** | N × (M rounds)   | 1 × (M rounds)   |
| **Polynomial checks**   | N claims         | 1 combined claim |
| **Transcript size**     | N × proof\_size  | 1 × proof\_size  |

### Prover Overhead

Batching adds minimal prover cost:

* Linear combination of univariate polynomials (cheap)
* Single transcript update per round
* **Net effect**: Negligible overhead, massive verifier savings

### Concrete Example: Jolt Stage 2

Stage 2 batches:

* Bytecode read checking (1 instance)
* Instruction lookups read-RAF (N table instances)
* Total: \~10-20 instances → **1 batched proof**

Verifier time: **\~95% reduction**

## Security Considerations

### Soundness

Batching relies on the **Schwartz-Zippel lemma**: if the prover cheats on any individual sumcheck, the batched polynomial is incorrect with high probability (≥ `1 - d/|F|` where `d` is the degree).

**Critical:** Batching coefficients MUST be sampled **after** all claims are committed (via transcript in standard mode, or via polynomial commitments in ZK mode).

### Zero-Knowledge

In ZK mode:

* Pedersen commitments hide polynomial coefficients
* Blinding factors are uniformly random
* BlindFold proves committed values satisfy sumcheck without revealing them

## Usage Example

```rust theme={null}
// Stage 2: Instruction lookups + bytecode
let mut instances: Vec<&mut dyn SumcheckInstanceProver<F, ProofTranscript>> = vec![
    &mut bytecode_read_raf,
    // ... instruction lookup instances
];

let (proof, r_sumcheck, initial_claim) = BatchedSumcheck::prove(
    instances,
    opening_accumulator,
    transcript,
);

// Verifier reconstructs the same batched claim
let batched_claim = instances.iter()
    .zip(batching_coeffs.iter())
    .map(|(sumcheck, coeff)| sumcheck.verify_claim() * coeff)
    .sum();
```

## Related Optimizations

* [Batched Openings](/architecture/optimizations/batched-openings): Batch polynomial opening proofs
* [EQ Optimizations](/architecture/optimizations/eq-optimizations): Fast EQ polynomial evaluation in sumcheck
* [CompactPolynomial](/architecture/optimizations/small-value): Memory-efficient polynomial storage

## References

* [Perspectives on Sumcheck Batching](https://hackmd.io/s/HyxaupAAA) by Jim Posen
* Jolt implements "front-loaded" batch sumcheck (batching coefficients sampled at the start)