Sigma Protocols & Schnorr Identification

A Sigma protocol has 3 messages: (1) Commit: prover sends a commitment to a random value. (2) Challenge: verifier sends a random challenge. (3) Response: prover sends a response computed from the challenge and the secret. Verifier accepts or rejects.

Prover knows secret x (private key); public key = g^x mod p (or point X = x*G on an elliptic curve). Goal: prove knowledge of x without revealing it. This is a discrete-log proof of knowledge.

(1) Prover picks random r, sends commitment R = r*G. (2) Verifier sends challenge c (random integer). (3) Prover sends response s = r + c*x. (4) Verifier checks s*G == R + c*X. If yes, accepts. Prover knows x; response s is computable only with x.

Completeness: honest prover always satisfies s*G = r*G + c*x*G = R + c*X. Soundness: two transcripts with same R but different challenges c, c' yield s, s' from which x = (s-s')/(c-c') is recoverable — so a cheater cannot produce two valid responses for the same R.

Simulator (no knowledge of x): pick random s and c, set R = s*G - c*X. This (R, c, s) is a valid transcript distribution. The verifier cannot distinguish real transcripts from simulated ones — Schnorr is honest-verifier zero-knowledge.

Make Schnorr non-interactive: replace the verifier's challenge with c = Hash(R || message). The prover computes c themselves and responds. Result: a 2-element proof (R, s) that anyone can verify. This is the Schnorr signature scheme.

Sign(x, m): r ← random; R = r*G; c = Hash(R||m); s = r + c*x. Signature = (R, s). Verify: s*G == R + Hash(R||m)*X. Compact (64 bytes for P-256), batch-verifiable, provably secure in ROM. Adopted in Bitcoin Taproot (BIP-340).

C = r*G + v*H where H is a second independent generator. Commits to value v with randomness r. Binding: can't open to different v (discrete log). Hiding: C is uniformly distributed. Used in Schnorr-based range proofs and Bulletproofs.

Prove knowledge of x1 AND x2 simultaneously: run two Schnorr protocols with the same challenge (share the challenge via Fiat-Shamir). The verifier accepts only if both sub-proofs are valid. Enables proving multiple statements in one interaction.

Prove knowledge of x1 OR x2 without revealing which: use the simulator for one branch to compute a fake transcript, then split the challenge between both. The verifier sees two valid-looking transcripts summing to the real challenge. Called "ring signatures".

Schnorr IDs: electronic passports (PACE protocol). Schnorr sigs: Bitcoin Taproot, Monero (RingCT uses Schnorr OR-proofs), Signal Protocol (X3DH key agreement). Pedersen commitments: Confidential Transactions, Bulletproofs, Zcash Sapling note encryption.

Sigma protocols: commit-challenge-respond. Schnorr proves knowledge of a discrete log. Fiat-Shamir makes it non-interactive (Schnorr signature). Next: zk-SNARKs for succinct non-interactive proofs.