多标量乘法是零知识证明的核心组成部分，也是主要瓶颈。

撰文：Kaveh Aasaraai、Don Beaver、Emanuele Cesena、Rahul Maganti、Nicolas Stalder、Javier Alejandro Varela

翻译 & 校对：Erliang、Cyan、Paul，来自 BuidlerDAO

零知识证明有许多神奇的特性，但现在遇到了一个根本问题——昂贵且难以制造。多标量乘法 （MSM） 是其中的核心组成部分，也是主要的瓶颈。本文描述了我们解决这个问题的方法以及我们为加速迈向 ZK 未来所做的努力。

我们刚刚发布了发布了通过 FPGA 加速的 MSM。具体地讲，我们专注于在椭圆曲线 BLS12-377 的 N = 2^26 点上加速 MSM。

我们用能找到的最快的服务器（18 核 Intel i9，4.8GHz）运行最佳软件实现（gnark-crypto v0.6.1）计算一个大的 *N*=2^26 MSM，用了 24 秒。而我们的 FPGA 只用了 5.66 秒 计算出相同的结果，并且是在一个使用了约 5 年的旧 FPGA 模型的 AWS F1 实例上，计算 N=2^22 MSM 只需不到一秒。同样非常有趣的是，我们为硬件开发的技术也可以应用于软件，从而使 MSM 比 gnark-crypto 中现有的实现快 10-20%。

<1s for 2^22 size MSM

5.66s for 2^26 size MSM

所有相关技术细节，包括所有数学和算法，请参阅这篇论文。在这篇文章中，我们想提供一些关于这个结果的背后的故事，以及一些在深入研究工作之前有更多了解的高阶指示。我们会很快将代码开源。

技术

我们使用的所有技术在椭圆曲线密码学领域都非常有名。你可以将实现 MSM 看成实现多层库，其中每一层都引入一个新的抽象。

在顶层，我们有桶方法 (bucket method）（又名 Pipppenger 算法）。这可以进一步分为 3 个阶段：桶累积 (bucket accumulation)、桶聚合 (bucket aggregation) 和最终结果聚合 (final result aggregation) 。最初，我们只想在硬件中运行桶累积，并在主机上用并行线程执行聚合。但是这样做太慢了，至少在只有 4 个 2.3GHz 真实内核的 AWS F1 上。我们最终的解决方案是，以一种开创性的方式将桶聚合包含在了 FPGA 中（下一节）。

在下面一层，我们有椭圆曲线运算。得益于 BLS12-377 的支持，我们选择了使用 extended Twisted Edwards 坐标。通过结合一个小技巧，我们可以在七次场乘法中做曲线加法，这意味着我们可以用更少的 FPGA 资源来构建完整的曲线加法管道。

最后，在底层，有 377 位的场运算——尤其是场乘法。在软件中，最好的实现是使用 CIOS 的蒙哥马利表示。替代方法包括执行 377x377 整数乘法，接着做蒙哥马利减法（可以通过另外两个整数乘法来完成）。整数乘法可以结合教科书，Karatsuba and Toom-Cook 方法。考虑到所有这些选项，我们有很多组合可以尝试。

结果#1：250MHz 下的全流水线 EC 加法器

我们在扩展的 Twisted Edwards 坐标中建立了一个全流水线的椭圆曲线加法器，运行频率为 250MHz，使用 7 个场乘法器。

让我们从 * 全流水线 * 的加法器开始解读前一句话。全流水线在硬件上相当于软件中没有循环或跳转。输入比特的时间为 t0，它们在每个时钟周期在电路中前进，并在 t0+L 时间到达输出，其中 L 称为流水线的延迟。全流水线加法器的最大优点是，你可以在每个时钟周期开始一个新的点加法（有一个小的注意事项，我们将在后面讨论，看看你是否能发现它）。

现在，我们提到我们的流水线运行在 250MHz。这意味着我们可以每隔 4 纳秒开始一个新的加点（并在大约 100 个周期后得到结果，即 400 纳秒）。在软件领域，我们已经习惯了以 GHz 速度运行的 CPU，而一个曲线加法可能需要比 400 纳秒还要少一点，比方说 350 纳秒。但是 CPU 很忙碌，所以要做 N 条曲线的添加，你需要 N*350 纳秒。在 FPGA 上，通过全流水线加法器，你可以在每个周期输入一个新的加法，所以总的时间是 (N + 100) * 4 纳秒 =~ N * 4 纳秒，这大约是 2 个数量级的速度!

稍微简化一下，桶式计算法需要计算 16 次

N

- 2^26

- 2^26

我们想强调的是，250MHz 是一个我们相当自豪的成就。在许多研究论文中，我们看到了 125MHz 的结果，并声称性能在 250 甚至 500MHz 时是线性扩展的。但是在更高的频率下工作会带来额外的复杂性，而这些复杂性绝不是微不足道的! 根据我们的经验，一个 125MHz 的原型花了大约一个月的时间。增加到 250MHz 需要四个多月的时间，而且几乎需要完全重新设计。

我们的流水线使用七个场乘法器在扩展的 Twisted Edwards 坐标中实现加法，如下图所示。

自然，我们使用的场操作越少，电路就越简单，就越容易在更高频率下运行。我们不得不尝试大量的组合，特别是在场乘法器层面，以实现这个工作设计。

我们发现的一个非显而易见的限制是我们可以使用的桶的数量，我们不得不把它设置为 2^15 个桶。桶被存储在 SRAM 中，SRAM 块沿设备表面物理分布，我们需要将管道的输入和输出物理地连接到所有这些 SRAM 块。事实证明，这是需要大量的电线! 而当我们尝试 2^16 个桶时，我们无法在 250MHz 下得到一个工作设计。

关于我们 FPGA 设计的更多技术细节，可以参考这篇论文。

结果#2：延迟的调度器

加法器流水线可以在每个时钟周期开始一个新的加点，在 250MHz 时，意味着每 4 纳秒一次。现在的挑战是如何让流水线尽可能地繁忙。

如果我们看一下软件库，它们是按照输入的确切顺序来处理 *N* 点的。毫不奇怪，这并不是硬件的最佳方法。在硬件中，我们引入了一个调度器的概念，它可以重新安排点的顺序，以最大限度地利用加法器流水线。

也许有点令人惊讶的是，同样的调度器也可以解决一个软件问题：使用批处理反转的仿生坐标实现 MSM。这是一种在理论上相对知名的技术。我们在各种库中也看到了关于它的讨论，然而它从未被成功实施过。

通过先用 FPGA，后用 gnark-crypto 工作，我们了解到建立一个有效的调度器有其自身的复杂性。它本身并不困难。事实上，它恰恰相反 -- 调度器是我们能想到的最原始的方法。它之所以成功，是因为它对重新洗牌点做了最低限度的工作（特别是，它最大限度地减少了主机上的内存写入），因此它对计算时间的影响可以忽略不计。

未解决的问题

在论文的结论中，我们强调了一些仍然困扰着我们的问题。如果你对其中任何一个感兴趣，请随时与我们联系，我们非常愿意合作。

走得更快：最大的亚秒。

我们展示了我们当前的实现，在亚秒内计算 N=2^22 MSM。至少在理论上，如果我们必须计算 N=2^23 椭圆曲线 （EC） 加法，乘以 16 个窗口，完美地每 4ns 调度 1 次加法，那就是 2^23 * 16 * 4ns = 537ms。这表明我们应该能够在亚秒内计算出 N=2^23 MSM。所以......我们应该这样做。通过类似的推理，N=2^24 MSM 似乎不可能在亚秒内实现，至少在 FPGA 以 250MHz 运行之前......然而，这看起来像是另一个非常有趣的挑战。

变得更大：N=2^36 及以上。

我们在一篇研究论文中能找到的最大 MSM 是 N=2^35。计算这个 MSM 花了好几天，作者说他们「只是由于时间限制而停止在这些大小上」。同样，从理论上讲，我们应该能够在短短几个小时内计算出 N=2^36，只需花 1.65 美元 / 小时按需支付使用 F1 实例的费用。绝对值得一试！

更智能。

最后也是最重要的，我们对调度程序有些不满。我们花了很多时间思考高效的调度程序，但最终，我们实际上能以高性能实现的最好的也是最简单的是：延迟调度程序。导致效率低下的主要原因是主机上的内存写入。因此，我们绝对期待实现一个更智能且非常高效的调度程序。为此，我们甚至不需要调整硬件，可以首先在 gnark-crypto 或 arkworks 上进行实验。