Zero Knowledge Proofs - A Gentle Introduction

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 the successful login, but this may not be sufficient for the verifier, or the verifier may not be present. Likewise for the billiard ball example, this could be a lengthy process so although zero knowledge proofs can come in many forms, cryptographic proofs are usually preferred for efficiency and convenience.

Interactive v Non Interactive Proofs

In the above cases, the proof is interactive, in that a number of intaeractions are required between the prover and verifier to complete the proof to the staisfaction of the verifier. Non interactive proofs, with a one step proof are more convenient.

zkSNARKS

Currently zkSNARKS are the most common proof system being used, they form the basis for the privacy provided in ZCash.

zkSNARK stands for zero knowledge Succint Non interative Argument of Knowledge. The features of succintness ( they are small in size and the amount of computation required ) and Non Interaction (a single step is sufficient to complete the proof) has helped their adoption in applications.

Simplified Overview of the process needed to create a zkSNARK

  1. Trusted Setup
    ZKSNarks require a one off set up step to produce prover and verifier keys. This step is generally seen as a drawback to zkSNARKS, it requires an amount of trust, if details of the setup are later leaked it would be possible to create false proofs.

  2. A High Level description is turned into an arithmetic circuit
    The creator of the zkSNARK uses a high level language to spcify the algorithm that constitutes and tests the proof.
    This high level specification is compiled into an arithmetic circuit.
    An arithmetic circuit can be thought of as similar to a physical electrical circuit consisting of logical gates and wires. This circuit contrains the allowed inputs that will lead to a correct proof.

  3. Further Mathematical refinement
    The circuit is then turned into a series of formulae called a Quadratic Arithmetic Program (QAP).
    The QAP is then further refined (beyond the scope of this introduction) to ensure the privacy aspect of the process.
    The end result is a proof in the form of series of bytes that is given to the verifier. The verifier can pass this proof through a verifier function to receive a true or false result.
    There is no information in the proof that the verifier can use to learn any further information about the prover or their witness.

For a more detailed description of this process and an overview of the technology, please see the content from our Zero Knowledge Proof Workshop

Maths Primer
Zero Knowledge Proof Theory

Use Cases

This technology has proved useful in providing

  1. Privacy
  2. Scalability - proofs of computation can be used to show that the result of a (costly) computation is correct without having to repeat the computation.

Privacy

ZCash is a cryptocurrency using zkSNARKS.
A typical cryptocurrency such as bitcoin uses transactions that are visible and hence verifiable by participants in the system. This provides transparency, but does mean that anyone can know the accounts that are sending and receiving the currency, and the amount transferred.
In ZCash it is possible to have shielded transactions, where although the transaction can be verified as correct, no information is given about the sender, receiver or amount transferred.

Scalability

The Coda protocol uses zero knowledge proofs to create a more scalable blockchain.