本文来自a16z，原文作者：JustinThaler，由Odaily星球日报译者Katie辜编译。
SNARK是一种重要的密码原语，用于发现区块链可扩展性和隐私的应用。SNARK允许某人向不可信验证器V证明他们知道一些数据。证明这一点的简单方法是将数据发送给V，然后V可以直接检查其有效性。SNARK实现了同样的效果，但对V来说成本更高。特别是SNARK证明应该比包含数据本身的原始证明更短。
SNARK的验证成本可能会有所不同，但成果通常都很好。例如，PlonK的证明在以太坊上的验证成本约为29万gas，而?StarkWare的证明成本约为500万gas。SNARK可能适用于区块链之外的各种不同的设置，例如，允许使用快速但不可信的服务器和硬件。
但由于SNARK验证通常很便宜，适用性的主要决定因素是SNARK证明者P的成本。本文中将解释如何估算这些成本，以确定何时合理使用SNARK，以及未来如何改进SNARK。值得注意的是，这是一个快速发展的领域，本文中讨论的几个项目正在积极提高其性能。
SNARK是如何部署的？
在SNARK部署中，开发人员通常编写一个计算机程序ψ，将证明人声称知道的数据w作为输入，并检查w是否有效。例如，在Rollup中，程序将检查w中的所有交易是否都经过数字签名，是否导致任何帐户余额低于零等。然后通过SNARK前端输入程序ψ，该前端将程序编译成更适合SNARK技术应用的格式。这种SNARK友好格式称为中间代码。
通常，IR是某种等效于ψ的电路可满足性实例。这意味着电路C以数据w作为输入，以及一些通常被称为“非确定性建议”的额外输入，并在w上运行ψ。这些建议输入用于帮助C运行ψ，同时保持C较小。例如，每当ψ除以两个数x和y时，商数q和余数r就可以作为建议提供给C,C可以简单地检查x=qy+r。这种检查比让C运行除法算法从头计算q和r更便宜。
最后，将可满足性电路SNARK应用于C。这称为SNARK后端。对于一些高度结构化的问题，如矩阵乘法、卷积和一些图问题，已知的SNARK可以避免这种前端/后端范式，从而实现更快的证明。但本文的重点是通用的SNARK。
正如我们将看到的，SNARK后端验证成本随着C的规模而增长。保持C尽可能小是一项挑战，因为电路是一种极为有限的计算格式。它们由门组成，由电线连接。给每个门g输入一些值，并对这些值应用一个非常简单的函数。然后，通过g发出的导线将结果送入“下游”门。
SNARK的可扩展性需要多长时间？
关键问题是，相对于简单地对数据重新执行ψ，SNARK证明器需要多长时间？答案是SNARK的验证程序，是相对于直接的验证者核查。后一个表达式指的是在P将w发送给V的原始证明中，V通过对w执行ψ来检查w的有效性。
将证明器开销分为“前端开销”和“后端开销”是有利的。如果逐门计算电路C的成本是运行ψ的F倍，那么我们称前端开销为F。如果将后端验证程序应用于C的成本是逐门评估C的B倍，那么我们称后端开销为B。总验证程序开销是F乘以B。即使F和B各自都不大，这个乘法开销也可能很大。
实际上，F和B都可以是1000或更大。这意味着相对于直接验证者核查，证明程序的总开销可能是100万到1000万或更多。在笔记本电脑上运行一秒钟的程序很容易导致SNARK验证程序需要数十天或数百天的计算时间。幸运的是，这项工作通常在不同程度上是并行的。
总之，如果你想在今天的应用程序中使用SNARK，必须满足以下三个条件中的一个：
1.在笔记本电脑上直接核查验证者只需要不到一秒钟的时间。
2.直接验证者核查特别适合在电路中进行，因此前端的开销很小。
3.你愿意等待数天等待SNARK验证程序完成，并/或支付巨大的并行计算资源。
本文的其余部分解释了前端和后端开销从何而来，以及我如何对不同的SNARK进行估算。以及未来改善的前景。
区分前端和后端
因为不同的后端支持不同类型的电路，所以完全区分前端和后端是一个挑战。因此，前端可以根据它们期望与之交互的后端而有所不同。
SNARK后端通常支持所谓的算术电路，这意味着电路的输入是某个有限域的元素，电路的门执行两个域元素的加法和乘法。这些电路大致相当于直线计算机程序，这些程序在本质上是代数的，也就是说，它们的原始数据类型是字段元素。
大多数后端实际上支持大部分算术电路，通常称为Rank-1约束满足实例。除了Groth16和它的前身，这些SNARK也可以用来支持其他的IR。例如，StarkWare使用了一种叫做代数中间表示的方法，这与PlonK和其他后端支持的PlonKish算术运算类似。一些后端支持更通用的IR的能力可以减少产生这些IR的前端的开销。
后端也因其本机支持的有限字段而有所不同。我将在下一节进一步讨论这个问题。
前端的多种方法
一些计算机程序自然对应于算术电路。一个例子是在某个域上执行矩阵简单乘法的计算机程序。但大多数计算机程序既不是直线也不是代数。它们通常涉及条件语句、整数除法或浮点运算等与有限域运算不自然对应的运算等。在这些情况下，前端开销将相当大。
一种热门的前端方法是生成基本的电路，逐步执行一些简单的CPU，也称为虚拟机。前端设计人员指定一组基本操作，类似于实际计算机处理器的汇编指令。想要使用前端的开发人员要么直接用汇编语言编写“验证者检查程序”，要么用诸如Solidity这样的高级语言编写“验证者检查程序”，然后让他们的程序自动编译成汇编代码。
例如，StarkWare的Cairo是一种非常有限的汇编语言，其中的汇编指令大致允许在有限域上进行加法和乘法运算、函数调用以及对不可变内存的读写。CairoVM是一种冯·诺伊曼架构，这意味着前端产生的电路本质上将Cairo程序作为公共输入，并在见证器面前运行该程序。Cairo语言是图灵完备的——尽管它的指令集有限，但它可以模拟更多的标准架构，尽管这样做可能会很昂贵。Cairo前端将执行T个原语指令的Cairo程序转换为所谓的“2级AIR,T行，大约50列”。这到底意味着什么并不重要，但就SNARK证明而言，这相当于Cairo?CPU的每个T步骤都有50到100个门的电路。
RISCZero采用了与Cairo类似的方法，但它的虚拟机是所谓的RISC-V架构，这是一种开源架构，具有丰富的软件生态系统，越来越受欢迎。作为一个非常简单的指令集，设计一个高效的支持它的SNARK前端可能是相对容易处理的。截至5月，RISCZero正在将执行原始RISC-V指令的程序转换为具有3排和160列的5级AIR。这对应于每步RISC-VCPU至少有500个门的电路。预计在不久的将来会有进一步的改进。
各种zkEVM项目将虚拟机作为以太坊虚拟机。将每条EVM指令转换为等效的“小工具”的过程要比简单的Cairo和RISC-V架构复杂得多。由于各种原因，一些zkEVM项目并没有直接实现EVM指令集，而是在将高级Solidity程序转化为电路之前将其编译成其他汇编语言。这些项目的性能结果尚未确定。
如RISC-V和Cairo的“CPU模拟器”项目，产生的单个电路可以处理相关汇编语言中的所有程序。另一种方法是类似ASIC芯片的，为不同的程序产生不同的电路。这种类似ASIC的方法可以为一些程序产生更小的电路，特别是当程序在每个时间步执行的汇编指令不依赖于程序的输入时。例如，它可以潜在地完全避免直线程序的前端开销。但ASIC的方法似乎也非常有限/据我所知，还不知道如何使用它来支持没有预先确定迭代边界的循环。
前端开销的最后一个组成部分来自于所有SNARK都使用在有限域上运行的电路。你的笔记本电脑上的CPU可以用一条机器指令将两个整数相乘或相加。如果前端输出电路的场特性足够大，它本质上可以通过相应的场操作来模拟乘法或加法。但是，在真正的CPU上实现字段操作通常需要许多机器指令。
一些SNARK后端支持比其他更灵活的字段选择。例如，如果后端使用加密组G，则电路的字段必须与G中的元素数量匹配，这可能是有限的。此外，并非所有领域都支持实用的FFT算法。
只有一个实现的SNARK——Brakedown，在本地支持任意字段的计算。除了它的下一代，它在其他SNARK支持的字段上具有最快的已知具体验证性能，但目前它的证明对于许多区块链应用来说太大了。最近的工作试图改进证明的大小，但证明器的速度较慢，并且在实用性方面似乎存在障碍。
有些项目选择在运算速度特别快的领域工作。例如，Plonky2和其他算法使用264-232+1的特征域，因为该域的算法实现速度比非结构化域快好几倍。然而，使用如此小的特征可能会导致通过字段操作有效地表示整数算术的挑战。
但是无论如何，对于今天所有热门的SNARK来说，要实现128位的安全性，它们必须在大于2128的域上工作。据我所知，这意味着每个字段操作将需要至少10次64位机器乘法，以及相当多的加法和位运算。因此，由于需要在有限域上运行的电路，应该考虑至少一个数量级的前端开销。
总而言之，使用虚拟机抽象的现有前端在虚拟机的每个步骤中产生100到1000个门的电路，对于更复杂的虚拟机可能会产生更多。最重要的是，有限字段算法比现代处理器上的类似指令至少慢10倍。一种“ASIC芯片前端方法”可能会减少其中一些开销，但目前仅限于它能支持的程序类型。
后端瓶颈是什么？
可满足性电路的SNARK通常是通过结合一个称为“多项式IOP”的信息理论上安全协议和一个称为“多项式承诺方案”的密码协议来设计的。在大多数情况下，证明器的具体瓶颈是多项式承诺方案。特别是这些SNARK使证明器以加密方式提交一个或多个多项式，其次数为|C|，即电路C中的门数。
相应地，多项式承诺方案中的具体瓶颈将取决于所使用的方案和电路大小。但总是以下三种操作中的一种：计算FFT、加密组中的幂运算或Merkle哈希。Merkle哈希通常只有在电路很小的情况下才是瓶颈，因此我们将不再进一步讨论它。
基于离散对数的多项式承诺
在基于密码组G中离散对数问题的硬度的多项式承诺中，证明者必须计算多项式系数的Pedersen向量承诺。这涉及到多重幂运算，其大小等于多项式的次数。在SNARK中，这种程度通常是电路C的大小|C|。
简单地说，对大小|C|进行多次幂运算需要大约1.5·124≈400·|C|群运算，其中124G|-表示群G中的元素数。然而，有一种称为Pippenger算法的方法，可以将其减少大约log|C|。对于大型电路，该对数|C|因子可以具体为25或更大，也就是说，对于大型电路，我们预计Pedersen向量组合可以通过略多于10·124C124的群运算来计算。反过来，每组操作往往比有限场操作慢10倍左右。使用这些多项式承诺的SNARK对于P来说与大约100·|C|现场操作一样昂贵。
但是现有的SNARK除了100倍的倍数之外还有额外的开销。例如：
Spartan的证明使用Hyrax多项式承诺，必须做|C|?多次幂，每个大小为|C|?，削弱了Pippenger的算法的加速约为2倍。
在Groth16中，P必须在对结对友好的组上工作，其操作通常比不对结对友好的组慢至少两倍。P也必须执行3次多次幂而不是1次。综合起来，这导致了相对于上面估计的100·|C|的至少额外6倍的减速。
Marlin和PlonK也要求配对，他们的证明者承诺的多项式远多于3个。
对于任何使用了子弹证明的SNARK，证明者必须在承诺方案的“开始”阶段计算对数级的多次幂，这在很大程度上消除了任何Pippenger加速。
总之，已知的SNARK使用Pedersen矢量承诺的后端开销至少为200倍，最高可达1000倍或更多。
其他多项式的承诺
对于使用其他多项式承诺的SNARK，瓶颈处在于证明程序需要执行大型FFT。例如，在Cairo生产的2级AIR中，StarkWare部署的验证程序每列至少执行2个FFT，长度在16·T到32·T之间。常量16和32依赖于StarkWare设置的FRI内部参数，可以减少，但以增加验证成本为代价。
乐观地说，一个长度为32的FFT大约需要64·T·log场乘法。这意味着即使T的值相对较小，每个列的字段操作数至少是64·25·T=1600·T。因此，后端开销似乎至少有数千。此外，大型FFT的瓶颈可能是内存带宽，而不是字段操作。
在某些上下文中，执行大型FFT的SNARK的后端开销可以通过一种称为证明聚合的技术来减轻。对于Rollup，这意味着P?将一大批交易分解为10个较小的批。对于每一个小批量i,P产生一个SNARK证明πi的批次有效性。但是P没有将这些证明发布到以太坊，因为这将导致gas成本增加近10倍。相反，再次应用了SNARK，这一次产生了π的证明，证明P知道π1，π10。也就是说，P声称知道的证人是π1，…，π10这十个证明，直接证人核查将SNARK验证程序应用到每一个证明上。这个简单的π证明被发布到以太坊。
在多项式承诺中，P时间和V花费之间存在很强的张力，内部参数充当一个旋钮，可以在两者之间进行权衡。由于π1，…，π10没有发布到以太坊，旋钮可以调整，所以这些证明是大的，生产它们的速度更快。只有在SNARK的最终应用中，才能将π1、π10聚合成单个证明π，才需要配置承诺方案来保证小证明。
StarkWare计划立即部署证据聚合。这也是Plonky2等项目的重点。
SNARK可扩展性的其他瓶颈是什么？
本文关注的是验证时间，但其他验证成本也可能是可扩展性的瓶颈。例如，对于许多SNARK后端，证明程序需要为C中的每个门存储多个字段元素，这种空间开销可能非常大。在笔记本电脑上运行一秒钟的程序ψ可以在现代处理器上执行10亿次原始操作。一般来说，C需要超过100个门来完成这样的操作。这意味着1000亿个门，这取决于SNARK，可能意味着P有几十或几百TB的空间。
另一个例子是许多热门的SNARK需要一个复杂的“可信设置仪式”来生成一个结构化的“证明密钥”，它必须由证明者存储。据我所知，最大的一次这样的仪式产生了一个能够支持电路的证明密钥，大约有228≈2.5亿个门。证明的关键是几十GB大小。
在证明聚合可能性较高的环境中，这些瓶颈可以适当突破。
展望未来：可扩展性更强的SNARK前景
前端和后端开销都可能是三个数量级或更多。我们能否期待在不久的将来这些数字会大幅下降？
在某种程度上，我认为我们会的。首先，今天最快的后端有很大的证明量——通常是电路大小的平方根，所以人们并没有真正使用它们。我预计在不久的将来，通过深度一合成和小的验证障碍，验证规模和验证时间将显著减少。与证明聚合类似，这意味着证明者将首先使用快速证明者，大证明者SNARK生成SNARK证明π，但不会将π发送给V。相反，P将使用一个小的证明SNARK产生一个证明π′，证明它知道π，并将π′发送给V。这可以在很大程度上减少目前流行的?SNARK?后端开销。
其次，硬件加速会有所帮助。一个非常简单的规则是GPU可以买到比CPU快10倍的速度，而ASIC可以买到比GPU快10倍的速度。然而，我有三个担忧。首先，大型FFT的瓶颈可能是内存带宽，而不是字段操作，所以执行此类FFT的SNARK在专用硬件上的加速可能有限。第二，虽然本文关注的是多项式承诺瓶颈，但许多SNARK要求证明者做其他的操作，这些操作的成本只比多项式承诺瓶颈低一点点。因此，打破多项式承诺瓶颈可能会留下一个新的瓶颈操作，它并不比旧的好多少。最后，导致最有效的SNARK的场和椭圆曲线可能会持续发展一段时间，这可能会给基于ASIC的验证加速带来挑战。
在前端，我们可能会越来越多地发现，Cairo、RISCZero、zkEVM等项目的“CPU模拟器”方法实际上可以很好地扩展CPU指令集的复杂性。事实上，这正是各种zkEVM项目的希望所在。这可能意味着，虽然前端开销仍然是三个数量级或更多，但前端可以支持越来越匹配真实CPU架构的虚拟机。与之相反的一个担忧是，随着手工编码的小工具实现越来越复杂的指令激增，前端可能会变得复杂，难以审核。正式的核查方法很可能在解决这一问题方面发挥重要作用。
最后，至少在区块链应用程序中，我们可能会发现大多数出现在非主流的智能合约主要使用简单的、SNARK友好的指令。这在实践中可能会降低前端开销，同时保留支持Solidity等高级编程语言和包括EVM在内的丰富指令集所带来的通用性和改进的开发人员体验。
来源：金色财经
郑重声明： 本文版权归原作者所有， 转载文章仅为传播更多信息之目的， 如作者信息标记有误， 请第一时间联系我们修改或删除， 多谢。