What is a zero-knowledge proof?

Build the intuition for a zero-knowledge proof: convincing a verifier that a statement is true while revealing nothing beyond its truth, the roles of prover and verifier, and how interactive proofs become non-interactive via Fiat–Shamir.

Track

Engineering

Module

4 · Zero-Knowledge Proofs

Prerequisites

Hash functions · Digital signatures

Imagine you want to convince someone that you know a password without ever typing it, or that a bank transfer is valid without revealing the balances. A zero-knowledge proof (ZKP) is a protocol that does exactly this: one party (the prover) persuades another party (the verifier) that a statement is true, while the verifier learns nothing except the fact that it is true. In particular the verifier learns nothing that would let them reproduce the proof or recover the secret that made the statement true.

The classic intuition is a cave shaped like a ring with a locked door splitting the far end. A prover claims to know the door's secret word. The verifier waits at the entrance, the prover walks into one of the two tunnels, and then the verifier shouts which side they want the prover to emerge from. A prover who truly knows the word can always comply; a prover who is bluffing can only comply half the time — by luck of having picked the right tunnel. Repeat many times and the bluffer's odds of surviving every round collapse toward zero, yet the verifier never hears the word.

A zero-knowledge proof is defined relative to a statement — a claim of the form "x belongs to language L", for example "this committed value is in a valid range" or "I know a private key for this public key". The prover tries to make the verifier accept; a sound protocol makes the verifier reject when the claim is false. The formal notion of an interactive zero-knowledge proof was introduced by Goldwasser, Micali and Rackoff in "The Knowledge Complexity of Interactive Proof Systems" (1985), which is the canonical reference for the three defining properties.

Prover

The party that holds whatever makes the statement true (the witness) and wants to convince the verifier, without handing over that witness.

Verifier

The party that checks the proof and outputs accept or reject. In a true ZKP the verifier learns only this bit — never the witness.

Simulator

A thought-experiment algorithm that, given only the (true) statement and no witness, produces transcripts indistinguishable from real ones. If such a simulator exists, the real transcript cannot have leaked anything — this is how zero-knowledge is formally defined.

An interactive proof is a conversation between a prover P (unbounded or with a witness) and a probabilistic polynomial-time verifier V. The three properties below, for a statement x in language L with witness w, are what distinguish a zero-knowledge proof from an ordinary argument. The notation is schematic — read it as structure, not as a formula to compute.

Interactive ZK proof (schematic; after Goldwasser–Micali–Rackoff 1985)
Setting: statement x, witness w, security parameter n
  Prover P(x, w)  <-- messages -->  Verifier V(x)
  at the end V outputs  accept / reject

Completeness:
  if x is true (x in L) and both are honest
     Pr[ V accepts ]  = 1          (or >= 1 - negligible(n))

Soundness:
  if x is false (x not in L), then for ANY cheating prover P*
     Pr[ V accepts ]  <= epsilon   (a small "soundness error")
  repeating k independent rounds drives epsilon -> epsilon^k

Zero-knowledge:
  there exists a simulator S such that, for the true x,
     S(x)            ~=   transcript of real(P(x,w) <-> V)
  (the two distributions are indistinguishable)
  => the verifier could have produced the transcript alone,
     so it learned nothing beyond "x is true"

The cave example is a 1-round protocol with soundness error 1/2 (a bluffer guesses the right tunnel half the time). Running it k times makes the cheating probability (1/2)^k — exponentially small. The simulator condition is the subtle one: because a simulator with no witness can fake a convincing transcript for a true statement, a real transcript provably carries no extractable knowledge.

A large family of ZK protocols (so-called Sigma protocols) follow a three-move "commit – challenge – respond" shape:

1. 1Commit: the prover sends a commitment that locks in a random choice without revealing it (see Module 4 on commitments).
2. 2Challenge: the verifier sends a fresh random challenge that the prover could not have predicted.
3. 3Respond: the prover answers in a way that is only consistent if they really hold the witness; the verifier checks the response against the commitment and challenge.
4. 4Repeat (interactive version) enough rounds that a bluffer's cumulative success probability becomes negligible.
5. 5Fiat–Shamir (non-interactive version): replace the verifier's random challenge with the hash of the statement and the commitment, so the prover generates the challenge itself from a hash it cannot steer — collapsing the conversation into a single proof anyone can check later.

synthetic — Schnorr-style proof of knowing a discrete log
Public:  group with generator g;  public key  Y = g^x
Secret (witness):  x      # the prover claims "I know x"

Interactive:
  1. Prover picks random r, sends  T = g^r          (commit)
  2. Verifier sends random challenge  c             (challenge)
  3. Prover sends  s = r + c*x                       (respond)
  4. Verifier accepts iff  g^s  ==  T * Y^c

Non-interactive (Fiat-Shamir):
  c = H( g, Y, T )     # prover derives the challenge by hashing
  proof = (T, s)       # anyone can recompute c and check

The verifier ends convinced the prover knows x, yet never sees x. The simulator argument holds: given a true Y, one can pick s and c first and solve for a matching T, producing a transcript that looks real — so a real transcript reveals nothing about x. This is a proof about a single secret; later modules generalize the same shape to arbitrary computations.

In an agent system, a worker often needs to prove it is entitled to act without exposing the credential that entitles it. A zero-knowledge proof lets an agent demonstrate "I hold a valid, unexpired delegation for this scope" to a verifier that never sees the delegation token itself — reducing the blast radius if the verifier is compromised, and enabling cross-organization checks where no shared secret exists.

Because Fiat–Shamir makes proofs non-interactive, an agent can attach a proof to a request like a signature: the verifier checks it offline, with no back-and-forth. This is the foundation for the delegation case study in Module 5, where authority is proven rather than revealed.

• ▸Zero-knowledge proves a statement, not good judgement: a valid proof that an agent is authorized says nothing about whether the authorized action is wise or safe.
• ▸Fiat–Shamir is only sound in the random-oracle model, and only if the hash binds every public input; "weak" implementations that skip inputs have been broken in practice.
• ▸Soundness is usually computational and statistical, not absolute — a single round of the cave protocol accepts a bluffer half the time; security comes from repetition or from well-chosen parameters.
• ▸Different proving systems achieve these properties under very different assumptions and costs (proof size, verifier time, setup, post-quantum posture). "It is a ZKP" does not mean two systems are interchangeable — a theme developed in the proving-systems comparison.
• ▸Implementation bugs, not the math, are the usual failure: bad randomness, missing domain separation, or an incorrectly constrained statement can silently void soundness or zero-knowledge.

Expected direction: Watching the prover choose a tunnel before issuing the challenge lets the verifier learn information correlated with the witness (and build transcripts a simulator could not fake without the secret), so the simulator argument fails and the protocol leaks. It breaks the assumption that the challenge is independent of the prover's secret choice — the challenge must be a fresh, unpredictable coin issued after the commitment, not a reaction to observed behavior.

What exactly does the verifier learn from a sound zero-knowledge proof of a true statement?

Only the single fact that the statement is true — not the witness, and nothing that would let them convince a third party or reproduce the secret.

What is the role of the simulator in the definition of zero-knowledge?

It shows that a convincing transcript can be produced for a true statement WITHOUT the witness; since the simulated and real transcripts are indistinguishable, the real one provably leaked no extractable knowledge.

What does the Fiat–Shamir transform do, and what is the main pitfall?

It replaces the verifier's random challenge with a hash of the statement and prior messages, making the proof non-interactive. The pitfall ("weak Fiat–Shamir") is failing to hash all public inputs, which can break soundness.