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.
SNARKs and constraint systems
Definition— SNARK
A SNARK for a relation (public statement , secret witness ) 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 , and verification takes time polylogarithmic in it plus time linear in ;
- 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 (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 .
Definition— arithmetic circuit
An arithmetic circuit over 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 matrices , , over . A vector with , containing the public inputs and the witness, satisfies it if
where is the entrywise product. Each of the 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 is a variable with the constraint , whose only solutions in a field are 0 and 1. A comparison such as "" has no direct field meaning (fields are not ordered), so it is done by decomposing 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.
Building an R1CS by hand
Our statement: "I know two 4-bit numbers and with ", for a public . For this is a claim to know a factorisation of 143 into two small factors. The variables are and the constraints are:
- and for : each is a bit (8 constraints);
- , and the same for : the bits represent and , so both are below 16 (2 constraints);
- (1 constraint).
Since , the product is below 256, far smaller than , so the field equation is the integer equation. The program builds the three matrices row by row, prints one row, and checks three assignments.
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))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.
From many constraints to one polynomial identity
Checking 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 to the point . For each variable , let be the polynomial of degree less than with for every row , found by Lagrange interpolation:
and define and in the same way. For an assignment , set , and similarly and . Then is exactly the left side minus the right side of constraint , so
where is the vanishing polynomial. The prover can exhibit the quotient with , and by Schwartz–Zippel it suffices to check this identity at one random point : if it is false, the two sides are different polynomials of degree at most , which agree at no more than points.
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)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 at a point the prover cannot anticipate, using values the prover has bound itself to in advance. That is what polynomial commitments provide.
Polynomial commitments and KZG
Definition— polynomial commitment scheme
A polynomial commitment scheme lets a prover publish a short commitment to a polynomial of degree less than , and later, for any point the verifier names, send a value with a short opening proof that . It is binding (no efficient prover can open 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 between groups of prime order on a pairing-friendly elliptic curve (BN254 or BLS12-381) that is bilinear, . A pairing lets the verifier check one multiplication "in the exponent" without knowing the exponents (see elliptic curves for the geometry behind it).
- Setup. Someone picks a secret and publishes and . Then must be destroyed.
- Commit. For , the prover computes : a multi-scalar multiplication (MSM) over the public powers. The commitment is one group element, whatever the degree.
- Open at . If , then divides ; the prover computes the quotient and sends , again one group element.
- Verify. Check , which says in the exponent.
If , no polynomial makes that identity hold, and producing a fake is believed infeasible (under the "-strong Diffie–Hellman" assumption) as long as nobody knows . 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).
Groth16 and PLONK
Groth16 (Jens Groth, 2016) compiles a QAP into a proof of exactly three group elements, and , 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 , 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 gas for 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 and fixed selector values, with the gate equation Selectors make an addition gate and 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 be a permutation that cycles through each group of cells that must be equal. Then for random challenges , holds when the values respect the wiring, and fails with high probability otherwise (two different multisets give different polynomials in and ). PLONK proves this product with a running-product polynomial, committed and checked at a random point.
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)}")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.
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.
The commitment scheme determines most of a SNARK's engineering profile:
| Commitment | Setup | Proof size | Verifier | Assumption | Post-quantum? |
|---|---|---|---|---|---|
| KZG | trusted (powers of tau) | constant, about 48 bytes per opening | constant: 2 pairings | pairings, -SDH | no |
| IPA / Bulletproofs | transparent | logarithmic | linear in degree | discrete log | no |
| FRI (Merkle trees of codewords) | transparent | polylogarithmic, tens to hundreds of KB per proof | polylogarithmic, hashes only | collision-resistant hash | plausibly yes |
| Multilinear schemes (Hyrax, Dory, Ligero/Brakedown-style, Basefold, WHIR) | mostly transparent | from logarithmic to square-root | varies | varies | some |
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):
| System | Proof size | Verify | Prover dominated by | Setup |
|---|---|---|---|---|
| Groth16 | 128–192 bytes | 3–4 pairings, about 1 ms | MSMs, FFTs | per circuit |
| PLONK + KZG | about 0.5–1 KB | 2 pairings | MSMs, FFTs | universal |
| STARK (FRI) | about 50–200 KB | hashes, a few ms | FFTs, hashing | none |
| Bulletproofs | about 1–2 KB | linear in circuit size | MSMs | none |
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.
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 , 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 , the "bits" can be any field elements, the range check disappears, and the field's wrap-around does the rest.
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)")The buggy circuit "proves" that , which is true in and nonsense as a statement about factoring. Every 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 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 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 , there is no "less than", and every nonzero element has an inverse, so has a solution for every nonzero . Any circuit that means integers must say so with range constraints.
Exercises
1. Arithmetisation and SNARKs
Warm-upHumanIn "SNARK", what does the word argument tell you, as opposed to "proof"?
2. Arithmetisation and SNARKs
CoreHumanWrite an R1CS for the statement "I know an 8-bit number with ", where is public, using bits 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
CoreHumanOver , let be the unique polynomial of degree at most 2 with , and . What is , as an integer from 0 to 6?
4. Arithmetisation and SNARKs
CoreHumanAfter a KZG setup, a participant secretly kept the full secret (because every other participant colluded with them). What can they do?
5. Arithmetisation and SNARKs
CoreHumanWhich single constraints over (for a large prime ) force a variable to be 0 or 1? Select all that apply.
6. Arithmetisation and SNARKs
StretchHumanIn 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 differ from 1?
7. Arithmetisation and SNARKs
CoreComputationalWrite 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 with . 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.
8. Arithmetisation and SNARKs
StretchComputationalA KZG opening at a point needs the value and the quotient . Write kzg_quotient(f, z, p), where f lists the coefficients of over 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 operations. The tests check at random , the identity behind the KZG verification equation.
Further reading and resources
- Proofs, Arguments, and Zero-Knowledge · Justin ThalerChapters on front ends, polynomial commitments, Groth16 and PLONK-style arguments.
- Quadratic span programs and succinct NIZKs without PCPs · Rosario Gennaro, Craig Gentry, Bryan Parno and Mariana Raykova · 2013Introduced quadratic arithmetic programs (QAPs).
- Pinocchio: nearly practical verifiable computation · Bryan Parno, Jon Howell, Craig Gentry and Mariana Raykova · 2013
- On the size of pairing-based non-interactive arguments · Jens Groth · 2016Groth16.
- Constant-size commitments to polynomials and their applications · Aniket Kate, Gregory M. Zaverucha and Ian Goldberg · 2010KZG commitments.
- PLONK: permutations over Lagrange-bases for oecumenical noninteractive arguments of knowledge · Ariel Gabizon, Zachary J. Williamson and Oana Ciobotaru · 2019
- Marlin: preprocessing zkSNARKs with universal and updatable SRS · Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Psi Vesely and Nicholas Ward · 2020
- Transparent SNARKs from DARK compilers · Benedikt Bünz, Ben Fisch and Alan Szepieniec · 2020Together with Marlin, the source of the "polynomial IOP + polynomial commitment" framing.
- Bulletproofs: short proofs for confidential transactions and more · Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille and Greg Maxwell · 2018
- KZG ceremony wrap-up · Ethereum Foundation · 2024The 2023 ceremony for EIP-4844, with 141,416 contributions.
- SoK: what don't we know? Understanding security vulnerabilities in SNARKs · Stefanos Chaliasos, Jens Ernstberger, David Theodore, David Wong, Mohammad Jahanara and Benjamin Livshits · 2024
- zk-bug-tracker · 0xPARCA community list of real bugs in zero-knowledge circuits and proof systems.