零知识证明：就像魔法，但我会解释它

假设佩吉需要向维克多证明她拥有一个秘密而不泄露这个秘密。她能否让维克多相信她确实知道这个秘密？这是我们可以在身份系统中使用的最强大的加密过程之一的核心问题： 零知识证明（ZKP） 。

例如，假设 Peggy 拥有数字驾驶执照，并且想要向酒保 Victor 证明她已经超过 21 岁，而无需交出驾驶执照，甚至不需要向他出示她的出生日期。 ZKP 允许 Peggy 证明她的驾驶执照说她至少 21 岁，这可以让 Victor 信服，而 Peggy 无需透露任何其他信息（即，多余知识为零）。

麻省理工学院的研究人员 Shafi Goldwasser、Silvio Micali 和 Charles Rackoff 在 20 世纪 80 年代首次探讨了这个问题，作为防止信息泄露的一种方法。目标是减少验证者 Victor 可以了解的关于证明者 Peggy 的额外信息量。

了解 ZKP 工作原理的一种方法是阿里巴巴洞穴的故事，该故事最初由密码学家 Quisquater、Guillou 和 Berson1 发表。下图提供了说明。

阿里巴巴洞有两条通道，分别标记为 A 和 B，它们分开一条与入口相连的通道。佩吉拥有一个密码，可以打开连接 A 和 B 的门。维克多想购买该密码，但只有在确定佩吉知道密码后才会付款。在维克多付钱之前，佩吉不会与他分享。

Peggy 证明她知道代码的算法如下：

• 维克多站在洞穴外，佩吉进入并选择其中一条通道。维克多不被允许看到佩吉走哪条路。
• 维克多进入洞穴并随机喊出“A”或“B”。
• 佩吉从正确的通道出现，因为无论她进入时做出哪种选择，她都可以轻松地打开门。
• 当然，佩吉可能只是运气好，猜对了，所以佩吉和维克多多次重复了这个实验。

如果佩吉总能从维克多选择的任何一条通道回来，那么佩吉真正知道密码的可能性就会增加。经过 20 次尝试后，佩吉只是猜测维克多会叫哪个字母的可能性不到百万分之一。这构成了佩吉知道这个秘密的概率证明。

该算法不仅可以让 Peggy 说服 Victor 她知道代码，而且可以确保 Victor 无法说服其他任何人 Peggy 知道代码。假设 Victor 记录了整个交易。观察者唯一看到的是维克多喊出字母，佩吉从右边的隧道中出现。观察者无法确定维克多和佩吉是否事先就字母顺序达成一致以欺骗观察者。

因此，虽然佩吉不能向维克多否认她知道这个秘密，但她可以向其他第三方否认她知道这个秘密。这确保了她向维克多证明的任何东西都留在他们之间，维克多不能泄露它——至少以密码方式证明它来自佩吉。佩吉保留了对她的秘密和她知道的事实的控制权。

当我们说“零知识”并谈论维克多除了所讨论的命题之外什么也没学到时，这并不完全正确。在阿里巴巴的洞穴里，佩吉以零知识证明她知道这个秘密。但维克多还了解到佩吉的许多其他事情，ZKP对此无能为力。例如，维克多知道佩吉可以听到他的声音、说他的语言、走路并且合作。他还可能了解有关洞穴的信息，例如打开门大约需要多长时间。佩吉从维克多身上也了解到类似的事情。因此，现实情况是，证明大约是零知识，而不是完全零知识。

ZKP系统

阿里巴巴Cave的例子是ZKP的一个非常具体的使用，即所谓的知识的零知识证明。佩吉正在证明她知道（或拥有某些东西）。更一般地说，佩吉可能想向维克多证明许多事实。这些可能包括命题短语甚至价值观。 ZKP 也可以做到这一点。

要理解如何在零知识中证明命题，请考虑一个不同的例子，有时称为社会主义百万富翁问题。假设佩吉和维克多想知道他们是否得到了公平的工资。具体来说，他们想知道自己的工资是否相同，但不想向彼此甚至可信的第三方透露他们的具体小时费率。在这种情况下，佩吉并没有证明她知道一个秘密，而是证明了一个平等（或不平等）的命题。

为简单起见，假设 Peggy 和 Victor 的工资为每小时 10 美元、20 美元、30 美元或 40 美元之一。

该算法的工作原理如下：

• 佩吉买了四个带锁的盒子，并给它们贴上 10 美元、20 美元、30 美元和 40 美元的标签。
• 她扔掉了每个箱子的钥匙，除了标有她工资的箱子之外。
• 佩吉把所有上锁的盒子交给维克多，维克多私下将一张带有“+”的纸条放入盒子顶部标有他工资的插槽中。他在所有其他盒子里放了一张带有“-”的纸条。
• 维克多把盒子还给佩吉，佩吉私下用她的钥匙打开了盒子，上面有她的工资。
• 如果她找到“+”，那么他们就赚到相同的金额。否则，他们的金额会有所不同。她可以用这个来向维克多证明事实。

这称为不经意转移，并在零知识（即不透露任何其他信息）的情况下证明命题VictorSalary = PeggySalary true 或 false。

为此，佩吉和维克多必须相信对方会主动说出他们的真实工资。维克多需要相信佩吉会扔掉另外三把钥匙。佩吉必须相信维克多只会将一张带有“+”的纸条放入盒子中。

就像数字证书需要 PKI 来建立超出仅使用自颁发证书所能实现的信任一样，ZKP 在允许 Peggy 和 Victor 能够从别人对他们的评价中证明事实的系统中更加强大，而不仅仅是他们所说的他们自己。例如，假设佩吉和维克多不是自行断言自己的工资，而是可以依靠人力资源部门签署的文件来进行断言，以便双方都知道对方正在陈述自己的真实工资。可验证的凭证提供了一个使用 ZKP 单独或协同证明许多不同事实的系统，从而使人们对方法充满信心并信任数据。

非交互式 ZKP

在前面的示例中，佩吉能够通过一系列交互向维克多证明事情。为了使 ZKP 实用，证明者和验证者之间的交互应该最小化。幸运的是，一种称为 SNARK 的技术允许非交互式零知识证明。

SNARK具有以下属性（它们的名称由此而来）：

• 简洁：与实际证明的长度相比，消息的大小很小。
• 非交互式：除了一些设置之外，证明者仅向验证者发送一条消息。
• 论证：这实际上是一个关于某件事是正确的论证，而不是我们在数学上理解的证明。具体来说，理论上，只要有足够的计算能力，证明者就可以证明错误的陈述。因此，SNARK 是“计算上合理的”而不是“完美合理的”。
• 知识：证明者知道所讨论的事实。

您通常会看到前面加上“zk”（零知识），表明在这个过程中，验证者除了被证明的事实之外什么也不知道。

zkSNARKs 的数学基础涉及高次多项式的同态计算。但我们可以理解 zkSNARK 的工作原理，而无需了解确保其健全的底层数学原理。如果您想了解更多数学细节，我推荐Christian Reitwiessner 的“zkSNARKs in a Nutshell” 。

举一个简单的例子，假设 Victor 被赋予了某个值的sha256哈希值H 。 Peggy 想要证明她知道一个值s ，使得sha265(s) == H而又不向 Victor 透露s 。我们可以定义一个函数C来捕获这种关系：

 C(x, w) = ( sha256(w) == x )

因此， C(H, s) == true ，而w的其他值将返回false 。

计算 zkSNARK 需要三个函数G 、 P和V 。 G是密钥生成器，它采用名为lambda秘密参数和函数C并生成两个公钥：证明密钥pk和验证密钥vk 。对于给定的函数C ，它们只需要生成一次。在此步骤之后必须销毁参数lambda ，因为不再需要它，并且任何拥有它的人都可以生成假证明。

证明者函数P将证明密钥pk 、公共输入x和私有（秘密）见证人w作为输入。执行P(pk,x,w)的结果是证明prf ，证明者知道满足C的w值。

验证器函数V计算V(vk, x, prf)如果证明prf正确，则 V(vk, x, prf) 为 true，否则为 false。

回到 Peggy 和 Victor，Victor 选择一个函数C代表他希望 Peggy 证明的内容，创建一个随机数lambda ，然后运行G来生成证明和验证密钥：

 (pk, vk) = G(C, lambda)

Peggy 不得学习lambda的值。 Victor 与 Peggy 共享C 、 pk和vk 。

Peggy 想要证明她知道满足C （对于x = H的s值。她使用这些值作为输入运行证明函数P ：

 prf = P(pk, H, s)

Peggy 将证明prf提交给运行验证函数的 Victor：

 V(vk, H, prf)

如果结果为真，则 Victor 可以确信 Peggy 知道值s 。

函数C不需要像我们在本示例中所做的那样仅限于哈希。在基础数学的限制内， C可能非常复杂，并且涉及 Victor 希望 Peggy 一次性证明的任意数量的值。

本文摘自我的书《学习数字身份》 ，由 O'Reilly Media 出版。

笔记

1. 让·雅克·基奎特；吉尤，路易斯·C.；托马斯·A·博森 (1990)。如何向您的孩子解释零知识协议 (PDF)。密码学进展 – CRYPTO '89：会议记录。计算机科学讲义。 435。第628-631页。 doi：10.1007/0-387-34805-0_60。 ISBN 978-0-387-97317-3。