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.
A sigma protocol is any 3-move ZK proof with the 'commit-challenge-response' shape. Schnorr is a sigma. Chaum-Pedersen (proving equality of discrete logs) is a sigma. Fujisaki-Okamoto (proving 'I know the factorization of N') is a sigma. These building blocks compose: AND-composition proves conjunctions of sigma statements; OR-composition proves disjunctions without revealing which is true. Range proofs, set membership proofs, and most privacy-preserving primitives are sigma protocols stitched together. The algebra is always the same shape, which is why learning sigma protocols is the single most practical ZK skill.
Chaum-Pedersen: prove 'g^x = y AND h^x = z' — i.e., the same x is the discrete log in two different bases. Prover picks r, sends R₁ = g^r, R₂ = h^r. Verifier sends c. Prover sends s = r + c·x. Verifier checks both: g^s = R₁ · y^c, h^s = R₂ · z^c. This is the primitive behind VRFs and many privacy coins.
// main.go — prove same discrete log under two bases (Chaum-Pedersen)
// run: go mod init demo && go get github.com/decred/dcrd/dcrec/secp256k1/v4 && go run main.go
package main
import (
"crypto/rand"
"crypto/sha256"
"fmt"
"math/big"
"github.com/decred/dcrd/dcrec/secp256k1/v4"
)
var curve = secp256k1.S256()
var order = curve.N
// point wraps (X, Y) so we can do scalar mul / add cleanly
type point struct{ x, y *big.Int }
func genPoint() point {
x, y := curve.ScalarBaseMult(big.NewInt(1).Bytes())
return point{x, y}
}
func scalarMul(k *big.Int, p point) point {
x, y := curve.ScalarMult(p.x, p.y, k.Bytes())
return point{x, y}
}
func addPoints(a, b point) point {
x, y := curve.Add(a.x, a.y, b.x, b.y)
return point{x, y}
}
func pointString(p point) string {
return fmt.Sprintf("(%s,%s)", p.x.String(), p.y.String())
}
func secondGen(seed []byte) point {
h := sha256.Sum256(seed)
k := new(big.Int).SetBytes(h[:])
k.Mod(k, order)
x, y := curve.ScalarBaseMult(k.Bytes())
return point{x, y}
}
// G1 is the standard secp256k1 base point
var G1 = func() point { x, y := curve.ScalarBaseMult(big.NewInt(1).Bytes()); return point{x, y} }()
var G2 = secondGen([]byte("chaum-pedersen-g2"))
func hashToScalar(parts ...string) *big.Int {
h := sha256.New()
for _, p := range parts {
h.Write([]byte(p))
}
return new(big.Int).Mod(new(big.Int).SetBytes(h.Sum(nil)), order)
}
func randScalar() *big.Int {
buf := make([]byte, 32)
rand.Read(buf)
return new(big.Int).Mod(new(big.Int).SetBytes(buf), order)
}
func main() {
x := randScalar()
Y1 := scalarMul(x, G1)
Y2 := scalarMul(x, G2)
// prove
r := randScalar()
R1, R2 := scalarMul(r, G1), scalarMul(r, G2)
c := hashToScalar(pointString(Y1), pointString(Y2), pointString(R1), pointString(R2)) // Fiat-Shamir
s := new(big.Int).Mod(new(big.Int).Add(r, new(big.Int).Mul(c, x)), order)
// verify
lhs1 := scalarMul(s, G1)
rhs1 := addPoints(R1, scalarMul(c, Y1))
lhs2 := scalarMul(s, G2)
rhs2 := addPoints(R2, scalarMul(c, Y2))
ok := lhs1.x.Cmp(rhs1.x) == 0 && lhs1.y.Cmp(rhs1.y) == 0 &&
lhs2.x.Cmp(rhs2.x) == 0 && lhs2.y.Cmp(rhs2.y) == 0
fmt.Println("same-dlog NIZK:", ok)
// OR-composition: prove "I know x1 s.t. Y1 = x1·G OR I know x2 s.t. Y2 = x2·G"
// without revealing which. Used in ring signatures (Monero), mixes, and voting.
}go run main.goUse these three in order. Each builds on the one before.
In one paragraph, explain sigma protocols — the three-move structure, why they're called 'sigma,' and why they compose via AND and OR in clean ways.
Walk me through the OR-composition of sigma protocols: how does a prover who only knows one of two witnesses produce a transcript that proves the disjunction without revealing which, and why does special soundness require the challenges to satisfy a specific linear relation?
I'm building a decentralised voting system where each voter proves 'I'm an authorised voter (ring membership) AND I vote yes-or-no (disjoint choice) AND this is my first vote.' Walk me through the sigma protocol composition and where the proof size blows up.