[MIT IAP 2023] Modern Zero Knowledge Cryptography

The stream link is here for all lectures. Please reach out to zk-iap-2023@0xparc.org with any questions!

What is this course?

The Modern Zero Knowledge Cryptography IAP program surveys recent advancements in zero-knowledge cryptography over the last ten years, with a strong emphasis on their practical and user-facing applications.

Topics covered range from the mathematical foundations of modern zero-knowledge protocols (interactive protocols, elliptic curve cryptography, pairing-based cryptography, polynomial commitment schemes, zkSNARKs, and more) to practical constructions of digital systems enabled by ZK primitives (privacy-preserving identity and reputation systems, anonymous digital transaction systems, verifiable computation, and more). Towards the end of the course, students will implement their own “zero-knowledge circuits” that can be integrated into practical applications.

The focus of this course will be on developing a conceptual understanding of modern zero-knowledge. As this four-week course is intended to be a survey of the “full-stack” landscape, from theory to application, less emphasis is placed on precise mathematical rigor, and more emphasis is placed on conveying the big picture ideas and methods that commonly appear in modern ZK applications.

The Modern ZK Crypto program has three components: lectures and workshops, optional (ungraded) problem sets and exercises, and an optional project component which interested students are highly encouraged to participate in.

Lecture schedule & materials

Recordings, slides, notes, and exercises are included in the dropdowns, updated after each session. Sessions are 90m each, held on MWF from 2-3:30pm in 4-237 (with the exception of MLK day, when lecture is held on Tuesday instead).

Session 1 (Monday 1/9) Introduction to ZK (Brian Gu)

We’ll give an overview of the course, and a whirlwind tour of modern zero-knowledge techniques and applications. This session will approach the “why” of the course: why has ZK been such an exciting topic lately, and why do we think that it has the potential to one of the biggest technology stories of the next decade?

Recording Link

Slides

Lecture Notes

Exercises

Session 2 (Wednesday 1/11) Circom 1 (Brian Gu)

This session focuses on practical zkSNARK circuit engineering: using a toolstack (circom/snarkjs/zkREPL) for the groth16 zkSNARK protocol to build simple zero-knowledge proofs. We’ll discuss the R1CS programming model (and cost model), and simple circuit components such as bit operators, range checks, and more.

Recording Link

Slides

Lecture Notes

Exercises

Session 3 (Friday 1/13) Mathematical building blocks (Yufei Zhao)

In this session, we’ll discuss some of the basic “building blocks” of modern proof systems, including: formalization of zero-knowledge, discrete logarithm and other common cryptographic sources of “hardness,” elliptic curve cryptography, and pairing-based cryptography.

Recording Link

Lecture notes - math building blocks.pdf3210.7KB
Exercises - math building blocks (updated Jan 14)122.4KB
Session 4 (Tuesday 1/17) Circom 2 (Vivek Bhupatiraju)

Note that this session will take place on Tuesday, as Monday is MLK day.

Building off “Circom 1,” we’ll write and discuss more complex circuits: inclusion proof verification, hash functions, signature and encryption verification.

snarkjs resources

Recording Link

Slides

Lecture Notes

Exercises: Check out https://semaphore.appliedzkp.org/ and set up a starter project!

Session 5 (Wednesday 1/18) Commitment Schemes (Ying Tong Lai)

We’ll build off of the “mathematical building blocks” session to construct vector, univariate polynomial, and multivariate polynomial commitment schemes.

Recording Link

Lecture Notes - Commitment Schemes.pdf315.0KB
Exercises - Commitment Schemes.pdf103.3KB
Solutions 5 - Commitment Schemes.pdf173.7KB
Session 6 (Friday 1/20) Algorithms for Efficient Cryptographic Operations (Jason Morton)

We’ll discuss techniques for efficient openings and polynomial arithmetic, including number-theoretic transform (NTT); multi-scalar multiplication (MSM); fast elliptic curve double-and-add operations.

Recording Link

Lecture Notes

6th session notes.pdf57599.4KB
Session 7 (Monday 1/23) Arithmetizations (Ying Tong Lai)

We discuss a few examples of arithmetizations—intermediate representations of ZK programs and circuits which can be consumed by a proving system.

Recording Link

Lecture Notes - Arithmetisations.pdf389.3KB
Session 8 (Wednesday 1/25) PLONK and polynomial identities. (Jason Morton)

We dive into the PLONK zkSNARK protocol—a zkSNARK construction based on polynomial commitment schemes, and a particular PLONK-style arithmetization. We also discuss arguments like LOOKUP, built from polynomial identities.

Recording Link

Lecture Notes

8th Session notes.pdf57184.7KB
Session 9 (Friday 1/27) Proving systems stack; recursion and composition. (Ying Tong Lai)

Based on the learnings from previous four sessions, we’ll give an overview of the zkSNARK protocol landscape, and build up a taxonomy of proving systems. We’ll also discuss proof system recursion and composition.

Recording Link

Lecture 9 - Proof Systems Stack.pdf438.2KB
Lecture 9 - Recursion & Proof Composition.pdf7964.1KB
Session 10 (Monday 1/30) Applied ZK Constructions 1 (Aayush Gupta)

We’ll discuss ZK constructions in the wild: membership proofs for pseudonymous messaging, nullifier-based constructions for private digital currency transfers, zk-email, and more.

Recording Link

Slides

Session 11 (Wednesday 2/1) Applied ZK Constructions 2 (Brian Gu)

We’ll discuss additional uses of zkSNARKs: incomplete information games, encrypted data marketplaces, ZKML, ZKVMs, recursive ZK proofs, and more.

Recording Link

Slides 1

dark forest - zkiap.key43063.1KB
Session 12 (Friday 2/3) Student and Staff Demos

In our final session, students and staff will demonstrate projects and ZK applications that they’ve been working on over IAP!

Recording Link

Student Notes

fareed_sheriff_notes_updated_jan_31_2023.pdf561.4KB
  • This excellent set of notes by ZKIAP participant Fareed Sheriff goes through a lot of the prerequisite material found at learn.0xparc.org
  • Currently goes up to Lecture 9 - Proof Systems

Course Staff

This course is designed and taught by a team of researchers and developers, with experience across the applied zero-knowledge cryptography “stack.”

Ying Tong Lai is a researcher at Geometry and 0xPARC. Previously, she was a senior engineer at Electric Coin Company, and a core developer of the Halo2 zkSNARK protocol and library.

Yufei Zhao is an Associate Professor of Mathematics at MIT.

Brian Gu is co-founder of 0xPARC Foundation, an R&D organization developing open-source infrastructure for applications of zero-knowledge cryptography.

Jason Morton is an Associate Professor of Mathematics at Penn State and the CEO of ZKonduit, where he is building tools for zero-knowledge machine learning inference.

Aayush Gupta is a research steward at ZK Email, a research group focused on building zero-knowledge primitives based on emails.

Vivek Bhupatiraju is building useful applications using cryptography.

Prerequisites

You should have familiarity with:

  • Elementary number theory and group theory. You should be comfortable working through the material in this handout from MIT’s 6.875 (Foundations of Cryptography) course.
  • Basic cryptographic primitives. You should be comfortable with the idea of hash functions, encryption and signature schemes, and cryptographic accumulators (i.e. Merkle Trees); ideally, you’ve had some experience using and manipulating these primitives in practical settings (for example, perhaps you’ve implemented or used a signature verification API in an application).
  • Basic algebraic concepts. You should be comfortable with basic manipulation of polynomials, perhaps with a bit of reading: polynomial multiplication and division, Lagrange interpolation, probabilistic polynomial identity testing, fast Fourier transform, and working in field extensions.

Some engineering or software development experience will also be beneficial, as we’ll be discussing the practical use of modern cryptographic primitives for real applications.

Logistics

This program will take place during MIT’s Independent Activities Period (1/9 - 2/3). This is a not-for-credit program. Communication will take place on a class Discord server. We expect the time commitment for this program to range from 10 to 20 hours per week, depending on whether you opt to join the optional project component, and whether you opt to complete the optional and ungraded problem sets.

Lectures and workshops

  • When: Mondays, Wednesdays, and Fridays, from 2:00 - 3:30PM (with the exception of 1/16, which is MLK day—that session will instead take place on 1/17).
  • Where: Classroom 4-237

Anyone is welcome to attend any lectures, regardless of whether or you are working on a project, or whether you’ve attended previous lectures. Lectures will be recorded and made publicly available.

Office hours

  • When: Tuesdays 10AM - 12PM and Thursdays 5PM - 7PM.
  • Where: 2-136

On Tuesdays and Thursdays, we’ll run smaller office hours / co-working sessions, for students interested in building a ZK project, receiving guidance on the optional problem sets, or learning about supplementary topics.

Class components

Recommended Project

We highly encourage interested to participate in the optional project component, to solidify their understanding of the material. Course staff will provide mentorship for students interested in building a ZK project over the course of the month. Projects may include:

  • A full-stack application of ZK crypto, such as an anonymous voting app, a p2p/decentralized game, a cryptocurrency mixer, etc.
  • A library of useful ZK primitives, such as ZK circuits for a ZK-friendly encryption scheme.
  • An implementation of a zero-knowledge proof system or some key component parts, along with a series of tutorials or writeups.
  • Documentation or educational material, such as a series of blog posts or tutorials explaining a ZK proof system.

Projects from teams that have participated in past 0xPARC educational programs have included:

Certain Tuesday and Thursday office hour sessions will be set aside for project brainstorming, team-matching, and mentorship and co-working sessions.

Interested students should submit a project proposal during the second week of the program. A final demos session will be scheduled in the last week of the program.

Optional Exercises and Problem Sets

Most lectures will be accompanied by problems sets or sets of “conceptual exercises.” These sets may include math problems; understanding questions which ask you to sketch out a protocol at a high level; coding tasks; and more. Problem sets are ungraded, though we highly recommend that you complete them for your own understanding; you’re also welcome to come in on Tuesdays and Thursdays to ask course staff to review your solutions, or to check your understanding.