Zero Knowledge Proofs

Origins

In cryptography, a zero-knowledge proof or zero-knowledge protocol (ZKP) is a class of method by which one party (the prover) can prove to another party (the verifier) that they know a value x, without revealing x itself or any other information.

The seminal work on ZKP was published by Goldwasser, Micali and Rackoff in 1985 . While their proposed zero-knowledge scheme was not practical, the result demonstrated that ZKP was a mathematical possibility that sparked its continual research to this day. A zero- knowledge proof must satisfy three properties:

• Soundness: if the statement is false, the verifier will always reject.

• Completeness:if the statement is true, the verifier will always accept it.

• Zero-knowledge: the verifier learns no information except for the truth of the statement.

Interactive ZKPs require interactions between the prover and the verifier when validating the proof, whereas non-interactive zero-knowledge (NIZK) proofs allow the prover to generate and publish a proof that can be validated by any verifier at any time with no further interaction. For this reason, non-interactive ZKPs are particularly useful in the blockchain setting.

Succinct Non-interactive Argument of Knowledge (SNARK) is a class of practical proofs which possesses the following properties:

• Succinct: the size of the proof is small compared to the size of the statement being proved.

• Non-interactive: it does not require rounds of interaction between the prover and veri- fier.

• Argument: a weaker notion of a mathematical proof where we assume the prover has bounded computational resources.

• Knowledge: the prover cannot construct a proof without knowing a certain witness for the statement.

A SNARK is not necessarily zero-knowledge. If a SNARK allows proofs to be conducted without revealing the witness, we call it a zero-knowledge SNARK or commonly zkSNARK. Generating a zkSNARK proof is a multi-stage process, an example of which is illustrated in Figure 2. For more details, an introduction to zkSNARKs and their recent development is presented in.

Figure 2: zkSNARK workflow

In DeFi and blockchain in general, zero-knowledge proofs are a solution to two different problems. Their zero-knowledge property provides privacy and anonymity to users’ transactions and their utility as proof of computation are exploited to implement blockchain scaling solutions.

Example​

To better illustrate a ZKP system, let us run a simple example in the finite field $F7​$.

• Statement: $22$ is a square in $F7​$

• Public input: $x=2$.

• Witness: $w=4$, since $42=2$ in $F7​$.

The protocol consists of the following steps:

1. The prover chooses a random non-zero $a∈F7​$ and sends $y=a2$ to the verifier.

2. The verifier chooses $b∈{0,1}$ and sends it to the prover.

3. The prover sends the verifier the proof $π=wba$.

4. The verifier accepts the proof if $π2=xby$.

Then they repeat the protocol above for different values of $a$ until the verifier is convinced.

Let us check that the above protocol satisfies the desired properties:

1. Completeness: It is clear, since $π2=w2ba2=xby$.

2. Soundness: A dishonest prover might try to trick the verifier by sending a $y$ in step 1 which is not a square. In that case the verifier would reject the proof in half the cases, when they choose $b=0$. If $y$ is a square but $x$ is not, the verifier would reject the proof when $b=1$. A dishonest prover has a $1/21/2$ probability to trick the protocol on each iteration, so this probability can be made negligible by iterating enough times.

3. Zero-knowledge: If $b=0$, the prover does not use $w$ at any point in the proof, it cannot be leaked. If $b=1$, the only place where the prover uses $w$ is in $π=wa$, from which the verifier cannot extract $w$ without the knowledge of $a$. As long as the prover does not repeat the above protocol with the same $a$ for different $b$'s, the protocol remains zero-knowledge.

Succint Non-Interactive Arguments of Knowledge (SNARKs)​

A particularly important type of ZKP systems are SNARKs. They are zero-knowledge proof systems which satisfy the following extra properties:

• Argument of knowledge: The prover wants to prove knowledge of the witness itself. In the example above, the statement would be "I know a square root of $22$ in $F7​$". One can show the protocol above also proves this stronger statement, thus making it an argument of knowledge.

• Succinctness: The proof size is constant or logarithmic compared with the circuit size (i.e. the amount of computations) of the statement. The protocol above is also succint, since the proof is just a number in $F7​$.

• Non-Interactive: Proof generation and proof verification happen in two consecutive rounds: first the prover runs a function $proveprove$ to generate a proof and then the verifier runs a function $verifyverify$ to verify it. The protocol above is interactive, i.e., it does not satisfy this property because of the continuous communication between prover and verifier.

Setup​

SNARKs need an extra element to be properly defined

• Setup: A set of proving and verifying keys necessary to execute the $proveprove$ and $verifyverify$ functions, respectively.

In pairing-based proving systems such as Groth16, the setup consists of a set of elliptic curve points, generated from a randomly sampled seed, more commonly known as the toxic waste. Knowledge of this seed allow an attacker to fabricate valid ZKPs for false statements, so it is of paramount importance that the generation of the keys is safely executed, i.e., that nobody knows the toxic waste employed to generate them. This is usually done in a multi-party computation known as Trusted Setup.

The simple definition of a SNARK​

Once all the elements are fixed, a SNARK is defined as a pair of functions

• prove(Setup, Public Input, Witness) -> Proof: Generates a proof for the knowledge of the witness using the public input and witness.

• verify(Setup, Public Input, Proof) -> bool: Verifies the proof against the public input.