# 由浅入深理解ZKP

By [CryptoScott](https://paragraph.com/@cryptoscott) · 2022-09-14

---

**作者： Research Dao | @RealResearchDAO**

**编译：@CryptoScott\_ETH 已获得原作者授权转载**

本文是对零知识证明领域相关资料的梳理以及行业应用的探讨，希望能给非技术出身的研究员提供 ZKP 研究的指引。企图帮助非技术出身的研究员由浅入深理解零知识证明。

从 Alice 和 Bob 的故事中体会 ZK
-----------------------

本章是对 [Aviv Zohar](https://medium.com/@avivzohar) 2017年发表的 [**The Incredible Machine**](https://medium.com/qed-it/the-incredible-machine-4d1270d7363a) 的概括，从故事的角度出发，帮助读者更直观得体会零知识证明的相关特性。

Alice 和 Bob 都是数独爱好者，有一天 Alice 向 Bob 说，“我设计了一个很难的数独，你要不要挑战一下？” Bob 接受挑战，但迟迟无法填满空格，便质疑 Alice 的题目是无解的。为了证明其题目有解且不暴露答案本身，Alice 想到了个办法。

*   承诺：Alice 拿出 81（9x9）张空白的卡片放在桌上，在每张纸上写上 1-9 中的一个数字，他让 Bob 转过身闭上眼，然后把这 81 张卡片按照解的排列放在桌上，代表谜底的卡片，数字面朝下放在桌上；代表谜面的卡片，则数字面朝上放在桌上。
    
*   随机实验：Bob 随意选择行，或者按照列，或者按照3x3的九宫格来检验解。接着把选中的9张卡片收起来单独放到一个麻布袋里。所有卡片都被收完放在了9个麻布袋里。Alice 接着摇了摇每个麻布袋，把里面的卡片顺序都打散。最后把这9个麻布袋交给 Bob。
    

![](https://storage.googleapis.com/papyrus_images/ea5f35823e355d963c2820f3f4752e710bbcc17dc259f6683583c8e11467f7f1.png)

*   验证：Bob 打开布袋，验证每个布袋是否都是 1～9 的数字卡片
    

![](https://storage.googleapis.com/papyrus_images/334666181ff273af07f6f6dbd5c543f311b15070241cf7f31156781fb5bee924.png)

*   重复：按照数独需要每一行每一列每个九宫格的数字都不会重复，只做一次随机实验，Alice 没说谎的概率只有 1/3，重复做几次实验，每次实验结果都是不会重复的数字，则可以证明 Alice 确实是知道这道题的解。
    
*   非交互式：Alice 和 Bob 挑选排列方式属于交互式，双方存在联合起来欺骗第三方的可能。于是Charlie 设计了一个机器来进行行列块的选择，以实现随机实验的非交互性。Alice 只要把卡片放在传送带上，机器会自动选择按行，或列，或九宫格来收取卡片，放到袋子里打乱顺序，然后把袋子通过传送带再送出来。
    

![](https://storage.googleapis.com/papyrus_images/f27e1b934d502bb7a966018f004269efef6e19bb4a0ca00bb4412bb2a8fad61b.png)

![](https://storage.googleapis.com/papyrus_images/8f98199f4a365c415caba69a082e9bc21bf104487c034416a902206b68d06dbe.png)

*   初始化设置：行列块的抽取顺序是 Charlie 设置的，因此这台机器没法验证他是否能解数独，其他人也可以通过贿赂 Charlie 知道抽取顺序。于是 Alice 提议让 Charlie 把控制面板重新打开，多方（multi-party）共同设置控制面板上的试验序列。这个过程称为“可信任的初始设置仪式（trusted setup ceremony）。把机器放在一个黑暗的房间里，第一个人进房间后拨动拨盘到任意随机的位置，第二个人和第三个人按照第一个人随机选中的顺序分别往下加一格和两格，用这样的方式，保证每一个拨盘都不会被其中任何人知道。这个设置仪式完成之后，他们就焊接好机器控制面板。
    

这样的机器，就可以实现 ZK 的三个特性：

*   完整性 —— 只要「陈述」是正确的，证明者(_prover)_ 就可以让验证者(_verifier)_ 确信
    
*   可靠性 —— 如果「陈述」是错误的，那么作弊的 _prover_ 就没有办法让 _verifier_ 相信
    
*   零知识 —— 协议的交互仅仅揭露「陈述」是否正确而不泄漏除公共信息外的其它的信息
    

从数学中体会 ZKP
----------

本章是对 ZK-SNARK（主流的 ZKP）的数学证明过程，主要参考 [Vitalik Buterin](https://medium.com/@VitalikButerin?source=post_page-----f6d558cea649--------------------------------) 2016 年发表的 [Quadratic Arithmetic Programs: from Zero to Hero](https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649) ，从数学的角度出发，帮助读者进一步理解零知识证明的实现过程。

### 预备知识

*   复杂度
    
    *   当问题规模扩大后，程序需要的时间长度增长得有多快。
        
    *   数据有多大，程序处理花的时间始终是那么多的，我们就说这个程序很好，具有O(1)的时间复杂度，也称常数级复杂度；
        
    *   数据规模变得有多大，花的时间也跟着变得有多长，这个程序的时间复杂度就是O(n)。
        
    *   O(1),O(log(n)),O(n^c)等，我们把它叫做多项式级的复杂度。
        
    *   O(c^n)和O(n!)型复杂度，它是非多项式级的，其复杂度计算机往往不能承受。
        
    *   当我们在解决一个问题时，我们选择的算法通常都需要是多项式级的复杂度，非多项式级的复杂度需要的时间太多，往往会超时，除非是数据规模非常小。
        

![](https://storage.googleapis.com/papyrus_images/816553b3569b5626598044967f37549078b8b42386334a845775045bc11d50f3.png)

*   P 问题 与 NP 问题
    
    *   P 问题：多项式时间内可解的问题，如
        
        *   已知私钥 sk 和椭圆曲线生成元 G，可快速计算出公钥 pk = sk \* G
            
        *   已知原象 x 和哈希函数 SHA256，可快速计算出哈希值 Y = SHA256(x)
            
    *   NP 问题：不能在多项式时间内可解（求解困难），但是可以在多项式时间内验证的问题（验证简单），如：
        
        *   已知公钥 pk 和椭圆曲线生成元 G，不可在多项式时间内计算出私钥sk使得 pk = sk\*G
            
        *   以知哈希值 Y 和哈希函数 SHA256， 不可在多项式时间内计算出原象 x 使得 Y = SHA256(x)
            
*   多项式
    
    *   多项式有一个非常好的特性，就是如果我们有两个阶为 d 的不相等多项式，他们相交的点数不会超过 d。我们不可能找到两条不同的曲线，他们会在某段区域内重合（他们只会相交于一些点）。
        
    *   如检查两个长度为 1000 的向量（prover提供的信息与正确的信息）是否相等，一定要检查1000次，而两个 1000 次的多项式，最多只有1000个点相同，在一个很大的取值范围，如 1 到 1 亿，两个不同多项式在同一点上相同的概率只有一百万分之一。检查两个多项式是否相等比检查同等规模的两个向量是否相等要快得多。
        
    *   (Ax, s) \* (Bx, s) - (Cx, s) 为二次算法多项式，简称 QAP 多项式（Ax、Bx、Cx为 d 阶多项式，s 为 d 阶向量，QAP为 2d 阶多项式）。a1,a2,…,an 是 QAP 多项式等于 0 的解，令Z(x)=(x-a1)_(x-a2)_…\*(x-an)，则QAP多项式可以被Z(x)整除。
        
    *   若不知道向量s，需要指数时间暴力搜索出向量s，使得构建的QAP多项式能整除Z(x)，若已知s，则可快速验证QAP多项式是否与Z(x)满足整除关系。
        
    *   QAP 多项式的整除关系，构成 NP 问题。
        
*   算术电路
    
    *   在用电路写程序方面，已经算是比较成熟了，例如 CPU 以及各种芯片、嵌入式设备、ASIC 矿机等都是电路设计。同时，电路的结构又足够简单，不至于给构造 ZKP 带来太多麻烦。只不过ZKP常用的是算术电路（左图），硬件中常见的是布尔电路（右图）。
        
    *   多项式时间运算关系的代码，都可以用算术电路来表示。算数电路由加法门和乘法门构成。
        
    *   连续光滑的函数能通过泰勒展开无限逼近，泰勒展开由加减法和幂构成，幂函数由乘法构成。AND 和 XOR 等位运算非光滑，较难用加法乘法表示。
        

![](https://storage.googleapis.com/papyrus_images/2f9b76be9416b9531b9023af160aa3e3116ea363a760f091c631afe8d9ad1f74.png)

*   线性代数基础知识
    
    *   向量内积运算
        

![](https://storage.googleapis.com/papyrus_images/a674c0b96d0fc4fdd611a748d0dcf8136251467fc25d98bbefbf4e49e549a7a6.png)

*   矩阵乘法运算
    

![](https://storage.googleapis.com/papyrus_images/bf5a2211edfe1c368f38956438f1158ac1140fd1900329e674372ceb740fbbbb.png)

*   拉格朗日插值法
    
    *   利用拉个郎日插值法可将点转化为多项式
        
    *   如求经过 (1, 3)、(2, 2)、(3, 4)的二阶多项式 f(x) 有且只有一个，求f(x)
        

![](https://storage.googleapis.com/papyrus_images/46816ce70ca6344fc1118d1dc76befbfc0df797e6af8c53dfd70a3c86cf168ff.png)

*   如左图所示，若已知输入，验证人（Verifier）想要验证证明人（Prover）给的结果是否正确，可通过计算术电路中每一个节点的值最终得出结果与输出进行对比，但此过程无法达到简洁性，也即证明人和验证人为了得出结论所使用的计算时间是相同的，因此可以将运算过程中的值作为未知变量，通过零知识证明来进行验证，以此达到验证过程的简洁性；如右图所示，证明人为了保持部分输入的隐私性，可通过零知识证明技术让验证人相信证明人是知道正确的解。
    

![](https://storage.googleapis.com/papyrus_images/8f3d033f4de99b67ebec2e6f2e33cd0a5e588cad055caba8bc87facd0b5c4df9.png)

*   验证者(Verifier)已知的信息为Statement（如下图绿色所示），证明者(Prover)知道的知识而验证者不知道的信息为Witness（如下图蓝色所示）。
    

![](https://storage.googleapis.com/papyrus_images/81abf52973418963377847aa21b3ea90d42db499892bc737e8c7f5f7e0ea1531.png)

### 数学证明过程

1.  为了实现简洁性或零知识性,需要把算法转换成NP问题（验证简单，求解困难）
    
2.  验证者知道的答案与正确答案包含的信息数据可以用向量来表示，判断两个向量是否相等需要进行向量长度的运算，例如判断两个长度为 100 的向量是否相等，需要进行 100 次对比后才能得出结论。没有达到简洁性和零知识性。
    
3.  判断两个多项式是否相等比判断两个向量是否相等更容易，因为两个不同的 n 阶多项式至多相较于n个点，只要把范围取得足够大，则碰撞出两个函数相交的点概率极低，是不可能事件。例如两个不相同的 100 阶多项式函数，至多只有 100 个相同的点，若把 x 的取值范围定在\[-1,000,000, 1,000,000\]，随机取 1 个点使得两个多项式相交的概率为100/2,000,000=1/20,000 , 若均匀取两个点使得两个多项式相交的概率为(1/20,000)\*(1/20,000)，为不可能事件。
    
4.  将验证两个向量是否相等的问题转化为验证两个多项式是否相等，可以将计算的复杂度大大降低。SNARK将向量对比问题转换为 QAP 多项式整除目标多项式这一天然的NP问题作为验证方式。
    
5.  为了构建 QAP 多项式，需要将程序转化为算术电路，构建 R1CS。
    
6.  SNARK证明过程：程序转化为多项式时间运算关系-> R1CS -> QAP -> QAP 整除关系 -> 椭圆曲线离散对数。
    

![](https://storage.googleapis.com/papyrus_images/160337b7bb4791430f0d89314c0dc23efc9ea7765bcfd8c7ae7ad2c31df802bb.png)

ZK - SNARK 与 ZK - STARK
-----------------------

目前主流的 ZKP 有 zkSNARK 和 zkSTARK。SNARK、STARK、ZKP都属证明系统，SNARK与ZKP相交的地方称为 zkSNARK, SNARK与ZKP相交的地方称为 zkSTARK。

![](https://storage.googleapis.com/papyrus_images/3f57d2079f24a904023b8dcf0d2534b9eef344152fdbf9a810746fbc3bb12ffb.png)

### SNARK 与 STARK 含义

*   SNARK
    
    *   S：简洁性 (Succinctness)。Prover 和 Verifier 执行这个证明系统，比 Prover 直接把 w 发送给 Verifier，还要节省通信带宽。\*\*有时候，简洁性还可能要求 Verifier 在证明系统中的计算量要低于验证 w。总之，简洁性要求证明系统在效率方面有优势。
        
    *   N：非交互性 (Non-Interactivity) 是指证明系统的全部交互只有 Prover 向 Verifier 发送的一条消息，这个消息叫做一个证明。非交互性可以带来许多的便利，为证明系统带来更多的应用场景。例如，在区块链系统中，\*\*非交互性的零知识证明可以附在交易中，供任何人随时查验，而不需要交易的作者随时在线与验证者交互。\*\*任何 NP 语言都天然具有一个非交互证明协议，也就是 Prover 直接将证据发送给 Verifier，而且这个证明是知识证明。
        
    *   ARK：知识论证(Argument of Knowledge)。 如果要求 Prover 必须“知道”一些信息才能让 Verifier 验证通过，这个系统就被称为知识证明 (Proof of Knowledge)。知识证明可以看做可靠性的加强版。知识证明在计算意义下的版本，叫做知识论证 (Argument of Knowledge)。
        
*   STARK
    
    *   S：扩展性 (Scalability)，它在简洁性的基础上还要求 Prover 复杂度至多是拟线性 (Quasi-linear) 的，即 O(n log n)。证明时间与证明内容的复杂性呈拟线性关系，而验证时间则与其呈多对数关系，因此，当证明内容的复杂性显著增加时，尽管链下证明的耗时也拟线性增长，链上验证的耗时却增加不大。
        
    *   T：透明性 (Transparent)，STARK 不需要可信第三方 Setup。
        
    *   ARK：知识论证(Argument of Knowledge)。
        

### SNARK 与 STARK 异同

STARK和 SNARK 只有一字之差，但有很多不同。下面我们比较一下这两个概念。

共同点：

*   都是知识论证 (ARK)，即只有计算意义下的可靠性，且证明是知识性的
    

区别：

*   SNARK 的 “S” 是简洁性 (Succintness)，而 STARK 的 “S” 是**可扩展性 (Scalability)**，它在简洁性的基础上还要求 Prover 复杂度至多是拟线性 (Quasi-linear) 的，即 O(n log n)。
    
*   透明性 (Transparent)：STARK 不需要可信第三方 Setup，因此是抗量子计算的。
    
*   非交互性 (Non-Interactivity)：SNARK 一定是非交互的，而 STARK 没有这个限制。可以看出，SNARK 比 STARK 唯一多出的限制就是非交互性。尽管如此，STARK 一般都可以转化为非交互证明，转化的结果必然是一个 SNARK。在这种意义上，可以把 STARK 看做 SNARK 的子集。
    
*   目前大多数的 zkSNARK 是基于电路模型的，STARK 是基于RAM 模型的，RAM 模型的构造极其复杂。
    
*   zk-STARKs 生成的加密证明的尺寸要大得多。此外，以太坊有针对特定 zk-SNARK 的预编译，因此，验证 zk-SNARK 加密证明的 gas 成本要低于 zk-STARK。
    

![](https://storage.googleapis.com/papyrus_images/e0e0a86e4201fd3fec3756838ea60ac2a72b6297202fd49ed20d650ec2741290.png)

ZKP Applications
----------------

ZKP 主要应用于扩容和隐私两个方向，而隐私方向又包括了建立在 Layer1 或 Layer2 上的隐私应用和隐私公链。在 Defi 还没爆发之前，ZK 主要应用于隐私方向，Defi 爆发后，Gas 费高涨是以太坊被大规模使用的最大障碍。因此大家开始把目光转移到 Layer2 扩容中，而 Layer2 方案中，zk- Rollup 在安全性和节省 Gas 费方面都有最佳的表现。

### Layer 2 扩容

讨论 Layer2 扩容方案之前，我们先来大致了解一下 以太坊的 Gas 构成。

以太坊上 gas 费的计算方式为燃料单价 (gasPrice) \* 燃料开销 (gasUsed)。

*   燃料单价 (gasPrice) 是一种报价方式，可以自己选择报价高低，燃料单价 (gasPrice) 的高低跟交易速度有关。燃料单价 (gasPrice) 跟交易的优先性呈现正相关关系，当同样复杂程度的交易需求，更高的燃料单价 (gasPrice)，矿工会更倾向优先处理，交易速度就更快。
    
*   燃料开销 (gasUsed) 跟交易的复杂程度呈现正相关关系，交易的复杂程度越高，燃料开销 (gasUsed) 就越高；反之，则越低。比如你分别进行转账操作和杠杆操作，通常来说前者的开销会低于后者，因为杠杆操作更加复杂。
    

Rollup 是将主网上需要计算的交易转移到了链下去，然后再将计算好的结果反馈给主网，以此来降低交易的复杂程度从而降低 gas 费用；而 ETH2.0 的解决方案是降低主网的 gas 燃料单价，从而降低 gas 费用。

Layer 2 扩容方案可按照数据存储方式和证明系统进行划分，具体划分方式如下图所示。目前主流的方案是 Optimistic Rollup 和 ZK Rollup。

![](https://storage.googleapis.com/papyrus_images/5094a6296a6a6caabf3ef8a19b2762d18fe752986502037f352523b99a84d610.png)

*   **Optimistic Rollup**
    
    *   交互式欺诈证明的方式来进行安全性的保障，即当 Layer 2 的计算结果返还 Layer 1 的时候，当验证者认为这个结果可能存在欺诈的行为时，验证者发起挑战，然后主链冻结资产，进行交易数据和记录验证，最后证明其是真实的交易还是欺诈的交易。当没有验证者怀疑这个结果的时候，主链默认这些结果都是真实的。
        
    *   优点：兼容性好；
        
    *   缺点：安全性低（没有从根本保障资产的控制权问题，即资产的安全性受到了威胁）；资产会被冻结；退出周期长。
        
*   **ZK Rollup**
    
    *   将大量交易打包到一个 Rollup 区块内，并在链下为该区块生成一个简洁证明。随后，Layer 1 上的智能合约只需验证该证明即可直接应用新的状态，无需重新执行这些交易。这样就可以节约一个数量级的 gas 费，因为证明的验证成本远低于重新执行的计算成本。另一个好处是可以通过数据压缩来节省存储空间（即，仅在链上存储最少量的数据用于验证）。
        
    *   优点：安全性高，退出周期短，Gas费低
        
    *   缺点：兼容性差
        

### 隐私

**隐私应用**

*   **Tornado.Cash**
    

以太坊上的交易纪录都是公开的，你可以在 etherscan 上看到某个地址的所有历史交易纪录，并且知道每个地址的资产余额。传统金融支付中，人们往往不愿意让别人知道自己账户里面有多少钱，也不愿意让随意一个人都能查询到自己的流水记录，利用 ZK 技术能很好得解决此问题。

Tornado.Cash 作为以太坊网络上最火的去中心化隐私解决方案，使用zk-SNARKs技术，打破了存款人和取款人地址之间的链上链接，做到了交易机密性，保护了用户隐私，实现了匿名的代币交易。简单来说，它是一份合约，当你要匿名传送代币时，就把一定数量的币丢进合约里(Deposit)，此时你会拿到一个note，note 就是一串字串，拥有这字串的人，就能提领(Withdraw) 刚刚传入合约的代币。握有note 就代表拥有提款的权利，所以note 一旦被别人知道，别人就可以把钱给提走。

*   **Dark Forest**
    

目前的 Gamefi 基本上只有资产上链，游戏的资产价值又很大程度依赖于游戏本身，中心化运行的游戏关闭之后，上链的资产价值也不复存在，因此仅仅是资产上链并不够去中心化。而将整个游戏部署在区块链上的游戏才能称为 Decentralized Game。

Dark Forest是一款实时策略游戏，也是第一款全链游戏，在Gnosis 链上运行。星球的移动和攻占是整个游戏的策略重点。既然是移动攻击，每个星球有一个坐标。为了增加游戏的策略体验，星球的具体坐标并不公开。有点像在浩瀚的宇宙中，只能观察（枚举）周围有限空间（hash碰撞）寻找其他星球。为了在不公开星球坐标的情况，还能证明星球的移动正确，引入了零知识证明技术。

**隐私公链**

*   **Zcash**
    

Zcash 诞生于 2011 年 11 月 9 日，全称 Zero Cash，简称 ZEC。 Zcash 的大部分代码与比特币极其相似，总量都是 2100 万枚，但它进一步完善了比特币匿名功能方面的不足。Zcash 是首个使用 Zk-SNARK 零知识证明机制的区块链系统，目的是彻底解决交易被追踪从而暴露用户隐私的问题。Zcash 交易自动隐藏区块链上所有交易的发送者、接收者及数额。只有拥有查看密钥的人才能看到交易的内容。 用户拥有完全的控制权，他们可自行选择向其他人提供查看密钥。目前，Zcash 交易分为两类：透明地址（「t」开头）和隐藏地址（「z」开头）。如果用户希望验证隐藏地址的详细信息，必须与相关方共享特殊的访问密钥。用户也可「选择性披露」，它还带有一个加密的备忘录字段，允许机构安全地将敏感数据附加到交易中，并使这些信息对授权方可见。

*   **Mina**
    

Mina是一个轻量级的公链，通过递归零知识证明，将区块链大小维持在22 KB左右，这允许节点以低门槛的硬件条件参与，哪怕是运算能力相对较弱的移动端，类似手机、平板电脑等，也可以去同步验证Mina网络，更低的节点门槛，节点也更具分布式，并且围绕着零知识证明搭建了一个可保护数据隐私的生态系统。

递归零知识证明指：在每次区块生产时，利用zk-SNARK技术将区块压缩为单个证明，并且每个新的SNARK证明都包含过去的SNARK证明，节点只需检测该证明即可，以此不需要检测整个交易历史记录，同时这些证明可以进行递归组合，以实现区块的大小恒定。

*   **Iron Fish**
    

Iron Fish 致力于为每笔交易提供强大的隐私保证。包括交易信息、挖矿信息、钱包信息全都处于隐藏，除了私钥所有者以外，任何第二方都无法查看。为实现这一目标，Iron Fish 构建了一个全新的 PoW 网络，使用 zk-SNARKs 以及 Sapling 协议来为每一笔链上交易提供最高层级的隐私保护。 Iron Fish 的一大亮点在于，该网络希望在保护隐私的同时也不去损害链上交易的可访问性，为此，Iron Fish 为每个链上地址额外配备了一个查看密钥（view key），地址持有者可通过该密钥授予其他人只读权限。

在路线上，Iron Fish 表示，未来网络层将支持 WebRTC 与 WebSockets，这意味着可通过浏览器直接运行完整的 Iron Fish 节点。 当前，Iron Fish 仍处于测试网阶段，并已启动激励计划，活跃参与者可以通过各种贡献获取相应积分，这些积分将在未来主网发布时兑换成主网代币。

*   **Aleo**
    

Aleo致力于构建模块化且合规的零知识隐私应用平台，用于构建私有应用的最终工具包。其利用去中心化系统、零知识加密技术，保护 Web 上的用户数据以实现这⼀目标。

Aleo Studio Aleo Studio是第⼀个用于编写零知识应用程序的 IDE。

专为正式验证的零知识应用程序设计的新编程语言。Leo 提供了⼀个不受运行时间、堆栈大小或指令集限制的强大执行环境。

PoSW 是比特币基于 SHA 的难度调整算法的变体，主要区别在于底层计算不是任意的哈希函数，而是知识证明。这使得 PoSW 解决方案不仅可以充当 PoW 以确保系统共识，还可以验证给定区块中的交易包含。

兼容性 - ZK EVM
------------

以太坊虚拟机 (EVM) 是基于区块链的开源软件，允许开发者创建去中心化的应用。它是全球虚拟计算机，记录以太坊网络存储和达成共识的每个智能合约的状态，Solidity 是其编程语言。EVM是第一个为开发者提供智能合约功能的软件，并且已经成长为一个蓬勃发展的生态系统，其极具价值的开发者网络效应超越了以太坊区块链本身。

如果某个协议的智能合约可以在 EVM 上执行，那么该协议就是与 EVM 兼容的，这意味着该协议的合约必须要么用 Solidity 编写，要么能够将其合约代码编译成可以在 EVM 上运行的字节码。新公链或 Layer2 想要快速扩充其生态，EVM 兼容是必不可少的，可以将以太坊上原有的用Solidity编写的应用快速部署到自己的链上。而Solidity语言有很多ZK-Unfriendly的语法，使得 ZK-EVM 的实现面临很大的挑战，哪个协议能实现更好的EVM兼容性，将更快达到网络效应。

*   Solidity源码 → 编译器 → EVM可执行的字节码 → EVM → EVM解释器 → 机器可执行的二进制文件→程序运行。
    
*   Solidity源码 → 编译器 → zkEVM可执行的字节码 → zkEVM → zkEVM解释器 → 机器可执行的二进制文件→程序运行。
    
*   非 Solidity 源码 → 编译器 → EVM可执行的字节码 → EVM → EVM解释器 → 机器可执行的二进制文件→程序运行。
    

下文是对 Vitalik 2022 年发表的 [The different types of ZK-EVMs](https://vitalik.ca/general/2022/08/04/zkevm.html) 以及 Ye Zhang 2022 年发表的[zkEVM](https://hackmd.io/@yezhang/S1_KMMbGt) 的概括与总结，从 ZK- EVM的分类和技术演变的角度出发，帮助读者更好得了解ZK-EVM的发展现状。

### 设计挑战

*   第一，EVM 对椭圆曲线的支持有限。目前，EVM 只支持 BN254 配对。由于不直接支持循环椭圆曲线，EVM 很难实现证明递归。在这种设置下，我们也很难使用其它专用协议。验证算法必须是 EVM 友好型的。
    
*   第二，EVM 的 word 大小是 256 位。EVM 基于 256 位整数运行（就像大多数基于 32～64 位整数运行的普通虚拟机那样），零知识证明则 “天然” 基于素域运行。在电路中进行 “错配域算术” 需要范围证明，进而给每个 EVM 操作增加大约 100 个约束。这会将 EVM 电路大小增加两个数量级。
    
*   第三，EVM 有许多特殊的操作码。不同于传统虚拟机，EVM 有很多特殊的操作码，如 `CALL` ，以及与执行环境和 gas 相关的错误类型。这会给电路设计带来新的挑战。
    
*   第四，EVM 是基于堆栈的虚拟机。SyncVM（zksync）和 Cario（starkware）架构在基于寄存器的模型中定义自己的 IR/AIR。它们构建了一个专门的编译器来将智能合约代码编译成一个新的零知识证明友好型 IR。该方法是语言兼容的，而非原生 EVM 兼容的。无论是证明基于堆栈的模型，还是直接支持原生工具链，都会变得更加困难。
    
*   第五，以太坊存储布局带来了高昂的成本。以太坊存储布局高度依赖 Keccak 和一个巨型 MPT4。二者都不是零知识证明友好型的，而且会产生高昂的证明成本。例如，Keccak 哈希的电路大小是 Poseidon 哈希的 1000 倍。但是，如果你将 Keccak 哈希替换成另一种哈希，就会给现有的以太坊基础设施带来一些兼容问题。
    
*   第六，基于机器的证明带来了高昂的成本。即使你可以妥善处理上述所有问题，你依然需要找到一种有效的方法来将它们组合起来得到一个完整的 EVM 电路。正如我在上一节中提到的，即使像 `add` 这样简单的操作码也有可能需要你负担整个 EVM 电路的成本。
    

### 分类

![](https://storage.googleapis.com/papyrus_images/e258da20b33555857fc54f607c8f60ca7a00dd9b2851fb8c9e2b9bdcdad9b135.png)

*   **Type 1（完全等效于以太坊）**
    

力求完全且毫不妥协地与以太坊等效。不改变以太坊系统的任何部分来生成证明。

优点：完美兼容， 这类 ZK-EVM 是我们最需要的，使以太坊第 1 层本身更具可扩展性，也是 rollup 的理想选择，因为它允许 rollup 能使用大量的基础设施。（可以使共识层面也用 ZK 来实现）

缺点：证明时间长。 以太坊最初并不是围绕 ZK 友好性设计的，因此以太坊协议的许多部分需要大量计算才能进行 ZK 证明。类型 1 旨在精确复制以太坊，因此它无法缓解这些低效率。

Builders：[privacy-scaling-explorations](https://github.com/privacy-scaling-explorations/zkevm-circuits)

*   **Type 2（完全等效于 EVM）**
    

类型 2 ZK-EVM 力求完全等同于 EVM，但不完全等同于以太坊。也就是说，它们「从内部」看起来与以太坊完全一样，但它们在外部存在一些差异，特别是在块结构和状态树等数据结构上。

优点：VM 级别的完美等价，你将无法按原样使用以太坊执行客户端，但你可以通过一些修改来使用它们，并且您仍然可以使用 EVM 调试工具和大多数其他开发人员基础设施。

缺点：有改进但仍然需要提供比类型 1 更快的证明时间，主要是通过删除依赖于不必要的复杂和 ZK 不友好密码学的部分以太坊堆栈，但它们并不能解决所有问题。

Builders：Scroll 的 ZK-EVM 项目正朝着 Type 2 ZK-EVM 方向发展，Polygon Hermez 也是如此。也就是说，这两个项目都还没有完成。特别是，许多更复杂的预编译还没有实现。因此，目前这两个项目都被更好地考虑为 Type 3。

*   **Type 2.5 （EVM 等效，gas 成本除外）**
    

显著改善最坏情况证明者时间的一种方法是大大增加 EVM 中很难进行 ZK 证明的特定操作的 gas 成本，更改 gas 成本可能会降低开发人员工具的兼容性并破坏一些应用程序，但通常认为它的风险低于「更深入」的 EVM 更改。

优点：加快证明时间

缺点：产生部分不相容

*   **Type 3（几乎等效于 EVM）**
    

类型 3 ZK-EVM 几乎与 EVM 等效，但在精确等效性方面做出了一些牺牲，以更进一步缩短验证时间并使 EVM 更易于开发，可能会删除一些在 ZK-EVM 实现中极难实现的功能。

优点：更容易构建，更快的验证时间

缺点：更多的不兼容 这类 ZK-EVM 的目标是与大多数应用程序兼容，并且只需要对其余部分进行最少的重写。也就是说，将有一些应用程序需要重写。

Builders：Scroll 和 Polygon 在其当前形式中都是 Type 3，尽管它们有望随着时间的推移提高兼容性。Polygon 使用了一些不同的内部逻辑来完成它。Type 3 只是一个过渡阶段，直到完成添加预编译的复杂工作并且项目可以移动到 Type 2.5。

*   **Type 4（高级语言等效）**
    

类型 4 通过获取以高级语言（例如 Solidity、Vyper 或两者都可以编译的中间语言）编写的智能合约源代码并将其编译为明确设计为 ZK-SNARK 友好的某种语言来工作.

优点：非常快的验证时间 通过不对每个 EVM 执行步骤的所有不同部分进行 ZK 证明，并直接从更高级别的代码开始，您可以避免很多开销。

缺点：更多的不兼容

Builders：ZKSync 是一个 Type 4 系统，尽管随着时间的推移它可能会增加对 EVM 字节码的兼容性。Nethermind 的 Warp 项目正在构建一个从 Solidity 到 Starkware 的 Cairo 的编译器，这将把 StarkNet 变成事实上的 Type 4 系统。

![](https://storage.googleapis.com/papyrus_images/6e41fe7f2f9fed9b0af11a4cf593b1f32851b9c217d1bb6d2693cd1d6fddb9be.png)

ZK-EVM 类型的未来分出这些类型并不是要比较「更好」或「更差」。相反，它们是权衡空间上不同的点：编号较小的类型与现有基础架构的兼容性更高，但速度较慢，编号较高的类型与现有基础架构的兼容性较差，但速度更快。

可以看到，为了实现更好的兼容性，不仅仅ZK项目方需要努力，还需要以太坊自身的改进以及硬件的发展。

### ZK EVM 实现的可能性

*   多项式承诺（polynomial commitment）的使用。过去几年来，大多数简洁零知识证明协议都使用 R1CS，PCP 查询被编码到了特定于应用的受信任起步设置（trusted setup）中。这往往会增加电路的大小，导致很多自定义优化都无法实现，因为每个约束的度必须是 2（双线性配对（bilinear pairing）只允许进行一次指数乘法计算）。有了多项式承诺方案，你可以通过通用设置（universal setup）乃至透明设置（transparent setup）将你的约束提高到任何阶，大幅提高了后端选择的灵活性。
    
*   查找表参数和自定义小工具的出现。另一个重要优化是查找表的使用。这个优化首次提议于 Arya，然后在 Plookup 中得到实现。对于零知识证明不友好型原语（即，AND 和 XOR 等位运算）来说，查找表可以省很多事。自定义小工具可以高效实现高阶的约束。TurboPlonk 和 UltraPlonk 定义了优雅的程序语法，降低了使用查找表和定义自定义小工具的难度。这对于降低 EVM 电路的成本帮助很大。
    
*   递归证明的可行性越来越高。过去，递归证明会带来很高的成本，因为它依赖特殊的配对友好型循环椭圆曲线（即，基于 MNT 曲线的结构）。这会产生很高的计算成本。然而，越来越多技术能够在不牺牲效率的情况下使得递归证明成为可能。例如，Halo 无需配对友好型曲线，还可以使用特殊的内积参数来摊销递归成本。Aztec 证明了可以直接聚合现有协议的证明（查找表可以减少非原生域运算的成本，从而缩小验证电路的体积）。同样的电路规模现在能够实现更多的功能。
    
*   硬件加速正在提高证明效率。据我们了解，我们已经为证明程序打造了最快的 GPU 和 ASIC/FPGA 加速器。我们关于 ASIC 证明程序的论文已于今年被顶级计算机学术会议 ISCA 接受了。我们的 GPU 证明器比 Filecoin 的实现快了大约 5 至 10 倍，可大幅提高证明器的计算效率。
    

总结
--

在 DeFi 爆发之前，ZKP 主要用于隐私方向。 DeFi爆发后，高昂的gas费用是以太坊大规模使用的最大障碍。于是大家开始将目光转向Layer2扩容，而Layer2方案中，zk-Rollup在安全性和节省gas成本方面表现最好。阻碍zk-Rollup大规模爆发的原因是由于其兼容性差，需要修改很多Layer 1协议来部署zk-Rollup。随着 zk-EVM 的发展，这个问题将得到解决。 ZK-Rollup 和 ETH 的结合在保证安全性的同时大大降低了 Gas 费用，进一步阻碍了 Alt Layer1 的发展。届时，以太坊将进一步实现其成为全球结算层的愿景。

原文标题：《Zero-Knowledge Proof: from Zero to Hero》

原文链接：[Zero-Knowledge Proof: from Zero to Hero](https://mirror.xyz/0xed111Cf8C23AEafe12286Fd60EE670007457Bf87/7JYEKachwX_ZHalD4oHNt5Ik2lemjeQU44_yt-fLdls)

**ResearchDAO Twitter:** [https://twitter.com/RealResearchDAO](https://twitter.com/RealResearchDAO%EF%BC%8C)

ResearchDAO 最近正在招募合作者，感兴趣的可以提交至：

[https://docs.google.com/forms/d/e/1FAIpQLSel53Un2E3WrVPCm5Niq3GpHjaYuZ7LdyJECdx-9qUWMpY-FA/viewform](https://docs.google.com/forms/d/e/1FAIpQLSel53Un2E3WrVPCm5Niq3GpHjaYuZ7LdyJECdx-9qUWMpY-FA/viewform)

---

*Originally published on [CryptoScott](https://paragraph.com/@cryptoscott/zkp)*