Ever wondered what a $\Sigma$-protocol is?

Fun fact: the name “Sigma” comes from the Greek letter $\Sigma$, which looks a bit like a zigzag, just like the three-step process this protocol performs 😊

Sigma is probably the most basic “zero-knowledge proof of knowledge” 😁 protocol: prove you know something secret, without revealing the secret itself.

You, the prover, know some private value(s) that satisfy a relation, and want to convince a verifier that this is true, without leaking $x$.

The three steps Sigma dance

1. Commitment: the prover sends an initial commitment to the verifier
2. Challenge: the verifier replies with a random challenge
3. Response: the prover answers using the secret and the challenge

From the response, the verifier becomes convinced that the prover must know a valid witness satisfying the relation, all without ever seeing it.

Later on, we’ll see how step 2 can be made non-interactive with Fiat-Shamir.

Notation

Cryptographers often write things using multiplicative notation (like $g^x \cdot h^r$), but since most real implementations use elliptic curves, I’ll use additive notation ($x \cdot G + r \cdot H$).

Same math, different flavor.

In this article, we’ll use:

• $G$: an elliptic curve generator
• $H$: another, independent generator

The Schnorr protocol

The Schnorr protocol is the simplest example of a $\Sigma$-protocol, the “hello world” of zero-knowledge proofs 😉

Here’s the setup:

You, the prover, want to show that you know a witness $x$ such that