At the door of a nightclub there is a bouncer with two questions: how old are you, and how can you prove it. The usual answer is to pull out your ID and show it, which also reveals your name, your address and your exact date of birth: far more information than the single question “are you an adult?” needs. For some years now there has been a branch of cryptography that answers exactly that —yes, I am of age— without revealing anything else. It is called a zero-knowledge proof, a proof that convinces whoever receives it that you know something, without revealing what it is that you know, and it is one of the most promising mathematical tools in computing: blockchains, voting systems and identity protocols already use it, and behind it lie circuits, polynomials and elliptic curves.
The three properties of a proof that tells nothing
A zero-knowledge proof is a protocol between two parties: a prover, who claims to know a secret, and a verifier, who must be convinced without learning the secret. The mathematical formalization, the work of Shafi Goldwasser, Silvio Micali and Charles Rackoff in 1985, demands three properties: completeness, soundness and zero knowledge.
Completeness means that if the prover knows the secret, they always convince the verifier. Soundness means that if they do not know it, they can only cheat with negligible probability. And “zero knowledge” imposes the most counterintuitive part: the verifier finishes the protocol without obtaining a single bit about the secret. The trap is in the word “zero”: the verifier learns nothing they did not know before starting, except that the claim is true.
Ali Baba’s cave, the thought experiment
The intuition is explained by Jean-Jacques Quisquater’s parable of Ali Baba’s cave. Imagine a circular cave with two entrances and, at the far end, a door that only opens with a magic word. The protagonist, Peggy, wants to prove to Victor that she knows the word without uttering it. Peggy enters through one of the two mouths at random; Victor, from outside, shouts which one she must exit through. If Peggy knows the word, she can open the door and always leave through the requested path; if she does not, she can only guess right by chance, with probability 1/2. Repeating the experiment 20 times, the probability that an impostor survives the whole session is (1/2)^20, less than one in a million.
This is an interactive proof: prover and verifier talk in several rounds, and the verifier’s faith grows with each one. It is elegant but impractical: who would run 20 rounds of questions against a server every time they want to authenticate?
The Fiat-Shamir trick: the interview becomes paper
In 1986, Amos Fiat and Adi Shamir found out how to remove the interaction. The idea is to replace the verifier’s randomness with something the prover cannot predict: the output of a hash function, a cryptographic function that turns data of any size into a fixed-length, unpredictable fingerprint. The prover produces their offer, hashes the transcript and uses that hash as the “question”. Since they cannot predict the hash before fixing their offer, the proof itself mimics the role of the verifier. The result is a non-interactive proof: a single message that anyone can verify at any time, as many times as they want. This is the famous Fiat-Shamir heuristic, the foundation of today’s SNARKs.
The circuit: turning “I know the password” into equations
The magic would not be complete without a way to represent knowledge as mathematics. The first step is compiling the claim (“I know a number x such that H(x) = y”, for instance, or “I am over 18”) into an arithmetic circuit: a graph of gates that add and multiply numbers instead of bits. The operations are not done with real numbers but inside a finite field, a set of numbers with its own addition and multiplication rules where everything is reduced modulo a prime; this keeps the arithmetic exact, with no rounding.
The circuit is then flattened into a rank-1 constraint system (R1CS): hundreds of thousands of equations of the form A × B = C. The prover’s secret, the witness, is an assignment of values that satisfies all the equations at once. Proving knowledge of a valid witness is, literally, proving that a solution to that system of equations exists without showing it.
A polynomial that condenses a thousand equations
Checking hundreds of thousands of constraints one by one would cost as much as rerunning the computation. Hence the second trick: condensing all the constraints into a single polynomial. Thanks to the Schwartz-Zippel lemma, two different polynomials agree at very few points; if the prover commits to a polynomial P and the verifier evaluates it at a random point, a correct value guarantees with overwhelming probability that P is the right polynomial at every point.
The commitment is made with one of the most elegant tools in modern cryptography: elliptic curves and their pairings, operations that pair points of two cryptographic groups and allow verifying equalities between polynomials without seeing the polynomials. The KZG polynomial commitment (named after its authors Kate, Zaverucha and Goldberg) fixes the polynomial in a single point on the curve: small, fast to verify and unforgeable as long as the curve’s discrete logarithm problem remains unsolved.
SNARK and STARK, the two great surnames
With the pieces assembled, the SNARK (Succinct Non-interactive ARgument of Knowledge) is born: a non-interactive, succinct proof of knowledge of a witness. “Succinct” is the key: the proof takes a few hundred bytes and verifies in milliseconds, whether the verified computation takes seconds or hours. Great for the verifier; the price is paid by the prover, who must build the circuit and compute the polynomial, an expensive process in both time and memory.
Groth16-style SNARKs require a trusted setup ceremony: a one-time phase in which a random secret is generated and then destroyed, with the security of the proof depending on it. If that “toxic waste” leaked, anyone could forge fake proofs. In contrast, STARKs (Scalable Transparent ARguments of Knowledge) replace elliptic curves with hash functions: they need no trusted setup (they are transparent), they withstand even quantum computers better, and their proofs are much larger. The third famous family, Bulletproofs, also avoids the trusted setup at the cost of proofs with logarithmic size.
From the math drawer to your pocket
Far from being an academic curiosity, zero-knowledge proofs already move real money and data. On Ethereum and other chains, zero-knowledge rollups (ZK-rollups) compress thousands of transactions into a single proof published on-chain: the layer 2 does the work and the layer 1 only verifies the proof, at a fixed cost per batch instead of per operation. Coins such as Zcash have used SNARKs since 2016 to hide sender, recipient and amount.
Outside the crypto world, the same engine serves to verify age without showing the document, to prove solvency without showing balances, for auditable electronic voting without breaking ballot secrecy, and for verifiable computation: delegating a heavy calculation to a server and receiving, together with the result, a proof that it was executed correctly. Artificial intelligence is starting to peek in too: the so-called zkML makes it possible to prove that an AI model satisfies a certain property without revealing the model or the data.
All of this rests on an idea at once simple and dizzying: that the information you do not say can be, mathematically, as convincing as the information you show. The next time a system asks you for “just one more detail”, think about whether it really needs to know it or only needs to be sure of you. More and more often, the right answer will be a proof that demonstrates it without telling it.
