Skip to main content
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: 
// 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: 
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 
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
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

AspectWithout BatchingWith Batching
Fiat-Shamir hashingN × (M rounds)1 × (M rounds)
Polynomial checksN claims1 combined claim
Transcript sizeN × proof_size1 × 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

// 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();

​
References

Build docs developers (and LLMs) love

Get started for freeTalk to us