ZKP - Week 1

This will be the first post in the ZKP series, following ZKU Academy's course. You can find it here. It will be a beginner-friendly introduction to Zero Knowledge Proofs.

It borrows heavily from the speakers' presentations at the mentioned course's week one, Elena Nadolinski and Pyrros Chaidos

What is ZKP?

ZKP or Zero Knowledge Proofs it's the ability to prove honest computation without revealing inputs.

The origins of ZKPs dates back to 1985, specifically to the paper "The Knowledge Complexity of Interactive Proof-Systems" by Shafi Goldwasser, Silvio Micali and Charles Rackoff

Then in 1986 with the paper "How to prove yourself: practical solutions to identification and signature problems. Non-intreractive ZK via ROM" [Fiat-Shamir]. Here it goes from interactive to non-interactive (interaction is very hard to achieve, expensive, since states have to be tracked among other things) Ideally we want systems that work in a single round, i.e prover -> verifier -> end

Later in 1988 with the paper "Non-interactive zero-knowledge and its applications. Non-interactive ZK via Common Random String (CRS)" by Blum, Feldman, Micali

They first coined the term zero-knowledge proofs for their interactive protocol (two parties have to go back and forth to make a proof actually work)

One of the most popular ZKP it's zk-SNARKs. The term was first coined in 2011 (Succinct Non-interactive Arguments of Knowledge) (Nir Bitansky, Ran Canetti, Alessandro Chiesa, Eran Tromer)

In 2013 zk-SNARKs were made applicable for general computing in the "Pinocchio" paper (PHGR13) by engineers at Microsoft and IBM

In 2016 zk-SNARKs were made really efficient (by Jens Groth) and the standard (Groth16) is still used today

Okay, but how do ZKPs exactly work?

Relations, statements, witnesses

• "I know a secret so that H(secret) = hash value"
  • statement x: public data describing what we are proving in this instance: hash value
  • witness w: private data that supports our statement: secret
  • relation r: the way in which 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 (if w hash is equal to x hash)
• Statement x is false if there is no w that makes R(x,w) true (if w hash is NOT equal to x hash)

And what can we do with them?

They are usually used for scalability and privacy. ZKP's must satisfy three properties to be considered so:

• completeness (protocol works as stated): if the statement is true, an honest verifier will be convinced by an honest prover: if R(x,w) is true, P(x,w) <-> V(x) will accept
• soundness: if the statement is true, no cheating prover can convince the honest verifier: if x is false, V(x) will reject for any P (even a cheating one)
  • knowledge soundness: if P can make V(x) accept, there's a way to get w so that R(x,w) is true
• zero-knowledge: if the statement is true, no verifier learns anything other than the fact that the statement is true. if R(x,w) is true, we can simulate execution logs of the protocol using only x, which would make the logs useless as anyone could see and build them

We MUST aim to achieve the three of these properties. Let's see if we achieve 2 out of 3:

• completeness + soundness = send w in the clear for anyone to see
• soundness + ZK = V always rejects
• completeness + ZK = V always accepts

Very nice but, how can I build one?

SNARK construction flow (Groth16, PHGR13):

1. computation
2. arithmetic circuit
3. R1CS (rank 1 constraint system)
4. QAP (quadratic arithmetic program)
5. SNARK

TL;DR:

• For SNARKs we have a programmatic way to transform a statement into a language of polynomials.
• Like with any proof system, there is a prover, and a verifier, and a challenge.
• To make the challenge non-interactive there is a “hard coded” common reference string (CRS) or SRS (Structured Reference String) which is part of the trusted setup.
• The SRS is encrypted in order for it to be reused, which requires multiplication of encrypted values with elliptic curves, which leads to the requirement of something called elliptic curve pairings

We mentioned a few ZKPs systems so far. Why Groth16 stands out?

ZKPs are typically graded on succinctness*:

• prover time
• proof size
• verification time

zk-SNARKs (Groth16) have:

• a (fairly) efficient prover time
• constant proof size (192 bytes)
• constant (and fast!) verification time

*And sometimes also on:

• The size of the SRS/CRS
• Cryptographic assumptions
• plus other criteria

Wait, so everything comes without a downside?

However, it has one big downside – a trusted setup (see this tutorial by Daniel Benarroch from Qedit)

Trusted Setup: several parties involved (MPC) to make sure no one can cheat

Universal Setup: use same setup for many specific complexity-level protocols

ZKPs without a trusted setup

2017 -> onwards there’s been an explosion in ZKP research to try and mitigate the trusted setup requirement while still competing with Groth16 on performance

Using interactive oracle proofs (IOP), algebraic holographic proving systems (AHP), polynomial commitment schemes (PC)*, and more

• Most notably the Kate, Zaverucha and Goldberg polynomial scheme [KZG10]. If you want to dig deeper on KZG polynomial commitments check this

The main ZKPs of this kind that you should pay attention:

• bulletproofs
• STARKs
• PLONK
• Halo2

So, having seen ZKPs with/without trusted setups, we should have these in mind:

• Groth16 🌟
  • Overall (proof size, prover time, verification time) it is currently the gold standard of ZKPs
  • R1CS is great – leads to high level DSLs (domain specific languages) or advanced toolsets:
  • ZoKrates, libsnark, bellman, circom, aleo (uses ZEXE which way more involved)
  • Very mature toolset that you can use today (!!) to write ZKP apps & smart contracts
• PLONK – universal trusted setup
  • Prover time overall slower than Groth16 – but not by much!
  • Even outperforms for some operations, like MiMC hashes or Pedersen commitments on bn128 curve
  • Proof size bigger – but not by much!
  • Verification time slower – but not by much!
  • Evolving (WIP) toolset: Aztec is working on Noir, Coda/Mina is working on Pickles, and Mir is working on Plonky
• Halo2
  • Super exciting work (still WIP) from the Zcash team (related to PLONK)

Notable examples of ZKPs in the wild on Ethereum

• Gaming – how to create a game on Ethereum (where all the state is public) that requires some hidden data? Check Dark Forest
• Private Transactions — how to add any privacy layer on top of Ethereum (where all state is public)? Check Tornado Cash
• Scalability — zkRollups
• Starkware’s StarkNet (using STARKs)
• Matter Lab’s zkSync
• Loopring

As an Ethereum Developer, What Can I Use Today?

• Zokrates — DSL for zkSNARKs

  • Circuit construction
  • Auto-generated Solidity verifier smart contract

• Circom & SnarkJS — DSL for zkSNARKs

  • Circuit construction
  • Auto-generated Solidity verifier smart contract

• Other notable DSLs for ZKPs:

  • Zinc from Matter Labs — for general circuit construction and smart contracts on zkSync, their zkRollup L2
  • Noir from Aztec — a DSL for PLONK

TLDR;

zk-SNARKs

• Trusted setup (initial creation event of keys that are used to create proofs required for private txs and the verification of those proofs).

• Depend on elliptic curves for security at their base. Elliptic curves in cryptography operate under the base assumption that finding the discrete logarithm of a random elliptic curve element with respect to a publicly known base point is infeasible. Although there's been some debate and there are several popular vulnerabilities in side-channel attacks, they are easily mitigated through several techniques.

• Quantum computing attacks loom over its security but the required resources are yet to be widely available. Supporters of SNARKs correctly point to the fact that we will have far more problems on our hands, such as the breaking of RSA and most wallet infrastructure, when quantum computers are utilized.

• Users of the SNARK based network must rely on the fact that the trusted set up was performed correctly, meaning that the secrets associated with the trusted set up key were destroyed and are not being held by the individuals who oversaw the ceremony. This reliance on a trusted set-up has been one of the largest areas of concern for critics of SNARKs. That being said, developers only need to utilize the trusted set up initially, not continuously.

• SNARKs have actually been adopted at a far faster rate than STARKs. SNARKs were discovered years ahead of STARKs, which gave the technology a significant head start in terms of adoption. SNARKs has the most developer libraries, published code, projects, and developers actively working on the technology.

• SNARKs are estimated to require only 24% of that gas that STARKs would require, meaning that transacting with SNARKs would be far cheaper for the end-user.

• The proof size for SNARKs is much smaller than STARKs, meaning it would take less on-chain storage.

zk-STARKs

• Eli Ben-Sasson, Iddo Bentov, Yinon Horeshy and Michael Riabzev wrote the first papers describing STARKs in 2018.

• The base technology for STARKs relies on hash functions. Relying on hash functions offers some benefits, such as being quantum resistant. Furthermore, no trusted set-up is required to begin utilizing STARKs in a network.

• STARKs have far larger proof sizes than SNARKs, which means that verifying STARKs takes more time than SNARKs and also leads to STARKs requiring more gas.

• Developers will have a much harder time utilizing STARKs because of the lacking developer documentation and community. Check this

• While both developer communities support both SNARKs and STARKs, the Ethereum Foundation in particular displays vocal support for STARKware, which utilizes Starks.

Some useful links

• Elena Nadolinski's slides
• Why zk-SNARKs need a trusted setup
• STARKs paper
• Pyrros Chaidos' presentation

Finally...

Well, If you made it this long... I hope you leave from here a little less confused about ZKPs than when you came. At least you will go with a ton of resources to learn from, that's for sure! ZKPs are not by any means an easy endeavor, but with practice and showing up every day, even just a little, you can make it.

Hope to see you around here again. Til next time.