Arithmetic circuits and R1CS

See how an arbitrary computation is turned into something a ZK system can prove: an arithmetic circuit over a finite field, and the Rank-1 Constraint System (R1CS) that encodes "I ran this computation correctly" as a set of equations a prover claims to satisfy.

Track

Engineering

Module

4 · Zero-Knowledge Proofs

Prerequisites

Statement, witness, and the properties · Basic modular arithmetic

The proof systems in earlier modules proved a single algebraic fact (knowing a discrete log). To prove something useful — "this transaction is valid", "this credential check passed" — we need a way to express an arbitrary computation in a form the prover and verifier can both reason about algebraically. The answer is to rewrite the computation as an arithmetic circuit: a network of addition and multiplication gates operating on numbers in a finite field, where "the program ran correctly" becomes "every gate's output is consistent with its inputs".

Once a computation is a circuit, proving it ran correctly is the same as proving you know values for every wire such that every gate equation holds. That bundle of wire values is the witness; the gate equations are the statement. R1CS is the standard, systematic way to write those equations down.

An arithmetic circuit over a field is a directed acyclic graph of gates. Each gate adds or multiplies its input wires; input wires carry the public inputs and the private witness, and output wires carry results. A computation is "satisfied" when there is an assignment to all wires that is consistent with every gate and with the claimed public output.

Finite field

The number system (integers mod a large prime p) in which all circuit arithmetic happens. Addition and multiplication wrap around mod p.

Arithmetic circuit

A DAG of add/multiply gates encoding the computation; the structure is public, the wire values are the witness.

R1CS (Rank-1 Constraint System)

A flattening of the circuit into a list of constraints, each of the form (linear combo of variables) × (linear combo) = (linear combo). The "rank-1" part is the single multiplication per constraint.

Witness vector z

The full vector of variable assignments (the constant 1, the public inputs, and all intermediate/private values) that the prover claims satisfies every constraint.

R1CS represents the circuit as three matrices A, B, C over the field. The witness vector z collects every variable (conventionally z[0] = 1, then public inputs, then private/intermediate values). A satisfying assignment makes every constraint hold simultaneously. The notation ∘ is the component-wise (Hadamard) product; · is matrix–vector multiplication.

R1CS (schematic)
Variables:  z = ( 1, public_inputs..., witness... )     over field F_p

One constraint i:
   ( A_i · z ) * ( B_i · z )  =  ( C_i · z )
   # each side is a linear combination of the variables in z;
   # exactly ONE multiplication per constraint (hence rank-1)

All m constraints at once:
   ( A · z )  ∘  ( B · z )  =  ( C · z )          (∘ = Hadamard)

The statement proven:
   "I know a z, consistent with the public inputs,
    such that ALL m constraints above hold."

Example: proving  y = x * x  (x private, y public)
   z = ( 1, y, x )
   constraint:  ( x ) * ( x )  =  ( y )
   A row selects x, B row selects x, C row selects y

Any computation expressible as a bounded circuit can be flattened this way: each multiplication gate becomes (at least) one rank-1 constraint, and additions fold into the linear combinations for free. A comparison like "a < b" is not a single field operation — it is encoded by introducing bit-decomposition variables and constraints that force each bit to be 0 or 1 (e.g. b·(b−1)=0). The number of constraints, not the prime, is the usual proxy for how expensive a statement is to prove.

1. 1Fix the computation and decide what is public (inputs/outputs in the statement) and what is private (the witness).
2. 2Arithmetize: rewrite the program using only field additions and multiplications; replace branches, comparisons and bit operations with equivalent constraints.
3. 3Compile to a circuit: express the computation as add/multiply gates, introducing intermediate wires for each multiplication.
4. 4Flatten to R1CS: emit one rank-1 constraint per multiplication, building the A, B, C matrices; additions live inside the linear combinations.
5. 5The prover computes the full witness vector z (all wire values) and proves, with a chosen proving system, that z satisfies every constraint — without revealing the private part of z.

synthetic — arithmetizing "I know x with x^3 + x + 5 == 35"
Goal: prove knowledge of x s.t.  x^3 + x + 5 = 35   (public: 35)

Introduce intermediate wires to keep each constraint rank-1:
   sym1 = x * x            # constraint 1:  (x)*(x) = sym1
   y    = sym1 * x         # constraint 2:  (sym1)*(x) = y      (= x^3)
   out  = y + x + 5        # linear, folds into C
   require  out = 35

Witness vector:
   z = ( 1, out=35, x, sym1, y )

R1CS constraints:
   (x)   * (x)   = sym1
   (sym1)* (x)   = y
   (y + x + 5) * (1) = out       # linear check, out pinned to 35

Prover knows x (e.g. x = 3): sym1=9, y=27, out=35. Valid.

This mirrors the canonical teaching example used across the ZK literature (e.g. Vitalik Buterin's widely-cited QAP write-up). The verifier only sees the public output 35 and the structure of the constraints; x stays in the private part of z. Proving the statement is now purely "I know a z satisfying this R1CS", which the proving systems of the next modules can handle generically.

For agent authorization, the policy check itself is the computation to arithmetize: "verify the delegation signature, check scope ⊇ request, check now < expiry, check nonce == challenge" becomes a circuit, and R1CS constraints encode each step. The witness is the credential; the public statement is the request context. A proof then certifies the entire policy evaluation ran correctly on a real credential — without exposing it.

Crucially, constraint count drives cost. A policy that needs signature verification and range checks inside the circuit can be thousands to millions of constraints, which is why the choice of proving system (next modules) and careful circuit design matter so much for agents that must prove authority at runtime.

• ▸Under-constraining is the classic bug: if the circuit forgets a constraint (e.g. that a bit is really 0 or 1), a malicious prover can assign values that "satisfy" the system while cheating — the proof is valid but meaningless.
• ▸Everything is mod p: subtraction, comparison and bit operations need explicit encoding, and an overlooked wrap-around can create soundness holes.
• ▸Cost scales with the number of constraints, not with how simple the program looks; signature checks and hashing inside a circuit are expensive.
• ▸R1CS is one arithmetization among several (Plonkish/custom gates, AIR for STARKs); a circuit written for one is not directly portable to another, and they have different performance trade-offs.
• ▸Correct arithmetization does not validate the policy itself — you can faithfully prove you executed a flawed authorization rule.

Expected direction: The single constraint only pins out to b; it never restricts b to {0,1}, so a prover can set b to any field element (e.g. 7) and still satisfy it — the circuit is under-constrained. Add the boolean constraint (b)*(b - 1) = 0, which holds only when b = 0 or b = 1. With both constraints, b is forced to be a genuine bit and out = b is meaningful.

What does an arithmetic circuit compute over, and what are its only operations?

Over a finite field (integers mod a large prime); its gates perform only field addition and multiplication.

What form does a single R1CS constraint take, and why "rank-1"?

(A·z)(B·z) = (C·z), where each term is a linear combination of the variables. "Rank-1" because there is exactly one multiplication per constraint.

Why is under-constraining a circuit dangerous?

A missing constraint lets a malicious prover assign values that satisfy the written equations while violating the intended meaning (e.g. a "bit" that is not 0 or 1), producing valid-but-meaningless proofs.