Open this lesson in your favourite AI. It'll walk you through the why, explain the demo, and quiz you on the try-it list.
Schnorr's 1989 identification protocol is the mother of modern ZK. It's three moves (commit, challenge, response), it works in any group where discrete log is hard, and it's a sigma-protocol — meaning it's simultaneously complete, sound, honest-verifier-ZK, and has a clean simulator + extractor. Every Bulletproof, every sigma protocol, every PLONK+Halo verifier has Schnorr DNA. If you can derive Schnorr from scratch, you can read ZK papers.
Prove knowledge of x such that Y = x·G in an elliptic curve group. Prover picks random r, sends R = r·G. Verifier sends random challenge c. Prover sends s = r + c·x. Verifier checks s·G = R + c·Y. The algebra is a one-liner; the security argument reveals everything about how sigma protocols work.
# schnorr_sigma.py — Schnorr's sigma protocol over the secp256k1 curve.
from ecdsa import SECP256k1, SigningKey
from ecdsa.util import number_to_string
import hashlib, os, secrets
G = SECP256k1.generator
n = SECP256k1.order
def hash_int(*parts):
h = hashlib.sha256()
for p in parts: h.update(p if isinstance(p, bytes) else str(p).encode())
return int.from_bytes(h.digest(), "big") % n
# Prover's secret
x = secrets.randbelow(n)
Y = x * G # public
# --- Interactive Schnorr ---
def prove_interactive(challenge):
r = secrets.randbelow(n)
R = r * G
s = (r + challenge * x) % n
return R, s
def verify_interactive(R, challenge, s):
return s * G == R + challenge * Y
# --- Non-interactive (Fiat-Shamir) ---
def prove_nizk(message=b""):
r = secrets.randbelow(n)
R = r * G
c = hash_int(Y.to_bytes(), R.to_bytes(), message)
s = (r + c * x) % n
return R, s
def verify_nizk(R, s, message=b""):
c = hash_int(Y.to_bytes(), R.to_bytes(), message)
return s * G == R + c * Y
R, s = prove_nizk(b"hello world")
print("verify:", verify_nizk(R, s, b"hello world"))
python3 main.pyUse these three in order. Each builds on the one before.
In one paragraph, explain Schnorr's identification protocol — the three moves, what the prover is proving knowledge of, and why it's the template for modern ZK.
Walk me through the simulator-extractor pair for Schnorr: how the simulator produces a verifying transcript without knowing x (honest-verifier ZK), and how the extractor recovers x from two transcripts with a shared commitment (special soundness).
Given I want to build a signature aggregation scheme (MuSig2) from Schnorr sigma protocols, walk me through: how do n parties jointly produce a valid Schnorr signature, what goes wrong with naive summation, and how nonces must be structured to prevent Wagner's k-sum attack.