Course Information
- Instructor: Prof. Yupeng Zhang zhangyp@illinois.edu
- Lectures: MW 3:30 pm - 4:45 pm
- Office Hour: By appointment
- Location: 3020 ECEB
Course Description and Prerequisites
This course covers topics of zero-knowledge proofs and their applications in machine learning and blockchain to enhance privacy, integrity and scalability. We will discuss the basic concepts and state-of-the-art constructions of these cryptographic schemes. Additionally, we will talk about how to use these techniques to construct privacy-preserving blockchain and crypto-currencies, zkRollups and zkEVM, and zero-knowledge proofs for machine learning. We will focus on efficiency and scalability constraints in practice, and discuss challenges and solutions to efficiently realize these cryptographic protocols.
Prerequisites: CS 407 or equivalent courses approved by the instructor. Basic knowledge of algorithms, data structures and programming is recommended.
Textbook and Resource Materials
MOOC on Zero-Knowledge Proofs: https://zk-learning.org/
No textbook is required for the course. Reading materials will be posted online during the semester
Schedule (tentative)
| Date | Topic | Readings | Deadline |
|---|---|---|---|
| Week 1 | Logistics, background, and introduction to verifiable computation and zero-knowledge proof | Merkle Hash Tree | |
| Week 2 | Polynomial commitments | Polynomial commitments | |
| Week 2 | Generic solutions: interactive proofs | ||
| Week 3 | |||
| Week 3 | Generic solutions:Plonk | Plonk | Team Formation |
| Week 4 | Introduction to blockchain and cryptocurrency | Bitcoin | |
| Week 4 | Pricacy-preserving crypto-currencies | ||
| Week 5 | Generic solutions: SNARK | ||
| Week 5 | Proposal due | ||
| Week 6 | Smart contract | ||
| Week 6 | Privacy-preserving smart contract, zkRollup and zkEVM | Hawk | |
| Week 7 | ZKP based on error-correcting codes | ||
| Week 7 | Interactive Oracle Proofs and FRI | FRI | |
| Week 8 | Midterm Presentation | ||
| Week 8 | |||
| Week 9 | Spring Break | ||
| Week 10 | Zero-knowledge proofs for machine learning CNN | zkCNN | |
| Week 10 | Zero-knowledge decision tree | Zero-knowledge decision trees | |
| Week 11 | Dynamic zkSNARKs | ||
| Week 11 | Linear-time encodable codes | ||
| Week 12 | RAA code | ||
| Week 12 | Recursive SNARKs | ||
| Week 13 | Folding | ||
| Week 13 | Distributed SNARKs | ||
| Week 14 | Lookup Arguments | ||
| Week 14 | Final Presentation | ||
| Week 15 | Final Presentation | ||
| Week 15 | Final Presentation | ||
| Week 16 | Final Presentation | ||
| Week 16 | Final report | Final report due |
Grading
Class Participation: 10%.
Reading assignments: 30%. Students will submit reviews for one of the reading materials every 1-2 weeks. The reviews should include a brief summary of the paper, the contributions, weaknesses and potential improvements.
Course project: 60%. Project (60%): Students will form groups and complete research projects related to the topics of the course. The grading consists of a project proposal, a mid-term progress report, a final presentation and a final project report. Students may propose their own topics or choose from a list of suggested topics on secure multiparty computations, verifiable computations and zero knowledge proof, privacy-preserving machine learning and blockchain.
- Proposal (10%)
- Mid-term presentation (10%)
- Final presentation (20%)
- Final report (20%)
Suggested topics for projects:
Blockchains
- Information inference from public data on Bitcoin blockchain: 1. Understand the public data posted on the blockchain of Bitcoin and figure out ways to download the data. 2. Repeat data analysis from existing papers. 3. Design new attacks to infer sensitive information from the public data, such as dead coins and large volume transactions and its correlations with the price of bitcoin.
- Information inference from public data on Ethereum: Same as bitcoin. In addition, analyze the smart contracts.
- Scaling up blockchains: Understand zk-rollup and its relationship to zero knowledge proofs. Survey existing protocols and challenges. Other techinques: sharding, optimistim rollup etc.
Zero Knowledge Proof
- Zero knowledge proof for machine learning model predictions: generate a proof that the predictions of a secret model on a public testing dataset reaches certain accuracy. Design efficient ZKP protocols for neural networks, CNN, GNN, RNN etc.
- Privacy-preserving smart contracts: 1. Understand the mechanism of smart contract. 2. Find commonly used smart contracts on existing blockchains and cryptocurrencies. 3. Given general purpose ZKP, design protocols for privacy-preserving smart contracts. 4. Implement the ZKP protocol using existing libraries and optimize for those commonly used smart contracts.
- Distributed and memory-efficient zero-knowledge proofs: improve the scalability of ZKPs via a protocol with sublinear memory usage, or a distributed protocol with multiple machines.
- Zero knowledge proof for graph algorithms: generate a proof that the result of graph algorithm is correct. Design efficient ZKP protocols for shortest path etc.