Technical Notes · Zero Knowledge

AIR Constraints

From execution trace to polynomial constraints — how AIR turns "correct computation" into an algebraic property, and why that gives it a different shape than R1CS.

Srishti Rathi · Technical Notes · March 2026

Start with the trace

Run a program and record its state at every step — register values, memory, the program counter, whatever the machine tracks — and the result is a table: one row per step of execution, one column per piece of state. This is the execution trace, and it's the raw material every STARK-style proving system starts from.

step	pc	a	b	acc
0	0	1	1	0
1	1	1	2	1
2	2	2	3	3
3	3	3	5	6

On its own, this table proves nothing — anyone can write down a grid of numbers. What turns it into a proof of correct execution is a set of rules that say which tables are actually valid. That rule set is what an AIR provides.

What AIR actually says

AIR stands for Algebraic Intermediate Representation: a way of expressing "this trace is a valid execution" as a set of polynomial equations that must hold between rows.

Where ordinary code would write "row 2 equals row 1 plus row 0" as an instruction, an AIR states it as a constraint that must evaluate to zero at every row where it applies. For a Fibonacci-style accumulator, the transition constraint reads: the accumulator's value at the next step, minus the sum of the current two values, equals zero.

execution trace (table of values) → transition constraints (row → row) → boundary constraints (fixed rows) → one algebraic object

Two kinds of constraints tend to show up together. Transition constraints govern the relationship between one row and the next, encoding the machine's step function. Boundary constraints pin down specific rows — requiring the first row to match a known public input, say, or the last row to equal a claimed output.

From table to polynomial

The reason this table can become a succinct proof is interpolation. Each column of the trace is treated as the evaluations of some polynomial over a set of points — typically the powers of a root of unity, since that's what makes FFT-based interpolation fast. Once every column is a polynomial, "the constraint holds at every row" becomes "this constraint polynomial is zero across the entire evaluation domain" — a claim a verifier can check probabilistically, without replaying every row.

column of values → interpolate over a domain → trace polynomial → constraint polynomial → low-degree test (FRI)

A constraint polynomial meant to vanish on the trace domain will be divisible by that domain's vanishing polynomial. Dividing it out gives a quotient polynomial, and confirming that quotient has the expected low degree is exactly the job FRI is built to do.

AIR versus R1CS

R1CS — Rank-1 Constraint System — is the other common way to express "this computation was done correctly," and it's worth contrasting the two directly, since constraint systems tend to get lumped together as interchangeable.

Property	AIR	R1CS
Shape	A table (trace) plus row-to-row rules	A flat list of individual constraint equations
Repetition	One rule applies uniformly across every row	Each loop iteration is usually its own constraint
Natural fit	Repeated, uniform computation — VM execution, hashing	Arbitrary, one-off arithmetic circuits
Typical partner	STARKs, via FRI and Merkle commitments	SNARKs, via pairing-based or other polynomial commitments
Compiling a loop	One transition constraint, many rows	The loop is usually unrolled into repeated constraints

Neither shape is strictly more powerful than the other — they're different ways of expressing the same underlying idea, chosen because each pairs naturally with a different commitment scheme. AIR's row-uniformity is what makes it a good match for machines that execute the same step function over and over, like a zkVM.

Why the "algebraic" part matters

Calling it an algebraic intermediate representation isn't decoration. The whole point is that "every row satisfies this rule" can be restated as a single polynomial identity over an entire domain — and polynomial identities are exactly the kind of statement that commitments, random sampling, and low-degree testing know how to check efficiently, without the verifier ever touching the full trace.

Takeaway

An execution trace is just a table until an AIR gives it rules. Transition constraints between rows and boundary constraints on specific rows turn "did this program run correctly" into a claim about polynomials.

That reframing is what lets a STARK prover commit to the trace, fold it down with FRI, and let a verifier check a handful of points instead of replaying the whole computation.