Math 480A2: Mathematics of Blockchain, Fall 2022

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,
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

Homework Assignments

Assignments will be posted here in PDF and LaTeX format throughout the course.

Week # Topic Due Date PDF TeX
1 Freivalds' Algorithm Sep. 1 PDF TeX
2 Rings, Ideals, and Polynomials Sep. 8 PDF TeX
3 Algebraic Field Extensions and Irreducible Polynomials Sep. 15 PDF TeX
4 Finite Fields Sep. 22 PDF TeX
5 Elliptic Curve Arithmetic and Bézout's Theorem Sep. 29 PDF TeX
6 Elliptic Curves Over Finite Fields and Discrete Logarithms Oct. 6 PDF TeX
7 Discrete Probability Oct. 13 PDF TeX
8 Schwartz-Zippel Lemma and Sum-check Protocol Oct. 20 PDF TeX
9 Arithmetization and Interpolation Oct. 27 PDF TeX
10 Zero-knowledge, Proofs of Knowledge, and Commitment Schemes Nov. 3 PDF TeX
11 Zero-knowledge 3-colorability Protocol, Merkle Trees Nov. 10 PDF TeX
12 KZG commitments, Circuit and R1CS Satisfiability Nov. 17 PDF TeX
13 Interactive Oracle Proofs, IOP for R1CS-Sat Dec. 1 PDF TeX
14 SNARKs Dec. 8 PDF TeX

Select Lecture Notes

Week # Topic PDF
2 Rings and Polynomials PDF
3 Algebraic Field Extensions PDF
4 Finite Fields PDF
5 Elliptic Curves PDF
6 Elliptic Curve Cryptography PDF
7 Probability and the Schwartz-Zippel Lemma PDF
8 Interactive Proofs and the Multivariate Sum Check Protocol PDF

Final Project

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.