What a Zero-Knowledge Proof Actually Proves

Every explanation of zero-knowledge cryptography eventually reaches for the cave. Two paths, a locked door, a friend who waits outside. It is a good story and it teaches exactly one idea, which is that you can be convinced of something without being shown it. Then the reader opens a specification and finds R1CS, trusted setups, polynomial commitments and a recursion argument, and the cave is no help at all.

This piece is the bridge. Four diagrams, each one a thing you have to hold in your head before the next one makes sense, and no claim that is not checkable.

The property, stated precisely

A proof system is a conversation between a prover, who claims something, and a verifier, who decides whether to believe it. Goldwasser, Micali and Rackoff formalised the interesting case in 1985: a proof can be zero-knowledge, meaning the verifier ends the conversation convinced and knowing nothing beyond the fact that the claim is true.

Three properties define the system, and they are not interchangeable.

Completeness. An honest prover with a true statement convinces an honest verifier, perfectly in some systems, with overwhelming probability in others. It is the requirement that the system work at all.

Soundness. A prover with a false statement cannot convince the verifier, except with negligible probability. This is the property that costs the most to get right, and it is the one that fails catastrophically rather than gracefully: a soundness bug does not make a system slower, it makes every proof meaningless.

Zero-knowledge. An efficient verifier learns nothing it could not have computed for itself, beyond the fact that the statement is true. This is made precise by a simulator: an algorithm that produces a transcript indistinguishable from a real conversation, without knowing the secret. If a fake transcript is indistinguishable from a real one, the real one cannot have carried the secret. That is the entire argument, and it is why the definition is about what an adversary can distinguish rather than about what it can see.

The word most often mistranslated in coverage is knowledge. A proof of knowledge does not merely establish that a satisfying input exists somewhere in the universe; it establishes that this prover has one. The formal device is an extractor, a hypothetical algorithm that could pull the secret out of a prover that succeeds too often. If no such extractor could exist, the prover is not proving knowledge of anything.

Interactive protocols ran a conversation: the prover commits, the verifier challenges, the prover responds. Where the verifier's challenges are simply public randomness, a public-coin protocol, the Fiat-Shamir transform collapses that conversation into a single message by replacing each challenge with a hash of everything said so far. This is what makes a proof postable to a blockchain, where there is no verifier sitting there to argue with, and it is also where a family of real vulnerabilities lives. The hash has to bind everything the challenge depends on: the statement, the public parameters and the commitment. An implementation that leaves any of them out lets a prover grind until it likes the challenge it gets, and the weak Fiat-Shamir bugs found in deployed libraries are all versions of that one omission.

From a program to a system of equations

The proof systems in production do not verify programs. They verify an arithmetised relation over a finite field, and getting from one to the other is most of the engineering. (Other constructions target Boolean circuits or machine execution directly; the arithmetic route is the one deployed chains took.)

The program is first flattened into an arithmetic circuit: a graph of additions and multiplications, with the private inputs at the top and a single output at the bottom that must equal the claimed result. Every branch is compiled away, both sides are computed and selected between, which is why a loop with a data-dependent bound is expensive in a way that has no equivalent in ordinary programming. There is no early exit in a circuit.

The circuit is then written as a system of constraints. In the widely used R1CS form, every constraint has the shape (A · z) × (B · z) = (C · z), where z is the vector of all the wire values including the witness. Satisfying the system is running the program correctly, and this is the sleight of hand at the centre of the whole field: the prover is not proving that it ran a program, it is proving that it knows a vector satisfying a system of equations that only a correct run could produce.

For an R1CS circuit the constraint count is the honest first-order measure of cost, not lines of code, not gas. It is a proxy rather than the whole story: field choice, circuit structure, witness generation and memory all move the real number.

The two families, and what actually separates them

Coverage tends to present SNARKs and STARKs as competitors. They are better understood as different answers to one question: where does the verifier's confidence come from?

SNARKs, succinct non-interactive arguments of knowledge, are a family, not a single design. The ones most deployed on chains today, Groth16 and the KZG-based PLONK systems, buy very small proofs and very fast verification by using elliptic-curve pairings, and pay for it with a trusted setup. Transparent SNARKs exist and need no ceremony; the ceremony is a property of those constructions rather than of the acronym. The setup produces public parameters from secret randomness that must then be destroyed. If it survives, its holder can forge proofs for false statements, undetectably. This is not a theoretical caveat; it is the reason ceremonies exist, and why they are run with hundreds of participants where a single honest one suffices to make the result safe.

Groth16, long the workhorse of on-chain verification, requires a trusted setup, and its setup is circuit-specific: change the program, run a new ceremony. PLONK and its descendants improved on this with a universal setup, one ceremony, reusable across circuits up to a size bound, which is why newer systems tend to be built on that line.

STARKs are transparent: no trusted setup at all, and transparency is not theirs alone: it is the axis, not the family, that matters. Their security rests on hash functions rather than on the hardness of discrete logarithms, which also makes them plausibly post-quantum, and their prover cost grows more gently on large computations. The price is proof size, kilobytes where a Groth16 proof is a few hundred bytes, which matters a great deal when every proof is stored on a chain forever.

There is no ranking here. A rollup posting one proof per block and a privacy protocol posting one proof per transaction are answering different questions about the same trade.

What this buys a blockchain

On a public chain, every full validating node re-executes every transaction for itself. That is where the integrity comes from, light clients trust the result rather than recomputing it, and it is also why the ledger is a permanent public record of who did what.

Zero-knowledge proofs break that coupling, in two directions that are worth keeping separate because they are constantly conflated.

Scaling. Verification can be much cheaper than execution. A rollup executes thousands of transactions off-chain and posts one proof; the chain checks the proof instead of the work. Nothing here is private, the data is usually published in full, and calling these systems "ZK rollups" is a misnomer that has stuck. The property being used is succinctness, not zero-knowledge.

Privacy. The witness never crosses the boundary. A user proves that a transaction is valid, inputs exist, are unspent, balance, without revealing which inputs, or how much. This is the property Zcash shipped in 2016 and the one Midnight is built around.

Midnight's design point is that neither total transparency nor total opacity is what regulated business can use. Its model is selective disclosure: the ledger keeps what must be public public, and lets a participant prove a specific fact to a specific counterparty, that a party is not sanctioned, that a balance clears a threshold, that a credential is valid, without publishing the underlying data. Contracts are written in Compact, a language whose whole design is deciding which state is public and which is proved, and the chain runs as a Cardano partner chain with its own tokens: NIGHT, and DUST, which is generated by holding NIGHT and consumed to pay for transactions.

Where the sharp edges are

Three, in the order that they bite.

The circuit is the trust boundary. A proof establishes that some constraint system is satisfied. If the constraint system does not say what the developer thought it said, an under-constrained circuit, the classic bug of the field, the proof is perfectly valid and proves nothing useful. Auditing here means reading constraints, not code.

Proving is expensive and verification is not. The asymmetry is the point, but it moves cost to whoever generates proofs, which shapes the architecture: proving on a phone is a different design from proving in a data centre, and "who proves" is a decentralisation question, not an implementation detail.

Cryptographic agility is unusually hard. Pairing-based systems rest on assumptions a cryptographically relevant quantum computer would break. Hash-based systems mostly do not. Migrating a live chain's proof system is not a library upgrade; it is a change to the rules by which everything already on the ledger was accepted.

What to hold on to

Zero-knowledge cryptography is not a privacy feature bolted onto a blockchain. It is a different answer to the question every ledger has to answer, how do you know this is true? that replaces "everyone re-executed it and agreed" with "here is a proof, check it yourself".

The cave was right about the destination. It just never mentioned that getting there means turning your program into polynomials and being extremely careful about what your constraints actually say.