什么是零知识证明?|ZK 科普系列(一)
December 26th, 2021

近来,我们在国外社区看到越来越多关于 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.
More from ZK 爱好者

Skeleton

Skeleton

Skeleton