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.
Before talking about zero-knowledge, you have to internalise what a 'proof' is in cryptography, which is subtly different from what a mathematician means. To a mathematician, a proof is a sequence of deductions convincing a skeptical reader that a claim holds. To a cryptographer, a proof is a protocol between a prover and a verifier such that (a) an honest prover always convinces the verifier (completeness), (b) a cheating prover fails with overwhelming probability (soundness), and (c) optionally, the verifier learns nothing beyond the claim itself (zero-knowledge). These three properties — completeness, soundness, zero-knowledge — are the three pillars every ZK scheme must satisfy. Understanding them individually makes every subsequent concept (succinctness, argument-of-knowledge, simulator, extractor) straightforward.
Graph 3-coloring as a warm-up. Prover knows a valid 3-coloring of a graph; verifier wants to be convinced without seeing the coloring. Commit to each node's color; verifier picks an edge; prover reveals the two endpoints' colors. If they're different, one round is convincing. Two symbols carry the whole soundness argument: let |E| be the number of edges in the graph (3 for the triangle below) and R the number of rounds you repeat the protocol (the ROUNDS constant in the code). A cheating prover who lacks a valid coloring must have at least one bad edge, so a uniformly random edge catches the lie with probability at least 1/|E| each round — and survives a single round with probability at most 1 − 1/|E|. Across R independent rounds the cheat's success bound is therefore (1 − 1/|E|)^R, which shrinks exponentially in R. The 'commit-challenge-reveal' shape is the template of every interactive ZK proof.
// main.go — interactive ZK proof of 3-colorability
// Run: go run main.go
package main
import (
"crypto/rand"
"crypto/sha256"
"fmt"
"math/big"
)
func commit(color byte, nonce []byte) [32]byte {
data := append(nonce, color)
return sha256.Sum256(data)
}
type Round struct {
commits map[string][32]byte
permuted map[string]byte
nonces map[string][]byte
}
func proverRound(coloring map[string]int) Round {
// Fresh random permutation of colors each round
perm := [3]byte{0, 1, 2}
// Fisher-Yates shuffle via crypto/rand
for i := 2; i > 0; i-- {
n, _ := rand.Int(rand.Reader, big.NewInt(int64(i+1)))
j := n.Int64()
perm[i], perm[j] = perm[j], perm[i]
}
permuted := make(map[string]byte)
nonces := make(map[string][]byte)
commits := make(map[string][32]byte)
for v, c := range coloring {
permuted[v] = perm[c]
nonce := make([]byte, 16)
rand.Read(nonce)
nonces[v] = nonce
commits[v] = commit(perm[c], nonce)
}
return Round{commits, permuted, nonces}
}
func verifierChallenge(edges [][2]string) [2]string {
n, _ := rand.Int(rand.Reader, big.NewInt(int64(len(edges))))
return edges[n.Int64()]
}
func verifierCheck(commitU, commitV [32]byte, cu, cv byte, nonceU, nonceV []byte) bool {
if commit(cu, nonceU) != commitU {
return false
}
if commit(cv, nonceV) != commitV {
return false
}
if cu == cv {
return false // two adjacent nodes must differ
}
return true
}
func main() {
// Example: triangle graph (3 nodes, 3 edges)
coloring := map[string]int{"A": 0, "B": 1, "C": 2}
edges := [][2]string{{"A", "B"}, {"B", "C"}, {"A", "C"}}
const rounds = 128
for i := 0; i < rounds; i++ {
r := proverRound(coloring)
e := verifierChallenge(edges)
u, v := e[0], e[1]
ok := verifierCheck(
r.commits[u], r.commits[v],
r.permuted[u], r.permuted[v],
r.nonces[u], r.nonces[v],
)
if !ok {
panic("verification failed")
}
}
fmt.Println("128 rounds verified — cheating prover success bound: (1 - 1/|E|)^128 ≈ 0")
}go run main.goUse these three in order. Each builds on the one before.
In one paragraph, explain what a cryptographic proof system is — the three properties of completeness, soundness, and zero-knowledge — and how it differs from a mathematician's notion of a proof.
Walk me through the graph 3-coloring ZK protocol step by step: how the prover commits to a permuted coloring, why the verifier's random edge query forces the prover to commit to a valid coloring, and why the permutation hides the actual color labels.
Given I want to prove I know a Hamiltonian cycle in a graph without revealing it (Blum 1986), walk me through the protocol structure and the concrete soundness error per round. Compare the proof size and round count to the 3-coloring protocol.