Skip to main content

​
Overview

Jolt’s R1CS (Rank-1 Constraint System) encodes the zkVM’s correctness conditions as a set of uniform equality-conditional constraints. Unlike traditional zkVMs that use constraint-per-step layouts, Jolt’s uniform structure applies the same constraints to every execution step, dramatically simplifying the constraint system.

​
Role in the Proving System

The R1CS constraint system is proved via Spartan, a sumcheck-based SNARK:
  1. Input: Execution trace converted to witness polynomials (instruction flags, register values, etc.)
  2. Constraints: Uniform R1CS rows encoding instruction semantics and state transitions
  3. Proving: Spartan IOP reduces R1CS satisfaction to polynomial evaluations via sumcheck
  4. Output: Opening claims verified via batched polynomial commitments

​
Uniform Equality-Conditional Constraints

​
Structure

Each constraint has the form: 
Az(x) · Bz(x) = 0
where:
  • Az, Bz are multilinear polynomials over witness/public inputs
  • x indexes into execution steps
  • No Cz term needed (all constraints are equality checks)

​
Uniformity

The same set of constraints applies to every step:
  • Dramatically smaller constraint system than per-step approaches
  • Enables efficient batching via sumcheck protocol
  • Leverages instruction flags for conditional activation

​
Constraint Organization

​
Linear Combinations

Constraints are built from linear combinations (LC) of terms: 
pub struct R1CSConstraint {
    pub a: LC,  // Left polynomial
    pub b: LC,  // Right polynomial
}
Each term references witness polynomials and public inputs via index:
  • Instruction flags (circuit flags for each instruction type)
  • Register values (rs1, rs2, rd)
  • Memory addresses and values
  • Lookup outputs (via virtual polynomials)

​
Univariate-Skip Split

Constraints are divided into two groups for the univariate-skip optimization: First Group (R1CS_CONSTRAINTS_FIRST_GROUP):
  • Constraints with boolean guards and small (~64-bit) magnitudes
  • Optimized for efficient univariate-skip first round
  • Size: OUTER_UNIVARIATE_SKIP_DOMAIN_SIZE (typically 64)
Second Group (R1CS_CONSTRAINTS_SECOND_GROUP):
  • Constraints with wider arithmetic (e.g., multiplication bounds)
  • Processed in subsequent sumcheck rounds
  • Complement of first group

​
Example Constraints

​
Instruction Consistency

flag_add · (rs1 + rs2 - rd) = 0
Activated only when flag_add is true (encoding the ADD instruction).

​
Memory Access

flag_load · (ram_address - (rs1 + imm)) = 0
Enforces correct address computation for load instructions.

​
Lookup Correctness

flag_xor · (lookup_output - (rs1 ⊕ rs2)) = 0
Verifies lookup table output matches XOR operation.

​
R1CS Inputs

​
Virtual Polynomials

Jolt uses virtual polynomials (not explicitly committed) derived from committed witness:
  • InstructionFlags: One-hot encoding of instruction type
  • RegisterValues: Contents of registers rs1, rs2, rd
  • RamAddress, RamValue: Memory access address and value
  • PC: Program counter

​
Public Inputs

Public inputs embedded in constraints:
  • Instruction immediates (from bytecode)
  • Memory layout parameters
  • Program I/O bounds

​
Constraint Generation

​
Compile-Time Definition

Constraints are statically defined at compile time: 
const R1CS_CONSTRAINTS: &[NamedR1CSConstraint] = &[
    /* ... constraint definitions ... */
];

​
Runtime Evaluation

During proving, constraints are evaluated over the execution trace:
  1. Bind to step: Evaluate Az(x), Bz(x) at specific execution step x
  2. Check satisfaction: Verify Az(x) · Bz(x) = 0
  3. Sumcheck reduction: Aggregate all steps via sumcheck protocol

​
Key Type: UniformSpartanKey

pub struct UniformSpartanKey<F: JoltField> {
    pub num_rows_total: usize,        // Padded trace length
    pub num_cols: usize,              // Number of R1CS inputs
    // ... constraint metadata ...
}
The UniformSpartanKey stores:
  • Constraint structure (Az, Bz polynomials)
  • Padding parameters
  • Univariate-skip split metadata

​
Product Virtualization

Some R1CS constraints reference virtual products from outer sumcheck: 
pub struct ProductConstraint {
    pub az: ProductFactorExpr,
    pub bz: ProductFactorExpr,
    pub z_prime: VirtualPolynomial,  // Opening from outer sumcheck
}
This enables deferred evaluation of complex products via sumcheck.

​
Integration with Spartan

The R1CS constraints are proved via the Spartan IOP:
  1. Outer sumcheck: Reduces R1CS satisfaction to Az, Bz evaluations
  2. Product virtual sumcheck: Handles deferred products
  3. Opening proofs: Verifies polynomial evaluations via commitment scheme

​
Performance Characteristics

  • Constraint count: ~50-100 uniform constraints (independent of trace length)
  • Prover time: Dominated by sumcheck polynomial bindings
  • Verifier time: O(num_constraints · log(trace_length))
  • Proof size: Logarithmic in trace length (via Spartan)

​
Key Files

  • jolt-core/src/zkvm/r1cs/constraints.rs: Constraint definitions
  • jolt-core/src/zkvm/r1cs/evaluation.rs: Runtime constraint evaluation
  • jolt-core/src/zkvm/r1cs/key.rs: UniformSpartanKey structure
  • jolt-core/src/zkvm/r1cs/inputs.rs: R1CS input polynomial mapping

​
Next Steps

Build docs developers (and LLMs) love

Get started for freeTalk to us