Groth16 still lives:exploring the tradeoffs of modern ZKProof systems
presenter：François Garillot (Mysten Labs)
Stream Link：Groth16 still lives:exploring the tradeoffs of modern ZKProof systems
演讲者是一位Sui系统的密码学工程师，目前Sui系统中有不少的Zero-Knowledge原语，包括密码学库fastcrypto，此外还有一些常用密码学原语的实现，包括Bulletproof、Pedersen承诺和基于BLS12-381的Groth16
这次演讲的内容不仅是为了回答一些问题，更多的是提出一些问题，同时探讨一下ZKP最近的一些现状
首先回顾一下NIAoK，NIAoK中有一个公共算术电路$C$，以及对应的statement和witness$(x,w)$，NIAoK首先通过预处理算法来生成证明所需要的公共参数$pp$，之后Prover和Verifier分别利用$pp$来生成与验证证明
在18-19年，ZKP经历了一次比较大的变革，公共参数的生成从Split setup变成了Universal setup，演讲者将这一时期称为SNARKtember（改自九月的英文单词September，因为2019年9月出现了许多Universal Setup的SNARK论文，包括但不限于Marlin、Plonk、Halo、DARK等等知名算法）
在引入探讨的话提前，先介绍一个概念，应该是一种新的信息论证明系统，称为函数族IOP，由Dan Boneh教授提出
F-IOP的证明方式大致如下
- 首先选择一个函数族$F$，可以是多项式、多变量多项式、向量、IPA等等，并将其与函数承诺方案相结合
- 在后续的IOP中，Prover将函数族$F$中的函数作为预言发送给Verifier
- Verifier通过请求这些预言来验证这些函数确实是来自于函数族$F$
F-IOP的概念让学者们以一种更加新颖的方式来思考SNARK，并且为学者们提供了新的分类方式与分析角度
以基于配对的承诺方案为例，通过结合KZG承诺和Plonk的F-IOP，可以得到诸如Barretenberg（AztecProtocol:barretenberg，C++实现）、Jellyfish（EspressoSystems:jellyfish）等具体的ZKP库，Halo则是结合了Bulletproof和Sonic的F-IOP（Halo2的F-IOP用的是Plonk）
在设计、讨论、分析方案时，值得注意的是方案的复杂性分析，以及权衡密码学假设与采用的承诺方案之间的关系
从承诺方案的角度出发，可以得到具有不同性质的系统
- 利用基于配对的承诺（比如KZG），可以得到全局可信设置，同时证明大小不会太大
- 利用基于DLOG假设的承诺（比如Bulletproof），可以得到满足透明性的系统，同时证明大小也不会太大，只不过会降低Verifier的验证效率
- 利用基于Hash的承诺可以得到透明性的系统，不损失证明与验证效率，但是证明大小会非常非常大
这些不同的承诺和其得到的具有不同性质的SNAKR，这样一来更容易在系统的开发前期选择合适的方案来实现ZKP（比如区块链上要求快速验证，因此首先基于DLOG假设的承诺就不太适用）
回到前面的话题，Plonk及其算术电路的应用非常广泛，许多实验室和公司的项目都在用Plonk或其变体构建方案，包括但不限于下列这么多，当然也有个别方案，诸如Aleo、Filecoin、Celo，其采用Groth16或其变体
这里可以将Plonk方案和Groth16做一个对比，以TurboPlonk为例，TurboPlonk是一个具有自定义门的Plonk（目的是为了实现自定义规模的乘法运算），其和基于SN-254曲线的Groth16相比具有更快的Prover Time（效率大约是Groth16的两倍）
后来在2020年，Aztec又提出了UltraPlonk（又名PLONKup），其是一个具有lookup argument的Plonk（查找论证？，没理解，也没接触过这个概念，待补充）
自lookup argument概念的提出，部分学者开始致力于对其效率的优化，比如上述的这个表格（$m$表示查询的此时，$N$表示表的大小）
除了lookup argument，前面提到了有的系统会使用到Hashing，在SNARKtember那段时间，Starkware发起了一个Satrkware hash challenge挑战（该挑战旨在提议一些STARK友好的hash函数），最后在Poseidon和Rescue两者之间，后者赢得了挑战的胜利
但是目前许多系统都在使用Poseidon hash，所以Rescue呢？
然后将Hash和lookup argument结合在一起，就可以得到一些满意的结果，如下图所示
这些高效的Hash函数，使得其可以以一种廉价的方式嵌入SNARK系统，也即不会因为引入了这些Hash函数而导致系统开销增大
但是Hash仍然存在一些问题（？，这里没理解，没听明白），不过也有解决方案，比如Poseidon Hash利用了一种称为Penumbra的基于参数生成模块的技术，该技术可以规范开发Hash函数的过程，解决如何选择Hash函数中一些关键参数的问题，使得最终设计出的Hash函数可以更快的完成开发并投入使用
讨论完了这些相对高层的内容，让我们回到算术化，因为一个计算问题转化为ZKP的第一步是需要将其算术化，那算术化是否会是局限ZKP效率的又一个边界呢？
实际系统中实现算术化的方案由很多：比如基于DSL的Circom、SnarkJS，基于IR的VampIR，以及直接实现或以嵌入的方式实现，不过目前为止R1CS仍然是ZKP实现过程中算术化步骤的主流选择
最后回到最高层，从ZKP构建的流程来看SNARK系统（这个流程之前的博客也有提到过）
首先是对一个函数族进行承诺，这一步基本上决定了证明的大小，是否需要可信设置，以及P和V的效率
其次是选择一个合适的IOP系统，这一步会影响后续转化到算术化的过程
然后是对于lookup argument，这里没看懂
再然后是选择一个合适的Hash函数，因为Hash函数通常会用作随机性的生成，或者扮演预言机的角色，因此一定程度上决定了方案的安全性
最后是选择递归方案，全局可更新的初始设置会存在并发问题，目前使用一些递归方案为了确保透明性会选择合适的承诺方案
Simulation-extractability of zkSNARKs
presenter：Michal Zajac (Nethermind)
Stream Link：Simulation-extractability of zkSNARKs
演讲者首先主要介绍一下他们团队的贡献，之后从NIZK开始讲起，探讨一下目前SRS仍存在的问题，之后介绍一下合理性的概念，以及用合理性可以达到什么目的，并基于此介绍一下模拟可抽取的概念，最后探讨一下如何构建一个可抽取的zkSNARK
该研究的主要贡献如下
- 为NIZK定义了可更新的模拟可抽取性
- 分析了模拟可抽取的NIZK所必须的三个性质
- 分析并证明了大部分的zkSNARK（Plonk、Marlin、Lunar、Sonic、Vampire）都满足模拟可抽取性（无需更改协议，因此意味着不存在效率损失）
- 可更新的Snarky Signature（？）
正式进入演讲，首先回顾一下zkSNARK的性质
- 完备性：诚实的Verifier总是接受诚实的Prover给出的证明（真的假不了）
- 知识合理性：若Verifier接受了关于$x$的证明，则其不仅可以相信$x$为真（假的真不了），还可以知道Prover确实有一个$w$，满足$R(x,w)=1$
知识合理性的定义通常由抽取器给出
- 零知识性：Verifier无法获取除了知statement为真以外的任何信息
零知识性的定义由模拟器给出：Verifier无法区分真实Prover和模拟器给出的Prover的证明
- 简洁性：上述三个性质是ZKP系统必备的，而简洁性是zkSNARK的特点之一，若证明的大小为statement和witnss的对数阶，则称方案为简洁的
有的paper不要求做到对数阶，但是要求不能超过statement和witness的亚线性阶
接下来看一下SRS生成过程中存在的一些问题
首先在现有的zkSNARK方案中，SRS的生成都是由$KGen$算法生成，该算法还会同时生成一个陷门$td$，陷门的作用是为了让模拟器可以完成模拟，但是这个陷门同时也是毒物，必须在生成后销毁，否则恶意的Prover可以用其任意伪造证明
$KGen$过程中如果参与生成的SRS的参与方变成恶意的了，则最后生成的SRS也会有问题，可能会被恶意的Prover利用并伪造证明
实际环境中的zkSNARK会采用MPC的方式来生成SRS，最近几年的论文提出了可更新SRS的概念，任意参与方均可以更新SRS，可更新的SRS只要确保有至少一个参与方是诚实更新的，就可以确保方案的合理性
zkSNARK的基本流程如上图，Prover和Verifier之间会进行多轮交互，每一轮Prover都会根据Verifier的挑战来发送一个多项式$p$，最后一轮中Verifier会发送一个值$z$，并要求Prover计算之前其发送的多项式在$z$处的求值，然后Verifier判断是否接受Prover
为了实现非交互性，采用FS变换将其转化为非交互式的协议，其中每一轮中Verifier发送的随机挑战由随机预言机提供
回到之前知识合理性的定义，知识合理性说明了Verifier在接受Prover证明时，不仅可以相信Statement为真，还可以相信Prover拥有一个有效的witness，这个witness可被一个高效的抽取器抽取出来
但是这个定义在现实协议中可能不太有效，根据知识合理性的定义，如果说协议只在一个Prover和一个Verifier之间完成，那知识合理性可以确保Prover无法证明一个错误的witness，但是如果有多个Prover，此时可能存在安全问题
考虑这样一个场景，假设有Prover相互勾结，并与同一个Verifier进行交互并生成证明，此时$P_1$生成了一个合法的证明并发送给了$V$，随后$P_2$从$P_1$那里获取该证明，将其随机化后作为$P_2$自己的证明发送给$V$
上述情况下$P_2$确实在不知道witness的情况下完成了一次证明，从而攻破了方案的完备性
不过利用一个更强的合理性概念可以确保此类情况下的安全性，也即本次演讲的主要内容，可抽取模拟性
可抽取模拟性的概念中赋予了敌手额外的能力：访问模拟器的能力，之前模拟器的概念是为确保方案的零知识性，这里再次用到了模拟器，目的是希望模拟器可以模拟一个错误的statement的证明，接下来看一下如何实现
在模拟可抽取性的概念中，敌手$A$不仅可以访问随机预言机$H$，还可以访问模拟器，$A$将模拟器也视为一个预言机
接下来定义一个安全游戏，我们要求敌手$A$利用这两个预言机和公共参数，输出一个statement $x$及其相关证明$\pi$，如果$\pi$不是模拟得到的证明，且$A$不知道witness，则表示敌手赢得了安全游戏
这里看一下抽取器的结构，会有一点复杂，因为此时若敌手赢得了安全游戏，输出了一个有效的证明，且$A$不知道witness，则抽取器应当抽取不出witness
因此为了确保抽取器可以成功，需要赋予其一些额外的能力，现在抽取器不仅可以访问公共参数$p$，结构串$SRS$，随机性$r$，还可以访问敌手$A$对两个预言机发起的查询$Q_H,Q_S$
但是这样一来又有两个问题
- 如果$A$只是输出另一个重随机化的模拟证明，怎么解决？
- $E$如何提供模拟证明？
对于第一个问题，可以利用zkSNARK中的唯一响应属性来解决，在安全参数$k$下，唯一响应属性确保了敌手无法提供两个可接受且不同的交互脚本，使得前$k$个输入相同，也即若连个不同的交互脚本的前$k$个输入相同，则意味着这两个脚本中的一个必然会被拒绝
第二个问题通过引入无陷门的零知识来解决，存在某种模拟器，可以在不知道SRS陷门的情况下输出一个模拟证明
无陷门的情况输出模拟证明，听起来有点怪，但是注意到现在是在随机预言机模型中讨论问题，我们可以利用随机预言机的可编程性，来确保模拟器和抽取器输出模拟证明
回到之间zk-SNARK如何构建的问题
以Plonk为例，Plonk的witness是一个大小为$3n$的串，Plonk将这个串拆分为三个大小为$n$的组，并分别编码成多项式（获取多项式意味着获取了witness）
Plonk中这三个多项式的度均为$n+2$，因此根据拉式插值法，如果每个多项式都有至少$n+3$个不同的点，则我们可以恢复这三个多项式
为了实现抽取，Plonk的做法是让抽取器获取这些多项式的乘法求值，而获取的方式是通过rewind
抽取器首先会发送随机挑战，然后$A$返回$z_1$处三个多项式的求值，通过将$A$的状态rewind到*处，继续发送挑战，重复该步骤直到抽取器获取到$n+3$个不同的点为止
但是这里又引出了新的问题，如何确保敌手在看到$z_2$后不会终止？
解决方式是利用基于rewind的知识合理性，该性质确保了无法从Prover发送的多项式中抽取出witness（？这里没看懂）
（然后中间这里有一段没听懂讲的啥，应该不影响，暂时跳过）
如果说$A$不断地响应抽取器，由于抽取器每次rewind都相当于重置了$A$的状态，因此每次rewind后$A$都会请求一个新的预言机，并将该预言机的响应作为随机挑战，则根据之前提到的无陷门零知识性，抽取器可以抽取出知识
总结一下基于FS变换的（可更新SRS）zkSNARK如何做到模拟可抽取性
- 首先是利用无陷门零知识性，确保抽取器可以提供一个模拟的证明
- 之后通过唯一响应性质确保$A$无法输出一个重随机的证明
- 最后利用基于rewind的知识合理性，确保rewind可以获取witness
回答问题环节，Ishai问了一个演讲者自己都不确定的问题，不过这一段我也没听懂
Counting Vampires: From Univariate Sumcheck to Updatable ZK-SNARK
presenter：Michal Zajac (Nethermind)
Stream Link：Counting Vampires: From Univariate Sumcheck to Updatable ZK-SNARK
演讲者还是前面那一位
先来看一下CV方案的证明大小
只需要4个群元素和2个域元素，整体大小估计在2Kb左右，对比目前已有的算法已经很不错了，只是Plonk的一半不到
尽管比Groth16大几百b，但是Groth16不可更新也不具备通用性，因此CV方案已经很不错了
整体上来说，CV实现这么小的证明大小主要有三个关键点
- 利用R1CSLite取代R1CS，从而使得证明过程只需要一个多项式就可以表达整个witness
和Marlin/Plonk相比，这么做可以减少两个群元素
- 新的和校验论证，本文称为Count，可以比Aurora中的和校验论证少用一个群元素
- 最关键的是，本文设计了更有效地批处理方案，使得进一步压缩证明大小
接下来分别来看这三个点，首先是第一个R1CSLite
R1CSLite将整个电路编码为一个矩阵$W$，同时将所有算术门的输出编码为一个列向量$z$，并让矩阵与列向量相乘
在R1CSLite中，若存在合法的witness，则矩阵与列向量的乘积$Wz=0$
这里跑去看了一下原文，没看懂，放个原文链接Link，后续再补
回顾一下R1CS，R1CS有三个矩阵$A,B,C$和一个解向量$z$，R1CS的成立条件为$(A\cdot z)\circ (B\cdot z)-(C\cdot z)=0$
由于矩阵乘解向量$z$的结果也为一个向量，我们可以对这个向量进行拉式插值法，得到一个多项式，用该多项式代表矩阵与解向量乘积的结果，就像上图左侧那样
R1CSLite的方式是将三个矩阵整合成一个更大的矩阵，然后令矩阵与解向量的乘积结果为零
这样一来，我们可以将矩阵和多项式的数量均减少至一个，尽管R1CSLite中的矩阵和解向量都要比R1CS中的大得多，但是其实际的复杂度取决于这个大矩阵的稀疏性（零元素的数量）
利用R1CSLite，zkSNARK原来每一步需要发送3个多项式的求值，此时只需要发送一个即可
接下来看一下如何将R1CSLite的矩阵转变为多项式
注意到R1CSLite成了爹条件为$W\cdot z=0$，因此矩阵$W$中的每一行与解向量$z$相乘的结果均为0，此时我们可以令$x$代表矩阵的行号，从而有
$$ \forall x\in H:\sum_{y\in H}^{} w_{x,y}\cdot z_y=0 $$
也即我们可以构建一个多项式$P$，并令$P(x)=\sum_{y\in H}^{} w_{x,y}\cdot z_y$
不过这还不够，我们希望$w$和$z$不带下标，因此我们需要将矩阵中的元素$w_{x,y}$和解向量$z_y$也变成多项式，利用拉式插值法可以得到$w(x,y)$和$z(y)$
此时上述多项式$P$就变成了
$$ P(X)=\sum_{y\in H}^{} w(X,y)\cdot z(y) $$
该多项式的度$deg_XP(X)=n-1$（因为矩阵的行数$|H|=n$）
接下来是第二步，构建一个新的和校验论证Count来进一步减少群元素的数量
在和校验协议中，P需要向V证明一个多项式$P(X)$在集合$H$中的求值之和为$v$
接下来在CV方案中嵌入和校验协议，回到上述的多项式$P(X)$，此时我们构建一个新的双变量多项式$\Psi(X,Y)$如下
$$ \Psi(X,Y)=w(X,Y)\cdot z(Y) $$
然后令$\Psi_a(Y)=w(a,Y)\cdot z(Y)$表示该多项式在$X=a$处的求值，此时利用和校验协议，上述$P(X)=0$就转化为了下面这个等式
$$ \sum_{y\in H}\Psi_a(y)=0 $$
Count的做法大致如下，需要的组件有下列这些
- KZG承诺
- 双线性配对$e$
- SRS串$\{g,g^s,...,g^{s^k},h\}$，SRS串将用于KZG承诺，$g,h$分别是双线性配对中两个源群$G,H$的生成元
为了对一个多项式$f(X)=f_0+f_1X+...+f_kX^K$在点$X=s$处承诺，承诺方式为计算$com(f(X))$如下
$$ com(f(X))=g^{f_0}\cdot (g^s)^{f_1}\cdot ...\cdot (g^{s^k})^{f_k} $$
这里的$s$相当于某种陷门
根据DH假设的变体，$s$不泄露的情况下，无法通过$\{g,g^s,...,g^{s^k}\}$计算得到$s$
这里有个点需要注意，如果$f(X)$中$X^m$的系数不为零，则SRS中需要包含$g^{s^m}$，否则无法计算承诺值
对于Count而言，SRS是一个很长的串，如下图所示
Notice：SRS中不包含$g^{gap}$这一项，至于为什么，看下面
这里有一个点：如果$f$是一个度小于$|H|$的多项式（多项式的度比乘法群大小要小），则有式1成立
$$ \sum_{y\in H}f(y)=f(0)\cdot |H|=v \tag 1 $$
基于这个点，有一个很妙的做法
在$deg(f)\leq gap-1\leq |H|$的情况下，我们可以构建一个新的多项式$f'$如下
$$ f'(X)=f(X)\cdot X^{gap}-\frac{v}{|H|}\cdot X^{gap} $$
如果我们把这个多项式展开，可以得到
$$ f'(X)=f_0\cdot X^{gap}-\frac{v}{|H|}\cdot X^{gap}+f_1\cdot X^{gap+1}+... $$
注意$X^{gap}$这一项的系数为$f_0-\frac{v}{|H|}$，根据上面提到的，如果$f$的度小于乘法群的大小，则有$f_0\cdot |H|=v$，移项之后就是$X^{gap}$的系数
因此我们把上面这个$f'$用到和校验协议中，P需要向V发送$f'(s)$的承诺，如果说$v$是正确计算得到的，那么根据上面的分析，$f'(s)$中$X^{gap}$的系数一定是0，这也意味着SRS中不需要包含幂为$gap$的元素
然后V只需要验证下列等式即可
$$ f(X)\cdot X^{gap}-f'(X)=\frac{v}{|H|}\cdot X^{gap} $$
具体而言，V通过双线性配对来验证
$$ g^{f(s)}\cdot h^{s^{gap}}-g^{f'(s)}\cdot h=\frac{v}{|H|}\cdot g\cdot h^{s^{gap}} $$
事实上，可以将$deg(f)\leq gap-1\leq |H|$条件放宽，不再让$gap$的大小收到群大小的限制
通过放宽限制条件，得到一个更宽的条件$deg(f)\leq gap-1$，此时之前的式1成立变成了下面这个式子成立
$$ \sum_{y\in H}f(y)=|H|\cdot (f_0+f_{|H|}+...+f_{\lfloor d/|H| \rfloor })=v \tag 2 $$
式2的证明可以看原视频的ppt
最后来看一下如何构建更高效的批处理方式
对于一个要求值的点集$X=\{x_1,...,x_k\}$，以及多项式集合$F=\{f_1(X),...,f_k(X)\}$，记一个函数$Dist(A)$表示$A$中包含的不同元素的个数
批处理方式可以分为两种，第一种是在不同多项式在同一个点求值，比如下面这样
P发送了五个多项式求值，其中前三个是不同的多项式$f_1,f_2,f_3$在同一个点$x_1$的求值，我们可以将这三个多项式打包（Plonk和Marlin也给出了类似的做法），但是此类方式要求揭示$Dist(X)$的承诺
另一种是对同一个多项式在不同点求值进行批处理，就像下面这样
这种方式需要揭示$Dist(F)$的承诺
本文采用了后者作为批处理的方式，可以最大程度上提高效率
到此，CV方案基本介绍完了，接下来还有一些相关的概念
对于CV的透明性而言，由于CV本质上是一个zkSNARK，KZG中用到的SRS串的生成需要通过可信设置生成
如果说我们希望实现CV的透明性，则我们需要将KZG方案替换成基于FRI的承诺方案，同时将上述Count和校验协议替换为Aurora中的方案
区别在于Aurora用的是上述式1，Count用的是式2，且Count用到了SRS，而Aurora无需可信设置
如果说我们希望去除CV中的可信设置，则证明大小会来到对数阶，保留可信设置可以达到更短的证明大小和更快的验证速度
此外，Aurora的SRS更短，且更适合通过MPC协议生成，甚至可以用目前现有的SRS实现，但是Count可以使得生成的证明更短，且和校验协议的速度更快
问答环节没听
接下来两个演讲没听，一个是伊登项目，主要介绍未来数字资产中的安全问题
另一个是大佬聊天，邀请了NIST委员会的人，以及一些大学的教授，主要探讨的是ZKP社区建设的问题
这个两个时间比较长，内容也不太重要，就没听了
Invited Talk: Project Eden and The future of securities settlement in a world of Digital Assets
presenter：Orly Grinfeld (TASECH), Efraim Glatt (TASE)
Stream Link：Invited Talk: Project Eden and The future of securities settlement in a world of Digital Assets
Panel Discussion: ZKProof Community Goals and Deliverables
presenter：Moderator: Eran Tromer (Columbia University),Panelists: Luís Brandão (NIST/Strativia), Michele Orrù (UC Berkeley), Ran Canetti (BU)
Stream Link：Panel Discussion: ZKProof Community Goals and Deliverables
