How Zero-Knowledge Proofs Work

A zero-knowledge proof convinces someone that a statement is true without revealing why it is true. It sounds paradoxical, but the smallest example needs only the elliptic curve math from the signatures post.

The idea, with no math

Imagine your friend is colorblind. You hold two balls, one red and one green, and they look identical to your friend. You claim they are different colors. How do you prove it without telling them which is which?

Play a game:

1. Your friend takes both balls, hides them behind their back, and either swaps them or doesn't.
2. They show you the balls and ask: "Did I swap them?"
3. You can see the colors, so you always answer correctly.

If the balls were really the same color, you would be guessing and be right half the time. Do ten rounds, and a liar gets all ten right with probability $1/1024$. After enough rounds your friend is convinced the balls differ, but they still can't say which is red.

That is a zero-knowledge proof:

• Your friend is convinced the claim is true: the balls really are different.
• A liar gets caught. Each round, cheating succeeds only by luck, and luck runs out.
• Your friend learns nothing else. They never find out which ball is red, and a recording of the game proves nothing to anyone else, because two people could stage the same rounds with a script they agreed on beforehand.

The shape of every proof in this post is the same as the game:

The rest of the post replaces the balls with a private key, and the guessing game with algebra. The secret is a number $d$, the commitment is a point on a curve, and the answer is a single equation that only someone who knows $d$ can satisfy.

What a proof must satisfy

• Completeness: an honest prover with a true statement convinces the verifier.
• Soundness: a prover with a false statement can't convince the verifier, except with negligible probability.
• Zero-knowledge: the verifier learns nothing beyond the fact that the statement is true.

A Schnorr proof of knowledge

The statement: "I know $d$ such that $Q = dG$." The prover wants to show this without revealing $d$.

1. Commit. The prover picks a random $k$ and sends $R = kG$.
2. Challenge. The verifier sends a random $e$.
3. Response. The prover sends $z = k + e d \pmod n$.
4. Check. The verifier accepts if:

It is correct because $zG = kG + e\, dG = R + eQ$.

Why it is sound

Suppose a prover can answer two different challenges $e \ne e'$ for the same commitment $R$, with responses $z$ and $z'$. Subtracting:

So anyone who can reliably pass the check must be able to produce $d$. This argument, called special soundness, is how security proofs show that passing means knowing. A prover who doesn't know $d$ can prepare an answer for one challenge in advance, but not for a random one.

Why it leaks nothing

The verifier sees a transcript $(R, e, z)$. Anyone can fake one without knowing $d$: pick $z$ and $e$ at random, then set:

This transcript passes the check, and it is distributed the same way as a real one. Since a simulator with no secret can produce transcripts the verifier can't tell apart from real ones, a real transcript can't contain information about $d$. The randomness of $k$ is what hides $d$, and this is why a repeated $k$ is fatal, as in the nonce reuse post.

Removing the verifier: Fiat-Shamir

An interactive proof needs the verifier online. Fiat-Shamir replaces the verifier's random challenge with a hash of everything that came before it:

Now the prover computes the whole proof $(R, z)$ alone, and anyone can check it later. With a message $m$ mixed in, this is a Schnorr signature, the same structure as EdDSA. A signature is a proof of knowledge of the private key, bound to a message.

The hash must include the statement ($Q$) and the commitment ($R$). Leaving out parts of the statement is a known source of real attacks.

From one statement to any program

Proving knowledge of a discrete log is one fixed statement. SNARKs and STARKs prove arbitrary computations, and they follow the same recipe at a larger scale:

1. Arithmetize. Turn the program into a set of polynomial constraints over a finite field. "The program ran correctly" becomes "these polynomials satisfy these equations".
2. Commit. The prover commits to the polynomials with a polynomial commitment scheme, such as KZG or FRI. A commitment is short and binds the prover to a fixed polynomial.
3. Check at a random point. Two different polynomials of degree $d$ agree on at most $d$ points, so if they agree at a random point out of a huge field, they are almost certainly equal (the Schwartz-Zippel lemma). The verifier checks the constraints at one random point instead of everywhere.
4. Make it non-interactive. The random point comes from Fiat-Shamir, as above.

The verifier does a small amount of work whatever the size of the original computation, which is what makes rollups possible: one short proof stands for thousands of transactions.

Zero-knowledge comes from adding random blinding terms to the polynomials, the same role $k$ plays in the Schnorr proof.

SNARKs and STARKs

• SNARKs have very small proofs and fast verification. Many need a trusted setup, a one-time ceremony whose secret must be destroyed, and most rely on elliptic curve pairings.
• STARKs need no trusted setup and rely only on hash functions, which is also why they are believed to resist quantum computers. The price is larger proofs.

The takeaway

A zero-knowledge proof is a commitment, a random challenge, and a response that can be verified only if the prover knows the secret. A simulator showing that the transcript could be faked is the argument that nothing leaks. Everything else, including circuits and polynomial commitments, is machinery for applying that pattern to more complex statements.