Skip to main content

​
Overview

Spartan is a sumcheck-based Interactive Oracle Proof (IOP) that proves R1CS constraint satisfaction without trusted setup. Jolt uses a customized version of Spartan with univariate-skip optimization and product virtualization to efficiently prove the zkVM’s uniform constraints.

​
Role in the Proving System

Spartan is the first major proving stage after witness generation:
  1. Stage 1: Outer sumcheck with univariate-skip first round
  2. Stage 2: Product virtual sumcheck for deferred products
  3. Stages 3-7: Instruction lookups, bytecode, RAM/register checking, claim reductions
  4. Stage 8: Batched opening proofs

​
Spartan Protocol Structure

​
Outer Sumcheck (Stage 1)

The outer sumcheck reduces R1CS satisfaction to polynomial evaluations: Claim: 
Σ_{x ∈ {0,1}^m} eq(τ, x) · [Az(x) · Bz(x)] = 0
where:
  • τ: Random challenge from Fiat-Shamir
  • eq(τ, x): Equality polynomial (1 when τ=x, 0 otherwise)
  • Az(x), Bz(x): R1CS constraint polynomials at step x
  • m: log₂(trace_length)
Univariate-Skip First Round: Instead of binding the first variable directly, Spartan uses a univariate-skip protocol:
  1. Prover evaluates the first-round polynomial on an extended domain:
    • Standard domain: constraint evaluations at 0 and 1
    • Extended domain: evaluations at points {-D, …, D} for degree D
    • Interpolates to obtain univariate polynomial s₁(Y)
    • Multiplies by Lagrange basis L(τ_high, Y) evaluated at challenge τ_high
  2. Verifier samples challenge r₀ from the univariate polynomial
  3. Benefit: Amortizes first-round cost across multiple constraints in parallel

​
Product Virtual Sumcheck (Stage 2)

Some R1CS constraints reference virtual products computed via a second sumcheck: Purpose: Prove that deferred products (e.g., complex instruction outputs) match their claimed values without materializing dense polynomials. Protocol:
  1. Outer sumcheck opens virtual products at challenge point r
  2. Product sumcheck reduces each product to its factors via another sumcheck
  3. Factor evaluations are verified in later stages

​
Spartan Submodules

​
outer.rs - Outer Sumcheck

OuterUniSkipProver:
  • Computes first-round univariate polynomial via extended evaluation
  • Performs streaming sumcheck for subsequent rounds
  • Binds R1CS constraint polynomials by challenge bits
OuterRemainingSumcheckProver:
  • Handles rounds after univariate-skip first round
  • Uses streaming window optimization for memory efficiency
  • Degree bound: 3 (cubic round polynomials)

​
product.rs - Product Virtualization

ProductVirtualUniSkipProver:
  • Proves deferred products via second sumcheck
  • Uses univariate-skip for first round (like outer sumcheck)
  • Opens factor polynomials at challenge point

​
shift.rs - Shift Polynomials

Purpose: Handle instructions that reference “next step” state (e.g., branch targets). Mechanism:
  • Shift polynomials represent witness[i+1] in constraints
  • Proved via explicit polynomial openings
  • Used sparingly (most constraints use within-step state)

​
instruction_input.rs - Instruction Constraints

Purpose: Enforce correct instruction operand extraction from bytecode. Constraints:
  • Immediate value extraction (from encoded instruction)
  • Register index decoding
  • Opcode consistency checks

​
Sumcheck Instance Parameters

Each sumcheck instance implements SumcheckInstanceParams: 
trait SumcheckInstanceParams {
    fn input_claim(accumulator) -> F::Challenge;
    fn input_claim_constraint() -> InputClaimConstraint;
    fn output_claim_constraint() -> OutputClaimConstraint;
    // ...
}
These define:
  • Input claim: How the sumcheck claim is computed from prior openings
  • Output claim: What polynomial evaluations the sumcheck produces
  • Constraints: BlindFold R1CS encoding (for ZK mode)

​
Streaming Sumcheck Optimization

Jolt uses streaming sumcheck to reduce memory usage: Standard Sumcheck:
  • Materializes all polynomial coefficients in memory
  • Memory: O(2^m · poly_count · field_size)
Streaming Sumcheck:
  • Processes polynomials in chunks (“windows”)
  • Recomputes coefficients on-the-fly for each round
  • Memory: O(window_size · poly_count · field_size)
  • Tradeoff: ~2x more computation for 10-100x less memory
Stages using streaming:
  • Outer sumcheck (Stage 1): Streams over R1CS constraint polynomials
  • Register checking (Stage 3): Streams over register state
  • RAM checking (Stage 4): Streams over memory accesses

​
ZK Mode: BlindFold Integration

In ZK mode (with --features zk), Spartan integrates with BlindFold: Standard mode:
  • Round polynomials sent in the clear
  • Verifier checks claims directly
ZK mode:
  • Round polynomials Pedersen-committed (hidden)
  • BlindFold R1CS proves verifier checks without revealing polynomials
  • No trusted setup required (unlike Groth16)
See BlindFold section in CLAUDE.md for details.

​
Opening Claims

Spartan produces opening claims for polynomial evaluations: 
pub struct OpeningId {
    polynomial: CommittedPolynomial,
    sumcheck_stage: SumcheckId,
}
Each opening claim specifies:
  • Which polynomial (e.g., RamInc, InstructionRa[0])
  • Evaluation point (derived from sumcheck challenges)
  • Expected evaluation result
Opening proofs are batched in Stage 8 for efficiency.

​
Performance Characteristics

​
Prover Time

Outer Sumcheck (Stage 1):
  • Dominates overall proving time (~40-50% of total)
  • Cost: O(trace_length · num_constraints · m) field operations
  • Univariate-skip reduces first-round cost by ~30%
Product Sumcheck (Stage 2):
  • Much cheaper (~5-10% of Stage 1)
  • Only processes virtual products (small subset of witness)

​
Verifier Time

  • O(num_constraints · m) field operations
  • Logarithmic in trace length (verifies sumcheck round polynomials)
  • Spartan verification ~1-10ms for typical zkVM traces

​
Memory Usage

  • Streaming sumcheck: ~100MB for 10⁶ cycles with 64GB trace materialized
  • Without streaming: ~10GB for same trace
  • Tradeoff configurable via ReadWriteConfig

​
Key Types

UniformSpartanKey: 
pub struct UniformSpartanKey<F: JoltField> {
    pub num_rows_total: usize,  // Padded trace length
    pub num_cols: usize,        // R1CS input count
    // Constraint metadata
}
OuterUniSkipParams: 
pub struct OuterUniSkipParams<F: JoltField> {
    pub tau: Vec<F::Challenge>,  // Fiat-Shamir challenge
}
ProductVirtualUniSkipParams: 
pub struct ProductVirtualUniSkipParams<F: JoltField> {
    pub product_openings: Vec<F>,  // Virtual product values
}

​
Key Files

  • jolt-core/src/zkvm/spartan/outer.rs: Outer sumcheck prover/verifier
  • jolt-core/src/zkvm/spartan/product.rs: Product virtualization
  • jolt-core/src/zkvm/spartan/shift.rs: Shift polynomial handling
  • jolt-core/src/zkvm/spartan/instruction_input.rs: Instruction constraint checking
  • jolt-core/src/zkvm/r1cs/key.rs: UniformSpartanKey definition

​
Next Steps

Build docs developers (and LLMs) love

Get started for freeTalk to us