Skip to content
LumenaryAcademy
Verifiable 90 min

Arithmetisation and SNARKs

Turning a computation into polynomial equations over a finite field, committing to polynomials, and the proof systems — Groth16 and PLONK — built from them.

Code tested · 6AI-draftedAwaiting review by a computer scientist

Your guides: Chloe · The Computer Scientist, Margaret · The Experimenter, Gideon · The Verifier

MotivationH

A proof the size of a tweet

A validity rollup executes thousands of transactions off-chain and posts to Ethereum a new state root together with a proof that the transition was computed correctly. With the Groth16 proof system that proof is three elliptic-curve points, 128 bytes in compressed form on the BN254 curve, and a smart contract checks it with a few pairing operations costing a couple of hundred thousand gas, whether the batch held ten transactions or ten thousand. Zcash's shielded payments are checked with SNARKs too.

Such proof systems are SNARKs: Succinct, Non-interactive ARguments of Knowledge. The previous two lessons gave us two of the ingredients: random evaluation of polynomials makes cheating detectable (sumcheck), and Fiat–Shamir removes interaction (zero knowledge). This lesson adds the remaining two: a way to turn an arbitrary computation into polynomials (arithmetisation), and a way for a prover to commit to a huge polynomial with a short message and later prove its value at a point (polynomial commitments). It ends with the bug that causes more real SNARK failures than any broken cryptography: a circuit that forgets to say something.

DefinitionsH

SNARKs and constraint systems

Definition— SNARK

A SNARK for a relation R(x,w)R(x, w) (public statement xx, secret witness ww) is a non-interactive proof system in which:

  • Succinct: the proof has size polylogarithmic in (often independent of) the size of the computation that checks RR, and verification takes time polylogarithmic in it plus time linear in ∣x∣|x|;
  • Argument: soundness holds against provers that run in polynomial time, under a cryptographic assumption;
  • of Knowledge: a prover that convinces the verifier must "know" a valid ww (an extractor exists).

A zkSNARK is additionally zero-knowledge. Some SNARKs need a setup that produces public parameters (a structured reference string, SRS); if the setup uses no secrets, the SNARK is transparent.

Proof systems do not run programs; they check equations. So the first step is to express "the computation was done correctly" as a set of equations over a finite field Fp\mathbb{F}_p.

Definition— arithmetic circuit

An arithmetic circuit over Fp\mathbb{F}_p is a directed acyclic graph whose inputs are field elements and whose gates add or multiply two field elements. A computation is expressed by a circuit whose output is 0 (or some public value) exactly when the computation was correct, given the witness as extra input.

Definition— rank-1 constraint system (R1CS)

An R1CS consists of three m×nm \times n matrices AA, BB, CC over Fp\mathbb{F}_p. A vector z∈Fp nz \in \mathbb{F}_p^{\,n} with z0=1z_0 = 1, containing the public inputs and the witness, satisfies it if

(Az)∘(Bz)=Cz,(Az) \circ (Bz) = Cz,

where ∘\circ is the entrywise product. Each of the mm rows says: (a linear combination of variables) times (a linear combination) equals (a linear combination). One multiplication per row, any number of additions for free.

Everything must be phrased in field arithmetic, and that shapes what is cheap. Addition and multiplication by constants are free inside the linear combinations; each multiplication of two variables costs a constraint. A bit bb is a variable with the constraint b⋅b=bb \cdot b = b, whose only solutions in a field are 0 and 1. A comparison such as "x<16x < 16" has no direct field meaning (fields are not ordered), so it is done by decomposing xx into bits and checking each one. A hash function designed for CPUs, like SHA-256, is all bit operations and costs tens of thousands of R1CS constraints per compression; "arithmetisation-friendly" hashes such as Poseidon are built from field operations and cost a few hundred. Choosing what to prove, and how, is the largest lever on prover cost.

ComputationC

Building an R1CS by hand

Our statement: "I know two 4-bit numbers xx and yy with x⋅y=Nx \cdot y = N", for a public NN. For N=143N = 143 this is a claim to know a factorisation of 143 into two small factors. The variables are z=(1,N,x,y,x0,…,x3,y0,…,y3)z = (1, N, x, y, x_0, \ldots, x_3, y_0, \ldots, y_3) and the constraints are:

  • xi⋅xi=xix_i \cdot x_i = x_i and yi⋅yi=yiy_i \cdot y_i = y_i for i=0,…,3i = 0, \ldots, 3: each xi,yix_i, y_i is a bit (8 constraints);
  • (x0+2x1+4x2+8x3)⋅1=x(x_0 + 2x_1 + 4x_2 + 8x_3) \cdot 1 = x, and the same for yy: the bits represent xx and yy, so both are below 16 (2 constraints);
  • x⋅y=Nx \cdot y = N (1 constraint).

Since x,y<16x, y < 16, the product is below 256, far smaller than pp, so the field equation x⋅y=Nx \cdot y = N is the integer equation. The program builds the three matrices row by row, prints one row, and checks three assignments.

python
p = 2**31 - 1        # a toy prime field; production SNARKs use primes of about 255 bits

# The statement: "I know 4-bit numbers x and y with x * y = N", for a public N.
# Variables z = [one, N, x, y, x0..x3, y0..y3]; one is always 1, N is public, the rest are secret.
NAMES = ["one", "N", "x", "y"] + [f"x{i}" for i in range(4)] + [f"y{i}" for i in range(4)]

def vec(**coeffs):
    return [coeffs.get(name, 0) % p for name in NAMES]

def factor_r1cs():
    rows, labels = [], []
    for v in "xy":
        for i in range(4):                                   # b * b = b forces b in {0, 1}
            b = f"{v}{i}"
            rows.append((vec(**{b: 1}), vec(**{b: 1}), vec(**{b: 1})))
            labels.append(f"{b} is a bit")
        rows.append((vec(**{f"{v}{i}": 2**i for i in range(4)}), vec(one=1), vec(**{v: 1})))
        labels.append(f"{v} = {v}0 + 2*{v}1 + 4*{v}2 + 8*{v}3")
    rows.append((vec(x=1), vec(y=1), vec(N=1)))
    labels.append("x * y = N")
    return rows, labels

def violated(rows, labels, z):
    dot = lambda r: sum(a * b for a, b in zip(r, z)) % p
    return [lab for (a, b, c), lab in zip(rows, labels) if dot(a) * dot(b) % p != dot(c)]

def assignment(N, x, y):
    return [1, N, x, y] + [(x >> i) & 1 for i in range(4)] + [(y >> i) & 1 for i in range(4)]

rows, labels = factor_r1cs()
print(f"{len(rows)} constraints over {len(NAMES)} variables; constraint 5 (x as a sum of its bits) is")
for name, r in zip("ABC", rows[4]):
    print(f"  {name}: {r}")
print("x=11, y=13, N=143 -> violated:", violated(rows, labels, assignment(143, 11, 13)))
print("x=3,  y=5,  N=143 -> violated:", violated(rows, labels, assignment(143, 3, 5)))
z = assignment(143, 11, 13)
z[NAMES.index("x1")] = 0                                     # tamper with one bit of x
print("one bit of x changed -> violated:", violated(rows, labels, z))
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

A checker that names the violated constraints is also how circuit developers debug: a "proof generation failed" error usually means a witness that violates some row.

ComputationC

From many constraints to one polynomial identity

Checking mm constraints one by one is not succinct. The quadratic arithmetic program (QAP) of Gennaro, Gentry, Parno and Raykova (2013) packs them into one statement about polynomials. Assign constraint ii to the point X=iX = i. For each variable jj, let Aj(X)A_j(X) be the polynomial of degree less than mm with Aj(i)=AijA_j(i) = A_{ij} for every row ii, found by Lagrange interpolation:

Aj(X)=∑i=1mAij∏k≠iX−ki−k,A_j(X) = \sum_{i=1}^{m} A_{ij} \prod_{k \neq i} \frac{X - k}{i - k},

and define BjB_j and CjC_j in the same way. For an assignment zz, set Az(X)=∑jzjAj(X)A_z(X) = \sum_j z_j A_j(X), and similarly BzB_z and CzC_z. Then Az(i)Bz(i)−Cz(i)A_z(i)B_z(i) - C_z(i) is exactly the left side minus the right side of constraint ii, so

z satisfies the R1CS  ⟺  Az(X) Bz(X)−Cz(X) vanishes at 1,…,m  ⟺  Z(X) divides Az(X)Bz(X)−Cz(X),z \text{ satisfies the R1CS} \iff A_z(X)\,B_z(X) - C_z(X) \text{ vanishes at } 1, \ldots, m \iff Z(X) \text{ divides } A_z(X)B_z(X) - C_z(X),

where Z(X)=(X−1)(X−2)⋯(X−m)Z(X) = (X - 1)(X - 2)\cdots(X - m) is the vanishing polynomial. The prover can exhibit the quotient H(X)H(X) with AzBz−Cz=H⋅ZA_zB_z - C_z = H \cdot Z, and by Schwartz–Zippel it suffices to check this identity at one random point τ\tau: if it is false, the two sides are different polynomials of degree at most 2m−22m - 2, which agree at no more than 2m−22m - 2 points.

python
import random

p = 2**31 - 1
NAMES = ["one", "N", "x", "y"] + [f"x{i}" for i in range(4)] + [f"y{i}" for i in range(4)]

def vec(**coeffs):
    return [coeffs.get(name, 0) % p for name in NAMES]

def factor_r1cs():                     # the same 11 constraints as before, as (a, b, c) rows
    rows = []
    for v in "xy":
        rows += [(vec(**{f"{v}{i}": 1}),) * 3 for i in range(4)]
        rows.append((vec(**{f"{v}{i}": 2**i for i in range(4)}), vec(one=1), vec(**{v: 1})))
    rows.append((vec(x=1), vec(y=1), vec(N=1)))
    return rows

def assignment(N, x, y):
    return [1, N, x, y] + [(x >> i) & 1 for i in range(4)] + [(y >> i) & 1 for i in range(4)]

# --- Polynomials over F_p as coefficient lists, lowest degree first -------------------------
def trim(f):
    while len(f) > 1 and f[-1] == 0:
        f = f[:-1]
    return f

def add(f, g, sign=1):
    n = max(len(f), len(g))
    f, g = f + [0] * (n - len(f)), g + [0] * (n - len(g))
    return trim([(a + sign * b) % p for a, b in zip(f, g)])

def mul(f, g):
    out = [0] * (len(f) + len(g) - 1)
    for i, a in enumerate(f):
        for j, b in enumerate(g):
            out[i + j] = (out[i + j] + a * b) % p
    return trim(out)

def divmod_poly(f, g):
    f, q = list(f), [0] * max(1, len(f) - len(g) + 1)
    inv = pow(g[-1], -1, p)
    for k in range(len(f) - len(g), -1, -1):
        q[k] = f[k + len(g) - 1] * inv % p
        for j, b in enumerate(g):
            f[k + j] = (f[k + j] - q[k] * b) % p
    return trim(q), trim(f[:len(g) - 1] or [0])

def evaluate(f, x):
    acc = 0
    for c in reversed(f):
        acc = (acc * x + c) % p
    return acc

def interpolate(xs, ys):
    """Lagrange: the unique polynomial of degree < len(xs) through the points (xs[i], ys[i])."""
    total = [0]
    for i, (xi, yi) in enumerate(zip(xs, ys)):
        basis, denom = [1], 1
        for j, xj in enumerate(xs):
            if j != i:
                basis = mul(basis, [-xj % p, 1])
                denom = denom * (xi - xj) % p
        total = add(total, mul(basis, [yi * pow(denom, -1, p) % p]))
    return total

# --- From R1CS to QAP: one polynomial per column of A, B and C ------------------------------
rows = factor_r1cs()
m = len(rows)
points = list(range(1, m + 1))                 # constraint i is checked at the point X = i
cols = [[interpolate(points, [rows[i][k][j] for i in range(m)]) for j in range(len(NAMES))]
        for k in range(3)]                     # cols[0][j] is A_j(X), and so on
Z = [1]
for i in points:
    Z = mul(Z, [-i % p, 1])                    # Z(X) = (X - 1)(X - 2)...(X - m)

def qap_check(z):
    A_z, B_z, C_z = [[0], [0], [0]]
    for j, zj in enumerate(z):
        A_z = add(A_z, mul(cols[0][j], [zj]))
        B_z = add(B_z, mul(cols[1][j], [zj]))
        C_z = add(C_z, mul(cols[2][j], [zj]))
    P = add(mul(A_z, B_z), C_z, sign=-1)       # vanishes at 1..m iff every constraint holds
    H, R = divmod_poly(P, Z)
    return P, H, R

for x, y in [(11, 13), (3, 5)]:
    P, H, R = qap_check(assignment(143, x, y))
    print(f"x={x:2}, y={y:2}: deg(A*B - C) = {len(P) - 1}, deg Z = {len(Z) - 1}, "
          f"deg H = {len(H) - 1}, Z divides A*B - C: {R == [0]}")

# The SNARK idea: instead of comparing polynomials, compare them at ONE secret random point tau.
tau = random.Random(1).randrange(p)
P, H, R = qap_check(assignment(143, 11, 13))
print("at a random tau: P(tau) == H(tau) * Z(tau):", evaluate(P, tau) == evaluate(H, tau) * evaluate(Z, tau) % p)
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

The remaining problem is that the verifier must not see the polynomials, which are as large as the computation and contain the witness. It needs to check Az(τ)Bz(τ)−Cz(τ)=H(τ)Z(τ)A_z(\tau)B_z(\tau) - C_z(\tau) = H(\tau)Z(\tau) at a point the prover cannot anticipate, using values the prover has bound itself to in advance. That is what polynomial commitments provide.

ExplanationH

Polynomial commitments and KZG

Definition— polynomial commitment scheme

A polynomial commitment scheme lets a prover publish a short commitment CC to a polynomial ff of degree less than DD, and later, for any point zz the verifier names, send a value yy with a short opening proof that f(z)=yf(z) = y. It is binding (no efficient prover can open CC to values of two different polynomials) and, if needed, hiding.

KZG (Kate, Zaverucha and Goldberg, 2010) is the scheme behind many deployed SNARKs and Ethereum's data blobs. It needs a pairing: a map e:G1×G2→GTe : \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T between groups of prime order pp on a pairing-friendly elliptic curve (BN254 or BLS12-381) that is bilinear, e(ga,hb)=e(g,h)abe(g^a, h^b) = e(g, h)^{ab}. A pairing lets the verifier check one multiplication "in the exponent" without knowing the exponents (see elliptic curves for the geometry behind it).

  1. Setup. Someone picks a secret τ∈Fp\tau \in \mathbb{F}_p and publishes g,gτ,gτ2,…,gτD−1g, g^{\tau}, g^{\tau^2}, \ldots, g^{\tau^{D-1}} and h,hτh, h^{\tau}. Then τ\tau must be destroyed.
  2. Commit. For f(X)=∑ifiXif(X) = \sum_i f_i X^i, the prover computes C=∏i(gτi)fi=gf(τ)C = \prod_i (g^{\tau^i})^{f_i} = g^{f(\tau)}: a multi-scalar multiplication (MSM) over the public powers. The commitment is one group element, whatever the degree.
  3. Open at zz. If f(z)=yf(z) = y, then X−zX - z divides f(X)−yf(X) - y; the prover computes the quotient q(X)=(f(X)−y)/(X−z)q(X) = (f(X) - y)/(X - z) and sends π=gq(τ)\pi = g^{q(\tau)}, again one group element.
  4. Verify. Check e(C⋅g−y, h)=e(π, hτ⋅h−z)e(C \cdot g^{-y},\ h) = e(\pi,\ h^{\tau} \cdot h^{-z}), which says f(τ)−y=q(τ)(τ−z)f(\tau) - y = q(\tau)(\tau - z) in the exponent.

If f(z)≠yf(z) \neq y, no polynomial qq makes that identity hold, and producing a fake π\pi is believed infeasible (under the "qq-strong Diffie–Hellman" assumption) as long as nobody knows τ\tau. Commitments and proofs are constant-size (48 bytes each on BLS12-381) and verification costs two pairings. This is exactly the QAP check of the last section: commit to the polynomials, let Fiat–Shamir pick the point, open there.

Ceremonies in practice. Zcash's first ceremony in 2016 had six participants; its "Powers of Tau" ceremony of 2017–2018 accepted 87 contributions, and anyone can verify the transcript. Ethereum's KZG ceremony, run from January to August 2023 for the data blobs of EIP-4844, received 141,416 contributions, many from people in a web browser, so that the 1-of-N trust assumption is spread over an enormous N. Setups have failed in other ways. In 2019 Zcash disclosed that a subtle error in the key-generation procedure of the paper behind its original 2016 proof system produced extra elements, unused by honest provers but present in the public ceremony transcript, that would have allowed undetectable counterfeiting (CVE-2019-7167). A company cryptographer found it in March 2018; it was quietly removed by the Sapling upgrade that October and disclosed in February 2019, with no evidence of exploitation (disclosure).

ExplanationH

Groth16 and PLONK

Groth16 (Jens Groth, 2016) compiles a QAP into a proof of exactly three group elements, A,C∈G1A, C \in \mathbb{G}_1 and B∈G2B \in \mathbb{G}_2, which the verifier checks with one pairing equation (a product of pairings, four in a typical implementation, one of which can be precomputed). The setup encodes the specific circuit's polynomials at the secret τ\tau, so it is circuit-specific: change one constraint and you need a new ceremony. In exchange Groth16 has the smallest proofs and fastest verification of any widely used SNARK. On Ethereum, the pairing precompile costs 45,000+34,000k45{,}000 + 34{,}000k gas for kk pairings, so a Groth16 check costs roughly 180,000–250,000 gas depending on the number of public inputs. Many systems use other proof systems for speed and then wrap the final proof in Groth16 for cheap on-chain verification.

PLONK (Gabizon, Williamson and Ciobotaru, 2019) changed the setup and the constraint format.

  • Universal, updatable setup. One powers-of-tau ceremony serves every circuit up to a maximum size, and anyone can add a fresh contribution later.
  • Gates with selectors. Each row of the circuit has three wires ai,bi,cia_i, b_i, c_i and fixed selector values, with the gate equation qL,i ai+qR,i bi+qO,i ci+qM,i aibi+qC,i=0.q_{L,i}\, a_i + q_{R,i}\, b_i + q_{O,i}\, c_i + q_{M,i}\, a_i b_i + q_{C,i} = 0. Selectors (1,1,−1,0,0)(1, 1, -1, 0, 0) make an addition gate and (0,0,−1,1,0)(0, 0, -1, 1, 0) a multiplication gate.
  • Copy constraints by a permutation argument. Gates are independent rows; wiring says that certain cells must hold equal values (the output of gate 1 is the left input of gate 3). Number the cells and let σ\sigma be a permutation that cycles through each group of cells that must be equal. Then for random challenges β,γ\beta, \gamma, ∏iwi+β⋅i+γwi+β⋅σ(i)+γ=1\prod_i \frac{w_i + \beta \cdot i + \gamma}{w_i + \beta \cdot \sigma(i) + \gamma} = 1 holds when the values ww respect the wiring, and fails with high probability otherwise (two different multisets give different polynomials in β\beta and γ\gamma). PLONK proves this product with a running-product polynomial, committed and checked at a random point.
python
import random

p = 2**31 - 1

# A PLONK-style circuit for out = (x + y) * (x * y): one row per gate, wires a, b, c, and
# selectors (qL, qR, qO, qM, qC) with the gate equation qL*a + qR*b + qO*c + qM*a*b + qC = 0.
gates = [
    ("add", (1, 1, -1, 0, 0)),     # c0 = a0 + b0
    ("mul", (0, 0, -1, 1, 0)),     # c1 = a1 * b1
    ("mul", (0, 0, -1, 1, 0)),     # c2 = a2 * b2
]
n = len(gates)
# Wire positions are numbered a0..a2 = 0..2, b0..b2 = 3..5, c0..c2 = 6..8.
# Copy constraints: a0 = a1 (both x), b0 = b1 (both y), c0 = a2, c1 = b2.
sigma = list(range(3 * n))
for i, j in [(0, 1), (3, 4), (6, 2), (7, 5)]:
    sigma[i], sigma[j] = j, i          # each pair forms a 2-cycle of the permutation

def gates_ok(w):
    a, b, c = w[:n], w[n:2 * n], w[2 * n:]
    return all((qL * a[i] + qR * b[i] + qO * c[i] + qM * a[i] * b[i] + qC) % p == 0
               for i, (_, (qL, qR, qO, qM, qC)) in enumerate(gates))

def grand_product(w, beta, gamma):
    """prod (w_i + beta*i + gamma) / (w_i + beta*sigma(i) + gamma): equals 1 if w is constant
    on every cycle of sigma, and (by Schwartz-Zippel in beta, gamma) almost surely not otherwise."""
    num = den = 1
    for i, wi in enumerate(w):
        num = num * (wi + beta * i + gamma) % p
        den = den * (wi + beta * sigma[i] + gamma) % p
    return num * pow(den, -1, p) % p

x, y = 3, 4
honest = [x, x, x + y,  y, y, x * y,  x + y, x * y, (x + y) * (x * y)]
# A cheat: feed gate 2 the value 8 instead of x + y = 7, and fix its output so the gate holds.
cheat = list(honest)
cheat[2] = 8
cheat[8] = 8 * cheat[5]

rng = random.Random(9)
beta, gamma = rng.randrange(p), rng.randrange(p)       # the verifier's random challenges
for name, w in [("honest", honest), ("cheat ", cheat)]:
    print(f"{name}: output {w[8]:3}, every gate holds: {gates_ok(w)}, "
          f"grand product = {grand_product(w, beta, gamma)}")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

The cheating table satisfies every gate equation, because each gate on its own is fine; only the wiring is broken, and only the grand product notices. Custom gates generalise the selectors: a gate can be any low-degree polynomial in a row's wires, so a whole round of a hash function, or an elliptic-curve addition, can be one row instead of dozens. This "PLONKish" arithmetisation, with lookup tables (next lesson), underlies systems such as Zcash's Halo 2, Plonky2 and many zkEVM circuits. A PLONK proof with KZG is around half a kilobyte, and verification needs two pairings plus a few dozen group and field operations.

ExplanationH

The modern framing: polynomial IOP + polynomial commitment

By 2020 a clean decomposition had emerged (in the Marlin and DARK papers, among others). A polynomial interactive oracle proof (polynomial IOP) is an interactive proof in which the prover's messages are polynomials that the verifier may query at points of its choice, as if it had oracle access to them. Its soundness is information-theoretic, like sumcheck's. Replacing each oracle by a polynomial commitment gives an interactive argument, and Fiat–Shamir makes it non-interactive.

computation or statementconstraint system over 𝔽ₚpolynomial IOPpublic-coin interactive argumentSNARKarithmetise: R1CS, PLONKish, AIRencode as polynomial identitiessound with no cryptographycommit: KZG, IPA, FRI, multilinear PCSFiat–Shamir: challenges are hashes
How a SNARK is assembled. Each arrow is a separate design choice: the arithmetisation, the polynomial IOP and the commitment scheme can be mixed and matched, and the security of the result rests on the IOP's soundness, the commitment's binding and the Fiat–Shamir hash.

The commitment scheme determines most of a SNARK's engineering profile:

CommitmentSetupProof sizeVerifierAssumptionPost-quantum?
KZGtrusted (powers of tau)constant, about 48 bytes per openingconstant: 2 pairingspairings, qq-SDHno
IPA / Bulletproofstransparentlogarithmiclinear in degreediscrete logno
FRI (Merkle trees of codewords)transparentpolylogarithmic, tens to hundreds of KB per proofpolylogarithmic, hashes onlycollision-resistant hashplausibly yes
Multilinear schemes (Hyrax, Dory, Ligero/Brakedown-style, Basefold, WHIR)mostly transparentfrom logarithmic to square-rootvariesvariessome

And whole systems, roughly, as of 2026 (sizes for about a million constraints; prover times vary by orders of magnitude with hardware and implementation, so compare designs, not marketing numbers):

SystemProof sizeVerifyProver dominated bySetup
Groth16128–192 bytes3–4 pairings, about 1 msMSMs, FFTsper circuit
PLONK + KZGabout 0.5–1 KB2 pairingsMSMs, FFTsuniversal
STARK (FRI)about 50–200 KBhashes, a few msFFTs, hashingnone
Bulletproofsabout 1–2 KBlinear in circuit sizeMSMsnone

Prover cost is the price of all this. Generating a proof typically takes thousands to millions of times longer than running the computation natively, and memory use is large; the next three lessons are largely about bringing that factor down.

Worked examplesH

The classic bug: an under-constrained circuit

A circuit is under-constrained if it accepts some witness that does not correspond to a correct computation. The proof system then works perfectly — and proves a false statement. Unlike a broken cryptographic assumption, nothing about this bug is exotic: it is a missing line.

Take our factoring circuit and delete the eight booleanity constraints, as a hurried author might ("the bits are computed from xx, so of course they are bits"). The bits are computed by the honest prover's witness generator; the constraints are all that bind a malicious one. Without b⋅b=bb \cdot b = b, the "bits" can be any field elements, the range check disappears, and the field's wrap-around does the rest.

python
p = 2**31 - 1
NAMES = ["one", "N", "x", "y"] + [f"x{i}" for i in range(4)] + [f"y{i}" for i in range(4)]

def vec(**coeffs):
    return [coeffs.get(name, 0) % p for name in NAMES]

def factor_r1cs(check_bits=True):
    rows = []
    for v in "xy":
        if check_bits:                                       # the line a hurried author forgets
            rows += [(vec(**{f"{v}{i}": 1}),) * 3 for i in range(4)]
        rows.append((vec(**{f"{v}{i}": 2**i for i in range(4)}), vec(one=1), vec(**{v: 1})))
    rows.append((vec(x=1), vec(y=1), vec(N=1)))
    return rows

def satisfied(rows, z):
    dot = lambda r: sum(a * b for a, b in zip(r, z)) % p
    return all(dot(a) * dot(b) % p == dot(c) for a, b, c in rows)

# A malicious "witness" claiming that 2 divides 143: y = 2 and x = 143 / 2 in the field.
x_fake = 143 * pow(2, -1, p) % p
fake = [1, 143, x_fake, 2] + [x_fake, 0, 0, 0] + [0, 1, 0, 0]   # x0 is not a bit at all
print("x_fake =", x_fake, "  check: x_fake * 2 mod p =", x_fake * 2 % p)
for name, check_bits in [("sound", True), ("under-constrained", False)]:
    print(f"{name:>17} circuit accepts the fake witness: {satisfied(factor_r1cs(check_bits), fake)}")

# How many accepted "factorisations" of 143 does the buggy circuit allow with y < 16?
count = 0
for y in range(16):
    if y == 0:
        continue
    x = 143 * pow(y, -1, p) % p
    z = [1, 143, x, y] + [x, 0, 0, 0] + [(y >> i) & 1 for i in range(4)]
    count += satisfied(factor_r1cs(False), z)
print("values of y from 1 to 15 with an accepted fake witness:", count, "(the honest answers are 11 and 13)")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

The buggy circuit "proves" that 2×1073741895=1432 \times 1073741895 = 143, which is true in Fp\mathbb{F}_p and nonsense as a statement about factoring. Every yy from 1 to 15 now has an accepted partner.

Example— Real under-constrained bugs

  • Tornado Cash, 2019. In the MiMC hash template of the circomlib library, an output was assigned with = instead of assigned and constrained with <==, so the hash output was unconstrained and a prover could fake a Merkle root. The team discovered it, used it to move the deposits to a fixed contract before anyone else could, and disclosed it (Trail of Bits discussion).
  • Range checks without bit-length checks. A comparison gadget assumed its inputs had at most kk bits without enforcing it, so oversized field elements passed (an early version of the game Dark Forest, among others).
  • zkEVM arithmetic. An audit of Polygon's zkEVM found a division routine that did not constrain the remainder to be smaller than the divisor, so a prover could choose a wrong quotient.

These and dozens more are collected in 0xPARC's zk-bug-tracker, and the SoK by Chaliasos et al. (USENIX Security 2024) classified 141 vulnerabilities in SNARK systems found between 2018 and 2024, with circuit-layer bugs, under-constrained circuits above all, as the largest group.

The defences: write witness generation and constraints in a language where assigning without constraining is hard (Noir, or typed Rust APIs, rather than raw <-- in Circom); test circuits with negative tests that try malicious witnesses, not only valid ones; use static analysers such as Circomspect and solvers that check whether outputs are uniquely determined by inputs (Veridise's Picus, 0xPARC's Ecne); and, increasingly, formal verification (the frontier lesson).

Common misconceptionsH

Common misconceptions

Misconception

"If the cryptography is sound, the proof is sound." The proof certifies that the constraints are satisfied. If the constraints do not capture the intended computation, the proof is valid and the statement false. Most real SNARK failures are in the constraints or the Fiat–Shamir transcript, not in the elliptic curves.

Misconception

"A trusted setup means you must trust the organiser." A multi-party ceremony needs only one honest participant among all contributors, and you can be that participant. The residual risks are implementation bugs in the ceremony software and the parameter files, as Zcash's 2019 disclosure showed.

Misconception

"SNARK proofs are slow to verify because the computation is big." Verification is the cheap part: constant time for Groth16, polylogarithmic for STARKs. Proving is expensive, typically by factors of thousands or more over native execution.

Misconception

"Field arithmetic behaves like integer arithmetic." Numbers wrap around modulo pp, there is no "less than", and every nonzero element has an inverse, so x⋅y=Nx \cdot y = N has a solution for every nonzero yy. Any circuit that means integers must say so with range constraints.

Exercises

Exercises

1. Arithmetisation and SNARKs

Warm-upHuman

In "SNARK", what does the word argument tell you, as opposed to "proof"?

Choose one

2. Arithmetisation and SNARKs

CoreHuman

Write an R1CS for the statement "I know an 8-bit number xx with x3+x=yx^3 + x = y", where yy is public, using bits x0,…,x7x_0, \ldots, x_7 for the range check. Remember that additions and multiplications by constants are free inside each linear combination. What is the smallest number of constraints you need?

3. Arithmetisation and SNARKs

CoreHuman

Over F7\mathbb{F}_7, let ff be the unique polynomial of degree at most 2 with f(1)=4f(1) = 4, f(2)=0f(2) = 0 and f(3)=6f(3) = 6. What is f(4)f(4), as an integer from 0 to 6?

4. Arithmetisation and SNARKs

CoreHuman

After a KZG setup, a participant secretly kept the full secret τ\tau (because every other participant colluded with them). What can they do?

Choose one

5. Arithmetisation and SNARKs

CoreHuman

Which single constraints over Fp\mathbb{F}_p (for a large prime pp) force a variable bb to be 0 or 1? Select all that apply.

Choose all that apply

6. Arithmetisation and SNARKs

StretchHuman

In the lesson's PLONK example, the cheating table changed gate 2's left input from 7 to 8 and fixed gate 2's output to match. Every gate equation still holds. Why does the grand product ∏i(wi+βi+γ)/(wi+βσ(i)+γ)\prod_i (w_i + \beta i + \gamma)/(w_i + \beta\sigma(i) + \gamma) differ from 1?

Choose one

7. Arithmetisation and SNARKs

CoreComputational

Write r1cs_violations(A, B, C, z, p), which returns the sorted list of indices of the rows of an R1CS that the assignment z violates, that is the rows ii with (Ai⋅z)(Bi⋅z)≠Ci⋅z(modp)(A_i \cdot z)(B_i \cdot z) \neq C_i \cdot z \pmod p. A, B and C are lists of rows (lists of field elements); z is a list of field elements. The tests use the lesson's factoring circuit and random systems.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

8. Arithmetisation and SNARKs

StretchComputational

A KZG opening at a point zz needs the value y=f(z)y = f(z) and the quotient q(X)=(f(X)−y)/(X−z)q(X) = (f(X) - y)/(X - z). Write kzg_quotient(f, z, p), where f lists the coefficients of ff over Fp\mathbb{F}_p lowest degree first, returning (q, y) with q the coefficient list of the quotient (lowest first, of length len(f) - 1, so a constant polynomial gives []). Aim for O(deg⁡f)O(\deg f) operations. The tests check f(τ)−y=q(τ)(τ−z)f(\tau) - y = q(\tau)(\tau - z) at random τ\tau, the identity behind the KZG verification equation.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Further reading and resources