Schnorr — The Canonical Sigma Protocol

Statement: "I know x such that y = g^x" (discrete log of y in some group).

Schnorr's protocol (1989):

Prover (knows x)               Verifier (sees y)
  k ← random
  r = g^k
  ------ r --------->
                       c ← random
                       <------- c --------
  z = k + c*x mod n
  ------ z --------->
                       check g^z == r * y^c

Why does this work?

• Completeness: g^z = g^(k + cx) = g^k * (g^x)^c = r * y^c. ✓
• Soundness: a forger who picked r first must commit to it before seeing c. To answer two different challenges c1, c2 with valid z1, z2:
  • g^z1 = r * y^c1
  • g^z2 = r * y^c2
  • Divide: g^(z1 - z2) = y^(c1 - c2)
  • So x = (z1 - z2) / (c1 - c2) — they actually KNOW x. Hence forging implies extracting.
• Zero-knowledge: the transcript can be SIMULATED without knowing x:
  • Pick random c, z.
  • Compute r = g^z * y^(-c).
  • Output (r, c, z) — looks identical to a real proof.
  • This means the verifier learns nothing beyond "x exists" — they could have generated this themselves.

Verification:

Schnorr proofs are extremely common: identity protocols, anonymous credentials, group signatures. Schnorr signatures (a Fiat-Shamir variant) are now in Bitcoin (BIP 340, Taproot upgrade).