ZKu Week 1: Introduction to ZKP
Tags: blockchain, web3, programming, todayilearned
Published: 2022-05-09 15:19:12

## 👋 Intro

Web3 technologies are fantastic, and one, in particular, has been talked about a lot lately, promising to solve the blockchain privacy and scalability problem.

The zero-knowledge proof is the idea that a user can prove to another user that they know an absolute value without revealing any other or extra information.

This means we can have trusted private transactions and a layer two solution called [zkRollup](https://docs.ethhub.io/ethereum-roadmap/layer-2-scaling/zk-rollups/).

To better understand this technology, I've enrolled in a Zero-Knowledge course promoted by ZKU.ONE.

> [ZKU.ONE](https://www.harmonyzku.one/) is an Online Course and Informal Study Group, for software developers to learn how to build market-ready products in WEB3 using zero-knowledge proof technology. The goal is to launch a ZK-product on mainnet within a couple of months. This is no doubt challenging; we’re here to help.

From now on, I will be sharing my studies in this 8-week course to fixate the knowledge and to provide material for others that want to know more about zero-knowledge proofs.

## 🔎 Week 1

It's possible to see the first-week material and the follow-up assignment in this [Moodle course](https://course.harmonyzku.one/course/view.php?id=5&section=2) with guest log in.

In this first week, ZKu provided videos explaining ZKp, its use cases, and some of its characteristics.

### 🐭 About ZKp

{% youtube https://www.youtube.com/watch?v=BT88s7_VtC8 %}

In the 'Introduction to Zero Knowledge Proofs', Elena Nadolinski provides the Waldo example as a ZKp analogy, talks about privacy and scalability, and explains three properties that have to be satisfied when using ZKp:

* **Completeness** _(Integralidade in Portuguese)_
If the statement is true, an honest verifier will be convinced by an honest prover

* **Soudness** _(Solidez in Portuguese)_
If the statement is false, no cheating prover can convince the honest verifier

* **Zero-knowledge**
If the statement is true, no verifier learns anything other than the fact that the statement is true

She also talks about the history of Zero-Knowledge.
Here's a summary:

**1985**: First coined as a Term in 1985 for an interactive protocol
**2011**: zk-SNARK as an evolution of ZKP
**2013**: zk-SNARKs are applicable for general computing
**2016**: zk-SNARKs are really efficient

### 🐯 About SNARKs

SNARK stands for **S**uccinct **N**on-interactive **A**rguments of **K**nowledge and is a way of using ZKp. More specifically, it's a fast+small (succinct) and non-interactive way of doing it.

With SNARKs, we have a programmatic way to transform a statement into a language of polynomials. This statement is a challenge that will involve a prover and a verifier.

To make the challenge non-interactive, there is a hardcoded common reference string (CRS) or SRS (Structured Reference String), which is part of a trusted setup (explained later).

There are several types (proving schemes/constructs) of zk-SNARKS, and they can be graded on proof size, prover time, and verifier time. The most known ones are Groth16 and PLONK.

* **Groth16**
It has an efficient prover time, constant proof size (192 bytes), and constant/fast verification time. The downside is it requires a trusted setup.

* **PLONK**
It has a slower prover time than Groth16, a bigger proof size, and a slower verification time. However, it doesn't require a trusted setup.

Other zk-SNARKs are Sonic, Fractal, Halo, Marlin, etc.

![zkSNARKs](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/bmjakk5dz2w92z33dyxq.png)

### ⚙️ Technical Details

Another video provides a general theoretical background, discussing hashing, trusted setups, and interaction types.

{% youtube https://youtu.be/9je336QIqAQ %}

For example, consider the following scenario:

"I know secret so that H(**secret**)=**hashvalue**."

Statement x is public data describing what we are proving in this instance: **hashvalue**
Witness w is private data that supports our statement: **secret**
Relation R is how statement and witness must be related: R(w,x): x == H(w)

Statement x is true if there is a w, so that R(x,w) is true
Statement x is false if there is no w, so that R(x,w) is true

We can check ZKp properties with these statements:

**Completeness**: if R(x,w) is true, P(x,w)  <-> V(x) will accept
**Soundness**: if x is false, V(x) will reject any P (even a cheating one)
**Zero-Knowledge**: if R(x,w) is true, we can simulate execution logs of the protocol using only x

### 👌 Trusted Setup

The way a prover and a verifier know they're with the same statement is by using a Common Reference String (CRS).

![trusted setup](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ac2oowtl5wio4ktf5whd.png) 

A trusted setup is a process to generate this CRS.

Pyrros Chaidos has a good explanation regarding the importance of this setup.

> If a single person makes this file, she will be able to cheat on the protocol.
> Most kinds of trusted setup protocols guarantee that when several people are taking part in a ceremony, only one person needs to be trustworthy to generate a common reference string that is not under any one person's control.
> The idea is everybody rolls some dice, and the randomness is pulled together in that file. As long as nobody knows what all the dice rolls were, the protocol is fine.
> For example, you're supposed to roll your dice and do stuff with the results. Then throw your dice away without writing down the result.
> If people write down their results, bad guys could hack and get all the dice rolls, reverse engineering what went into the string and therefore cheating on the protocol.

In a more cryptographic explanation, a trusted setup refers to the initial creation event of the keys used to create the proofs required for private transactions and verify those proofs. Initially, a hidden parameter is linked between the verification key and the keys sending private transactions when those keys are created. Suppose the secrets used to create these keys in the trusted setup event are not destroyed. In that case, they could be utilized to forge transactions by false verifications, giving the holder the ability to perform actions such as creating new tokens out of thin air and using them for transactions.

A trusted setup can be universal or non-universal.
Universal means that it doesn't have to be set up again to be used on other protocols, but it might be less efficient than a non-universal setup.

### 🌟 About STARK

{% youtube https://www.youtube.com/watch?v=VUN35BC11Qw %}

STARK is a type of SNARK that stands for Scalable Transparent Argument of Knowledge. The transparent keyword means that it doesn't require a trusted setup.

Everything needed to generate the proofs is public, and the proofs are generated from random numbers.

Technically speaking, zk-STARKs do not require an initial trusted setup because they rely on leaner cryptography through collision-resistant hash functions. 

Also, ZK-STARKs are more scalable in terms of computational speed and size when compared to ZK-SNARKs.

As a final note, ZK-SNARKs are vulnerable to attacks from quantum computers due to the cryptography they use. ZK-STARKs are currently quantum-resistant.

### 💻 Circom and SnarkJS

After answering the theoretical questions from the assignment, which led me to the research I've just written above, I moved to the practical ones.

Their goal was to teach how to use [Circom](https://docs.circom.io/) to build zero-knowledge circuits and [SnarkJS](https://github.com/iden3/snarkjs) to compile them into solidity smart contracts.

{% github https://github.com/iden3/snarkjs %}

I've also learned how to perform and utilize a Powers of Tau ceremony, call and create tests for the generated verifier contracts, and use a ZKp to solve sudoku puzzles.

## 🔥 Conclusion

That's a lot of new information to process, and I'm still unsure if I got everything intended to be taught in just one week. 

However, this is just the start of this course. I'm sure that by the end of it, I will be able to a dapp with zero knowledge on a mainnet 😎.

## 📚 References
* [Consensys: Gnark Prove schemes and curves](https://docs.gnark.consensys.net/en/latest/Concepts/schemes_curves/)
* [Consensys: Zero-Knowledge Proofs: STARKs vs. SNARKs](https://consensys.net/blog/blockchain-explained/zero-knowledge-proofs-starks-vs-snarks/)
* [Binance: zk-SNARKs and zk-STARKs Explained](https://academy.binance.com/en/articles/zk-snarks-and-zk-starks-explained)
* [ZCash: What are zk-SNARKs?](https://z.cash/technology/zksnarks/)
* [Youtube: Introduction zk SNARKs STARKs by Eli Ben Sasson](https://www.youtube.com/watch?v=VUN35BC11Qw)
* [Crypto StackExchange: What are zk-STARKs?](https://crypto.stackexchange.com/questions/56327/what-are-zk-starks)
* [Crypto StackExchange: Transparent Setup of SNARKs]( https://crypto.stackexchange.com/questions/68077/transparent-setup-of-snarks)
* [Crypto StackExchange: CRS vs. SRS in zk-SNARK](https://crypto.stackexchange.com/questions/88565/crs-vs-srs-in-zk-snark)
* [Medium: Diving into the zk-SNARKs Setup Phase](https://medium.com/qed-it/diving-into-the-snarks-setup-phase-b7660242a0d7)
* [Medium: Comparing General Purpose zk-SNARKs](https://medium.com/coinmonks/comparing-general-purpose-zk-snarks-51ce124c60bd)
* [Xord: The Trusted Setup of ZK-SNARK](https://xord.com/research/the-trusted-setup-of-zk-snark/)
* [ZKProof: Setup Ceremonies](https://zkproof.org/2021/06/30/setup-ceremonies/)
* [ZKProof: ZKProof Community Reference (PDF)](https://docs.zkproof.org/pages/reference/reference.pdf)