CIS 7000: Theory and Practice of Succinct Zero Knowledge Proofs
Basics
Instructor: Pratyush Mishra
Time: Tuesdays and Thursdays, 10:15AM11:45AM
Location: Towne 311
Office hours: Thursdays 12PM, Towne 219B
Useful links: Ed Discussions; Canvas
Course Description
Zero knowledge proofs are a core object of study in cryptography that enable a prover to convince a verifier of the truth of a claim in an efficient and private manner. Despite their attractive properties, for most of their history zero knowledge proofs have remained of primarily theoretical interest. However, this has changed in the last decade with the development and deployment of very efficient zero knowledge proof systems called zkSNARKs. In this course, we will cover the mathematical foundations, implementation aspects, and applications of zkSNARKs.
Prerequisites
This course requires a basic background in discrete mathematics (at the level of CIS 1600), and a basic background in algorithms and complexity (at the level of CIS 3200).
Grading
Your grade in the course is determined by the following components:
 Assignments (15%)
 Regular attendance and participation (15%)
 Presenting a paper (25%)
 Completing a final project (45%)
 10% for project proposal (due on 10/10/23)
 15% for presentation
 15% for final report
Schedule
For classes marked as Lecture, the assigned readings are optional.
For classes marked as Discussion, everyone is expected to read the assigned readings are (with the exception of “presenteronly” readings, which are mandatory only for the presenter. Feel free to read them if you want to, though!)
Date  Topic  Resources/Readings 

08/29/2023 Lecture  Introduction and background
 Interactive proofs: 
08/31/2023 Lecture  Interactive Oracle Proofs
 Compiler from IOP to argument system: 
09/05/23 Lecture  Polynomial IOPs
 
09/07/23 Lecture  Marlin PIOP I
 
09/12/23 Lecture  Marlin PIOP II
 
09/14/23 Lab Lecture  Inclass lab for Marlin  Python notebook 
09/19/23 Lecture  Multilinear sumcheck + Spartan PIOP
 
09/21/23 Lecture  PC Schemes from Innerproduct arguments (IPAs)
 
09/26/23 Lecture Lab  KZG PC Scheme
 
09/28/23 Lecture Discussion  Lookup protocols
 
10/03/2023 Lecture  Linear PCPs and IPs
 
10/05/2023 Lab  Inclass lab for Hadamard LPCP + AGMbased linearonly encoding  Python notebook will be provided 
10/10/23 Lecture Discussion Project  IncrementallyVerifiable Computation and ProofCarrying Data
 
10/12/23  No class due to fall break  
10/17/23  No class due to USENIX deadline  
10/19/23 Lecture Discussion  Programming zkSNARKs
 CirC: Compiler infrastructure for proof systems, software verification, and more. Ozdemir, Brown, Wahby. 2020 
10/24/23 Lecture Discussion  Formal verification for zkSNARKs
 
10/26/23 Lecture Discussion  SNARKs for uniform computations
 Sections 1 and 2 of SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge. BenSasson, Chiesa, Genkin, Tromer, Virza. 2013 
10/31/23 Lecture Discussion  Systems aspects of zkSNARKs
 DIZK: A Distributed Zero Knowledge Proof System. Wu, Zheng, Chiesa, Popa, Stoica. 2018 
11/02/23 Lecture Discussion  Privacypreserving payments
 
11/07/23 Lecture Discussion  Privacypreserving smart contracts
 Sections 1 and 2 of Zexe: Enabling Decentralized Private Computation. Bowe, Chiesa, Green, Miers, Mishra, Wu. 2020 
11/09/23 Lecture Discussion  Succinct Blockchains
 Reducing Participation Costs via Incremental Verification for Ledger Systems. Chen, Chiesa, Dauterman, Ward. 2020 
11/14/23 Lecture Discussion  Rollups
 
11/16/23 Lecture Discussion  Collaborative zkSNARKs
 Experimenting with Collaborative zkSNARKs: ZeroKnowledge Proofs for Distributed Secrets. Ozdemir, Boneh. 2022 
11/21/23 Lecture Discussion  Verifiable credentials


11/23/23  No class due to Thanksgiving  
11/28/23 Lecture Discussion  zkSNARKs for Authenticated Edits
 
11/30/23  Societal Aspects of Cryptography Informal discussion, no presentation  
12/05/23 Project  Final Project Presentations  
12/07/23 Project  Final Project Presentations  
12/15/23 Project  Final Project Report Due 
Overview of course grade components
Reading assignments
Each class with a Discussion component will be accompanied by an assignment consisting of 12 shortanswer questions about the assigned reading(s). These assignments will be posted on Canvas, and will be due before class.
Note: you are not required to read papers marked as “Presenter only” in the schedule below.
Attendance and participation
You are expected to attend lectures and participate in discussions, particularly for classes marked Discussion
Paper presentation
You will lead a 4045 minute long discussion on a paper of your choice (from one of the classes marked Discussion). There will be a signup sheet on Ed for choosing papers. The discussion should include a brief presentation of the paper, interspersed with questions and discussion. An example split would be 25 minutes of presentation + 10 minutes of discussion + 5 minutes of feedback.
You can choose whatever presentation tools you see fit (chalkboard, slides, etc.). No matter the medium, you should aim for a presentation that:
 motivates the problem tackled by the paper (most likely in relation to the material I introduce before your presentation), and
 describes at a highlevel the main protocol, idea, or system introduced in the paper.
See here for strategies on how to prepare for this presentation.
Final project
A core component of your grade will be determined by the final project. A project can be either a research project or a literature survey:
Research project: You are expected to form teams of size 12 people and undertake independent research in the broader area of zeroknowledge proofs. I encourage using Ed to find project partners. I will post a list of potential project ideas to Ed.
The ideal goal of this type of project is to make preliminary progress towards a result that can eventually be published at a major cryptography (CRYPTO, EUROCRYPT, TCC) or security (IEEE S&P, USENIX Security, ACM CCS) conference.
Note: students are encouraged to use ongoing research projects, but in this case they must clearly delineate work that had been done prior to the start of the course and work that was done during the course.
Literature survey: This is an individual project: you can pick any topic in the area of zkSNARKs (whether covered in the class or not), and write a survey of the existing literature on this topic. Your survey should pick a few relevant papers, summarize them in some depth, and provide a comparison between the chosen papers.
Both kinds of projects consist of the following deliverables:
 Project proposal (due on 10/10/23): A 23page proposal describing the project, and containing the following details:
 Teammates (if any)
 Proposed research problem/survey topic
 Initial study of prior work, with references that you plan to use. This is due on October 10th.
 Initial plan of attack (for research projects), or outline of the survey (for literature surveys)
 Project presentation (due on either 12/05/23 or 12/07/23): The presentation should be highlevel, and accessible to the entire class. It should contain the following information.
 Research project:
 Problem introduction, and motivation (with a clear threat model).
 Brief description of why existing techniques are insufficient.
 Highlevel explanation of your contribution, and what you plan to do before the final report deadline.
 Literature survey:
 Problem introduction, and motivation (with a clear threat model).
 Highlevel overview of the important papers in the chosen problem space.
 Explanation of the core contribution of 1 important paper, and how it relates to the other papers in the space.
Regarding the duration of the presentation, a 1person group should prepare a 910 minute presentation, while a 2person group should prepare a 12minute presentation. Expect 34 minutes of questions per group.
 Research project:
 Project report (due on either 12/15/23): The final report should be a singlecolumn paper no longer than 810 pages (excluding references). It should contain the following information.
 Research project:
 Teammates, if any.
 Problem introduction, and motivation (with a clear threat model).
 Comprehensive related work
 Description of contributions (protocol design, security proof sketch, system design, application design, etc.)
 Brief description of implementation (if appropriate), and experiment design (and results, if any).
 Literature survey:
 Teammates, if any.
 Problem introduction, and motivation (with a clear threat model).
 Highlevel overview of the important papers in the chosen problem space
 Detailed summary and comparison of the chosen papers.
 Key takeaways, including open problems and future directions.
 Research project: