从头梳理ZKP理论和应用层面的一些变化。
撰文：HashKeyCapital
当前区块链行业里零知识证明项目增速惊人，特别是ZKP在扩容和隐私保护两个层面应用的崛起，令我们接触到了各种花样繁多的零知识证明项目。由于ZKP极富数学性的特质，对于加密爱好者来说，想要深度了解ZK的难度大幅提升。因此我们也希望从头梳理ZKP理论和应用层面的一些变化，与读者一起探索对于crypto行业的影响和价值——通过几篇报告的形式共同学习，也作为HashKeyCapital研究团队的思考总结。本篇是该系列的第一篇，主要介绍ZKP的发展历史、应用和一些基本原理。
一、零知识证明的历史
现代零知识证明体系最早来源于Goldwasser、Micali和Rackoff合作发表的论文：TheKnowledgeComplexityofInteractiveProofSystems，该论文提出于1985年，发表于1989年。这篇论文主要阐释的是在一个交互系统中，经过K轮交互，需要多少知识被交换，从而证明一个证言是正确的。如果可以让交换的知识为零，则被称之为零知识证明。这里面会假设证明者具有无限资源，而验证者只具有有限资源。而交互式系统的问题在于证明不完全是数学上可证的，而是概率意义上正确的，虽然概率很小(1/2^n)。
所以交互式系统并不完美，只有近似完备性，以此为基础诞生的非交互式系统系统则具有完备性，成为零知识证明系统的完美所选。
早年的零知识证明系统在效率以及可用性方面都有所欠缺，所以一直都停留在理论层面，直到最近10年才开始蓬勃发展，伴随着密码学在crypto成为显学，零知识证明走向台前，成为至关重要的一个方向。特别是发展出一个通用的、非交互的、证明大小有限的零知识证明协议，是其中最关键的探索方向之一。
欧易OKX宣布将基于全览默克尔树、零知识证明升级储备金证明:3月2日消息，据欧易 OKX 官方消息，平台宣布在未来几个月内升级储备金证明，将基于全览默克尔树、零知识证明的技术来证明偿付能力。后续将允许任何人查阅默克尔树中的所有资产情况，但也会通过拆分和洗牌的方式保障用户隐私。
据了解，除储备金干净度为 100% 外，欧易 OKX 是目前唯一一家同时实现默克尔树开源验证、钱包地址所有权开源验证、链上资产开源验证的交易平台。自去年 11 月份以来，欧易按月定期发布 PoR 报告，持续引领行业提升透明度。[2023/3/2 12:38:51]
基本上零知识证明就是要在证明的速度、验证的速度和证明体积的大小之间做取舍，理想的协议是证明快、验证快、证明体积小。
零知识证明最重要的突破是Groth在2010年的论文ShortPairing-basedNon-interactiveZero-KnowledgeArguments，也是ZKP里面最重要的一组zk-SNARK的理论先驱。
零知识证明在应用上最重要的进展就是2015年Z-cash使用的零知识证明系统，实现了对交易及金额隐私的保护，后来发展到zk-SNARK和智能合约相结合，zk-SNARK进入了更为广泛的应用场景。
在此期间，一些重要的学术成果包括：
2013年的Pinocchio(PGHR13)：Pinocchio:NearlyPracticalVerifiableComputation，将证明和验证时间压缩到适用范围，也是Zcash使用的基础协议。
a16z：零知识证明保护去中心化和隐私，将取得一系列进展:4月15日消息，a16z发文《去中心化的速度：零知识证明的进步》表示，随着区块链吸引了数以百万计的用户，并且它们所承载的应用程序的复杂性不断提高，围绕隐私和可扩展性的两个关键需求已经出现。需要识别的一个关键趋势是，虽然正在为其中许多应用开发专用硬件，但也有一项运动正在优化消费者级硬件的算法，以保护去中心化和隐私。这一趋势的一个特别好的例子是零知识证明。
我们目前正处于一个非常早期的时刻，零知识证明计划将取得一系列进展。我们已经从零知识领域中极少数面向消费者的应用程序，发展到在很短的时间内为隐私和可扩展性提供应用程序和区块链的整个生态系统。像这样的新技术最令人兴奋的一点是，很难预测另一面到底是什么样子。[2022/4/15 14:27:35]
2016年的Groth16：OntheSizeofPairing-basedNon-interactiveArguments，精简了证明的大小，并提升了验证效率，是目前应用最多的ZK基础算法。
2017年的Bulletproofs(BBBPWM17)Bulletproofs:ShortProofsforConfidentialTransactionsandMore，提出了Bulletproof算法，非常短的非交互式零知识证明，不需要可信的设置，6个月以后应用于Monero，是非常快的理论到应用的结合。
2018年的zk-STARKs(BBHR18)Scalable,transparent,andpost-quantumsecurecomputationalintegrity，提出了不需要可信设置的ZK-STARK算法协议，这也是目前ZK发展另一个让人瞩目的方向，也以此为基础诞生了StarkWare这个最重量级的ZK项目。
Polygon 推出基于STARK零知识证明的扩容方案 Miden，采用Facebook开源技术且兼容EVM:11月16日消息，Polygon宣布推出基于零知识的、与 EVM 兼容的扩容解决方案Miden，同时也将开源其核心组件的早期原型版本Polygon Miden 虚拟机 (VM) 。Polygon Miden 是一个基于 STARK 的 ZK Rollup，Polygon Miden VM 是完全开源的基于 STARK 的虚拟机，它的作用是验证程序执行并为DApp 部署提供增强的尽职调查。Miden VM 通过利用Facebook的Novi开发的STARK证明器/验证器Winterfell 对基于Rust语言编写的零知识虚拟机 Distaff VM进行了扩展。Distaff VM和Winterfell的核心开发人员Bobbin Threadbare将加入 Polygon 作为 Miden Lead，致力于重新整合 Distaff，将 Distaff 和 Winterfell 结合起来，并继续开发 Miden VM 及其周围的生态系统。
除Polygon Miden外，Polygon价值10亿美元的ZK策略资金还孵化Polygon Hermez和Polygon Nightfall。Polygon Hermez是此前收购的Hermez Network，Polygon Nightfall是与安永共同开发构建的以隐私为重点保护的Rollup。[2021/11/17 21:56:06]
其他的发展包括PLONK、Halo2等也是极为重要的进展，也对zk-SNARK做出了某些层面上的改进。
金色沙龙 | 燕丽：零知识证明对于协调区块链底层扩容也有很大帮助:在今日举行的《隐私计算——区块链信息安全守护者》为主题的金色沙龙中，算力智库创始人燕丽表示，2020年1月1日，中国首部《中华人民共和国密码法》将正式开始实施，而在这之前一直只有一部 2007年4月23日公布的《商用密码产品使用管理规定》和《境外组织和个人在华使用密码产品管理办法》。很多人把这次《密码法》和2019年“1024”中央把区块链技术作为国家战略联系在一起。区块链技术是完全基于密码学技术，所以按照这个逻辑，如果政府要完全掌控未来区块链技术的发展，首先就要完全掌控密码学技术，而这个其中的核心是国家主权范围之间在所有的通信安全和商业行为之间军备竞赛的升级。区块链有大量扩容压力，而为了达到这个操作，必然要牺牲系统处理效能和部分隐私。但矛盾的是，区块链前期的应用场景如虚拟货币，数字金融等，都需要有更好的隐私保护和不容易被恶意攻击的防护。所以若想让区块链技术落地生根，那么提高区块链底层技术来满足对于高安全性(含高完整性和高保密性)、高性能、高广义效率的要求，也许是个稳妥做法。所以隐私计算中的零知识证明等对于协调区块链底层扩容也有很大帮助。[2020/4/15]
二、零知识证明的应用简述
零知识证明最广泛的两个应用就是隐私保护和扩容。早期随着隐私交易和几个有名的项目Zcash和Monero等推出，隐私交易一度成为非常重要的门类，但由于隐私交易的必要性并没有业界希望的那样突出，因此这一类代表性项目开始慢慢进入二三线的阵营。而应用层面，扩容的必要性提升到无以复加，随着以太坊2.0在2020年转变为以rollup为中心的路线，ZK系列正式又回归业界的视线，成为焦点。
声音 | 常山北明：将为至信链贡献跨链交换、零知识证明、分片共识相关的技术:常山北明（SZ000158）董秘在互动平台回复投资者对于“公司在区块链布局及技术优势”的提问表示，至信链是腾讯、中国网安和北明软件做为核心节点携手发布的区块链。至信链将致力于生态建设，在数据保全、纠纷解决、诉讼辅助等方面做出自己的贡献。北明软件将为至信链贡献跨链交换，零知识证明，分片共识相关的技术和知识的积累。[2019/9/27]
隐私交易：隐私交易有很多已经实现的项目，包括使用SNARK的Zcash，Tornado,使用bulletproof的Monero,以及Dash。Dash严格意义上用的不是ZKP，而是一种简单粗暴的混币系统，只可以隐藏地址而不能隐藏金额，在此略过不表。
Zcash应用的zk-SNARKs交易步骤如下：
Source:DemystifyingtheRoleofzk-SNARKsinZcash
Systemsetup阶段生成证明秘钥和验证秘钥，借助KeyGenfunction
CPA阶段ECIES加密方法用来生成公钥和私钥
MintingCoins阶段，生成新币的数量。公共地址和币的commitment
Pouring阶段，生成zk-SNARK证明，证明被加到了pour交易账本中
Verification阶段，验证者验证Mint和Pour的交易量是否正确
Receiving阶段，receiver接收币。如果想使用收到的币，则继续调用Pouring，形成zk-SNARK验证，重复上述4-6的步骤，完成交易。
Zcash使用零知识还是有局限性的，就是其基于UTXO,所以部分交易信息只是被shield了，而不是真正的掩盖。因为其基于比特币的设计的单独网络，所以难以扩展。真正使用shielding的使用率只有不到10%，说明隐私交易并没有很成功的扩展。
Tornado使用的单一大混币池更加通用，而且基于以太坊这样“久经考验”的网络。Torndao本质上就是一个用了zk-SNARK的混币池，可信设置基于Groth16的论文。TornadoCash可以提供的特性包括：
只有被存进去的coin可以被提取
没有币可以被提取两次
证明过程和币的废止通知是绑定的，相同证明但不同Nullifier的哈希不会允许提币
安全性有126-bit的安全，不会因为composition而降级
Vitalik提到过，和扩容相比，隐私相对比较容易实现，如果一些扩容的protocol都可以成立的话，隐私基本上不会成为问题。
扩容：ZK的扩容可以在一层网络上做，如Mina，也可以在二层网络上做，即zk-rollup.ZKrollup的思路可能最早来自于Vitalik于2018的post，On-chainscalingtopotentially~500tx/secthroughmasstxvalidation。
ZK-rollup有两类角色，一类是Sequencer,还有一个是Aggregator。Sequencer负责打包交易，Aggregator负责将大量的交易合并并创造一个rollup,并形成一个SNARK证明，这个证明会和Layer1以前的状态进行比较，进而更新以太坊的Merkle树，计算新的状态树。
Source:Polygon
ZKrollup的优缺点：
优点：费用低，不像OP会被经济攻击，不需要延迟交易，可以保护隐私，快速达成最终性
缺点：形成ZK证明需要大计算量，安全问题，不抗量子攻击，交易顺序可能被改变
Source:以太坊research
根据数据可用性以及证明的方法，Starkware对L2有一张经典的分类图：
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。zkSync2.0是EVM兼容的，有自己的zkEVM
Scroll，一种EVM兼容的ZKrollup,团队也是以太坊基金会zkEVM项目的重要贡献者
简要讨论下EVM兼容性问题：
ZK系统和EVM的兼容一直令人头疼，一般项目会在两者间取舍。强调ZK的可能会在自己的系统里做一个虚拟机，并有自己的ZK语言以及编译器，但会加重开发者的学习难度，而且因为基本上不开源，会变成一个黑箱子。一般业界目前是两种选择，一是和Solidity的操作码完全兼容，另一种是设计一种新的虚拟机同时ZK友好并兼容Solidity。业界一开始也没有想到可以这么快的融合，但是近一两年技术的快速迭代，让EVM的兼容提升到一个新高度，开发者可以做到一定程度的无缝迁移，是振奋人心的进展，这将影响ZK的开发生态和竞争格局。我们会在之后的报告中仔细讨论这个问题。
三、ZKSNARK实现的基本原理
Goldwasser、Micali和Rackoff提出了零知识证明有三个性质：
完整性：每一个拥有合理见证的声明，都是可以被验证者验证的
可靠性：每一个只拥有不合理见证的声明，都不应该被验证者验证
零知识：验证过程是零知识的
所以为了了解ZKP,我们从zk-SNARK开始，因为很多目前的区块链应用都是从SNARK开始。首先，我们先了解一下zk-SNARK。
zk-SNARK的意思是：零知识证明是zero-knowledgeSuccintNon-interactiveARgumentsofKnowledge。
ZeroKnowledge：证明过程零知识，不会暴露多余信息
Succinct：验证体积小
Non-interactive：非交互过程
ARguments：计算具备可靠性，即有限计算能力的证明者不能伪造证明，无限计算能力的证明者可以伪造证明
ofKnowledge：证明者无法在不知道有效信息的情况下构建出一个参数和证明
对于证明者来说，在不知道证据的情况下，构造出一组参数和证明是不可能的。
Groth16的zk-SNARK的证明原理和如下：
Source：https://learnblockchain.cn/article/3220
步骤是：
将问题转换为电路
将电路拍平成R1CS的形式.
R1CS转换成QAP形式
建立trustedsetup,生成随机参数，包括PK(provingkey)，VK(verifyingkey)
zk-SNARK的证明生成和验证
下一篇我们将开始研究zk-SNARK的原理、应用，通过几个案例来透视ZK-SNARK的发展，并探索它与zk-STARK的关系等。
郑重声明： 本文版权归原作者所有， 转载文章仅为传播更多信息之目的， 如作者信息标记有误， 请第一时间联系我们修改或删除， 多谢。