Proof PeaksISSUE #15 of 38

arithmetic circuits · r1cs · constraints

ZeekaVSThe Collision

Zeeka saysA SNARK proves a computation by first rewriting it as an arithmetic circuit, then as R1CS: a list of constraints of the form (A·w)(B·w) = (C·w).

To prove a computation you first turn it into an arithmetic circuit of add and multiply gates over a field, then flatten that into R1CS (Rank-1 Constraint System). Each gate becomes one constraint (A·w) × (B·w) = (C·w), where w is the witness vector: the constant 1, the public inputs, and every intermediate wire value.

A valid witness satisfies all constraints at once. R1CS is the universal bridge from "a program" to "something a SNARK can prove" — Groth16 and PLONK both start here. The demo encodes Vitalik's classic example, proving you know x with x³ + x + 5 = 35 (answer x = 3), and checks that the witness satisfies every constraint.

Power-ups you unlock

Computations become circuits of add and multiply gates over a field
R1CS encodes each gate as (A·w) × (B·w) = (C·w)
w is the witness: 1, public inputs, and all intermediate wires
A valid witness satisfies every constraint simultaneously
This is the bridge from a program to something provable

The Collision attacks — common mistakes

Forgetting the constant 1 entry in the witness vector
Adding more constraints than the computation needs (bloats the proof)
Leaving a wire under-constrained — lets a prover cheat
Doing the arithmetic outside the field

Boss battleEncode x³ + x + 5 = 35 as R1CS and verify the witness for x = 3 satisfies all constraints.

Example code

<!doctype html><html><head><meta charset="utf-8"></head>
<body style="background:#06040d;color:#e6e0ff;font-family:monospace;padding:20px"><pre id="o"></pre>
<script>
// R1CS: know x with x³ + x + 5 = 35  (x=3), as (A·w)(B·w) = (C·w).
const F=97, mod=(n)=>((n%F)+F)%F, dot=(v,w)=>mod(v.reduce((s,a,i)=>s+a*w[i],0));
const x=3, s1=x*x, s2=s1*x, out=s2+x+5;
const w=[1, x, out, s1, s2].map(mod);              // w = [1, x, out, x², x³]
const cons=[
  { A:[0,1,0,0,0], B:[0,1,0,0,0], C:[0,0,0,1,0] },   // x · x = x²
  { A:[0,0,0,1,0], B:[0,1,0,0,0], C:[0,0,0,0,1] },   // x² · x = x³
  { A:[0,0,0,0,1], B:[1,0,0,0,0], C:[-5,-1,1,0,0] }, // x³ · 1 = out − x − 5
];
const res = cons.map(c => ({ lhs: mod(dot(c.A,w)*dot(c.B,w)), rhs: dot(c.C,w) }));
const allOk = res.every(r => r.lhs === r.rhs);
document.getElementById('o').textContent = [
  'prove knowledge of x: x³ + x + 5 = 35',
  'witness w = [1, x, out, x², x³] = [' + w.join(', ') + ']',
  ...res.map((r,i)=> '  constraint ' + (i+1) + ': ' + r.lhs + ' == ' + r.rhs + '  ' + (r.lhs===r.rhs?'✓':'✗')),
  'all constraints satisfied? ' + allOk + '   (x=3 is a valid witness)'
].join('\n');
</script></body></html>

▶ Open the interactive comic issue

‹ Interactive Vs Non-Interactive · Fiat-Shamir Qap · From R1cs To Polynomials ›