这篇文章是对2022年8月3日，0xScope Labs与深潮共同举办的第一次Webinar的记录。视频回放和完整讲义在文末，请自取～
什么是0xScope Labs
0xScope是第一个Web3知识图谱协议，它通过权重归集算法，将多个“单点地址”联系成一个实体，并基于实体构建多种类型的知识图谱来深度刻画赛博世界，我们确信0xScope是Web3伟大范式变革中的先驱之一。
0xScope Labs是由0xScope发起的Web3创新实验室。我们的使命是「以技术洞见驱动伟大创新」。
我们每周会围绕前沿技术、行业思辨、创新案例举办Webinar。基于0xScope独有的数据分析能力，提供硬核技术分享、热点事件剖析与深度行业洞察，让行业最前沿的技术创新和最具洞见的商业思潮在这里融汇。
如果您想了解0xScope & Labs的愿景并加入我们：
zk溯源与展望
zk技术将成为区块链终局的重要组成部分，我们非常激动地站在技术革新的前沿，本次讲座将一路引领，从最基本的概念到最前沿的应用，为你构建zk技术最全面的知识框架和创新图谱。
zk的本质是什么？zk在实际应用中的实现？现有的zk方案有哪些特性？他们都做了哪些Trade-Off？本周由0xScope Labs Engineer & 密码学研究者 Pan ，为我们拆解zk的历史、现状与未来。
我们希望以一场Webinar和活动回顾，为大家呈现一个较为完整的zk认知谱系，并尝试为0xScope Labs的建立奠定基础。受篇幅所限，不能逐一进行细节讨论。关于诸多算法和应用的细节讨论，可以加入社群，与Pan老师以及其他zk爱好者交流：
嘉宾&主持人介绍
0xOar | 0xScope 创始人，致力于为Web3打造基于实体和知识图谱的全新数据层。
Pan | 0xScope 研究员，密码学专家。
大纲
证明系统的分类：知识证明和零知识证明
证明系统 (Proof System)
是一个交互式协议，包含两个参与方 Prover 和 Verifier。证明系统的作用是让 Prover 说服 Verifier 相信一件事，我们把这件事叫做一个陈述 (Statement)。
- 完备性（completeness）：整个证明系统能通过输入生成证明，证明的结果可以被验
- 可靠性（soundness）：伪造证明来通过验证的概率极小或几乎为零
证明系统的其他特性：
- 简洁性 (Succinctness)：证明系统的通信量比证据witness还要小，那么这个证明系统就具有简洁性
- 交互性/非交互性：通过密码学工具（fiat-shamir）可以将交互式证明转换为非交互证明。
- 零知识 (Zero-Knowledge)：在statement是正确的情况下，如果除了正确性，Verifier无法从交互中获取任何其他“知识”，就称这个系统是零知识的。
- 可迁移 (Transferable) ：如果statement是正确的，并且把交互过程发送给其他 验证者，也能够让其他验证者相信陈述的正确性，这个证明系统就是可迁移的；
知识证明
如果要求 Prover 必须知道一些信息才能让 Verifier 验证通过，那么这个系统可以被称为知识证明 (Proof of Knowledge)。知识证明在计算意义下的版本，叫做知识论证 (Argument of Knowledge)
不同特性的组合：
1. 非交互性 + 零知识 (Non-Interactive Zero-Knowledge, NIZK) 将零知识性和非交互性结合起来，就有了非交互零知识。
2. 非交互性 + 简洁性 (Succinct Non-interactive ARGument, SNARG) 简洁性的证明系统结合非交互性，就有了简洁非交互式论证。
3. 非交互性+简洁性+知识证明 (Succinct Non-interactive ARGument of Knowledge, SNARK) 如果一个 SNARG 同时是一个知识论证，它就被称为简洁非交互式知识性论证。
零知识证明的定义和判断方法
零知识证明(Zero—Knowledge Proof)，是由S.Goldwasser、S.Micali及C.Rackoff在20世纪80年代初提出的。它指的是证明者能够在不向验证者提供任何有用的信息的情况下，使验证者相信某个论断是正确的。 性质：零知识证明是一个证明系统，且它拥有以下三种性质：完备性（completeness）；可靠性（soundness）与零知识性（ zero knowledge ）。 当判断一个系统是否是零知识证明时，需要问以下三个问题：
- 是否是证明？
- 是否有知识？
- 零知识性？需要注意的是，零知识意味着没有获得任何更多的信息（如更多的算力或更高的概率披露）
以数独和离散对数的例子来举例：
1、数独游戏
规则：填入1-9的数字使得每行每列以及9个3x3方格都包含数字1-9，且每个数字只出现一次 现在有两个玩家P和V，P为V准备了一张数独图要求其完成数独游戏，但V花了很长时间都没有解决这个问题，于是怀疑P提供的这个数独游戏没有解法，于是要求P证明V这个数独游戏是可解的。 P可以直接提供给V这个数独的解，但这就使得V知道了数独的答案，失去了游戏的意义，与此同时这就变成了一个“知识证明”。如果有一种证明方法，可以让P不用给V看这个数独的解，就能证明这个数独有解，那就是一个“零知识证明”。 这个证明分为几个部分：
- 承诺阶段
P将每一个包括题目和解的数字都变为一个单独的纸片，将其按找解的排列顺序摆在桌子上。但是将已经由题目提供的数字翻到正面，V可视。将解的数字翻到背面，V不可视，V此时看到的和原来的题目一致。 - 挑战阶段
V选择通过行/列/3x3方格的形式进行验证 - 回应挑战
如果V选择了按照行验证，P将每一行的所有数字纸片都打包到一个空间里，一共打包9个空间。然后由V对空间内的数字纸片进行打乱。 - 验证阶段
打乱后V将空间内的纸片取出，如果纸片包含1-9数字，则验证成功。 - 重复验证
由于P有1/3个概率猜中V选哪种方式验证，所以需要通过多次重复验证使得P猜中的概率指数级缩小，最后达到一个可接受，可忽略不计的范围。在这个过程中，V并没有看到解的方案，但却成功相信这个数独游戏有解，完成了一个零知识证明过程。
2、离散对数
一个零知识例子：Pinocchio
1、如何表示一个陈述 statement，具体来说，如何表示一个statement的verify？
R1CS
我们可以把计算用一个算术电路来描述。一个算术电路可以对数字进行算术运算。电路由加法门、乘法门以及一些常数门组成。
一种描述方法：R1CS：
A·z * B·z = C·z
A、B、C代表问题的描述，可以理解为约束关系；z是这个问题的解
QAP
在零知识证明领域，许多 zkSNARK 把 R1CS 问题作为目标问题。不过，大部分 zkSNARK 是把 R1CS 问题继续转化，得到一个等价的多项式问题，再对这个多项式问题设计证明方案。
2、证明方案：
在第一步中，我们通过电路转化，将一个statement转换成电路形式，进而将statement的验证转化成了多项式是否能够被整除的问题。考虑到计算的效率，方案通常检验在某个随机的点上，多项式是否被整除。因此，为了防止Prover通过得知这个随机的点来伪造证明，我们需要通过某个工具来隐藏这个点，并且这个工具不会破坏原有多项式的线性运算，这个工具就是椭圆曲线群。
总结：
- Pinocchio需要可信setup，并且这个setup与具体的应用（电路）强绑定
- 安全性：方案使用了椭圆曲线群和双线性映射（pairing），具体的难题假设是KOE
- 证明大小：通信复杂度为 8 个群元素
主流方案
目前主流方案改进的方向有：
- 如何提升效率：证明开销&验证开销
- 可信set up的问题
- 电路优化
- recursive
- lookup arguments
Source：https://www.michaelstraka.com/posts/recursivesnarks/
Recursive
- 把证明验证的逻辑放入电路中，即验证 verify(crs, X, proof) = 1
- 可以一次证明验证中的验证多个proof的有效性
- 使用场景：1）区块链状态的压缩（Mina）；2）Proof composition（zkEVM）
主流方案比较
- bulletproof 不需要可信设置，具有较小的 proof size
- groth16 基于 QAP 构造了通信量仅为 3 个元素，验证者计算开销仅为 4 个配对运算的 zk-SNARK
- plonk 多项式承诺 + 新的电路范式（PLONKish Arithmetization），实现了一个低开销的，同时setup string是通用且可以更新的zk-SNARK
- halo 无需可信set up + aggregation
验证计算与SNARK
随着layer2技术的发展，基于零知识的zk-rollup得到了大家越来越多的关注，特别是最近polygon，zksync，scroll这些项目的进展。zk-SNARK在很多人看来一般会画在隐私保护的范畴里，那它layer2中扮演的是什么角色呢？实际上，在layer2中，zk-SNARK更多的是起到验证计算的作用。为什么在layer2中，我们不用普通的验证，而需要用看起来更复杂的SNARK呢？
zk-SNARK的两个特点：
- 零知识性：
标准验证：需要用到证据（witness）的验证计算。
zkSNARK 验证不需要witness，因此证明不会泄露任何信息 - 简洁性 (Succinct)：
a) zkSNARK 证明比证据（witness）更小
b) 验证 zkSNARK 证明比标准验证更快
当前一些很热门的应用场景，比如验证计算（zk rollup）。例如，大量交易的验证和执行交给layer2的节点（服务器），借助服务器打包并生成对应的证明，只需在验证节点进行少量的验证计算就可以验证计算结果，保证安全。这个场景中交易数据并不需要隐私保护，也就不需要 ZK，但是需要简洁性。
Q&A
Q：请问我们看到市面上也有几个STARK的zk-Rollup解决方案，那STARK/SNARK之间有什么主要区别吗？对于zk-Rollup来说是否SNARK更适宜？
Pan：对于ZK-Rollup来说，实际上并没有说很明显的哪种更适宜的说法。但完全基于我个人的揣测，我觉得像STARKWARE这样的项目方坚持于STARK可能有立场上的考虑，包括一些沉没成本和基于抗量子性的宣传考虑。
Q：针对于zk-Rollup解决方案，为何市面上有特定的解决方案（Transfer/Swap/NFT）与通用的解决方案之分？
Pan：这个要考虑到一些专用方案在开发时并没有像Plonk这样的通用setup方案，当时缺乏一个通用setup的解决方案能满足所有应用的需求，受限于此，应用在launch前都需要进行一次多方参与的可信setup，但是让应用方做这个事情肯定是不安全和技术难度复杂的。同时由于有groth16这样的方案，基于特定电路的解决方案在效率上要比通用的解决方案更优秀，这也是需要考虑的一点。考虑到新技术的发展和layer2生态未来的可扩展、可组合性，相信通用解决方案像zkEVM会逐渐成为市场的主流。
Q：在上面的R1CS转化QAP的过程图中，s是多项式的根。多项式又是乘积的形式，所以只要一个s是正确的根，导致一个乘积子项=0，就可以认为整体的结果为0。 这样就大大加速了计算，并且足够简洁。 对么？
Pan：从R1CS的等式来看，s确实是方程组的解，但是这个方程组（A·s * B·s = C·s）没有乘积子项为0的要求。加速了运算是因为在转化成QAP的过程中，我们引入了多项式（A(x)*B(x)-C(x)），这样我们可以将检验方程组转化为判断多项式是否能整除一个其他多项式的问题（例子里的Z(x)）。而多项式有个特点，就是两个不同的多项式只要有一个系数不一样，经过的点会截然不同，即使我们只检验某个随机选择的点，两个不同多项式在该点相等的概率也极低。这样的话，多项式就起到了类似放大器的作用，使得检验多项式会比检验方程组要快的多。
Q：记得在optimistic-rollups中存在争议时挑战流程是交互性的，有一个对数据二分挑战的递归过程。这与zk-rollup不同的主要原因是什么？
Pan：Optimistic Rollup本质是一个挑战应答的机制，需要为挑战行为敞开一个窗口期，往往在时间上有一定牺牲。ZK Rollup并没有使用这一机制，证明验证过了就是过了， 没过就是没过，在ZK Rollup上主要状态更新了它就一定是有效的，因为如果无效ZK证明就不会通过验证。问题提到的二分递归过程我猜测是为了能够在挑战时快速的找到发生错误的状态根，对于这一点后续我们可以再进行深入交流。
Q：对两张图的解释
Pan：这两张图都是为了从某些维度去给现在比较主流的零知识方案做一些分类，其中第一张图里先是从reference string做了划分，uniform是指均匀随机的字符串，而structured是指引入了toxic waste，这个指setup时必需，但是一旦setup完，需要立刻销毁的私密信息。再往下细分的区别是一类setup的字符串是通用的，即一次生成后可以满足所有应用逻辑，如plonk，另一类是针对不同应用或者不同电路都需要运行一次setup，如比较早期的groth16，匹诺曹等。另一个划分的维度是验证的复杂性，有些是线性的，有些是对所有电路都是高效的，有些是对特定满足要求的电路是高效的（比如这个电路可以被比这个电路小得多的信息描述）。不同的compiler可以理解为方案基于的密码学工具、证明协议、代数结构不同。第二张图是对snark的设计做了分类，比如groth就是基于pairing和线性pcp做的，bulletproof是基于多项式承诺实现的，跟同属于多项式承诺下的其他方案区别是它是基于离散对数，因此有transparent性质（也就是不依赖可信setup）。
结语
第一期Webinar的第一部分就到这里结束了。
想了解更多技术细节和推导过程，请看视频回放（访问密码：fyMC）；
如果您有想要分享与探索的内容，可以在我们的idea pool中写下您对下一期议题的建议；
感谢大家的阅读，我们下期再见。
To get involved and stay up to date: