原文：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）
成员证明示例
问题：当你遇到一个不认识的人，但她声称自己也是你所在团队的成员。你如何知道她说的是真的？
解决办法：幸运的是，你的团队有一个带锁的保险箱，只有你的团队成员知道密码，可以打开保险箱。因此，写一条秘密信息并放入锁定的保险箱中。具体步骤如下：
- 验证者写一条秘密信息并放入锁定的保险箱中。
- 符合要求的证明者具有密码，打开锁定的保险箱。
- 证明者将秘密信息交还给验证者。
- 验证者确信证明者真的知道保险箱密码，因此可以信任。
如果这个陌生人是如她所说是团队成员，那她就会知道密码。因此，她将能够打开锁定的保险箱，找到你的秘密信息，从而向你证明她确实是你团队的成员。
这是交互式零知识证明的类比。只有真正是该团队的成员才会知道秘密组合代码（密码），能够访问锁定的保险箱，从而在不泄露任何其他信息的情况下证明他的成员资格。
四、向团队解释零知识证明（Lv.3）
不透明定价示例
在这个示例中，你和竞争对手正在从同一供应商购买相同的材料，你想知道每千克是否支付相同的价格。但是，你们之间缺乏足够的信任来透露各自的价格，你还受到不得分享此信息的合同约束。
假设材料的市场价格只能为 100、200、300 或 400 每千克，这种情况下我们可以通过零知识证明来解决上述问题。按照以下步骤操作：
- 你和竞争对手想要知道是否支付相同的价格，同时不泄露各自支付的金额。
- 假设有 4 个带锁的锁盒（没有钥匙无法打开），每个盒子上标有 100、200、300 和 400 的数字，以及一个只能放一张纸的小插槽，放置于一个安全的私人房间中。
- 你首先独自进入房间。由于你每千克支付 200，你拿走了标有 200 的锁盒的钥匙，并摧毁了其他盒子的钥匙，然后你离开房间。
- 你的竞争对手独自进入房间，带有 4 张纸，其中 1 张为支票（无具体数额），另外 3 张上面都是叉号。由于你的竞争对手每千克支付 300，他将带有支票的纸张放入标有 300 的锁盒中，并将带有叉号的纸张放入其他锁盒中，最后离开房间。
- 在他们离开后，你可以带着只能打开标有 200 盒子的钥匙返回。你会发现一张上面有叉号的纸，现在你知道你的竞争对手没有与你支付相同的金额。
- 你的竞争对手回来后，看到你手上有一张上面有叉号的纸，所以现在他们也知道你没有与他们支付相同的金额。
如果你得到一张上面有支票的纸，你俩都会知道你支付相同的金额。由于你得到的纸上有叉号，你俩都知道你没有支付相同的金额，但也不知道对方支付了多少。
你俩离开时只知道你没有支付相同的金额，但你俩都没有获得对方支付了多少的知识。
这是使用原始半范围证明的交互式零知识证明的另一个类比。重要的是要注意，所有这些示例都有限制，并且必须采用某些假设，但它们足够形象地说明了它们的工作方式。
五、最后
这篇文章通过 3 个实例层层递进、简单易懂的解释了零知识证明的概念和原理。
通过了解零知识证明的工作原理，会发现零知识证明并不是魔法。目前它在区块链以及需要敏感信服务器托管网息的各种应用中具有巨大的潜力，例如提供密码证明、身份证明和成员证明。比如：国外某些银行中就有用到零知识证明技术，让他们的客户能够在抵押贷款申请中，证明银行账户中的金额而不泄露具体金额等信息。
PrimiHub 一款由密码学专家团队打造的开源隐私计算平台，专注于分享数据安全、密码学、联邦学习、同态加密等隐私计算领域的技术和内容。
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
