快速了解零知识证明

# 快速了解零知识证明 来源：https://bernsteinbear.com/blog/zkp/ *注意：这与加密货币无关。我不关心加密货币。* 克里斯（https://www.chrisgregory.me/）前几周联系我，问我是否想实现零知识证明。我起初并不感兴趣，但后来他说道： > 如果我告诉你有一种版本的零知识证明与加密货币完全无关，你会怎么想？如果我告诉你它涉及图论呢？如果我告诉你其实现只需要30行代码呢？ 这*确实*引起了我的兴趣。 零知识证明（ZKP）的核心思想是涉及两方：证明者和验证者。证明者声称其对某个（通常是NP完全）问题有解决方案。证明者可以在不分享实际解决方案的情况下让验证者信服这一点。 经典的例子是对图进行3着色。即证明者声称对于给定的（共享）图，其有一个有效的3着色方案。它希望让验证者信服这一点，而不透露实际的颜色分配。 > 简单回顾一下，图着色问题是指给定一个图，我们找到一种为每个节点分配颜色的方式，使得任意两个相邻节点的颜色都不同。3着色是指使用最多3种颜色进行着色。 如何做到这一点呢？各种博客文章和花哨的演示很有趣，但并未帮助我们真正理解。 克里斯和我来回讨论了一段时间，最终决定查阅一篇原始论文（PDF）——Goldreich、Micali和Widgerson的论文（https://dl.acm.org/doi/pdf/10.1145/116825.116852）。我们主要只阅读了第23页（在PDF中标为713页），但这足以让我们开始行动。 ## 论文中的协议 论文中的协议4描述了证明者（P，步骤带编号）和验证者（V，步骤带编号）之间的交互式3着色验证会话，复述如下： > *公共输入*一个图`G(V, E)`（`n = |V|`，`m = |E|`）。以下四个步骤执行`m²`次，每次使用独立的随机比特。（P1）证明者随机选择一个由`φ`导出的三个独立集的三色分配，使用此3着色为图着色，并将这些颜色放入`n`个上锁的盒子中，每个盒子标有相应顶点的编号。更具体地说，证明者随机选择一个置换`π ∈_R S₃`，将`π(φ(i))`放入标记为`i`的盒子（∀`i ∈ V`），锁住所有盒子并将它们（不带钥匙）发送给验证者。（V1）验证者随机选择一条边`e ∈_R E`并将其发送给证明者。（直观上，验证者要求检查`e ∈ E`端点的颜色。）（P2）如果`e = (u, v) ∈ E`，则证明者通过发送`u`和`v`盒子的钥匙来揭示`u`和`v`的颜色。否则，证明者什么也不做。（V2）验证者使用收到的钥匙打开`u`和`v`的盒子，检查它们是否包含`\{1, 2, 3\}`中两个不同的元素。如果钥匙与盒子不匹配，或内容违反条件，则验证者*拒绝*并停止。否则，验证者继续进行下一轮迭代。如果验证者已完成所有`m²`轮迭代，则*接受*。 我们会回过头来讨论迭代次数。现在，让我们先尝试仅进行*一次*迭代。对于每个步骤，我将在代码中用“仅证明者”或“仅验证者”来标注，以明确谁能看到哪些数据。 ## 单次迭代 我们首先概括一下图的含义。对于上面的示例graphviz图，我们有以下边列表数据结构： ``` # 证明者和验证者共享 edges = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0), (0, 2)] ``` 列表中的每个元组表示两个编号节点之间的连接。挺简单的。因为这是一个无向图，`(0, 1)`与`(1, 0)`含义相同，所以我们不必两者都包含。我们也可以给它着色： ``` # 仅证明者 coloring = {0: "海军蓝", 1: "深绿", 2: "深红", 3: "海军蓝", 4: "深绿"} ``` 每个键是节点编号，每个值是颜色。 虽然找到图的3着色很慢，但验证一个着色方案很快——时间复杂度与边数成线性关系。让我们验证一下我们是否有有效的示例着色： ``` # 供读者参考 # 检查每条边，确保边上没有相同的颜色 assert all(coloring[u] != coloring[v] for u, v in edges) # 检查使用的总颜色数是否为3 assert len(set(coloring.values())) <= 3 ``` 现在，我们将逐步进行论文中的步骤，并为每个步骤编写一些配套代码。 ### 技巧与提示 如果你正在边看博客边实践，我建议使用`random.seed(0)`，这样你的随机性在程序多次运行时不会改变。如果你使用`hash`函数，出于同样的稳定性原因，我也建议将环境变量`PYTHONHASHSEED`设置为`0`。 ### 步骤 P1 我们需要做的第一件事是置换我们现有的着色方案。也就是说，我们应该在保持3着色特性的前提下，交换颜色值。 幸运的是，这比听起来更容易：颜色的名称对3着色来说没有意义；它们只需要在边上不同即可。因此，如果我们从旧名称到新名称做一个双射（A映射到某个B，而B来自某个A）映射，这个条件就能保持。 我想出了这个函数来打乱颜色，将它们并排放置，制成一个表格，然后用它来生成新的着色： ``` import random # 仅证明者 def permute_three_coloring(coloring): all_colors = list(set(coloring.values())) new_colors = random.sample(all_colors, len(all_colors)) permutation = {old: new for old, new in zip(all_colors, new_colors)} return {node: permutation[color] for node, color in coloring.items()} # 例如， # {0: "深红", 1: "海军蓝", 2: "深绿", 3: "深红", 4: "海军蓝"} ``` 然后我们必须将颜色放入“上锁的盒子”。比喻性地锁住盒子的一种方法是应用一个单向函数：例如，哈希函数。如果我们对每个颜色进行哈希，然后只将哈希值传递给验证者，验证者就无法打开它们。 这个例子为了简洁使用了Python标准库的哈希函数，但可能最好使用像`hashlib.sha256`这样的密码学哈希函数： ``` # 仅证明者。错误的做法！ def hash_coloring_wrong(coloring): return {node: hash(color) for node, color in coloring.items()} # 例如： # {0: -6789624683659967261, 1: 7846608853949633950, 2: 6009240650600289446, # 3: -6789624683659967261, 4: 7846608853949633950} ``` 但将这些上锁的盒子交给验证者有一个问题：用相同颜色锁住的两个盒子会有相同的哈希值。验证者将能够知道着色方案。即使确切的颜色现在被隐藏了，但我们实际上想放弃零知识的，正是着色的*结构*。 为了解决这个问题，我们可以为每个节点及其着色添加所谓的*随机数*。也就是说，每个节点获得一点随机数据打包到哈希中，这样不同节点的`"深绿"`哈希值看起来就不同了。 ``` # 仅证明者 def nonce(): return random.randrange(100) def box_coloring(coloring): return {node: (color, nonce()) for (node, color) in coloring.items()} def hash_values(coloring): return {k: hash(v) for (k, v) in coloring.items()} permuted_coloring = permute_three_coloring(coloring) # 例如： # {0: "深红", 1: "海军蓝", 2: "深绿", 3: "深红", 4: "海军蓝"} boxed_coloring = box_coloring(permuted_coloring) # 例如： # {0: ("深红", 33), 1: ("海军蓝", 65), 2: ("深绿", 62), # 3: ("深红", 51), 4: ("海军蓝", 38)} hashed_coloring = hash_values(boxed_coloring) # 例如： # {0: -2275004828450249492, 1: 2227921633151400991, 2: -5024343381376265886, # 3: -5381005702768533635, 4: 1164729608819214729} ``` 再次强调，你可能不想使用标准库的随机数生成器来生成你的随机数。你应该考虑使用`secrets`模块（Python 3.6+）中的`secrets.token_hex()`之类的东西。甚至可以考虑使用`hmac`模块。 最后，我们可以将`hashed_coloring`发送给验证者，并开始步骤V1。 ### 步骤 V1 由于验证者知道图（但不知道其颜色），它可以任意选择一条边来检查。它想验证所选的任意边是否满足3着色条件。它发出请求，要求检查任意边`e`： ``` # 仅验证者 e = random.choice(edges) revealed = prover_please_reveal_colors(e) ``` 这隐式地依赖于一些全局状态（证明者知道与验证者哪个“会话”是活跃的）。如果你有多个验证者或并发会话，你可能需要在通信中传递一些上下文标识符。 ### 步骤 P2 证明者收到此请求后，发送边上每个节点的颜色和随机数。 ``` # 仅证明者 def prover_please_reveal_colors(edge): u, v = edge return {u: boxed_coloring[u], v: boxed_coloring[v]} # 例如： # {3: ('深红', 51), 4: ("海军蓝", 38)} ``` 你此时可能有些怀疑，因为我们泄漏了一些关于着色方案的信息。 请注意，证明者揭示一条边的颜色是可以的，因为1）颜色在每一轮都被重新置换过，2）我们将在*每次揭示一条边时*（同样每轮一次）应用我们的盒子上锁协议，因此验证者在各轮迭代之间不会累积关于颜色的任何信息。 ### 步骤 V2 验证者可以检查颜色+随机数的哈希值是否与步骤P1中为每个节点提供的哈希值匹配。这确保了证明者没有在轮次中途更改颜色。这依赖于验证者和证明者使用相同的哈希函数（如果使用`hash`，则使用相同的哈希种子）。 ``` # 仅验证者 for (node, (color, nonce)) in revealed.items(): assert hashed_coloring[node] == hash((color, nonce)), "哈希不匹配！" ``` 验证者然后可以检查两个颜色值是否不同。这给出了少量的可信度（`1/|E|`，因为你现在知道一条边的信息），表明图已被适当3着色，因为证明者无法知道验证者会想要检查哪条边。 如果这两个条件中任何一个不满足，验证者*拒绝*。 ## 概率 验证者必须执行至少几轮这样的操作，才会相信证明者关于3着色的声明。 论文接着断言，“验证者接受的概率（即，完成所有`m²`轮而没有检测到‘出问题’）的上界是`(1 - m⁻¹)^(m²)`”（其中`m = |E|`）。这相当不错。对于一个大图（比如，1000条边），这个概率下降得相当快： ``` m = 1000 for i in range(1, 4600): print("(1 - m⁻¹)^round = ", (1 - m**-1)**i) ``` 在4600轮时，“作弊”的可能性降到1%。在10,000轮时，降至0.0045%。在`m² = 1,000,000`轮时，这个概率*非常低*。 ## 网络化演示 编写在单进程运行的Python代码，用注释标明“证明者”和“验证者”，这并不令人满意。它丝毫不能防止意外的数据泄漏。如果证明者和验证者之间存在某种屏障，比如进程屏障或网络屏障，那会令人满意得多。 因此，克里斯和我准备了一个服务器（证明者）和客户端（验证者）演示。你可以点击“运行轮次”来运行一轮（并显示置换后的颜色）。你可以访问文档页面（https://zkp-3color-demo.fly.dev/docs）查看API文档并自己构建客户端！ *（如果你在此消息下方看不到图表，请稍等片刻让服务器唤醒。）* ## 编码其他NP完全问题 到目前为止，我们已经展示了如何使用零知识交互式证明来验证某人是否拥有图的有效3着色，而*不*透露关于3着色的*任何*信息。那又怎样？我们还能用零知识证明什么吗？3着色的交互式证明只是一个没有实际应用的、人为设计的把戏吗？ 嗯... ### 数独 数独谜题是另一个难以求解但容易验证的问题的例子。填满81个方格以满足所有行、列和宫包含数字1-9的约束在算法上是困难的，但验证者可以非常快速地检查。 假设我们想证明我们完成了一个数独，但我们不想透露关于解的任何信息。我们可以执行一个与3着色非常类似的交互式证明！我们不是打乱颜色，而是打乱数字。我们不是揭示边，而是揭示行、列和宫。 下次你的同车乘客探过头来看你的数独解时，只需要求他们先完成90,000个简单的步骤！ ### 归约 假设我们有一个困难问题并已计算出解决方案，但我们手头没有明显的算法来执行其交互式证明。感谢上述论文的作者，我们知道如果问题是NP完全的，那么它就存在一个交互式证明！ 我们利用多项式时间归约的能力。我们（以某种方式）将我们的解决方案转换为图及其3着色，然后只需遵循上述步骤和代码！“某种方式”是棘手的部分，但关于不同NP完全问题之间转换的研究很多。 例如，你可能想创建一个零知识证明，证明你知道一个非常大的合数的素数因子。不幸的是，对于仅仅两位数的数字，你的图就有数千个节点，因此在实践中归约到3着色有其局限性，使用比归约到3着色更复杂的证明技术可能更好。 ## 总结 经过一些研究，我们确定零知识证明最常见的现实世界用例（年龄验证、加密货币等）对我们来说并不特别有趣。不过，我们喜欢图、计算理论和网络计算。我们希望你也喜欢玩交互式证明。