Schnorr / Fiat–Shamir Zero-Knowledge Proofs Explained

What is a zero-knowledge proof?

A zero-knowledge proof (ZKP) lets a prover convince a verifier that a statement is true — typically that the prover knows some secret — without revealing the secret itself. The canonical example: you prove you know the PIN to a vault without entering it. Formally, a ZKP has three properties:

• Completeness: if the statement is true, an honest prover convinces an honest verifier.
• Soundness: if the statement is false, no cheating prover can convince the verifier (except with negligible probability).
• Zero-knowledge: the verifier learns nothing beyond the truth of the statement — there exists a simulator that can produce an indistinguishable transcript without knowing the secret.

For Tessera, the statement is “I know the secret key xcorresponding to public key Y” — or, after blinding,“I know x′ such that Y′ = x′·G.” The proof authenticates the sender to the recipient, but the transcript reveals nothing about x.

The Schnorr identification protocol

Schnorr’s protocol (1989) is the simplest ZKP of knowledge of a discrete logarithm. Setup: a cyclic group of prime order q with generator G (Tessera uses SECP256k1). The prover’s secret is x ∈ Z_q; the corresponding public key isY = x·G. The interactive, three-move protocol is:

1. Commit: Prover samples r ←$ Z_q, computes R = r·G, sends R.
2. Challenge: Verifier sends a random challenge c ←$ Z_q.
3. Response: Prover computes s = (r + c·x) mod q, sends s.

The verifier accepts iff s·G == R + c·Y. This holds becauses·G = (r + c·x)·G = r·G + c·(x·G) = R + c·Y. The verifier is convinced the prover knows x — but the transcript(R, c, s) could have been simulated by anyone who knewc in advance, which is the source of zero-knowledge.

The math: Prove and Verify

Tessera’s non-interactive variant binds the proof to a messagem (the delivery context). The prover computes:

Prove(x, Y, m):
  r ←$ Z_q
  R = r·G
  c = H(R ‖ Y ‖ m)        # Fiat–Shamir challenge
  s = (r + c·x) mod q
  return π = (R, s)

The verifier recomputes the challenge and checks the response:

Verify(Y, m, π):
  (R, s) = π
  c = H(R ‖ Y ‖ m)
  accept iff s·G == R + c·Y

The entire proof is the pair (R, s) — two group/scalar elements. On SECP256k1 that is 33 bytes for R (compressed) and 32 bytes for s, plus metadata, giving a serialized proof of roughly 216 bytes.

Why it is zero-knowledge

The simulator, given Y and m but notx, picks s ←$ Z_q and c ←$ Z_q, computes R = s·G − c·Y, and outputs (R, s) withc = H(R ‖ Y ‖ m). In the random oracle model the distribution of these simulated proofs is identical to that of real proofs — the simulator programs the oracle so the hash matches. Hence the verifier learns nothing about x beyond the fact that the prover knows it: this is honest-verifier zero-knowledge (HVZK) in the random oracle model.

The Fiat–Shamir transform

The Schnorr protocol as described is interactive — the verifier must send a fresh random challenge. The Fiat–Shamir transform(Fiat & Shamir, 1986; Bellare & Rogaway, 1993) removes the interaction by replacing the verifier’s challenge with a hash of the prover’s first message and the statement:c = H(R ‖ Y ‖ m). Under the random-oracle model this is provably as secure as the interactive protocol: a cheating prover would need to commit to R before seeing c, and sinceH is a random oracle, c is unpredictable.

The result is a non-interactive zero-knowledge proof (NIZK): the prover produces π in one shot, the verifier checks in one shot. This is what makes Tessera’s store-and-gossip routing possible — proofs are self-contained and can be relayed by any peer without a back-channel to the verifier.

Security: unforgeability, HVZK, and NIZK

Tessera relies on three security properties, all with formal proofs in the literature:

• Unforgeability (EUF-CMA under DLog). A forger who can produce a valid proof for a fresh (Y, m) without knowingx can be turned, via the forking lemma(Pointcheval & Stern, 1996), into an algorithm that solves the discrete-logarithm problem. Hence EUF-CMA ⇐ DLog.
• HVZK in the ROM. The simulator described above shows the interactive transcript reveals nothing about x to an honest verifier. The random-oracle model is required for the non-interactive case.
• NIZK under Fiat–Shamir. Bellare & Rogaway (1993) prove that FS-transformed Schnorr is a NIZK in the ROM, with soundness error roughly q_H / q where q_H is the number of oracle queries — negligible for SECP256k1.

Why Schnorr over other ZK proof systems?

Tessera’s authentication proof is a statement of knowledge of a discrete log — exactly what Schnorr is designed for. Compared with more expressive systems:

• Short proofs: ~216 bytes serialized on SECP256k1, versus ~50–200 KB for zk-STARKs.
• Fast generation: ~0.85 ms (a single scalar multiplication plus a hash), versus tens of ms for SNARKs and hundreds of ms for STARKs.
• Fast verification: ~13 ms (two scalar multiplications, or one if using batch verification), comparable to SNARKs and far faster than Bulletproofs.
• No trusted setup: unlike Groth16 SNARKs, Schnorr has no per-circuit ceremony and no toxic waste.
• Standard assumptions: only the discrete-logarithm assumption in a prime-order group and a random oracle — no pairings, no knowledge-of-exponent, no FRI.

The tradeoff is expressiveness: Schnorr proves knowledge of a discrete log, not arbitrary circuits. Tessera’s proof is exactly the statement it needs, so the simpler system wins on every axis that matters here.

Comparison: Schnorr vs zk-SNARK vs zk-STARK vs Bulletproof

Schnorr / Fiat–Shamir is the smallest and fastest option for proving knowledge of a discrete log, with no trusted setup and standard assumptions — which is precisely Tessera’s use case.

Code example: Tessera ZKProver / ZKVerifier API

from tessera.crypto import ZKProver, ZKVerifier

# Sender side — generate a non-interactive proof bound to a message
prover = ZKProver(secret_key=x, public_key=Y)
proof = prover.prove(message=session_id)        # returns (R, s), ~0.85 ms

# Recipient side — verify without learning x
verifier = ZKVerifier(public_key=Y)
ok = verifier.verify(message=session_id, proof=proof)   # ~13 ms, returns bool

The proof is then AES-GCM encrypted to the recipient’s delivery key and routed via bucketed broadcast. The recipient decrypts, verifies the Schnorr proof, and accepts the delivery — all without ever learning the sender’s long-term public key (which has been blinded; seePer-Recipient Blinded Pseudonyms).

Frequently asked questions