Zero Knowledge Proofs

This post is a quick brief intro to Zero Knowledge Proofs (ZKPs). ZKPs are the new magic tech buzzword in web3, similar to ML in its early days.

Zero Knowledge proofs have two main parties - a prover and a verifier. The prover wants to show they have or did something (proof) to the verifier without revealing any details (zero knowledge).

Some use cases:

• Prove I have a valid passport without giving away any personal details.
• Prove I sent money to an address without revealing the amount.

The classic intuitive explanation

We have a Prover - Patricia, who wants to prove that two balls are different colours. We have a Verifier - Victor, who is blind.

Each turn, Victor places the balls behind his back, switching them or keeping them in the same hands before showing them to Patricia. Victor cannot tell the difference in colours as he is blind, but Patricia can, and she tells Victor each time if the balls were swapped or not.

Iteration 0: Victor shows the balls in each hand. Iteration 1: Victor does not switch and shows Patricia - a 50% chance Patricia guesses correctly. Iteration 2: Victor switches the balls and shows Patricia - a 50% chance Patricia guesses correctly, but there is a 25% chance she was correct on both iterations 1 and 2. Iteration 3: Victor switches the balls and shows Patricia - a 50% chance Patricia guesses correctly, but there is a 12.5% chance she was correct on iterations 1, 2 and 3.

Repeating these iterations n times, say a thousand times, there is a 9.33263619×10^−302% Patricia is lying. This probability allows Victor (the verifier) to trust Patricia (the prover).

In this example, the prover (Patricia) proved the colour of the balls was different without revealing their colour to the Verifier (Victor). Zero Knowledge proofs rely on probabilistic truths. However, since we have an almost certain confidence, we trust them.

Where’s Wally intuitive explanation

Patricia has found Wally and wants to prove it to Victor, however, if she shows him, Victor is liable to cheat and claim he also found Wally. To prove to Victor, she found Wally without giving away his location in the picture:

Patricia cuts a hole in a large sheet of paper, and the hole is the exact shape of Wally in the underlying picture.

Patricia places the paper over the original picture.

Victor can see through the hole that Wally has been found, but since the alignment of the underlying picture cannot be seen, he doesn’t gain any information about the location of Wally.

Vitalik Buterin quote on ZKPs

You can make a proof for the statement “I know a secret number such that if you take the word ‘cow’, add the number to the end, and SHA256 hash it 100 million times, the output starts with 0x57d00485aa”. The verifier can verify the proof far more quickly than it would take for them to run 100 million hashes themselves, and the proof would also not reveal what the secret number is.”

Hopefully, these high-level examples give insight into how a Zero Knowledge Proof could look.