Keynote：Linear-Time SNARKs for R1CS and Friends
Presenter：Justin Thaler（Georgetown）
Stream Link：Keynote：Linear-Time SNARKs for R1CS and Friends[]( https://youtu.be/TrcT3-VPOz4)
教授先花了一点时间简单介绍一下这个方向的研究现状，之后简单介绍一下线性时间的SNARK，接下来重点探讨乐SNARK中的安全问题，最后介绍了一下他们即将发表的新工作
Part 1 Survey of SNARKs
首先回顾一下ZKP系统，ZKP系统讲的是一个不受信的Prover声称其知道满足某种性质的秘密$w$，比如P声称其知道一个由密码学Hash函数$h$的输出值$y$的原像$w$，也即P声称其知道$w$，满足$h(w)=y$
对于证明系统而言，最平凡的方式是P直接将$w$发送给V，然后由V自行运算$h$并验证等式是否成立
但是SNARK是Succintc Non-interactive ARgument of Knowledge，SNARK不仅需要以零知识的完成上述证明，还希望节约V的开销，简单来说就是需要做到下列两点
- SNARK的证明串$\pi$大小必须（应当）比$w$要小，也即SNARK中的的S（部分研究中认为简洁性应当做到对数阶，也有研究者表明亚线性即可）
- 理想状态下，我们希望V通过$\pi$来验证要比通过$w$验证要快（也即节约V的开销）
How are SNARKsdesigned and uesd？
一般而言，可以采用标准范式构建SNARK
此类方法通常从一个高级语言描述的程序$\psi$（比如C，JAVA程序等等）开始，然后完成证明，以前面那个Hash为例，此时程序以$w$作为输入，之后程序计算$w$的Hash值，并判断是否与$y$相等即可
此类方法主要分为下列几个步骤
首先将程序$\psi$转变为可概率验证的等价模型，该过程在一些电路可满足问题（及其变体）上非常常见，因为电路的中间值本身就是一个中间表示法（Intermiediate Representation，比如算术电路，R1CS，AIR，Plonkish IR等等），这个步骤通常也称为证明系统的前端
其次，利用SNARK为这些变体构建证明系统，这一步也成为证明系统的后端
就像这张图一样，首先将一个C程序，转换成一个电路，然后再利用SNARK完成该电路的证明
前端的例子有很多，比如下面这些
- Bellman and CirCom：基于低级硬件语言描述，通过witness来检查$\psi$的方式
- Cairo，ZoKrates，XJSnark，etc：$\psi$由某些特定受限域的语言描述
这个受限的形式有很多，比如限制写内存的次数为一次，不允许使用重要的数据结构（比如不允许使用string），限制使用或不允许使用控制流
- 支持各种高级语言的项目：
比如各种zkEVM项目，旨在支持EVM字节码（以太坊虚拟机字节码），并用其编译Solidity程序（一种智能合约编程语言），也可以将zkEVM项目称为Solidity导向的项目
或者RISC-Zero项目，目的是支持RISC-V的指令集，从而让其编译高级程序语言
CirC项目：并期望设计一个编译器结构工具包（比如LLVM for SNARK front end）
从后端的角度来看，针对电路可满足性或其他IR表示的SNARK，通常需要满足下列三个条件
- P的时间开销尽可能的与电路大小呈线性关系（必然不会小于线性，因为P至少需要读取整个电路）
- 证明大小尽可能地小
- V的开销尽可能地小
当然理想情况下还希望做到下列两点
4.透明性，也即可信设置中不存在毒物（toxic waste）
因为我们不希望系统在初始化阶段需要执行一个很复杂的流程来生成所需要的参数，这个过程也会产生上述所谓的毒物
若部分恶意的参与方没有销毁这些毒物，他们可以利用这些毒物来伪造证明，从而攻破系统的合理性（这里的毒物可以理解为某种陷门）
不过目前很多系统都在使用非透明的SNARK，因此透明性并不阻碍系统的实现，但理想世界中我们更希望系统满足这一性质，因为其可以完全消除信任
5.看起来最好是抗量子的
这个也不急，因为量算还没普及，大部分基于计算的困难性假设仍然成立，从而确保系统的合理性
目前ZKP后端设计流程主要遵循下面三个步骤
- 为R1CS或C-SAT设计一个P-IOP证明系统
- 将该证明系统与多项式承诺方案相结合，以得到简洁的交互式论证
- 利用FS变化将其转化为非交互式论证
目前主流的SNARK方案都遵循上述设计范式，除了Groth16，GGPR13，Pinocchio等，不过这些方案只是第一步不同而已，这些方案的第一步是设计L-PCP，而非P-IOP，因为那时候还没有IOP，除此之外，后两步还是相同的
P-IOP中，Prover需要向Verifier发送一条关于某个多项式$h$的消息，Verifier不会直接读取整个多项式（因为多项式的度很可能和电路的规模一样大），取而代之的是Verifier通过交互时证明，请求该多项式上某个点的求值来完成对该多项式的验证
上述过程可以结合多项式承诺完成，利用多项式承诺，不仅可以确保P无法伪造一个证明，还可以利用承诺方案来压缩证明的大小，提高证明的效率
目前学界也有许多不同的IOP方案和多项式承诺方案，可以通过组合不同的方案来权衡P的效率、证明大小以及基于的假设等等
注：方案的透明性和抗量子性与采用的IOP方案无关，仅与采用的多项式承诺方案有关
Part 2 Taxonomy of SNARKs
对于SNARK的分类，先从非透明的方案开始讲起，主要可以分为两类
- 以Groth16为代表的基于L-PCP的方案：Groth16仍然是最优，因为证明串仅包含三个群元素（且该论文给出了下界为两个群元素），该方案中的Verifier的复杂度也很低
但是此类方案的缺点比较明显，其可信设置是与电路相关的，初始化过程比较慢，而且P的空间开销比较大，不满足抗量子性
- P-IOP+KZG方案：可以达到常数轮的交互，此类方案的典型例子有Marlin、Plonk等方案
方案的优点在于其可信设置是全局的，与具体的电路无关
缺点在于证明大小会稍大一些（大约是Groth16的4-6倍），且P的效率耶尔必Groth16慢，同样不满足抗量子性
不过此类方案有一个比较有意思的优势，就是其可以使用比R1CS和C-SAT更灵活的中间表达法
接下来看一下透明的方案
- 任意P-IOP+Bulletproof多项式承诺：代表方案为Halo2
最大的优点在于此类方法构建的证明大小为所有透明SNARK中最小的
缺点是Verifier的验证时间很慢
- 任意IOP+FRI多项式承诺：此类方案设计的比较多，代表方案以STARK为首，包括Fractal、Aurora、Virgo、Ligero++等等
此类方案构建的SNARK在满足（可能）抗量子性的情况下达到最短的证明大小
但是P的时间很慢，证明大小实际上也不小（具备抗量子性最小而已，和其他不具备抗量子的方案相比仍然很大）
- MIP或IP方案+高效Prover多项式承诺：利用基于和校验的交互式证明系统与快速Prover承诺方案构建
代表方案有Spartan、Brakedown、Orion等等
此类方案的Prover效率是所有透明SNARK中最高的，如果使用的多项式承诺具备抗量子性，则此类方案得到的证明系统也应该是抗量子的
缺点在于证明大小都比上述两种透明SNARK要大
这里简单介绍透明SNARK的第三种构建方案
以Breakdown为例，Brakedown结合了用于R1CS的P-IOP和一个高效的多项式承诺，该方案可以达到线性阶的Prover（只需要线性次数的域运算或Merkle Hashing），不基于特定的域（可以在任意足够大的域上构建方案）
Brakedown的证明大小为$O(\sqrt{\lambda N})$，其中$N$为R1CS实例的大小，虽然从复杂度的角度来说是亚线性的，但是具体实现的时候并不太亚线性，实际证明大小会非常大（MB级别，比其他方案大1-2个数量级）
尽管缺点很明显，不过Brakedown给出一些新的关键技术组核心
- 线性时间内完成编码的纠错码
- 编码函数随机生成
- 码字不满足相对距离的错误概率至多可达$2^{-100}$
- 一种可抽取的多项式承诺方案，可快速编码，但是不能快速解码
Crypto22上，Xie，Zhang，Song提出了Orion，该方案将Brakedown与Virgo相结合，旨在解决Brakedown中证明长度过大的问题
Orion的通过将Brakedown中的V表示为一个电路，并采用Virgo证明一个满足该电路的赋值，此外Orion还抛弃了Merkle认证路径，因为这样做会导致Brakedown的电路很大，从而降低验证效率
结合上述两个方法，Orion可以将证明大小缩短至1/6至1/7，但是由于Virgo采用的是FRI多项式承诺，需要用到FFT，因此Orion不再和Brakedown一样可以在任意域上实施，需要在FFT友好的域上实施
基于Orion的想法，Chen，Bunz，Boneh，Zhang提出了Hyperplonk，主要思想是通过KZG或PST承诺方案来代替Orion中的Merkle Tree
利用KZG/PST承诺的高效批处理性质，以更简洁的方式来验证Brakedown中Verifier的证明
目前Hyperplonk还没有具体实施，估算实际证明大小不会超过10KB
尽管证明长度很短，代价是失去了透明性，任意域和抗量子这三个性质
Part 3
Security of Fiat-Shamir Transform
这部分从FS变换的安全性讲起
考虑一个恶意的Prover，目的是攻破FS变换，由于FS变换中的Verifier随机挑战由Random Oracle生成，因此Prover的朴素做法是随机生成$\alpha$，不断的请求RO，直到其获得一个合适的$\beta$（找到碰撞）
假设系统的安全参数$\lambda =80$，假设Prover进行了$2^b$次Hash（请求RO），则其攻击成功的概率为$2^{b-80}$
如果需要达到$2^{-10}$的成功概率，则理论上需要计算至少$2^{70}$次Hash，但是根据生日悖论，安全参数为80的情况下，计算$2^k$次Hash找到碰撞的概率为$2^{2k-160}$，因此实际上计算$2^{70}$次Hash的成功概率为$2^{-20}$
基于上述分析和目前已知的攻击手段，咱们分析一下Orion的安全性
Orion采用一个122比特的域，经分析，交互式Orion的合理性错误不超过120比特（估计甚至小于100比特），此时利用FS变换转化为SNARK系统，大约需要$2^{60}$次Hash可以以$2^{-60}$的概率攻击成功（实际上可能是$2^{-40}$或更高）
在Brakedown的初始化只会执行一次，因此此类方法不适用于Brakedown方案
从证明和推测的角度来考虑安全性的话，Orion声称其在适用FS变换之前的安全性可达128位，但是目前已知的安全性分析并未证实其是否真的满足这么高的安全性，目前只证明其满足48位的安全性
如果Brakedown适用同样的假设，则证明大小可以减少差不多一半
Security of deployed FRI-based SNARKs
讨论完了FS变换的安全性，接下来看看基于FRI的SNARKs的安全性
以StarkWare为例，目前该系统在适用FS变换前推测可达到80位的安全性，然而目前已证明的应用FS变换前的安全性仅可达到54位
另一个例子是Plonky2，安全性可达100位
对比一下计算Hash的成本
- 2020年1月，计算$2^{64}$次SHA-1的成本为45k美刀，简单推测一下计算$2^{70}$次大约需要300万刀（现在应该会更便宜）
- 比特币的算力可以在75分钟内完成$2^{80}$次SHA-256，但是该过程产生的价值只有不到100万刀
Proposals to resolves the disconnect
最后演讲者给出了一些研究和社区脱节的解决思路
- 更新社区参考文档，使其讨论的范围不仅仅局限于benchmarking，还应当多关注SNARK的实施（paper里面效率分析满天飞，最后系统做出来效率还是差）
- 鼓励一些安全级别较低的项目，让他们解释为什么认为他们的安全级别足够（你说你行，但是我觉得你不行，你得解释清楚你为什么行）
- 解决一些脱节问题，因为密码学对于相当一部分人来说还是太“高端”了，而且许多终端用户不仅安全意识较差，同时也是风险意识比较薄弱的一群人，因此有必要解决此类脱节的问题
Q&A
这里没听懂，老头的口音比较重，而且麦炸了听不清
回头有时间去看看油管自带的字母能不能识别一下老头的话
Halo2 and Standardizing Plonk
Presenter：Aurelien Nicolas（QEDIT/Scroll）
Stream Link：Halo2 and Standardizing Plonk
演讲者主要介绍了一下Halo2中的性能、安全设计等方面
对于性能而言，主要关注三个方面
- Witness Area：性能必然和witness相关，包括各种数据和中间结果的数量，如何以合理的方式组织这些数据
- Height & Width：需要分Prover和Verifier讨论，以及讨论电路中是否有递归
- Gate Complexity：门的复杂度，因为这一块涉及到方案实施时的效率
首先是Witness Area，这一部分首先需要考虑的是数据结构，包括输入输出和所有的中间结果，都会消耗cell（Halo2中的一种单元格），为了简单起见，这一部分先通过静态设计，然后再进行动态优化
以EVM的加法门为例，以位为单位，处理256位的数据需要$3*256$个cell，以字节为单位，处理32字节的数据需要$3*32$个cell，截断处理只需要少数数量的cell，但是此类情况取决于数据（处理方式就和上面那个图的右侧差不多）
但是存在一些特殊情况，比如下面这个图
电路中有些门可能会共享或独立使用某一列的数据，同一列中相同的门是互斥的，这种互斥的门会一定程度上浪费Prover的时间，但是却是一种很好的减小电路的方式
分配方式可能是取决于数据的，比如EVM中的步骤可能有多种形式，越小的操作步骤意味着占用更少的cell，因此需要评估电路中门和cell的利用率
此外，门的最大度会与Prover时间相关，这个度一般只有5和9两种情况
大部分的门应该都是度为9，若不为9，则可以用更多的witness行来提高度，就像下面这个图一样
度比较高的表达式可以在中间cell中被拆分
最后看一下电路的高度和宽度，电路越宽意味着Verifier的开销越大（取决于列的数量），越高意味着Prover的开销约到（取决于行的数量和门的度）
Halo2有许多变体，不同的变体的Verifier开销不同
这里以zk-rollup为例，分析一下开销模型，说明一下何种情况需要宽的电路和窄的电路
当witness很大，且具有很多的的门，此时需要尽可能地降低Prover的开销，根据上面的分析，降低Prover开销的方式是将电路变矮，也即将电路做的尽可能地宽
但是如果是在链上完成验证，需要尽可能减少验证开销，因此需要把电路做的尽可能窄，从而降低Verifier的开销，此时可以利用KZG变体来实现
将上述两者聚合就可以得到下面这张图
最后看一下Gate Complexity（这部分没听懂，可能是没学Halo2的原因，不太了解Halo2的实现细节）
aPlonK: Aggregated PlonK from Multi-Polynomial Commitment Schemes
Presenter：Miguel Ambrona (Nomadic Labs)
Stream Link：aPlonK: Aggregated PlonK from Multi-Polynomial Commitment Schemes
这位演讲者是来自Nomadic Labs的开发人员，这个实验室主要是研究智能合约和区块链扩容问题的，ZKP可以很好的解决智能合约的一些问题，而且非常适用于链扩容，题目中的aPlonk实际上是aggregate Plonk，也即聚合Plonk，旨在解决区块链扩容问题
区块链扩容的目的是提高其吞吐量，使其可以处理更多的交易，因此区块链研究员与开发者们提出了一个二层的解决方案，称为Validity rollups，大概意思就是通过rollup来压缩多笔交易，然后再发布到链上
以上面那个图为例，Alice和Daisy都向Bob转账了，此时rollup处理器（独立于区块链）将所有的交易汇总起来，并构建一个证明，然后将这个证明和更新后的交易值发布到链上，此时验证该证明就等价于验证了这一批中所有的交易
事实上这个过程并不是很简单，会遇到很多问题，包括但不限于
- 验证证明的复杂度和开销要比单独验证这些交易要小，要不然还不如不打包
- Prover复杂度为$O(n\log n)$，能否进一步降低
对于上述问题，目前有一些解决方案，如下
- 采用递归技术
- 利用IVC和PCD技术，将SNARK中一部分验证工作从电路中去除
不过这样会引入新的问题：需要用到循环椭圆曲线和非本地的操作，而实际环境中希望尽可能的避免这些操作
一个比较好的解决方案是Plonk的证明聚合，一种基于SnarkPack的技术$[GMN21]$
首先简单回顾一下Plonk方案，具体可以看之前Plonk的那片博客
Plonk主要运用了多项式承诺，Plonk需要对一个很大的多项式完成承诺，根据承诺的特点，可以将这个很大的多项式压缩成群或曲线上的某个点，之后由Verifier发起一个挑战，Prover响应多项式在该挑战上的求值即可
Plonk中构造了很多高阶多项式及其对应的承诺，然后计算这些承诺值的Hash来作为Verifier的随机挑战，之后再揭示这些多项式在这个挑战的值来完成证明
如果以Relation的方式描述的话，公共输入和相关信息就是$x$，三个多项式$A,B,C$就是Prover的witness
接下来看一下aPlonk如何聚合，假设我们有$K$个证明需要聚合，因此也就有三个大小为$K$的多项式需要证明，aPlonk的思想是通过置换论证使得$K$个证明之间可以共享（前提是这些证明都是基于同一个电路，rollup环境中显然是同一个电路）
由于Plonk用的是KZG多项式承诺方案，这个方案是具有同态性的，因此与其挨个证明每个承诺，不如证明这一堆承诺的某个线性组合，就向下面这样
上述对承诺的承诺的证明可通过一些现有的技术来完成，比如利用SnarkPack
SnarkPack的方式是在目标群中构建上述线性组合，从而得到一系列的配对，然后再用内积论证来完成配对的证明
这里演讲者说了一个问题，这里的对承诺的承诺无需满足绑定性，具体不太清楚为什么，没太听懂
上述过程需要Verifier执行线性次数的群操作和多项式求值，为了进一步减少Verifier开销，再套一个Plonk来完成验证
为了做到上述的聚合证明，还是需要进行承诺，也即对（这$K$个）承诺的承诺，因此需要完成的工作是，对这些承诺进行承诺，然后计算Hash，得到$r$，构建一个关于$r$的多项式$w$，并生成该多项式的证明
详细内容可以看论文原文：$[ABST22]$ aPlonK : Aggregated PlonK from Multi-Polynomial Commitment Schemes
接下来再介绍一些其他的技术，Hiding Public Inputs，一种隐藏公共输入的方式
回到原来rollup的例子，我们可以为四个rollup交易生成证明，这四个证明均包含两个公共输入：一个是已验证的上一个交易，一个是交易之后的状态
实际上区块链Verifier只关心第一个和最后一个，也即图中最左侧的黄色输入和最右侧的橙色输入，中间的输入只是对中间证明很重要，区块链Verifier实际上并不关心这些中间证明，因此可以用Plonk来隐藏这些中间输入，使得Verifier只看到黄色和橙色的输入
这么做不仅可以使得证明大小降低至亚线性，还可以使得待证明的statement降低至亚线性
最后看一下本方案的效率，在$2^{16}$个约束下，上述方案的测试如上图所示，和Plonk相比，显然aPlonk在验证时间和证明大小都达到了预期的亚线性
前面提到了aPlonk在生成证明过程中需要很多额外的计算，经过测试对比，和相同数量的Plonk相比，在初始化和生成证明过程中的时间开销并没有太显著的增加
总结一下aPlonk的工作
- 一种聚合Plonk的方案，旨在提高多个Plonk证明的效率
- 为了实现上述目标，还提出了多多项式承诺方案
- 提出了元验证（Meta-Verification）的概念，不仅可以隐藏公共输入，更重要的是它可以阐述证明的生成与聚合之间的关系，将多个聚合后的证明以特定的方式联系在一起
- 有效的将承诺数据纳入了Plonk的Statement中
最后演讲者给出了这个项目的地址GitLab:aPlonk