密码学 - ZK纪事：Sum-Check

为了获得更具互动性的体验，请在我的个人博客 Arkana 上阅读本文。

现在我们已经掌握了有限域和多项式，是时候看看我们的第一个证明系统了。耶！

事实上，我们即将展示的工具乍一看可能有点毫无意义。当孤立地研究它时，会感觉像是一种极其复杂的方式来执行一个非常简单的任务。

但不要因此而气馁！事实上，这个工具极其重要，原因妙不可言：许多我们想要证明的问题都可以简化为我们即将揭示的一个版本。

因此，我恳请大家以开放的心态来阅读今天的文章。将今天的主题视为我们获得有用证明系统的道路上的又一个垫脚石。

我保证，事情很快就会开始变得清晰起来。相信这个过程！

好吧！期望很高，所以我们不要浪费时间。让我们来谈谈 sum-check 协议。

开始

作为对我们第一次相遇的简短回顾，我们想要做的是构建某种证明系统，以证明某些计算的结果是有效的，并且理想情况下，所用的时间要少于计算本身。

好的，那么…… 我们在谈论什么样的计算？

到目前为止，我们的工具包只包括多项式。以这些为基础，我们可以尝试想出表示有用计算的方法——我们可以证明的那种。

好的，那我们先从小处着手。取某个单变量多项式 $P(X)$。也许我们能做的最简单的事情就是在某个点评估它。就此而言，我想指出的是，在评估时，有两个特殊的点具有有趣的特性：0 和 1。

思考一下：当 X = 0 时，所有包含 X 的项都会消失，只留下没有 X 的项。这通常被称为常数项或零次系数。

同样，在 X = 1 处评估多项式，只会得到多项式中所有系数的和！

从本质上讲，这些点很好，因为我们不需要花时间计算 $X$ 的任何幂。当然，我们可以使用任何其他的点，但这些点正好很方便，并且对今天的构造非常重要。

我知道。这不是最有趣的东西，但这是一个开始。

耶……

接下来我们可以尝试的是将评估结果加在一起。例如，我们可以有：

$P(0) + P(1) = k$

其中 $k$ 是某个域元素。由于我们之前陈述的原因，直接执行这个计算非常容易：评估非常简单。看来我们并没有取得多大进展——毕竟，我们说过，只有当验证时间与计算工作量相比有真正收益时，证明结果才有意义。

在这里，计算非常简单，以至于尝试构建一个单独的验证算法有点荒谬。

我的意思是，看看上面的表达式！

那么，我们如何提高难度呢？

加大难度

如果我们的起点是一个多元多项式，会发生什么？就像这样：

$g(X_1, X_2, X_3,…,X_v)$

现在我们开始讨论了。

在评估复杂度方面，我们与之前的情况几乎相同：在变量值为 0 和 1 时评估这些多项式非常简单。

但是当我们考虑组合学时，情况会发生变化。由于我们现在有 v 个变量，并且每个变量可以是 0 或 1，因此我们现在有 $2^v$ 种可能的组合要评估！

这些点，表示为集合 {0,1}ᵛ，形成了所谓的 布尔超立方体。

计算这个和确实需要更多的工作：

$H = \sum_{b1 \in {0,1}} \sum{b2 \in {0,1}}\cdots\sum{b_v \in {0,1}} g(b_1, b_2, …, b_v)$

用 Big O 术语来说，我们可以说计算 $H$ 需要指数时间 $O(2^v)$。这意味着至少需要 $2^v$ 次评估。

我假设你熟悉这个符号，但作为一个简短的解释，它所做的是根据表达式中增长最快的项来表达复杂度。

随着变量值的增加，所述项的增长速度将比其他项更快（更重要），使得与每个其他项相比，其他每个项都可以忽略不计。

因此，例如，取 2X² + X。随着 X 变大，X² 的增长速度比 X 快得多 —— 并且很快，X² 将比 X 大得多。因此，我们说表达式的复杂度为 O(X²)。请注意，我们忽略了乘法因子，因为它们不影响函数的行为 —— 它们只会缩放它。

对于非常大的 $v$ 值，指数时间可能非常长。

对于我可怜的电脑来说，时间太长了，但对于拥有重型硬件的人来说，可能并非如此。

是啊…… 这行不通

在这种情况下，尝试制造一种算法来快速验证某个声明的结果 确实 是有意义的。

而这正是 sum-check 协议的目标！

让我们看看它是如何工作的。

协议

协议 只是一个步骤序列，由各方之间交互期间必须遵循的规则定义。这正是我们的情况：证明者和验证者将以一种非常特殊的方式互动。

我们即将提出的这个协议的优点在于它的递归 性质。

计划是这样的：我们将首先解释单个轮次是如何工作的。一旦我们完成了这一点，就会立即清楚地看到，要继续前进，我们将不得不进行另一轮这样的轮次。每轮都会对问题进行某种程度的简化，直到我们剩下一个非常容易检查的条件。

很简单，对吧？

哇，哇，冷静…… 好的，一步一步来。

Sum-Check 轮次

设置如下：证明者声称已经计算了在 ${0,1}^v$ 上多项式 $g(X₁, X₂,…, Xᵥ)$ 的和 $C$。 他们的目标是说服验证者 $C$ 是正确的结果。

为此，证明者将做一些看起来很奇怪的事情：$g$ 的部分和。

$g_1(X1) = \sum{(x_2, …, x_v) \in {0,1}^{v-1}} g(X_1, x_2, …, x_v)$

如果你仔细观察，你会注意到我们没有包括第一个变量 $X₁$ 的计算。 因此，结果是一个新的多项式 —— 具体来说，是一个单变量多项式。

信不信由你，这是他们必须做的全部。 证明者可以将 $C$ 和 $g₁(X₁)$ 发送给验证者，有了这些值，验证者可以轻松检查以下等式：

$C = g_1(0) + g_1(1)$

显然，如果 $C$ 被正确计算，则该等式应该成立（如果不相信，请随时自己检查！）。 因此，如果此测试通过，我们就完成了！ 验证者可以自信地说 $C$ 是正确的！

或者... 他们可以这样做吗？

天堂里的问题

实际上，这种推理存在一个关键问题 —— 这也是我们在前进的过程中需要始终牢记的考虑事项。 我们之前说过这一点，但我会再次用大写字母说出来，这样你们就永远不会忘记：

证明者可能在撒谎

他们会隐瞒什么呢？ 好吧，他们可以隐瞒一切 —— 但在这种情况下，他们没有太多选择：他们要么不知道 $g$，要么隐瞒 $C$ 的值。

因此，假设证明者想要说服验证者某个值 $C^*$ 是正确的结果，但实际上是不正确的。 他们会怎么做？

他们可以控制的几乎唯一的旋钮是多项式 $g₁(X₁)$。 如果你考虑一下，没有任何东西可以阻止证明者制作一个简单的多项式 $g₁^*$，以便通过验证者的检查！

$C^ = g_1^(0) + g_1^*(1)$

这甚至不会太难！

就目前的情况而言，该算法将无法工作。 我们需要一种方法来检查 $g₁(X₁)$ 是否已正确计算。

让我们花点时间思考一下我们的选择。 当然，验证者不能相信证明者的话。 而 $g₁(X₁)$ 只是一个多项式 —— 我们能做的就是评估它在某个点的值。

等等…… 如果我们在某个随机点 $r₁$ 评估 $g₁(X₁)$ 会发生什么？

$g_1(r1) = \sum{(x_2, …, x_v) \in {0,1}^{v-1}} g(r_1, x_2, …, x_v) = C_2$

你看到了吗？ 一个小小的奇迹在我们眼前展开：我们回到了起点！

嗯？

是的，对不起。 让我解释一下。

一旦我们选择并确定了一个随机点 $r₁$，评估 $g₁(r₁)$ 实际上是对简化的布尔超立方体求和。 好像我们正在用另一个函数 $g’$ 替换原始函数 $g$，并且变量少了一个：

$g’(X_2, …, X_v) = g(r_1, X_2, …, X_v)$

现在，我们可以问同一个原始问题：我们能否证明 $g$ 的这个简化版本在简化的布尔超立方体上的和为 $C₂$？

而妙处在于，另一轮 sum-check 就能解决问题！

全貌

我想说的是，我们可以以递归方式 一遍又一遍地 执行此操作，在每一轮中将 $g$ 中的变量数量减少一个。 因此，在 $v$ 轮之后，我们将只剩下一个 $g$ 的单个评估。

在结束之前，我相信通过一个简单的例子来看看到底是怎么做的会很有帮助。

例如，取这个 4 次的多项式：

$g(X_1, X_2, X_3, X_4) = X_1X_4 + X_2X_4 + X_3X_4$

这个多项式必须在某个有限域上定义，所以让我们选择一个简单的，比如 𝔽₁₃。

首先，证明者将计算布尔超立方体 ${0,1}⁴$ 上的和。

这总共加起来是 16 个评估！

你可以随意自己进行计算 —— 但本着查看证明系统实际运作的精神，让我们假设证明者声称结果为 $C₁ = 12$。

证明者还发送多项式 $g₁(X₁)$，并声称它是 $4X₁ + 4$。 然后，验证者只需检查：

$g_1(0) + g_1(1) = 4 + 8 = 12$

好的，第一轮，完成。 现在验证者选择一个随机值 $r₁$。 假设该值为 $r₁ = 5$。

然后，证明者计算 $C₂$，结果恰好为 $C₂ = 11$。 所以现在，证明者必须计算这里的这个多项式：

$g_2(X2) = \sum{(x_3, x_4) \in {0,1}²} g(r_1, X_2, x_3, x_4)$

结果是 $g₂(X₂) = 2X₂ + 11$。

我们可以很容易地计算出这一点，因为作为证明者，我们知道原始的 g。

如果我们不知道 g，那么这个随机选择的 r₁ 已经会让我们的生活变得艰难！ 这种类型的“挑战”互动非常重要，我们稍后会将其形式化。

好的！ 现在我们检查是否：

$g_2(0) + g_2(1) = 11$

尽管结果似乎是错误的（我们得到 24），但一旦我们记住我们正在有限域上工作，一切都变得清晰起来，所以 $24 \mod 13 = 11$。

对于第三轮和第四轮，我们只需冲洗并重复。 为了简洁起见，我将只总结步骤：

• 验证者选择 $r₂ = 3$。
• 证明者响应 $C₃ = 4$ 和 $g₃(X₃) = X₃ + 8.$
• 验证者检查 $g₃(0) + g₃(1) = 4$，并选择 $r₃ = 7.$
• 证明者响应 $C₄ = 2$ 和 $g₄(X₄) = 2X₄.$
• 验证者检查 $g₄(0) + g₄(1) = 2$，并选择 $r₄ = 2$。

完整的过程如下所示：

到目前为止，一切都进展顺利。 但是我们有一个小问题：我们的变量用完了！

咦？

闭环

没错 —— 原始多项式无法进一步简化。 验证者收到了 $g₄(X₄) = 2X₄$，他们需要检查 $g₄(2)$（在本例中，等于 $C₅ = 4$）是否与评估 $g(5,3,7,2)$ 的结果完全相同。

由于我们无法执行另一轮，因此看起来我们没有任何选择来检查最后一个值的有效性。 这不好：如果该值只是编造的，以便一切都能正常工作呢？

此时，我们需要一种不同的策略。

我们需要一种机制来验证 $C₅$ 是否正确。 请注意，$C₅ = g(5,3,7,2).$ 如果存在某种神奇的方法可以在该输入下安全地评估 $g$，那么我们可以将其与 $g₄(2)$ 进行比较，并很好地结束该过程。

可悲的是…… 现在还不是我们了解如何在数学上实现这一点的时候。

不过，与其要求你信任我，我建议你这样做：让我们给它取一个名字，这样我们就不会忘记它。 当时机成熟时，我们可以回到这个概念，并真正地将一切联系在一起。

我们会说我们有对 $g$ 的预言机访问权限。 通过这一点，我们意味着我们有一种方法可以在某个随机点评估 $g$，并且我们保证获得正确的值。

因此，最后，经过每一轮中的所有检查后，验证者在 ( $r₁, r₂, r₃, r₄$) 处执行 $g$ 的预言机查询，如果该值与 $C₅ = g₄(r₄)$ 匹配，则接受证明。

当然，整个过程可以推广到任何程度 —— 而且程度越高，节省的时间就越有意义！

这就是 sum-check 协议！

完整性和可靠性

这绝对是一个非常优雅的算法。 我知道一开始可能感觉有点太多，所以我鼓励你花时间让它沉淀下来，然后再继续前进。

不过，有了这些证明方法，我们需要精确 —— 这意味着为了让我们自信地说“是的，这行得通”，我们需要正式证明该算法既是完整的又是可靠的。

从现在开始，这将成为我们学习的任何算法的标准做法。 由于这是我们第一次在本系列中介绍算法，因此让我们简要回顾一下这些属性意味着什么：

• 完整性 意味着如果原始语句有效（布尔超立方体上 $g$ 的和实际上是 $C$），则验证者将始终接受证明，除非概率可以忽略不计。
• 可靠性 意味着不诚实的证明者很难生成有效的证明，除非概率可以忽略不计。

实际上，可靠性有各种类型，但我们将把该讨论推迟到以后。

完整性非常简单：如果证明者确实知道 $g$，并且已正确计算出 $C$，那么他们只需根据协议正确构建每个 $gᵢ$，即可通过每一轮。 这是因为他们知道 $g$，所以他们应该可以毫无问题地对每个挑战提供回应。

可靠性更难证明。 本质上，我们需要衡量证明者作弊的难度。

为此，让我们实际完成一次作弊尝试。 假设证明者不知道 $C$，而是声称 $g$ 在布尔超立方体上的和为 $C^$。 或者更糟：他们有兴趣说服我们，结果 $C^$ 对他们自己有好处！

他们如何欺骗验证者？

好吧，在第一轮中，他们需要发送一些多项式 $g₁^*(X₁)$，以便：

$g_1^(0) + g_1^(1) = C^*$

现在，这就是有趣的地方：他们不能使用 g 来计算 $g₁^(X₁)$，因为总和（很可能）不同于 $C^$。 因此，他们需要制作 $g₁^*(X₁)$，以便通过第一次检查。

换句话说，$g₁^(X₁)$ 和真实的 $g₁(X₁)$ 是不同的多项式。 因此，当验证者选择他们的第一个挑战 $r₁$ 时，$g₁(r₁)$ 和 $g₁^(r₁)$ 具有相同值的可能性非常小。

我们实际上可以准确地知道这种可能性有多小。 本着保持渐进的精神，我认为最好将该讨论留到以后进行。 不过，我想说的是，你在上篇文章中拥有进行此项工作所需的所有信息。

所以如果你想考虑一下，请便！ 如果没有，请不要担心 —— 我们会回到这一点。

如果 $g₁(r₁)$ 和 $g₁^*(r₁)$ 恰好重合，那就太不幸了。 如果是这种情况，证明者可以继续他们的谎言，只是这一次他们可以在理论上用有效的多项式回应每一个后续轮次：他们只需正常计算 $gᵢ$ 即可。

我们可以以相同的递归方式将相同的推理应用于每一轮：要通过第 2 轮，证明者需要构建 $g₂^(X₂)$，以便它通过下一次检查，并且他们必须在下一次挑战中幸运（$g₂(r₂) = g₂^(r₂)_$）。

如果发生这种情况的概率为某个值 $δ$，那么作弊的证明者有 $v$ 机会幸运（或总共 $v$ 个掷骰子），因此成功抢劫的总概率为 $v\cdotδ$。 只要这个组合值很小，那么该算法就是可靠的。

最后，最终的预言机查询允许验证者抓住证明者在最后的谎言（当然，除非他们幸运）。

所以你明白了！ sum-check 协议满足完整性和可靠性要求。

总结

我们刚刚看到了我们的第一个可验证的计算算法。 现在看来可能并不多，但这是一个开始。 在此过程中，我们已经了解了一些有价值的工具和概念，例如递归、验证者挑战、巧妙的多项式评估、预言机查询，甚至如何检查完整性和可靠性！

我故意跳过了此协议的计算成本，因为我希望我们现在专注于数学。 如果你好奇的话，你可以轻松地自己进行计算 —— 并且你会发现三件事：

• 证明者在 $O(2^v)$ 时间内运行。
• 验证者在 $O(v)$ 时间（线性）内运行。
• 总共有 $v$ 个通信步骤，并且在整个协议期间发送的字段元素总数为 $O(v)$。

显然，随着 $v$ 变大，验证者比证明者快得多。 但是可能会围绕这一点出现一些问题：线性时间是否足够好？ 证明者花费太长时间是否重要？

特别是，通信开销 呢？ 验证者可能运行得更快，但如果它必须等待证明者，那么整个过程就会变慢！

嗯…… 是的。 以目前的形式来看，这不是一个非常实用的协议。

我警告过你！

让我们只说它具有潜力。

在接下来的几篇文章中，我们将开始拼凑 sum-check 协议的重要性。 为此，我们将希望跳到其他重要的想法上，特别是关于如何以通用方式表示语句和计算。

这将是下一个主题！

• 原文链接： medium.com/@francomangon...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～