From Zero to Hero in Zero Knowledge Proofs [Part 7]

This is the seventh part of the series that takes you from absolute ground zero in ZKPs to a fairly advanced level. We will start from the absolute basics and then move onward and upward. Subscribe to get regular updates!

In the previous 6 parts, we were covering the basics of ZKPs. From this post onwards, we will start with the first practical application of ZKPs i.e. zk-SNARKs.

What does zk-SNARK mean?

The acronym zk-SNARK stands for “Zero-Knowledge Succinct Non-Interactive Argument of Knowledge”, and refers to a proof construction where one can prove possession of certain information like a secret key, without revealing that information, and without any interaction between the prover and verifier.

Currently, zkSNARK is the most common proof system being used.

zkSNARK was named in a 2012 paper by Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer, with the term describing a new zero-knowledge protocol that would not, like prior methods, require interaction between the prover and verifier outside of a single message.

Let’s quickly recap what the terms mean in the zk-SNARK abbreviation.

• Zero-Knowledge: A verifier can validate the integrity of a statement without knowing anything else about the statement. The verifier’s only knowledge of the statement is whether it is true or false.
• (S)uccinct: The zk-proof is smaller than the secret information (witness) and can be verified quickly.
• (N)on-interactive: The proof itself is non-interactive meaning the prover and verifier only interact once using algorithms.
• (AR)gument: The proof satisfies the “soundness” requirement, so cheating is unlikely.
• (K)nowledge: The zero-knowledge proof cannot be constructed without access to the secret information (witness).

Building blocks of zkSNARK

A zk-SNARK consists of three algorithms G, P, and V, defined as follows:

Generator G

The Generator algorithm is responsible for generating the key material required to create and verify proofs.

The Generator takes a secret parameter lambda and a program C (which has the logic for what needs to be proved). Using lambda and C, the Generator generates two publicly available keys, known as the proving key pk and the verification key vk:

(pk,vk)=G(lambda,C)

These keys (also known as the Common Reference String) are public parameters that only need to be generated once for a given program C.

This step is also called the Trusted Setup. We will go into its details in the next blog post.

Prover P

The Prover algorithm is responsible for generating proofs.

Let’s say Peggy needs to prove a specific statement and therefore needs to generate a proof.

To do this, Peggy takes the proving key pk (created by the Generator), a public input x which the verifier also knows, and a private witness w that only Peggy knows. Peggy passes these parameters to the Prover P algorithm to generate the proof.

proof=P(pk,x,w)

Using this proof, Peggy claims that she knows a witness and that the witness satisfies the program.

Verifier V

The Verifier algorithm is responsible for verifying the proofs generated by the Prover.

Let’s say Peggy sends the proof created in the previous step to Victor, who needs to verify whether the proof is correct.

To do this, Victor takes the verification key vk (created by the Generator), the same public input x which Peggy used, and the proof that Peggy sent to him. Victor passes these parameters to the Verifier V algorithm to verify the proof.

VerificationResult=V(vk,x,proof)

Verification Result equals true if the proof is correct, and false otherwise.

That’s it for today. In the next blog post, we will go into the zk-SNARK details. Until then, ciao!

Hey there, thanks for reading this far. If you liked this article, don’t forget to follow and leave a clap.

I am building Plurality Network, the user context layer on web3. Join our discord to get alpha!

Follow me here, on LinkedIn, on X, or on Farcaster to get the latest blockchain technical content in simple, bite-sized reads.