Zero-Knowledge Proofs

in reviewThis lesson is complete and being validated before release - details may still change.

Zero-knowledge identification

Loading interactive demo…

The strip at the top holds the public numbers p, g, and y, and says whether the prover knows x. The left table fills round by round with the commitment t, the coin c, the answer s, and the verifier's two sides of the check; the right table with rounds made up with no secret. The strip at the bottom marks each round held or failed. Tap a round to light it in both tables.Take the tour, or press and explore. Legend:

The panel beside the stage is the real SchnorrIdentification class from the published library executing in your browser, with the current line highlighted.

The round and the values under way.
A check that held, and a cheater's bet that matched the coin.
A check that failed, and the bet that lost.
The public key.
Values not yet reached, ghosted.

passed is how many real rounds held, caught the first that failed, cheat chance the odds a prover without x survives every round, verdict whether the verifier accepts. Reseed draws a new secret and new coins.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

One round. The prover knows $x$ with $y = g^x \bmod p$ . It picks a fresh $r$ and sends $t = g^r$ ; the verifier sends a coin $c \in \{0, 1\}$ ; the prover answers $s = r + c\,x \bmod (p - 1)$ ; the verifier accepts when

g^s \equiv t \cdot y^c \pmod p .

Exponents live mod $p - 1$ because $g^{p-1} = 1$ , which is Fermat's little theorem from the modular arithmetic lesson.

Completeness. An honest prover always passes: $g^{r + c x} = g^r \cdot (g^x)^c = t \cdot y^c$ .

Soundness. Suppose a prover, honest or not, could answer both coins for the same $t$ , with $s_0$ and $s_1$ . Then $g^{s_0} = t$ and $g^{s_1} = t\,y$ , so $y = g^{s_1 - s_0}$ and

x = s_1 - s_0 \bmod (p - 1) .

Whoever can answer both questions can compute $x$ , so a prover without $x$ can answer at most one, and the coin finds the other half the time. After $n$ rounds a cheater survives with chance $2^{-n}$ . This argument is called special soundness, and the formula for $x$ is the extractor: it is also why $r$ must never repeat.

Zero knowledge. Pick $c$ and $s$ at random and set $t = g^s \cdot y^{-c}$ . The triple $(t, c, s)$ passes the check, and it is distributed exactly like a real round: in both, $s$ is uniform and $t$ is whatever makes the check hold. Anything the verifier could compute from real transcripts it could compute from these, so the conversation taught it nothing about $x$ . Such a procedure is called a simulator, and its existence is the definition of zero knowledge.

Why the simulator does not break soundness. The simulator and the cheater use the same trick: choose the answer, then the commitment. The simulator gets to choose $c$ too; the cheater must commit before the verifier's coin. That ordering is the entire difference between a convincing proof and a transcript anyone could have written, and it is why a recording of the session convinces no one else.

From proof to signature. Replace the coin with a hash of $t$ and the message, and the prover can run the protocol alone; the transcript becomes a signature anyone can check. That is the Fiat-Shamir transform, and it trades away deniability: a signature, unlike the live proof, is meant to convince third parties. Real Schnorr draws its challenge from a group of about $2^{256}$ elements, so one round is enough; the one-bit coin is here so the cheater has a visible half chance.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

commit and simulate share one formula, $g^s \cdot y^{-c}$ . The cheater uses it with a guessed coin before the challenge; the simulator with a chosen coin after the fact. Reading the two side by side is the lesson's argument in code.
yPower takes the inverse of $y$ from the Euclid lesson's class, so $y^{-c}$ is $(y^{-1})^c$ and no division mod $p$ appears anywhere.
The secret is null for a cheater in respond, not hidden: the code path that would use $x$ is simply unreachable, which is how the stage can promise the cheater never touches it.
caught fires once, at the first failed check, while verify records every round, so the verdict can count all failures and the narration can still name the round that first exposed the cheat.

Shafi Goldwasser, Silvio Micali, and Charles Rackoff asked in 1985 how much knowledge a proof conveys beyond the fact that it is true, and showed that interaction and randomness can bring that to zero: the verifier ends convinced, and holds nothing it could not have made up alone. Identification schemes followed within a few years, and Claus Schnorr's of 1989, built on the discrete logarithm, became the template; with the coin replaced by a hash it is a signature, and its descendants sign SSH keys and Bitcoin transactions. The stage runs Schnorr's protocol with one-bit coins.

1985Shafi Goldwasser, Silvio Micali, and Charles Rackoff - Define interactive proofs and their knowledge complexity, and give the first zero-knowledge proofs, for quadratic residuosity.source
1986Amos Fiat and Adi Shamir - Replace the verifier's coins with a hash of the commitment, turning an interactive identification into a signature anyone can check later.source
1989Claus Schnorr - Publishes an identification protocol and signature over a discrete logarithm group, short and fast enough for smart cards; the patent expires in 2008.source
2012Shafi Goldwasser and Silvio Micali - Receive the Turing Award for laying the complexity-theoretic foundations of cryptography, work that includes probabilistic encryption and zero-knowledge proofs.source
2016Zcash - Launches a currency whose shielded transactions carry succinct zero-knowledge proofs that they balance, without revealing sender, receiver, or amount.source

Used today

Signatures - Fiat-Shamir turns this exact protocol into Schnorr signatures; Ed25519, common for SSH keys, is a variant, and Bitcoin adopted Schnorr signatures with Taproot in 2021.
Private transactions and rollups - Succinct proofs show that a transaction or a whole batch of them obeys the rules, revealing neither amounts nor the computation.
Credentials - Anonymous credential schemes let a holder prove a property of a signed attribute, such as being over 18, without showing the attribute itself.

prover

rounds5 rounds

passed: 5 of 5
caught: no
cheat chance: 1 in 32
verdict: accepted

schnorr-identification.ts

import { EuclideanAlgorithm } from "../number-theory/euclidean-algorithm";import { ModularArithmetic } from "../number-theory/modular-arithmetic";import { Mulberry32 } from "../random";import type { Tracer } from "../trace";/** The group the proof runs in: a small prime with a generator, so every number stays readable. */export const ZK_GROUP = { p: 127, g: 3 } as const;export const MAX_ROUNDS = 10;export type Prover = "honest" | "cheater";export interface Transcript {  round: number;  /** The commitment, g to a fresh r. */  t: number;  /** The verifier's challenge bit. */  c: number;  /** The response, r + c x mod p - 1. */  s: number;  ok: boolean;}export interface ZkRun {  p: number;  g: number;  /** The secret the honest prover holds; a cheater does not know it, but it exists. */  x: number;  secret: number;  /** The public key, g to the x. */  y: number;  publicKey: number;  prover: Prover;  rounds: number;  transcripts: Transcript[];  /** The round a cheater was caught in, or null. */  caughtAt: number | null;  accepted: boolean;  /** The chance a cheater passes every round: one half per round. */  cheatProbability: number;  /** Transcripts made with no secret at all, which verify just the same. */  simulated: Transcript[];}/** * Schnorr's identification protocol with one-bit challenges: a prover * who knows x with y = g to the x convinces a verifier of that without * revealing x. Each round the prover commits to t = g to a fresh r, * the verifier flips a coin c, and the prover answers s = r + c x; the * verifier checks g to the s = t times y to the c. An honest prover * passes every round. A cheater who does not know x can prepare an * answer for one value of c in advance, by choosing s first and * setting t = g to the s over y to the c, but not for both, so each * round catches the cheat with probability one half and ten rounds * leave a chance below one in a thousand. The protocol is zero * knowledge because a transcript made that way, with no secret, is * distributed exactly like a real one: the verifier learns nothing it * could not have made up. * * Time: O(rounds) modular powers. Space: O(rounds) transcripts. */export class SchnorrIdentification {  constructor(    private readonly tracer?: Tracer,    private readonly modular: ModularArithmetic = new ModularArithmetic(),    private readonly euclid: EuclideanAlgorithm = new EuclideanAlgorithm(),  ) {}  /** The public key from the secret: y = g to the x mod p. */  setup(p: number, g: number, x: number): number {  setup(p: number, g: number, secret: number): number {    if (!ModularArithmetic.isGenerator(g, p)) throw new RangeError(`${g} does not generate the group mod ${p}`);    if (!Number.isInteger(x) || x < 1 || x > p - 2) throw new RangeError(`the secret is a whole number from 1 to p - 2, got ${x}`);    if (!Number.isInteger(secret) || secret < 1 || secret > p - 2) throw new RangeError(`the secret is a whole number from 1 to p - 2, got ${x}`);    const y = this.modular.pow(g, x, p);    const publicKey = this.modular.pow(g, secret, p);    // ▸ publish y = g to the x; x stays with the prover    this.tracer?.emit("setup", { p, g, x, y });    this.tracer?.emit("setup", { p, g, secret, publicKey });    return y;    return publicKey;  }  /** y to the minus c: the inverse of y, raised to c. */  private yPower(p: number, y: number, c: number, negative: boolean): number {  private yPower(p: number, publicKey: number, c: number, negative: boolean): number {    const base = negative ? (this.euclid.inverse(y, p).inverse ?? 1) : y;    const base = negative ? (this.euclid.inverse(publicKey, p).inverse ?? 1) : publicKey;    return this.modular.pow(base, c, p);  }  /** The commitment: g to r for an honest prover; for a cheater guessing c, g to s over y to the guess, so that one answer will fit. */  commit(p: number, g: number, y: number, round: number, r: number, guess: number | null, s: number): number {  commit(p: number, g: number, publicKey: number, round: number, nonce: number, guess: number | null, s: number): number {    const t = guess === null ? this.modular.pow(g, r, p) : this.modular.mul(this.modular.pow(g, s, p), this.yPower(p, y, guess, true), p);    const t = guess === null ? this.modular.pow(g, nonce, p) : this.modular.mul(this.modular.pow(g, s, p), this.yPower(p, publicKey, guess, true), p);    // ▸ the prover commits to t before seeing the coin    this.tracer?.emit("commit", { round, t, guess });    return t;  }  /** The verifier's coin. */  challenge(round: number, c: number): number {    // ▸ the verifier flips a coin    this.tracer?.emit("challenge", { round, c });    return c;  }  /** The response: r + c x mod p - 1 for an honest prover, or the answer prepared in advance. */  respond(p: number, round: number, r: number, c: number, x: number | null, prepared: number): number {  respond(p: number, round: number, nonce: number, c: number, secret: number | null, prepared: number): number {    const s = x === null ? prepared : (r + c * x) % (p - 1);    const s = secret === null ? prepared : (nonce + c * secret) % (p - 1);    // ▸ the prover answers; only someone who knows x can answer both coins    this.tracer?.emit("respond", { round, s, hasSecret: x !== null });    this.tracer?.emit("respond", { round, s, hasSecret: secret !== null });    return s;  }  /** The check: g to the s against t times y to the c. */  verify(p: number, g: number, y: number, round: number, t: number, c: number, s: number): boolean {  verify(p: number, g: number, publicKey: number, round: number, t: number, c: number, s: number): boolean {    const lhs = this.modular.pow(g, s, p);    const rhs = this.modular.mul(t, this.yPower(p, y, c, false), p);    const rhs = this.modular.mul(t, this.yPower(p, publicKey, c, false), p);    const ok = lhs === rhs;    // ▸ the check: g to the s must equal t times y to the c    this.tracer?.emit("verify", { round, lhs, rhs, ok });    return ok;  }  /** A transcript with no secret: pick c and s, then set t so that the check holds. It is distributed like a real one. */  simulate(p: number, g: number, y: number, round: number, c: number, s: number): Transcript {  simulate(p: number, g: number, publicKey: number, round: number, c: number, s: number): Transcript {    const t = this.modular.mul(this.modular.pow(g, s, p), this.yPower(p, y, c, true), p);    const t = this.modular.mul(this.modular.pow(g, s, p), this.yPower(p, publicKey, c, true), p);    const ok = this.modular.pow(g, s, p) === this.modular.mul(t, this.yPower(p, y, c, false), p);    const ok = this.modular.pow(g, s, p) === this.modular.mul(t, this.yPower(p, publicKey, c, false), p);    // ▸ pick c and s first, then solve for t: a valid transcript with no secret    this.tracer?.emit("simulate", { round, c, s, t, ok });    return { round, t, c, s, ok };  }  /** The secret from the seed, the rounds with an honest or a cheating prover, the verdict, then as many simulated transcripts. */  run(prover: Prover, rounds: number, seed: number): ZkRun {    if (!Number.isInteger(rounds) || rounds < 1 || rounds > MAX_ROUNDS) throw new RangeError(`rounds must be a whole number from 1 to ${MAX_ROUNDS}, got ${rounds}`);    const { p, g } = ZK_GROUP;    const random = new Mulberry32(seed);    const x = random.intBetween(1, p - 2);    const secret = random.intBetween(1, p - 2);    const y = this.setup(p, g, x);    const publicKey = this.setup(p, g, secret);    const transcripts: Transcript[] = [];    let caughtAt: number | null = null;    for (let round = 0; round < rounds; round++) {      const r = random.intBetween(1, p - 2);      const nonce = random.intBetween(1, p - 2);      const guess = prover === "cheater" ? random.index(2) : null;      const prepared = random.intBetween(0, p - 2);      const t = this.commit(p, g, y, round, r, guess, prepared);      const t = this.commit(p, g, publicKey, round, nonce, guess, prepared);      const c = this.challenge(round, random.index(2));      const s = this.respond(p, round, r, c, prover === "honest" ? x : null, prepared);      const s = this.respond(p, round, nonce, c, prover === "honest" ? secret : null, prepared);      const ok = this.verify(p, g, y, round, t, c, s);      const ok = this.verify(p, g, publicKey, round, t, c, s);      if (!ok && caughtAt === null) {        caughtAt = round;        // ▸ a wrong answer exposes a prover who does not know x        this.tracer?.emit("caught", { round, guess, c });      }      transcripts.push({ round, t, c, s, ok });    }    const failed = transcripts.filter((tr) => !tr.ok).length;    const accepted = failed === 0;    const cheatProbability = 2 ** -rounds;    // ▸ accept only if every round held    this.tracer?.emit("verdict", { rounds, failed, accepted, cheatProbability });    const simulated: Transcript[] = [];    for (let round = 0; round < rounds; round++) simulated.push(this.simulate(p, g, y, round, random.index(2), random.intBetween(0, p - 2)));    for (let round = 0; round < rounds; round++) simulated.push(this.simulate(p, g, publicKey, round, random.index(2), random.intBetween(0, p - 2)));    return { p, g, x, y, prover, rounds, transcripts, caughtAt, accepted, cheatProbability, simulated };    return { p, g, secret, publicKey, prover, rounds, transcripts, caughtAt, accepted, cheatProbability, simulated };  }}

accepted =: yes

5 of 5 real rounds held and 5 of 5 fakes verify: accepted, and the transcript taught the verifier nothing it could not have made up.

import { EuclideanAlgorithm } from "../number-theory/euclidean-algorithm";import { ModularArithmetic } from "../number-theory/modular-arithmetic";import { Mulberry32 } from "../random";import type { Tracer } from "../trace";/** The group the proof runs in: a small prime with a generator, so every number stays readable. */export const ZK_GROUP = { p: 127, g: 3 } as const;export const MAX_ROUNDS = 10;export type Prover = "honest" | "cheater";export interface Transcript { round: number; /** The commitment, g to a fresh r. */ t: number; /** The verifier's challenge bit. */ c: number; /** The response, r + c x mod p - 1. */ s: number; ok: boolean;}export interface ZkRun { p: number; g: number; /** The secret the honest prover holds; a cheater does not know it, but it exists. */ x: number; secret: number; /** The public key, g to the x. */ y: number; publicKey: number; prover: Prover; rounds: number; transcripts: Transcript[]; /** The round a cheater was caught in, or null. */ caughtAt: number | null; accepted: boolean; /** The chance a cheater passes every round: one half per round. */ cheatProbability: number; /** Transcripts made with no secret at all, which verify just the same. */ simulated: Transcript[];}/** * Schnorr's identification protocol with one-bit challenges: a prover * who knows x with y = g to the x convinces a verifier of that without * revealing x. Each round the prover commits to t = g to a fresh r, * the verifier flips a coin c, and the prover answers s = r + c x; the * verifier checks g to the s = t times y to the c. An honest prover * passes every round. A cheater who does not know x can prepare an * answer for one value of c in advance, by choosing s first and * setting t = g to the s over y to the c, but not for both, so each * round catches the cheat with probability one half and ten rounds * leave a chance below one in a thousand. The protocol is zero * knowledge because a transcript made that way, with no secret, is * distributed exactly like a real one: the verifier learns nothing it * could not have made up. * * Time: O(rounds) modular powers. Space: O(rounds) transcripts. */export class SchnorrIdentification { constructor( private readonly tracer?: Tracer, private readonly modular: ModularArithmetic = new ModularArithmetic(), private readonly euclid: EuclideanAlgorithm = new EuclideanAlgorithm(), ) {} /** The public key from the secret: y = g to the x mod p. */ setup(p: number, g: number, x: number): number { setup(p: number, g: number, secret: number): number { if (!ModularArithmetic.isGenerator(g, p)) throw new RangeError(`${g} does not generate the group mod ${p}`); if (!Number.isInteger(x) || x < 1 || x > p - 2) throw new RangeError(`the secret is a whole number from 1 to p - 2, got ${x}`); if (!Number.isInteger(secret) || secret < 1 || secret > p - 2) throw new RangeError(`the secret is a whole number from 1 to p - 2, got ${x}`); const y = this.modular.pow(g, x, p); const publicKey = this.modular.pow(g, secret, p); // ▸ publish y = g to the x; x stays with the prover this.tracer?.emit("setup", { p, g, x, y }); this.tracer?.emit("setup", { p, g, secret, publicKey }); return y; return publicKey; } /** y to the minus c: the inverse of y, raised to c. */ private yPower(p: number, y: number, c: number, negative: boolean): number { private yPower(p: number, publicKey: number, c: number, negative: boolean): number { const base = negative ? (this.euclid.inverse(y, p).inverse ?? 1) : y; const base = negative ? (this.euclid.inverse(publicKey, p).inverse ?? 1) : publicKey; return this.modular.pow(base, c, p); } /** The commitment: g to r for an honest prover; for a cheater guessing c, g to s over y to the guess, so that one answer will fit. */ commit(p: number, g: number, y: number, round: number, r: number, guess: number | null, s: number): number { commit(p: number, g: number, publicKey: number, round: number, nonce: number, guess: number | null, s: number): number { const t = guess === null ? this.modular.pow(g, r, p) : this.modular.mul(this.modular.pow(g, s, p), this.yPower(p, y, guess, true), p); const t = guess === null ? this.modular.pow(g, nonce, p) : this.modular.mul(this.modular.pow(g, s, p), this.yPower(p, publicKey, guess, true), p); // ▸ the prover commits to t before seeing the coin this.tracer?.emit("commit", { round, t, guess }); return t; } /** The verifier's coin. */ challenge(round: number, c: number): number { // ▸ the verifier flips a coin this.tracer?.emit("challenge", { round, c }); return c; } /** The response: r + c x mod p - 1 for an honest prover, or the answer prepared in advance. */ respond(p: number, round: number, r: number, c: number, x: number | null, prepared: number): number { respond(p: number, round: number, nonce: number, c: number, secret: number | null, prepared: number): number { const s = x === null ? prepared : (r + c * x) % (p - 1); const s = secret === null ? prepared : (nonce + c * secret) % (p - 1); // ▸ the prover answers; only someone who knows x can answer both coins this.tracer?.emit("respond", { round, s, hasSecret: x !== null }); this.tracer?.emit("respond", { round, s, hasSecret: secret !== null }); return s; } /** The check: g to the s against t times y to the c. */ verify(p: number, g: number, y: number, round: number, t: number, c: number, s: number): boolean { verify(p: number, g: number, publicKey: number, round: number, t: number, c: number, s: number): boolean { const lhs = this.modular.pow(g, s, p); const rhs = this.modular.mul(t, this.yPower(p, y, c, false), p); const rhs = this.modular.mul(t, this.yPower(p, publicKey, c, false), p); const ok = lhs === rhs; // ▸ the check: g to the s must equal t times y to the c this.tracer?.emit("verify", { round, lhs, rhs, ok }); return ok; } /** A transcript with no secret: pick c and s, then set t so that the check holds. It is distributed like a real one. */ simulate(p: number, g: number, y: number, round: number, c: number, s: number): Transcript { simulate(p: number, g: number, publicKey: number, round: number, c: number, s: number): Transcript { const t = this.modular.mul(this.modular.pow(g, s, p), this.yPower(p, y, c, true), p); const t = this.modular.mul(this.modular.pow(g, s, p), this.yPower(p, publicKey, c, true), p); const ok = this.modular.pow(g, s, p) === this.modular.mul(t, this.yPower(p, y, c, false), p); const ok = this.modular.pow(g, s, p) === this.modular.mul(t, this.yPower(p, publicKey, c, false), p); // ▸ pick c and s first, then solve for t: a valid transcript with no secret this.tracer?.emit("simulate", { round, c, s, t, ok }); return { round, t, c, s, ok }; } /** The secret from the seed, the rounds with an honest or a cheating prover, the verdict, then as many simulated transcripts. */ run(prover: Prover, rounds: number, seed: number): ZkRun { if (!Number.isInteger(rounds) || rounds < 1 || rounds > MAX_ROUNDS) throw new RangeError(`rounds must be a whole number from 1 to ${MAX_ROUNDS}, got ${rounds}`); const { p, g } = ZK_GROUP; const random = new Mulberry32(seed); const x = random.intBetween(1, p - 2); const secret = random.intBetween(1, p - 2); const y = this.setup(p, g, x); const publicKey = this.setup(p, g, secret); const transcripts: Transcript[] = []; let caughtAt: number | null = null; for (let round = 0; round < rounds; round++) { const r = random.intBetween(1, p - 2); const nonce = random.intBetween(1, p - 2); const guess = prover === "cheater" ? random.index(2) : null; const prepared = random.intBetween(0, p - 2); const t = this.commit(p, g, y, round, r, guess, prepared); const t = this.commit(p, g, publicKey, round, nonce, guess, prepared); const c = this.challenge(round, random.index(2)); const s = this.respond(p, round, r, c, prover === "honest" ? x : null, prepared); const s = this.respond(p, round, nonce, c, prover === "honest" ? secret : null, prepared); const ok = this.verify(p, g, y, round, t, c, s); const ok = this.verify(p, g, publicKey, round, t, c, s); if (!ok && caughtAt === null) { caughtAt = round; // ▸ a wrong answer exposes a prover who does not know x this.tracer?.emit("caught", { round, guess, c }); } transcripts.push({ round, t, c, s, ok }); } const failed = transcripts.filter((tr) => !tr.ok).length; const accepted = failed === 0; const cheatProbability = 2 ** -rounds; // ▸ accept only if every round held this.tracer?.emit("verdict", { rounds, failed, accepted, cheatProbability }); const simulated: Transcript[] = []; for (let round = 0; round < rounds; round++) simulated.push(this.simulate(p, g, y, round, random.index(2), random.intBetween(0, p - 2))); for (let round = 0; round < rounds; round++) simulated.push(this.simulate(p, g, publicKey, round, random.index(2), random.intBetween(0, p - 2))); return { p, g, x, y, prover, rounds, transcripts, caughtAt, accepted, cheatProbability, simulated }; return { p, g, secret, publicKey, prover, rounds, transcripts, caughtAt, accepted, cheatProbability, simulated }; }}