ZK Learning Group

0xPARC

Today

• Learning group logistics
• Program structure/schedule
• Participant introductions
• Conceptual intro to ZKPs and zkSNARKs
• A few examples of ZK apps
• A few examples of ZK problems (project inspiration!)

Logistics

• Communication is on Discord (no more emails!)
• Discord is home of async discussion as well
• Channel overview
• Turn on notifications and check regularly!
• Resources are in Notion
• Add the Google Calendar
• Most programming is 8-9:30AM PT weekdays, unless otherwise noted
• Sessions will recorded and uploaded
• We might post some online publicly, but we’ll ask you in advance if we do so
• You’ll get the most out of this if you can spend 5-10hr/wk outside of sync sessions

Program Content

• “Applied ZK”: understanding and building user-facing applications with ZK crypto
• These applications are often decentralized apps (“dapps”) for reasons we’ll get into.
• ZK theory - not a primary focus, but we’ll have some resources available
• We’ll mostly be using the circom + snarkjs stack
• This is an experimental program!
• https://learn.0xparc.org

Structure / Schedule

• Weeks 1 + 2: Structured(ish) workshops
• Weeks 3 + 4: Hands-on building a project + guest talks from ZK ecosystem speakers
• Everyone needs to build something!
• Final demos: Friday 4/8 8AM PT (Put this in your calendar)

Week 1

• Tues: Circom workshop #1
• Weds: Overview of SNARK dapps
• Thurs: optional general office hours
• Friday: Circom workshop #2

Week 2

• Mon: lightning talks #1, trusted setup MPC workshop
• Everyone to give a 3m presentation on some ZK-related topic!
• Tues: (optional) topics in applied crypto
• Weds: project ideation
• Thurs: circom workshop #3
• Fri: breaking down tornado.cash

Norms

• Wide range of backgrounds, and areas of expertise: crypto theory, engineering, dapp engineering, …
• No question is too basic!
• We’re here to learn from you too

About 0xPARC

Intros

Thesis

Thesis

• ZK crypto (specifically SNARKs, STARKs, etc. - ZKPs for arbitrary computation) is more important and general than people think it is

​

• ZK crypto is easier to use than people realize it is

Thesis

• Especially important for blockchains: https://gubsheep.substack.com/p/six-moonshot-zk-applications

What is a Zero Knowledge Protocol?

Zero Knowledge Proofs / Protocols

Zero-Knowledge (ZK) crypto lets me prove to you that I know a fact, without telling you the fact.

• I know the private key corresponding to an Ethereum account - but I won’t tell you what my private key is!
• I know a way to fill in a map with 3 colors such that no two adjacent regions are the same color - but I won’t tell you the coloring!
• I know a number x such that SHA256(x) = 0x77af… - but I won’t tell you x!

Zero Knowledge Proofs / Protocols

Setup: a prover wants to convince a verifier that they know something, without revealing the underlying information.

Verifier: Asks questions / issues challenges to the prover, and checks responses.

Prover: Responds to verifier questions or challenges.

​

​

Example: ZK protocol for knowledge of map (3-)coloring

Example: map 3-coloring

Example: map 3-coloring

Example: map 3-coloring

Example: map 3-coloring

Example: map 3-coloring

http://web.mit.edu/~ezyang/Public/graph/svg.html

Zero Knowledge Proofs / Protocols

ZK Protocols have 3 properties:

• The Prover’s responses don’t reveal the underlying information.

Zero Knowledge Proofs / Protocols

ZK Protocols have 3 properties:

• The Prover’s responses don’t reveal the underlying information.
• If the Prover knows the underlying information, they’re always able to answer satisfactorily.

Zero Knowledge Proofs / Protocols

ZK Protocols have 3 properties:

• The Prover’s responses don’t reveal the underlying information.
• If the Prover knows the underlying information, they’re always able to answer satisfactorily.
• If the Prover doesn’t know the underlying info, they’ll eventually get caught.

Zero Knowledge Proofs / Protocols

ZK Protocols have 3 properties:

• [Zero Knowledge] The Prover’s responses don’t reveal the underlying information.
• [Completeness] If the Prover knows the underlying information, they’re always able to answer satisfactorily.
• [Soundness] If the Prover doesn’t know the underlying info, they’ll eventually get caught.

Example 2: Digital Signatures

In Ethereum, all transactions are signed with public-key cryptography.

Every public account is associated with a secret, private key.

You shouldn’t be able to send funds out of an account unless you know the private key to that account.

Example 2: Digital Signatures

A “signature” is attached to every transaction.

Under the hood, a signature is (essentially) a zero knowledge proof that you know the private key corresponding to the public key you’re sending funds from.

ZKPs are not new!

• Digital signature schemes have been around for decades.
• Zero Knowledge protocols for specific problems have been known for decades as well.
• Map 3-coloring
• Graph isomorphism
• Discrete logarithm
• Hash pre-images

ZKPs are not new!

• For each of the above problems, researchers would have to come up with a special-purpose / specific ZK protocol.
• The holy grail: “Here’s an output y and an arbitrary function f. I know a secret value x such that f(x) = y”
• A technique to do this would allow us to verify arbitrary computation (for example, money or digital ownership transfers) with complete privacy

Homomorphic Encryption

Encryption lets you “lock” data

• Many services often store “encrypted” versions of your data
• End-to-end encrypted chat services store encrypted copies of your messages in their servers.
• Sensitive data (medical records, govt records), are often stored under encryption.

​

• Problem: Encrypted data is gibberish, and can’t be indexed or searched or computed on.
• Calculating aggregate statistics on encrypted data sets
• Delegating heavy computations on sensitive data to remote servers

Homomorphic Encryption

• I have two secret numbers x and y that I want to add, but I don’t have the computational power to add them.
• I send you Enc(x) and Enc(y), encrypted with a key that you don’t know the private key to.
• You add Enc(x) + Enc(y) and send the result back to me.
• I decrypt the result to get x + y.

Idea: the homomorphic encryption function Enc “preserves” addition.

Homomorphic Encryption

• I have two secret numbers x and y that I want to add, but I don’t have the computational power to add them.
• I send you Enc(x) and Enc(y), encrypted with a key that you don’t know the private key to.
• You add Enc(x) + Enc(y) and send the result back to me.
• I decrypt the result to get x + y.

Idea: the homomorphic encryption function Enc “preserves” addition.

Enc (x + y) = Enc (x) + Enc (y)

Homomorphic Encryption

• I have two secret numbers x and y that I want to f, but I don’t have the computational power to f them.
• I send you Enc(x) and Enc(y), encrypted with a key that you don’t know the private key to.
• You f(Enc(x), Enc(y)) and send the result back to me.
• I decrypt the result to get f(x, y).

Idea: the homomorphic encryption function Enc “preserves” f.

Enc (f(x, y)) = f(Enc (x), Enc (y))

Homomorphic Encryption

Homomorphic Encryption is like ZK for arbitrary functions

• The holy grail: “Here’s an output y and an arbitrary function f. I know a secret value x such that f(x) = y”

Homomorphic Encryption is like ZK for arbitrary functions

• The holy grail: “Here’s an output y and an arbitrary function f. I know a secret value x such that f(x) = y”
• Solution: homomorphically encrypt x, perform the whole computation f under homomorphic encryption to obtain Enc(y), and reveal the computation to a verifier.
• The verifier can check the whole computation without knowing any of the underlying values!

zkSNARKs

What are zkSNARKs?

• A new cryptographic tool that can efficiently generate a zero-knowledge protocol for any problem or function.
• Properties:
• zk: hides inputs
• Succinct: generates short proofs that can be verified quickly
• Noninteractive: doesn’t require a back-and-forth
• ARgument of Knowledge: proves you know the input

What are zkSNARKs?

High-level idea:

• Turn your problem (graph 3-coloring, discrete log, etc.) into a function whose inputs you want to hide.
• Specifically, an arithmetic circuit - a bunch of + and * operations on prime field elements
• Execute the function inside homomorphic encryption.
• Mathematical magic to “roll up” the function into a short signature of the execution.

zkSNARK Properties

• A new cryptographic tool that can efficiently generate a zero-knowledge protocol for any problem or function.
• Properties:
• zk: hides inputs
• Succinct: generates short proofs that can be verified quickly
• Noninteractive: doesn’t require a back-and-forth
• ARgument of Knowledge: proves you know the input

Applications

Applications

Applications

Applications

What’s hard

• You can prove any function made up of + and * operations on residues modulo the babyjubjub prime (254 bit prime)
• How do you implement functions we care about?
• Simulate bit operations
• Conditionals
• (SNARK-friendly) hash functions
• Procedural generation
• Trig functions
• Pseudorandomness
• Noninteger arithmetic
• Other cryptographic primitives (ECC, PBC)