三个经典示例解释什么是「零知识证明」

原创
2023/08/29 10:43
阅读数 9.7K

原文:Zero-knowledge proofs explained in 3 examples

作者:Tian Daphne

翻译整理:开放隐私计算 & PrimiHub

零知识证明(Zero-knowledge proof)是一种在不泄露陈述内容的情况下证明陈述有效性的方法。它是一个证明系统使用户能够公开分享知识或所有权的证明,而不揭示其细节。

在密码学中,零知识证明允许用户在不透露秘密内容的情况下,说服其他用户知道某事或已经做过某事,它是迄今为止最强大的密码学工具之一。

下面,我们将深入探讨了零知识证明的概念,并通过几个通俗易懂的示例帮助读者理解它们的工作原理。

一、零知识证明简史

密码学中的零知识首次出现在 1985 年 The knowledge complexity of interactive proof systems [GMR85] 论文中,由先驱者 Shafi Goldwasser、Silvio Micali 和 Charles Rackoff 提出。他们提供了今天广泛使用的零知识证明定义:

“零知识协议是一种方法,通过该方法,一方(证明者)可以向另一方(验证者)证明某个陈述为真,而不揭示任何信息,除了这个特定陈述为真。”

零知识证明必须满足三个性质:

  • 完备性:如果陈述为真,诚实的验证者将被诚实的证明者说服。
  • 严密性:如果陈述为假,没有不诚实的证明者能够说服诚实的验证者。证明系统是诚实的,不允许作弊。
  • 零知识性:如果陈述为真,没有验证者会获得除了这个陈述为真之外的任何信息。

交互式零知识证明要求证明者和验证者进行来回对话,以完成证明。非交互式零知识证明是指证明者向验证者发送单个消息,验证者能够在不需要证明者进一步通信的情况下检查证明的有效性。下图是零知识证明的发展史:

zk-SNARK(Succinct Non-Interactive Arguments of Knowledge) 可能是最流行的零知识证明形式,最早出现在 2011 年的 Bit+11 论文中。到 2013 年,多亏了 Pinocchio PHGR13 论文,零知识证明可以在现实应用中使用,该论文使 zk-SNARKS 适用于一般计算,尽管速度较慢。2016 年提出的 Groth16 算法大大降低了计算复杂性,使 zk-SNARKS 非常高效,至今仍然是标准。

然而,可信设置对于这些零知识协议的安全性至关重要。必须使用初始过程生成加密参数,以便能够运行零知识协议。由第三方执行此操作,以确保加密参数是随机、不可预测和安全的。

随后在 2017 年引入了 Bulletproofs(BBBPWM17),在 2018 年引入了 zk-STARKs(BBHR18)。与前任不同,它们是不需要初始可信设置的范围证明类型。2019 年的 PlonK 论文实现了通用零知识证明算法,这意味着只需要启动一次可信设置,而与之相比,Groth16 需要每个电路都有一个单独的可信设置。

由于领域的发展,零知识证明已经从纯理论过渡到应用,在区块链、安全通信、电子投票、访问控制和游戏中均有实际应用。随着这些技术继续投入商业应用,相信未来将会有更多令人兴奋的发展来推进这项技术。

以下是一些概念性示例,帮助你在不涉及复杂理论和高级数学的情况下,直观地理解不同级别的零知识证明(ZKP)

二、向孩子们解释零知识证明(Lv.1)

瓦利在哪里?

在不泄露秘密信息的情况下证明自己知道某事,可以通过常用的“瓦利在哪里?”示例来说明。

问题:你和朋友想要找到瓦利。

条件:你知道瓦利在图像中的位置,但你的朋友不相信。你如何向朋友证明你知道瓦利在哪里,同时又不泄露他具体的位置?

解决办法:你可以拿出一张大纸,盖住整个图像,通过一个切口向朋友展示瓦利的图像。这样做就可以可以证明你真的知道瓦利的位置,但你的朋友不会获得瓦利的位置,因为相对于图像的确切坐标对他来说仍然是未知的。

这是一个非交互式零知识证明的简单类比。透过孔隙看到瓦利的任何人都能够证明瓦利的存在,以及证明者知道他在哪里,同时又不泄露任何其他信息。

三、向朋友解释零知识证明(Lv.2)

成员证明示例

问题:当你遇到一个不认识的人,但她声称自己也是你所在团队的成员。你如何知道她说的是真的?

解决办法:幸运的是,你的团队有一个带锁的保险箱,只有你的团队成员知道密码,可以打开保险箱。因此,写一条秘密信息并放入锁定的保险箱中。具体步骤如下:

  1. 验证者写一条秘密信息并放入锁定的保险箱中。
  2. 符合要求的证明者具有密码,打开锁定的保险箱。
  3. 证明者将秘密信息交还给验证者。
  4. 验证者确信证明者真的知道保险箱密码,因此可以信任。

如果这个陌生人是如她所说是团队成员,那她就会知道密码。因此,她将能够打开锁定的保险箱,找到你的秘密信息,从而向你证明她确实是你团队的成员。

这是交互式零知识证明的类比。只有真正是该团队的成员才会知道秘密组合代码(密码),能够访问锁定的保险箱,从而在不泄露任何其他信息的情况下证明他的成员资格。

四、向团队解释零知识证明(Lv.3)

不透明定价示例

在这个示例中,你和竞争对手正在从同一供应商购买相同的材料,你想知道每千克是否支付相同的价格。但是,你们之间缺乏足够的信任来透露各自的价格,你还受到不得分享此信息的合同约束。

假设材料的市场价格只能为 100、200、300 或 400 每千克,这种情况下我们可以通过零知识证明来解决上述问题。按照以下步骤操作:

  1. 你和竞争对手想要知道是否支付相同的价格,同时不泄露各自支付的金额。
  2. 假设有 4 个带锁的锁盒(没有钥匙无法打开),每个盒子上标有 100、200、300 和 400 的数字,以及一个只能放一张纸的小插槽,放置于一个安全的私人房间中。
  3. 你首先独自进入房间。由于你每千克支付 200,你拿走了标有 200 的锁盒的钥匙,并摧毁了其他盒子的钥匙,然后你离开房间。
  4. 你的竞争对手独自进入房间,带有 4 张纸,其中 1 张为支票(无具体数额),另外 3 张上面都是叉号。由于你的竞争对手每千克支付 300,他将带有支票的纸张放入标有 300 的锁盒中,并将带有叉号的纸张放入其他锁盒中,最后离开房间。
  5. 在他们离开后,你可以带着只能打开标有 200 盒子的钥匙返回。你会发现一张上面有叉号的纸,现在你知道你的竞争对手没有与你支付相同的金额。
  6. 你的竞争对手回来后,看到你手上有一张上面有叉号的纸,所以现在他们也知道你没有与他们支付相同的金额。

如果你得到一张上面有支票的纸,你俩都会知道你支付相同的金额。由于你得到的纸上有叉号,你俩都知道你没有支付相同的金额,但也不知道对方支付了多少。

你俩离开时只知道你没有支付相同的金额,但你俩都没有获得对方支付了多少的知识。

这是使用原始半范围证明的交互式零知识证明的另一个类比。重要的是要注意,所有这些示例都有限制,并且必须采用某些假设,但它们足够形象地说明了它们的工作方式。

五、最后

这篇文章通过 3 个实例层层递进、简单易懂的解释了零知识证明的概念和原理。

通过了解零知识证明的工作原理,会发现零知识证明并不是魔法。目前它在区块链以及需要敏感信息的各种应用中具有巨大的潜力,例如提供密码证明、身份证明和成员证明。比如:国外某些银行中就有用到零知识证明技术,让他们的客户能够在抵押贷款申请中,证明银行账户中的金额而不泄露具体金额等信息。

PrimiHub 一款由密码学专家团队打造的开源隐私计算平台,专注于分享数据安全、密码学、联邦学习、同态加密等隐私计算领域的技术和内容。

展开阅读全文
加载中
点击加入讨论🔥(6) 发布并加入讨论🔥
打赏
6 评论
14 收藏
3
分享
返回顶部
顶部