HashKey ZK 101 第一期：历史原理与行业

HashKey Capital ｜2022-08-11 15:28

当前区块链行业里零知识证明项目（ZKP）增速惊人，HashKey Capital 研究团队希望通过几篇报告的形式共同学习。本篇是该系列的第一篇，主要介绍ZKP的发展历史、应用和一些基本原理。

前言：当前区块链行业里零知识证明项目（ZKP）增速惊人，特别是ZKP在扩容和隐私保护两个层面应用的崛起，令我们接触到了各种花样繁多的零知识证明项目。由于ZKP极富数学性的特质，对于加密爱好者来说，想要深度了解ZK的难度大幅提升。因此我们也希望从头梳理ZKP理论和应用层面的一些变化，与读者一起探索对于crypto行业的影响和价值——通过几篇报告的形式共同学习，也作为HashKey Capital 研究团队的思考总结。本篇是该系列的第一篇，主要介绍ZKP的发展历史、应用和一些基本原理。

一、零知识证明的历史

现代零知识证明体系最早来源于Goldwasser、Micali 和Rackoff合作发表的论文：The Knowledge Complexity of Interactive Proof Systems（即GMR85），该论文提出于1985年，发表于1989年。这篇论文主要阐释的是在一个交互系统中，经过K轮交互，需要多少知识被交换，从而证明一个证言（statement）是正确的。如果可以让交换的知识为零，则被称之为零知识证明。这里面会假设证明者（prover）具有无限资源，而验证者（verifer）只具有有限资源。而交互式系统的问题在于证明不完全是数学上可证的，而是概率意义上正确的，虽然概率很小(1/2^n)。

所以交互式系统并不完美，只有近似完备性，以此为基础诞生的非交互式系统（NP）系统则具有完备性，成为零知识证明系统的完美所选。

早年的零知识证明系统在效率以及可用性方面都有所欠缺，所以一直都停留在理论层面，直到最近10年才开始蓬勃发展，伴随着密码学在crypto成为显学，零知识证明走向台前，成为至关重要的一个方向。特别是发展出一个通用的、非交互的、证明大小有限的零知识证明协议，是其中最关键的探索方向之一。

基本上零知识证明就是要在证明的速度、验证的速度和证明体积的大小之间做取舍，理想的协议是证明快、验证快、证明体积小。

零知识证明最重要的突破是Groth在2010年的论文Short Pairing-based Non-interactive Zero-Knowledge Arguments，是ZKP里面最重要的一组zk-SNARK的理论先驱。

零知识证明在应用上最重要的进展就是2015年Z-cash使用的零知识证明系统，实现了对交易及金额隐私的保护，后来发展到zk-SNARK和智能合约相结合，zk-SNARK进入了更为广泛的应用场景。

在此期间，一些重要的学术成果包括：

2013 年的Pinocchio (PGHR13)：Pinocchio: Nearly Practical Verifiable Computation，将证明和验证时间压缩到适用范围，也是Zcash使用的基础协议。

2016 年的Groth16：On the Size of Pairing-based Non-interactive Arguments，精简了证明的大小，并提升了验证效率，是目前应用最多的ZK基础算法。

2017 年的Bulletproofs (BBBPWM17)Bulletproofs: Short Proofs for Confidential Transactions and More，提出了Bulletproof算法，非常短的非交互式零知识证明，不需要可信的设置，6个月以后应用于Monero，是非常快的理论到应用的结合。

2018 年的zk-STARKs (BBHR18)Scalable, transparent, and post-quantum secure computational integrity，提出了不需要可信设置的ZK-STARK算法协议，这也是目前ZK发展另一个让人瞩目的方向，也以此为基础诞生了StarkWare这个最重量级的ZK项目。

其他的发展包括PLONK、Halo2等也是极为重要的进展，也对zk-SNARK做出了某些层面上的改进。

二、零知识证明的应用简述

零知识证明最广泛的两个应用就是隐私保护和扩容。早期随着隐私交易和几个有名的项目Zcash和Monero等推出，隐私交易一度成为非常重要的门类，但由于隐私交易的必要性并没有业界希望的那样突出，因此这一类代表性项目开始慢慢进入二三线的阵营（不是退出历史舞台）。而应用层面，扩容的必要性提升到无以复加，随着以太坊2.0（已经改名叫consensuslayer）在2020年转变为以rollup为中心的路线，ZK系列正式又回归业界的视线，成为焦点。

隐私交易：隐私交易有很多已经实现的项目，包括使用SNARK的Zcash，Tornado,使用bulletproof的Monero, 以及Dash。Dash严格意义上用的不是ZKP，而是一种简单粗暴的混币系统，只可以隐藏地址而不能隐藏金额，在此略过不表。

Zcash应用的zk-SNARKs交易步骤如下：

HashKey ZK 101 第一期：历史原理与行业

Source: Demystifying the Role of zk-SNARKs in Zcash

·Systemsetup阶段生成证明秘钥（加密证明多项式）和验证秘钥，借助KeyGenfunction

·CPA阶段 ECIES加密方法（Elliptic Curve Integrated Encryption Scheme）用来生成公钥和私钥

·MintingCoins阶段，生成新币的数量。公共地址和币的commitment

·Pouring阶段，生成zk-SNARK证明，证明被加到了pour交易账本中

·Verification阶段，验证者验证Mint和Pour的交易量是否正确

·Receiving阶段，receiver接收币。如果想使用收到的币，则继续调用Pouring，形成zk-SNARK验证，重复上述4-6的步骤，完成交易。

Zcash使用零知识还是有局限性的，就是其基于UTXO, 所以部分交易信息只是被shield了，而不是真正的掩盖。因为其基于比特币的设计的单独网络，所以难以扩展（和其他应用结合）。真正使用shielding（即隐私交易）的使用率只有不到10%，说明隐私交易并没有很成功的扩展。（from2202）

Tornado使用的单一大混币池更加通用，而且基于以太坊这样“久经考验”的网络。Torndao本质上就是一个用了zk-SNARK的混币池，可信设置基于Groth16的论文。Tornado Cash可以提供的特性包括：

·只有被存进去的coin可以被提取

·没有币可以被提取两次

·证明过程和币的废止通知（Nullifier）是绑定的，相同证明但不同Nullifier的哈希不会允许提币

·安全性有126-bit的安全，不会因为composition而降级

Vitalik提到过，和扩容相比，隐私相对比较容易实现，如果一些扩容的protocol都可以成立的话，隐私基本上不会成为问题。

扩容：ZK的扩容可以在一层网络上做，如Mina，也可以在二层网络上做，即zk-roll up。ZK roll up的思路可能最早来自于Vitalik于2018的post，On-chain scaling to potentially ~500 tx/sec through mass tx validation。

ZK-rollup有两类角色，一类是Sequencer, 还有一个是Aggregator。Sequencer负责打包交易，Aggregator负责将大量的交易合并并创造一个rollup, 并形成一个SNARK证明（也可以是基于其他算法的零知识证明），这个证明会和Layer1以前的状态进行比较，进而更新以太坊的Merkle树，计算新的状态树。

HashKey ZK 101 第一期：历史原理与行业

Source: Polygon

ZKrollup的优缺点：

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

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

HashKey ZK 101 第一期：历史原理与行业

Source: 以太坊research

根据数据可用性以及证明的方法，Starkware对L2有一张经典的分类图（Volition的数据可用层可以在链上和链下选择）：

HashKey ZK 101 第一期：历史原理与行业

Source: Starkware

目前市场上最有竞争力的ZKrollup项目有：Starkware的StarkNet，Matterlabs的zkSync和Aztec的Aztecconnect，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兼容的ZKrollup, 团队也是以太坊基金会zkEVM项目的重要贡献者

简要讨论下EVM兼容性问题：

ZK系统和EVM的兼容一直令人头疼，一般项目会在两者间取舍。强调ZK的可能会在自己的系统里做一个虚拟机，并有自己的ZK语言以及编译器，但会加重开发者的学习难度，而且因为基本上不开源，会变成一个黑箱子。一般业界目前是两种选择，一是和Solidity的操作码完全兼容，另一种是设计一种新的虚拟机同时ZK友好并兼容Solidity。业界一开始也没有想到可以这么快的融合，但是近一两年技术的快速迭代，让EVM的兼容提升到一个新高度，开发者可以做到一定程度的无缝迁移（即以太坊主链到ZKrollup），是振奋人心的进展，这将影响ZK的开发生态和竞争格局。我们会在之后的报告中仔细讨论这个问题。