什么是零知识证明?|ZK 科普系列(一)

近来,我们在国外社区看到越来越多关于 ZKP (零知识证明)的讨论。无论是 Aztec 的新一轮融资,还是以 Polygon 为代表的以太坊二层网络的进展,都让 ZK 受到了极大的关注。但在国内,ZK 技术尚没有得到大规模的讨论,这其中原因不乏通俗易懂科普资料的匮乏。而作者,作为 ZK 的爱好者和初学者,试图通过系统的资料归纳和学习定期为大家奉献一系列的科普文章,让大家对于 ZK 有更全面的理解。本文为 ZK 科普系列第一篇:《什么是零知识证明?》


零知识证明(Zero-knowledge proofs,以下简称 ZKP)

零知识证明的想法最初是在1980年的一份学术论文中——《交互性证明系统的知识复杂度》中被提出。论文中提到:证明者可以在不披露信息本身的情况下向验证者证实信息的真实性。

从更技术的角度说,ZKP 是证明者与验证者两方之间的一个协议,证明者可以在不透露证明本身之外任何信息的前提下,让验证者确认某项证明是有效的。这是证明的“零知识”部分——没有知识或信息可以支持这条证明,除了证明本身。这听起来毫无道理,也似乎是不可能的。正是如此,这些技术才更加重要。

经常拿来解释 ZKP 的例子是一个名叫《寻找 Waldo》的游戏。证明者如何利用零知识来向验证者证明他知道 Waldo 在图中的哪个地方。一般的情况来说,证明者只需要在图上指出 Waldo 的位置即可,或者说 Waldo 在红白条纹的帐篷旁边,这样通过提供知识来向验证者证明他确实知道 Waldo 在哪儿。

但是如果用零知识的方法,证明者需要拿出一张纸,在中间剪个洞,并将洞放在 Waldo 上面来展示给验证者。这样,验证者可以看到 Waldo,知道证明者说的是真的,而且过程中也没有任何知识/信息的泄露。

这个例子可以很好地解释零知识证明,因为验证者可以询问 “Waldo 在哪儿”,证明者通过一张带洞的纸来证明了他知道 Waldo (只有 Waldo 自己)的位置。证明本身就是事实的证据。

如果验证者问的是“Waldo 在哪儿”,而证明者指出的是一艘小船,验证者只通过证明本身就知道证明者在撒谎。

从结构上来说,ZKP 有三个主要部分:

  • 完整性 如果证明者说的是真的,验证者不需要额外的信息就可以得出结论;

比如:通过指出 Waldo 自己的位置,验证者立即可以验证证明者确实知道 Waldo 在哪里,不需要其它额外的信息。

  • 可靠性 如果证明者的说法是错误的,验证者绝不可能认为是真的;

如果证明者指出的不是 Waldo 而是其它内容,验证者便知道这不是 Waldo。

  • 零知识 证明者没有提供除了证明本身外的任何其它知识;

只用一张带洞的纸指出了 Wlado ,没有其它任何语言等暗示。

作为读者,你可能会想:故事不错,但是 ZKP 有什么现实意义呢?

有两个非常重要的方向:

  1. 隐私性——ZKP 做到了信息的隐私性。在交易中,你需要能证明你拥有某种未花费的资产,但是不想暴露资产的整个来源去向,可解决比特币等区块链平台中交易透明性带来的信息泄露,如转账地址和金额;
  2. 可拓展性——若某个区块直接验证的时间很长,可改为由一人验证并生成证明,而网络中的其它人快速验证该证明,而不再需要每个人都花很长时间来直接验证;

从上面的例子来看:

  1. 证明者只指出了 Waldo,而没有展示其它任何信息。因此关于 Waldo 具体位置的信息是隐私的;
  2. 对于验证者来说,通过带洞的剪纸看到 Waldo 比坐着听证明者试图用语言描述 Waldo 在图片中的哪个位置可以更快地进行验证。而这样,为了让验证者更快速地进行验证,证明者需要在执行过程中做更多的工作;

ZKP 本身非常复杂,这种简化的举例说明可以让大家对于 ZKP 的基础有个大概的了解。


零知识证明的分类

ZKP 主要有两种类型:zkSNARK 和 zkSTARK

zkSNARK 的概念最早于 2013年被学者提出。SNARK 分别是以下几个字母的首字母缩写。

  • Succinct (简洁)
  • Non-Interactive (非交互)
  • ARgument (论证)
  • of Knowledge (知识)

ZKP 是“简洁的”——即便在数据量很大的情况下,也可以快讯进行验证(几毫秒),验证长度只有几百字节。这意味着,验证时间不会随着运算吞吐量而成倍增长(因此可以用来扩容)。

在最初的零知识证明中,证明者和验证者为了建立可信度,可能需要多次交互。这样产生的问题是,交互越多,效率越低,会进而减慢 ZKP 的速度并影响可拓展性。而在非交互式 ZKP 中,证明只是从证明者到验证者的单条信息,这让整个过程变得更加高效。在实践中,可以生成非交互式且足够短到向区块链发布的、最高效的零知识证明方法是从 SNARK 设置之初(也就是“初始设置阶段 initial setup phase”)就在证明者和验证者之间创造一个公共参考字符串。从技术上讲复杂度很高,但这样也许可以帮助理解:

交易依靠 zkSNARK 的公共参数来在区块链上进行 ZKP 的构建和验证。公共参数的生成可以理解为创建一个公共/私密钥匙串(就像你创建一个 MetaMask 账户,获得你的地址——公钥,和助记词——私钥)。但问题是设置 SNARK 的个人是知晓私钥的(可信设置),有私钥就有滥用系统的可能性,因此为了保证 SNARK 的安全性,私钥必须要被有效破坏掉。

2017年,Zcash 成为首个使用 zkSNARK 的加密货币项目。在一场非常引人注目的仪式上,Zcash 销毁了私钥。zkSNARK 需要确保私钥不被任何人所知,这也被认为是其最主要的安全风险。

zkSNARK 是 ZKP 的一种形式。zkSNARK 很简洁,可以被快速验证,验证时间不会随验证计算量的增长而线形增加。zkSNARK 是非交互式的,证明者和验证者之间少有交互,因此也更高效。可信设置是必须的,但是可能存在安全风险。

zkSTARK 技术2018年在一份学术论文中被提出。论文作者随后创建了 StarkWare。zkSTARK 构建于 zkSANRK 之上,并试图对其进行改进:

STARK 是以下几个首字母的缩写:

  • Scalable (可拓展)
  • Transparent(透明)
  • ARgument(论证)
  • of Knowledge(知识)

STARK 的目标是比 SNARK 更具可拓展性,STARK 的 “S” 是可扩展性。这种可拓展性被 STARK 的创造者之一 Eli Ben-Sasson 形容为“full scalability”,主要包括两部分:

  1. 随着 STARK 中转账数量的增加,验证速度相比执行速度呈指数型增长;
  2. Prover 复杂度是拟线性的 (Quasi-linear),随着 STARK 扩展性提高,STARK 的证明复杂度并没有相应增加;

为了解决 zkSNARK 中存在的可信设置问题,zkSTARK 使用可公开验证的随机数来产生 STARK。这也是 STARK 中 “Transparent”(透明)的部分。

zkSTARK 相比于 zkSANRK 的第三个改进是“抗量子计算”,意味着其并不会被量子计算破解。当然,这些改进同时也伴随着牺牲。相比于 SNARK,STARK 更加复杂,proof size 更大,而且消耗的以太坊验证手续费也更高。

https://cdn.substack.com/image/fetch/w_1100,c_limit,f_auto,q_auto:good,fl_progressive:steep/https%3A%2F%2Fbucketeer-e05bbc84-baa3-437e-9518-adb32be77984.s3.amazonaws.com%2Fpublic%2Fimages%2F011555c3-fdcb-43e6-b4a4-960ad157bee0_679x255.png
https://cdn.substack.com/image/fetch/w_1100,c_limit,f_auto,q_auto:good,fl_progressive:steep/https%3A%2F%2Fbucketeer-e05bbc84-baa3-437e-9518-adb32be77984.s3.amazonaws.com%2Fpublic%2Fimages%2F011555c3-fdcb-43e6-b4a4-960ad157bee0_679x255.png

总结一下,SNARK 是首个被成功应用于主流加密货币项目(Zcash)的 ZKP 技术。SNARK 是非常领先的密码学技术,但是可信设置有一定的安全风险。STARK 构建于 SNARK 基础之上,解决了可信设置的问题,创造了一种更具可拓展性的 ZKP,也因此更加复杂,需要更大的 prove size 和更高的 gas 费用。

其实我们无需夸大 SNARK 和 STARK 之间的区别,也无需在二者之间非要分出高低。无论人们选择构建 SNARK 还是 STARK,我们都期待会有有越来越多的人看到 ZKP 的价值。

原文链接 https://cryptoexplainere60.substack.com/p/zk-world-pt-2-zkp

译者:ZK 爱好者

Subscribe to ZK 爱好者
Receive the latest updates directly to your inbox.
Verification
This entry has been permanently stored onchain and signed by its creator.