ZKP and Schnorr Protocol

Apr 03, 2026 cryptography

The Problem With Traditional Proofs

In the classical NP sense, proving something means handing over evidence. To prove you know a satisfying assignment for a boolean formula, you give the assignment. The verifier checks it, everyone’s happy — except now the verifier has your assignment. The proof leaked information.

This might sound academic, but the practical version is familiar: every time you type a password into a website, you’re sending the secret to prove your identity. If the server is compromised, your password is gone.

Zero-knowledge proofs eliminate this trade-off. They let you convince someone that a statement is true — “I know the password,” “I know the discrete log,” “this transaction is valid” — without revealing anything beyond that single bit of conviction.

Three Properties Every ZKP Must Satisfy

Completeness — If the prover actually knows the secret, the verifier always accepts. An honest prover never fails.
Soundness — If the prover doesn’t know the secret, they get caught. No strategy, no matter how clever, can consistently fool the verifier.
Zero-Knowledge — The verifier learns nothing from the interaction. Formally, everything the verifier sees could have been generated by the verifier alone, without ever talking to the prover. If the real transcript is indistinguishable from a fake one, then no knowledge leaked.

These three properties were first formalized by Goldwasser, Micali, and Rackoff in their 1989 paper “The Knowledge Complexity of Interactive Proof Systems”.

The Ali Baba Cave

The standard intuition-builder for ZKPs comes from Quisquater et al.’s 1990 paper “How to Explain Zero-Knowledge Protocols to Your Children.”

Imagine a cave shaped like a ring. A single entrance forks into two paths — left and right — that meet at a locked door deep inside.

    Entrance
       |
      / \
     L   R
      \ /
    [DOOR] ← needs secret password

You claim you know the password. The verifier wants proof.

The verifier waits outside while you walk in and take a random path — left or right. They don’t see which way you went. Then the verifier shouts: “Come out from the LEFT!” (or right, chosen randomly).

If you know the password, you can always comply. Already on the left? Walk back. On the right? Unlock the door, walk through, come out the left side. You always succeed.

If you don’t know the password, you’re stuck half the time. You picked a path, the verifier asked for the other side, and there’s a locked door between you and it.

Repeat this 20 times. A liar’s odds of faking every round: (1/2)^20, roughly one in a million. The password is never spoken aloud, never transmitted, never revealed.

The Schnorr Protocol

Claus-Peter Schnorr published “Efficient Signature Generation by Smart Cards” in 1991, building directly on the theoretical framework GMR had established. Where GMR proved that zero-knowledge proofs exist, Schnorr built one efficient enough to run on a smart card chip.

The protocol proves knowledge of a discrete logarithm: “I know w such that g^w = y mod p.”

What Everyone Knows, What Only You Know

The public parameters are the group setup — a large prime p, the order of the subgroup q (where p = 2q + 1), a generator g, and your public key y = g^w mod p. These are out in the open.

The secret is w — your private key. The security rests entirely on the discrete logarithm problem: given g, y, and p, nobody can efficiently compute w.

During each run of the protocol, the prover also generates a fresh random nonce r. This nonce is ephemeral — used once and discarded — and it’s what makes the protocol zero-knowledge.

The Three-Message Dance

The protocol follows the Sigma (Σ) pattern — named for the shape of the message flow arrows, which look like the Greek letter.

Commitment. The prover picks a random r from {1, ..., q-1} and sends a = g^r mod p to the verifier. This locks the prover in — they can’t change their answer after seeing the challenge.

Challenge. The verifier picks a random e and sends it back. This is the pop quiz that prevents precomputation.

Response. The prover computes z = (r + e * w) mod q and sends it to the verifier.

Prover                                Verifier

Choose random r
a = g^r mod p
                  ---- a ---->
                                      Choose random e
                  <--- e ----

z = (r + e*w) mod q
                  ---- z ---->
                                      Accept iff g^z = a * y^e mod p

Why Verification Works

The verifier checks whether g^z = a * y^e mod p. If the prover is honest, this always holds:

g^z = g^(r + e*w)
    = g^r * g^(e*w)
    = g^r * (g^w)^e
    = a * y^e  mod p

The verifier has a (received in step 1), e (they chose it), z (received in step 3), and the public values g, y, p. They can check the equation without knowing w or r.

Why a Cheater Can’t Fake It

A cheater who doesn’t know w commits to a before seeing e. To pass verification, they’d need to produce a z satisfying g^z = a * y^e mod p for a challenge e they haven’t seen yet. Without knowing w, this requires solving the discrete logarithm problem on the spot.

Why the Verifier Learns Nothing

The response z = r + e*w mod q contains the secret w, but it’s masked by the random nonce r. Since r is uniformly random and unknown to the verifier, z looks uniformly random too — like a one-time pad over the secret.

More formally, a simulator can produce transcripts indistinguishable from real ones without knowing w: pick z and e at random, compute a = g^z * y^(-e) mod p. The result looks exactly like a legitimate protocol run.

One Round Is Enough

In the cave analogy, each round only eliminates half the cheaters — you need many rounds. But Schnorr’s insight for smart cards was that you don’t need multiple rounds if the challenge space is large enough.

A 1-bit challenge over 40 rounds gives the same security as a 40-bit challenge in a single round — in both cases, a cheater’s odds are 1/2^40. The CryptoHack server uses a 511-bit challenge, making the probability of faking it in one round roughly 1/2^511.

This is what made the protocol practical for smart cards. One interaction, one tap, done.

Why Each Step Matters

Remove any of the three messages and the protocol collapses:

Without the commitment, the prover sees the challenge first and can pick z freely, then compute a = g^z * y^(-e) mod p backwards. No knowledge of w needed.

Without the challenge, the prover can prepare everything in advance without knowing w.

Without the response, there’s nothing for the verifier to check.

What Schnorr’s Paper Actually Addresses

Schnorr wasn’t writing about blockchain or abstract cryptographic theory. The paper solves a specific engineering problem: smart cards in 1991 had extremely limited processors, and existing signature schemes (RSA, Fiat-Shamir) required too many modular multiplications to be practical.

The key performance numbers from Section 3 of the paper:

	Schnorr	Fiat-Shamir	RSA	GQ
Sig generation (without preprocessing)	0	44	750	180
Preprocessing	210	0	0	0
Sig verification	228	44	>2	108

(Values are number of modular multiplications)

The trick is splitting the work into two phases. The expensive computation — g^r mod p — happens during preprocessing, when the card is idle. The actual signature, computed when the message arrives, is just a 72-bit × 140-bit multiplication. Nearly free.

The paper explicitly covers:

Smart card authentication (the primary use case)
Digital signatures (making the protocol non-interactive via hashing: e = h(x, m))
Access control for communication networks
Electronic fund transfers
Key distribution (integrating with Beth authentication and Günther’s scheme)

Schnorr signatures eventually made it into Bitcoin’s Taproot upgrade in 2021 — 32 years after the paper. The same protocol has also served as a building block for multi-signatures, ring signatures (Monero), and the foundations of zk-SNARKs and zk-STARKs.