Zero-Knowledge Proofs

Imagine you want to prove you know the password to a door — but without ever typing the password, and without letting the other person learn a single letter of it. It sounds impossible. How can a proof convince someone of anything while leaking nothing?

That is exactly what a zero-knowledge proof does. A prover persuades a verifier that some statement is true, and at the end the verifier is completely convinced — yet has learned nothing beyond the bare fact that the statement holds. No password. No secret. Not even a clue that would help them prove it to anyone else.

The idea was introduced in 1985 by Shafi Goldwasser, Silvio Micali and Charles Rackoff, work that helped earn Goldwasser and Micali the Turing Award in 2012. It began as deep theory and ended up running underneath modern privacy systems and blockchains.

Picture a ring-shaped cave with a single entrance that splits into two tunnels, left and right, joined at the back by a magic door that only opens with a secret word. Peggy claims she knows the word. Victor waits at the entrance.

Each round, Peggy walks in and picks a tunnel out of Victor's sight. Then Victor shouts which side he wants her to come out of. If she truly knows the word she can always obey — she just opens the door when needed. If she is bluffing, she can only obey when she happened to pick the right tunnel: a coin-flip, 50% chance.

<p class="hint">{{hint}}</p>
<div class="who">
  <label><input type="radio" name="role" value="knower" checked> {{role_knower}}</label>
  <label><input type="radio" name="role" value="cheater"> {{role_cheater}}</label>
</div>
<div class="cave" id="cave">
  <div class="ring"></div>
  <div class="door" id="door">{{door_lbl}}</div>
  <div class="peg" id="peg">P</div>
  <div class="vic">V</div>
  <div class="lbl lblL">{{lbl_left}}</div>
  <div class="lbl lblR">{{lbl_right}}</div>
</div>
<div class="status" id="status">{{status_init}}</div>
<div class="tally" id="tally"></div>
<div class="btns">
  <button id="one" type="button">{{btn_one}}</button>
  <button id="ten" type="button">{{btn_ten}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.who { display: flex; gap: 1rem; flex-wrap: wrap; font-size: .9rem; margin: 0 0 .6rem; }
.who label { cursor: pointer; }
.cave { position: relative; width: 230px; height: 150px; margin: .4rem auto .6rem; }
.ring { position: absolute; inset: 18px 18px 0 18px; border: 14px solid #cdd9e3;
        border-bottom: none; border-radius: 90px 90px 0 0; background: #f3f6f9; }
.door { position: absolute; top: 0; left: 50%; transform: translateX(-50%);
        background: #1d3557; color: #fff; font: 700 10px system-ui; padding: 2px 7px;
        border-radius: 5px; transition: background .2s; }
.door.open { background: #0a7d33; }
.peg { position: absolute; bottom: 4px; left: 50%; transform: translate(-50%,0);
       width: 26px; height: 26px; border-radius: 50%; background: #e63946; color: #fff;
       font: 700 13px system-ui; display: flex; align-items: center; justify-content: center;
       transition: left .45s ease, transform .45s ease; z-index: 2; }
.vic { position: absolute; bottom: -22px; left: 50%; transform: translateX(-50%);
       width: 24px; height: 24px; border-radius: 50%; background: #1d3557; color: #fff;
       font: 700 12px system-ui; display: flex; align-items: center; justify-content: center; }
.lbl { position: absolute; bottom: 56px; font: 700 11px system-ui; color: #1d3557; }
.lblL { left: 6px; } .lblR { right: 6px; }
.status { font-size: .98rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; text-align: center; }
.status.ok { color: #0a7d33; } .status.bad { color: #c92f3c; }
.tally { font-size: .9rem; text-align: center; margin: .3rem 0 .6rem; color: #1d3557; min-height: 1.3em; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; justify-content: center; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Run a few rounds as a real knower, then toggle to Cheater and watch. One round proves nothing — a bluffer gets lucky half the time. But the chance of fluking n rounds in a row is 1/$2^{n}$: ten rounds and it's under one in a thousand. Victor ends up certain Peggy knows the word, yet he never heard it. That is zero knowledge.

A zero-knowledge proof is not magic — it is a precise object that must satisfy three properties at once:

• Completeness: if the statement is true and both sides follow the rules, an honest verifier is convinced.
• Soundness: if the statement is false, no cheating prover can fool the verifier except with tiny probability — exactly the 1/$2^{n}$ the cave squeezes down round by round.
• Zero-knowledge: the verifier learns nothing except that the statement is true. This is made rigorous by a simulator: a program that, without knowing the secret, produces transcripts indistinguishable from real ones. If fake conversations look identical to real ones, the real ones cannot have leaked anything.

How far does this reach? Astonishingly far. In 1986, Goldreich, Micali and Wigderson proved that every problem in NP has a zero-knowledge proof — assuming one-way functions exist. Their key example is graph 3-coloring: the prover commits to a coloring under sealed envelopes, the verifier asks to open just one edge's two endpoints and checks the colors differ. One edge leaks nothing about the whole coloring, yet repeating over random edges drives a cheater's odds to zero.

Since 3-coloring is NP-complete, anything you can verify efficiently you can also prove in zero knowledge. The same constraint-satisfaction core behind graph coloring and SAT is exactly what makes universal zero-knowledge possible.

"Convince me, but tell me nothing" turns out to be one of the most useful requests in computing:

• Authentication: prove you hold a private key or password without sending it, so an eavesdropper or even the server learns nothing reusable.
• Blockchains and zk-rollups: thousands of transactions are compressed into one tiny proof (a zk-SNARK/zk-STARK) that anyone can check in milliseconds without re-running the work or seeing the data.
• Private identity: prove you are over 18, or a citizen, or have enough funds — without revealing your birthdate, name or balance.
• Verifiable computation: a powerful but untrusted server runs a heavy job and hands back a short proof that it ran the program correctly.

The thread tying these together is the same one in the cave: separate "is it true?" from "how do you know?". Zero-knowledge proofs let us answer the first while keeping the second completely private — a kind of cryptographic cousin to the verify-versus-find gap at the heart of P vs NP.

Zero-knowledge proofs answer a question that sounds paradoxical: how do you make someone certain of a truth while telling them nothing? The cave gives the intuition — pure luck cannot survive enough rounds — and the theory makes it ironclad: completeness, soundness and a simulator that proves no information leaked.

What started as abstract complexity theory in 1985 now quietly authenticates logins, shrinks blockchains and protects identities. And because every problem in NP has a zero-knowledge proof, the reach is almost unlimited: anything you can check, you can prove you know — without ever giving it away.