R1CS vs Plonkish vs AIR

You read the Groth16 paper and learn that a ZK circuit is a system of matrices called R1CS, then you open the halo2 docs and the same circuit is a table of cells with custom gates, and somewhere in the STARK literature the same thing shows up as an execution trace with transition constraints. Three names, three layouts, and no tutorial bothers to point out that all three are doing the same job.

That job is called arithmetization: you take a computation and rewrite it as polynomial equations, because ZK provers do not run code, they evaluate polynomials. R1CS, Plonkish, and AIR are three different answers to what those equations should look like, and this post writes Fibonacci in all three, side by side, in around 1200 lines of plain Rust with no proving libraries and no external dependencies. The repo is at github.com/adamsmo/r1cs-plonkish-air.

Fibonacci because it is boring, and a boring computation makes the differences between the arithmetizations obvious instead of hiding them behind complicated logic. The field everywhere is $p = 2^{31} – 1$, the Mersenne-31 prime used by Plonky3 and primary in Stwo, while SP1 ran on BabyBear up to V5 and switched to KoalaBear in V6.

R1CS

R1CS is the oldest of the three. Three matrices $A, B, C$, a witness vector $z$ with $z_0 = 1$, one equation:

$$(Az) \circ (Bz) = (Cz)$$

The $\circ$ is element-wise multiplication, also called Hadamard. Each row is two linear forms multiplied: $\langle a_i, z\rangle \cdot \langle b_i, z\rangle = \langle c_i, z\rangle$. “Rank-1” is a fancy way of saying every constraint is one multiplication.

Addition is free, you fold it into the coefficients of one of the linear forms, but every multiplication costs you a row, which is what makes Fibonacci the worst case for R1CS: the recurrence $f_{i+2} = f_i + f_{i+1}$ has no multiplication anywhere, so you have to manufacture one by multiplying the sum by 1.

$$(f_i + f_{i+1}) \cdot 1 = f_{i+2}$$

Witness vector:

z = [1, f_0, f_1, f_2, ..., f_n]

Row $i$ of $A$ picks $f_i$ and $f_{i+1}$, row of $B$ picks the constant, row of $C$ picks $f_{i+2}$. Two nonzero entries in $A$, one in $B$, one in $C$:

for i in 0..num_constraints {
    r1cs.a.set(i, 1 + i, F::ONE);  // f_i
    r1cs.a.set(i, 2 + i, F::ONE);  // f_{i+1}
    r1cs.b.set(i, 0, F::ONE);      // constant 1
    r1cs.c.set(i, 3 + i, F::ONE);  // f_{i+2}
}

For n = 10 the matrices, dots are zeros:

A =                                 B =
[ . 1 1 . . . . . . . . . ]         [ 1 . . . . . . . . . . . ]
[ . . 1 1 . . . . . . . . ]         [ 1 . . . . . . . . . . . ]
[ . . . 1 1 . . . . . . . ]         [ 1 . . . . . . . . . . . ]
[ . . . . 1 1 . . . . . . ]         [ 1 . . . . . . . . . . . ]
[ . . . . . 1 1 . . . . . ]         [ 1 . . . . . . . . . . . ]
...                                 ...

C =
[ . . . 1 . . . . . . . . ]
[ . . . . 1 . . . . . . . ]
[ . . . . . 1 . . . . . . ]
...

The entries are coefficients, not values. Every one is 1 because Fibonacci is pure addition with no scaling, and if the recurrence were something like $2f_i + 3f_{i+1}$ you would see 2 and 3 in $A$ instead. The Fibonacci numbers themselves live in the witness $z = [1, 0, 1, 1, 2, 3, 5, \dots]$, and the matrices only pick which entries to add: row 0 of $A$ has 1s in columns 1 and 2, so $Az$ pulls out $z_1 + z_2 = f_0 + f_1$.

Demo prints every constraint evaluated:

[f_0 + f_1 = f_2]  (1·z[1] + 1·z[2]) · (1·z[0]) = (1·z[3])   =>   1 · 1 = 1
[f_1 + f_2 = f_3]  (1·z[2] + 1·z[3]) · (1·z[0]) = (1·z[4])   =>   2 · 1 = 2
...
[f_8 + f_9 = f_10] (1·z[9] + 1·z[10]) · (1·z[0]) = (1·z[11]) =>   55 · 1 = 55

To verify, you do three sparse matrix-vector products and one Hadamard product, and that is the whole check: the format is rigid but the verifier is dead simple.

R1CS lives under Groth16, Marlin, Spartan, and Nova, where Nova uses a relaxed variant tuned for folding. In Rust the big ecosystem is arkworks, with bellman and bellpepper as the other major line, the one that Filecoin, Lurk, and Spartan2 sit on.

Plonkish

R1CS forces every row to be a degree-2 bilinear product, and every row carries a constraint. PLONK relaxed both of those, and the family of constraint systems that followed ended up being called “Plonkish”.

You write your circuit as a table, where each column has a type:

• advice holds your secret witness (you commit to it)
• fixed holds setup data
• selector is a 0/1 flag per row, says “this constraint fires here”

A constraint is a polynomial over those cells, and it can read not just the current row but also offsets above and below, where the offset is called a rotation. You multiply the whole constraint by a selector polynomial, and it fires only on rows where the selector is one.

On top of that you get two more tools: copy constraints, which are a permutation argument internally and let you say “this cell equals that cell” without writing the relationship into the witness layout, and lookups, which force a value to come from a precomputed table.

For Fibonacci you allocate one advice column called a, one selector s, and one fixed column to hold the boundary values 0 and 1, and you define a single gate:

$$s(\text{row}) \cdot \big(a(\text{row}) + a(\text{row}+1) – a(\text{row}+2)\big) = 0$$

That is three rotations of the same column wrapped in one selector, all in a single polynomial, with two copy constraints pinning $a(0) = \text{boundary}(0) = 0$ and $a(1) = \text{boundary}(1) = 1$.

let gate_expr = query(s, Rotation::CUR)
    * (query(a, Rotation::CUR)
       + query(a, Rotation::NEXT)
       - query(a, Rotation(2)));
cs.add_gate("fibonacci_step", gate_expr);

cs.copy(CellRef { column: a, row: 0 }, CellRef { column: boundary, row: 0 });
cs.copy(CellRef { column: a, row: 1 }, CellRef { column: boundary, row: 1 });

Resulting table for n = 10:

 row | advice a | selector s | boundary
-----+----------+------------+---------
   0 |     0    |     1      |    0
   1 |     1    |     1      |    1
   2 |     1    |     1      |    0
   3 |     2    |     1      |    0
   4 |     3    |     1      |    0
   5 |     5    |     1      |    0
   6 |     8    |     1      |    0
   7 |    13    |     1      |    0
   8 |    21    |     1      |    0
   9 |    34    |     0      |    0    (gate off: rotation +2 has no next-next)
  10 |    55    |     0      |    0    (gate off: end of trace)

The gate fires wherever the selector is one, and the last two rows turn it off because the rotation $+2$ would read past the end of the table.

The cost of all this flexibility is design effort: you pick the column layout, the custom gates, and which rotations make sense, and you watch the gate degree because bumping it from 2 to 3 roughly doubles prover cost. Column width, gate degree, and lookup usage all pull against each other, and balancing them is most of the work in writing a Plonkish circuit. What you get in return is compact circuits for common operations, plus wiring through copy constraints that is almost free in your circuit’s constraint count (not free in permutation argument cost, but free in the gate you write).

Plonkish is what halo2 runs on, along with its production fork axiom-crypto/halo2-lib, Plonky2, UltraPlonk, and many in-house variants.

AIR

Plonkish is still a two-dimensional table, and AIR is the same table viewed as a state machine that ticks row by row, where rows are time steps and columns are registers. A transition constraint is a polynomial over a fixed window of row offsets that has to evaluate to zero on every window, and a boundary constraint pins a single cell to a fixed value.

The window can be arbitrary in theory, but every real implementation (Plonky3, Winterfell, RISC Zero, Cairo, SP1) uses two consecutive rows for the standard API, for performance and proof size reasons. RAP (Randomized AIR with Preprocessing) adds randomized auxiliary columns tied to verifier challenges, LogUp adds lookups on top, and everything else stacks on the same core of trace plus transitions plus boundaries.

Fibonacci in AIR uses two columns: column a at row $r$ holds $f_r$, column b holds $f_{r+1}$, and you write two transition constraints between row $i$ and row $i+1$:

$$\text{shift: } a(\text{next}) – b(\text{curr}) = 0$$

$$\text{sum: } b(\text{next}) – \big(a(\text{curr}) + b(\text{curr})\big) = 0$$

Two boundaries: $a(0) = 0$, $b(0) = 1$.

let shift = next(0) - curr(1);
let sum   = next(1) - curr(0) - curr(1);

Trace:

 row |   a (f_i) |  b (f_{i+1})
-----+-----------+--------------
   0 |     0     |       1
   1 |     1     |       1
   2 |     1     |       2
   3 |     2     |       3
   4 |     3     |       5
   5 |     5     |       8
   6 |     8     |      13
   7 |    13     |      21
   8 |    21     |      34
   9 |    34     |      55

Both transitions are linear, degree 1, because Fibonacci is a linear recurrence with no multiplication anywhere in the body. This is the one spot where the three visibly diverge: R1CS had to fake a multiplication by 1, Plonkish ended up at degree 2 since the selector multiplies the linear body, and AIR stays at degree 1 with no fake multiplication to pay for.

The cost of AIR is having to think in state machines, which fits anything that already looks like one (RISC Zero proves full RISC-V execution as a Randomized AIR) and is awkward for anything that does not tick row by row. Transition constraints see only two rows at a time, so anything spanning a larger window needs extra columns, periodic columns, or auxiliary state encodings.

STARK-style AIR provers skip the trusted setup, which is the usual reason to pick them, but STARK proofs are typically much bigger than KZG-based PLONK proofs and the verifier is slower, so the choice comes down to what you can afford where you deploy.

AIR powers Cairo (StarkWare), Winterfell, Plonky3, RISC Zero, and SP1 pre-V6 (the version called Turbo). SP1 V6 (codenamed Hypercube) has been on mainnet since 19.02.2026 and swapped the FRI/STARK back end for a Jagged PCS multilinear IOP, but the per-chip constraint layer is still AIR. The paper is Hemo et al., ePrint 2025/917.

Side by side

For Fibonacci with n = 10:

Degrees in the table are for these Fibonacci circuits, not properties of the systems. R1CS is always rank-1 by definition, Plonkish allows higher degrees (zcash/halo2 computes the degree dynamically, axiom-crypto/halo2 defaults to MAX_DEGREE=5 via an env var), and AIR allows arbitrary polynomial degree, with real STARK constraints usually at degree 2-3 or more. Nova uses relaxed R1CS, a variant tuned for folding.

Same answer in all three: $f_{10} = 55$.

Run cargo run --bin compare in the repo to get the table with live values.

Can you unify the three

Kind of: a 2023 paper called CCS, short for Customizable Constraint Systems (ePrint 2023/552), generalizes all three by letting you specify a set of matrices and a multilinear combination over them, so R1CS, Plonkish, and AIR each fall out as special cases. Nova’s follow-up, HyperNova, uses CCS as the underlying representation.

In practice though, you pick a stack and the stack comes with one of the three shapes built in, so CCS is more of an academic unifier than something you actually use day to day.

Which one do you pick

Usually the stack picks for you, and the question is just what you are building. For a one-off SNARK over a small relation where pairing-based crypto and a trusted setup are fine, R1CS via arkworks plus Groth16 is what you get for free. For a production circuit like a bridge, a rollup, or a custom EVM precompile, Plonkish via halo2-lib is the default, because the ergonomics, the ecosystem, and the audit history are all there.

Anything that looks like a CPU executing instructions belongs in AIR, where Winterfell is the one to learn on and Plonky3 the one for when you need performance, or you can skip writing circuits entirely and grab a zkVM like RISC Zero, SP1, or Valida. And if you are learning, do all three: the repo writes Fibonacci in each, and going through the three implementations yourself shows the differences faster than reading papers about them does.

The repo

github.com/adamsmo/r1cs-plonkish-air

• src/field.rs: prime field over $p = 2^{31} – 1$, 140 lines
• src/r1cs.rs: sparse matrices, constraint check, Fibonacci builder
• src/plonkish.rs: cell table, custom gates with rotations, copy constraints, Fibonacci builder
• src/air.rs: trace, transition constraints, boundary constraints, Fibonacci builder
• src/bin/*.rs: four demos, fib_r1cs, fib_plonkish, fib_air, compare

cargo test passes 13 tests with zero external dependencies and standard library only.

What’s not in there: commitments, polynomial interpolation, FRI, KZG, Fiat-Shamir, or any actual proving. This is the arithmetization layer only, and proving sits on top of it.

What next

The next post goes back to step 5 of the road map, applying constraints to polynomials, and shows what happens when you feed one of these arithmetizations into FFT plus a commitment scheme: the trace becomes a polynomial that collapses to a single field element the verifier checks.

Until then, the repo is the fastest way to build intuition: pick the arithmetization that confuses you most, break the witness somewhere, and watch the fib_*_rejects_bad_witness soundness tests catch you. If something looks off or you find a bug, ping me on Discord.

Further reading

R1CS

• Gennaro, Gentry, Parno, Raykova “Quadratic Span Programs and Succinct NIZKs without PCPs” EUROCRYPT 2013 (ePrint 2012/215): the QAP construction that R1CS reformulates.
• Ben-Sasson, Chiesa, Genkin, Tromer, Virza “SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge” CRYPTO 2013 (ePrint 2013/507): introduces the R1CS format itself.
• Groth “On the Size of Pairing-based Non-interactive Arguments” EUROCRYPT 2016 (ePrint 2016/260): Groth16 over R1CS.

Plonkish

• Gabizon, Williamson, Ciobotaru “PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge” 2019 (ePrint 2019/953).
• Gabizon, Williamson “plookup: A simplified polynomial protocol for lookup tables” 2020 (ePrint 2020/315).

AIR

• Ben-Sasson, Bentov, Horesh, Riabzev “Scalable, transparent, and post-quantum secure computational integrity” 2018 (ePrint 2018/046): original STARK paper.