Figment Capital：深入解读零知识证明加速

原文标题：Accelerating Zero-Knowledge Proofs

原文作者：Figment Capital

原文编译：Lynn，MarsBit

零知识证明允许一个团体在向另一个团体证明一条声明时不需要透露除去「该声明为真实的」的信息以外的任何额外信息。尽管这项密码原语早在上世纪八十年代就已出现，但直到区块链技术的萌发，零知识证明才发现其实际应用，包括区块链扩展、隐私、互操作性，和身份。

尽管声称其可以解决区块链技术中的许多最重大的难题，零知识证明仍旧是一项不成熟的技术。在这些问题之中，最主要的其中之一是其证明时间之久。零知识技术应用在不断改进，其证明的复杂程度也在改进。这些声明需要更大的算数电路，导致证明时间飙升。生产一个零知识证明可能需要比底层计算增加多达百万倍。相应地，有大量的团队正在研究可以改进加速零知识证明所需要的软件和硬件。

在本文中，我们将提供加速零知识证明的概览。我们将总结生产零知识证明的主要操作作为讨论的起点，并在之后转向讨论这些操作可以如何被加速。

零知识证明允许一方（通常被称为证明者），向另一方（通常被称为验证者）证明他们成功地完成了一次计算。一个零知识证明拥有以下三个关键特性：

区块链背景下最主要的零知识证明的类型是 zk-SNARK（全称是「零知识的简洁的非交互式知识论证」）。这终证明在上述的传统的零知识证明的三个特性之上额外有两条特性：简洁性和非交互式。具有简洁性意味着证明的规格小，通常只有几百字节，并且可以迅速地被验证者检验。非交互式的特性意味着证明者和验证者之间不需要交互，单单该证明本身已经足够。较老的零知识证明需要证明者和验证者之间互发信息以生成一项证明。

简介性使零知识证明能够快速地验证，且从计算角度来看很便宜。这使它们成为了一项很棒的扩展技术。在有效性 rollup（也就是零知识 rollup）中，强大的证明者能够计算数以千计的交易的输出，针对它们的正确性生产一个简洁的证明，并将它们发送到底层链上。在那里，验证者能够检验该证明并立刻接受所有已包含的交易的结果，而无需再自行计算。因此，在底层链保持去中心化的同时，网络得以进行扩展。

将上千条交易打包进单一的证明需要巨量的计算工作，从而导致证明时间变长。冗长的证明时间会导致同样冗长的最终确认时间。因为在交易和证明被发送至底层链之前，用户的交易没有完全的最终性。而这一过程可能要花一些时间。例如，在 Starknet，我们预期证明时间初步上将需要几个小时。零知识证明在更好的操作、安全、和 UX 上都需要加速。

一个零知识证明系统包含三个步骤：配置，证明的生成，以及证明的检验。

在证明中要用到 6 个值：

以上就是深入浅出的「什么是零知识证明？」。就是这么简洁明了！当你真正过一遍其原理的时候，你会发现它其实挺简单。但是如果要明白如何加速零知识证明，我们就必须先明白它们在幕后是如何工作的。

零知识证明生成有两大主要瓶颈：多标量乘法（Multi-scalar Multiplication，MSM）和数论变换（Number Theoretic Transform，NTT）。这两项操作自己就能占到证明生成时间的 80% 到 95%?，具体则取决于零知识证明的承诺方案和具体的执行。首先，我们会介绍这些操作，其后，我们将提供各个操作能够如何加速的概览。

让我们从素数有限域开始。MSM 和 NTT 都发生在素数有限域中，因此了解素数有限域是重要的第一步。

想象一下，我们有一组 0-10 的数字。我们可以给这组数字添加一条规则，即：一旦我们数过数字 10?，我们就从数字 0 重新开始。如果我们减去最低的数字 0?，我们就从最后的 10 开始。

我们称数字 11 为模数，因为它是我们开始「循环」的数字。这种类型的数学被称为模算数。我们与模算数互动的最直观的经验是在报时时，我们以 12 为模数计算小时。

乘法也适用于模算数。如果我们把 9 ? 3=27?，我们会得到 5 作为我们的输出（如果你想检查，自己算一下！）。这被称为简单除法中的「余数」。我们可以把解决方案写成：

9 ? 3?mod(?11)=27?mod(?11)=5, 因为 11 ? 2 5=27. 2 代表我们循环的次数。

请注意，在我们这个 0-10 的集合中，无论我们选择什么数字做加法、减法或乘法，我们的结果永远是这个集合中的另一个数字。换句话说，没有办法跳出这个集合。在模算术中，除法要稍微复杂一些，但它的工作原理是相似的。因为我们的集合具有这种封闭性，所以它是一种特殊类型的集合，称为场。

从一个场到一个素数有限场是微不足道的。一个有限场是一个具有有限个元素的场。素数有限场是一个以素数为模数的有限场。由于我们的例子中 0-10 的集合是有限的，并且以质数 11 作为其模数，所以它是一个质数有限场！

现在我们已经涵盖了素数有限场，我们能够理解 MSM 了。假设我们有两行数字。我们可以对这些行进行的一个操作是，将一行中的每个元素，与另一行中的相应元素相乘，然后将乘积相加成为一个单一的数字。这种操作被称为点积，在数学中常用。下面是它的样子：

一个向量就是一个数字列表。注意，我们把两个向量的数字作为输入，并产生一个单一的数字作为输出。现在，让我们修改一下我们的例子。我们可以不计算 2 个数字向量的点积，而是计算一个点的向量和一个数字向量的点积。

一个标量就是一个普通的数字。在这种情况下，我们的输出不是一个单独的数字，而是一个网格上的新点。从图形上看，上面的计算看起来像下图这样：

这个计算包括将网格上的每一个点按一定的系数进行缩放，然后将所有的点相加，得到一个新的点。请注意，无论我们在这个网格上选取什么点，无论我们用什么标量乘以它们，我们的输出总是网格上的另一个点。

正如我们可以用网格上的点而不是整数来计算点积一样，我们也可以用椭圆曲线上的点来进行这种计算。椭圆曲线（EC）看起来像这样：

我们在零知识中使用的数学涉及椭圆曲线，它位于素数有限场中。因此，无论我们对椭圆曲线上的任何一点进行何种加法或乘法，其输出都将是椭圆曲线上的另一个点。标量的点积会输出另一个标量，（x, y）坐标的点积会产生另一个坐标，而椭圆曲线点的点积会产生另一个 EC 点。从视觉上看，椭圆曲线的点积看起来像这样：

椭圆曲线上的一个点与一个标量相乘称为点乘法。将两个点相加称为点加。点乘法和点加法都会在椭圆曲线上输出一个新的点。

在视觉上，椭圆曲线加法是一个简单的操作。给定任何两个 EC 点，我们可以在它们之间画一条线。如果我们看一下这条线与曲线第三次相交的地方，我们可以找到它在 X 轴上的反射，从而找到这两个点的和。要把一个点 G 加到自己身上，我们要找到曲线的切线，看看那条线与曲线的交点，然后在 X 轴上画一条反射线，直到再次与曲线相交。那个点就是 2?G. 因此，点乘法也很容易直观化。它只是涉及到将一个点本身相加。

关于如何从数学上计算 EC 加法的详细解释超出了本文的范围。在高层次上，EC 加法将两个非常大的整数相加，并以某个大的素数为模数。

这种将多个椭圆曲线点，与标量相乘（点乘），然后相加（点加），得到椭圆曲线上的一个新点的操作称为多标量乘法（MSM）。MSM 是 ZKP 生成中最重要的操作之一，然而它只是一个点积。

实际上比这还要简单： MSM 可以被改写为一堆 EC 点的加法。

因此，每当你听到「多标量乘法」时，我们所做的就是把许多 EC 点加在一起，得到一个新的 EC 点。

「水桶法」是用于加速 MSM 计算的一个巧妙的技巧。点加法计算在计算上是很便宜的。MSM 的问题在于点乘法。在真正的零知识证明中，我们的 EC 点所乘的标量是非常大的。对于每一个点乘法，计算都需要数百万次的求和。幸运的是，有一个简单的方法可以加快 MSM 的速度：我们可以并行计算所有的点乘法。

水桶法的关键思想是，我们可以将这些大点积减少为小点积，并行计算，然后将它们加在一起。

下面是它的工作原理。回顾一下，在计算机中，数字被表示为 1 和 0 的二进制数字。

因此，在我们的计算机上，我们的 EC 乘法实际上可能看起来像这样（只是用大得多的二进制数字）：

水桶法的第一步是将这些二进制标量分割成一定位数的窗口。在下面的图片中，我们将标量分割成 4 比特的窗口。

请注意，每个桶涵盖的数值从 0000=0 到 1111=15. 在我们将标量分解成 4 位的窗口后，我们可以将每个 EC 点分类到涵盖 0-15 范围的桶中。

对于一个给定的窗口，一旦我们把每个点都分类到一个桶里，我们就可以把所有的点加起来，得到每个桶的一个点。

请注意，在这个例子中，我们只显示了几个点，但实际上，每个桶都包含很多数字。一旦我们有了每个桶的值，我们就可以把它们都乘以它们的桶号，得到整个窗口的最终值。这个窗口的计算只是另一个点积。

一旦我们计算出每个窗口的窗口值，我们就可以把它们全部加起来，得到我们的最终输出。但首先，我们需要调整的是，每个窗口代表不同的数值范围。要做到这一点，我们需要将每个窗口乘以 2**?，其中 i 是窗口编号，s 是窗口长度。我们的窗口是 4 比特长，所以窗口大小是 4?。

然后，我们只需将所有数字相加，就可以得到我们的 MSM 的最终输出结果！简而言之，水桶法包括 3 个步骤：桶式积累、桶式汇总和窗口汇总。

几乎所有的零知识证明加速设置都使用了这种水桶法。例如，下面是由 Jump Crypto 和 Jump Trading 团队共同设计的 MSM 的硬件加速器的图示。它的大部分内容看起来很熟悉！

水桶法通过并行计算和有效平衡硬件上的工作负荷来加速 MSM，从而使证明生成时间得到显著改善。

NTT，也被称为快速傅里叶变换（FFT），是零知识证明生成中的第二个关键瓶颈。其操作和基础数学比 MSM 更复杂，所以我们不会在此提供技术解释。相反，我们将触及一些关于如何和为什么计算它们的直觉。

零知识证明涉及证明关于多项式的声明。多项式是一个类似 f(x)=x2 3?x 1 的函数。在零知识证明中，验证者证明他们拥有一些秘密信息的方式是，证明他们知道一个给定的多项式的输入，而这个输入可以求值到一个给定的输出。例如，验证者可能被赋予上述多项式，并被要求找到一个使输出等于 11 的输入（答案是 x=2?）。虽然这个任务对于小多项式来说是微不足道的，但是当给定的多项式非常大时，它就变得很有挑战性。事实上，零知识证明的整个基础是，这项任务对于大多项式来说是如此困难，以至于验证者将无法重复找到答案，除非他们知道秘密见证。

那么一个必要的步骤就是对多项式进行评估，以证明它等于某个输出。在零知识中，这些多项式是由算术电路表示的。

算术电路接受一个输入矢量，并产生一个在这些点上评估的多项式。算术电路的大小因应用而大不相同，从 ~?10000 到超过 1000000.

我们可以通过插入一个数字并计算其输出来直接评估一个多项式。这里有一个例子：

这种方法被称为直接评估，也是多项式的典型评估方式。问题是，直接求值的计算成本很高——它需要 N2 次运算，其中 N 是多项式的度数。因此，虽然这对小的多项式来说不是问题，但在处理大的算术电路时，直接评估会变得非常大。NTT 解决了这个问题。通过利用非常大的多项式评估背后的模式，NTT 可以评估一项多项式，只需进行 N*log(N) 计算。

如果我们要评估一个度数为 100 万的多项式（意味着多项式中的最高指数为 100 万），直接评估需要 1 万亿次操作。用 NTT 计算同样的多项式，只需要 2000 万次操作——速度提高了 5 万倍。

总之，评估多项式在零知识证明生成中起着关键作用，NTT 使我们能够更有效地评估多项式。然而，即使采用这种技术，大型 NTT 的处理时间仍然是零知识证明生成的主要瓶颈。

我们已经对零知识证明加速的最重要的计算做了一个高层次的概述。算法上的改进，如用于 MSM 的水桶法和用于评估多项式的 NTT，导致了零知识证明时间的重大进步。但要进一步提高零知识证明性能，我们必须优化底层硬件。

正如我们用水桶法所证明的那样，MSM 很容易被并行化。然而，即使在严重并行化的情况下，计算时间仍然很长。此外，MSM 有大量的内存需求，因为需要存储所有被操作的 EC 值。因此，尽管 MSM 具有在硬件上加速的潜力，但它们需要巨大的内存和并行计算。

NTT 对硬件不太友好。最重要的是，它们需要频繁地将数据洗进洗出外部存储器。数据是以随机访问模式从内存中检索的，这就增加了数据传输时间的延迟。随机内存访问和数据洗牌成为一个主要瓶颈，限制了 NTT 的并行化能力。大多数关于加速 NTT 的工作都集中在管理计算与内存的互动方式上。例如，这篇来自 Jump 的论文描述了一种方法，通过减少需要访问内存的次数和将数据流向计算机芯片，从而加速 NTT，将内存访问延迟降到最低。

解决 MSM 和 NTT 瓶颈的最简单方法是完全消除该操作。事实上，最近的一些工作，如 Hyperplonk 引入了对 Plonk 的修改，取消了执行 NTT 的需要。这使得 Hyperplonk 的加速更简单，但是引入了新的瓶颈，比如昂贵的 sumcheck 协议。在光谱的另一端，STARK 不需要 MSM，也提供了一个更简单的优化问题。

然而，加速 MSM 和 NTT 仅仅是零知识加速的第一步。即使我们可以假设将 MSM 和 NTT 的计算时间降至 0?，我们也只能实现证明生成时间的 5-20 倍加速。这是由于阿姆达尔定律，该定律指出，加速度受我们实际进行计算的时间部分的限制。如果 MSM 和 NTT 占了 90% 的证明时间，消除它们仍会留下 10% 的证明时间。

虽然加快 MSM 和 NTT 的速度很重要，但它们只是一个开始。为了取得进一步的进展，我们还必须加快「其他」操作，包括见证生成和散列。

有四种主要的计算机芯片类型： CPU、GPU、FPGA 和 ASIC. 每种芯片在其结构、性能和通用性方面都有不同的权衡。

中央处理单元（CPU）是大多数消费类电子产品如笔记本电脑中的芯片。它们的通用性使它们很适合用于各种设备和日常任务。高通用性是以牺牲性能为代价的。CPU 只能按顺序处理操作，使其在许多应用中表现不佳。

图形处理单元（GPU）是一种更专业的芯片。它们有大量的内核用于并行处理，使它们特别适合于图形渲染和机器学习等应用。尽管没有 CPU 那么普遍，也没有 FPGA 或 ASIC 那么专业，但 GPU 是一种普遍的、可获得的硬件。它们的流行导致了像 CUDA 和 OpenCL 这样的低级库的发展，帮助开发者利用 GPU 的可并行性，而不需要了解底层硬件。

现场可编程门阵列（FPGA）是可定制的芯片，可以以可重复使用的方式为特定的应用进行优化。开发人员可以使用硬件描述语言（HDL）直接对其硬件进行编程，从而实现更高的性能。硬件可以被反复修改，而不需要新的芯片。FPGA 的缺点是其更大的技术复杂性——很少有开发者有编程经验。即使拥有必要的专业知识，定制 FPGA 的研究和开发成本也很高。尽管如此，FPGA 在从国防科技到电信等行业都有应用。

特定应用集成电路（ASIC）是为某一特定任务过度优化的定制设计芯片。与允许硬件重新编程的 FPGA 不同，ASIC 的规格是根植于芯片中的，防止它们被重新利用。对于任何特定的任务，ASIC 都是最强大和最节能的芯片。例如，比特币挖矿是由 ASIC 主导的，它计算的哈希值远远多于其他类型的芯片。

鉴于这些选择，哪一个是最好的零知识证明成？这取决于应用程序。像 Penumbra 和 Aztec 这样的隐私应用程序允许用户在提交给网络之前，通过创建其交易的 SNARK 来进行私人交易。由于所需的证明相对较小，只需使用他们的 CPU 就可以在他们的本地浏览器中生成。但对于真正需要硬件加速的较大的零知识证明，CPU 是不够的。

我们可以通过多种方式在硬件上加速零知识证明：

任何类型的芯片都可以被流水线化和超频。GPU 非常适合并行化，但它们的架构是固定的；开发者被限制在所提供的内核和内存上。GPU 不能为大整数创造更好的表示方法，也不能使内存访问模式更可预测。虽然 CUDA 和 OpenCL 等 GPU 库提供了一定程度的灵活性，但硬件有局限性；更高的性能最终需要更灵活的硬件。尽管如此，GPU 仍然可以加速零知识证明。零知识硬件加速公司 Ingonyama 正在建立 ICICLE，这是一个用 CUDA 为 Nvidia GPU 建立的零知识加速库。该库包含加速常见零知识操作的工具，如 MSM 和 NTT.

FPGA 的时钟速度比 GPU 低，但可以通过编程来解决上述所有的加速策略。他们最大的问题只是对其进行编程。对于零知识来说，组织一个既有密码学专业知识又有 FPGA 工程专业知识的团队是非常困难的。早期为零知识加速生产 FPGA 的团队是像 Jump Crypto 和 Jane Street 这样已经拥有 FPGA 和密码学人才的复杂交易公司。FPGA 也仍然有瓶颈——单个 FPGA 往往没有足够的片上存储器来执行 NTT，需要额外的外部存储器。

将硬件驱动的零知识速商业化的最严格的尝试，甚至比单片 FPGA 更进一步。为了获得进一步的收益，像 Cysic 和 Ulvetanna 这样的公司正在建立 FPGA 服务器和 FPGA 集群，结合多个 FPGA 提供额外的存储器和可并行计算，以进一步加速证明生成。这些团队的早期结果是有希望的： Cysic 声称他们的 FPGA 服务器在 MSM 比 Jump 的 FPGA 架构快 100 倍，在 NTT 比最知名的 GPU 实现快 13 倍。标准化的基准还没有建立起来，但结果指向了重大改进。

ASIC 能够为零知识证明生成提供绝对最高的性能。今天的 ZK ASIC 的问题是，他们正在为一个移动的目标进行优化——零知识正在迅速发展。由于 ASIC 需要 1 - 2 年和 1000 - 2000 万美元来生产，他们必须等到零知识已经足够稳固，所生产的芯片不会很快被淘汰。另外，零知识证明的市场规模在未来几年才变得足够大，足以证明 ASIC 所需的资本投资是合理的。

FPGA 和 ASIC 之间有一个微妙的梯度。虽然 FPGA 是可编程的，但它们的芯片有不可编程的硬化部分。固化部件的性能比可编程的要高得多。随着零知识市场的发展，像 Xilinx（AMD）和 Altera（Intel）这样的 FPGA 公司可以生产新的 FPGA，嵌入专门为零知识证明中的常见操作设计的硬化组件。同样，ASIC 也可以被设计成包括一些灵活性。例如，Cysic 未来计划生产专门针对 MSM、NTT 和其他一般操作的 ASIC，同时保持灵活性以适应许多证明系统。

从长远来看，ASIC 将提供最强大的零知识证明加速功能。在此之前，我们预计 FPGA 将服务于计算最密集的零知识用例，因为其可编程性使其能够比 GPU 更快地执行 NTT、MSM 和其他加密操作。对于某些应用，GPU 将提供性能和可及性之间最具吸引力的平衡。

区块链行业多年来一直在等待零知识证明为生产做好准备。这项技术已经吸引了我们的想象力，承诺增强去中心化应用的可扩展性、隐私和互操作性。直到最近，该技术还不现实，主要是由于硬件限制和漫长的证明时间。这种情况正在迅速改变：零知识证明方案和硬件的进步正在解决 MSM 和 NTT 等计算瓶颈问题。有了更好的算法和更强大的硬件，我们可以将零知识证明加速到足以释放其潜力，从而彻底改变 Web3。

鸣谢： 特别感谢 Brian Retford（RiscZero）、Leo Fan（Cysic）、Emanuele Cesena（Jump Crypto）、Mikhail Komarov（=nil; Foundation）、Anthony Rose（zkSync）、Will Wolf 和 Luke Pearson（Polychain），以及 Penumbra Labs 团队的精彩讨论和反馈，为本文做出了贡献。