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 π^{}

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!^{}

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 β^{}

Check it out below β

https://twitter.com/varunshenoy_/status/1571949645085155328

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 (Γ).^{}

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.^{}

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.^{}

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.^{}

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.^{}

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.^{}

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.^{}

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^{}

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.^{}

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.^{}

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.^{}

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.^{}

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.^{}

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! π π π^{}

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.^{}

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.^{}

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.^{}

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.^{}

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.^{}

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.^{}

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β¦)^{}

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.^{}

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).^{}

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.^{}

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.^{}

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.^{}

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.^{}

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__

zkhack.dev/whiteboard/modβ¦^{}

ZK Whiteboard Sessions from @__zkhack__

zkhack.dev/whiteboard/modβ¦

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.

z.cash/technology/parβ¦^{}

This piece describes into how Zcash generated public parameters for their initial Sprout system as well as the Powers of Tau ceremony for Sapling.

z.cash/technology/parβ¦

33/ "Episode 38: Intro to zkSNARKs with Howard Wu" from @zeroknowledgefm and @1HowardWu

zeroknowledge.fm/38-2/^{}

zeroknowledge.fm/38-2/

34/ "Explaining SNARKs" by @rel_Aztec

A more mathematical look into SNARKs for those interested.

electriccoin.co/blog/snark-expβ¦^{}

A more mathematical look into SNARKs for those interested.

electriccoin.co/blog/snark-expβ¦

37/ Interested in reading more content from Chapter One Labs? Check out the @chapterone library!

threadsby.me/its/chapterone^{}

threadsby.me/its/chapterone

β’ β’ β’

Missing some Tweet in this thread? You can try to
force a refresh

γ
**
Keep Current with
Varun Shenoy
**

Stay in touch and get notified when new unrolls are available from this author!

**
This Thread may be Removed Anytime!**

Twitter may remove this content at anytime! Save it as PDF for later use!

- Follow @ThreadReaderApp to mention us!
- From a Twitter thread mention us with a keyword "unroll"

`@threadreaderapp unroll`

Practice here first or read more on our help page!

Sep 19
Read 31 tweets

Zero knowledge proofs (ZKPs) will revolutionize how we think about privacy and scaling computation.

And they're just starting to take off.

Don't want to get left behind?

Here's a quick primer, just for youπ

And they're just starting to take off.

Don't want to get left behind?

Here's a quick primer, just for youπ

1/ Despite becoming popular only recently in the context of crypto, ZKPs have a rich history.

In 1987, @JamesGleick published an article in The New York Times titled "A NEW APPROACH TO PROTECTING SECRETS IS DISCOVERED".

nytimes.com/1987/02/17/sciβ¦

In 1987, @JamesGleick published an article in The New York Times titled "A NEW APPROACH TO PROTECTING SECRETS IS DISCOVERED".

nytimes.com/1987/02/17/sciβ¦

Support us! We are indie developers!

This site is made by just two indie developers on a laptop doing marketing, support and development! Read more about the story.

**Become a Premium Member** ($3/month or $30/year) and get exclusive features!

**Make a small donation** by buying us coffee ($5) or help with server cost ($10)

Or Donate anonymously using crypto!

**Ethereum**

`0xfe58350B80634f60Fa6Dc149a72b4DFbc17D341E`

copy

**Bitcoin**

`3ATGMxNzCUFzxpMCHL5sWSt4DVtS8UqXpi`

copy

Thank you for your support!

Email the whole thread instead of just a link!

Separate emails with commas