ZK Class: Introduction to ZKP

Introduction

The speaker introduces themselves and the topic of the class, zero knowledge proofs. They apologize for technical difficulties and explain how the class came to be.

About the Speaker

• The speaker likes math and cryptography.

• They have been studying cryptography since 2013.

• They are a member of Nomis.

About Zero Knowledge Proofs

• Zero knowledge proofs are a new development in cryptography.

• Encryption is traditional cryptography, while zero knowledge proofs are newer.

• Zero knowledge proofs are used in blockchain technology.

Story of the Class

• The speaker's friends asked them to teach a class on zero knowledge proofs.

• The speaker decided to open it up on Twitter and many people signed up.

• The speaker was not expecting so many sign-ups and had to change their plans.

Class Information

The speaker provides information about the structure of the class, when it will be held, and how it will be recorded.

Class Schedule

• Classes will be held at 1400 UTC on Mondays and Thursdays.

Recording

• Classes will be recorded and posted on YouTube.

About Me

The speaker talks more about themselves, including their interest in NFTs and their background in math competitions.

Personal Interests

• The speaker enjoys NFTs even if they lose money.

• They have never had a beard like their profile picture suggests.

Background in Math Competitions

• The speaker did a lot of math competitions growing up.

• They always knew they wanted to do something hands-on with math that applied to the real world.

Cryptography

The speaker talks more about cryptography, including encryption, code breaking, and algebraic structures.

Traditional Cryptography

• Encryption is a traditional form of cryptography.

• It involves codes and code breaking.

Algebraic Structures

• Algebraic structures are used in cryptography.

• Zero knowledge proofs use algebraic structures.

Story of the Class (Continued)

The speaker continues their story about how the class came to be and apologizes for being unorganized.

Unexpected Sign-Ups

• The speaker was not expecting so many people to sign up for the class.

• They had to change their plans because of it.

Apology for Being Unorganized

• The speaker apologizes for being unorganized due to the unexpected number of sign-ups.

• They hope that things will get better as time goes on.

Course Outline

In this section, the instructor goes over the course outline and what will be covered in each class.

Class 1: Introduction

• The first class is an introduction to zero-knowledge proofs.

• The instructor aims to cover the main topics and provide a concrete understanding of how ZK works.

Class 2: Industry Overview

• This class covers different companies using ZK and Y, including Ethereum's L2 scaling model.

• The instructor will go through various privacy applications like Tornado Cash or Zcash.

Class 3: Types of Zero Knowledge Proofs

• This class delves deeper into types of zero-knowledge proofs such as snarks versus starks.

• Different algorithms like plonk, plunkish, plonky, bulletproofs are explained.

Class 4: Math Details

• This class covers more math details related to zero-knowledge proofs.

Class 5 & 6: Programming Surcom

• These classes focus on programming surcom so that students can write their own circuits.

Class 7: Deep Dive on Elliptic Curve Pairings

• This class provides a full deep dive on elliptic curve pairings and why they come up in ZK technology.

Class 8: Summary and Future Thoughts on ZK Technology

• The final class summarizes everything covered in the course and provides thoughts on the future of ZK technology.

Background Experience with ZK Tech

In this section, the instructor talks about their background experience with zero-knowledge technology.

• The instructor started studying zero-knowledge proofs about a year ago when they became interested in blockchain technology.

• They aim to provide a solid overview for beginners so that by the end of the course, students should have intermediate knowledge of ZK technology.

Introduction to Zero Knowledge Proofs

In this section, the speaker introduces the concept of zero knowledge proofs and explains how it can be used for verifiable computation.

What is Zero Knowledge?

• Zero knowledge is a field of verifiable computation that allows one to prove that a computation was done correctly.

• The power of zero knowledge lies in its ability to verify computations without revealing any information about them.

• Many applications labeled as "zero knowledge" may not actually require privacy features.

Background in Mathematics

• Polynomials are a key component of zero knowledge proofs.

• Different polynomials are mostly different, which allows us to check if two polynomials are the same by checking them at one point.

Motivating Problem

• How do you know if someone has your data when sending it over an untrusted network?

• A solution will be presented later on in the class.

Verifiable Computation

In this section, the speaker discusses the problem of verifying computations and introduces the concept of verifiable computation.

The Problem of Verifying Computations

• The problem of verifying computations is ubiquitous.

• Solution 1 to verify if all data points are saved is to ask for all million data points back from Eve. This solution is not efficient when doing a computation.

• Solution 2 is to ask Eve to send one value back at a time. However, this method is also inefficient as it requires asking for many values.

Making a Polynomial through All Points

• A polynomial can be made through all data points, and then evaluated at one random point outside the original data.

• If Eve has all the data points, she will be able to make the correct polynomial and evaluate it correctly.

• If Eve does not have all the data points, there will be a strong probability that she will mess up with a high percentage of times.

Achievable Problems

In this section, the speaker talks about how it is possible to get a million data points by just asking for one point. This idea can give intuition for how achievable problems are.

Understanding Achievable Problems

• It is possible to get a million data points by just asking for one point.

• This idea can give intuition for how achievable problems are.

Desired Properties of Ethereum

In this section, the speaker discusses the desired properties of Ethereum and what they want to achieve with it.

Desired Properties of Ethereum

• The desired properties of Ethereum include being cheap to verify and generate.

• They don't want Eve to have to do too much work generating proofs.

• They want proof size to be small.

• Recent ZK developments aim at making proofs cheaper for Eve.

ZK Snarks

In this section, the speaker introduces ZK snarks as a solution that meets their desired properties.

Introduction to ZK Snarks

• ZK snarks meet the desired properties of being cheap to verify and generate while keeping proof size small.

• The goal is to make the solution non-interactive so that proofs can be posted once without back-and-forth communication between parties.

Generating a Polynomial Proof

In this section, the speakers discuss how to generate a polynomial proof that can be verified without revealing the data. They explain why it is important to prevent Eve from having control over the evaluation point and introduce the concept of trusted setup.

Preventing Eve from Cheating

• To prevent Eve from cheating, we shouldn't let her pick the evaluation point.

• The task is for Eve to generate a polynomial to prove that the data has been processed and the result is uniquely verifiable.

• We want Eve to be able to generate the entire proof on our own but still not let her pick whichever evaluation point she wants.

Fiat-Shamir Transformation

• The Fiat-Shamir transformation is used when we don't want you to pick the points so we're going to use a trusted setup.

• Trusted setup means everyone in the world agrees on some randomness.

• A hash function is used in this example where Peggy has no control over what output of hash will be because no one can reverse engineer hash functions.

• By taking hash, we end up with this value C that Peggy couldn't have known ahead of time.

Using Randomness in Cryptographic Algorithms

In this section, speakers discuss using randomness in cryptographic algorithms and how it helps keep information zero knowledge.

Discrete Logarithm Problem

• The discrete logarithm problem involves proving that you know some X such that when you raise G to power X, you get some Y which is public.

• We include some randomness as a blinding factor so that we don't reveal information about what's happening and keep it zero knowledge.

• Hash function comes into play here as it's like a one-way function and by taking its hash, we end up with value C which Peggy couldn't have known ahead of time.

Trusted Setup

• Trusted setup is used in ZK snarks where everyone agrees on some randomness.

• There are whole ceremonies with multi-party computation where everybody adds a little randomness in and as long as one person did it correctly, there's going to be some random value.

• The future zero knowledge proofs can refer to this random value in the trusted setup.

Making Proofs Non-Interactive

In this section, the speaker discusses how to make proofs non-interactive using a hash function and polynomial commitment.

Discrete Logarithm Problem

• The discrete logarithm problem is used to create a wave so that Eve cannot pick the points.

• A hash function is used to generate an output that is uncontrollable.

Polynomial Commitment

• To make solutions more efficient, a polynomial commitment is used instead of reading the whole polynomial.

• This allows for checking only certain points rather than all of the data.

• Merkle trees are used as a data structure for polynomial commitments.

Merkle Trees

• Merkle trees start with data blocks at the bottom and hash them together to create a top hash.

• The top hash can be put on the blockchain or sent over to commit to everything below it.

• Hash functions are one way, so the only way to get the top hash is by starting with the data and going through all of the hashes.

Polynomial Commitment and Fry

In this section, the speaker discusses polynomial commitment and Fry, which stands for fast read Solomon interactive Oracle proofs of proximity.

Polynomial Commitment

• A top hash is a sort of a commit polynomial commitment.

• The coefficients of the polynomials are committed to by posting the top hash to the blockchain.

• There are scaling solutions to blockchains by storing some data on-chain and having the rest off-chain.

• The problem with polynomial commitment is that if one is not going to read the whole polynomial, how do they know it's a polynomial?

• Vitalik has a blog post on Fry (fast read Solomon interactive Oracle proofs of proximity), which refers to polynomials that are fast and interactive Oracle proofs.

Fry

• Interactive Oracle proofs involve back-and-forth checking of points.

• Proofs of proximity ensure that it's close to small polynomials most of the time.

• Arrange data points into a grid and check rows, columns, and diagonal points to ensure it's a low degree polynomial.

• Combining with Merkle tree involves committing to entire data structure so that specific pieces can be requested later.

Recursive Snarks

In this section, the speaker talks about recursive snarks as an improvement over current methods.

Recursive Snarks

• Instead of verifying proof directly, verify that proof verifies by coming up with another proof or quick check.

• Condense all information down into quick check.

Markle Trees and Rank One Constraint System

In this section, the speaker explains how Markle trees work and why they are useful in zero-knowledge proofs. The speaker also introduces the concept of rank one constraint system (R1CS) as an intermediate representation of code that can be fed into a zero-knowledge proof.

Markle Trees

• Hashing all data together is not efficient for verifying specific pieces of data.

• Markle trees allow for quick verification by checking only relevant hash values instead of every single piece of data.

• This cheap verification cost makes Markle trees ideal for use in zero-knowledge proofs.

Rank One Constraint System (R1CS)

• R1CS is an intermediate representation of code that can be fed into a zero-knowledge proof.

• R1CS involves converting code to polynomials using logic gates such as plus and times.

• The output is a polynomial that represents the computation performed by the original code.

Zero-Knowledge Proofs with Snarks

In this section, the speaker explains how to convert code into a format suitable for use in zero-knowledge proofs with snarks. They also discuss how snarks can be used to verify computations without revealing any sensitive information.

Converting Code to Snark-Friendly Format

• Code must be converted to r1cs or another snark-friendly format before it can be used in a zero-knowledge proof.

• The snark requires a trusted setup with randomness parameters.

• The verifier is typically a smart contract on the blockchain, while the prover generates a proof and sends it to the verifier.

Verifying Computations with Snarks

• Snarks can be used to verify computations without revealing any sensitive information.

• Efficiency for both the prover and verifier is a main concern in using snarks.

Resources for Learning ZK

In this section, the speaker recommends resources for learning Zero Knowledge (ZK) concepts and programming.

Recommended Resources

• ZK Whiteboard Sessions by ZK Hack: A series of 11 or 12 videos on ZK concepts. The first three videos by Dan Benet are highly recommended.

• ZK Hack Discord: A community of smart people from the ZK community who can help with questions.

• ZK Podcast: A podcast that covers various topics related to ZK.

• Ox Park's ZK Class: A practical class for programmers to learn Hands-On programming.

Incentives and Scalability in ZK

This section discusses incentives and scalability in using Zero Knowledge (ZK) proofs.

Incentives for Provers and Verifiers

• Transaction fees are the incentive for provers and verifiers. The more proofs added, the less reward to users involved.

• As scale increases, efficiency improves. For example, if a Merkle tree has only four values, it is not very efficient. However, if it has a billion values, it becomes much more efficient.

• Roll-Ups generate a proof every couple of hours because batching many things at once into one short simple proof is more efficient than generating one every minute.

Sharing Information to Generate Proof

• To generate a proof, you need the code or circuit and the Trusted setup.

• From the Stark process, you get R1CS to feed into the snark, which produces a verifier and prover.

• Once you have the proof and a way to verify it, you can post it on the blockchain.

Use Cases for ZK

This section discusses use cases for Zero Knowledge (ZK) proofs.

Incentives for Non-Financial Tasks

• The incentive for using ZK in non-financial tasks is when the proverb doesn't trust the verifier.

Recap of Information Shared to Generate Proof

• To generate a proof, you need the code or circuit and the Trusted setup.

• From the Stark process, you get R1CS to feed into the snark, which produces a verifier and prover.

• Once you have the proof and a way to verify it, you can post it on the blockchain.

Introduction

In this section, the speaker introduces the course and outlines what will be covered.

Course Content

• The speaker plans to cover different companies and their privacy applications.

• They plan to do five or ten-minute breakdowns of as many different companies and applications as possible.

• The speaker invites suggestions for favorite blockchain using CK.

Security Auditing ZK Systems

In this section, a participant asks about gaining competency in auditing ZK systems, and the speaker provides resources for learning.

Learning Resources

• Trail of Bits has a good resource on common ZK security vulnerabilities.

• The speaker plans to cover this topic in one of their later classes.

• They recommend checking out Trail of Bits or Outpost for more information.

Hands-On Coding

In this section, the speaker discusses getting hands-on coding experience with ZK systems.

Programming Classes

• Week three will include hands-on coding.

• The speaker plans to show more than just a "hello world" example.

• They want to focus on one component in detail instead of trying to cover everything at once.

• Classes five and six will be entirely focused on programming.

Homework and Questions

In this section, the speaker addresses questions from participants and encourages them to ask questions that are helpful for everyone.

Questions and Homework

• Participants can post questions in Discord if they have specific ones related to industry overview or other topics covered in class.

• The class will be better if the questions asked are helpful for everyone else.

Conclusion

In this section, the speaker concludes the class by thanking participants and inviting them back for future classes.

Final Thoughts

• The speaker plans to practice streaming in the next few days to improve stream quality and size.

• They are happy that so many people are interested in ZK systems.

• The speaker hopes to give a good introduction to ZK systems and generate excitement for future topics.

• Participants can be in Discord voice while the speaker streams on YouTube.