前言
隐衷研究院【PrivacyIN】第一期 ZK 训练营课程精讲内容上线啦，本期课堂邀请到美国德州农工大学（Texas A&M University）计算机科学与工程学院的助理传授张宇鹏，次要介绍经典零常识证实协定设计原理，课堂主题为《Basic Principles of the Classic ZK Protocols (Groth16 Plonk Stark)》。
此次授课采取小班授课，邀请了数十名来自国内外密码学及相干畛域的专家学者作为学员，加入了高强度的 90 分钟的密码学培训课堂。
课程精讲全文
零常识证实（Zero-Knowledge-Proofs）自 1985 年由 Goldwasser、Micali 和 Rackof 首次提出至今，随着零常识证实实践和技术的提高，涌现出很多经典零常识证实零碎，比方：Groth16，Pinocchio，Plonk，Marlin，Stark，Halo2 等，这些零常识证实零碎推动着零常识证实从实践逐渐进入实用利用，同时了解这些协定的工作机制和结构原理，对于设计 ZKP 利用零碎有着十分重要意义。
本期课堂张宇鹏老师别离对这三种典型协定（non-universal）SNARK、PLONK 和 STARK 进行设计原理剖析，次要内容有：多项式承诺、密码学数论简介、PlONK 协定、SNARK 类协定、STARK 协定等。
课堂开始，张宇鹏老师首先对上一堂课的零常识证实零碎进行简略回顾，帮忙同学们加深对 ZKP 概念和计算模型的了解。
多项式承诺
多项式承诺（polynomial commitment）是结构零常识证实零碎罕用密码学工具，其结构模型中 prover/verifer 为次要参与者，应用交互证实形式结构（能够应用 Fiat–Shamir-heuristic 转换为非交互方式）。理论能够认为多项式承诺是一个种非凡的零常识证实，其同样满足零常识证实的 Correctness、Soundness、Zero-knowledge 这些个性。
多项式承诺的基本原理是：
- prover 领有一个多项式，其构建一个对于这个多项式的承诺 commitmentδf，而后将承诺 δf 发送给 verifier
- verifier 收到的承诺 commitmentδf，任意取一点 a，发送该点给 prover，以申请计算该点上的后果
- prover 接管计算申请，应用多项式在 a 点计算失去 f(a)，并生成一个证实 proof，而后将 f(a)和证实 proof 都发给 verifer 进行验证
很多经典的零常识证实协定都基于多项式承诺进行结构，比方 Plonk、Dark、Stark、Supersonic 等。
KZG 多项式承诺是十分经典高效的一种多项式承诺结构实现，尤其在 Plonk 协定中是十分根底的组件。KGZ 多项式承诺基于 Bilinear-Pairing 和生成群（注：后续内容将具体介绍），其中生成群个别为基于椭圆曲线在一个无限域中生成（如选取椭圆曲线后确定 g），KGZ 承诺次要步骤：
- trust setup 生成参数
个别为选取公共参数素数 p 和 g（关联一条椭圆曲线），应用 MPC 典礼生成：
$$
\left\{
\begin{matrix}
g,g^{s},g^{s^{2}},g^{s^{3}},\cdots，g^{s^{d}}
\end{matrix}
\right\}
$$
其中 s 为随机数且生成过程中将会被抛弃（s 放弃为机密）
- 创立承诺和证实
生成群具备加法同态和 scale 乘法性质，承诺示意为：
$$
g^{f(s)}=g^{\sum{c_{i}s^{i}}}=\Pi\left(g^{s^{i}}\right)^{c_{i}}
$$
- 承诺 +proof 验证
应用 Bilinear-Pairing 验证：
$$e(g^f(s)/g^f(a),g)=e(g^{s-a},g^{q(s)}$$
是否成立，也即验证了 f(s)-f(a)=(s-a)q(s)成立。
密码学数论根底
零常识证实有着十分重的数论实践要求，为了克服重度的数学问题，帮忙大家了解经典协定结构背地的数学原理，课程中张宇鹏老师率领大家从最根本的素数定义和模运算开启数论的学习。
素数 p，是一个数 p 大于或等于 2 且只能被本身 p 和 1 整除的整数；
模态算术，是指任何数或者其算术运算值（包含两头运算）都须要模上指定的正整数（如 p)，这能保障模态运算后的数都落在 (0,p) 之间，比方模 13 运算：
-1mod13=-1 +1×13=12；
-1+2mod13，即：(-1mod13)+(2mod13)=(12+2)mod13=1。
群 Group 是定义在数汇合上，对某个运算符满足：
- 封闭性 closure（群中的元素，执行该操作符运算后仍然在定义的群中）
- 结合律 associativity（群中的元素对于该定义操作符运算满足交换律，如：(a+b)+c=a+(b+c)）
- 零元 identity element（群中存在一个元素 e，任何群中的元素与 e 执行该定义操作都为元素自身）
- 逆元 inverse element（群中的任何元素 a，都存在一个群中的元素 b，满足 a +b=e）
例如，对加法 + 的整数群，对加法取模整数群。
域 Field 是一个群 Group，对于操作 (+,x) 满足：
- 域 Field 是一个加法群
- 域 Field 是一个剔除加法零元，在「x」操作上的一个群
有理数、实数、复数、整数模素数 p（无限域）都是域，无限域是密码学很罕用的。
无限域有一个个性，其总是能够找到了一个生成元（Generator），生成元对本人循环乘法操作可能失去无限域所有元素，也即失去一个循环群，因而能够用生成元生成的指数模式元素作为无限域的示意，另外目前具备疾速的算法可能找到无限域的生成元。
双线性对 Bilinear-Pairing 一个十分高效的密码学工具，其将一个 base 乘法循环群中的两个元素对，映射到一个指标 target 群，即：
$$
e(p^a,Q^b)=e(P,Q)^ab:G \times G \rightarrow G_T
$$
Bilinear-Pairing 能够用来验证乘法循环群元素间的乘法关系（是否相等），然而不能用来计算，其实现较为简单，课程中次要介绍了 Bilinear-Pairing 的运算个性，并提供应用范例，如：
$$e(g^a,G^b)=e{(g,g)}^ab=e(g^ab,g)$$
PLONK 协定
为了更好地解说 Plonk 结构原理，张宇鹏老师给出一个通用的 ZKP 结构模型，其中 prover 领有机密数据 secret data，计算问题转换为通用的电路 C 计算问题，prover 向 verifier 证实本人应用 secret data 作为输出并执行电路失去输入，verifier 验证 prover 的证实 proof 是否正确。
Plonk 协定是一种 universal-trusted-setup 的零常识证实协定，它应用 SRC(Structure-Reference-String）形如：
$$
\left\{
\begin{matrix}
g,g^{s},g^{s^{2}},g^{s^{3}},\cdots，g^{s^{d}}
\end{matrix}
\right\}
$$
的结构化参数，这些参数具备通用、可更新的个性。Plonk 次要通过设计独特的电路示意，基于 KZG 承诺和置换 permutation 来实现。Plonk 电路门应用 Plonkish 格局（区别于 R1CS）对立来示意电路门的束缚，即：
$$q_{L_i}a_i+q_{R_i}b_i+q_{M_i}a_i \times b_i+q_{O_i}c_i+q_{c_i}=0$$
这样加、乘、公开输出、输入都能够用这个式子表白。
例如加法门能够示意为：
$$q_{L_1}=1,q_{R_1}=1，q_{M_1}=0，q_{O_1}=-1，q_{c_1}=0$$
例如乘法门能够示意为：
$$q_{L_2}=0,q_{R_2}=0，q_{M_2}=1，q_{O_2}=-1，q_{c_1}=0$$
Plonk 协定构建次要分为两大部分：电路门束缚解决和复制（线）束缚解决。
电路门束缚解决次要步骤：
prover、verifier 预处理，应用多项式插值求解失去系数多项式 qL(x)、qR(x)、qM(x)、qO(x)、qC(x)；prover 失去电路门线输出多项式 a(x)、b(x)、c(x)，其求解的插值为元根：
$$x=w^i,i=0,\ldots,n-1$$
prover 这些多项式压缩成一个多项式，并接着能够失去一个指标多项式 t(x)：
（注：t(x)原论文实现是由电路门束缚和复制束缚构建两局部的多项式复合而成的）
prover 应用 KZG 承诺创立 a(x)、b(x)、c(x)、t(x)作为证实，提供给 verifier 进行承诺关上验证正确性。
Plonk 的复制束缚次要思路是，通过将相等的电路线进行置换（重排），置换后的元素和元素是相等同的，引入置换多项式，而后进一步转换为等价束缚多项式：
并最终转换为基于拉格朗日多项式的非凡多项式 Z(X)，而后应用这个多项式和门束缚多项式形成一个压缩的新多项式进行证实和验证。
复制（线）束缚的解决次要步骤：
-
prover 和 verifier 预处理，多项式插值求解置换 permutation 多项式：
$$S_{ID}(x),S_\delta(x)$$
（注：Plonk 原论文应用相似多个 permutation 函数，原理类似）
- prover 对 Z(x)等多项式进行 KZG 承诺，输入证实。
- verifier 进行 KZG 承诺关上和多项式关系正确性验证。
Plonk 协定整体执行：
Plonk 协定整体执行理论就是对门束缚和复制束缚的解决，而后构建一个大的门束缚和复制束缚关联的大多项式束缚，次要基于 KZG 多项式承诺和拉格朗日插值来构建残缺协定，最初应用 Bilinear-Pairing 进行验证。
SNARK 协定
传统的 SNARK 协定，次要是指应用非通用 trusted-setup 生成零常识证实所须要得公共参数和公共 key（证实 key 和验证 key)，个别基于 Billinear-Pairing 构建的简洁非交互零常识证实协定，这里比拟经典的结构有 Pinocchio 和 Groth16 协定，它们次要是应用 R1CS 构建电路束缚，而后转换为 QAP 构建多项式证实，并应用 Billinear-Pairing 对多项式进行验证。
传统的 SNARK 计算问题个别工作流程如下：
- 将一个计算问题转换为电路问题（示意为电路）
- 将电路示意为 R1CS 束缚（乘法门束缚）
- 将 R1CS 束缚通过多项式插值求解失去 QAP，将 QAP 多项式和指标多项式 t(x)转换到加密模式的群 G，作为证实局部
-
应用 Billinear-Pairing 对 QAP 多项式和指标多项式 t(x)进行验证：
$$
\text {Verification:} e\left(\pi_{1}, \pi_{2}\right) / e\left(\pi_{3}, g\right)=e\left(g^{t(s)}, \pi_{4}\right)
$$
STARK 协定
STARK 是一种无需 trusted-setup 的简洁非交互零常识证实协定，STARK 前端次要采纳 RAM(Random-Access-Memory)Program 的形式进行协构建，一个典型的 RAM-program 由 CPU（包含很多寄存器等）, 内存 Memory，程序执行指令 program 等组成。
STARK 将证实问题转换为证实 RAM Program 是否正确地执行，这跟传统 zkSNARK 协定验证电路执行有很大地差别。STARK 应用 RAM Program 进行前端程序结构使得设计程序能够以很少指令代码来运行大批量次数和循环的指令步骤执行，而不会限度于电路大小；Random Access 操作在常数复杂度等长处。
STARK 应用 RAM-to-cuirt-Reduction 的技术进行证实，其将整个计算过程中所有跟 RAM 的交互、CPU State 的变动等记录下来，而后连贯或聚合起来，并转换成相似电路模式束缚去证实和验证 RAW Program 是否执行正确。
STARK 的算数运算是通过一系列的多项式来示意的，如程序执行步骤 1 的状态为 P1(X,⋯,Y)，执行步骤 2 的状态为 P2(X,⋯,Y)，每个步骤能够结构一个多项式。
STARK 的后端实现能够将执行步骤多项式转换为相似 SNARK 或 Plonk 形式的多项式束缚，而后在某个 degree 上进行 Random linear combination 构建一个大的验证多项式，用来证实和验证程序执行正确性。
实际上 STARK 应用基于默克尔树的 FRI protocol (low degree test)来实现后端构建，另外 STARK 中还须要进行额定的 Permutation 测试和公共束缚，FRI 局部的实践较为简单，课堂中没有深入探讨。
自在探讨环节，张宇鹏急躁地为学员解答了一系列对于协定设计原理的相干问题。
关 PrivacyIN
PrivacyIN 隐衷学院 (Privacy Institution) 由 LatticeX 基金会发动，致力于建设凋谢的明码和隐衷技术布道和钻研社区。联结寰球顶尖的学者、隐衷技术开发者推动 ZK(零常识证实)、MPC(平安多方计算)、FHE(全同态明码)的翻新和落地。
对于 LatticeX 基金会
LatticeX 基金会（LatticeX Foundation）是一家寰球范畴的开源技术社区，以通过构建简单计算偿还用户数据主权，爱护数据隐衷，实现数据价值替换为愿景，旨在构建一个齐全去中心化的计算互操作网络，在爱护数据主权和隐衷的前提下促成数据使用权的交易，并为实现 LatticeX 愿景赞助各类学术研究及科研项目。