Zero Knowledge (ZK) 零知识证明

零知识证明是指一方（证明者）向另一方（验证者）证明一个陈述是正确的，而无需透露除该陈述正确以外的任何信息，适用于解决任何NP问题。而区块链恰好可以抽象成多方验证交易是否有效（NP问题）的平台。

简单而言，就是证明者向验证者在不透露问题的解的前提下，证明自己知道某问题的解。

举例而言，对于一道数独题，可以这样进行零知识证明：

1. 证明者在一个个小卡片上填写答案，将其数字朝下放在桌子上，对于数独已给出的数字则数字朝上放置。

2. 验证者可以选择某行或某列进行验证，验证前证明者将该行或该列的卡片进行打乱。

3. 验证者将被打乱的卡片进行翻开，验证数字是否是1–9。

4. 验证者进行还原后，验证者可以继续进行验证。反复进行多次后，可以确定证明者知道数独问题的解，同时验证者没有得到解的信息。

在实际应用中，零知识证明往往与同态加密相关。

上面的两个例子中，都需要验证者去进行选择，所以称之为交互式的。但由于交互式存在一个等待过程，所以效率不高，在实际应用中大家更希望证明者直接生成一个完全的证明，验证者收到证明后私下验证即可，我们称之为非交互式的。

Goldwasser、Micali 和 Rackoff 提出了零知识证明有三个性质：

完备性（Completeness）：如果证明者对证明给出诚实的回答，则验证者就能以极高的置信度确定证明者了解关键数据。（真的假不了）

正确性（Soundness）：证明者如果不了解关键数据，就无法欺骗验证者。（假的真不了）

零知识性（Zero-knowledge）：证明者不会对验证者透露任何关键数据，而只是间接证明其了解数据。（无额外信息）

当前zk主要分为两类算法，SNARK和STARK。

SNARK

SNARK, Succinct Non-Interactive Argument of Knowledge，即简洁非交互式知识论据。所谓简洁性，通常是指即使验证程序很大，生成的 proof size 也不会很大，同时又能很快的完成验证。

SNARK具备以下性质：

• 简洁性（Succinct）：验证所需要的计算资源远远小于重新跑一遍需要证明的程序。

• 非交互性（Non-interactive）：证明者和验证者不需要每一轮都沟通。他们只需要在一开始完成可信初始化（Trust Setup）：其他验证者也可以在可信初始化之后加入验证。

• Argument：如果证明者有着无比强大的算力，那么他可以生成假证明。如果这种情况发生，主流的公私钥加密模式也不再安全。

证明者与验证者之间不需要交互即可实现证明，交互的零知识证明要求每个验证者都要向证明者发送数据来完成证明，而无交互的零知识证明，证明者只需要计算一次产生一个 proof，所有的验证者都可以验证这个 proof。

SNARKs利用同态承诺等手段，使得证明方在不暴露原始数据的情况下向验证方证明他手中持有该多项式问题的解。证明过程依然是基于前面的三段论与非交互证明构造出来的这种技术通常用于区块链中智能合约的验证，即证明方需要证明它的输入确实能经由合约内容产生给定的输出。当然实际使用中，我们有时候甚至连输出的内容和多项式系数都不想暴露，但这并不妨碍利用同态性质导出证明。

它是对所有零知识证明问题的通用解决方法，由加密数字货币zcash首次使用并开源。

SNARK的优势：

1.通用库，可以解很多零知识证明问题

2.验证证明性能较高（300tps）

SNARK的不足：

1.底层模型不容易理解，用户需要根据具体的零知识证明问题，在上层构建自己的业务模型，这块开发的工作量较大。

2.生成每笔交易时延较长（57s）

业界广泛采用以下几种算法：

• Groth16：Zcash 一开始使用了这种算法。它是零知识证明中的跑分对照组，因为它具有证明快，生成的证明小的特点。它的缺点是需要可信初始化，并且一次可信初始化只能针对一个程序。它拥有最完善的工具链。

• Sonic：支持 Universal Setup. SRS 的大小和程序大小成线性关系。生成的证明是固定大小，但是验证需要消耗很多的计算资源。Sonic 让通用计算的零知识证明变为可能。

• Fractal：支持递归（Recursion）。生成的证明占用较多空间。

• Halo： 支持递归，但并不满足简洁性（Succinct）因为证明时间是非线性的。Halo2 是目前主流使用的证明系统。

• SuperSonic：第一个实际的，可以应用的 Transparent ZK-SNARK。

• Marlin：程序可以升级。性能处于 Sonic 和 Groth16 之间。

• Plonk：程序可以升级；参与者按照顺序加入可信初始化。这让进行有很多人参与的可信初始化不那么复杂；Plonk 使用 Kate commitments 而不是多项式承诺（ZK-SNARK 的第一步是将计算问题转化为多项式问题）。许多现代化的零知识证明系统都构建与 Plonk 之上。Plonk 有着非常优秀的工具链。

当前zkSync, Scroll, Polygon Hermez都使用SNARK算法。

STARK

与SNARK不同，STARK（Scalable Transparent Argument of Knowledge，即可扩透明知识论证）依赖于哈希函数，类似于工作证明区块链，可以更好地抵抗量子，从而保障应用STARK的协议。因此，STARK的证明规模更大，网络供电需求更高，且验证证明时间更长。

不同于SNARK和PLONK，STARK在程序创世阶段不需要受信私钥初始化。此外，STARK依赖于抗冲突哈希函数形式的更精简的加密技术，因而被认为是一种更有效的ZKPs。

由于社区较小，资料库或论坛等资源也不多，开发人员并不能轻松使用zk-STARK构建协议。尽管有几个项目创建了基于STARK的扩容方案，如Polygon的Miden和Starkware的Starknet，但SNARK社区还需要长时间的发展并增加可用资源。

ZK Rollup

首先，需要明确Rollup的概念。

Rollup最初出现的原因是以太坊的TPS有限，经常出现网络拥堵，GAS过高等问题。为了解决这个问题，当时许多链打着ETH Killer的旗号横空出世，也吸引了不少眼球。不过最后大家发现这些链要么是中心化程度高容易被单点攻击(Solana)，要么是生态太差无人使用(EOS)，而ETH仍然守着他的王座。

所以大家一致认为，扩容(Scaling)还得依靠着以太坊这颗大树。有人想着我能不能在一条GAS更低，TPS更高的链上进行交易，通过双向挂钩与以太坊的资产连接？这个是侧链(side chain)，但是侧链有自己的共识协议，不继承以太坊的安全性。还有人想着我能不能压缩交易之后发到以太坊来降低GAS费用，提升TPS？这个是Layer2，继承了以太坊的安全性。

Rollup是Layer2的一种方案，其他包括Channel以及Plasma，不过市场最终选择了Rollup作为主流的解决方案。

Rollup可以分为Optimistic Rollup和ZK Rollup。

举例而言，Layer1(ETH)和Layer2可以认为是分行和总行的关系。以太坊作为总行，开设分行(Layer2)，让它们去处理交易，最后每个分行给以太坊上传一个汇总表，交给以太坊检查存档。

Optimistic Rollup的概念比较像以太坊总行收到OP Rollup账单之后，把这些账单全都公示出来。如果在公示期内没有异议，这笔账单就被确认和存档了。 ZK Rollup的想法更多是通过数学进行压缩，原先30 页的账单可能会被压缩成只有一页，那么这个时候以太坊的验证工作也会变得非常少，并且验证存档工作都会变得比较轻松，同时也能保证一定的安全性。其实zk的核心就是在进行压缩，目前估计有30倍到 50倍的压缩水平线。

ZK Rollup存在两个角色，排序者(Sequencer)和证明者(Prover)。Sequencer在链下接受交易的提交，对交易进行排序和打包。Prover负责对交易记录进行合并压缩，形成零知识证明。这个证明会和 Layer1 以前的状态进行比较，进而更新以太坊的 Merkle Trie，计算新的状态树。

Optimistic Rollup当前已收到广泛应用，Optimism和Arbitrum主网被大量用户使用，Arbitrum One的交易数量已经超过了以太坊主网。

而技术难度较大的ZK Rollup，目前基本还在建设中，只有少数专用型ZK Rollup被广泛使用(如Stackware上的DYDX, IMX)。

ZK Rollup 的优缺点：

• 优点：费用低，不像 OP 会被经济攻击，不需要延迟交易，可以保护隐私，快速达成最终性

• 缺点：形成 ZK 证明需要大计算量，安全问题（SNARK 需要一个可信设置），不抗量子攻击（SNARK, STARK 可以），交易顺序可能被改变

目前市场上最有竞争力的 ZK rollup 项目有：Starkware 的 StarkNet，Matterlabs 的 zkSync 和 Aztec 的 Aztec connect，Polygon 的 Hermez 和 Miden，Loopring，Scroll 等。

基本上技术路线就在于 SNARK( 及其改进版本 ) 和 STARK 的选择，以及对 EVM 的支持（包括兼容还是等同）。

• Aztec 开发了通用化的 SNARK 协议 -Plonk 协议，运行中的 Aztec3 可能会支持 EVM，但是隐私优先于 EVM 兼容

• Starnet 用的是 zk-STARK，一种不需要可信设置的 zkp，但是目前不支持 EVM，有自己的编译器和开发语言

• zkSync 也是用的 plonk，支持 EVM。zkSync 2.0 是 EVM 兼容的，有自己的 zkEVM

• Scroll， 一种 EVM 兼容的 ZK rollup, 团队也是以太坊基金会 zkEVM 项目的重要贡献者

ZK-EVMs

ZK-EVMs是通用性的ZK Rollup解决方案，让Layer2与Layer1之间的摩擦更低，切换更流畅。ZK-EVM的核心使命是利用ZK-SNARK技术对类似以太坊的交易执行进行加密证明，无论是为了更容易地验证以太坊链本身，还是为了构建ZK-rollups，这些ZK-rollups（几乎）相当于以太坊提供的功能，但具有更高的可扩展性。

Vitalik将ZK-EVMs分为以下五类：

1. Type 1(fully Ethereum-equivalent)完美兼容以太坊，可以验证以太坊区块或者至少验证执行层。是对以太坊的扩容，而不仅是Rollup，且可以共享以太坊基础设施。但是需要很长时间来生成证明。Scroll的最终目标是该类型。

2. Type 2 (fully EVM-equivalent)对以太坊底层做了一些不涉及应用层的微小变动，把不适合ZK的哈希算法和区块大小等进行修改，减少了一些证明生成时间。由于EVM不涉及底层结构，所以EVM层面上感受不到变化，可以与几乎所有以太坊应用兼容，能共享大部分基础设施。Scroll的ZK-EVM和Polygon Hermez正在建设该阶段。

3. Type 2.5 (EVM-equivalent, except for gas costs)对EVM中某些操作的GAS进行修改，通过价格来降低人们对生成证明时间久的操作的使用，证明生成速度更快，但是会带来一定的不兼容性。Scroll的ZK-EVM和Polygon Hermez已经实现。

4. Type 3 (almost EVM-equivalent)对以太坊底层做了一些涉及应用层的微小变动，去除难以生成证明的特征，例如预编译、内存、栈等方面。兼容大部分应用，对于其他应用只需要很小的修改。

5. Type 4 (high-level-language equivalent)将由Solidity和Vyper等高级语言编写的应用编译成ZK友好的语言，生成证明非常快，但是不兼容性较高。如Starkware的Cairo语言。

总结

Vitalik官方声明ZK Rollup是Scaling的END GAME，ZK赛道上孕育着下一个万亿级机遇。最终ZK项目会演进至Type 1(fully Ethereum-equivalent)的形态，当下可以关注各大项目方的MileStone，多参与生态。尤其是在EIP-4844上线之后，ZK Rollup赛道会更具备吸引力。