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

# R1CS Constraint System

> Understand Jolt's uniform R1CS constraints and equality-conditional structure

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

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

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

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

```rust theme={null}
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](/architecture/spartan):

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

* [Spartan IOP](/architecture/spartan): How R1CS constraints are proved
* [Witness Generation](/architecture/overview): Creating witness polynomials from traces
* [Instruction Execution](/architecture/instruction-execution): Lookup-based instruction verification