Zero-Knowledge Proofs, in depth: Schnorr by hand, Fiat-Shamir, circuits, SNARKs versus STARKs and how they break

What zero-knowledge means

A proof system for a statement is zero-knowledge if it has three properties. Completeness: an honest prover with a true statement convinces an honest verifier. Soundness: a cheating prover with a false statement convinces the verifier only with negligible probability. Zero knowledge: whatever the verifier sees, it could have generated by itself without the secret. That last property is defined with a simulator, an algorithm that produces transcripts indistinguishable from real ones while knowing only the public statement. If fake conversations look exactly like real ones, the real ones cannot carry information about the secret.

Two refinements matter in practice. A proof of knowledge is stronger than a proof of truth: it shows the prover actually knows a witness, formalised by an extractor that can pull the witness out of any prover who succeeds often enough. And most deployed systems are arguments, sound only against provers with bounded computation, which is why their security rests on assumptions such as the hardness of discrete logarithms or collision resistance of a hash function.

Worked example: Schnorr by hand

Take a prime p = 23 and a generator g = 2 of a subgroup of prime order q = 11 (you can check 2^11 mod 23 = 1). The prover's secret is x = 7 and the public key is y = g^x mod p = 128 mod 23 = 13. The statement is: I know x such that 2^x = 13 (mod 23). The protocol has three moves.

1. Commit. The prover picks a fresh random r = 5 and sends t = g^r mod p = 32 mod 23 = 9.
2. Challenge. The verifier picks a random c = 4 from 0..q-1 and sends it.
3. Response. The prover sends s = r + c*x mod q = 5 + 28 mod 11 = 0.

The verifier checks g^s = t * y^c (mod p). Left side: 2^0 = 1. Right side: 13^2 = 169 = 8 (mod 23), so 13^4 = 64 = 18, and 9 * 18 = 162 = 1 (mod 23). Both sides are 1, so the proof is accepted. Completeness follows from algebra: g^(r + c*x) = g^r * (g^x)^c.

Why it is sound. Suppose a prover could answer two different challenges c1 and c2 for the same commitment t. Dividing the two verification equations gives g^(s1 - s2) = y^(c1 - c2), so x = (s1 - s2) / (c1 - c2) mod q. This property, called special soundness, is the extractor: anyone who can answer more than one challenge must know x. A cheater who does not know it can prepare for only one challenge and is caught with probability 1 - 1/q, which is overwhelming for a real 256-bit group.

Why it is zero-knowledge. The simulator picks s and c at random first, then computes t = g^s * y^(-c). The triple (t, c, s) verifies and has exactly the same distribution as a real transcript with an honest verifier. The verifier learns nothing it could not have produced alone.

The same equations break if you are careless. Reuse r for two different challenges and you have just handed the verifier the two transcripts the extractor needs, and the secret with them. That is the same arithmetic that leaked private keys from ECDSA signers with repeated nonces.

Non-interactive proofs with Fiat-Shamir

An interactive protocol needs the verifier online. The Fiat-Shamir transform removes it: the prover computes the challenge as a hash of everything the verifier would have seen so far. Because the hash output is unpredictable, the prover cannot choose t to fit a known challenge. Applied to Schnorr with a message included in the hash, this is exactly the Schnorr signature scheme.

import hashlib, secrets

# Teaching code: (g, p, q) is a prime-order subgroup; use a vetted library and curve in practice.
def H(*parts):
    h = hashlib.sha256()
    for part in parts:
        b = str(part).encode()
        h.update(len(b).to_bytes(4, "big") + b)   # length-prefix to avoid ambiguity
    return int.from_bytes(h.digest(), "big")

def prove(g, p, q, x, context):
    y = pow(g, x, p)
    r = secrets.randbelow(q)                   # fresh per proof, never reused
    t = pow(g, r, p)
    c = H("schnorr-v1", g, p, q, y, t, context) % q   # bind EVERYTHING public
    s = (r + c * x) % q
    return y, (t, s)

def verify(g, p, q, y, proof, context):
    t, s = proof
    c = H("schnorr-v1", g, p, q, y, t, context) % q
    return pow(g, s, p) == (t * pow(y, c, p)) % p

The comment on the challenge line is the most important line in the file. If the hash omits the public key, the group parameters or the statement, a prover can pick those after seeing the challenge and forge proofs for statements it cannot prove. In 2022 researchers disclosed this weak Fiat-Shamir pattern, nicknamed Frozen Heart, in several production proof-system implementations. The rule is simple: hash a domain-separation tag, the full statement and every prover message, with unambiguous encoding. Do not use the toy parameters above in real code; use a library and a standard curve.

From programs to circuits

Schnorr proves one specific algebraic fact. General-purpose systems prove that a program ran correctly. To do that, the program is compiled into arithmetic constraints over a large prime field. Every value becomes a field element and every step becomes an equation. A common target is a rank-1 constraint system (R1CS), where each constraint has the form (A.z) * (B.z) = (C.z) for a vector z holding 1, the public inputs and all intermediate values.

Take the statement: I know x such that x^3 + x + 5 = 35. Flatten it into steps that each contain at most one multiplication:

v1  = x * x          # constraint 1: x  * x  = v1
v2  = v1 * x         # constraint 2: v1 * x  = v2
out = v2 + x + 5     # constraint 3: (v2 + x + 5) * 1 = out

witness z = [1, out=35, x=3, v1=9, v2=27]
check:  3*3 = 9,  9*3 = 27,  (27 + 3 + 5)*1 = 35

The prover knows the full witness; the verifier knows only out = 35. A proof system then encodes all constraints as polynomials and lets the prover show they hold at once. The usual trick is to commit to polynomials built from the witness and have the verifier check an identity at a random point: two different low-degree polynomials agree at a random point of a huge field with negligible probability (the Schwartz-Zippel lemma), so one evaluation stands in for millions of constraint checks. That is where the succinctness of a SNARK comes from.

Notice what was not written: nothing forces x to be small, an integer, or anything other than a field element. If the application assumed x was a 32-bit amount, the circuit must say so with explicit range constraints. Missing constraints are the dominant class of real bugs.

The proving pipeline

In engineering terms the expensive parts are on the prover. Committing to polynomials means large multi-scalar multiplications over elliptic-curve points, and moving between coefficient and evaluation form means number-theoretic transforms, the finite-field cousin of the fast Fourier transform. Proving is commonly several orders of magnitude slower than running the computation directly, and memory grows with circuit size, which is why provers are often run on GPUs and why circuit size is the number to optimise. Verification, by contrast, is cheap: milliseconds, and in some systems constant regardless of the computation.

Proof systems compared

The setup column is the biggest operational difference. A trusted setup produces structured reference parameters from secret randomness; anyone who keeps that randomness, the so-called toxic waste, can forge proofs. Multi-party ceremonies reduce the risk to needing just one honest participant. Groth16 needs a new ceremony per circuit, so every circuit change means another ceremony. PLONK-style universal setups are made once for all circuits up to a size bound. STARKs avoid the problem by using only hash-based commitments, paying for it in larger proofs. Treat the figures as orders of magnitude; exact sizes depend on the curve, the field, the hash and the parameters chosen.

The Merkle trees behind STARK commitments and proof-of-reserves schemes are explained in Merkle trees.

Where ZK is used

• Validity rollups. An off-chain operator executes many transactions and posts a succinct proof that the new state root follows from the old one. The chain verifies one proof instead of re-executing everything. Here the goal is mostly succinctness; the data is often public.
• Private credentials. A holder proves a predicate over a signed credential, such as age at least eighteen or residence in a country, without revealing other attributes. Selective disclosure and unlinkability between presentations are the goals.
• Proof of reserves. Customer balances are committed in a Merkle sum tree; a proof shows the total is covered and each customer can check their own leaf, with range proofs preventing negative balances from hiding liabilities.
• Verifiable computation and ML inference. Proving that a specific model produced an output is an active research area. Today it is practical for small models; costs for large networks remain high, so evaluate claims with measured prover times.

Failure modes

Notice that the cryptography itself is rarely the weak point. Proof systems fail where the circuit does not express the intended statement, where the transcript is not bound to it, or where keys and encodings drift between components. Treat circuits like smart contracts: small, reviewed, tested adversarially.

Trade-offs

Choose by constraint. If proofs must be tiny and cheap to verify, for example on a blockchain where every byte and operation costs money, pairing-based SNARKs win, and a universal setup is usually the better operational choice than per-circuit Groth16 unless proof size is critical. If you cannot accept any trusted setup or need a plausible post-quantum story, use a STARK and budget for larger proofs, sometimes wrapping a STARK inside a SNARK to compress it. If you only need range proofs or small statements with no setup, Bulletproofs are simple and well understood.

Also ask whether you need zero knowledge at all. Many systems use SNARKs only for succinctness, with public data. Others need privacy but could get it from simpler tools: commitments, signatures with selective disclosure, or a trusted execution environment, each with its own trust model. General ZK is powerful, but proving costs, circuit audits and key management are real and ongoing. The complexity background for why verifying is easier than finding a witness is in NP-completeness.

What to do next

1. Implement the Schnorr protocol above with toy numbers, then break it by reusing r and extracting x.
2. Remove the public key from the Fiat-Shamir hash and write a forgery; then fix it.
3. Write the x^3 + x + 5 circuit in a circuit language such as Circom or a Rust proving framework and generate a proof.
4. Add a deliberately missing constraint and write a test that proves a false statement with it.
5. Pick a proof system by writing down your limits on proof size, verifier cost, setup trust and prover hardware.
6. Before production, get the circuit audited and pin the verifying key hash everywhere it is checked.