本文来自 a16z，原文作者：Justin Thaler，由 Odaily 星球日报译者 Katie 辜编译。
SNARK（简练的非交互式常识参数）是一种重要的暗码原语，用于发现区块链可扩展性（例如 L2 Rollup）和隐私的运用。SNARK 答应或人向不可信验证器 V（例如以太坊区块链）证明他们知道一些数据（例如一批有用交易）。证明这一点的简略办法是将数据发送给 V，然后 V 能够直接查看其有用性。SNARK 完结了同样的作用，但对 V 来说本钱更高。特别是SNARK 证明应该比包括数据本身的原始证明更短。
SNARK 的验证本钱或许会有所不同，但效果一般都很好。例如，PlonK 的证明在以太坊上的验证本钱约为 29 万 gas，而 StarkWare 的证明本钱约为 500 万 gas。SNARK 或许适用于区块链之外的各种不同的设置，例如，答应运用快速但不可信的服务器和硬件。
但因为 SNARK 验证一般很便宜，适用性的首要决定因素是 SNARK 证明者 P 的本钱。本文中将解说怎么预算这些本钱，以确认何时合理运用 SNARK，以及未来怎么改善 SNARK。值得注意的是，这是一个快速发展的范畴，本文中讨论的几个项目正在积极进步其功能。
SNARK 是怎么布置的？
在 SNARK 布置中，开发人员一般编写一个核算机程序 ψ，将证明人声称知道的数据 w 作为输入（w 代表验证者），并查看 w 是否有用。例如，在 Rollup 中，程序将查看 w 中的一切交易是否都经过数字签名，是否导致任何帐户余额低于零等。然后经过 SNARK 前端输入程序 ψ，该前端将程序编译成更适合 SNARK 技能运用的格局。这种 SNARK 友爱格局称为中间代码（IR）。
一般，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）。
总归，假如你想在今日的运用程序中运用 SNARK，有必要满足以下三个条件中的一个：
1.在笔记本电脑上直接核对验证者只需求不到一秒钟的时刻。
2.直接验证者核对特别适合在电路中进行，因而前端的开支很小。
3.你乐意等候数天等候 SNARK 验证程序完结，并/或付出巨大的并行核算资源。
本文的其余部分解说了前端和后端开支从何而来，以及我怎么对不同的SNARK进行预算。以及未来改善的远景。
区分前端和后端
因为不同的后端支撑不同类型的电路，所以彻底区分前端和后端是一个应战。因而，前端能够根据它们期望与之交互的后端而有所不同。
SNARK 后端一般支撑所谓的算术电路，这意味着电路的输入是某个有限域的元素，电路的门履行两个域元素的加法和乘法。这些电路大致相当于直线核算机程序（没有分支、条件语句等），这些程序在本质上是代数的，也就是说，它们的原始数据类型是字段元素。
大多数后端实际上支撑大部分算术电路，一般称为 Rank-1 约束满足（R1CS）实例。除了 Groth16 和它的前身，这些 SNARK 也能够用来支撑其他的 IR。例如，StarkWare 运用了一种叫做代数中间表明（AIR）的办法，这与 PlonK 和其他后端支撑的 PlonKish 算术运算相似。一些后端支撑更通用的 IR 的能力能够削减发生这些 IR 的前端的开支。
后端也因其本机支撑的有限字段而有所不同。我将在下一节进一步讨论这个问题。
前端的多种办法
一些（十分特别的）核算机程序天然对应于算术电路。一个比如是在某个域上履行矩阵简略乘法的核算机程序。但大多数核算机程序既不是直线也不是代数。它们一般涉及条件语句、整数除法或浮点运算等与有限域运算不天然对应的运算等。在这些情况下，前端开支将相当大。
一种抢手的前端办法是生成根本的电路，逐渐履行一些简略的 CPU，也称为虚拟机（VM）。前端规划人员指定一组根本操作，相似于实际核算机处理器的汇编指令。想要运用前端的开发人员要么直接用汇编言语编写“验证者查看程序”，要么用比如 Solidity 这样的高档言语编写“验证者查看程序”，然后让他们的程序自动编译成汇编代码。
例如，StarkWare 的 Cairo 是一种十分有限的汇编言语，其间的汇编指令大致答应在有限域上进行加法和乘法运算、函数调用以及对不可变（即只写一次）内存的读写。Cairo VM 是一种冯·诺伊曼架构，这意味着前端发生的电路本质大将 Cairo 程序作为公共输入，并在见证器面前运转该程序。Cairo 言语是图灵齐备的——尽管它的指令集有限，但它能够模仿更多的标准架构，尽管这样做或许会很贵重。Cairo 前端将履行 T 个原语指令的 Cairo 程序转换为所谓的“2 级 AIR, T 行，大约 50 列”。这到底意味着什么并不重要，但就 SNARK 证明而言，这相当于 Cairo CPU 的每个 T 进程都有 50 到 100 个门的电路。
RISC Zero 采用了与 Cairo 相似的办法，但它的虚拟机是所谓的 RISC-V 架构，这是一种开源架构，具有丰富的软件生态系统，越来越受欢迎。作为一个十分简略的指令集，规划一个高效的支撑它的 SNARK 前端或许是相对简略处理的（至少相关于杂乱的体系结构，如 x86 或 ARM）。截至5月，RISC Zero 正在将履行原始 RISC-V 指令的程序转换为具有 3 排和 160 列的 5 级 AIR。这对应于每步 RISC-V CPU 至少有 500 个门的电路。估量在不久的将来会有进一步的改善。
各种 zkEVM 项目（例如，zkSync 2.0、Scroll、Polygo 的 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 的特征域，因为该域的算法完结速度比非结构化域快好几倍。可是，运用如此小的特征或许会导致经过字段操作有用地表明整数算术的应战。（例如，将一个32位无符号整数乘以任何大于 232 的数字或许会发生大于字段特征的成果。因而，字段挑选天然只支撑 32 位数字的算术。）
可是无论怎么，关于今日一切抢手的 SNARK 来说，要完结 128 位的安全性（不需求明显添加验证本钱），它们有必要在大于 2128 的域上作业。据我所知，这意味着每个字段操作将需求至少 10 次 64 位机器乘法，以及相当多的加法和位运算。因而，因为需求在有限域上运转的电路，应该考虑至少一个数量级的前端开支。
总而言之，运用虚拟机抽象的现有前端在虚拟机的每个进程中发生 100 到 1000 个门的电路，关于更杂乱的虚拟机或许会发生更多。最重要的是，有限字段算法比现代处理器上的相似指令至少慢 10 倍（假如处理器内置了对某些字段的支撑，也或许有例外）。一种“ ASIC 芯片前端办法”或许会削减其间一些开支，但现在仅限于它能支撑的程序类型。
后端瓶颈是什么？
可满足性电路的 SNARK 一般是经过结合一个称为“多项式 IOP ”的信息理论上安全协议和一个称为“多项式许诺方案”的暗码协议来规划的。在大多数情况下，证冥具的详细瓶颈是多项式许诺方案。特别是这些 SNARK 使证冥具以加密方式提交一个或多个多项式，其次数为（至少）|C|，即电路 C 中的门数。
相应地，多项式许诺方案中的详细瓶颈将取决于所运用的方案和电路巨细。但总是以下三种操作中的一种：核算 FFT、加密组中的幂运算或 Merkle 哈希。Merkle 哈希一般只要在电路很小的情况下才是瓶颈，因而咱们将不再进一步讨论它。
根据离散对数的多项式许诺
在根据暗码组 G（KZG、BulletProof、Dory 和 Hyrax commit）中离散对数问题的硬度的多项式许诺中，证明者有必要核算多项式系数的 Pedersen 向量许诺。这涉及到多重幂运算，其巨细等于多项式的次数。在 SNARK 中，这种程度一般是电路C的巨细|C|。
简略地说，对巨细|C|进行屡次幂运算需求大约 1.5·124≈400·|C|群运算，其间 124G|-表明群G中的元素数。可是，有一种称为 Pippenger 算法的办法，能够将其削减大约 log|C|。关于大型电路（例如|C|≥225），该对数|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（例如 Halo2，它大致是 PlonK，但运用了子弹证明而不是 KZG 多项式许诺），证明者有必要在许诺方案的“开始”阶段核算对数级的屡次幂，这在很大程度上消除了任何 Pippenger 加快。
总归，已知的 SNARK 运用 Pedersen 矢量许诺的后端开支至少为 200 倍，最高可达 1000 倍或更多。
其他多项式的许诺
关于运用其他多项式许诺（如 FRI 和 liigero -commit）的 SNARK，瓶颈处在于证明程序需求履行大型 FFT。例如，在Cairo 生产的 2 级 AIR（有 51 列和 T 行，Cairo CPU 每步有 1 行）中，StarkWare 布置的验证程序每列至少履行 2 个 FFT，长度在 16·T 到 32·T 之间。常量 16 和 32 依赖于 StarkWare 设置的 FRI 内部参数，能够削减，但以添加验证本钱为代价。
达观地说，一个长度为 32 的 FFT 大约需求 64·T·log（32T）场乘法。这意味着即便T的值相对较小（例如 T≥220），每个列的字段操作数至少是 64·25·T=1600·T。因而，后端开支似乎至少有数千。此外，大型 FFT 的瓶颈或许是内存带宽，而不是字段操作。
在某些上下文中，履行大型 FFT 的 SNARK 的后端开支能够经过一种称为证明聚合的技能来减轻。关于 Rollup，这意味着P （Rollup 服务）将一大批交易分解为 10 个较小的批。关于每一个小批量 i, P 发生一个 SNARK 证明 πi 的批次有用性。可是 P 没有将这些证明发布到以太坊，因为这将导致gas本钱添加近 10 倍。相反，再次运用了 SNARK，这一次发生了 π 的证明，证明 P 知道 π1，π10。也就是说，P 声称知道的证人是 π1，…，π10 这十个证明，直接证人核对将 SNARK 验证程序运用到每一个证明上。这个简略的 π 证明被发布到以太坊。
在多项式许诺（如 FRI 和 liigero -commit）中，P 时刻和 V 花费之间存在很强的张力，内部参数充任一个旋钮，能够在两者之间进行权衡。因为 π1，…，π10 没有发布到以太坊，旋钮能够调整，所以这些证明是大的，生产它们的速度更快。只要在 SNARK 的最终运用中，才能将 π1、π10 聚合成单个证明 π，才需求装备许诺方案来保证小证明。
StarkWare 方案立即布置证据聚合。这也是 Plonky2 等项目的重点。
SNARK 可扩展性的其他瓶颈是什么？
本文关注的是验证时刻，但其他验证本钱也或许是可扩展性的瓶颈。例如，关于许多 SNARK 后端，证明程序需求为 C 中的每个门存储多个字段元素，这种空间开支或许十分大。在笔记本电脑上运转一秒钟的程序 ψ 能够在现代处理器上履行10亿次原始操作。一般来说，C 需求超过 100 个门来完结这样的操作。这意味着 1000 亿个门，这取决于 SNARK，或许意味着 P 有几十或几百 TB 的空间。
另一个比如是许多抢手的 SNARK（例如，PlonK、Marlin、Groth16）需求一个杂乱的“可信设置仪式”来生成一个结构化的“证明密钥”，它有必要由证明者存储。据我所知，最大的一次这样的仪式发生了一个能够支撑电路的证明密钥，大约有228≈2.5 亿个门。证明的要害是几十 GB 巨细。
在证明聚合或许性较高的环境中，这些瓶颈能够适当突破。
展望未来：可扩展性更强的 SNARK 远景
前端和后端开支都或许是三个数量级或更多。咱们能否期待在不久的将来这些数字会大幅下降？
在某种程度上，我以为咱们会的。首要，今日最快的后端（例如 Spartanand Brakedown 以及其他结合了求和校验协议和多项式许诺的 SNARK）有很大的证明量——一般是电路巨细的平方根，所以人们并没有真实运用它们。我估量在不久的将来，经过深度一合成和小的验证妨碍，验证规模和验证时刻将显著削减。与证明聚合相似，这意味着证明者将首要运用快速证明者，大证明者 SNARK 生成 SNARK 证明 π，但不会将 π 发送给 V。相反，P 将运用一个小的证明 SNARK 发生一个证明 π′，证明它知道 π，并将 π′ 发送给 V。这能够在很大程度上削减现在流行的 SNARK 后端开支。
其次，硬件加快会有所协助。一个十分简略的规则是 GPU 能够买到比 CPU 快 10 倍的速度，而 ASIC 能够买到比 GPU 快 10 倍的速度。可是，我有三个忧虑。首要，大型 FFT 的瓶颈或许是内存带宽，而不是字段操作，所以履行此类 FFT 的SNARK 在专用硬件上的加快或许有限。第二，尽管本文关注的是多项式许诺瓶颈，但许多SNARK要求证明者做其他的操作，这些操作的本钱只比多项式许诺瓶颈低一点点。因而，打破多项式许诺瓶颈（例如，在根据离散日志的 SNARK 中加快屡次幂）或许会留下一个新的瓶颈操作，它并不比旧的好多少。（例如，SNARK 包括 Groth16、Marlin 和 PlonK，除了屡次幂之外，也有 FFT 的验证程序。）最后，导致最有用的 SNARK 的场和椭圆曲线或许会持续发展一段时刻，这或许会给根据 ASIC 的验证加快带来应战。
在前端，咱们或许会越来越多地发现，Cairo、RISC Zero、zkEVM 等项目的“CPU 模仿器”办法实际上能够很好地扩展（就功能而言）CPU 指令集的杂乱性。事实上，这正是各种 zkEVM 项目的期望所在。这或许意味着，尽管前端开支仍然是三个数量级或更多，但前端能够支撑越来越匹配真实 CPU 架构的虚拟机。与之相反的一个忧虑是，跟着手工编码的小工具完结越来越杂乱的指令激增，前端或许会变得杂乱，难以审核。正式的核对办法很或许在解决这一问题方面发挥重要作用。
最后，至少在区块链运用程序中，咱们或许会发现大多数出现在非主流的智能合约首要运用简略的、SNARK 友爱的指令。这在实践中或许会降低前端开支，同时保存支撑 Solidity 等高档编程言语和包括 EVM 在内的丰富指令集所带来的通用性和改善的开发人员体验。
