Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Chapter 16: $\Sigma$-Protocols: The Simplest Zero-Knowledge Proofs

In 1989, a Belgian cryptographer named Jean-Jacques Quisquater faced an unusual challenge: explaining zero-knowledge proofs to his children.

The mathematics was forbidding. Goldwasser, Micali, and Rackoff had formalized the concept four years earlier, but their definitions involved Turing machines, polynomial-time simulators, and computational indistinguishability. Quisquater wanted something a six-year-old could grasp.

So he invented a cave.

The Children’s Story

In Quisquater’s tale, Peggy (the Prover) wants to prove to Victor (the Verifier) that she knows the magic word to open a door deep inside a cave. The cave splits into two paths (Left and Right) that reconnect at the magic door.

Peggy enters the cave and takes a random path while Victor waits outside. Victor then walks to the fork and shouts: “Come out the Left path!”

If Peggy knows the magic word, she can always comply. If she originally went Left, she walks out. If she went Right, she opens the door with the magic word and exits through the Left. Either way, Victor sees her emerge from the Left.

If Peggy doesn’t know the word, she’s trapped. Half the time, Victor shouts for the path she’s already on (she succeeds). Half the time, he shouts for the other side (she fails, stuck behind a locked door).

They repeat this 20 times. A faker has a $(1/2)^{20}$ ≈ one-in-a-million chance of consistently appearing from the correct side. But someone who knows the word succeeds every time.

This story, published as “How to Explain Zero-Knowledge Protocols to Your Children,” captures the essence of what we now call a $\Sigma$-protocol: Commitment (entering the cave), Challenge (Victor shouting), Response (appearing from the correct side). Almost all modern cryptography, from your credit card chip to your blockchain wallet, is a mathematical version of this cave.

The paper became a classic. The cave analogy appears in nearly every introductory cryptography course. What makes it so powerful is that it captures the structure of zero-knowledge: the prover commits to a position before knowing the challenge, then demonstrates knowledge by responding correctly.

This chapter develops the mathematics behind the cave. A prover commits to something random. A verifier challenges with something random. The prover responds with something that combines both randomnesses with their secret. The verifier checks a simple algebraic equation. If it holds, accept; if not, reject.

This is a $\Sigma$-protocol. The name comes from the shape of the message flow: three arrows forming the Greek letter $\Sigma$ when drawn between prover and verifier. The structure is so fundamental that it appears everywhere cryptography touches authentication: digital signatures, identification schemes, credential systems, and as building blocks within the complex SNARKs we’ve studied.

Why study something so simple after the machinery of Groth16 and STARKs?

Because $\Sigma$-protocols crystallize the essential ideas of zero-knowledge. The simulator that we’ll construct, picking the response first then computing what the commitment “must have been,” is the archetype of all simulation arguments. The special soundness property (that two accepting transcripts with different challenges allow witness extraction) is the template for proofs of knowledge everywhere. And the Fiat-Shamir transform, which converts interaction into non-interaction, was developed precisely for $\Sigma$-protocols.

Understand $\Sigma$-protocols, and the zero-knowledge property itself becomes clear. This chapter prepares the ground for Chapter 17, where we formalize what “zero-knowledge” means. Here, we see it in its simplest form.

The Discrete Logarithm Problem

We return to familiar ground. Chapter 6 introduced the discrete logarithm problem as the foundation for Pedersen commitments. Now it serves a different purpose: enabling proofs of knowledge.

The setting is a cyclic group $\mathbb{G}$ of prime order $q$ with generator $g$. Every element $h \in \mathbb{G}$ can be written as $h = g^w$ for some $w \in \mathbb{Z}_q$. This $w$ is the discrete logarithm of $h$ with respect to $g$. Computing $w$ from $h$ is hard; computing $h$ from $w$ is easy. This asymmetry, the one-wayness that made Pedersen commitments binding, now enables something new.

The prover knows $w$. The verifier sees $h$ but cannot compute $w$ directly. The prover wants to convince the verifier that they know $w$ without revealing what $w$ is.

The naive approach fails immediately. If the prover just sends $w$, the verifier can check $g^w = h$, but the secret is exposed. If the prover sends nothing, the verifier has no basis for belief. There seems to be no middle ground.

Interactive proofs create that middle ground.

Schnorr’s Protocol

Claus Schnorr discovered the canonical solution in 1989. The protocol is three messages, two exponentiations for the prover, two exponentiations for the verifier. It is as close to optimal as plausible.

Public information: Group $\mathbb{G}$, generator $g$, target element $h$.

Private information (prover only): Witness $w$ such that $h = g^w$.

The protocol:

  1. Commitment. The prover samples a random $r \leftarrow \mathbb{Z}_q$ and computes $a = g^r$. The prover sends $a$ to the verifier.

  2. Challenge. The verifier samples a random $e \leftarrow \mathbb{Z}_q$ and sends $e$ to the prover.

  3. Response. The prover computes $z = r + w \cdot e \mod q$ and sends $z$ to the verifier.

  4. Verification. The verifier checks whether $g^z = a \cdot h^e$. Accept if yes, reject otherwise.

sequenceDiagram
    participant P as Prover (knows w)
    participant V as Verifier

    Note over P: Sample r ← ℤq
    Note over P: Compute a = gʳ
    P->>V: a (commitment)

    Note over V: Sample e ← ℤq
    V->>P: e (challenge)

    Note over P: Compute z = r + w·e
    P->>V: z (response)

    Note over V: Check gᶻ = a · hᵉ
    Note over V: Accept / Reject

That’s the entire protocol. Let’s understand why it works.

The Equation of a Line

Schnorr’s protocol is secretly proving you know the equation of a line. In $z = r + w \cdot e$, think of $w$ as the slope and $r$ as the y-intercept. The prover commits to the intercept ($r$, hidden as $a = g^r$). The verifier picks an x-coordinate ($e$). The prover reveals the y-coordinate ($z$). One point on a line doesn’t reveal the slope, but two points would. That’s why the protocol must be run once per challenge: a single $(e, z)$ pair is consistent with infinitely many slopes, but two pairs with the same intercept uniquely determine $w$.

Completeness. An honest prover with the correct $w$ always passes verification: $$g^z = g^{r + we} = g^r \cdot g^{we} = g^r \cdot (g^w)^e = a \cdot h^e$$

The algebra is straightforward. The commitment $a = g^r$ hides $r$; the response $z = r + we$ reveals a linear combination of $r$ and $w$; but one equation in two unknowns doesn’t determine either.

Soundness. A prover who doesn’t know $w$ can cheat only by guessing the challenge $e$ before committing. Once they send $a$, they’re locked in. For a random $e$, there’s exactly one $z$ that satisfies the verification equation (namely $z = r + we$). A cheating prover who doesn’t know $w$ cannot compute this $z$.

More precisely: suppose a cheater could answer two different challenges $e_1$ and $e_2$ for the same commitment $a$. Then we’d have: $$g^{z_1} = a \cdot h^{e_1} \quad \text{and} \quad g^{z_2} = a \cdot h^{e_2}$$

Dividing these equations: $$g^{z_1 - z_2} = h^{e_1 - e_2}$$

Taking discrete logarithms (which the extractor can do symbolically, as both exponents are known): $$w = \frac{z_1 - z_2}{e_1 - e_2} \mod q$$

A cheater who could answer two challenges must know $w$. This is special soundness: two accepting transcripts with different challenges allow extracting the witness.

The Rewinding Lemma

How do we get two transcripts with the same commitment $a$ but different challenges? In real life, we cannot. The prover sends $a$ only once, receives one challenge, and responds.

But in a thought experiment, we can rewind time. We let the prover send $a$, we send challenge $e_1$, and receive response $z_1$. Then we press “rewind,” return to the moment after they sent $a$, and send a different challenge $e_2$. If the prover can answer both, we solve the system of equations to extract $w$.

This “rewinding” argument is the mathematical foundation of proofs of knowledge. It’s why $\Sigma$-protocols prove you know something, not merely that something exists. An extractor with rewind powers could pry the secret from any successful prover.

Zero-knowledge (honest verifier). Here is where things become subtle. Consider a simulator that doesn’t know $w$ but wants to produce a valid-looking transcript $(a, e, z)$. The simulator proceeds backwards:

  1. Sample $e \leftarrow \mathbb{Z}_q$ (the challenge first!)
  2. Sample $z \leftarrow \mathbb{Z}_q$ (the response, uniform and independent)
  3. Compute $a = g^z \cdot h^{-e}$ (the commitment that makes the equation hold)

The Simulator’s Time Machine

In real execution, events unfold: Commitment → Challenge → Response. The simulator cheats time. It picks the answer first ($z$), invents a question that fits ($e$), then back-calculates what the commitment “must have been” ($a = g^z h^{-e}$). This temporal reversal is invisible in the final transcript. Anyone looking at $(a, e, z)$ cannot tell whether it was produced forward (by someone who knows $w$) or backward (by someone who cheated time). This is the heart of zero-knowledge: if a transcript can be faked without the secret, then having the secret cannot be what makes the transcript convincing. The transcript itself carries no information about $w$.

Check: $g^z = a \cdot h^e = g^z h^{-e} \cdot h^e = g^z$.

The transcript $(a, e, z)$ is valid. And its distribution is identical to a real transcript:

  • In a real transcript: $e$ is uniform (verifier’s randomness), $z = r + we$ is uniform (because $r$ is uniform), and $a = g^r$ is determined.
  • In a simulated transcript: $e$ is uniform (simulator’s choice), $z$ is uniform (simulator’s choice), and $a = g^z h^{-e}$ is determined.

Both distributions have $e$ and $z$ uniform and independent, with $a$ determined by the verification equation. They are identical.

This is honest-verifier zero-knowledge (HVZK): if the verifier samples $e$ honestly (uniformly at random), the transcript reveals nothing about $w$ that the verifier couldn’t have generated alone.

A Concrete Computation

Let’s trace through Schnorr’s protocol with actual numbers. Working in a small group makes the arithmetic visible.

Setup. Take the multiplicative group $\mathbb{Z}_{11}^* = {1, 2, 3, \ldots, 10}$, which has order 10. Let $g = 2$ (a generator).

Secret. The prover knows $w = 6$. The public value is: $$h = g^w = 2^6 = 64 \equiv 9 \pmod{11}$$

Round 1 (Commitment). The prover samples $r = 4$ and computes: $$a = g^r = 2^4 = 16 \equiv 5 \pmod{11}$$ The prover sends $a = 5$.

Round 2 (Challenge). The verifier samples $e = 7$ and sends it.

Round 3 (Response). The prover computes: $$z = r + w \cdot e = 4 + 6 \cdot 7 = 4 + 42 = 46 \equiv 6 \pmod{10}$$ (Note: we reduce modulo 10, the group order, not modulo 11.) The prover sends $z = 6$.

Verification. The verifier checks $g^z = a \cdot h^e$:

  • Left side: $g^z = 2^6 = 64 \equiv 9 \pmod{11}$
  • Right side: $a \cdot h^e = 5 \cdot 9^7 \pmod{11}$

To compute $9^7 \pmod{11}$: Note $9 \equiv -2 \pmod{11}$, so $9^7 = (-2)^7 = -128 \equiv -128 + 132 = 4 \pmod{11}$.

Thus $a \cdot h^e = 5 \cdot 4 = 20 \equiv 9 \pmod{11}$.

Both sides equal 9. The proof verifies.

Why the Order Matters: Commitment Before Challenge

The protocol’s security rests entirely on the order of messages. The prover commits to $a$ before seeing $e$. This temporal ordering is crucial.

Consider what happens if the order is reversed. Suppose the verifier sends $e$ first, then the prover responds with $(a, z)$. A cheating prover, without knowing $w$, could:

  1. Receive $e$
  2. Choose any $z$
  3. Compute $a = g^z h^{-e}$ (which satisfies the verification equation)
  4. Send $(a, z)$

This always passes verification! The protocol would have no soundness at all.

Commitment before challenge forces the prover to “bet” on a strategy before knowing what will be tested. A prover without the witness bets blind; a prover with the witness can always respond correctly.

This is the essence of interactive proof security: randomness forces the prover’s hand.

Pedersen Commitments and $\Sigma$-Protocols

Chapter 6 introduced Pedersen commitments: $C = g^m h^r$ commits to message $m$ with blinding factor $r$, where $g, h$ are generators with unknown discrete log relation. Now we complete the picture: $\Sigma$-protocols let you prove things about committed values.

The connection runs deeper than mere compatibility. Schnorr’s protocol and Pedersen commitments are algebraically the same construction. In Schnorr, the prover commits to $a = g^r$ and later reveals $z = r + we$ (a linear combination of the randomness and the secret). In Pedersen, the committer computes $C = g^m h^r$ (a linear combination of two generators weighted by the message and randomness). Both rely on the same hardness assumption; both achieve the same hiding property.

Recall from Chapter 6: a Pedersen commitment $C = g^m h^r$ is perfectly hiding (reveals nothing about $m$) and computationally binding (opening to a different value requires solving discrete log). The additive homomorphism $C_1 \cdot C_2 = g^{m_1+m_2} h^{r_1+r_2}$ lets us compute on committed values.

What Chapter 6 couldn’t address: how does a prover demonstrate they know the opening $(m, r)$ without revealing it? This is precisely what $\Sigma$-protocols provide.

Proving Knowledge of Openings

Schnorr’s protocol proves knowledge of one discrete log: given $h = g^w$, prove you know $w$. Pedersen commitments involve two exponents: $C = g^m h^r$. To prove you know the opening $(m, r)$, we need the two-dimensional generalization.

Statement. Given a Pedersen commitment $C$, prove knowledge of $(m, r)$ such that $C = g^m h^r$.

The structure mirrors Schnorr exactly (commit, challenge, respond) but now with two secrets handled in parallel.

The protocol:

  1. Commitment. Prover samples $d, s \leftarrow \mathbb{Z}_q$ and sends $a = g^d h^s$.

  2. Challenge. Verifier sends random $e \leftarrow \mathbb{Z}_q$.

  3. Response. Prover sends $z_1 = d + m \cdot e$ and $z_2 = s + r \cdot e$.

  4. Verification. Check $g^{z_1} h^{z_2} = a \cdot C^e$.

This is just two Schnorr protocols glued together. One proves knowledge of the message part ($m$, committed via $g^m$), the other proves knowledge of the randomness part ($r$, committed via $h^r$). The same challenge $e$ binds them, ensuring the prover cannot mix-and-match unrelated values.

The analysis parallels Schnorr’s protocol:

Completeness. $$g^{z_1} h^{z_2} = g^{d + me} h^{s + re} = g^d h^s \cdot (g^m h^r)^e = a \cdot C^e \checkmark$$

Special soundness. Two transcripts with the same $a$ but different challenges $e_1, e_2$ yield: $$g^{z_1^{(1)} - z_1^{(2)}} h^{z_2^{(1)} - z_2^{(2)}} = C^{e_1 - e_2}$$ From which both $m$ and $r$ can be extracted.

Zero-knowledge (honest verifier). Simulator picks $e, z_1, z_2$ uniformly, sets $a = g^{z_1} h^{z_2} \cdot C^{-e}$.

The prover demonstrates knowledge of the commitment opening without revealing what that opening is.

Proving Relations on Committed Values

The homomorphic property enables something remarkable: proving statements about committed values without revealing them.

Proving addition. Given commitments $C_1, C_2, C_3$, prove that the committed values satisfy $m_1 + m_2 = m_3$.

Consider the product $C_1 \cdot C_2 \cdot C_3^{-1}$. Expanding the Pedersen structure:

$$C_1 \cdot C_2 \cdot C_3^{-1} = g^{m_1} h^{r_1} \cdot g^{m_2} h^{r_2} \cdot g^{-m_3} h^{-r_3} = g^{m_1 + m_2 - m_3} \cdot h^{r_1 + r_2 - r_3}$$

If the relation $m_1 + m_2 = m_3$ holds, the $g$ exponent vanishes:

$$C_1 \cdot C_2 \cdot C_3^{-1} = g^0 \cdot h^{r_1 + r_2 - r_3} = h^{r_1 + r_2 - r_3}$$

The combined commitment collapses to a pure power of $h$. To prove the relation holds, the prover demonstrates knowledge of this exponent $r_1 + r_2 - r_3$ (a single Schnorr proof with base $h$ and public element $C_1 \cdot C_2 \cdot C_3^{-1}$).

Proving multiplication. This is harder. Pedersen commitments aren’t multiplicatively homomorphic. Given $C_1 = g^{m_1} h^{r_1}$, $C_2 = g^{m_2} h^{r_2}$, $C_3 = g^{m_3} h^{r_3}$, how do we prove $m_1 \cdot m_2 = m_3$?

The key insight is to change bases. Observe that: $$g^{m_3} = g^{m_1 \cdot m_2} = (g^{m_1})^{m_2}$$

If $C_3 = g^{m_1 m_2} h^{r_3}$, then $C_3$ can also be viewed as: $$C_3 = (g^{m_1})^{m_2} h^{r_3}$$

Now substitute $g^{m_1} = C_1 \cdot h^{-r_1}$: $$C_3 = (C_1 \cdot h^{-r_1})^{m_2} h^{r_3} = C_1^{m_2} \cdot h^{r_3 - r_1 m_2}$$

This expresses $C_3$ as a “Pedersen commitment with base $C_1$” to the value $m_2$ with blinding factor $r_3 - r_1 m_2$.

The prover runs three parallel $\Sigma$-protocols:

  1. Prove knowledge of $(m_1, r_1)$ opening $C_1$ (standard Pedersen opening)
  2. Prove knowledge of $(m_2, r_2)$ opening $C_2$ (standard Pedersen opening)
  3. Prove knowledge of $(m_2, r_3 - r_1 m_2)$ opening $C_3$ with respect to bases $(C_1, h)$

The third proof links to the second because the same $m_2$ appears. This linking requires careful protocol design, but the core technique is $\Sigma$-protocol composition with shared secrets.

Fiat-Shamir: From Interaction to Non-Interaction

Interactive proofs are impractical for many applications. A signature scheme cannot require real-time communication with every verifier. A blockchain proof must be verifiable by anyone, at any time, without the prover present.

The Fiat-Shamir transform removes interaction. The idea is elegant: replace the verifier’s random challenge with a hash of the transcript.

In Schnorr’s protocol:

  1. Prover computes $a = g^r$
  2. Instead of waiting for verifier’s $e$, prover computes $e = H(a)$ (or $H(g, h, a)$ for domain separation)
  3. Prover computes $z = r + we$
  4. Proof is $(a, z)$

Verification:

  1. Recompute $e = H(a)$
  2. Check $g^z = a \cdot h^e$

The transform works because $H$ is modeled as a random oracle: a function that returns uniformly random output for each new input. The prover cannot predict $H(a)$ before choosing $a$. Once $a$ is fixed, the hash determines $e$ deterministically. The prover faces a random challenge, just as in the interactive version.

In practice, $H$ is a cryptographic hash function like SHA-256. The random oracle model is an idealization (hash functions aren’t truly random functions) but the heuristic is empirically robust for well-designed protocols.

Schnorr signatures are the direct application. Given secret key $w$ and public key $h = g^w$:

  • Sign message $M$: Compute $a = g^r$, $e = H(h, a, M)$, $z = r + we$. Signature is $(a, z)$.
  • Verify: Check $g^z = a \cdot h^e$ where $e = H(h, a, M)$.

This is the foundation of EdDSA (Ed25519), now standard in TLS, SSH, and cryptocurrency systems. Bitcoin adopted Schnorr signatures in the 2021 Taproot upgrade.

Why Schnorr beats ECDSA. The equation $z = r + we$ is linear. This linearity enables:

  • Batch verification: Check many signatures faster than individually by taking random linear combinations (Schwartz-Zippel ensures invalid signatures can’t cancel)
  • Native aggregation: Multiple signers can combine signatures into one. MuSig2 produces a single 64-byte signature for $n$ parties that verifies against an aggregate public key
  • ZK-friendliness: No modular inversions (unlike ECDSA’s $s = k^{-1}(H(m) + rx)$), so Schnorr verification is cheap inside circuits

Compare to ECDSA: the $k^{-1}$ term makes the equation non-linear. You cannot simply add ECDSA signatures; the inverses don’t combine. This algebraic accident kept Bitcoin on ECDSA for a decade.

Composition: AND and OR

$\Sigma$-protocols compose cleanly, enabling proofs of complex statements from simple building blocks.

AND composition. To prove “I know $w_1$ such that $h_1 = g^{w_1}$ AND $w_2$ such that $h_2 = g^{w_2}$”:

  1. Run both protocols in parallel with independent commitments
  2. Use the same challenge $e$ for both
  3. Check both verification equations

If the prover knows both witnesses, they can respond to any challenge. If they lack either witness, they can’t respond correctly.

OR composition. To prove “I know $w_1$ OR $w_2$” (without revealing which):

The Card Trick Analogy

Imagine a magician holding two decks of cards. They claim: “I know the order of Deck A OR the order of Deck B.” You shuffle one deck and ask them to name the top card.

If the magician knows that deck’s order, they answer instantly. If they don’t, they use sleight of hand: they “force” the right card to the top, making it look like they predicted it all along.

In an OR-proof, the prover plays the magician. For the secret they know, they answer honestly. For the secret they don’t know, they use the Simulator (the “sleight of hand”) to produce a transcript that looks legitimate. The verifier sees two correct answers and cannot tell which was genuine knowledge and which was mathematical magic.

  1. For the witness you don’t know, simulate a transcript $(a_i, e_i, z_i)$ (using the honest-verifier simulator from the zero-knowledge property)
  2. For the witness you do know, commit honestly to $a_j$
  3. When you receive the verifier’s challenge $e$, set $e_j = e - e_i$
  4. Respond honestly to $e_j$ using your witness

The verifier checks:

  • Both verification equations hold
  • $e_1 + e_2 = e$

Concrete example. Alice knows the discrete log of $h_1 = g^{w_1}$ but not $h_2$. She wants to prove she knows at least one of them.

  1. Simulate the unknown: Alice picks $e_2 = 7$ and $z_2 = 13$ at random, then computes $a_2 = g^{z_2} h_2^{-e_2} = g^{13} h_2^{-7}$. This is a valid-looking transcript for $h_2$.

  2. Commit honestly for the known: Alice picks $r_1 = 5$ and computes $a_1 = g^{r_1} = g^5$.

  3. Send commitments: Alice sends $(a_1, a_2)$ to the verifier.

  4. Receive challenge: The verifier sends $e = 19$.

  5. Split the challenge: Alice sets $e_1 = e - e_2 = 19 - 7 = 12$. Now she must respond to challenge 12 for $h_1$.

  6. Respond honestly: Alice computes $z_1 = r_1 + w_1 \cdot e_1 = 5 + w_1 \cdot 12$.

  7. Send responses: Alice sends $(e_1, z_1, e_2, z_2) = (12, z_1, 7, 13)$.

The verifier checks $g^{z_1} = a_1 \cdot h_1^{e_1}$ and $g^{z_2} = a_2 \cdot h_2^{e_2}$, plus $e_1 + e_2 = 19$. Both equations hold. The verifier cannot tell which transcript was simulated; the simulated $(a_2, e_2, z_2)$ is statistically identical to an honest execution.

The prover can always succeed by simulating one protocol and honestly executing the other. The verifier cannot tell which is which; the simulated transcript is indistinguishable from a real one.

This is remarkable: you can prove you know one of two secrets without revealing which. Ring signatures, anonymous credentials, and many privacy-preserving constructions build on this technique.

Connection to Larger Systems

$\Sigma$-protocols appear as components within the complex proof systems of earlier chapters.

The inner product argument (Chapter 9) is a recursive $\Sigma$-protocol. Each round (commit to cross-terms $L, R$; receive challenge $u$; fold the vectors) follows the three-move structure. The recursion terminates when the vectors shrink to single elements, yielding logarithmic proof size.

Bulletproofs generalize the IPA to prove range statements and circuit satisfiability. The construction is layered: Pedersen vector commitments at the base, IPA for compression, $\Sigma$-protocols for linking claims. The entire system inherits honest-verifier zero-knowledge from its $\Sigma$-protocol core.

Polynomial commitment openings in KZG can be viewed through this lens too. The pairing check $e(C - g^v, g) = e(\pi, g^\tau - g^z)$ proves that the committed polynomial evaluates correctly at $z$. It’s not a three-move protocol per se, but it shares the algebraic structure: commitment (the polynomial commitment $C$), challenge (the evaluation point $z$), and verification equation (the pairing check).

Understanding $\Sigma$-protocols provides the vocabulary for understanding zero-knowledge more broadly. The simulator, the extractor, the honest-verifier assumption: these concepts appear in precisely the same form in systems a hundred times more complex.

Elliptic Curve Notation

Modern implementations use elliptic curves, where the group operation is written additively rather than multiplicatively:

MultiplicativeAdditive
$g^w$$w \cdot G$
$g^r \cdot g^s = g^{r+s}$$r \cdot G + s \cdot G = (r+s) \cdot G$
$h = g^w$$H = w \cdot G$

The Schnorr verification equation becomes: $$z \cdot G = A + e \cdot H$$

The mathematics is identical. The notation change reflects the underlying group structure: elliptic curve groups are abelian, naturally written additively. Every $\Sigma$-protocol translates directly; only the symbols change.

Key Takeaways

  1. Three messages suffice for zero-knowledge proofs of knowledge. Commit → Challenge → Response. The temporal ordering (commitment before challenge) is essential for soundness.

  2. Special soundness means two accepting transcripts with different challenges enable witness extraction. This makes $\Sigma$-protocols proofs of knowledge, not merely proofs of existence.

  3. Zero-knowledge via simulation: pick the challenge and response first, compute what the commitment must have been. The simulated transcript is indistinguishable from a real one, proving the verifier learns nothing beyond the statement’s truth.

  4. Schnorr’s protocol proves knowledge of a discrete logarithm: you know $w$ such that $h = g^w$. Verification: $g^z = a \cdot h^e$. It is the archetype.

  5. Proving Pedersen openings extends Schnorr to two dimensions. To prove knowledge of $(m, r)$ such that $C = g^m h^r$, commit to both exponents and respond with linear combinations.

  6. Relations on committed values reduce to simpler proofs. Addition: the product $C_1 \cdot C_2 \cdot C_3^{-1}$ collapses to $h^{r_1+r_2-r_3}$ when $m_1 + m_2 = m_3$, requiring only a single Schnorr proof. Multiplication requires base-changing tricks.

  7. Fiat-Shamir removes interaction: hash the commitment to derive the challenge. This yields Schnorr signatures (linear, aggregatable, ZK-friendly) and non-interactive proofs.

  8. Composition builds complex proofs from simple ones. AND runs protocols in parallel with a shared challenge. OR uses simulation for the unknown witness; the verifier cannot tell which branch was real.

  9. Connection to SNARKs: The inner product argument (Bulletproofs), KZG opening proofs, and recursive protocols all inherit the three-move structure and simulation-based security of $\Sigma$-protocols.

  10. Minimal assumptions: $\Sigma$-protocols require only the discrete logarithm assumption. No pairings, no trusted setup, no hash functions beyond Fiat-Shamir.