本文是对零知识证明领域相关资料的梳理以及行业应用的探讨,希望能给非技术出身的研究员提供 ZKP 研究的指引。企图帮助非技术出身的研究员由浅入深理解零知识证明。
原文标题:Zero-Knowledge Proof: from Zero toHero
原文作者:Research Dao
原文来源: Mirror
本文是对零知识证明领域相关资料的梳理以及行业应用的探讨,希望能给非技术出身的研究员提供 ZKP 研究的指引。企图帮助非技术出身的研究员由浅入深理解零知识证明。
本章是对 Aviv Zohar 2017年发表的 The Incredible Machine 的概括,从故事的角度出发,帮助读者更直观得体会零知识证明的相关特性。
Alice 和 Bob 都是数独爱好者,有一天 Alice 向 Bob 说,“我设计了一个很难的数独,你要不要挑战一下?” Bob 接受挑战,但迟迟无法填满空格,便质疑 Alice 的题目是无解的。为了证明其题目有解且不暴露答案本身,Alice 想到了个办法。
验证:Bob 打开布袋,验证每个布袋是否都是 1~9 的数字卡片
重复:按照数独需要每一行每一列每个九宫格的数字都不会重复,只做一次随机实验,Alice 没说谎的概率只有 1/3,重复做几次实验,每次实验结果都是不会重复的数字,则可以证明 Alice 确实是知道这道题的解。
初始化设置:行列块的抽取顺序是 Charlie 设置的,因此这台机器没法验证他是否能解数独,其他人也可以通过贿赂 Charlie 知道抽取顺序。于是 Alice 提议让 Charlie 把控制面板重新打开,多方(multi-party)共同设置控制面板上的试验序列。这个过程称为“可信任的初始设置仪式(trusted setup ceremony)。把机器放在一个黑暗的房间里,第一个人进房间后拨动拨盘到任意随机的位置,第二个人和第三个人按照第一个人随机选中的顺序分别往下加一格和两格,用这样的方式,保证每一个拨盘都不会被其中任何人知道。这个设置仪式完成之后,他们就焊接好机器控制面板。
这样的机器,就可以实现 ZK 的三个特性:
本章是对 ZK-SNARK(主流的 ZKP)的数学证明过程,主要参考 Vitalik Buterin 2016 年发表的 Quadratic Arithmetic Programs: from Zero to Hero ,从数学的角度出发,帮助读者进一步理解零知识证明的实现过程。
P 问题 与 NP 问题
线性代数基础知识
矩阵乘法运算
拉格朗日插值法
如左图所示,若已知输入,验证人(Verifier)想要验证证明人(Prover)给的结果是否正确,可通过计算术电路中每一个节点的值最终得出结果与输出进行对比,但此过程无法达到简洁性,也即证明人和验证人为了得出结论所使用的计算时间是相同的,因此可以将运算过程中的值作为未知变量,通过零知识证明来进行验证,以此达到验证过程的简洁性;如右图所示,证明人为了保持部分输入的隐私性,可通过零知识证明技术让验证人相信证明人是知道正确的解。
验证者(Verifier)已知的信息为Statement(如下图绿色所示),证明者(Prover)知道的知识而验证者不知道的信息为Witness(如下图蓝色所示)。
目前主流的 ZKP 有 zkSNARK 和 zkSTARK。SNARK、STARK、ZKP都属证明系统,SNARK与ZKP相交的地方称为 zkSNARK, SNARK与ZKP相交的地方称为 zkSTARK。
STARK和 SNARK 只有一字之差,但有很多不同。下面我们比较一下这两个概念。
共同点:
区别:
ZKP 主要应用于扩容和隐私两个方向,而隐私方向又包括了建立在 Layer1 或 Layer2 上的隐私应用和隐私公链。在 Defi 还没爆发之前,ZK 主要应用于隐私方向,Defi 爆发后,Gas 费高涨是以太坊被大规模使用的最大障碍。因此大家开始把目光转移到 Layer2 扩容中,而 Layer2 方案中,zk- Rollup 在安全性和节省 Gas 费方面都有最佳的表现。
讨论 Layer2 扩容方案之前,我们先来大致了解一下 以太坊的 Gas 构成。
以太坊上 gas 费的计算方式为燃料单价 (gasPrice) * 燃料开销 (gasUsed)。
Rollup 是将主网上需要计算的交易转移到了链下去,然后再将计算好的结果反馈给主网,以此来降低交易的复杂程度从而降低 gas 费用;而 ETH2.0 的解决方案是降低主网的 gas 燃料单价,从而降低 gas 费用。
Layer 2 扩容方案可按照数据存储方式和证明系统进行划分,具体划分方式如下图所示。目前主流的方案是 Optimistic Rollup 和 ZK Rollup。
Optimistic Rollup
隐私应用
以太坊上的交易纪录都是公开的,你可以在 etherscan 上看到某个地址的所有历史交易纪录,并且知道每个地址的资产余额。传统金融支付中,人们往往不愿意让别人知道自己账户里面有多少钱,也不愿意让随意一个人都能查询到自己的流水记录,利用 ZK 技术能很好得解决此问题。
Tornado.Cash 作为以太坊网络上最火的去中心化隐私解决方案,使用zk-SNARKs技术,打破了存款人和取款人地址之间的链上链接,做到了交易机密性,保护了用户隐私,实现了匿名的代币交易。简单来说,它是一份合约,当你要匿名传送代币时,就把一定数量的币丢进合约里(Deposit),此时你会拿到一个note,note 就是一串字串,拥有这字串的人,就能提领(Withdraw) 刚刚传入合约的代币。握有note 就代表拥有提款的权利,所以note 一旦被别人知道,别人就可以把钱给提走。
目前的 Gamefi 基本上只有资产上链,游戏的资产价值又很大程度依赖于游戏本身,中心化运行的游戏关闭之后,上链的资产价值也不复存在,因此仅仅是资产上链并不够去中心化。而将整个游戏部署在区块链上的游戏才能称为 Decentralized Game。
Dark Forest是一款实时策略游戏,也是第一款全链游戏,在Gnosis 链上运行。星球的移动和攻占是整个游戏的策略重点。既然是移动攻击,每个星球有一个坐标。为了增加游戏的策略体验,星球的具体坐标并不公开。有点像在浩瀚的宇宙中,只能观察(枚举)周围有限空间(hash碰撞)寻找其他星球。为了在不公开星球坐标的情况,还能证明星球的移动正确,引入了零知识证明技术。
隐私公链
Zcash 诞生于 2011 年 11 月 9 日,全称 Zero Cash,简称 ZEC。 Zcash 的大部分代码与比特币极其相似,总量都是 2100 万枚,但它进一步完善了比特币匿名功能方面的不足。Zcash 是首个使用 Zk-SNARK 零知识证明机制的区块链系统,目的是彻底解决交易被追踪从而暴露用户隐私的问题。Zcash 交易自动隐藏区块链上所有交易的发送者、接收者及数额。只有拥有查看密钥的人才能看到交易的内容。 用户拥有完全的控制权,他们可自行选择向其他人提供查看密钥。目前,Zcash 交易分为两类:透明地址(「t」开头)和隐藏地址(「z」开头)。如果用户希望验证隐藏地址的详细信息,必须与相关方共享特殊的访问密钥。用户也可「选择性披露」,它还带有一个加密的备忘录字段,允许机构安全地将敏感数据附加到交易中,并使这些信息对授权方可见。
Mina是一个轻量级的公链,通过递归零知识证明,将区块链大小维持在22 KB左右,这允许节点以低门槛的硬件条件参与,哪怕是运算能力相对较弱的移动端,类似手机、平板电脑等,也可以去同步验证Mina网络,更低的节点门槛,节点也更具分布式,并且围绕着零知识证明搭建了一个可保护数据隐私的生态系统。
递归零知识证明指:在每次区块生产时,利用zk-SNARK技术将区块压缩为单个证明,并且每个新的SNARK证明都包含过去的SNARK证明,节点只需检测该证明即可,以此不需要检测整个交易历史记录,同时这些证明可以进行递归组合,以实现区块的大小恒定。
Iron Fish 致力于为每笔交易提供强大的隐私保证。包括交易信息、挖矿信息、钱包信息全都处于隐藏,除了私钥所有者以外,任何第二方都无法查看。为实现这一目标,Iron Fish 构建了一个全新的 PoW 网络,使用 zk-SNARKs 以及 Sapling 协议来为每一笔链上交易提供最高层级的隐私保护。 Iron Fish 的一大亮点在于,该网络希望在保护隐私的同时也不去损害链上交易的可访问性,为此,Iron Fish 为每个链上地址额外配备了一个查看密钥(view key),地址持有者可通过该密钥授予其他人只读权限。
在路线上,Iron Fish 表示,未来网络层将支持 WebRTC 与 WebSockets,这意味着可通过浏览器直接运行完整的 Iron Fish 节点。 当前,Iron Fish 仍处于测试网阶段,并已启动激励计划,活跃参与者可以通过各种贡献获取相应积分,这些积分将在未来主网发布时兑换成主网代币。
Aleo致力于构建模块化且合规的零知识隐私应用平台,用于构建私有应用的最终工具包。其利用去中心化系统、零知识加密技术,保护 Web 上的用户数据以实现这⼀目标。
Aleo Studio Aleo Studio是第⼀个用于编写零知识应用程序的 IDE。
专为正式验证的零知识应用程序设计的新编程语言。Leo 提供了⼀个不受运行时间、堆栈大小或指令集限制的强大执行环境。
PoSW 是比特币基于 SHA 的难度调整算法的变体,主要区别在于底层计算不是任意的哈希函数,而是知识证明。这使得 PoSW 解决方案不仅可以充当 PoW 以确保系统共识,还可以验证给定区块中的交易包含。
以太坊虚拟机 (EVM) 是基于区块链的开源软件,允许开发者创建去中心化的应用。它是全球虚拟计算机,记录以太坊网络存储和达成共识的每个智能合约的状态,Solidity 是其编程语言。EVM是第一个为开发者提供智能合约功能的软件,并且已经成长为一个蓬勃发展的生态系统,其极具价值的开发者网络效应超越了以太坊区块链本身。
如果某个协议的智能合约可以在 EVM 上执行,那么该协议就是与 EVM 兼容的,这意味着该协议的合约必须要么用 Solidity 编写,要么能够将其合约代码编译成可以在 EVM 上运行的字节码。新公链或 Layer2 想要快速扩充其生态,EVM 兼容是必不可少的,可以将以太坊上原有的用Solidity编写的应用快速部署到自己的链上。而Solidity语言有很多ZK-Unfriendly的语法,使得 ZK-EVM 的实现面临很大的挑战,哪个协议能实现更好的EVM兼容性,将更快达到网络效应。
下文是对 Vitalik 2022 年发表的 The different types of ZK-EVMs 以及 Ye Zhang 2022 年发表的zkEVM 的概括与总结,从 ZK- EVM的分类和技术演变的角度出发,帮助读者更好得了解ZK-EVM的发展现状。
Type 1(完全等效于以太坊)
力求完全且毫不妥协地与以太坊等效。不改变以太坊系统的任何部分来生成证明。
优点:完美兼容, 这类 ZK-EVM 是我们最需要的,使以太坊第 1 层本身更具可扩展性,也是 rollup 的理想选择,因为它允许 rollup 能使用大量的基础设施。(可以使共识层面也用 ZK 来实现)
缺点:证明时间长。 以太坊最初并不是围绕 ZK 友好性设计的,因此以太坊协议的许多部分需要大量计算才能进行 ZK 证明。类型 1 旨在精确复制以太坊,因此它无法缓解这些低效率。
Builders:privacy-scaling-explorations
类型 2 ZK-EVM 力求完全等同于 EVM,但不完全等同于以太坊。也就是说,它们「从内部」看起来与以太坊完全一样,但它们在外部存在一些差异,特别是在块结构和状态树等数据结构上。
优点:VM 级别的完美等价,你将无法按原样使用以太坊执行客户端,但你可以通过一些修改来使用它们,并且您仍然可以使用 EVM 调试工具和大多数其他开发人员基础设施。
缺点:有改进但仍然需要提供比类型 1 更快的证明时间,主要是通过删除依赖于不必要的复杂和 ZK 不友好密码学的部分以太坊堆栈,但它们并不能解决所有问题。
Builders:Scroll 的 ZK-EVM 项目正朝着 Type 2 ZK-EVM 方向发展,Polygon Hermez 也是如此。也就是说,这两个项目都还没有完成。特别是,许多更复杂的预编译还没有实现。因此,目前这两个项目都被更好地考虑为 Type 3。
显著改善最坏情况证明者时间的一种方法是大大增加 EVM 中很难进行 ZK 证明的特定操作的 gas 成本,更改 gas 成本可能会降低开发人员工具的兼容性并破坏一些应用程序,但通常认为它的风险低于「更深入」的 EVM 更改。
优点:加快证明时间
缺点:产生部分不相容
类型 3 ZK-EVM 几乎与 EVM 等效,但在精确等效性方面做出了一些牺牲,以更进一步缩短验证时间并使 EVM 更易于开发,可能会删除一些在 ZK-EVM 实现中极难实现的功能。
优点:更容易构建,更快的验证时间
缺点:更多的不兼容 这类 ZK-EVM 的目标是与大多数应用程序兼容,并且只需要对其余部分进行最少的重写。也就是说,将有一些应用程序需要重写。
Builders:Scroll 和 Polygon 在其当前形式中都是 Type 3,尽管它们有望随着时间的推移提高兼容性。Polygon 使用了一些不同的内部逻辑来完成它。Type 3 只是一个过渡阶段,直到完成添加预编译的复杂工作并且项目可以移动到 Type 2.5。
类型 4 通过获取以高级语言(例如 Solidity、Vyper 或两者都可以编译的中间语言)编写的智能合约源代码并将其编译为明确设计为 ZK-SNARK 友好的某种语言来工作.
优点:非常快的验证时间 通过不对每个 EVM 执行步骤的所有不同部分进行 ZK 证明,并直接从更高级别的代码开始,您可以避免很多开销。
缺点:更多的不兼容
Builders:ZKSync 是一个 Type 4 系统,尽管随着时间的推移它可能会增加对 EVM 字节码的兼容性。Nethermind 的 Warp 项目正在构建一个从 Solidity 到 Starkware 的 Cairo 的编译器,这将把 StarkNet 变成事实上的 Type 4 系统。
ZK-EVM 类型的未来分出这些类型并不是要比较「更好」或「更差」。相反,它们是权衡空间上不同的点:编号较小的类型与现有基础架构的兼容性更高,但速度较慢,编号较高的类型与现有基础架构的兼容性较差,但速度更快。
可以看到,为了实现更好的兼容性,不仅仅ZK项目方需要努力,还需要以太坊自身的改进以及硬件的发展。
在 DeFi 爆发之前,ZKP 主要用于隐私方向。 DeFi爆发后,高昂的gas费用是以太坊大规模使用的最大障碍。于是大家开始将目光转向Layer2扩容,而Layer2方案中,zk-Rollup在安全性和节省gas成本方面表现最好。阻碍zk-Rollup大规模爆发的原因是由于其兼容性差,需要修改很多Layer 1协议来部署zk-Rollup。随着 zk-EVM 的发展,这个问题将得到解决。 ZK-Rollup 和 ETH 的结合在保证安全性的同时大大降低了 Gas 费用,进一步阻碍了 Alt Layer1 的发展。届时,以太坊将进一步实现其成为全球结算层的愿景。
责编:Lynn