多标量乘法是零知识证明的核心组成部分，也是主要瓶颈。
撰文：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 方法。考虑到所有这些选项，我们有很多组合可以尝试。
我们在扩展的 Twisted Edwards 坐标中建立了一个全流水线的椭圆曲线加法器，运行频率为 250MHz，使用 7 个场乘法器。