Welcome! This mathematics, cryptography, and theoretical computer science course will aim to introduce the theory of succinct non-interactive arguments of knowledge (SNARKs), including necessary background in abstract algebra, cryptographic primitives, and verifiable computation. This topic has extensive applications in production software used in the developing cryptocurrency and decentralized finance industries, and during the course we will aim to develop the theory sufficiently to study and understand the mechanics of at least one currently deployed SNARK system. For details on grading, policies, and a tentative weekly schedule, please see the course syllabus.
Instructor: Bryan Gillespie, Bryan.Gillespie@colostate.edu
Class time and location: Tuesdays and Thursdays 8:00-9:15 am, C364 Clark Building
Office Hours: Tuesdays 9:30-10:30 am and Thursdays 11:30-12:30 am, 119 Weber Building
Textbook: Proofs, Arguments, and Zero-Knowledge by Justin Thaler
Final project presentations: Thursday, Dec. 15, 9:40-11:40 am, C364 Clark Building
Assignments will be posted here in PDF and LaTeX format throughout the course.
| Week # | Topic | Due Date | TeX | |
|---|---|---|---|---|
| 1 | Freivalds' Algorithm | Sep. 1 | TeX | |
| 2 | Rings, Ideals, and Polynomials | Sep. 8 | TeX | |
| 3 | Algebraic Field Extensions and Irreducible Polynomials | Sep. 15 | TeX | |
| 4 | Finite Fields | Sep. 22 | TeX | |
| 5 | Elliptic Curve Arithmetic and Bézout's Theorem | Sep. 29 | TeX | |
| 6 | Elliptic Curves Over Finite Fields and Discrete Logarithms | Oct. 6 | TeX | |
| 7 | Discrete Probability | Oct. 13 | TeX | |
| 8 | Schwartz-Zippel Lemma and Sum-check Protocol | Oct. 20 | TeX | |
| 9 | Arithmetization and Interpolation | Oct. 27 | TeX | |
| 10 | Zero-knowledge, Proofs of Knowledge, and Commitment Schemes | Nov. 3 | TeX | |
| 11 | Zero-knowledge 3-colorability Protocol, Merkle Trees | Nov. 10 | TeX | |
| 12 | KZG commitments, Circuit and R1CS Satisfiability | Nov. 17 | TeX | |
| 13 | Interactive Oracle Proofs, IOP for R1CS-Sat | Dec. 1 | TeX | |
| 14 | SNARKs | Dec. 8 | TeX |
| Week # | Topic | |
|---|---|---|
| 2 | Rings and Polynomials | |
| 3 | Algebraic Field Extensions | |
| 4 | Finite Fields | |
| 5 | Elliptic Curves | |
| 6 | Elliptic Curve Cryptography | |
| 7 | Probability and the Schwartz-Zippel Lemma | |
| 8 | Interactive Proofs and the Multivariate Sum Check Protocol |
Final projects will consist of a write-up and short presentation on a chosen topic. Presentations will take place during the scheduled final exam block during finals week, and write-ups are due at this time. The project description, rubric, and topic ideas can be found here.