原文标题：AcceleratingZero-KnowledgeProofs
原文作者：FigmentCapital
原文编译：Lynn，MarsBit
零知识证明允许一个团体在向另一个团体证明一条声明时不需要透露除去「该声明为真实的」的信息以外的任何额外信息。尽管这项密码原语早在上世纪八十年代就已出现，但直到区块链技术的萌发，零知识证明才发现其实际应用，包括区块链扩展、隐私、互操作性，和身份。
尽管声称其可以解决区块链技术中的许多最重大的难题，零知识证明仍旧是一项不成熟的技术。在这些问题之中，最主要的其中之一是其证明时间之久。零知识技术应用在不断改进，其证明的复杂程度也在改进。这些声明需要更大的算数电路，导致证明时间飙升。生产一个零知识证明可能需要比底层计算增加多达百万倍。相应地，有大量的团队正在研究可以改进加速零知识证明所需要的软件和硬件。
在本文中，我们将提供加速零知识证明的概览。我们将总结生产零知识证明的主要操作作为讨论的起点，并在之后转向讨论这些操作可以如何被加速。
快速上手：什么是零知识证明？
零知识证明允许一方，向另一方证明他们成功地完成了一次计算。一个零知识证明拥有以下三个关键特性：
完整性：如果证明者生成了一项有效的证明，一个诚实的验证者将视该声明是有效的。
合理性：如果该声明是虚假的，一个证明者将无法生成一项看起来有效的证明。
零知识：如果该声明是真实的，一个验证者不会知道除去「该声明是真实的」以外的任何信息。
区块链背景下最主要的零知识证明的类型是zk-SNARK。这终证明在上述的传统的零知识证明的三个特性之上额外有两条特性：简洁性和非交互式。具有简洁性意味着证明的规格小，通常只有几百字节，并且可以迅速地被验证者检验。非交互式的特性意味着证明者和验证者之间不需要交互，单单该证明本身已经足够。较老的零知识证明需要证明者和验证者之间互发信息以生成一项证明。
简介性使零知识证明能够快速地验证，且从计算角度来看很便宜。这使它们成为了一项很棒的扩展技术。在有效性rollup中，强大的证明者能够计算数以千计的交易的输出，针对它们的正确性生产一个简洁的证明，并将它们发送到底层链上。在那里，验证者能够检验该证明并立刻接受所有已包含的交易的结果，而无需再自行计算。因此，在底层链保持去中心化的同时，网络得以进行扩展。
将上千条交易打包进单一的证明需要巨量的计算工作，从而导致证明时间变长。冗长的证明时间会导致同样冗长的最终确认时间。因为在交易和证明被发送至底层链之前，用户的交易没有完全的最终性。而这一过程可能要花一些时间。例如，在Starknet，我们预期证明时间初步上将需要几个小时。零知识证明在更好的操作、安全、和UX上都需要加速。
一个零知识证明系统包含三个步骤：配置，证明的生成，以及证明的检验。
在证明中要用到6个值：
R-随即数字：建立一个零知识证明系统需要一个一次性的秘密随机数。如果任何群体知道了该随机数，他们就可以破解代码并确认秘密输入值，消除其零知识属性。这便是「可信设置」的概念从何而来。在可信配置中，不同群体聚到一起，共同生成该随机数，以保证没有任何个体能够知道该秘密。作为一名用户，你必须信任该设置是被正确完成的，以确保你的信息是私密的。注意，STARK并不要求可信设置。
S?-证明者设置常数：设置完成后将交由证明者的常数，允许其验证一项有效的证明。
S?-验证者设置常数：设置完成后将交由验证者的常数，允许其验证一项有效的证明。
X-公开输入值：我们用于计算的输入值。这些将被给到证明者和验证者，且并不是保密的。
W-私密输入值：这是秘密的输入值，被称作见证，只会被给到证明者。需要注意的是，在上面的图表中，见证不会被交给验证者。零知识的关键就是它使我们能够证明有关见证的声明，且不需要泄露见证。
P-证明：这是由证明者创建、发送给给验证者的证明。
以上就是深入浅出的「什么是零知识证明？」。就是这么简洁明了！当你真正过一遍其原理的时候，你会发现它其实挺简单。但是如果要明白如何加速零知识证明，我们就必须先明白它们在幕后是如何工作的。
MSM与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点。从视觉上看，椭圆曲线的点积看起来像这样：
椭圆曲线上的一个点与一个标量相乘称为点乘法。将两个点相加称为点加。点乘法和点加法都会在椭圆曲线上输出一个新的点。
在视觉上，椭圆曲线加法是一个简单的操作。给定任何两个EC点，我们可以在它们之间画一条线。如果我们看一下这条线与曲线第三次相交的地方，我们可以找到它在X轴上的反射，从而找到这两个点的和。要把一个点G加到自己身上，我们要找到曲线的切线，看看那条线与曲线的交点，然后在X轴上画一条反射线，直到再次与曲线相交。那个点就是2?G.因此，点乘法也很容易直观化。它只是涉及到将一个点本身相加。
关于如何从数学上计算EC加法的详细解释超出了本文的范围。在高层次上，EC加法将两个非常大的整数相加，并以某个大的素数为模数。
这种将多个椭圆曲线点，与标量相乘，然后相加，得到椭圆曲线上的一个新点的操作称为多标量乘法。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个步骤：桶式积累、桶式汇总和窗口汇总。
桶式积累：对于每个窗口，根据其系数，将每个EC点分类到一个桶中。然后将每个桶中的所有点相加，得到每个桶的最终值。
桶式汇总：对于每个窗口，用所有的桶值乘以它们的桶号，然后加在一起，得到一个窗口值。
窗口汇总：把所有的窗口值，乘以它们的位偏移量，然后把它们加在一起，得到你最终的椭圆曲线点。
几乎所有的零知识证明加速设置都使用了这种水桶法。例如，下面是由JumpCrypto和JumpTrading团队共同设计的MSM的硬件加速器的图示。它的大部分内容看起来很熟悉！
水桶法通过并行计算和有效平衡硬件上的工作负荷来加速MSM，从而使证明生成时间得到显著改善。
数论变换
NTT，也被称为快速傅里叶变换，是零知识证明生成中的第二个关键瓶颈。其操作和基础数学比MSM更复杂，所以我们不会在此提供技术解释。相反，我们将触及一些关于如何和为什么计算它们的直觉。
零知识证明涉及证明关于多项式的声明。多项式是一个类似f(x)=x2+3?x+1的函数。在零知识证明中，验证者证明他们拥有一些秘密信息的方式是，证明他们知道一个给定的多项式的输入，而这个输入可以求值到一个给定的输出。例如，验证者可能被赋予上述多项式，并被要求找到一个使输出等于11的输入。虽然这个任务对于小多项式来说是微不足道的，但是当给定的多项式非常大时，它就变得很有挑战性。事实上，零知识证明的整个基础是，这项任务对于大多项式来说是如此困难，以至于验证者将无法重复找到答案，除非他们知道秘密见证。
那么一个必要的步骤就是对多项式进行评估，以证明它等于某个输出。在零知识中，这些多项式是由算术电路表示的。
算术电路接受一个输入矢量，并产生一个在这些点上评估的多项式。算术电路的大小因应用而大不相同，从~?10000到超过1000000.
我们可以通过插入一个数字并计算其输出来直接评估一个多项式。这里有一个例子：
这种方法被称为直接评估，也是多项式的典型评估方式。问题是，直接求值的计算成本很高——它需要N2次运算，其中N是多项式的度数。因此，虽然这对小的多项式来说不是问题，但在处理大的算术电路时，直接评估会变得非常大。NTT解决了这个问题。通过利用非常大的多项式评估背后的模式，NTT可以评估一项多项式，只需进行N*log(N)计算。
如果我们要评估一个度数为100万的多项式，直接评估需要1万亿次操作。用NTT计算同样的多项式，只需要2000万次操作——速度提高了5万倍。
总之，评估多项式在零知识证明生成中起着关键作用，NTT使我们能够更有效地评估多项式。然而，即使采用这种技术，大型NTT的处理时间仍然是零知识证明生成的主要瓶颈。
零知识硬件
我们已经对零知识证明加速的最重要的计算做了一个高层次的概述。算法上的改进，如用于MSM的水桶法和用于评估多项式的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那么普遍，也没有FPGA或ASIC那么专业，但GPU是一种普遍的、可获得的硬件。它们的流行导致了像CUDA和OpenCL这样的低级库的发展，帮助开发者利用GPU的可并行性，而不需要了解底层硬件。
现场可编程门阵列是可定制的芯片，可以以可重复使用的方式为特定的应用进行优化。开发人员可以使用硬件描述语言直接对其硬件进行编程，从而实现更高的性能。硬件可以被反复修改，而不需要新的芯片。FPGA的缺点是其更大的技术复杂性——很少有开发者有编程经验。即使拥有必要的专业知识，定制FPGA的研究和开发成本也很高。尽管如此，FPGA在从国防科技到电信等行业都有应用。
特定应用集成电路是为某一特定任务过度优化的定制设计芯片。与允许硬件重新编程的FPGA不同，ASIC的规格是根植于芯片中的，防止它们被重新利用。对于任何特定的任务，ASIC都是最强大和最节能的芯片。例如，比特币挖矿是由ASIC主导的，它计算的哈希值远远多于其他类型的芯片。
鉴于这些选择，哪一个是最好的零知识证明成？这取决于应用程序。像Penumbra和Aztec这样的隐私应用程序允许用户在提交给网络之前，通过创建其交易的SNARK来进行私人交易。由于所需的证明相对较小，只需使用他们的CPU就可以在他们的本地浏览器中生成。但对于真正需要硬件加速的较大的零知识证明，CPU是不够的。
硬件加速
我们可以通过多种方式在硬件上加速零知识证明：
并行处理：同时进行独立计算。
管线：确保我们的计算机的所有资源在任何时候都被使用，以最大限度地提高我们在一个时钟周期内的计算量。
超频：将硬件的时钟速度提高到超过默认速度，以加速计算。如果不小心这样做，可能会损坏硬件。
增加内存带宽：使用更高带宽的内存来提高我们读写数据的速度。在零知识中，证明生成的瓶颈往往不是计算，而是数据的传递。
在内存中实现对大整数的更好表示：GPU被设计为在浮点数上进行计算。零知识运算是在有限域的大整数上进行的。在内存中实现对这些大整数的更好表示，可以减少内存需求和数据洗牌。
使内存访问模式可预测：像PipeZK这样的论文探讨了在计算NTT的同时使内存访问模式可预测的方法，使其更容易并行化。
任何类型的芯片都可以被流水线化和超频。GPU非常适合并行化，但它们的架构是固定的；开发者被限制在所提供的内核和内存上。GPU不能为大整数创造更好的表示方法，也不能使内存访问模式更可预测。虽然CUDA和OpenCL等GPU库提供了一定程度的灵活性，但硬件有局限性；更高的性能最终需要更灵活的硬件。尽管如此，GPU仍然可以加速零知识证明。零知识硬件加速公司Ingonyama正在建立ICICLE，这是一个用CUDA为NvidiaGPU建立的零知识加速库。该库包含加速常见零知识操作的工具，如MSM和NTT.
FPGA的时钟速度比GPU低，但可以通过编程来解决上述所有的加速策略。他们最大的问题只是对其进行编程。对于零知识来说，组织一个既有密码学专业知识又有FPGA工程专业知识的团队是非常困难的。早期为零知识加速生产FPGA的团队是像JumpCrypto和JaneStreet这样已经拥有FPGA和密码学人才的复杂交易公司。FPGA也仍然有瓶颈——单个FPGA往往没有足够的片上存储器来执行NTT，需要额外的外部存储器。
将硬件驱动的零知识速商业化的最严格的尝试，甚至比单片FPGA更进一步。为了获得进一步的收益，像Cysic和Ulvetanna这样的公司正在建立FPGA服务器和FPGA集群，结合多个FPGA提供额外的存储器和可并行计算，以进一步加速证明生成。这些团队的早期结果是有希望的：Cysic声称他们的FPGA服务器在MSM比Jump的FPGA架构快100倍，在NTT比最知名的GPU实现快13倍。标准化的基准还没有建立起来，但结果指向了重大改进。
ASIC能够为零知识证明生成提供绝对最高的性能。今天的ZKASIC的问题是，他们正在为一个移动的目标进行优化——零知识正在迅速发展。由于ASIC需要1-2年和1000-2000万美元来生产，他们必须等到零知识已经足够稳固，所生产的芯片不会很快被淘汰。另外，零知识证明的市场规模在未来几年才变得足够大，足以证明ASIC所需的资本投资是合理的。
FPGA和ASIC之间有一个微妙的梯度。虽然FPGA是可编程的，但它们的芯片有不可编程的硬化部分。固化部件的性能比可编程的要高得多。随着零知识市场的发展，像Xilinx和Altera这样的FPGA公司可以生产新的FPGA，嵌入专门为零知识证明中的常见操作设计的硬化组件。同样，ASIC也可以被设计成包括一些灵活性。例如，Cysic未来计划生产专门针对MSM、NTT和其他一般操作的ASIC，同时保持灵活性以适应许多证明系统。
从长远来看，ASIC将提供最强大的零知识证明加速功能。在此之前，我们预计FPGA将服务于计算最密集的零知识用例，因为其可编程性使其能够比GPU更快地执行NTT、MSM和其他加密操作。对于某些应用，GPU将提供性能和可及性之间最具吸引力的平衡。
结论
区块链行业多年来一直在等待零知识证明为生产做好准备。这项技术已经吸引了我们的想象力，承诺增强去中心化应用的可扩展性、隐私和互操作性。直到最近，该技术还不现实，主要是由于硬件限制和漫长的证明时间。这种情况正在迅速改变：零知识证明方案和硬件的进步正在解决MSM和NTT等计算瓶颈问题。有了更好的算法和更强大的硬件，我们可以将零知识证明加速到足以释放其潜力，从而彻底改变Web3。
鸣谢：特别感谢BrianRetford、LeoFan、EmanueleCesena、MikhailKomarov、AnthonyRose、WillWolf和LukePearson，以及PenumbraLabs团队的精彩讨论和反馈，为本文做出了贡献。
郑重声明： 本文版权归原作者所有， 转载文章仅为传播更多信息之目的， 如作者信息标记有误， 请第一时间联系我们修改或删除， 多谢。