Zero bits leaked: what a zero-knowledge proof actually proves

Part 1 of Zero Knowledge, Full Proof, a series on zero-knowledge proofs and privacy on-chain.

In 2020 I started reading crypto whitepapers, beginning with Vitalik Buterin’s Ethereum whitepaper [1], shown above. The first thing one notices is how public everything is. The whitepaper describes the ledger of a cryptocurrency such as Bitcoin as “a state transition system”: a state, which records who owns what, and transactions that move the ledger from one state to the next. Every full node applies every transaction in order to check it. That is the whole design: nobody has to trust anybody, because everybody can check.

The price of this design is that checking and seeing become the same thing. To verify a transaction, one has to read it.

Zero-knowledge proofs pull the two apart: they make it possible to check a claim without seeing the data behind it. “Zero knowledge” sounds like marketing. It is not. It is a precise mathematical statement, and the precision is the interesting part.

A statement and a secret

The idea, and the name, come from a 1985 paper by Shafi Goldwasser, Silvio Micali and Charles Rackoff [2]. In the language used today, every zero-knowledge proof involves two objects: a public statement and a private witness. Three examples make the distinction concrete. The first is the statement “I know the password whose hash is this string”, whose witness is the password. The second is “this transaction spends coins I own, and the amounts balance”, whose witness is the coins, the keys and the amounts. The third is “these 1,000 transfers were applied to the ledger correctly”, whose witness is the transfers themselves.

The prover holds the witness; the verifier holds only the statement. A zero-knowledge proof convinces the verifier that the statement is true (and, in the variants that blockchains use, that the prover actually knows a witness) without handing the witness over. To deserve the name, it must satisfy three properties.

The first is completeness: if the statement is true and the prover follows the protocol honestly, the verifier accepts.

The second is soundness: if the statement is false, no prover, however clever, can make the verifier accept, except with negligible probability.

The third is zero knowledge: the verifier learns that the statement is true, and nothing else about the witness.

The first two properties make it a proof. The third is what makes it strange.

A proof for a colour-blind friend

The cleanest example I know needs two balls and a friend. The balls are identical except that one is red and one is green. The friend is red-green colour-blind and suspects the difference is made up. The goal is to convince them the balls really are different colours, without telling them which one is red.

They take one ball in each hand and put their hands behind their back. Out of my sight, they flip a coin: heads, they swap the balls; tails, they keep them where they were. Then they show me the balls again, and I say “swapped” or “kept”.

All three properties can be read off this game. First, completeness: if the balls really are different, I can see the answer every time. Second, soundness: if they were secretly the same colour, I would be guessing, and I would be right half the time. One round proves little, but the rounds are independent, so the chance that a guesser survives 20 rounds is (1/2)²⁰, about one in a million. One never obtains certainty; one repeats the experiment until the probability of error is smaller than anything that matters.

Third, zero knowledge: my friend learns nothing about which ball is red. They already knew whether they swapped, so my answer only tells them something they could have written down themselves.

What “learns nothing” means

That last observation is, in fact, the definition. Goldwasser, Micali and Rackoff made “learns nothing” precise with a thought experiment [2]. Imagine a simulator: a program that does not know the witness, but produces transcripts of the conversation anyway. If its fake transcripts cannot be told apart from real ones, then the real conversation cannot contain the witness, because anything the verifier could extract from a real transcript, it could equally have extracted from a fake one it made by itself.

For the balls, the simulator is trivial: flip the coin, then write down the matching answer.

Round	Real run	Simulated, no colours seen
1	heads → “swapped”	tails → “kept”
2	tails → “kept”	heads → “swapped”
3	heads → “swapped”	heads → “swapped”
4	tails → “kept”	tails → “kept”

Both columns are random coin flips, each followed by the matching answer. Looking at a transcript, nobody can tell which one needed someone to see the colours.

Loosely, I read this as a statement about information. Before the proof, the verifier does not know whether the claim is true; afterwards, they do. That is at most one bit, and about the witness itself, zero bits leaked. (The formal definition is about indistinguishability rather than Shannon entropy, but the intuition holds.)

There is an obvious objection. If a simulator can fake a convincing transcript, why cannot a cheating prover do the same? The answer lies in the order of events. The simulator chooses the challenge before it writes the answer, or rewinds and tries again; a real prover has to answer a challenge it could not predict. It follows that a recording of an interactive zero-knowledge proof convinces nobody else, since for all a viewer knows, it was staged. The classic illustration of these ideas is the story of Ali Baba’s cave and its magic door, told by Quisquater and his co-authors at CRYPTO ’89 [3].

Taking out the conversation

The ball game is a conversation, and blockchains cannot hold conversations. A smart contract cannot flip a secret coin and wait for your reply, and a proof published on a ledger has to convince everyone who reads it later, not just one verifier in the room.

The fix is the Fiat–Shamir transform, introduced in 1986 [4]. In protocols where the verifier’s only job is to send random challenges, the prover replaces those challenges with a hash of everything it has sent so far. Since the prover cannot predict the hash before committing to its messages, the hash plays the part of an honest coin, and the whole exchange collapses into a single message that anyone can check at any time. Strictly speaking, this is a heuristic: its security is argued in an idealised setting in which the hash function is treated as a truly random function, the random-oracle model [5].

This reverses the point about recordings. A non-interactive proof convinces anyone who reads it, precisely because nobody, not even the prover, got to choose the challenge.

Succinct, and why that matters more than it sounds

The proofs that blockchains use have one more property. A zk-SNARK is a zero-knowledge Succinct Non-interactive ARgument of Knowledge: the proof is short and quick to check, however large the computation behind it. The word argument is deliberate: soundness holds against provers with realistic computing power, not against unbounded ones. In Jens Groth’s 2016 construction, known as Groth16, a proof consists of just three group elements [6], under 200 bytes in compressed form on the curves used in practice, and checking it takes milliseconds.

Today, such proofs are used for two quite different purposes.

The first is privacy. Zcash, which launched on 28 October 2016 [7], implements the Zerocash design [8]. A shielded transaction carries a proof that it is valid: the coins it spends exist, the sender is authorised to spend them, and the amounts balance. A public nullifier (the Zerocash paper calls it a serial number) marks each spent coin, so the same coin cannot be spent twice. When both sides use shielded addresses, the sender, the receiver and the amount all stay hidden. Since the Sapling upgrade of October 2018, Zcash has used Groth16 on the BLS12-381 curve [9], and a shielded payment can be constructed in a few seconds with about 40 MB of memory [10].

The second is scaling. A zk-rollup executes thousands of transactions off Ethereum, then posts a proof that they were applied correctly, together with enough transaction data on-chain for anyone to reconstruct the resulting state. Ethereum checks the proof instead of re-executing every transaction. Vitalik Buterin’s guide from January 2021 is the best overview, and notes that Loopring and zkSync were already running [11]. StarkWare’s StarkEx engine has run dYdX’s perpetuals exchange on Layer 2 since April 2021 [12].

It is worth noting that most zk-rollups barely use the zero-knowledge property. Their transactions are not hidden; the data is posted publicly precisely so that anyone can reconstruct the state. The proof is there to make checking cheap, not to hide anything. The name stuck because the same proof systems can do both.

Next

That leaves the hard question: how does one prove something about an arbitrary program, rather than about two balls? Right now it is the major unsolved engineering problem in the space, because the program everyone wants to prove is the Ethereum Virtual Machine itself. As Ye Zhang of Scroll wrote recently, “no one has built a native EVM circuit successfully” [13]. The way in is to turn code into polynomials [14], and that is the subject of part 2.

References

1. Vitalik Buterin. Ethereum whitepaper: a next-generation smart contract and decentralized application platform. 2013. ethereum.org/whitepaper. Archived copy: 13 October 2021.
2. Shafi Goldwasser, Silvio Micali and Charles Rackoff. The knowledge complexity of interactive proof-systems. In Proceedings of the 17th Annual ACM Symposium on Theory of Computing (STOC '85), pp. 291–304, 1985. doi:10.1145/22145.22178.
3. Jean-Jacques Quisquater et al. How to explain zero-knowledge protocols to your children. In Advances in Cryptology: CRYPTO '89, pp. 628–631. doi:10.1007/0-387-34805-0_60.
4. Amos Fiat and Adi Shamir. How to prove yourself: practical solutions to identification and signature problems. In Advances in Cryptology: CRYPTO '86, pp. 186–194. doi:10.1007/3-540-47721-7_12.
5. Mihir Bellare and Phillip Rogaway. Random oracles are practical: a paradigm for designing efficient protocols. In Proceedings of the 1st ACM Conference on Computer and Communications Security (CCS '93), pp. 62–73, 1993. doi:10.1145/168588.168596.
6. Jens Groth. On the size of pairing-based non-interactive arguments. In Advances in Cryptology: EUROCRYPT 2016, pp. 305–326, 2016. doi:10.1007/978-3-662-49896-5_11. Preprint: IACR ePrint 2016/260.
7. Zcash documentation. Zcash basics. zcash.readthedocs.io. Archived copy: 3 December 2020.
8. Eli Ben-Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer and Madars Virza. Zerocash: decentralized anonymous payments from Bitcoin. In 2014 IEEE Symposium on Security and Privacy, pp. 459–474, 2014. doi:10.1109/SP.2014.36. Preprint: IACR ePrint 2014/349.
9. Daira Hopwood, Sean Bowe, Taylor Hornby and Nathan Wilcox. Zcash protocol specification. Version 2021.2.16, 30 September 2021; see sections 5.4.9.2 (BLS12-381) and 5.4.10.2 (Groth16). zips.z.cash/protocol/protocol.pdf. Archived copy of version 2021.2.14, with the same sections: 21 August 2021.
10. Zcash. Sapling network upgrade. z.cash/upgrade/sapling. Archived copy: 16 August 2021.
11. Vitalik Buterin. An incomplete guide to rollups. 5 January 2021. vitalik.eth.limo.
12. dYdX. Trade now on Layer 2. 6 April 2021. dydx.exchange/blog/public. Archived copy: 19 April 2021.
13. Ye Zhang. zkEVM. HackMD, 2021. hackmd.io/@yezhang/S1_KMMbGt. Archived copy: 27 September 2021.
14. Maksym Petkus. Why and how zk-SNARK works. 2019. arXiv:1906.07221.