作者：Trace. 编译：Cointime.com QDD

零知识证明（ZKP）允许一方向另一方证明一个陈述的真实性，而不透露任何关于该陈述的额外信息。虽然这种密码学原语自上世纪80年代就存在，但直到区块链技术的出现，ZKP才找到了实际应用，包括区块链的可扩展性、隐私性、互操作性和身份验证等方面。

尽管ZKP在解决区块链技术中的许多重要问题方面有着巨大潜力，但它仍然是一项不成熟的技术。其中一个主要问题是其漫长的证明时间。随着ZKP应用的发展，其证明的复杂性也在增加。这些陈述需要更大的算术电路，导致证明时间增加。生成一个ZKP可能需要对底层计算的增加达到100万倍。因此，许多团队正在研究改进软件和硬件以加速ZKP的方法。

在本文中，我们提供了ZKP加速的概述。我们首先总结了ZKP生成中的主要操作，然后介绍了如何加速这些操作。

零知识证明简介

ZKP允许一方，称为证明者，向另一方，称为验证者，证明其正确执行了一个计算。ZKP系统具有三个关键属性：

在区块链环境中使用的主要类型的ZKP是zk-SNARKs（或“零知识简洁非交互式知识论证”）。这些证明在传统ZKP的基础上增加了两个附加属性：简洁性和非交互性。简洁性意味着证明的大小很小，通常只有几百字节，并且可以由验证者快速检查。非交互性意味着证明者和验证者不需要进行交互；证明本身足够了。旧的ZKP需要证明者和验证者相互发送消息来生成证明。

简洁性使得ZKP快速且计算成本低廉。这使得它们成为一种出色的扩展技术。在有效性回滚（即zkRollups）中，强大的证明者可以计算成千上万个交易的输出，生成其正确性的简洁证明，并将它们发送到基本链。在那里，验证者可以检查证明并立即接受所有包含的交易结果，而无需自行计算它们。因此，网络可以实现规模化，而基本链仍然保持去中心化。

将成千上万个交易打包成单个证明需要大量的计算，并导致较长的证明时间。由于用户的交易在其交易及其证明被提交到基本链之前不具有完全的确定性，所以这会导致更长的最终时间。这可能需要一些时间。例如，在Starknet中，我们预计最初的证明时间将需要几个小时。为了获得更好的性能、安全性和用户体验，需要加速ZKP。

ZKP系统包括三个步骤：设置、证明生成和证明验证。

证明中使用了6个值。

这就是零知识的要点。看起来实际上相当简单。但要理解如何加速ZKP，我们必须了解它们在内部是如何工作的。

MSMs和NTTs

ZKP生成中存在两个主要瓶颈：多标量乘法（MSMs）和数论变换（NTTs）。根据ZKP的承诺方案和具体实现，这些操作单独可以占据证明生成时间的80-95%。首先，让我们介绍这些操作，然后我们将概述如何加速每个操作。

素数有限域

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

假设我们有一个数字集合0-10。我们可以给这个数字集合添加一个规则，即：一旦我们数到超过数字10，我们就重新从数字0开始数。例如，如果我们计算9+2=11，我们将重新回到集合的开头，得到0。减法也类似。如果我们从最小的数字0开始减，我们就会重新回到集合的末尾，即10。

我们将数字11称为模数，因为它是我们“循环”的数字。这种数学被称为模运算。我们与模运算最直观的接触是在计时上，我们将小时数模12计数。

在模运算中，乘法也适用。如果我们计算9*3=27，我们将得到5作为输出（如果您愿意，可以自行计算验证！）。这在简单除法中称为“余数”。我们可以将解写为：

9 * 3mod(11) = 27mod(11) = 5，因为11*2 + 5 = 27。2代表我们循环集合的次数。

请注意，在我们的0-10集合中，无论我们选择什么数字进行加法、减法或乘法，我们的结果总是集合中的另一个数字。换句话说，没有办法跳出集合。除法在模运算中稍微复杂一些，但原理类似。由于我们的集合具有这种封闭性质，它是一种特殊类型的集合，称为域。

从域到素数有限域的转换非常简单。有限域是一个具有有限元素数量的域。素数有限域是一个具有素数作为模数的有限域。由于我们的示例集合0-10是有限的，并且其模数是素数11，它就是一个素数有限域！

多标量乘法

既然我们已经了解了素数有限域，我们就能理解多标量乘法（MSMs）了。假设我们有两行数字。我们可以对这些行执行的一种操作是，将一行中的每个元素与另一行中的对应元素相乘，并将乘积相加得到一个单独的数字。这个操作被称为点积，是数学中常用的操作。下面是它的样子：

矢量只是一系列数字。请注意，我们将两个数字矢量作为输入，并产生一个单独的数字作为输出。现在，让我们修改一下我们的例子。我们不再计算两个数字矢量的点积，而是计算点矢量和数字矢量的点积。

标量只是一个普通的数字。在这种情况下，我们的输出不是一个单独的数字，而是网格上的一个新点。从图形上看，计算过程如下：

这个计算涉及将网格上的每个点按某个因子进行缩放，然后将所有点相加以得到一个新点。请注意，无论我们选择网格上的哪些点，也无论我们将它们乘以什么标量，我们的输出总是网格上的另一个点。

就像我们可以用整数而不是点来计算点积一样，我们也可以用椭圆曲线上的点来执行这个计算。一个椭圆曲线（EC）看起来像这样：

在ZK中使用的数学涉及嵌套在素数有限域中的椭圆曲线。因此，无论我们对椭圆曲线上的任何点执行什么样的加法或乘法，其输出始终是椭圆曲线上的另一个点。标量的点积输出另一个标量，（x，y）坐标的点积会产生另一个坐标，椭圆曲线点的点积会产生另一个EC点。在视觉上，椭圆曲线的点积如下所示：

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

在视觉上，椭圆曲线加法是一个简单的操作。给定任意两个EC点，我们可以在它们之间画一条线。如果我们查看该线在曲线上第三次相交的位置，我们可以找到其关于x轴的反射，以得到这两个点的和。要将点G加上它自身，我们找到曲线的切线，看它与曲线相交的位置，然后画一条反射在x轴上的线，直到再次与曲线相交。那个点就是2G。因此，点乘法也很容易形象化，只需将一个点自身加上。

关于如何在数学上计算EC加法的详细说明超出了本文的范围。在高层次上，EC加法是将两个非常大的整数相加，模一些大的素数。

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

事实上，它甚至比这更简单：MSM可以重写为许多EC点加法。

因此，无论您听到“多标量乘法”，我们所做的只是将许多EC点相加，以得到一个新的EC点。

木桶法（The bucket method）

“木桶法”是一种用于加速MSM计算的巧妙技巧。点加法计算是计算量较小的操作。MSMs的问题在于点乘法。在实际的ZKP证明中，我们要将EC点乘以的标量非常大。对于每个点乘法，计算将需要数百万次求和。幸运的是，有一种简单的方法可以加速MSMs：我们可以并行计算所有的点乘法。

木桶法的关键思想是我们可以将这些大的点积缩小为较小的点积，以并行计算它们，然后将它们相加。

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

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

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

请注意，每个桶覆盖了从0000 = 0到1111 = 15的值范围。在我们将标量分割成4位窗口后，我们可以将每个EC点排序到覆盖0-15范围的桶中。

对于给定的窗口，一旦我们将每个点都排序到一个桶中，我们就可以将该桶中的所有点相加，以获得每个桶的最终点。

请注意，这个示例中只显示了一些点，但在实践中，每个桶包含许多数字。一旦我们有了每个桶的值，我们就可以将它们乘以它们的桶编号，以获得整个窗口的最终值。这个窗口计算只是另一个点积。

一旦我们计算了每个窗口的窗口值，我们就可以将它们相加，以获得最终输出。但首先，我们需要调整这些窗口表示不同值范围的事实。为此，我们需要将每个窗口乘以2ⁱ*ˢ，其中i是窗口编号，s是窗口长度。我们的窗口长度为4，所以窗口大小为4。

然后，我们只需将所有数字相加，即可获得MSM的最终输出！回顾一下，木桶法包括3个步骤：桶累积、桶聚合和窗口聚合。

这种木桶法在几乎所有的ZKP加速设置中都得到了使用。例如，下面是由Jump Crypto和Jump Trading团队共同设计的MSM硬件加速器的示意图。其中大部分看起来很熟悉！

木桶法通过并行化计算并在硬件上有效地平衡工作负载，从而显著提高证明生成时间。

数论变换（NTTs）

NTTs，也称为快速傅里叶变换（FFTs），是零知识证明（ZKP）生成中的第二个主要瓶颈。其操作和底层数学比MSMs更复杂，因此我们不会在这里提供技术解释。相反，我们将简要介绍它们的计算方式和原理。

ZKPs涉及证明关于多项式的陈述。多项式是一个函数，如f（x）= x² + 3x + 1。在ZKPs中，证明者展示他们拥有某些秘密信息的方式是展示他们知道一个使得给定多项式的输出等于给定输出的输入。例如，证明者可能会被给予上述多项式，并被要求找到一个使得输出等于11的输入（答案是x = 2）。虽然对于小多项式来说这个任务很简单，但当给定的多项式非常大时，它就变得具有挑战性。实际上，ZKP的基础在于对于大多项式来说，这个任务是如此困难，以至于除非证明者知道秘密见证，否则他们将无法重复找到答案。

因此，评估多项式以证明它等于某个输出是必要的。在ZK中，这些多项式由算术电路表示。

算术电路接受输入向量并在这些点上计算多项式的值。算术电路的规模因应用而异，范围从大约10,000到超过1,000,000。

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

这种方法称为直接计算，通常用于多项式的计算。问题是直接计算的计算成本很高——它需要N²次操作，其中N是多项式的次数。因此，对于小多项式来说，这不是一个问题，但在处理大型算术电路时，直接计算变得非常昂贵。NTTs解决了这个问题。通过利用评估非常大多项式的模式，NTTs可以使用仅需N*log(N)次计算来评估多项式。

例如，如果我们要评估一个次数为100万的多项式（意味着多项式中最高的指数是100万），直接计算需要进行1万亿次操作。而使用NTT计算相同的多项式只需要2000万次操作，加速了50000倍。

总之，评估多项式在ZKP生成中起着关键作用，而NTTs使我们能够更高效地评估多项式。然而，即使使用这种技术，大型NTTs的处理时间仍然是ZKP生成中的一个主要瓶颈。

ZK硬件

我们已经对ZKP加速中最重要的计算进行了高级概述。像MSM的桶方法和NTTs用于评估多项式的算法改进，大大提高了ZK证明时间。但为了进一步提高ZKP性能，我们必须优化底层硬件。

加速MSMs和NTTs

正如我们通过桶方法所演示的那样，MSMs易于并行化。然而，即使在进行了大量并行化的情况下，计算时间仍然很长。此外，MSMs具有巨大的内存需求，这源于需要存储正在操作的所有椭圆曲线值。因此，尽管MSMs有可能在硬件上加速，但它们需要巨大的内存和并行计算。

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

解决MSMs和NTTs瓶颈的最简单方法是完全消除这两个操作。事实上，一些最近的工作，如Hyperplonk，引入了对Plonk的修改，消除了执行NTTs的需求。这使得Hyperplonk更容易加速，但也引入了新的瓶颈，如昂贵的sumcheck协议。在另一方面，STARKs不需要MSMs，也提供了一个更简单的优化问题。

然而，加速MSMs和NTTs只是ZK加速的第一步。即使我们能够假设将MSMs和NTTs的计算时间降至0，我们在证明生成时间上只能实现5-20倍的加速。这是由于阿姆达尔定律（Amdahl‘s law）所限制，该定律指出加速受限于我们实际进行计算的时间所占的比例。如果MSMs和NTTs占证明时间的90％，消除它们仍将留下10％的证明时间。

尽管加速MSMs和NTTs很重要，但这只是个开始。要取得进一步的进展，我们还必须加速“其他”操作，包括见证生成和哈希计算。

硬件概述

计算机芯片有四种主要类型：中央处理器（CPU）、图形处理器（GPU）、现场可编程门阵列（FPGA）和专用集成电路（ASIC）。每种芯片在其架构、性能和通用性方面都有不同的权衡。

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

图形处理器（GPU）是一种更专用的芯片。它们拥有大量的核心用于并行处理，因此特别适用于图形渲染和机器学习等应用。尽管比CPU更专用，比FPGA或ASIC更不专业，但GPU是一种普遍和易于获取的硬件。它们的流行程度导致了低级别的库，如CUDA和OpenCL的开发，这些库帮助开发人员利用GPU的并行性而无需了解底层硬件。

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

专用集成电路（ASIC）是针对特定任务进行超优化的定制芯片。与允许硬件重新编程的FPGA不同，ASIC规格已嵌入芯片中，防止其被重新用于其他目的。对于任何给定的任务，ASIC是性能最强大且能效最高的芯片。例如，比特币挖矿由ASIC主导，其计算的哈希远远超过其他任何类型的芯片。

在这些选项中，哪种对于ZKP生成最好？这取决于应用。像Penumbra和Aztec这样的隐私应用程序允许用户在提交到网络之前创建其交易的SNARK以进行私密交易。由于所需的证明相对较小，可以在用户的本地浏览器中使用CPU生成。但对于真正需要硬件加速的较大ZKP，CPU是不够的。

硬件加速

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

任何类型的芯片都可以进行流水线处理和超频。GPU非常适合并行化，但其架构是固定的；开发人员受限于提供的核心和内存。GPU无法创建更好的大整数表示，也无法使内存访问模式更可预测。尽管如此，GPU仍然可以加速ZKPs。ZK硬件加速公司Ingonyama正在构建ICICLE，这是一个基于Nvidia GPU的CUDA ZK加速库。该库包含用于加速常见ZK操作（如MSMs和NTTs）的工具。

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

最严谨的商业化硬件驱动ZK加速的尝试正在超越单个FPGA。为了进一步提升性能，Cysic和Ulvetanna等公司正在构建FPGA服务器和FPGA集群，将多个FPGA组合在一起，提供额外的内存和可并行化计算，进一步加速证明生成。这些团队的初步结果是令人鼓舞的：Cysic声称他们的FPGA服务器在MSM方面比Jump的FPGA架构快100倍，在NTT方面比最好的已知GPU实现快13倍。尽管尚未建立标准化的基准测试，但结果表明了重大的改进。

ASIC能够为ZKP生成提供绝对最高的性能。目前ZK ASIC的问题在于它们正在为一个不断发展的目标进行优化——ZK正在迅速发展。由于ASIC的生产需要1-2年和1000-2000万美元，它们必须等到ZK已经足够稳定，以使生产的芯片不会很快过时。此外，ZK证明的市场规模仅在未来几年内变得足够大，以证明对ASIC的资本投资是有意义的。

FPGA和ASIC之间存在微妙的渐变。虽然FPGA是可编程的，但它们的芯片中有一些硬件部分是固化的。固化的组件比可编程组件具有更高的性能。随着ZK市场的发展，Xilinx（AMD）和Altera（Intel）等FPGA公司可能会生产新的FPGA，其中嵌入了专门针对ZK证明中常见操作的固化组件。类似地，ASIC可以设计为具有一定的灵活性。例如，Cysic计划未来生产专门针对MSMs、NTTs和其他通用操作的ASIC，同时保持适应多个证明系统的灵活性。

从长远来看，ASIC将为ZKP加速提供最强大的能力。在此之前，我们预计FPGA将为计算密集型的ZK应用提供最好的解决方案，因为其可编程性使其能够比GPU更快地执行NTT、MSM和其他加密操作。对于某些应用程序，GPU将在性能和可访问性之间提供最有吸引力的平衡。

结论

区块链行业已经花费多年时间等待ZKPs达到生产就绪状态。这项技术通过提升分布式应用程序的可扩展性、隐私性和互操作性来吸引了我们的想象力。直到最近，由于硬件限制和长时间的证明时间，这项技术一直是不切实际的。但是，情况正在迅速改变：ZKP证明方案和硬件的进步正在解决像MSMs和NTTs这样的计算瓶颈。通过更好的算法和更强大的硬件，我们可以加速ZK证明，以释放其革命化Web3潜力。