Confused about how zero knowledge proofs work under the hood? Don't know where to start?
I've got you covered.
Spoiler: you don't need a degree in math to understand zk-SNARKs 😉 Let's dive in 👇
1/ In this thread, we will cover some basic cryptography and build up to a high-level overview of zk-SNARK systems.
I recommend saving this thread for future use!
2/ Don't know what zero knowledge proofs are? My last thread was a high-level deep dive on exactly that!
Check it out below ↓
3/ Before diving into zk-SNARKs, it's important to understand arithmetic circuits.
An arithmetic circuit is composed of inputs, internal nodes (aka gates), and an output.
Internal nodes can be addition (+), subtraction (-), or multiplication (×).
4/ Mathematically, an arithmetic circuit defines a recipe for evaluating a polynomial given input parameters.
We define the size of an arithmetic circuit to be the number of gates it contains.
Small detail: all operations within a circuit occur over a chosen prime field.
5/ A practical example:
We can define a circuit C that has inputs h and m such that C outputs 0 if SHA256(m) = h and a non-zero value otherwise.
This circuit only has a size of about 20K gates!*SHA256 is a common collision resistant hashing function.
6/ So, what's a zk-SNARK?
zk-SNARKs are Zero Knowledge Succinct Non-interactive ARguments of Knowledge.Let's break this down, starting with arguments of knowledge.
7/ We have a prover who wants to convince a verifier that a statement is true.
For example, the prover might know a number x such that f(x) = 0, for some function f.
The function f would be described as an arithmetic circuit which is agreed upon between the prover and verifier.
8/ Trivially, the prover can send over the entire number x to the verifier.If the number is long (e.g. 1 GB), it could take a long time to verify. This is why we care about sending a proof instead. SNARKs provide a succinct proof that a given statement is true.
9/ Thanks to their short size, SNARKs can be verified on the order of milliseconds.
If we reveal nothing about the number within the proof, we have a zk-SNARK.
10/ zk-SNARKs are a currently a huge topic in the blockchain space.
For example, zk-SNARKs promise to:- enable privacy on dApps (@AleoHQ)- secure layer 1 blockchains (@Zcash, @ironfishcrypto)- provide scalability through validity proofs
11/ There are two requirements for SNARK systems.
1. Completeness: if the prover has a valid solution, it will be accepted by the verifier.
2. Soundness: if the verifier accepts a proof, the prover must have a valid solution.
12/ There's a third requirement for zk-SNARK systems.3. Zero knowledge: the proof reveals nothing about the solution.
13/ But what does it mean for a zk-SNARK to be non-interactive?
Argument systems between provers and verifiers are usually interactive.
The prover's goal is to eventually convince the verifier that they know a solution to the statement in question.
14/ This works well for some cases, but this would create unnecessary computational constraints for blockchain applications.If we want to post data to the blockchain (e.g. proof of a rollup) we need to be able to verify it asynchronously.
15/ In order to make an argument system non-interactive and fast, we need to have a preprocessing step. We will apply an algorithm to the circuit to generate public parameters for the prover and verifier before any communication takes place. I'll explain why in a bit.
16/ We want the size of the generated proof given by the prover to logarithmically scale with the size of the circuit. We want the verification time to also logarithmically scale with the size of the circuit. The proof is short and verification is fast! 🏎 🏎 🏎
17/ This is why we need to have a preprocessing step! If we didn't, our verification time would scale linearly with the size of the circuit at a minimum.
18/ Informally, the public parameters outputted by the preprocessing step "summarize" qualities of the given circuit. This helps us save time during proof verification. Let's take a closer look at preprocessing steps.
19/ There are three main types of preprocessing steps.
The first involves a trusted setup per circuit. This involves using a special secret for every circuit generated.
If the prover has knowledge about this secret, they can forge verifiable proofs for false statements.
20/ A better solution is to have a trusted universal setup, before any preprocessing step.We pick a secret independent of circuits. Everyone is given public parameters generated from the secret.
21/ The preprocessing step for every circuit no longer depends on a secret and uses the public parameters instead. This is more secure. However, there is an even safer approach.
22/ The safest approach is to conduct a transparent setup. Let's get rid of secret data and setup phases altogether! However, this can come at the cost of larger proof size and slower verification time.
23/ The algorithms involved in converting circuits into proofs and their verification are bundled into proof systems.
Some common ones are Groth16 and Plonk.
Here's a table providing some details about these systems.
(from zkhack.dev/whiteboard/mod…)
24/ Note that Bulletproofs, STARKs, and DARKs are not SNARKs, but other systems for zero knowledge proofs.This is evident by their varying proof sizes and verification times. They all share a lack of a trusted setup phase.
25/ How do you implement a SNARK software system?There are a few key components. First, you have to pick a domain specific language (DSL) program that compiles into SNARK formats. Some examples are Circom (@identhree), ZoKrates, and Cairo (@StarkWareLtd).
26/ The compiled circuit is then passed to a SNARK backend prover with the statement.The SNARK backend prover is generally an implementation of one of the proof systems highlighted above.
27/ Prover systems are computationally intensive and can take a while to run depending on the scale of the problem.
This is due to the use of complex operations that run behind the scenes.
We can expect these systems to become faster and more efficient over the next few years.
28/ In summary: We construct arithmetic circuits to describe statements.SNARKs allow a prover to generate a short proof that they know a solution to a given statement (e.g. h(x) = 0). These proofs can be verified quickly.
29/ For a SNARK to be a zk-SNARK, no information about the solution is conveyed in the proof to the verifier. Some SNARK systems have trusted setup processes to ensure verification time is fast. There are many, many kinds of proof systems, and its a growing area of study.
30/ Some useful resources for learning more:
ZK Whiteboard Sessions from @__zkhack__
31/ "Parameter Generation" from @zcash.
This piece describes into how Zcash generated public parameters for their initial Sprout system as well as the Powers of Tau ceremony for Sapling.
32/ learn.0xparc.org from @0xPARC:
33/ "Episode 38: Intro to zkSNARKs with Howard Wu" from
34/ "Explaining SNARKs" by @rel_Aztec.
A more mathematical look into SNARKs for those interested.
35/ "Introduction to Zero Knowledge Proofs" from @leanthebean:
36/ As always, my DMs are open!
Thanks to @nonieengel and @yb_effect for feedback!