AIR or R1CS?

Start with the problem

A zero-knowledge proof system needs a mathematical description of a computation.

Suppose a program computes:

We cannot directly hand the prover the sentence:

We first translate the computation into mathematical relationships.

Two important ways of organizing those constraints are R1CS and AIR.

The shortest possible distinction

Both are algebraic descriptions of computation. The major difference is how the computation is organized.

First principle: both live over a field

R1CS and AIR are normally defined over a finite field.

For a prime field:

Every variable, trace value, coefficient, and constraint evaluation belongs to this field.

For example, over F₇:

because the results are reduced modulo 7.

R1CS from first principles

R1CS means Rank-1 Constraint System.

At its core, R1CS works with a single assignment vector called the witness vector.

The variables in W may contain:

• public inputs;
• private witness values;
• intermediate values produced by the computation;
• a constant 1 slot for representing constants.

Each R1CS constraint has the form:

where A, B, and C are vectors for one constraint, or rows of matrices when many constraints are collected together.

What does A · W actually mean?

Suppose:

and:

Then:

So an R1CS vector is simply a way to describe a linear combination of witness variables.

The multiplication of two such linear combinations gives the quadratic structure:

R1CS example: multiplication

Suppose we want to enforce:

Use:

Choose:

Then:

Therefore:

R1CS example: addition

Suppose:

We can represent the left side as:

Using:

we can choose:

Then:

so the constraint is satisfied exactly when the intended addition is satisfied.

Many R1CS constraints become matrices

A real computation has many constraints.

Instead of storing one A, B, and C vector, we stack them into matrices:

For every constraint row i:

The entire witness is valid only if every row satisfies its equation.

Arithmetic circuit → R1CS

Consider:

Introduce intermediate variables:

Now we have three simple constraints:

This is the basic workflow used by many circuit-based systems:

AIR from first principles

AIR means Algebraic Intermediate Representation.

The key idea is different from R1CS.

Instead of putting the whole computation into one long witness vector, we organize the execution into a trace.

Imagine a machine running for several steps:

At every step, we record relevant machine state.

The execution trace

Suppose a machine has a single register r.

It starts at 2 and increments by 1:

The trace can be represented as:

In a real zkVM, the trace can contain many columns:

Transition constraints

The trace alone is just data. AIR defines what makes that trace valid.

For our incrementing register:

Move everything to one side:

This is a transition constraint.

It says that every pair of neighboring rows must follow the transition rule.

Boundary constraints

The transition rule alone does not specify where the computation starts.

For example, the transition:

allows:

as well as:

If the intended computation must start at 2, we need:

That is a boundary constraint.

We might also require a final value:

Complete AIR example

For the trace:

we can define:

Now the constraints describe the intended computation much more precisely.

Why AIR uses columns

A zkVM executes many different pieces of state at every step.

Imagine:

Each column represents some piece of state. AIR constraints describe relationships between columns and between neighboring rows.

This makes AIR particularly natural for long computations.

Locality: the key AIR idea

Many AIR constraints are local.

A constraint may inspect:

For example:

or:

This local structure is extremely useful for proving long execution traces.

AIR becomes polynomial algebra

Now comes the important bridge to STARKs.

Suppose a trace column contains:

We interpret those values as evaluations of a polynomial on a domain.

If the domain contains:

then we can think of:

The transition relation:

can then be expressed algebraically as:

evaluated on the relevant domain.

Vanishing constraints

Suppose a polynomial constraint should be zero on a domain.

We can represent the domain using a vanishing polynomial.

For a domain D:

By construction:

This lets STARK systems express the idea that a constraint polynomial vanishes over the required domain.

Constraint degree

Constraint degree matters in both representations, but it appears differently.

For R1CS:

the constraint is at most quadratic in the witness variables.

In AIR, a transition constraint can contain products of trace values and therefore can also have a degree greater than one.

The proving system tracks these degrees because polynomial degree affects the algebraic checks used later.

R1CS vs AIR: the conceptual difference

The same computation in R1CS and AIR

Consider the simple recurrence:

R1CS view

We could create a variable for every trace value:

Then create constraints:

Each step becomes an explicit constraint over witness variables.

AIR view

Instead, describe the same repeated rule once:

and state the boundary:

The trace supplies all rows to which the transition rule applies.

Why AIR is natural for zkVMs

A CPU executes one step after another:

A zkVM can record these states as rows of a trace.

For example:

Then AIR describes valid state transitions.

For an instruction that performs:

the corresponding transition constraint can conceptually be:

Of course, a real zkVM needs many more constraints for opcode selection, register addressing, program counter updates, memory consistency, range checks, and other machine semantics.

A small zkVM-style AIR example

Imagine a toy machine with:

and an ADD instruction:

The PC advances by four bytes:

The corresponding transition constraints are:

The trace might therefore look conceptually like:

The transition constraint checks that row 1 correctly follows row 0.

Public inputs and boundaries

Public values often enter the algebraic representation through boundary or dedicated input constraints.

Suppose a computation must start with public input:

A boundary constraint can enforce:

The important idea is that the public statement must be algebraically connected to the computation being proved.

From AIR constraints to a composition polynomial

A real AIR contains many constraints.

Conceptually, suppose we have:

A prover can combine them using random coefficients:

The random coefficients are typically obtained from the proof transcript through Fiat–Shamir.

This connects AIR to the STARK pipeline:

Rust: a tiny R1CS model

// Educational R1CS-style check.
// W = [1, x, y, z]
// Constraint: x * y = z

fn dot(a: &[i64], w: &[i64]) -> i64 {
    a.iter()
        .zip(w.iter())
        .map(|(x, y)| x * y)
        .sum()
}

fn check_r1cs(
    a: &[i64],
    b: &[i64],
    c: &[i64],
    w: &[i64],
) -> bool {
    dot(a, w) * dot(b, w) == dot(c, w)
}

fn main() {
    let x = 3;
    let y = 5;
    let z = 15;

    let w = [1, x, y, z];

    // A * W = x
    let a = [0, 1, 0, 0];

    // B * W = y
    let b = [0, 0, 1, 0];

    // C * W = z
    let c = [0, 0, 0, 1];

    assert!(check_r1cs(&a, &b, &c, &w));

    println!("R1CS constraint satisfied.");
}

This toy implementation uses i64 only to make the algebra visible. A real proving system performs the operations in a finite field.

Rust: a tiny AIR-style checker

// Educational AIR-style checker.
// Transition: r_next = r_current + 1

fn check_trace(trace: &[i64], initial: i64) -> bool {
    if trace.is_empty() {
        return false;
    }

    // Boundary constraint.
    if trace[0] != initial {
        return false;
    }

    // Transition constraints.
    for i in 0..trace.len() - 1 {
        let current = trace[i];
        let next = trace[i + 1];

        if next - current - 1 != 0 {
            return false;
        }
    }

    true
}

fn main() {
    let trace = [2, 3, 4, 5, 6];

    assert!(check_trace(&trace, 2));

    println!("AIR constraints satisfied.");
}

The important distinction is visible in the code:

What changes in a real proving system?

The toy Rust programs above only check constraints. They do not produce a ZK proof.

A real system adds layers such as:

• finite-field arithmetic;
• constraint generation;
• witness or trace generation;
• polynomial interpolation;
• low-degree extension;
• commitments;
• Fiat–Shamir challenges;
• polynomial identity testing;
• FRI or another polynomial proof system;
• verification.

Therefore R1CS and AIR should be understood as intermediate representations, not complete proof systems by themselves.

Why zkVM architecture often prefers a trace representation

Consider a program with one million execution steps.

A circuit representation can conceptually turn those steps into a very large collection of constraints and intermediate variables.

A trace-oriented representation instead naturally says:

This matches the temporal structure of machine execution.

That does not make AIR universally superior. It means that the representation aligns naturally with the problem being represented.

Trade-offs

Common mistakes when learning AIR and R1CS

Where AIR and R1CS fit in the ZK pipeline

For the STARK-style path you are building in your zkVM, the conceptual chain is:

For a circuit-based R1CS system, the conceptual path is more like:

So which one should you use?

The choice is ultimately an engineering choice about which algebraic representation makes the target computation easiest and most efficient to prove.

The whole idea in one map

If you remember only one distinction, remember this: R1CS thinks in terms of variables and algebraic equations; AIR thinks in terms of machine states and algebraic transition rules. Both ultimately turn computation into algebra so that a proving system can establish correctness without requiring the verifier to execute the entire computation.