Zero-Knowledge Proofs - Theory

Quote from Remco Bloemen remco@0x.org

Disclaimer: contains maths

If you don’t understand something
    * Not your fault, this stuff is hard
    * Nobody understands it fully

If you don’t understand anything
    * My fault, anything can be explained at some level

If you do understand everything
    * Collect your Turing Award & Fields Medal

Introduction

It is difficult to find zero knowledge resources that avoid the extremes of either over simplyfying the subject, or presenting so much mathematical detail that the reader gets bogged down and loses interest. The purpose of this tutorial then is to find an accessible but informative middle ground.

We start with some examples to show how zero knowledge proofs can proceed, and the situations where they could be used.

Actors in a Zero Knowledge Proof

   * Creator - optional, maybe combined with the prover
   * Prover - I will call her Peggy
   * Verifier - I will call him Victor

Examples to give an Intuitive grasp of zero-knowledge proofs

1. 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 they have different colours but does not want him to learn which is red and which is green.

   • Step 1: The verifier takes the balls, each 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 say the verifier switched them or not.

   • Step 3: Since they have different colours, the prover can always say whether they were switched or not.
   But, if they were identical (the verifier is inclined to believe that), the prover would be wrong with probability 1/2.

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

   Wheres Wally
   Based on the pictures of crowds where Wally is distinctivly dressed, the aim being to find him amoungst a sea of similar people.
   The proof procedes as follows :
   Imagine the Peggy has found Wally in the pricture and wants to prove this fact to Victor, however if she just shows him, Victor is liable to cheat and claim he also found Wally.
   In order to prove to Victor that she has indeed found Wally, without givin away his loaction in the picture
       Peggy cuts a hole in a (very) large sheet of paper, the hole should be the exact shape of Wally in the underlying picture.
       Peggy places the paper sheet over the original picture, so that the location of the picture beneath the paper is obscured.
       Victor can then see throught he hole that Wally has indeed been found, but since the alignment with the underlying picture cannot be seen, he doesn’t gain any information about the location of Wally.

   Sudoku
   An interactive proof can be created to prove the knowledge of a solution to a sudoku puzzle by placing cards in the sudoku grid. The process is descrived here Sudoku Proof

Now that we an intuitive grasp of zero knowledge proofs, lets go into the details by looking at a certain type of proof system, a zk-SNARK.

resource :

* http://extropy.foundation/workshops/zkp/theory.html
* http://extropy.foundation/workshops/zkp/zkpreal.html
* http://extropy.foundation/workshops/zkp/index.html