Zero-Knowledge Proofs

Wikipedia (CC BY-SA 4.0) · Zero-knowledge proof

A zero-knowledge proof lets you prove you know a secret without revealing the secret itself. The verifier learns nothing except that the statement is true. This is one of the deepest ideas in cryptography: conviction without information.

The Ali Baba cave

Imagine a circular cave with a magic door at the back. The prover enters and takes path A or B (the verifier does not see which). The verifier shouts "come out path A" or "come out path B." If the prover knows the secret to open the door, they can always comply. If they do not, they have a 50% chance of being on the wrong side. After 20 rounds, a fake prover's odds of passing are less than one in a million.

Scheme

; Ali Baba cave simulation
; The prover either knows the secret (can use door) or doesn't.

; Simple pseudo-random (linear congruential)
(define seed 42)
(define (rand)
  (set! seed (modulo (+ (* seed 1103515245) 12345) 2147483648))
  (modulo seed 2))

(define (simulate-cave knows-secret rounds)
  (define (go round passed)
    (if (> round rounds)
        passed
        (let* ((prover-path (rand))        ; 0=A, 1=B
               (challenge (rand))          ; 0=A, 1=B
               (can-comply (or knows-secret
                              (= prover-path challenge))))
          (go (+ round 1)
              (and passed can-comply)))))
  (go 1 #t))

; Honest prover (knows the secret): always passes
(display "Honest prover (20 rounds): ")
(display (simulate-cave #t 20)) (newline)

; Fake prover: almost certainly caught
(display "Fake prover trials:") (newline)
(define (run-fakes n caught)
  (if (= n 0) caught
      (run-fakes (- n 1)
                 (if (simulate-cave #f 20) caught (+ caught 1)))))

(define total 10)
(define caught (run-fakes total 0))
(display "  ") (display caught) (display "/")
(display total) (display " caught")

; Ali Baba cave simulation
; The prover either knows the secret (can use door) or doesn't.

; Simple pseudo-random (linear congruential)
(define seed 42)
(define (rand)
  (set! seed (modulo (+ (* seed 1103515245) 12345) 2147483648))
  (modulo seed 2))

(define (simulate-cave knows-secret rounds)
  (define (go round passed)
    (if (> round rounds)
        passed
        (let* ((prover-path (rand))        ; 0=A, 1=B
               (challenge (rand))          ; 0=A, 1=B
               (can-comply (or knows-secret
                              (= prover-path challenge))))
          (go (+ round 1)
              (and passed can-comply)))))
  (go 1 #t))

; Honest prover (knows the secret): always passes
(display "Honest prover (20 rounds): ")
(display (simulate-cave #t 20)) (newline)

; Fake prover: almost certainly caught
(display "Fake prover trials:") (newline)
(define (run-fakes n caught)
  (if (= n 0) caught
      (run-fakes (- n 1)
                 (if (simulate-cave #f 20) caught (+ caught 1)))))

(define total 10)
(define caught (run-fakes total 0))
(display "  ") (display caught) (display "/")
(display total) (display " caught")

Interactive vs non-interactive

The cave protocol is interactive: the verifier must be online, issuing fresh challenges. A non-interactive proof replaces the verifier with a hash function (the Fiat-Shamir heuristic). The prover hashes the commitment to generate their own challenge. Anyone can verify the proof later without interaction.

Scheme

; Fiat-Shamir heuristic: replace the verifier with a hash.
; Interactive: verifier sends challenge c
; Non-interactive: c = hash(commitment)

; Schnorr identification protocol (simplified)
; Prover knows secret x, public key y = g^x mod p
; 1. Prover picks random r, sends commitment t = g^r mod p
; 2. Challenge c = hash(t) (non-interactive)
; 3. Prover sends s = r + c*x
; 4. Verifier checks g^s = t * y^c

(display "Interactive ZKP:") (newline)
(display "  Prover -> commitment -> Verifier") (newline)
(display "  Verifier -> challenge -> Prover") (newline)
(display "  Prover -> response -> Verifier checks") (newline)
(newline)
(display "Non-interactive (Fiat-Shamir):") (newline)
(display "  challenge = hash(commitment)") (newline)
(display "  Proof = (commitment, response)") (newline)
(display "  Anyone can verify, anytime")

ZK-SNARKs

ZK-SNARK stands for Zero-Knowledge Succinct Non-interactive Argument of Knowledge. "Succinct" means the proof is tiny (a few hundred bytes) regardless of the computation's size. "Non-interactive" means no back-and-forth. ZK-SNARKs let you prove you ran an arbitrary computation correctly, without revealing the inputs.

Scheme

; ZK-SNARKs: what each word means

(display "Zero-Knowledge:") (newline)
(display "  Verifier learns nothing beyond validity") (newline)
(newline)
(display "Succinct:") (newline)
(display "  Proof size is O(1), not O(computation)") (newline)
(display "  A proof for 1M operations is the same") (newline)
(display "  size as a proof for 10 operations") (newline)
(newline)
(display "Non-interactive:") (newline)
(display "  Single message from prover to verifier") (newline)
(newline)
(display "Argument of Knowledge:") (newline)
(display "  The prover must actually know a witness") (newline)
(display "  (not just that one exists)") (newline)
(newline)
(display "Applications:") (newline)
(display "  - Private transactions (Zcash)") (newline)
(display "  - Credential verification without") (newline)
(display "    revealing the credential") (newline)
(display "  - Verifiable computation (prove you") (newline)
(display "    ran the code correctly)")

Neighbors

This series

Foundations (Wikipedia)

← Digital Signatures by june.kim TLS Handshake →