零知识证明系列公开课：ZKDL Camp 带你从代数基础到前沿协议
ZKDL Camp 是由 Distributed Lab（https://distributedlab.com/）举办的一系列零知识（Zero-Knowledge）主题讲座（未来可能发展为研讨会）。在这些课程中，我们将从零开始理解 zk-SNARK（如 Groth16 和 Pinocchio）以及 zk-STARK 的工作原理，包括它们所依赖的所有组成部分。
🔗 原文链接：https://ethresear.ch/t/is-data-available-in-the-el-mempool/22329?u=barnabe
关于 ZKDL Camp
ZKDL Camp 是由 Distributed Lab（https://distributedlab.com/）举办的一系列零知识（Zero-Knowledge）主题讲座（未来可能发展为研讨会）。在这些课程中，我们将从零开始理解 zk-SNARK（如 Groth16 和 Pinocchio）以及 zk-STARK 的工作原理，包括它们所依赖的所有组成部分。
请注意，本课程旨在帮助学习者全面深入地理解这些协议的底层原理，因此会涉及大量相关数学知识。这也是为什么课程不仅讲解零知识证明本身及其应用，还系统涵盖了理解零知识证明与密码学所需的基础数学内容。
课程教材
我们基于讲座内容整理编写了一本教材，可通过下方链接访问。请注意，这本书仍在持续更新中，我们非常欢迎你提供反馈意见。如果你希望参与内容完善，可以访问我们的 GitHub 仓库（https://github.com/ZKDL-Camp/lectures-tex）并在其中留言或提交 Pull Request。
第 1 讲：代数基础
讲师：Dmytro Zakharov
内容简介
本讲将介绍理解零知识证明系统所需的基础数学知识，主
要包括以下内容：
基础集合论与逻辑
基础群论
域及有限域运算
讲义材料：
讲义笔记：https://zkdl-camp.github.io/files/notes/1-math.pdf
幻灯片：https://zkdl-camp.github.io/files/slides/1-math.pdf
练习题：https://zkdl-camp.github.io/files/exercises/1-math.pdf
测验表单：https://docs.google.com/forms/d/e/1FAIpQLSd9X8KRiGBzrAZCnou6j2VIGqwrV-ovU1GObMdKfiNiDJhs2w/viewform
GitHub 仓库：https://github.com/ZKDL-Camp/lecture-1-math
其他推荐资源：
Michael Penn 的 “抽象代数” YouTube 课程：这是我见过对代数 I 讲解最清晰、例子最丰富的课程之一。
链接：
麻省理工学院现代代数课程（18.703）：课程内容严谨，但仍然易于理解。
链接：https://ocw.mit.edu/courses/18-703-modern-algebra-spring-2013/
Visual Group Theory：这是一个非常全面的群论与伽罗瓦理论课程列表，配有丰富的图示和示例。
第 2 讲：安全性、多项式与拉格朗日插值
讲师：Dmytro Zakharov 和 Denis Riabtsev
内容简介
本讲将继续讲解密码学中使用的基础数学知识，主要包括以下内容：
基础安全性定义
多项式
拉格朗日插值：Shamir 秘密共享与 Reed-Solomon 编码
Schwarz-Zippel 引理
数论基础
讲义材料：
讲义笔记：https://zkdl-camp.github.io/files/notes/2-math-and-crypto.pdf
幻灯片：https://zkdl-camp.github.io/files/slides/2-math-and-crypto.pdf
练习题：https://zkdl-camp.github.io/files/exercises/2-math-and-crypto.pdf
测验表单：https://docs.google.com/forms/d/e/1FAIpQLSc5A5q7SCz0XZ1vuEyufYZdl0ggADgaFk_AwyaQwjRZQHEVxg/viewform
其他推荐资源：
Dan Boneh 与 Victor Shoup 合著的《应用密码学研究生课程》（A Graduate Course in Applied Cryptography），第 2 章（加密）：本书有助于深入理解系统安全分析与密码学形式化方法，尤其推荐第 2 章对安全性定义的介绍。
链接：https://toc.cryptobook.us/
Reed, Irving S. 和 Solomon, Gustave（1960）《某些有限域上的多项式编码》：Reed-Solomon 纠错编码的原始论文。
链接：https://epubs.siam.org/doi/10.1137/0108018
第 3 讲：有限域扩展与椭圆曲线
讲师：Dmytro Zakharov
内容简介
本讲主要聚焦于有限域扩展，同时也介绍椭圆曲线的基本概念，涵盖以下内容：
有限域扩展
代数闭包
椭圆曲线的定义
椭圆曲线上的离散对数问题
讲义材料：
讲义笔记：https://zkdl-camp.github.io/files/notes/3-fields-and-ec.pdf
幻灯片：https://zkdl-camp.github.io/files/slides/3-ec.pdf
练习题：https://zkdl-camp.github.io/files/exercises/3-ec.pdf
测验表单：https://forms.gle/LiXaeXkzzHFyLvMX9
其他推荐资源：
Samuel Moy 的《域扩展理论导论》（An Introduction to the Theory of Field Extensions）：这是一本严谨而偏数学化的域扩展入门教材，强烈推荐，但对于初学者可能略显晦涩。
链接：https://www.math.uchicago.edu/~may/VIGRE/VIGRE2009/REUPapers/Moy.pdf
Alfred Menezes 等人所著的《椭圆曲线密码学指南》（Guide to Elliptic Curve Cryptography）：关于椭圆曲线优化的出色著作，同时也对有限域有很好的介绍。
链接：http://tomlr.free.fr/Math�matiques/Math Complete/Cryptography/Guide to Elliptic Curve Cryptography - D. Hankerson, A. Menezes, S. Vanstone.pdf
Craig Costello 的《Pairing for Beginners》：快速了解椭圆曲线配对技术的内部机制。
链接：https://static1.squarespace.com/static/5fdbb09f31d71c1227082339/t/5ff394720493bd28278889c6/1609798774687/PairingsForBeginners.pdf
Dan Boneh 与 Victor Shoup 的《应用密码学研究生课程》（A Graduate Course in Applied Cryptography）第 15 章（椭圆曲线密码学与配对）：很好地介绍了椭圆曲线及其配对的基本知识（不涉及构造细节）。
链接：https://toc.cryptobook.us/
第 4 讲：射影坐标与配对运算
讲师：Dmytro Zakharov
内容简介
本讲将介绍 SNARKs 的核心部分——椭圆曲线配对（Pairing），其性质及应用。在此之前，我们将首先学习射影坐标及其在优化椭圆曲线运算中的作用。整体内容包括：
关系与等价类
射影坐标（Projective Coordinates）
如何在射影坐标中进行点加法，以及如何使用“倍加算法（double-and-add）”进行标量乘法
椭圆曲线配对
配对的实际应用
讲义材料：
讲义笔记：https://zkdl-camp.github.io/files/notes/4-pairing.pdf
幻灯片：https://zkdl-camp.github.io/files/slides/4-pairing.pdf
练习题：https://zkdl-camp.github.io/files/exercises/4-pairing.pdf
测验表单：https://docs.google.com/forms/d/e/1FAIpQLSfpu1kdYkVGzpVRHAbGAx1Rru87rvnUFPZx_WOjMIxMMgGmfQ/viewform?usp=send_form
GitHub 仓库：https://github.com/ZKDL-Camp/lecture-4-pairings
其他推荐资源：
Craig Costello 的《Pairing for Beginners》：这本之前提到的书不仅详细讲解了配对的内部机制，也提供了对椭圆曲线射影形式的深入介绍。
链接：https://static1.squarespace.com/static/5fdbb09f31d71c1227082339/t/5ff394720493bd28278889c6/1609798774687/PairingsForBeginners.pdf
Dan Boneh 与 Victor Shoup 的《应用密码学研究生课程》（A Graduate Course in Applied Cryptography），第 15 章：推荐阅读至第 15.5 小节，内容涵盖椭圆曲线与配对的基础。
链接：https://toc.cryptobook.us/
Jonathan Wang 的《BN254 For The Rest of Us》：如果你想了解具体的“适用于配对”的曲线参数，这篇文章值得一读。BN254 是当前广泛使用的一种曲线。
链接：https://hackmd.io/@jpw/bn254
Jean-Luc Beuchat 等人撰写的《High-Speed Software Implementation of the Optimal Ate Pairing over Barreto-Naehrig Curves》：如果你希望深入了解配对的具体实现细节，这篇论文是最佳参考，文中提供了从零实现配对所需的全部算法。
翻译：https://eprint.iacr.org/2010/354.pdf
第 5 讲：密码学承诺方案
讲师：Denis Riabtsev
内容简介
本讲将深入讲解多种密码学承诺方案的设计与应用，这些方案在零知识证明系统中被广泛使用。主要内容包括：
基于哈希的承诺（Hash-based commitments）
向量承诺（Vector commitments）
多项式承诺（Polynomial commitments）
讲义材料：
讲义笔记：https://zkdl-camp.github.io/files/notes/5-commitments.pdf
幻灯片：https://zkdl-camp.github.io/files/slides/5-commitments.pdf
练习题：https://zkdl-camp.github.io/files/exercises/5-commitments.pdf
测验表单：https://docs.google.com/forms/d/e/1FAIpQLSfBYGvraga2D2jGWy5vuJ46Uy6a4sYb_A33FSmFhnq2E_Cr5g/viewform
其他推荐资源：
Scroll 团队的《KZG 承诺方案》：解释了 KZG 承诺方案背后的数学原理。
链接：https://docs.scroll.io/en/learn/zero-knowledge/kzg-commitment-scheme/
Ying Tong 的《现代零知识密码学》第五讲：形式化讲解了向量承诺与多项式承诺。
链接：https://assets.super.so/9c1ce0ba-bad4-4680-8c65-3a46532bf44a/files/61fb28e6-f2dc-420f-89e1-cc8000233a4f.pdf
RareSkills 的文章《什么是 Pedersen 承诺及其工作原理》：用通俗易懂的语言解释了 Pedersen 承诺，并提供了 Python 示例代码。
链接：https://www.rareskills.io/post/pedersen-commitment
第 6 讲：零知识证明导论
讲师：Dmytro Zakharov
内容简介
本讲将正式介绍零知识证明（Zero-Knowledge Proofs）的基本概念及其应用。主要内容包括：
什么是密码学意义上的“证明”？
交互式证明（Interactive Proofs）
可靠性（Soundness）与零知识性（Zero-Knowledge）的定义
证明 vs 知识的证明（Proof vs Proof of Knowledge）
Fiat-Shamir 启发式方法
讲义材料：
讲义笔记：https://zkdl-camp.github.io/files/notes/6-intro-zk.pdf
幻灯片：https://zkdl-camp.github.io/files/slides/6-intro-zk.pdf
练习题：https://zkdl-camp.github.io/files/exercises/6-intro-zk.pdf
测验表单：https://docs.google.com/forms/d/e/1FAIpQLSfRKxhsY2x1IclR0xbLLLuXBO5lm8oU91RmNXE0dcn5StIP0g/viewform
其他推荐资源：
《Zero Knowledge Proofs MOOC, Spring 2023》：极其精彩的零知识证明系列课程，本讲主要参考了 Shafi Goldwasser 的第一讲。
链接：https://rdi.berkeley.edu/zk-learning/
Boaz Barak 的《Zero Knowledge Proofs Lecture》：对零知识证明基本原理讲解非常清晰，包含对“二次剩余交互协议”的详细分析。
链接：https://www.cs.princeton.edu/courses/archive/fall07/cos433/lec15.pdf
第 7 讲：Sigma 协议
讲师：Dmytro Zakharov
内容简介
本讲将介绍最基础的一类交互式证明形式 —— Sigma 协议。我们将学习如何将其转化为非交互式证明，并了解其在实际中的应用。主要内容包括：
Schnorr 签名方案
Sigma 协议的基本结构
Sigma 协议示例：Okamoto 协议 和 Chaum-Pedersen 协议
Sigma 协议的组合方式
讲义材料：
讲义笔记：https://zkdl-camp.github.io/files/notes/7-sigma.pdf
幻灯片：https://zkdl-camp.github.io/files/slides/7-sigma.pdf
练习题：https://zkdl-camp.github.io/files/exercises/7-sigma.pdf
测验表单：https://docs.google.com/forms/d/e/1FAIpQLScxeVsgLqUIJcUVErN2q1nh4q_FiG6uBawAQ2XBbFACV1P_nQ/viewform
GitHub 仓库：https://github.com/ZKDL-Camp/lecture-7-sigma
其他推荐资源：
Dan Boneh 与 Victor Shoup 合著的《应用密码学研究生课程》第 19 章：对 Sigma 协议进行了非常形式化和严谨的介绍，第 20 章还进一步讲解了如何将交互式证明转化为非交互式证明。
链接：https://toc.cryptobook.us/
Justin Thaler 的《Proofs, Arguments, and Zero-Knowledge》第 12 章：对基于离散对数的零知识协议进行了相当严谨的描述。
链接：https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf
第 8 讲：SNARKs 与算术电路
讲师：Anton Levochko
内容简介
本讲是关于 SNARKs 的入门课程——这项技术在我们的项目中日常使用。主要内容包括：
zk-SNARK 的定义
算术电路（Arithmetic Circuits）
电路满足性问题（Circuit Satisfiability Problem）
向量和矩阵形式的 Rank-1 约束系统（R1CS）
讲义材料：
讲义笔记：https://zkdl-camp.github.io/files/notes/8-circuits.pdf
幻灯片：https://zkdl-camp.github.io/files/slides/8-circuits.pdf
任务：https://zkdl-camp.github.io/files/exercises/8-circuits.pdf
GitHub 仓库：https://github.com/ZKDL-Camp/lecture-8-r1cs-qap
其他推荐资源：
Maksym Petkus 的《Why and How zk-SNARK Works》：非常易懂的入门教程，带你从零开始理解 zk-SNARK 的工作原理，是初学者的友好指南。
链接：https://arxiv.org/abs/1906.07221
RareSkills 的《Converting Algebraic Circuits to R1CS》：详细讲解了 R1CS 的工作机制，并配有大量实用示例。
链接：https://www.rareskills.io/post/rank-1-constraint-system
第 9 讲：二次算术程序（QAP）与概率可验证证明（PCP）
讲师：Anton Levochko
内容简介
在掌握了 R1CS 后，我们将学习如何将其简洁地表示为二次算术程序（QAP）。此外，我们还会介绍一些基本理论，为后续讲解 Groth16 协议做准备。主要内容包括：
将 R1CS 转换为 QAP
什么是 PCP、IPCP 和 IOP
指数证明（Proof of Exponent）
讲义材料：
讲义笔记：https://zkdl-camp.github.io/files/notes/9-qap-pcp.pdf
幻灯片：https://zkdl-camp.github.io/files/slides/9-qap-pcp.pdf
其他推荐资源：
Maksym Petkus 的《Why and How zk-SNARK Works》：非常易懂的入门教程，带你从零开始理解 zk-SNARK 的工作原理，是初学者的友好指南。
链接：https://arxiv.org/abs/1906.07221
Vitalik Buterin 的《Quadratic Arithmetic Programs: From Zero to Hero》：基于实数演示了 R1CS 和 QAP 的关系。
链接：https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649
第 10 讲：基于配对的 zk-SNARKs
讲师：Anton Levochko 与 Dmytro Zakharov
内容简介
最后，我们将介绍最先进的 zk-SNARKs 之一：Pinocchio 和 Groth16。主要内容包括：
将 QAP 转换为加密空间上的简洁验证
使 SNARK 具有可靠性（Soundness）
将 SNARK 转换为零知识 SNARK（zk-SNARK）
Pinocchio 协议
Groth16 协议
讲义材料：
讲义笔记：https://zkdl-camp.github.io/files/notes/10-groth16.pdf
幻灯片：https://zkdl-camp.github.io/files/slides/10-groth16.pdf
其他推荐资源：
Maksym Petkus 的《Why and How zk-SNARK Works》：非常易懂的入门教程，带你从零开始理解 zk-SNARK 的工作原理，是初学者的友好指南。
链接：https://arxiv.org/abs/1906.07221
2023 年春季 ZK MOOC《线性 PCP》课程：精彩讲解了 Pinocchio 和 Groth16 协议的构建思想，形式化且数学严谨。
链接：https://rdi.berkeley.edu/zk-learning/
Bryan Parno 与 Craig Gentry 的《Pinocchio: Nearly Practical Verifiable Computation》：Pinocchio 协议的原创论文，如果熟悉讲义中的符号，理解起来相对容易。
链接：https://eprint.iacr.org/2013/279.pdf
Jens Groth 的《On the Size of Pairing-based Non-interactive Arguments》：Groth16 协议的原创论文，更为形式化地阐述了该协议及线性非交互式证明的用途。
链接：https://eprint.iacr.org/2016/260.pdf
第 11 讲：使用 Circom 编写零知识证明程序
讲师：Kyrylo Riabov
内容简介
在学习完 Groth16 zk-SNARK 理论后，我们将进入课程的实操部分。本讲将学习如何使用 Circom 创建电路并生成证明。主要内容包括：
Circom 的基础语法
创建电路
生成证明
解析生成的所有数据文件（如 .r1cs、.sym、proof.json）及其与之前理论的关联
讲义材料：
讲义笔记：https://zkdl-camp.github.io/files/notes/11-circom.pdf
幻灯片：https://zkdl-camp.github.io/files/slides/11-circom.pdf
GitHub 仓库：https://github.com/ZKDL-Camp/circom-walkthrough
其他推荐资源：
Marta Belles-Munoz 等人的《Circom：构建零知识应用的电路描述语言》：Circom 语言的原创论文。
链接：https://ieeexplore.ieee.org/document/10002421
zkintro 的《Programming ZKPs: From Zero to Hero》：详尽易懂的 Circom 使用教程。
链接：https://zkintro.com/articles/programming-zkps-from-zero-to-hero
erhant 的《Circom101》：介绍了多个实用示例（算术运算、比较器、哈希、默克尔树等），展示 Circom 的应用场景。
链接：https://circom.erhant.me/index.html
RareSkills 团队的《Circom 语言教程及 circomlib 讲解》：非常详细的 Circom 使用教程，包含实操示例。
链接：https://www.rareskills.io/post/circom-tutorial
第 12 讲：PlonK 算术化
讲师：Nikita Masych
内容简介
Groth16 并不是实际应用中唯一的 zk-SNARK 协议！本讲将介绍 PlonK 协议，该协议在多种 zkEVM 实现中被广泛采用。主要内容包括：
PlonK 算术化
PlonK 中门（Gates）的工作原理及自定义门（Custom Gates）
门与连线的满足性检查（Satisfiability Checks）
多项式上的置换检查（Permutation Check）
讲义材料：
讲义笔记：https://zkdl-camp.github.io/files/notes/12-plonk-arithm.pdf
幻灯片：https://zkdl-camp.github.io/files/slides/12-plonk-arithm.pdf
其他推荐资源：
Ariel Gabizon 等人的《PlonK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge》：PlonK 原创论文，阅读难度较大，但非常值得深入研究。
链接：https://eprint.iacr.org/2019/953.pdf
LambdaClass 的《All you wanted to know about Plonk》：可能是最全面且讲解最清晰的 PlonK 结构文章。
链接：https://blog.lambdaclass.com/all-you-wanted-to-know-about-plonk/
Vitalik Buterin 的《Understanding PLONK》：另一篇对 PlonK 进行了详尽说明和图示的优秀指南。
链接：https://vitalik.eth.limo/general/2019/09/22/plonk.html
第 13 讲：数论变换（NTT/FFT）
讲师：Anton Levochko
内容简介
本讲是关于 SNARKs 的入门课程——这项技术在我们的项目中日常使用。主要内容包括：
zk-SNARK 的定义
算术电路（Arithmetic Circuits）
电路满足性问题（Circuit Satisfiability Problem）
向量和矩阵形式的 Rank-1 约束系统（R1CS）
讲义材料：
讲义笔记：https://zkdl-camp.github.io/files/notes/8-circuits.pdf
幻灯片：https://zkdl-camp.github.io/files/slides/8-circuits.pdf
任务：https://zkdl-camp.github.io/files/exercises/8-circuits.pdf
GitHub 仓库：https://github.com/ZKDL-Camp/lecture-8-r1cs-qap
其他推荐资源：
Maksym Petkus 的《Why and How zk-SNARK Works》：非常易懂的入门教程，带你从零开始理解 zk-SNARK 的工作原理，是初学者的友好指南。
链接：https://arxiv.org/abs/1906.07221
RareSkills 的《Converting Algebraic Circuits to R1CS》：详细讲解了 R1CS 的工作机制，并配有大量实用示例。
链接：https://www.rareskills.io/post/rank-1-constraint-system
第 14 讲：zk-STARK 简明入门
讲师：Oleg Fomenko
内容简介
本讲介绍 zk-STARK 协议的基本描述。顾名思义，课程通过平方斐波那契数列的示例，概述了 zk-STARK 的主要构建模块。
感谢该资源提供预览图片：https://aszepieniec.github.io/stark-anatomy/fri.html
讲义材料：
讲义笔记：https://zkdl-camp.github.io/files/notes/14-stark.pdf
幻灯片：https://zkdl-camp.github.io/files/slides/14-stark.pdf
其他推荐资源：
StarkWare 团队的《ethSTARK Documentation》：StarkWare 使用的 STARK 协议定义。
链接：https://eprint.iacr.org/2021/582.pdf
Vitalik Buterin 的《STARKs, Part I: Proofs with Polynomial》
链接：https://vitalik.eth.limo/general/2017/11/09/starks_part_1.html
Vitalik Buterin 的《STARKs, Part II: Thank Goodness It's FRI-day》
链接：https://vitalik.eth.limo/general/2017/11/22/starks_part_2.html
Vitalik Buterin 的《STARKs, Part 3: Into the Weeds》
链接：https://vitalik.eth.limo/general/2018/07/21/starks_part_3.html
StarkWare 的《STARK-101》课程：包含编码示例的系列讲座，介绍 STARK 的实际构建方法。
链接：https://starkware.co/stark-101/
欢迎关注 ETHPanda 获取更多资讯！
