| layout | title | permalink | redirect_from | |
|---|---|---|---|---|
default |
Zero Knowledge Proofs |
/s23 |
|
- Zoom link:
(Password: 826181) [Add to your calendar] - Guest Speaker Webinars:
- OH (Monday 1-2PM): (Password: 826181)
- For general course content related questions, please join our edstem.
- Do not email the course staff or TAs. For private matters, post a private question on edstem and make sure it is visible to all teaching staff.
 |
 |
 |
|---|---|---|
| Dawn Song | Shafi Goldwasser | Arka Rai Choudhuri (Guest Instructor) |
| UC Berkeley | UC Berkeley | NTT Research |
- TAs: Deevashwer Rathee (Head TA)
- Readers: Elden Ren, Vikhyath Mondreti
- Synchronous lectures: 5:00 PM-6:59 PM PT Tue in Soda 306, starting Jan 17.
- Asynchronous lectures: links to pre-recorded videos will be posted on the course website.
This is a variable-unit course. The requirements for each number of units are listed below:
- 1 unit: attend lectures + article + weekly quizzes
- 2 units: attend lectures + do lab + HW + weekly quizzes
- 3 units: requirements for 2 units + class project with implementation and short report
- 4 units: requirements for 2 units + class project with broader scope, implementation and a longer workshop-style report
If you need a permission code to join the course, please fill out this form and we’ll get back to you as soon as possible.
<tr>
<td>01/24</td>
<td>Overview of Modern SNARK Constructions
| <a href = "https://youtu.be/bGEXYpt3sj0"> Lecture </a>
| <a href = "https://youtube.com/playlist?list=PLS01nW3Rtgoo_0Y-X5bQ32SyDbMiGFqee"> Playlist </a>
| <a href ="https://forms.gle/jyRJmNttcd2knFXz9"> Quiz </a>
| <a href="{{site.baseurl}}/assets/Lecture2-2023.pdf"> Slides </a>
| <a href="{{site.baseurl}}/assets/Disc2.pdf"> Notes </a>
<br>
<br>
<b> Readings </b>
<ul>
<li><a href= "https://www.cs.ubc.ca/~nickhar/W12/Lecture9Notes.pdf">Schwartz-Zippel Lemma - Section 1</a></li>
<li><a href= "https://www.di.ens.fr/~nitulesc/files/Survey-SNARKs.pdf">Anca Nitulescu - zk-SNARKs: A Gentle Introduction</a></li>
<li><a href= "https://medium.com/@boneh/using-zk-proofs-to-fight-disinformation-17e7d57fe52f">Using ZK Proofs to Fight Disinformation</a></li>
<li><a href= "https://a16zcrypto.com/zero-knowledge-canon">Zero Knowledge Canon</a></li>
</ul>
</td>
</tr>
<tr>
<td>01/31</td>
<td>Libraries and Compilers to build ZKP
| <a href="https://youtu.be/UpRSaG6iuks"> Lecture </a>
| <a href = "https://youtube.com/playlist?list=PLS01nW3RtgoqqvF39f11ncNAClgSLPlXD"> Playlist </a>
| <a href="https://forms.gle/9Q3PQzjFextViGE16"> Quiz </a>
| <a href = "{{site.baseurl}}/assets/lecture3-2023.pdf"> Slides </a>
<br>
<br>
<b>Resources</b>
<ul>
<li><a href="https://github.com/rdi-berkeley/zkp-course-lecture3-code">Code from Lecture</a></li>
<li><a href="https://docs.circom.io/">Circom Documentation</a></li>
<li><a href="https://github.com/arkworks-rs/r1cs-tutorial/">Arkworks Tutorial</a></li>
<li><a href="https://zokrates.github.io/">ZoKrates Documentation</a></li>
</ul>
</td>
</tr>
<tr>
<td colspan=2 align=center> <b>2. Efficient Constructions of ZKP</b> </td>
</tr>
<tr>
<td colspan=2 align=center> <font size="-0.5" style="font-weight: bolder">2.1. Polynomial IOPs</font> </td>
</tr>
<tr>
<td>02/07</td>
<td>Interactive Proofs (IP)
| <a href = "https://youtu.be/4018OYyoAf8"> Lecture </a>
| <a href = "https://youtube.com/playlist?list=PLS01nW3RtgopePvLcZgMJK8gC5trUWVsT"> Playlist </a>
| <a href = "https://forms.gle/NcqyqsqAodu8HAPE8"> Quiz </a>
| <a href = "{{site.baseurl}}/assets/lecture4.pdf"> Slides </a>
<br>
<br>
<b>Readings</b>
<ul>
<li><a href="https://theory.cs.princeton.edu/complexity/book.pdf">Interactive Proofs and the Sum-Check Protocol</a></li>
<li><a href="https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf">Chapters 3 and 4 of [Thaler]</a></li>
<li><a href="https://en.wikipedia.org/wiki/Merkle_tree">Merkle Trees</a></li>
<li><a href="https://eprint.iacr.org/2014/846.pdf">Sum-Check-Based Polynomial IOPs for Circuit-SAT</a></li>
</ul>
<b>Other Helpful Resources</b>
<ul>
<li><a href="https://eprint.iacr.org/2019/550" style="font-size:24px">Spartan</a></li>
<li><a href="https://eprint.iacr.org/2017/1132" style="font-size:24px">Hyrax</a></li>
<li><a href="https://faculty.cc.gatech.edu/~genkin/papers/vsql.pdf style="font-size:24px">vSQL</a></li>
<li><a href="https://eprint.iacr.org/2019/317.pdf" style="font-size:24px">Libra</a></li>
</ul>
</td>
</tr>
<tr>
<td>02/14</td>
<td>Plonk Interactive Oracle Proofs (IOP)
| <a href = "https://youtu.be/A0oZVEXav24"> Lecture </a>
| <a href = "https://youtube.com/playlist?list=PLS01nW3Rtgopdkrlu2-Lqgg7MKIS2vv2J"> Playlist </a>
| <a href = "https://forms.gle/MrWBrWNjtHWaNsDBA"> Quiz </a>
| <a href = "{{site.baseurl}}/assets/lecture5-2023.pdf"> Slides </a>
<br>
<br>
<b>Readings</b>
<ul>
<li><a href="https://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf">Constant-Size Commitments to Polynomials and Their Applications</a></li>
<li><a href="https://alinush.github.io/2021/06/17/Feist-Khovratovich-technique-for-computing-KZG-proofs-fast.html">Feist-Khovratovich technique for computing KZG proofs fast</a></li>
<li><a href="https://eprint.iacr.org/2020/1274">Dory: Efficient, Transparent arguments for Generalised Inner Products and Polynomial Commitments</a></li>
<li><a href="https://eprint.iacr.org/2019/953">PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge</a></li>
<li><a href="https://eprint.iacr.org/2022/1355">HyperPlonk: Plonk with Linear-Time Prover and High-Degree Custom Gates</a></li>
<li><a href="https://zcash.github.io/halo2/concepts/arithmetization.html">PLONKish Arithmetization</a></li>
</ul></td>
</tr>
<tr>
<td colspan=2 align=center> <font size="-0.5" style="font-weight: bolder">2.2. Polynomial Commitments</font> </td>
</tr>
<tr>
<td>02/21</td>
<td>Discrete-log-based Polynomial Commitments
| <a href = "https://youtu.be/WyT5KkKBJUw"> Lecture </a>
| <a href = "https://youtube.com/playlist?list=PLS01nW3RtgopRnH84Omx0C4yZo75uSHWO"> Playlist </a>
| <a href = "https://forms.gle/uiiPZQjEqEmbSW437"> Quiz </a>
| <a href = "{{site.baseurl}}/assets/lecture6.pdf"> Slides </a>
<br>
<br>
<b>Readings</b>
<ul>
<li><a href="https://eprint.iacr.org/2017/1146">A Zero-Knowledge Version of vSQL</a></li>
<li><a href="https://eprint.iacr.org/2017/1066.pdf">Bulletproofs: Short Proofs for Confidential Transactions and More</a></li>
</ul>
</td>
</tr>
<tr>
<td>02/28</td>
<td>ZKP based on Error-Correcting Codes
| <a href = "https://youtu.be/1S7ZjqG9uyI"> Lecture </a>
| <a href = "https://youtube.com/playlist?list=PLS01nW3RtgopEpcPnXiXsHPO8HsaGUgmd"> Playlist </a>
| <a href = "https://forms.gle/5qis42djSbxCH3rr5"> Quiz </a>
| <a href = "{{site.baseurl}}/assets/lecture7.pdf"> Slides </a>
<br>
<br>
<b>Readings</b>
<ul>
<li><a href="https://acmccs.github.io/papers/p2087-amesA.pdf">Ligero: Lightweight Sublinear Arguments Without a Trusted Setup</a></li>
<li><a href="https://eprint.iacr.org/2022/1010">Orion: Zero Knowledge Proof with Linear Prover Time</a></li>
<li><a href="https://eprint.iacr.org/2021/1043">Brakedown: Linear-time and post-quantum SNARKs for R1CS</a></li>
</ul>
</td>
</tr>
<tr>
<td>03/07</td>
<td>Transparent ZKP
| <a href = "https://youtu.be/A3edAQDPnDY"> Lecture </a>
| <a href = "https://youtube.com/playlist?list=PLS01nW3RtgorRZsBnqch6gGBStZB9VVrM"> Playlist </a>
| <a href = "https://forms.gle/fXpx8HhgmbweLJQu9"> Quiz </a>
| <a href = "{{site.baseurl}}/assets/lecture8.pdf"> Slides </a>
<br>
<br>
<b>Readings</b>
<ul>
<li><a href="https://eccc.weizmann.ac.il/report/2017/134/">FRI Paper</a></li>
<li><a href="https://eprint.iacr.org/2020/654.pdf">Best Existing Soundness Analysis of FRI</a></li>
<li><a href="https://eprint.iacr.org/2019/1020">Polynomial Commitments from FRI</a></li>
<li><a href="https://eprint.iacr.org/2018/1004.pdf">Round-by-round Soundness, Fiat-Shamir, and Sum-check</a></li>
</ul>
</td>
</tr>
<tr>
<td colspan=2 align=center> <font size="-0.5" style="font-weight: bolder">2.3. Linear PCP</font> </td>
</tr>
<tr>
<td>03/14</td>
<td>Linear Probabilistically Checkable Proofs (PCP)
| <a href = "https://youtu.be/I7TXIHXamwM"> Lecture </a>
| <a href = "https://youtube.com/playlist?list=PLS01nW3RtgorEgSixlZA2rJ-2q7_eAKe3"> Playlist </a>
| <a href = "https://forms.gle/bCpdFz1QbdU5jEwR9"> Quiz </a>
| <a href = "{{site.baseurl}}/assets/lecture9.pdf"> Slides </a>
<br>
<br>
<b>Readings</b>
<ul>
<li><a href="https://eprint.iacr.org/2013/279.pdf">Pinocchio</a></li>
<li><a href="https://eprint.iacr.org/2012/718">Succinct Non-Interactive Arguments via Linear Interactive Proofs</a></li>
<li><a href="https://eprint.iacr.org/2016/260.pdf">Groth16</a></li>
</ul>
</td>
</tr>
<tr>
<td colspan=2 align=center> <font size="-0.5" style="font-weight: bolder">2.4. Recursive SNARKs</font> </td>
</tr>
<tr>
<td>03/21</td>
<td>Recursive SNARKs, Aggregation and Accumulation
| <a href = "https://youtu.be/0LW-qeVe6QI"> Lecture </a>
| <a href = "https://youtube.com/playlist?list=PLS01nW3RtgopkbOmAfolTngGbnJ3SYmYu"> Playlist </a>
| <a href = "https://forms.gle/AX24FKdR52hp1Sos6"> Quiz </a>
| <a href = "{{site.baseurl}}/assets/lecture10.pdf"> Slides </a>
<br>
<br>
<b>Readings</b>
<ul>
<li><a href="https://medium.com/starkware/recursive-starks-78f8dd401025">Recursive STARK Proofs</a></li>
<li><a href="https://eprint.iacr.org/2019/1407">Incrementally Verifiable Computation via Incremental PCPs</a></li>
<li><a href="https://eprint.iacr.org/2014/595.pdf">Scalable Zero Knowledge via Cycles of Elliptic Curves</a></li>
<li><a href="https://eprint.iacr.org/2021/370.pdf">Nova</a></li>
<li><a href="https://eprint.iacr.org/2020/1618.pdf">Proof-Carrying Data without Succinct Arguments</a></li>
<li><a href="https://eprint.iacr.org/2022/1576.pdf">Folding Schemes with Selective Verification</a></li>
</ul>
</td>
</tr>
<tr>
<td colspan=2 align=center> <font size="-0.5" style="font-weight: bolder">Spring Break (03/27 - 03/31)</font> </td>
</tr>
<tr>
<td colspan=2 align=center> <b>3. Applications and Advanced Topics in ZKP</b> </td>
</tr>
<tr>
<td>04/04</td>
<td>Theoretical Foundations & Recent Theoretical Advancements
| <a href = "https://youtu.be/CIGnBb8B0rQ"> Lecture </a>
| <a href = "https://youtube.com/playlist?list=PLS01nW3RtgortBgR8sznyBbYvS2R63fe0"> Playlist </a>
| <a href = "https://forms.gle/1kVrKn7SupCX8Eqg9"> Quiz </a>
| <a href = "{{site.baseurl}}/assets/lecture11.pdf"> Slides </a>
</td>
</tr>
<tr>
<td>04/11</td>
<td>Overview of ZKP Applications & zkRollup and zkEVM
| <a href = "https://youtu.be/vuQGdbpDWcs"> Lecture </a>
| <a href = "https://youtube.com/playlist?list=PLS01nW3RtgoqV9S-crVXIkMoaE1JRJwML"> Playlist </a>
| <a href = "{{site.baseurl}}/assets/lecture12.pdf"> Slides </a>
<br>
Building opcode compatible zk EVMs
| <a href = "https://youtu.be/Crzw7ccuHd0"> Lecture </a>
| <a href = "{{site.baseurl}}/assets/lecture_opcode.pdf"> Slides </a>
</td>
</tr>
<tr>
<td>04/18</td>
<td>Privacy-preserving Architectures
| <a href = "https://youtu.be/1o3cl42bs40"> Lecture </a>
| <a href = "{{site.baseurl}}/assets/lecture_privacy.pdf"> Slides </a>
<br>
</td>
</tr>
<tr>
<td>04/25</td>
<td>ZKP Applications & zkBridge, Trustless Bridge made Practical
| <a href = "https://youtu.be/0bKasr4G7OM"> Lecture </a>
| <a href = "{{site.baseurl}}/assets/dawnsong-lecture.pdf"> Slides </a>
<br>
More ZKP Applications
| <a href = "https://youtu.be/tbEsv2afhko"> Lecture </a>
| <a href = "{{site.baseurl}}/assets/yupeng-lecture.pdf"> Slides </a>
</td>
</tr>
<tr>
<td>05/02</td>
<td>Formal Verification of ZKP
| <a href = "https://youtu.be/av7Wq742GIA"> Lecture </a>
| <a href = "https://youtube.com/playlist?list=PLS01nW3RtgorMPv-awIn16HAdmyfIqsNj"> Playlist </a>
| <a href = "{{site.baseurl}}/assets/lecture14.pdf"> Slides </a>
</td>
</tr>
<tr>
<td>05/09</td>
<td>Hardware Acceleration of ZKP
| <a href = "https://youtu.be/ez46At3xTjM"> Lecture </a> </td>
</tr>
| Date | Topic |
|---|---|
| 01/17 | Introduction and History of ZKP |
Lecture
| Playlist
| Quiz
| Slides
| Notes
Readings
|
1 unit
|
2 units
|
3 units
|
4 units
|
All quizzes are released in parallel with (or shortly after) the corresponding lecture and will be due midnight the following Tuesday. Please remember to complete the quiz each week. Although it's graded on completion , we encourage you to do your best. The questions are all multiple-choice.
Students will be completing an open-ended research project culminating in a presentation and a workshop-style paper submitted at the end of the semester. You will choose an area of research in ZKP that you wish to explore and are encouraged to read related papers in that area. You will then identify an area that you believe needs improvement or merits further research and build systems and/or conduct experiments to further the state of the art within your chosen field. Students are welcome to choose their own topics, but we’ll also provide a list of topic suggestions that you can take inspiration from if you wish. More details TBD.
More on this to be announced on Ed.
Students taking 1 unit should also write an article (at least 2 pages) about the relevant topic covered in this course or your experience of the course posted online, and optionally tweet about the article. The article should be finished by May 5th. For example a blog post on:
- Summarizing information from certain lectures
- Specific zk-proof protocols
- Applications of zk-proofs such as privacy or blockchain scaling.
The article’s marking criteria can be found below:
- Understanding (3 marks): displays breadth/depth of understanding of the topic.
- Importance (2 marks): content conveys an important aspect of zk-proofs.
- Clarity (3 marks): explains complex concepts simply, clearly, and accurately.
- References (2 marks): cites the relevant lecture and reference material such as research papers properly.
| Assignment | Released | Deadline |
|---|---|---|
| Group formation | 01/23 | 02/06 |
| Project proposal | 02/07 | |
| Lab | 02/28 | 03/13 |
| Project milestone | 03/21 | 03/26 |
| HW (Solutions) | 04/04 | 04/17 |
| Project presentation | - | 04/25 (In Class) |
| Project final report | 05/02 | 05/12 |
This class aims to bring together students and experts in academia and industry to explore Zero-Knowledge Proofs (ZKP). ZKP is a classical cryptographic primitive that ensures the validity of data and computations without sacrificing their confidentiality. It was proposed in the seminal paper by Goldwasser-Micali-Rackoff in 1985. Long considered wildly impractical, ZKPs have seen enormous efficiency improvements over the last decade. This has unlocked entirely new paradigms in the design of distributed and trustless systems, making ZKP one of the most important technologies to the future of blockchains. ZKPs are already being used to build privacy-preserving cryptocurrencies and to improve scalability via zkRollups and zkEVMs, and they stand poised to transform society’s mechanisms for establishing trust and privacy in the coming years and decades.
Our goal is to provide a platform for students to learn the cutting-edge technology of ZKP. Through the exposure to research in academia, and technology in industry, the students will be able to quickly gain the knowledge of ZKP and to develop ZKP systems for various applications.
This course covers fundamental techniques to build ZKP protocols, tools to implement ZKP for different computations, and different applications of ZKP in blockchain and other areas. Topics in the course include:
- An introduction on the history of ZKP. We will cover the theoretical foundations and early constructions of ZKP, as well as the recent theoretical advancements in this research area.
- We will cover the design of several current efficient ZKP systems. We will discuss the key ideas in the constructions of these ZKP schemes. ZKP schemes can be based on various different cryptographic techniques and the course will elaborate on their advantages and disadvantages in terms of efficiency, trust model and assumptions.
- To help students with developing ZKP systems and applications, we will provide tutorials on the front-end compilers to write ZKP statements. Students can write the computations using such higher-level programming languages, and compile them to low-level representations and run the ZKP protocols using these tools.
- Finally, we will cover applications of ZKP, including (1) privacy-preserving cryptocurrencies and computations such as Zcash and Zexe; (2) zkRollup and zkEVM that improve the scalability of blockchain; (3) zkBridge to build a secure foundation for multi-chain interoperability; (4) other applications in machine learning, program analysis, and network traffic analysis.