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

# Spartan IOP

> Learn how Jolt uses Spartan to prove R1CS constraint satisfaction

## 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`:

```rust theme={null}
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](/architecture/blindfold) for details.

## Opening Claims

Spartan produces **opening claims** for polynomial evaluations:

```rust theme={null}
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**:

```rust theme={null}
pub struct UniformSpartanKey<F: JoltField> {
    pub num_rows_total: usize,  // Padded trace length
    pub num_cols: usize,        // R1CS input count
    // Constraint metadata
}
```

**OuterUniSkipParams**:

```rust theme={null}
pub struct OuterUniSkipParams<F: JoltField> {
    pub tau: Vec<F::Challenge>,  // Fiat-Shamir challenge
}
```

**ProductVirtualUniSkipParams**:

```rust theme={null}
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

* [R1CS Constraints](/architecture/r1cs-constraints): Understanding the constraint system
* [RAM Checking](/architecture/ram): Memory consistency verification
* [Opening Proofs](/architecture/opening-proof): Batched polynomial commitments