A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
A zero-knowledge proof lets a prover convince a verifier that a statement is true without revealing any information beyond the truth of the statement. It satisfies three properties: completeness (honest prover convinces honest verifier), soundness (no cheating prover convinces the verifier of a false statement), and zero-knowledge (the verifier learns nothing beyond the statement's validity, formalized via simulation — a simulator can produce transcripts indistinguishable from real interactions without knowing the witness). Every NP language has a zero-knowledge proof (assuming OWFs). ZK proofs are foundational for privacy-preserving authentication, blockchain privacy (Zcash), and verifiable computation.
Imagine you know the password to a vault, and you want to convince a guard that you know it — without ever revealing the password. Not a single bit of it. Not even information that helps the guard narrow down what the password might be. This is the promise of zero-knowledge proofs: a prover can convince a verifier that a statement is true while revealing absolutely nothing beyond the truth of the statement. The three defining properties are: completeness (an honest prover with a valid witness always convinces the verifier), soundness (a cheating prover without a witness fails with overwhelming probability), and zero-knowledge (the verifier learns nothing they couldn't have computed on their own).
Zero-knowledge is formalized through the simulation paradigm. A protocol is zero-knowledge if there exists an efficient simulator that, without knowing the witness, can generate fake transcripts that are computationally indistinguishable from real prover-verifier interactions. If such a simulator exists, the real interaction provides no computational advantage to the verifier — whatever they could compute from the transcript, they could compute without it (by running the simulator). This definition elegantly handles arbitrary verifier strategies, including malicious verifiers who deviate from the protocol.
The most remarkable theoretical result is that every NP language has a zero-knowledge proof, assuming one-way functions exist. Goldreich, Micali, and Wigderson proved this in 1987 by constructing a ZK proof for graph 3-coloring (NP-complete) using commitment schemes. The prover commits to a random permutation of a valid 3-coloring, the verifier challenges by selecting a random edge, and the prover opens the commitments for that edge's two vertices, showing they have different colors. After enough rounds, the verifier is convinced the graph is 3-colorable, but learns nothing about which coloring the prover used (because each round reveals only two of three color classes under a random permutation). Since every NP problem reduces to 3-coloring, this gives ZK proofs for all NP statements.
Practical zero-knowledge has exploded in recent years, driven by blockchain applications. zk-SNARKs (Succinct Non-interactive Arguments of Knowledge) compress a proof to constant size (a few hundred bytes) verifiable in milliseconds, regardless of the statement's complexity. Zcash uses zk-SNARKs to prove that a cryptocurrency transaction is valid (inputs equal outputs, sender has sufficient balance, no double-spending) without revealing the sender, recipient, or amount. zk-STARKs achieve similar goals without a trusted setup, using hash functions instead of elliptic curves, but with larger proof sizes. These technologies represent a transition of zero-knowledge from a theoretical curiosity to a deployed infrastructure component for privacy and scalability in distributed systems.