Lectures
Lecture 12: PlonK Arithmetization
Speaker: Nikita Masych
Content. Groth16 is not the only zk-SNARK protocol used in practice! In this lecture, we will consider the PlonK protocol, which is frequently used in various zkEVM implementations. Here, we cover:
- PlonK Arithmetization
- How gates work in PlonK. Custom Gates.
- Gate and Wiring Satisfability Checks.
- Permutation Check over Polynomials.
Lecture Material:
Other Helpful Resources:
- "PlonK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge" by Ariel Gabizon et. al.: original paper. Hard to read, but definitely worth it.
- "All you wanted to know about Plonk" by LambdaClass: Probably the most complete and well-explained article on PlonK anatomy.
- "Understanding PLONK" by Vitalik Buterin: Another well-explained and illustrated guide on PlonK.
Lecture 11: Programming ZKPs in Circom
Speaker: Kyrylo Riabov
Content. After covering the Groth16 zk-SNARK theory, we will move to the practical part of the course. Here, we will learn how to use Circom to create circuits and generate proofs. Here, we cover:
- Basic Circom syntax.
- Creating circuits.
- Generating proofs.
- Interpreting all the generated data such as .r1cs, .sym, proof.json, and how they relate to the previously covered theory.
Lecture Material:
Other Helpful Resources:
- "Circom: A Circuit Description Language for Building Zero-Knowledge Applications" by Marta Belles-Munoz et al: Original Circom language paper.
- "Programming ZKPs: From Zero to Hero" by zkintro: Well-explained tutorial on working with Circom.
- "Circom101" by erhant: introduces many practical examples (arithmetic, comparators, hashing, merkle trees etc.) where Circom can be used.
- "Circom language tutorial with circomlib walkthrough" by Team RareSkills: a very detailed tutorial on how to use Circom with practical examples.
Lecture 10: Pairing-based zk-SNARKs
Speakers: Anton Levochko and Dmytro Zakharov
Content. Finally, we consider one of the most advanced zk-SNARKs: Pinocchio and Groth16. Here, we cover:
- Turning QAP into succint verification over encrypted space.
- Making SNARK sound.
- Turning SNARK into zk-SNARK.
- Pinocchio Protocol.
- Groth16 Protocol.
Lecture Material:
Other Helpful Resources:
- "Why and How zk-SNARK Works" by Maksym Petkus: Very easy-to-follow tutorial on how zk-SNARKs work from scratch. Very friendly guide for beginners.
- ZK MOOC, Spring 2023 , "Linear PCP" lecture: amazing lecture on the idea of building Pinocchio and Groth16 protocols, expressed formally and mathematically.
- "Pinocchio: Nearly Practical Verifiable Computation" by Bryan Parno and Craig Gentry: original Pinocchio paper. Quite easy to understand if you are familiar with notation from lecture notes.
- "On the Size of Pairing-based Non-interactive Arguments" by Jens Groth: original Groth16 paper. A bit more formalistic view of the Groth16 protocol and what linear non-interactive proofs are used for.
Lecture 9: Quadratic Arithmetic Program. Probabilistically Checkable Proofs
Speaker: Anton Levochko
Content. With R1CS in our hands, we are now ready to succintly represent it as a Quadratic Arithmetic Program (QAP). Additionally, we consider other basic theory before specifying the Groth16 protocol. Here, we cover:
- Turning R1CS into QAP.
- What is PCP, IPCP, IOP.
- Proof of Exponent.
Lecture Material:
Other Helpful Resources:
- "Why and How zk-SNARK Works" by Maksym Petkus: Very easy-to-follow tutorial on how zk-SNARKs work from scratch. Very friendly guide for beginners.
- "Quadratic Arithmetic Programs: From Zero to Hero" by Vitalik Buterin: R1CS and QAP demonstrated over real numbers.
Lecture 8: SNARKs. Arithmetical Circuits
Speaker: Anton Levochko
Content. This is an opening lecture on SNARKs: technology we are using daily in our projects. Here, we cover:
- The definition of zk-SNARK.
- Arithmetic Circuits. Circuit Satisfability Problem.
- Rank-1 Constraint System (R1CS) in vector and matrix forms.
Lecture Material:
Other Helpful Resources:
- "Why and How zk-SNARK Works" by Maksym Petkus: Very easy-to-follow tutorial on how zk-SNARKs work from scratch. Very friendly guide for beginners.
- "Converting Algebraic Circuits to R1CS" by RareSkills: Also well-explained how R1CS works with many practical examples.
Lecture 7: Sigma Protocols
Speaker: Dmytro Zakharov
Content. Here, we will consider the most basic form of interactive proofs - Sigma Protocols. We will understand how to turn them into non-interactive proofs and how to use them in practice. Here, we cover:
- Schnorr Signature Scheme.
- Sigma Protocols.
- Examples of Sigma Protocols: Okamoto's and Chaum-Pedersen Protocols
- Combining Sigma Protocols.
Lecture Material:
Other Helpful Resources:
- "A Graduate Course in Applied Cryptography" by Dan Boneh and Victor Shoup, Section 19: Very formalistic and rigorous introduction to Sigma Protocols and turning interactiveness to non-interactiveness in the subsequent Section 20.
- "Proofs, Arguments, and Zero-Knowledge" by Justin Thaler, Chapter 12 : quite rigorous description of Discrete Logarithm-based zero-knowledge protocols.
Lecture 6: Introduction to Zero-Knowledge Proofs
Speaker: Dmytro Zakharov
Content. This lecture finally introduces the concept of Zero-Knowledge Proofs and their applications. Here, we cover:
- What is a cryptographic proof exactly?
- Interactive Proofs.
- Soundness and Zero-Knowledge definitions.
- Proof vs Proof of Knowledge.
- Fiat-Shamir Heuristic.
Lecture Material:
Other Helpful Resources:
- "Zero Knowledge Proofs MOOC, Spring 2023" Amazing series of lectures on zero-knowledge proofs. This lecture was primarily based on the first lecture by Shafi Goldwasser.
- "Zero Knowledge Proofs Lecture" by Boaz Barak: very well-explained fundamentals of zero-knowledge proof with a detailed analysis of a quadratic residue interactive protocol.
Lecture 5: Cryptographic commitment schemes
Speaker: Denis Riabtsev
Content. In this lecture we will dive into the design and application of various cryptographic commit schemes that are often used in zero knowledge proof systems. All in all, here we cover:
- Hash-based commitments.
- Vector commitments.
- Polynomial commitments.
Lecture Material:
Other Helpful Resources:
- KZG Commitment Scheme by Scroll, explains the math behind KZG commitment schemes.
- Modern Zero Knowledge Cryptography. Lecture 5 by Ying Tong with formally explained vector and polynomial commitments.
- "What are Pedersen Commitments and How They Work" by RareSkills: an article that explains Pedersen commitments in simple words with code examples in Python.
Lecture 4: Projective Coordinates and Pairing
Speaker: Dmytro Zakharov
Content. This lecture will touch the central part of SNARKs: elliptic curve pairing, its properties and applications. But first, we will cover projective coordinates and how they can be used to optimize elliptic curve operations. All in all, here we cover:
- Relations and equivalence classes.
- Projective Coordinates.
- Adding points in projective coordinates. Scalar multiplication using double-and-add algorithm.
- Elliptic Curve Pairing.
- Pairing applications.
Lecture Material:
Other Helpful Resources:
- "Pairing for Beginners" by Craig Costello: Not only this already mentioned book contains pairing inner working, but also a profound introduction into projective form of elliptic curves.
- "A Graduate Course in Applied Cryptography" by Dan Boneh and Victor Shoup, Section 15. Recommended to read this chapter up to section 15.5 including.
- "BN254 For The Rest of Us" by Jonathan Wang: if you want specifics of pairing-friendly curve parameters, you can take a look here. This curve is currently widely used.
- High-Speed Software Implementation of the Optimal Ate Pairing over Barreto-Naehrig Curves by Jean-Luc Beuchat et al.: if you really want to get into the details of pairing implementation, this paper is the best. It contains all the algorithms to implement pairing from scratch.
Lecture 3: Finite Field Extensions and Elliptic Curves
Speaker: Dmytro Zakharov
Content. Our primary focus will be on Finite Field Extensions, while also covering basics of Elliptic Curves. Here, we cover:
- Finite Field Extensions
- Algebraic Closure
- Elliptic Curve Definition
- Discere Logarithm on Elliptic Curves
Lecture Material:
Other Helpful Resources:
- An Introduction to the Theory of Field Extensions by Samuel Moy: rigorous and "mathematicalish" introduction to what field extensions are. Highly recommended, but maybe too much for basic understanding of finite field extensions.
- "Guide to Elliptic Curve Cryptography" by Alfred Menezes et al.: Amazing book on Elliptic Curves optimizations. It also contains a great introduction into finite fields.
- "Pairing for Beginners" by Craig Costello: Quick dive into inner workings of elliptic curve pairing.
- "A Graduate Course in Applied Cryptography" by Dan Boneh and Victor Shoup, Section 15 (Elliptic curve cryptography and pairings): Elliptic Curves are described very well together with the basics of pairing (without going into the details of construction).
Lecture 2: Security, Polynomials, Lagrange Interpolation
Speakers: Dmytro Zakharov and Denis Riabtsev
Content. In this lecture, we will continue covering the basic mathematics used in cryptography. Here, we cover:
- Basic Security Definitions
- Polynomials
- Lagrange Interpolation: Shamir's Secret Sharing and Reed-Solomon Codes
- Schwarz-Zippel Lemma
- Number Theory
Lecture Material:
Other Helpful Resources:
- "A Graduate Course in Applied Cryptography" by Dan Boneh and Victor Shoup, Section 2 (Encryption): This book can give a fundamental understanding of system security analysis and cryptography formalism. In particular, check Section 2 for introduction to security definitions.
- Reed, Irving S.; Solomon, Gustave (1960), Polynomial Codes over Certain Finite Fields : Original Paper on Reed-Solomon Error Correction.
Lecture 1: Algebra Basics
Speaker: Dmytro Zakharov
Content. In this lecture, we will cover the basic mathematics required for understanding Zero-Knowledge Proving Systems. Here, we cover:
- Basic Set Theory and Logic
- Basic Group Theory
- Fields. Finite Field Arithmetic.
Lecture Material:
Other Helpful Resources:
- Michael Penn's "Abstract Algebra" Youtube Course : one of the best explanations of Algebra I have seen with tons of examples.
- MIT Modern Algebra Class (18.703) : Quite a rigorous course in Algebra, yet still easy-to-follow.
- Visual Group Theory : Very comprehensive list of lectures on Group Theory and Galois Theory with illustrations and many examples.