ZK编年史：哈希登场

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

仅仅使用有限域 和 多项式就能走到今天这一步，这难道不是很神奇吗？

就协议而言，我们甚至以 GKR 的形式获得了我们的第一个通用证明系统。在理论方面，我们深入研究了一些非常深刻的概念，将不同类型的问题联系起来，并为未来的许多事情提供了强大的理论基础。

但是，我的意思是，算了吧。如果你对这些东西感兴趣，你就会知道我们还有一些要素没有触及。当然，在我们对 ZK 的探索中，我们仍然缺少一个重要的元素：哈希函数。

所以今天，终于到了将它们融入其中的时候了。它们看起来很简单，但它们将为我们的证明系统解锁一些关键的超能力。

不是我想要表达的，但还是...

让我们首先看看我们究竟在处理什么，然后我们将充分利用这些哈希的东西！

哈希函数

你可能已经听说过哈希函数。它们无处不在：密码存储、数据完整性检查、数字签名等等。它们真的是万事通。

我愿意打赌你可能知道它们是什么以及它们是如何工作的，但为了完整起见，让我们简单地解释一下。

我还有一篇关于这个主题的入门级文章，你可能想看看！

为了使这个介绍简洁明了，哈希函数只是一个函数，它接受一些输入，对其进行搅乱，并产生一个完全无法识别于输入的输出。

顺便说一下，我们通常将哈希函数的输出称为输入值的 哈希值！

这就是它所做的全部，真的。“哈希”字面意思是将某物切成小块并烹饪，有效地将其混合并从混合物中创造出新的东西。就像我们都了解和喜爱的美味薯饼一样。

太完美了

然而，与我们的烹饪相似之处相比，这种切碎发生的方式非常具体，赋予哈希函数一些特殊的属性：

• 它们是 确定性的：每次我们通过哈希函数传递输入 $x$ 时，无论我们尝试多少次，我们都会获得完全相同的值。
• 它们是 扩散性的：输入中的微小变化将导致输出的巨大变化。这有时也称为 雪崩效应。
• 它们是 不可预测的：我们无法仅通过分析输入来提前知道输出会是什么。
• 它们是 不可逆的：我们无法通过分析输出来知道输入是什么。更准确地说，我们在这里看到的是 抗原像性：找到产生给定输出的输入非常困难。因此，哈希函数有时被称为 单向函数。

在大多数情况下，我们还关心 抗碰撞性，这意味着找到两个产生相同输出（甚至部分匹配输出）的输入非常困难。

构建一个满足这些要求的函数并非易事，但也并非不可能。

一旦我们获得这样的构造，它的属性使其适用于大量应用，其中之一我们在此之后需要讨论。

Merkle 树

这些哈希函数的存在允许我们围绕它们构建复杂的数据结构，其中最著名的可能是 Merkle 树。

Merkle 树有多种形式，但最简单的形式是以树的形式（是的，你猜对了）存在的图。然而，可以这么说，它不是你“正常”的图。

让我们从最简单的例子开始，这将使我们了解它是如何工作的以及为什么这种结构在更大的范围内有用。 它是这样的：

• 选取任意两个字符串。选择你喜欢的任何内容——从简单的单词（如“hello”和“world”）到 Lorem Ipsum 的前两个段落。
• 对它们进行哈希处理。我们可以为此使用常见的哈希函数，例如 SHA256。
• 现在，取出这两个结果，并将它们连接起来。就像简单的字符串连接一样。
• 最后，再次对它们进行哈希处理。

你刚刚所做的如下所示：

你可能会问，为什么要这样做？实际上有三个原因。

第一个原因与信息是如何联系在一起的有关：由于哈希的属性，原始文本中任何一个的单个小变化都会导致完全不同的输出值（我们称之为树的 根）。此外，如果哈希是抗碰撞的，则意味着很难找到其他可以产生相同根的文本。

总而言之：根是对原始数据 完整性 的保证。任何微小的变化，根都会发生巨大的变化。因此，这是一种 提交 到那些初始值的方法。

其次，让我们看看当我们 放大这个过程 时会发生什么。没有人说我们应该将自己限制为两个输入！ 事实上，我们可以对 4、16、64 甚至 数千 个原始值执行相同的过程，所有这些值都减少到 单个根。 因此，我们这样做的第二个原因是 压缩：我们可以提交到大量数据，其完整性可以通过单个小值进行检查。

“但是 Frank”——你可能会问，“哈希已经压缩了！为什么不只是将所有输入一并哈希处理呢？”。 你说得对。 事实上，哈希函数采用一些潜在不受限制的域中的输入 $D$，并将其映射到固定长度的比特字符串：

$H: D \rightarrow {0,1}^n$

那么……为什么不全部哈希处理，然后完成呢？

这就引出了我们的第三个也是最后一个原因：生成 包含证明 的能力。 Merkle 树允许我们通过提供到达根的路径上的中间哈希值来证明 单个输入叶子 是树的一部分，因此与根绑定，这些中间哈希值称为 Merkle 路径 或 身份验证路径。 像这样：

想要证明 $A$ 是原始集合的一部分的人，不需要提供所有原始数据来重新计算根，而只需要发送 绿色节点 的值，并且验证此人可以轻松找到根。

这是一个不错且有用的技巧！

尤其是在正确的上下文中：例如，一些区块链（如比特币）使用 Merkle 树来压缩区块中的交易，从而提供了一种快速验证交易是否包含在该区块中的方法。

但我们来这里是为了可验证计算和 ZK。 那么问题就很清楚了：Merkle 树在这种上下文中有什么好处吗？

正如你可能预料到的那样，答案是肯定的。 然而，我们仍然太早而无法发挥这些结构的全部潜力。 目前，我只能向你展示冰山一角……但我很确定这对于现在来说已经足够了！

多项式承诺

在之前的几篇文章中，当我们首次介绍总和检查协议时，我提到了对某些多项式 $g$ 进行 oracle 查询 的想法。

那时，我们缺少一些关键的数学概念来真正介绍如何实现这一点。 公平地说，我们仍然缺少——但哈希开始解锁一些可能性。

让我们分析一下拥有 oracle 访问权限 会是什么样子。 假设你有一些在有限域 𝔽 上定义的多项式 $P(X)$，并且你想在某个输入 $x$ 处对其求值。 这里有两种选择：

• 你有一种自己计算 $P(x)$ 的方法，不信任任何其他方。
• 你让其他人计算 $P(x)$，他们提供 正确性证明。

如果可能的话，第一个是最简单的解决方案。 然而，验证者通常无法获得原始多项式 $P$，或者至少，让他们自己计算 $P(x)$ 是不切实际的。

相反，验证者可以向证明者请求值 $y = P(x)$。 当然，证明者可能会说谎——那么验证者如何信任这个值呢？

好吧，解决这个问题的一种方法（虽然有点疯狂）涉及使用 Merkle 树。

告诉我更多

这个想法非常原始，但功能强大：证明者评估 $P(X)$ 的 每个可能的输入，并将所有可能的结果压缩成单个 Merkle 根。

当然，这棵树可能会变得很大。 真的，非常大。 尽管如此，证明者只需要执行一次此操作，并将根发送给验证者，这就是我们需要的所有设置。 通过这样做，证明者已提交到 Merkle 树中的值，并且只能在提示时回复有效值。

因此，有趣的部分发生在验证者要求在某个值 $xᵢ$ 处进行评估时。

重要的是，输入值具有某种排序，该排序与 Merkle 树叶的顺序相匹配。 顺序可以简单到 x₀ = 0、x₁ = 1 等。

证明者所做的只是提供 $yᵢ$ 的值，以及通向验证者已经拥有的根的 身份验证路径！

这非常好，因为提供的证明可以用 对数时间 来检查。 如果总共有 $N$ 个可能的评估需要请求，那么验证将在 $log₂(N)$ 步内发生！

实际上，验证者正在请求某个值 $P(x)$，而证明者正在回复正确的值，以及 其正确性的证明 （通过包含在 Merkle 树中）。

不错

对证明者来说，这看起来很昂贵，是的，但似乎是合理的。 只是……这个解决方案存在一个巨大的问题：我们如何知道 Merkle 树中的评估首先对应于 $P(X)$？

这远远超出了今天文章的范围。 但是我没有完全对你们撒谎：Merkle 树 确实 对此有用。 让我们只说，在适当的上下文中，我们可以检查额外的条件。

尽管如此，我们已经证明了 Merkle 树可以用作我们所说的 多项式承诺 的基础：提交到多项式的方法，以便在请求时可以检查评估对于承诺的有效性。

还有其他方法可以做到这一点，我们将在以后的道路上探索更多方法！

现在有足够的 Merkle 树了！ 哈希在可验证计算中还有其他用途，其中两个对我们来说比 Merkle 树更有价值。 接下来，我们将检查这些哈希。

电路中的哈希

在上一篇文章中，我们评论了如何将任何计算转换为电路可满足性 (CSAT) 问题。

如果不是计算，那么哈希函数是什么？ 这意味着我们可以将它们转换为电路！

我们应该这样做吗？

如果说我们到目前为止学到了一件事，那就是我们的证明协议的成本在很大程度上取决于电路的大小。 我们的 #SAT 系统 和 GKR 协议都随着电路尺寸的增加而变得更加昂贵，因此有理由说我们希望保持电路 尽可能小。

我想表达的是：假设我们编写了一些使用哈希函数的程序，并且我们将所述程序（我们知道这可以通过 Cook-Levin 实现）转换为电路。 那个电路有多大？

嘿，我一点都不“大”，好吗？

我们可以通过哈希函数拥有的数学 约束 的数量来衡量产生的电路的预期大小。

将这些约束视为计算最终哈希所需的 步骤 数。稍后我们将更准确地说明这些约束实际上是什么。 现在，我们可以将这些步骤中的每一步设想为一个 表达式，该表达式需要对整个过程有效才是正确的——就像我们在 GKR 协议中分析电路时的情况一样。 并且每个约束可以用少量的加法和乘法门来表示。

传统的哈希函数（例如 SHA-256）是专门为使用布尔电路的 CPU 设计的。 它们使用按位运算，例如 XOR、AND 或轮换，并以混合轮次进行组织。 更糟的是，它们执行许多这样的混合轮次（在 SHA-256 的情况下为 64 轮）。 这样做的结果是 约束数量巨大，很容易达到数万个。

我认为很明显，这使得常见的哈希函数对于可验证计算和一般的 ZK 而言 非常不切实际，因为它们使我们的证明工作变得非常昂贵。

接下来自然而然地引出的问题是：是否存在我们可以用小电路实现的 安全哈希函数 （具有我们之前描述的所有良好属性）？

ZK 友好型哈希函数

当然！

随着可验证计算的出现，并且认识到需要产生小电路的哈希函数，开发了一些新的替代方案。 与更“传统”的哈希函数相比，像 MiMC 或 Poseidon 这样的哈希函数可以产生更小的电路，使其适合于语句表示。

那么，它们是如何工作的呢？ 这些构造背后有一些有趣的技巧（例如它们如何实现 S 盒操作），但简而言之，魔力在于它们使用 算术电路固有的 操作：有限域加法和乘法。

另外，请查看这篇 Rareskills 文章以获取一些额外的详细信息！

这导致 非常精简的电路，只有几百个约束。

由于这些函数是为算术电路而不是 CPU 设计的，因此它们比其他常见的哈希函数（如 SHA-256 或 Keccak-256）慢得多。 然而，对于可验证计算来说，它们 非常有意义，正如我们已经知道的那样，电路大小是王道。

对于大多数 ZK 应用程序，Poseidon 似乎是事实上的首选哈希函数。

我想这已经有很多信息了。

如果需要，可以暂停一下！

但是，我将 哈希最重要的应用 （可以说是最重要的）留到了最后再讲。 事实是，如果不理解下一个概念，我们几乎无法正确地继续我们的旅程。 所以我仍然不会让你们离开。 对此感到抱歉！

交互性问题

到目前为止，你可能已经发现我们的证明系统存在的一个大“问题”是 交互性。

在我们的设计中，证明者和验证者必须相互 交互，来回发送消息和挑战，最终使证明者能够说服验证者某些计算的有效性。

事实上，这种交互性并不是一个真正的问题——毕竟，正是这种交互性使得系统能够首先工作。 但我们至少可以认识到交互性有两个复杂之处：

• 它使整个过程 变慢。 在每个验证者的挑战中，证明者都必须进行一些相对昂贵的计算，这成为整个协议的瓶颈。
• 它要求双方在整个交互过程中都处于活动状态。 如果一方断开连接或不可用，则该过程将无法继续！

好吧，是的……但是我们能对此做些什么呢？ 我们有没有办法以非交互方式做到这一点？

幸运的是，由于哈希和 Amos Fiat 和 Adi Shamir 的想法，我们可以！

Fiat-Shamir 变换

让我们先暂停一下，思考一下为什么交互性如此重要。

为简单起见，让我们专注于 总和检查协议。 作为简短的提醒，在第一轮中，证明者发送布尔超立方体上的声明总和 $C₁$ 和多项式 $g₁$，以便：

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

在检查完这一点后，验证者选择一些证明者无法预测的随机值 $r₁$，并且该数字提示他们计算一些意外的值 $C₂$，为此他们需要执行另一轮总和检查。

这里的关键见解是，证明者无法预先计算 $C₂$，因为他们无法预测 $r₁$ 的选择。 正如我们已经看到的那样，正是这种不可预测性使得协议听起来不错。

你知道还有什么也是不可预测的吗？ 疯狂的 哈希函数！

这就是 Fiat 和 Shamir 的绝妙想法：我们可以通过获取 交换消息 的 哈希 来模拟验证者的选择：

酷！ 我们利用哈希函数的伪随机性和不可预测性来完全消除交互！ 验证者所需要检查的就是所有检查是否通过以及所有哈希是否已正确计算。

这被称为 Fiat-Shamir 变换 或 启发式，它可用于将任何交互式协议转换为非交互式协议，从而有效地消除验证瓶颈。

安全

当然，从挑战选择的等式中删除验证者意味着证明者可能会操纵事情。

那么，这实际上安全吗？

关键在于对 整个记录 进行哈希处理：所有先前交换的消息，包括证明者自己的响应。 这创建了一个 绑定链：

• $r₁ = H(C₁, g₁)$
• $r₂ = H(C₁, g₁, r₁, C₂, g₂)$
• $r₃ = H(C₁, g₁, r₁, C₂, g₂, r₂, C₃, g₃)$

等等。

之所以可行，是因为为了使恶意证明者能够将某个挑战 $rᵢ$ 操纵为有利值，他们需要找到哈希到他们想要的 $rᵢ$ 的输入（如果我们使用抗碰撞哈希函数，这很难）。

但是更改较早的消息会影响所有后续挑战！ 因此，他们需要找到一个 完整的记录，其中所有挑战都对他们有利。 这需要找到不是一个，而是多个哈希冲突或 原像，这非常困难。 如此之多以至于证明者无法通过此策略进行欺骗！

最后，包括初始输入（在我们之前的案例中为 $C₁$），我们使其甚至无法更改计算结果。 这非常重要，因为我们将记录绑定到正在证明的内容。

严格来说，我们必须变得更加技术性才能正式证明变换的安全性。 不过现在还为时过早。 我们将在以后的旅程中到达那里！

Fiat-Shamir 变换是密码学中最优雅、最强大的想法之一。 最吸引人的事情之一是它的通用性：只要存在我们可以哈希的记录，它就可以应用于 任何 交互式协议，而不仅仅是总和检查。

实际影响是巨大的：证明变成了 可移植的工件，可以存储并由任何人随时随地进行验证。

这就是为什么基本上每个现代 ZK 系统都使用 Fiat-Shamir，并且它是使可验证计算和 ZK 实用 的关键因素之一！

总结

所以你明白了！ 哈希！

这些小家伙为我们的证明系统解锁了关键功能。 它们无处不在，并提供了宝贵的构造，使我们的密码学能够正常工作。

我们今天看到的所有应用程序都在实践中得到非常广泛的使用。 我认为这篇文章可能比预期的要长一点，但请相信我：每一部分对于接下来发生的事情都很重要。 没有什么会被浪费！

对我们来说，特别重要的是 Fiat-Shamir 变换。 可以肯定的是，我们将把它应用于我们在此设计的几乎任何交互式协议，即使我没有明确提及。 所以只要把这个记在心里就行了！

在本系列中，我们仍然需要介绍一些协议。 但在此之前，我们将需要开始研究另一个将在我们旅程的剩余时间里陪伴我们的关键数学概念：群。

那将是我们的下一个目的地！

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