Zk Proofs · Completeness · Soundness · Zero-Knowledge · Cryptography & Zero-Knowledge Lesson 13

A zero-knowledge proof lets a prover convince a verifier that some statement is true without revealing why it is true. Three properties define it. Completeness: an honest prover always convinces an honest verifier. Soundness: a cheating prover is caught except with negligible probability. Zero-knowledge: the verifier learns nothing beyond the bare fact that the statement holds.

The classic intuition is a cut-and-choose game: each round, a cheater who lacks the secret can fake an answer only half the time, so after n rounds their odds of getting away with it are 2⁻ⁿ — vanishingly small. Zero-knowledge is captured by the idea that the entire transcript could have been simulated without the secret, so it cannot leak it. The demo runs many rounds to show completeness and soundness numerically.

Power-ups you unlock

Completeness: an honest prover always convinces an honest verifier

Soundness: a cheating prover is caught except with negligible probability

Zero-knowledge: the verifier learns nothing beyond the statement being true

Repeated challenge rounds drive the soundness error toward zero (2⁻ⁿ)

The transcript could have been simulated → it leaks no secret

The Collision attacks — common mistakes

Confusing zero-knowledge (leaks nothing) with mere privacy

Assuming one round is enough — soundness needs many rounds or a big field

Thinking a proof of knowledge and a proof of a fact are identical

Believing ZK hides the statement — only the witness is hidden

Boss battleSimulate many challenge rounds and show an honest prover always passes while a cheater passes only with probability 2⁻ʳᵒᵘⁿᵈˢ.

Example code

<!doctype html><html><head><meta charset="utf-8"></head> <body style="background:#06040d;color:#e6e0ff;font-family:monospace;padding:20px"><pre id="o"></pre> <script> // the 3 properties via a cut-and-choose simulation. const round = (knows)=> knows ? true : Math.random() < 0.5; // pass this round? const trial = (knows, rounds)=>{ for(let i=0;i<rounds;i++) if(!round(knows)) return false; return true; }; const rounds = 20, N = 100000; let honest=0, cheat=0; for(let i=0;i<N;i++){ if(trial(true,rounds)) honest++; if(trial(false,rounds)) cheat++; } document.getElementById('o').textContent = [ rounds + ' challenge rounds · ' + N.toLocaleString() + ' trials', 'COMPLETENESS — honest prover passes: ' + (100*honest/N).toFixed(1) + '% (always)', 'SOUNDNESS — cheater passes: ' + cheat + '/' + N + ' (≈ 2^-' + rounds + ')', 'ZERO-KNOWLEDGE — verifier learns only pass/fail, never the secret', 'soundness error halves each round → negligible fast' ].join('\n'); </script></body></html>

▶ Open the interactive comic issue

zk proofs · completeness · soundness · zero-knowledge

Power-ups you unlock

The Collision attacks — common mistakes

Example code