当前位置:okx > 头条 > 零知识证明入门指南: 发展历史、应用和基本原理

零知识证明入门指南: 发展历史、应用和基本原理

小欧2022-08-11 11:24:18头条23
从头梳理 ZKP 理论和应用层面的一些变化。

撰文:HashKey Capital

当前区块链行业里零知识证明项目(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(已经改名叫 consensus layer)在 2020 年转变为以 rollup 为中心的路线,ZK 系列正式又回归业界的视线,成为焦点。

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

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

零知识证明入门指南: 发展历史、应用和基本原理-第1张图片

Source: Demystifying the Role of zk-SNARKs in Zcash
  • System setup 阶段生成证明秘钥(加密证明多项式)和验证秘钥,借助 KeyGen function

  • CPA 阶段 ECIES 加密方法(Elliptic Curve Integrated Encryption Scheme)用来生成公钥和私钥

  • Minting Coins 阶段,生成新币的数量。公共地址和币的 commitment

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

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

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

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

Tornado 使用的单一大混币池更加通用,而且基于以太坊这样“久经考验”的网络。Torndao 本质上就是一个用了 zk-SNARK 的混币池,可信设置基于 Groth 16 的论文。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 树,计算新的状态树。

零知识证明入门指南: 发展历史、应用和基本原理-第2张图片

Source: Polygon

ZK rollup 的优缺点:

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

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

零知识证明入门指南: 发展历史、应用和基本原理-第3张图片

Source: 以太坊 research

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

零知识证明入门指南: 发展历史、应用和基本原理-第4张图片

Source: Starkware

目前市场上最有竞争力的 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 项目的重要贡献者

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

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

三、ZK SNARK 实现的基本原理

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

  • 完整性(Completeness):每一个拥有合理见证的声明(statement),都是可以被验证者验证的

  • 可靠性(Soundness):每一个只拥有不合理见证的声明,都不应该被验证者验证

  • 零知识(Zero-knowledgeness):验证过程是零知识的

所以为了了解 ZKP, 我们从 zk-SNARK 开始,因为很多目前的区块链应用都是从 SNARK 开始。首先,我们先了解一下 zk-SNARK。

zk-SNARK 的意思是:零知识证明(zh-SNARK)是 zero-knowledge Succint Non-interactive ARguments of Knowledge。

  • Zero Knowledge:证明过程零知识,不会暴露多余信息

  • Succinct:验证体积小

  • Non-interactive:非交互过程

  • ARguments:计算具备可靠性,即有限计算能力的证明者不能伪造证明,无限计算能力的证明者可以伪造证明

  • of Knowledge:证明者无法在不知道有效信息的情况下构建出一个参数和证明

  • 对于证明者来说,在不知道证据(Witness,比如一个哈希函数的输入或者一个确定 Merkle-tree 节点的路径)的情况下,构造出一组参数和证明是不可能的。

Groth16 的 zk-SNARK 的证明原理和如下:

零知识证明入门指南: 发展历史、应用和基本原理-第5张图片

Source: https://learnblockchain.cn/article/3220

步骤是:

  1. 将问题转换为电路

  2. 将电路拍平成 R1CS 的形式.

  3. R1CS 转换成 QAP(Quadratic Arithmetic Programs)形式

  4. 建立 trUSTed setup, 生成随机参数,包括 PK (proving key),VK(verifying key)

  5. zk-SNARK 的证明生成和验证

下一篇我们将开始研究 zk-SNARK 的原理、应用,通过几个案例来透视 ZK-SNARK 的发展,并探索它与 zk-STARK 的关系等。

“零知识证明入门指南: 发展历史、应用和基本原理” 的相关文章

UST 崩盘  波场版算法稳定币亮相

UST 崩盘 波场版算法稳定币亮相

算法稳定币 UST 已然崩盘,波场版的「算稳」USDD 又来了。USDD 由多家机构参与的「波场联合储备」发行和背书,采用了与 UST 几乎相同的价格波动调节机制,这使得其在极端下跌行情下仍存脱锚风险。此外,由于二级市场用户无法自行铸造和销毁 USDD,也导致其宣称的「去中心化」打了折扣。LUNA...

Storonosky 表示,Revolut 计划中的原生代币将奖励客户忠诚度

在接受 The Block 采访时,Revolut 首席执行官 Nik Storonosky 详细介绍了传闻已久的“Revcoin”以及它将如何作为一种可交易的忠诚度形式发挥作用。 Storonsky 计划在以太坊网络上推出 Revolut 的非托管加密钱包,长期目标是多链钱包。首席执行官...

比特币、以太坊与股票的相关性极高,这对价格意味着什么

比特币(BTC)和以太坊(ETH)继续与股市保持极高的相关性根据IntoTheblock分析公司最近分享的数据,比特币(BTC)和以太坊(ETH)继续与股市保持极高的相关性,30 天相关性高达 0.9。比特币多头的棘手结论是,最近加密市场的下跌不能与传统市场的低迷分开。周四,股票期货再次承压,标准普...

Coingecko联合创始人预测,美联储提高利率 未来 12 到 18 个月的加密市场将充满挑战

Coingecko联合创始人预测,美联储提高利率 未来 12 到 18 个月的加密市场将充满挑战

Coingecko联合创始人Bobby Ong在社交媒体预测,由于美联储提高利率以抑制通货膨胀,而且现在正处于加息周期的开始阶段,所以未来 12 到 18 个月的加密市场将充满挑战。此外,比特币和加密货币现在与传统金融也变得密切相关,并且被视为科技股/风险资产,因此股市下跌也会给加密市场造成影响。...

eBay 在 Polygon 上推出 Wayne Gretzky NFT

eBay 的首批 NFT 将是曲棍球传奇人物韦恩·格雷茨基 (Wayne Gretzky) 的数字收藏品。现年 61 岁的格雷茨基在 NHL 打了 20 个赛季,跨越了三个十年,赢得了四次斯坦利杯,被许多人认为是有史以来最伟大的球员。Gretzky NFT(表示所有权的独特区块链代币)位于...

Filecoin 基金会和洛克希德马丁合作将去中心化存储带入太空

Filecoin 基金会和美国航空航天科技公司洛克希德马丁公司周一宣布了为航天工业设计去中心化存储的计划。 此次合作旨在建立基础设施以共享信息、加快通信并降低地球和太空之间的存储成本。 Filecoin 基金会是星际文件系统 (IPFS) 的创建者,这是一种基于区块链的存储协议,...