A gentle introduction to Zero Knowledge Proofs

Zero Knowledge proofs are gaining in interest thanks in part to the role they have played in providing privacy to distributed ledger technology.
This post serves as a gentle intuitive explanation, of zero knowledge proofs, more rigorous explanations can be found at our workshops notes (see below).

A zero knowledge proof is used in the context of 2 actors, a prover and a verifier. The prover wishes to prove to the verifier that they have knowledge of a secret item (called the witness). They want the verifier to be satisfied that they have this knowledge, without providing any further information to the verfier.
The verifier only learns that the proof is true or false; i.e. that the prover knows the secret, or not.
For example the prover may wish to prove that they know a password for an account, without revelaing the password to the verifier.

A commonly used example involves the colour of billiard balls and a colour blind verifier.

This is an interactive proof showing that the prover can distinguish between a red and a green billiard ball, whereas the verifier cannot distinguish them.

• The prover wants to show the verifier that the balls have different colours but does not want the verifier to learn which ball is red and which is green.

• Step 1: The verifier takes the balls, one in each hand, holds them in front of the prover and then hides them behind his back. Then, with probability 1/2 either swaps them (at most once) or keeps them as they are. Finally, he brings them out in front.

• Step 2: The prover has to tell the verifier whether he thinks they were switched them or not.

• Step 3: Since they have different colours, the prover will always know whether they were switched or not.(This is the knowledge they are trying to prove)
But, if they were identical (the verifier is inclined to believe that), the prover would at each step have the possibility of being wrong of 1/2.

• Finally, to convince the verifier with very high probability, the prover could repeat Step 1 to Step 3 many times to reduce the probability of the prover being successful by chance to a extremely small amount.

With the password example it may be possible for the prover to use the password to login to the system, and show the verifier…