Zero-knowledge proof

The three conditions

A zero-knowledge proof is defined as one satisfying the following three conditions. The first is completeness: if the claim really is correct, an honest prover can convince the verifier. The second is soundness: if the claim is false, the probability that any prover, however devious, can convince the verifier is negligibly small. The third is the zero-knowledge property: the information the verifier gains through the dialogue goes no further than the single fact that the claim is correct.

The formalization of the zero-knowledge property cannot simply be written as "learns nothing". What is used instead is a form showing that the record the verifier sees in the dialogue can be produced by the verifier alone, without interacting with the prover. If the record of the dialogue can be made up, then that record contains no information known only to the prover. This argument by a "simulator" reduces the vague intuition of zero knowledge to a condition that can be handled mathematically.

That soundness holds only probabilistically is an important property of the method. If the probability that cheating succeeds in one round of dialogue is one half, then repeating it independently 20 times brings it down to about one in a million. The proof is secured not in the form of "absolutely correct" but of "the probability of cheating can be made as small as one likes".

Ali Baba's cave

The analogy of the cave in "How to Explain Zero-Knowledge Protocols to Your Children", presented at CRYPTO in 1989, is often cited as an intuitive explanation^※1. There is a ring-shaped cave; entering from the mouth, the path forks in two, and the dead ends at the back are connected by a door that opens on a magic word. The prover wants to show that they know this word without disclosing it.

The procedure runs as follows. The verifier waits at the entrance, and the prover goes in along whichever path they like. Once the prover is out of sight, the verifier shouts one of "come out from the right" or "come out from the left". If the prover knows the word, they can come out from either side by passing through the door. If not, they can only come out when the path chosen at the start happens to match the instruction. One round is a one-in-two guess, but succeeding dozens of times in a row is effectively impossible. And what the verifier saw is only the fact that the prover came out from the side instructed; the word itself is never conveyed.

Extension to all of NP

The initial constructions were limited to number-theoretic claims such as quadratic residuosity and discrete logarithms. This was generalized by the 1986 presentation of Oded Goldreich, Micali and Avi Wigderson (journal version in the Journal of the ACM, volume 38, 1991^※2), which showed that, under the assumption that secure encryption functions exist, every language in NP has a zero-knowledge proof.

NP is the class of problems for which, given an answer, it can be verified efficiently that the answer is correct. This result means that any such problem can be converted into a method for "proving only that one holds the answer, without disclosing the answer". It marks the turning point at which the character of the work changed from a tool resting on individual mathematical structures into a general technique applicable over a wide range. Goldwasser and Micali received the 2012 Turing Award for work in this line, and the 1985 paper was also recognized by the first Gödel Prize^※3.

Making it non-interactive, and practical use

The original definition presupposes a dialogue in which prover and verifier exchange messages many times, and as such it cannot be left behind as a record. The Fiat-Shamir transform replaces the role of the random numbers thrown by the verifier with the output of a hash function, folding the dialogue into a single message. It is a technique that holds on the premise of idealizing the hash as a random function (the random oracle model). Making it non-interactive does not preserve all of the properties the interactive version had; deniability, the ability to claim later that "no such proof was made", is lost.

What came into wide use in implementation are methods in which the length of the proof and the verification time are extremely small compared with the scale of the original computation. The line called zk-SNARK falls here, and the cryptocurrency Zcash uses a protocol called Groth16 to hide the contents of payments on a public ledger. The weakness of this line is that it requires a "trusted setup" generating secret parameters before use; if the secret from the generation has leaked, false proofs can be made. What removed this need is the method called zk-STARK, which tends to have larger proof sizes in exchange for transparency (no setup required).