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.
Every new ZK scheme in the literature is judged on three properties. Miss one and you don't have a valid ZK proof — you have either an insecure system or a revealing one. Completeness says honest provers always succeed; soundness says cheaters almost never do; zero-knowledge says verifiers learn only the statement. This task nails these three into muscle memory by showing a protocol that passes each one separately and a protocol that fails each one separately.
Four concrete protocols on the discrete log statement 'I know x such that g^x = y': (1) honest → passes all three. (2) 'Trust me bro' (prover sends x) → completeness + soundness but NOT zero-knowledge. (3) 'Fake commitment' (prover sends random number as commitment) → zero-knowledge but NOT soundness. (4) 'Always reject' (verifier always returns false) → soundness + zero-knowledge but NOT completeness. Reading all four side-by-side crystallises what each property protects.
// main.go — each protocol fails a different pillar
package main
import (
"fmt"
"math/big"
"math/rand"
)
var (
p int64 = 23
g int64 = 5
x int64 = 7 // prover's secret
y = modpow(g, x, p) // public statement: "I know x s.t. g^x = y"
)
func modpow(base, exp, mod int64) int64 {
r := new(big.Int).Exp(big.NewInt(base), big.NewInt(exp), big.NewInt(mod))
return r.Int64()
}
// Protocol 1: Honest Schnorr (passes all three)
func honestProve() (int64, int64, int64) {
r := rand.Int63n(p-1) + 1
commit := modpow(g, r, p)
challenge := rand.Int63n(p-1) + 1
response := (r + challenge*x) % (p - 1)
return commit, challenge, response
}
func honestVerify(commit, challenge, response int64) bool {
lhs := modpow(g, response, p)
rhs := (commit * modpow(y, challenge, p)) % p
return lhs == rhs // completeness ✓, soundness ✓, ZK ✓
}
// Protocol 2: "Trust me" — not ZK
func trustmeProve() int64 {
return x // reveals secret; ZK is broken
}
// Protocol 3: cheater — not sound
func cheaterProve() (int64, int64, int64) {
r := rand.Int63n(p-1) + 1
commit := modpow(g, r, p)
challenge := rand.Int63n(p-1) + 1
response := rand.Int63n(p-1) + 1 // random — 1/(p-1) chance to verify
return commit, challenge, response
}
// Protocol 4: "Always reject" — not complete
func rejectVerify(commit, challenge, response int64) bool {
return false // even honest provers are rejected
}
func main() {
commit, challenge, response := honestProve()
fmt.Println("honest verify honest:", honestVerify(commit, challenge, response)) // true (completeness ✓)
successes := 0
for i := 0; i < 10000; i++ {
c, ch, resp := cheaterProve()
if honestVerify(c, ch, resp) {
successes++
}
}
fmt.Printf("cheater success rate: %.4f\n", float64(successes)/10000.0) // ~1/(p-1)
commit2, challenge2, response2 := honestProve()
fmt.Println("reject any:", rejectVerify(commit2, challenge2, response2)) // false (completeness ✗)
}go run main.goUse these three in order. Each builds on the one before.
In one paragraph, explain completeness, soundness, and zero-knowledge — one sentence per property, and one example of a protocol that fails each.
Walk me through the simulator-based definition of zero-knowledge: what does it mean to say 'the verifier could have produced the transcript themselves,' and why is this the correct formal definition?
Given I'm designing a protocol where I want computational soundness (rather than statistical) — i.e., I'm OK if a computationally bounded adversary cannot cheat — what primitives can I rely on (hash functions, DLP, LWE) and how does this change the security argument versus statistical soundness?