ZK 编年史：快速傅里叶变换

想要获得更具互动性的体验，请在我的个人博客 Arkana 上阅读。

起初，对于是否要专门写一篇关于这个主题的文章，我感到有些犹豫。我通常喜欢在每次发布时涵盖更广泛的主题。你知道的，就是那种感觉具有凝聚力的专题包。

但问题在于，除了极其有用之外，这也是你能找到的最优雅的算法之一。

它无处不在，以至于你可能永远不需要亲自实现它。然而，理解其精美设计的来龙去脉仍然具有巨大的价值。

当然，我说的就是快速傅里叶变换 (Fast Fourier transform)，简称 FFT。

正如我 之前提到过的，它允许执行高效的多项式插值，由于这是我们在即将到来的证明系统中会大量使用的活动，FFT 基本上成为了这些协议的骨干。

我觉得我无法再进行更多的预热了，所以让我们把这些精力投入到正题上，看看今天为我们准备了什么！

核心挑战 (The Core Challenge)

让我们先快速回顾一下 前一篇文章。

我们对 Sigma 协议的分析表明，我们可以构建一个惊人简单的机制来证明对整个电路的知识。然而，这样做需要与乘法门数量成正比的承诺数量。这可不是什么好事，朋友 (no bueno amigo)。

为了规避这一点，其他协议选择将电路编码为多项式。

他们是怎么做到的？我不想剧透，所以这里只是一个小小的预告：

假设我们将每个乘法门 i 的左输入 (a) 编码为多项式 A(X)，要求 A(i) = aᵢ。同样，右输入 (b) 被编码在 B(X) 中，使得 B(i) = bᵢ。而输出，我们将其编码在 C(X) 中。

然后，我们需要证明 A(X)· B(X) = C(X) 对所有可能的 i 值都成立！

这个简单的例子（尽管简单，但它是现代最流行的 ZK 协议之一 Groth16 的核心）告诉我们一些重要的事情：在处理多项式时，我们经常需要对它们进行运算——要么是将多项式相加，要么是计算它们的乘积。

当使用某种特定的多项式表示法执行时，这些操作中的每一个恰好都是高效的。

噢，对了。我想我们还没有明确讨论过这一点。表示多项式主要有两种策略：

• 作为一组系数，如 A(X) = a₀ + a₁X + a₂X² + … + aₙ₋₁Xⁿ⁻¹。在这样做时，我们可能会选择不同的基，例如 拉格朗日基。
• 或者作为一组求值：点对 (i, A(x_ ᵢ _))，它们最终插值为同一个多项式。第一个坐标是索引，第二个是函数值。

系数表示法让加法变得轻而易举，而乘法在使用求值表示法时更易处理，因为你只需要将每个索引处的函数值相乘即可。

因此，当某些协议（或实际上任何其他类型的应用程序）需要我们执行多个此类操作时，能够在这两种形式之间自由切换是很有吸引力的。不过问题是，我们能否高效地做到这一点：如果转换成本高于直接运行原始计算，那么切换就没有意义了！

那到底是怎么回事呢？这些成本是合理的吗？

朴素方法 (The Naive Approach)

让我们分析一下我们能想到的最直接的方法，你会看到我们很快就会遇到问题。

让我们先分析从系数到求值的转换。我们要在一个次数为 n 的多项式上求 n + 1 个不同点的值（以便稍后可以插值回来）。单次求值至少需要我们计算 Xⁿ，因此需要 O(n) 个步骤。由于我们需要求 n + 1 个点的值，整个转换过程是 O(n²)。

然后是逆向路径，从求值到系数。执行此操作的标准方法涉及构建拉格朗日基多项式并将其组合。在不深入细节的情况下，这个过程需要更多的工作，运算量在 O(n²) 到 O(n³) 之间。

考虑到这些数字，情况到底有多糟？嗯，考虑到我们想要编码可能具有数百万个门的电路，我们将处理巨大的多项式，而转换成本简直是疯狂的。

这意味着，如果没有更高效的方法，这些转换是完全不在考虑范围内的。

因此，我们将提出我们在整个系列中多次提出的同一个问题：我们能做得更好吗？

答案当然是一个大大的肯定的，这归功于对我们迄今为止忽略的一点所产生的聪明洞察：我们可以选择在哪里对多项式进行求值。

也许最自然的选择是简单地使用连续整数作为我们的索引：0, 1, 2, 3 等等。这没问题。但是……如果我告诉你有一个更好的选择呢？

魔力属性 (The Magic Properties)

记得我吗？

没错！单位根 (Roots of unity)！

当我们在几篇文章前谈论它们时，是在群的背景下。这一次，我们实际上对模 p 的整数乘法群的单位根感兴趣。因为这些将作为我们多项式的输入，而多项式以整数作为输入。

作为一个简短的回顾，一个群的 n 次单位根是满足以下条件的集合值 ω：

是的，很酷。但归根结底，那些只是数字。是什么让它们如此特别？

*显而易见的困惑*

秘密在于这些小家伙拥有的几个特殊属性：对称性 (symmetry) 和平方封闭性 (closure under squaring)。

对称性 (Symmetry)

为了理解我所说的这一点，让我们倒推一下。我们知道，当我们有一个本原 (primitive) n 次单位根时，将其提升到 n 次方会得到单位元，在我们的例子中就是 1。

考虑到这一信息，如果我们不提升到 n 次方，而是尝试其一半会发生什么？

显然，前提是 n/2 是一个整数！

因为它是一个本原单位根，所以结果不能是 1。此外，它必须是一个满足以下条件的数字：

啊，等等。那么有一个明显的候选者：-1！

或者，在我们的例子中，是 -1 mod p。

由于这一观察，我们可以做一件神奇的事情：将 n 个单位根组成的群分成互为相反数的对，因为：

因为我们只是乘以 -1，所以我们有一种非常快速的方法来获得单位根的（模）相反数。这在聚合结果时将非常重要，但实际上是另一个属性才是该算法背后的秘密配方。

平方封闭性 (Closure Under Squaring)

同样，我们可以问自己，当我们对一个单位根进行平方时会发生什么：

我们可以通过一些简单的推导来回答：

你能看到吗？对任何单位根求平方会将其转换为一个 (n/2) 次单位根！

不难推断，(n/2) 次单位根的数量正好是 n 次单位根数量的一半。这很有趣，因为如果我们更进一步，对所有 n 次单位根求平方，就会发生一些非常神奇的事情。

这个平方集合的大小是 n，但它只包含 (n/2) 次单位根……所以一定存在重复值！事实上，我们每个根都正好得到了两次！

试着自己看看那是什样子的！

如果你认为这只是一个有趣的事实，那你完全情有可原，但你也会完全错误：这是快速傅里叶变换能够运作的全部原因！

我们只需要找到一种巧妙的方法来利用这些属性。

分治法 (Divide and Conquer)

我们即将使用的技术实际上是我们在过去已经涉猎过的一种：递归 (recursion)。

简而言之，我们在这里尝试做的是将一个更大的问题分解为一个其自身的更小版本，通过这样做，可以大大降低计算成本。这是一个优美而简单的想法，在某些天时地利人和的情况下，它可以产生巨大的威力。

而这恰好就是其中一种情况！

好的，设置如下：假设我们有一个次数为 n - 1 的多项式 A(X)，我们想将其从系数形式转换为求值形式。

我们将从把 A(X) 分解为奇次幂和偶次幂开始。然后我们选择相应的系数，并构建两个新的多项式，如下所示：

• 来自偶次幂项：Aₑ(X) = a₀ + a₂X + a₄X² + a₆X³ + …
• 来自奇次幂项：Aₒ(X) = a₁ + a₃X + a₅X² + a₇X³ + …

系数索引与幂次之间的不匹配起初可能会让你感到困惑，但它实际上并非随意的。其原因是原始多项式 A(X) 可以表示为这两个新多项式的巧妙组合：

这是一个很酷的技巧——但就其本身而言，它并不代表什么。真正的乐趣在于我们将其与关于单位根的知识结合起来时。

求值 (Evaluation)

让我们尝试将一个单位根代入 A(X) 的那种形式，看看会发生什么：

与其在每个 n 次单位根处直接计算 A(X)，上面的表达式表明，我们可以通过在 (n/2) 次单位根处计算另外两个多项式来获得相同的结果。

在这里，我们的封闭性发挥了关键作用：我们知道 (n/2) 次单位根的数量是 n 次单位根的一半！

结果非常棒：Aₑ(X) 和 Aₒ(X) 的一些求值可以重复使用，因为它们是重复的！或者，更直观地说，你可以很容易地验证：

啊哈！我们在 n 个点求 A(X) 的值的问题已经简化为在一半数量的点上求 Aₑ(X) 和 Aₒ(X) 的值，并执行一些简单的操作。只要我们能高效地求出 Aₑ(X) 和 Aₒ(X) 的值，我们就能做到这一点……但是等等……

那就是我们最初的问题，只是规模大约缩小了一半！

是的！这正是递归发挥作用的地方：得益于单位根的优良属性，我们可以不断地重复这样做！

而且，似乎这还不够，锦上添花的是我们之前研究过的对称性。既然我们知道：

那么我们的第二次求值就变成了：

这看起来和在 ωᵏ 处的求值完全一样，只是多了一个负号！

总而言之，我们需要为从 0 到 n/2 - 1 的每个 k 执行以下步骤：

1. 计算一次 Aₑ(ω²ᵏ)
2. 计算一次 Aₒ(ω²ᵏ)
3. 计算一次 ωᵏAₒ(ω²ᵏ)
4. 通过将结果相加来计算 A(ωᵏ)
5. 通过相减来计算 A(-ωᵏ)

由于我们是在一半数量的点上对两个次数减半的多项式进行求值，我们以几乎等同于一次求值的成本得到了两次求值的结果！

这些碎片是如何拼凑在一起的，简直令人难以置信，仿佛是由某个隐形的数学精灵引导的一样。以至于人们不禁仍然心存疑虑，直到看到一个实际运行的例子。

所以让我们来做一个！

一个具体的例子

我们将在 𝔽₁₇ 中进行，其乘法群为 ℤ₁₇*。这个域很好，因为它有本原 4 次单位根，这意味着我们可以做一个 n = 4 的小例子。

首先，我们需要单位根的具体值。在这种情况下，值 ω = 4 恰好是一个本原单位根，所以如果你完成这些运算，你会发现根的集合如下所示：

完美！接下来，让我们取一个简单的多项式，例如：A(X) = 3 + 2X + 5X² + 7X³。我们想在 H（我们的单位根集合）中的点处求它的值，所以我们按照我们的递归过程进行：

• 首先，分为偶次系数和奇次系数，得到 Aₑ(X) = 3 + 5X 和 Aₒ(X) = 2 + 7X。
• 接下来，我们需要在 2 次单位根处求这两个多项式的值，它们就是 {1, 16}。这些是非常基本的运算（因为多项式的次数为 1），结果为：

• 然后我们利用对称性进行组合。例如，对于 k = 0，我们有：A(1) = 8 + 9 mod 17 = 0，以及 A(-1) = A(16) = 8 – 9 mod 17 = 16。只需对 k = 1 重复操作，我们就完成了！

最终结果是 A(1) = 0，A(4) = 12，A(16) = 16，以及 A(13) = 1，以防你一直在用纸笔跟着算并想检查一下！

如果你已经在那样做了，一定要检查一下这是否与直接求值的结果一致！

就这样！只需拆分、递归并组合。周而复始，我们就拥有了 FFT 算法！

这个小例子看起来可能并没有太大的改进，但你仍然已经可以看到一些收益：

• 直接方法需要 4 次求值，每次求值有 4 个运算（计算 X³ 然后将所有项相加），总共大约 16 个计算步骤。
• 相比之下，FFT 进行了 4 次求值（对拆分后的多项式）加上 4 次组合，总共 8 次运算。

这只有一半的工作量！当我们尝试更大的多项式时，效果会更好：每个递归步骤将花费 O(n) 次运算，并且步骤数相对于 n 是对数的（我们在每一步都将求值次数除以二！），因此算法的总复杂度是 O(n.log₂(n))。

为了直观地说明这一点，当 n = 100 时，直接求值将花费大约 10000 步，而 FFT 仅需大约 650 步！

插值 (Interpolation)

有了这个，我们就有了从系数到求值的有效方法。

我们难道不能尝试朝另一个方向走吗？你知道的，为了真正能够在各种形式之间来回转换。这里有类似的技巧吗？

神奇的是，这在反方向也同样适用！

逆 FFT (inverse FFT) 使用几乎完全相同的算法，只需进行一些微调。为了理解这是如何运作的，我们需要稍微改变一下视角——我们必须将获得求值的过程想象成一个矩阵乘法：

上面那个方程中的矩阵被称为离散傅里叶变换 (DFT) 矩阵。从这个角度来看，很明显，为了解这个方程，我们要做的就是计算这个矩阵的逆，然后进行相应的乘法。

而且，逆矩阵的结构实际上非常好！对于我们 n = 4 的例子，我们会得到：

对此的推广正如你所期望的那样：一个更大的矩阵，以及一个 1/n 的标量因子！

就这样，我们几乎免费获得了从求值中恢复系数的算法！

总结 (Summary)

FFT 是那种感觉近乎神奇的算法之一。一切都严丝合缝。

难怪我们要归功于像高斯或傅里叶这样伟大的数学家的努力！

一切都始于一个平淡无奇的观察，即我们可以选择在哪里对我们的多项式进行求值。正是通过选择一个具有某些非常好属性的集合，我们最终得到了这个真正美丽的算法。

FFT 对 ZK 来说极其重要，因为它能够使大型多项式的运算在计算上变得可行。正如我在文章开头提到的，你可能永远不需要自己实现它：几乎每个 ZK 库都会包含该算法的高度优化版本，其中包含更多的小技巧，如并行化、缓存等。

此外，还有一些我没有明确提到的细微差别需要考虑。例如，你需要确保在2 的幂次个点中进行求值，这要求多项式具有特定的次数，并且所选的有限域包含适当的单位根集合！

所以，是的，这个故事还有更多内容——但我认为我们涵盖的内容对我们来说已经足够了。

既然我们在讨论多项式，我希望我们的下一站能展示我们在旅程中需要的另一种成分。

我们即将研究的东西，能够让我们从 Sigma 协议实现质的飞跃，跨向能够充分利用 FFT 的更现代的技术，从而提供最终使 ZK 进入实用领域的效率水平。

因此，下一次我们将讨论多项式承诺方案，这是在我们在现代 ZK 算法上全力冲刺之前的最后几个小工具之一。

我们最终将揭开我们已经在冰箱里冷藏了很久的预言机访问 (oracle access) 的神秘面纱！

下次见！

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