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:

// 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

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

// 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: Batch polynomial opening proofs
• EQ Optimizations: Fast EQ polynomial evaluation in sumcheck
• CompactPolynomial: Memory-efficient polynomial storage

References

• Perspectives on Sumcheck Batching by Jim Posen
• Jolt implements “front-loaded” batch sumcheck (batching coefficients sampled at the start)