Arithmetic Circuits & R1CS

To prove a computation in ZK, you translate it into an arithmetic circuit — addition and multiplication gates over a finite field.

Example: prove c = a*b + d for hidden a, b, d.

Gates:

• t = a * b (multiplication gate)
• c = t + d (addition gate)

Each gate becomes a constraint. R1CS (Rank-1 Constraint System) is the standard form:

(A · w) * (B · w) = (C · w)

where w is the witness vector, A, B, C are matrices.

For our example:

• w = (1, a, b, c, d, t)
• Constraint 1: a * b = t
  • A row: (0, 1, 0, 0, 0, 0)
  • B row: (0, 0, 1, 0, 0, 0)
  • C row: (0, 0, 0, 0, 0, 1)
• Constraint 2: 1 * (t + d) = c
  • A row: (1, 0, 0, 0, 0, 0)
  • B row: (0, 0, 0, 0, 1, 1)
  • C row: (0, 0, 0, 1, 0, 0)

A SNARK proves: "I know w such that all constraints hold."

R1CS to circuit complexity: Bitcoin's proof-of-work has ~80k constraints. A complex computation (zkRollup batch verifying 1000 transactions): millions of constraints.

Languages for circuits:

• Circom (Iden3, used by zk-SNARKs widely).
• Cairo (StarkNet).
• Noir (Aztec).
• zkSTARK assembly (RISC-style).

Constraint optimization is a big art. Reducing 1M gates → 500k = 2x faster proof generation.

Witness reduction: in real systems, prover allocates intermediate variables to keep the constraint count down. Compilers from high-level languages (Noir, Circom) handle this.