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…