零知识证明浅析

文章背景与核心概要

本文从计算机科学和图论的角度出发，带读者深入探讨了零知识证明（Zero-Knowledge Proofs, ZKPs）的底层原理，全程不涉及任何加密货币。受 Goldreich、Micali 和 Wigderson 在 1990 年发表的经典论文启发，作者拆解了证明者（Prover）与验证者（Verifier）如何在不泄露解本身的前提下，向验证者证明自己掌握了 NP 完全问题（具体为图的三染色问题）的解。

文章不仅附带了单轮交互的 Python 代码片段、概率计算公式，还延伸讨论了数独等智力游戏的应用，以及如何通过规约（Reduction）将其他 NP 完全问题转化为图三染色问题，从而揭开交互式证明机制的神秘面纱。

简介 (Introduction)

Chris 上周给我发信息，问我想不想实现零知识证明。我一开始并不感兴趣，但他接着说：

如果我告诉你有一种零知识证明和加密货币毫无关系呢？如果我告诉你它涉及图论呢？如果我告诉你只需要 30 行代码就能实现呢？

这下有意思了。

零知识证明（ZKP）的核心思想是存在两个参与者：证明者和验证者。证明者声称自己拥有某个（通常是 NP 完全的）问题的解。证明者可以在不共享该问题实际解的情况下，让验证者确信这一点。

最经典的例子是图的三染色（3-coloring）。也就是说，证明者声称，对于一个给定的（共享的）图，它有一个合法的 3 染色方案。它希望让验证者相信这一点，同时又不能透露具体的颜色分配方案。

简单回顾一下，图染色问题是指：给定一个图，我们要为每个节点指定一种颜色，使得任意两个相邻节点没有相同的颜色。3 染色则是指最多使用 3 种颜色进行染色。

%0
node [color=black, fillcolor=white, style=filled];
subgraph cluster_0 {
    label = "";
    style = invis;
    0 [fillcolor=red];
    1 [fillcolor=blue];
    0 -- 1;
    2 [fillcolor=green];
    0 -- 2;
    1 -- 2;
    3 [fillcolor=red];
    2 -- 3;
    4 [fillcolor=blue];
    3 -- 4;
    4 -- 0;
}

%0
node [color=black, fillcolor=white, style=filled];
subgraph cluster_0 {
    label = "";
    style = invis;
    0 [fillcolor=red];
    1 [fillcolor=blue];
    0 -- 1;
    2 [fillcolor=green];
    0 -- 2;
    1 -- 2;
    3 [fillcolor=red];
    2 -- 3;
    4 [fillcolor=blue];
    3 -- 4;
    4 -- 0;
}

怎么做到这一点呢？各式各样的博客文章和花哨的演示虽然很有趣，但并不能帮我们理解太多本质。

我和 Chris 兜兜转转了一阵，决定去读一读 Goldreich、Micali 和 Widgerson 的原始论文之一（PDF）。我们其实只读了第 23 页（PDF 中标注为第 713 页），但这已经足够让我们把代码跑起来了。

论文中的协议 (The Paper’s Protocol)

论文中的协议 4 描述了证明者（P，带有编号的步骤）与验证者（V，带有编号的步骤）之间进行交互式 3 染色证明的过程，现重现如下：

公共输入 一个图 G(V, E)（其中 n = |V|, m = |E|）。

以下四个步骤将执行 m² 次，每次使用独立的抛硬币结果。

(P1) 证明者随机选择一个对 φ 诱导出的三个独立集的 3 种颜色的置换，用这个 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² 次迭代，则表示它接受。

我们稍后会回过头来讨论迭代次数。现在，让我们尝试只执行单轮迭代。对于每个步骤，我都会在代码中加上“仅限证明者 (Only prover)”或“仅限验证者 (Only verifier)”的注释，以便清楚地了解谁能看到什么数据。

单轮迭代 (One Iteration)

我们首先勾勒出一个图的结构。对于上面那个 graphviz 示例图，我们有以下边列表数据结构：

# Shared between prover, verifier
edges = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0), (0, 2)]

> # 在证明者和验证者之间共享

列表中的每个元组表示两个编号节点之间的连接。非常巧妙。因为这是一个无向图，所以 (0, 1) 和 (1, 0) 是等价的，因此我们不需要把两边都列出来。我们还可以为它着色：

# Only prover
coloring = {0: "navy", 1: "darkgreen", 2: "crimson", 3: "navy", 4: "darkgreen"}

> # 仅限证明者

每个键是一个节点编号，每个值是一种颜色。

虽然为图找到一个 3 染色方案很慢，但验证一个 3 染色方案很快——其时间复杂度与边的数量呈线性关系。让我们验证一下我们拥有一个合法的示例染色方案：

# For the reader
# Check each edge to make sure no edge has the same color on each node
assert all(coloring[u] != coloring[v] for u, v in edges)
# Check that the total number of colors used is 3
assert len(set(coloring.values())) <= 3

> # 供读者参考 > # 检查每条边，确保没有任何一条边的两个节点颜色相同 > # 检查使用的颜色总数是否为 3

现在我们将逐一执行论文中的步骤，并为每个步骤编写一些配套代码。

提示与技巧 (Tips and Tricks)

如果你正在跟着这篇博客一起写代码，我建议使用 random.seed(0)，这样你的随机性在每次运行程序时都不会改变。如果你在用 hash 函数并且出于同样的稳定性考虑，我还建议将环境变量 PYTHONHASHSEED 设置为 0。

步骤 P1 (Step P1)

我们需要做的第一件事是对现有的着色方案进行置换。也就是说，我们应该在保持 3 染色特性的同时，把颜色值置换调换一下。

值得庆幸的是，这比听起来要简单：颜色的名字对 3 染色本身并没有意义；它们只需要在每条边的两端各不相同即可。因此，如果我们对旧名字和新名字进行双射映射（A 映射到一个 B，且 B 来源于一个 A），这个性质就能保持。

我想出了这个函数，它可以打乱颜色，将它们并排对齐，制作一个对照表，然后利用该表生成一个新的染色方案：

import random

# Only prover
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()}
# For example,
# {0: "crimson", 1: "navy", 2: "darkgreen", 3: "crimson", 4: "navy"}

> # 仅限证明者 > # 例如，

然后我们必须把颜色放进“加锁的盒子”里。对比喻中的锁盒子的一种方法是对其应用单向函数：例如，哈希函数（hash function）。如果我们对每种颜色进行哈希处理，然后只把哈希值传递给验证者，验证者就无法打开它们。

为了简便起见，这个例子使用了 Python 标准库的哈希函数，但在实际应用中，最好使用诸如 hashlib.sha256 这样的密码学哈希函数：

# Only prover. Wrong!
def hash_coloring_wrong(coloring):
    return {node: hash(color) for node, color in coloring.items()}
# For example:
# {0: -6789624683659967261, 1: 7846608853949633950, 2: 6009240650600289446,
#  3: -6789624683659967261, 4: 7846608853949633950}

> # 仅限证明者。错误的做法！ > # 例如：

把这些加锁的盒子交个验证者会带来一个小问题：用相同颜色锁定的两个盒子会产生相同的哈希值。这样验证者就能推断出染色方案了。即便具体的颜色现在被隐藏了，我们希望做到“零知识”保护的恰恰是染色方案的结构。

为了解决这个问题，我们可以向每个节点及其颜色添加所谓的随机数（nonce）。也就是说，每个节点都在哈希中打包了一点随机数据，这样不同节点的 "darkgreen" 哈希值看起来就会各不相同。

# Only prover
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)
# For example:
# {0: "crimson", 1: "navy", 2: "darkgreen", 3: "crimson", 4: "navy"}
boxed_coloring = box_coloring(permuted_coloring)
# For example:
# {0: ("crimson", 33), 1: ("navy", 65), 2: ("darkgreen", 62),
#  3: ("crimson", 51), 4: ("navy", 38)}
hashed_coloring = hash_values(boxed_coloring)
# For example:
# {0: -2275004828450249492, 1: 2227921633151400991, 2: -5024343381376265886,
#  3: -5381005702768533635, 4: 1164729608819214729}

> # 仅限证明者 > # 例如： > # 例如： > # 例如：

同样，你大概率不希望为随机数使用标准库的随机数生成器。你应该考虑使用 secrets 模块（Python 3.6+）中的 secrets.token_hex() 之类的方法。甚至可以考虑使用 hmac 模块。

最后，我们可以将 hashed_coloring 发送给验证者，并开始步骤 V1。

步骤 V1 (Step V1)

由于验证者知道图的结构（但不知道其颜色），它就可以挑选任意一条边进行检查。它想要验证它所挑选的任意一条边是否满足 3 染色条件。它会发送一个针对任意边 e 的检查请求：

# Only verifier
e = random.choice(edges)
revealed = prover_please_reveal_colors(e)

> # 仅限验证者

这隐式地依赖于某些全局状态（证明者知道当前与验证者处于哪个活跃的“会话”中）。如果你有多个验证者、并发会话或其他情况，你可能需要在通信中串联一些上下文标识符。

步骤 P2 (Step P2)

证明者收到此请求后，将发送该边中每个节点的颜色和随机数。

# Only prover
def prover_please_reveal_colors(edge):
    u, v = edge
    return {u: boxed_coloring[u], v: boxed_coloring[v]}
# For example:
# {3: ('crimson', 51), 4: ('navy', 38)}

> # 仅限证明者 > # 例如：

你此时可能会心存疑虑，因为我们确实泄露了关于染色方案的一些信息。

请注意，证明者透露一条边的颜色是可以的，因为 1）每轮中的颜色都已经被重新打乱过了，2）我们将在每次揭晓边的时候（同样也是每轮一次）应用我们的盒子加锁协议，因此验证者在多次迭代之间无法积累任何关于我们颜色的信息。

步骤 V2 (Step V2)

验证者可以检查“颜色 + 随机数”组合的哈希值是否与步骤 P1 中给出的每个节点的哈希值相匹配。这确保了证明者不会在每轮进行到一半时偷偷篡改颜色。这依赖于验证者和证明者使用相同的哈希函数（如果使用 hash，则需要相同的哈希种子）。

# Only verifier
for (node, (color, nonce)) in revealed.items():
    assert hashed_coloring[node] == hash((color, nonce)), f"Hash mismatch!"

> # 仅限验证者

然后，验证者可以检查这两个颜色值是否确实不同。由于证明者无法预知验证者会要求检查哪条边，这种机制赋予了验证者一定的信任度（概率为 1/|E|，因为你现在掌握了一条边的信息），确信该图确实被正确地进行了 3 染色。

如果这两个条件中有任何一个不成立，验证者就会拒绝。

概率 (Probabilities)

为了让验证者真正相信证明者的 3 染色方案，你必须执行好几轮这样的交互。

论文接着断言，“验证者接受的概率（即完成所有 m² 轮且没有检测到‘出问题’的概率）上限为 (1 - m⁻¹)^(m²)”（其中 m = |E|）。这个概率相当不错。对于一个大型图（比如有 1000 条边），这个概率下降得相当快：

m = 1000
for i in range(1, 4600):
    print("(1 - m⁻¹)^round = ", (1 - m**-1)**i)

在 4,600 轮时，“作弊”的可能性降至 1%。在 10,000 轮时，“作弊”的可能性为 0.0045%。而在 m² = 1,000,000 轮时，这个概率低到可以忽略不计。

网络化演示 (A Networked Demo)

在单个进程中运行 Python 代码、并用注释标明“证明者”和“验证者”其实并不是很过瘾。这根本无法排除数据意外泄漏的一丝可能。如果在证明者和验证者之间设置某种隔离屏障——比如进程隔离或网络隔离——那将要带劲得多。

出于这个原因，我和 Chris 准备了一个服务器（证明者）和客户端（验证者）的演示程序。你可以点击“运行一轮 (Run Round)”来执行一轮交互（并展示置换后的颜色）。你可以访问文档页面查看 API 文档并自己构建客户端！

运行一轮 (Run Round)

(如果你在紧挨着这段文字的下方没有看到图，请稍等片刻，服务器正在唤醒中。)

编码其他 NP 完全问题 (Encoding Other NP-Complete Problems)

到目前为止，我们已经展示了如何使用零知识交互式证明来验证某人拥有图的合法 3 染色方案，而不会了解到关于该 3 染色方案的任何信息。那又怎样？我们还能用零知识证明证明其他东西吗？3染色的交互式证明仅仅是一个没有实际应用的刻意设计的派对小把戏吗？

其实……

数独 (Sudoku)

数独谜题是另一个“求解困难但验证容易”的问题的例子。要在 81 个格子中填入数字，同时满足所有行、列和宫（box）都包含数字 1-9 的约束，在算法上是非常困难的，但验证起来却极其迅速。

假设我们想证明我们已经完成了数独，但又不想泄露关于解的半点信息。我们可以执行一个与 3 染色非常相似的交互式证明！我们不置换颜色，而是置换数字。我们不揭晓边，而是揭晓行、列和宫。

下次你的同车乘客靠过来想看你的数独答案时，只需让他们先过完 90,000 个简单步骤就行了！

规约 (Reduction)

假设我们遇到了一个难题并且已经计算出了它的解，但我们手头没有现成的算法来为它执行交互式证明。多亏了前面那篇论文的作者，我们知道只要这个问题是 NP 完全的，就一定存在对应的交互式证明！

我们运用多项式时间规约（polynomial time reduction）的力量。我们（通过某种方式）将我们的解转化为一个图及其 3 染色方案，然后只需遵循上面的步骤和代码即可！其中的“通过某种方式”是最棘手的部分，但关于如何在不同 NP 完全问题之间进行转换的研究已经非常丰富。

例如，你可能想要创建一个零知识证明，证明你知道某个非常大的合数的质因数。不幸的是，对于仅仅两位数的数字，你的图就已经包含数千个节点了，因此规约到 3 染色在实践中是有局限性的，相比之下，你最好采用比规约到 3 染色更复杂的证明技术。

总结 (Wrapping Up)

在做了一些研究之后，我们发现零知识证明最常见的现实世界用例（年龄验证、加密货币等）对我们来说并没有那么吸引人。不过，我们确实很享受图论、计算理论以及网络计算带来的乐趣。希望你在把玩交互式证明时也玩得开心。