Lectures
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 SNARK
- Arithmetic Circuits. Circuit Satisfability Problem.
- R1CS in vector and matrix forms.
- Quadratic Arithmetic Program.
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.
- "Quadratic Arithmetic Programs: From Zero to Hero" by Vitalik Buterin: R1CS and QAP demonstrated over real numbers.
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.