每日一博 | 三个经典示例解释什么是「零知识证明」

原文：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 一款由密码学专家团队打造的开源隐私计算平台，专注于分享数据安全、密码学、联邦学习、同态加密等隐私计算领域的技术和内容。