SNARK (Succinct Non-interactive Arguments of Knowledge) 是实现：
的重要密码学原语。
SNARK中有2个重要角色：
同时本文将SNARK Prover 工作分为前后端：
关于SNARK的更多知识，可参看：
SNARKs的verification cost根据具体的实现方案，会各有不同，但是普遍认为其verification cost不错。如：
SNARK可用于除区块链之外的其它领域，如：
由于SNARK的验证开销较低，影响SNARK可用性的决定性因素在于SNARK prover P的开销。
SNARK部署通常为：
如在rollups中，该program为检查 w w w中的所有交易都已有效签名且account balance不会为负值等等。然后program ψ \psi ψ作为某SNARK frontend的输入被编译为某种有利于SNARK技术应用的格式。这种SNARK友好的格式称为intermediate representation（IR）。
通常，IR为某种与 ψ \psi ψ等价的circuit-satisfiability实例。即有某circuit C C C，其输入为数据 w w w 以及 一些称为“non-deterministic advice”的额外输入，然后基于 w w w运行 ψ \psi ψ。advice输入帮助 C C C运行 ψ \psi ψ，同时keeping C C C small。如，每次 ψ \psi ψ计算 x / y x/y x/y，将商 q q q和余数 r r r作为advice提供给 C C C， C C C仅需要简单的检查 x = q y + r x=qy+r x=qy+r即可。相对于重新做除法运算，该检查的开销要没那么贵。
最后，对 C C C应用circuit-satisfiability SNARK，这称为SNARK backend。对于一些高度结构化的问题，如：
已知的SNARK可以避免这种frontend/backend范式，从而实现更快的Prover。但这篇文章的重点是通用SNARK。
同时，将发现SNARK backend的Prover cost将随 C C C size增长。保持 C C C small是有调整的，因circuit是表示计算的特别有限的格式。circuit中包含了gates，这些gates通过wires连接。每个gate g g g基于 某些输入值 通过 某个很简单的函数运算 获得 某些输出值。 g g g这些输出值 又通过wires 作为后续gate的输入值。
关键在于，相比于基于data重新执行
ψ
\psi
ψ，SNARK prover的用时要多多少呢？
答案为：
所谓“direct witness checking开销”是指：P将 w w w发送给V，V通过执行 ψ \psi ψ来检查 w w w的有效性。
可将"SNARK prover开销"分解为：
总的"SNARK prover开销"为 F ⋅ B F\cdot B F⋅B，即使 F , B F,B F,B各自为适度的，但乘积之后的开销也可能是相当大的。
事实上， F , B F,B F,B都可能约为1000或更大，这意味着总的prover开销 相对于 “direct witness checking” 将是百万级甚至千万级的。笔记本电脑上运行仅需1秒的程序，SNARK prover在笔记本电脑上使用单线程的情况下将需要数十或数百天。幸运的是，SNARK prover的工作看具体的方案，通常可不同程度的并行化。
总之，若想在当今应用中使用SNARK，需要以下三者之一成立：
本文接下来将解释前端和后端开销的来源，以及不同SNARK方案相应的开销评估。然后将讨论改进的前景。
完全将前后端分离是有调整的，因不同的后端支持不同类型的circuits，因此，前端会根据其交互的后端而不同。
SNARK后端支持所谓的arithmetic circuit，即该circuit的输入为某有限域的元素，且circuit的gate会对2个域元素进行加法和乘法运算。大致对应于本质上是代数的直线计算机程序（无分支、条件语句等），也就是说，它们的原始数据类型是域元素。
大多数SNARK后端都支持名为Rank-1 Constraint Satisfaction (R1CS)的通用arithmetic circuit。除了Groth16及其前身之外，这些SNARK也可用于支持其他IRs。如StarkWare使用名为“Algebraic Intermediate Representation (AIR)”，一种类似于PlonK和其它后端所支持从名为PlonKish arithmetization。某些后端支持更通用的IR可减少生成这些IR所需的前段开销。
根据所支持的有限域，后端也会有所不同。
某些非常特别的计算机程序天然对应arithmetic circuit，如某程序对某域进行直接的矩阵乘法运算。但大多数计算机诚实既不是straight-line的，也不是algebraic的，它们通常包含了条件声明、整数除法运算、浮点数运算这些并不天然对应有限域的运算 等等。此时，前端开销将是大量的。
一种流行的前端方法是，按单一CPU逐步执行的方式来生成电路，也称为virtual machine（VM）。前端设计者会定义一组类似于真实计算机处理器的汇编指令的“基本操作”（“primitive operations”）。想要使用前端的开发人员要么直接用汇编语言编写“witness-checking programs”，要么用Solidity等高级语言编写，然后让他们的程序自动编译成汇编代码。
如：
1）StarkWare的Cairo是一种功能非常有限的汇编语言，其汇编指令仅支持基于有限域的加法和乘法、函数调用、对某immutable（即write-once）memory的读写。
Cairo VM为von Neumann架构，即意味着前端生成的circuit，以某Cairo program为public input，并基于witness “运行”该程序。Cairo语言为图灵完备的——除了其指令集有限，Cairo可模拟更标准的架构，尽管可能更昂贵。
Cairo前端将 执行
T
T
T个primitive指令的Cairo程序 转换为 名为“degree-2 AIR with
T
T
T rows and about 50 columns”。其具体含义见：ethSTARK Documentation – Version 1.1。但是只要考虑SNARK prover足够快，每个Cairo CPU的
T
T
T steps对应电路中的50到100个gates。
2）RISC Zero的方案与Cairo类似，但其virtual machine为RISC-V架构。RISC-V架构为一种开源架构，具有丰富的软件生态并广受欢迎。由于其指令集非常简单，设计高效的SNARK前端 相对易处理（至少相对于复杂的架构，如x86或ARM）。截止2022年5月，RISC Zero是 图灵程序——ZK7: RISC Zero: Encoding Von-Neumann Architectures in Zero-Knowledge Proof Systems - Risc0的，可将 T T T primitive RISC-V指令 执行转换为 “degree-5 AIRs with 3T rows and 160 columns”。对于RISC-V CPU的每个step，对应的circuit中至少有500 gates。未来将对其进行改进。
不同的zkEVM项目（如zkSync 2.0，Scroll，Polygon的zkEVM）将虚拟机视为以太坊虚拟机。将每个EVM指令 转换为 等价“gadget” （即针对该指令的某优化电路）的过程，相比于简单的Cairo和RISC-V架构，这种转换的开销将更大。为此，某些zkEVM项目（见Vitalik The different types of ZK-EVMs），并不直接实现EVM指令集，而是将高层Solidity程序 变意思为其它 汇编语言，然后将汇编语言转换为电路。这些项目的性能效果尚待确定。
RISC-V和Cairo这样的“CPU仿真器”，可生成单一电路 来 处理 相关汇编语言中的所有程序。
备选方案有“RISC-like”方法：为不同的程序 生成 不同的电路。这样可为某程序生成更小的电路，特别是当程序在每个timestep的汇编指令不依赖程序输入时。如，对于naive矩阵乘法这类straight-line程序，可能可完全避免前端开销。
但是ASIC方法仍然有局限，迄今为止，其无法支持具有固定上限的循环计算。
前端开销的最后一部分来自于，所有的SNARK都是用基于有限域的circuit运算。笔记本上的CPU可通过单一机器指令来对2个整数求和或求积。若前端输出的circuit基于的域具有足够大的characteristic，则可通过相应的域运算来模仿加法或乘法运算。但是，基于real CPU来做域运算通常需要很多机器指令（尽管当今有某些处理器原生支持特定域）。
某些SNARK后端所采用的域选择很灵活。如，若后端使用密码学群 G G G，则其circuit的域必须与 G G G群中的元素数量相匹配，这就是限制。此外，并不是所有的域都支持实用FFT算法。
当前的情况为：
某些项目会选择某些可快速运算的域，如Plonky2等项目使用了characteristic为 2 64 − 2 32 + 1 2^{64}-2^{32}+1 264−232+1的域（即 Goldilocks域），因该域内的计算可比其他less structured域快数倍。但是，使用如此小的characteristic可能会为通过域操作高效表达整数运算带来风险。（如，32-bit无符号整数 与 任意大于 2 32 2^{32} 232 的整数相乘时，结果将大于该field characteristic。因此，选择该域意味着仅支持32-bit number运算。）
但不管怎样，对于当今所有流行的SNARK来说，要实现128位的安全性（在不显著增加验证成本的情况下），它们必须在大于 2 128 2^{128} 2128的域上工作。据我所知，这意味着每个域操作将需要至少10个64位机器乘法，以及相当多的加法和按位操作。因此，对于需要在有限域上工作的电路，应考虑至少一个数量级的前端开销。
总而言之，使用虚拟机抽象的现有前端在虚拟机的每一步生成100x到1000x个gates的电路，对于更复杂的虚拟机可能更多。除此之外，有限域运算至少比现代处理器上的类似指令慢10倍（如果处理器内置了对某些域的支持，则可能会有例外）。“ASIC前端方法”可能会减少一些开销，但目前其支持的程序种类有限。
SNARKs for circuit-satisfiability通常设计为：
的结合。大多数情况下，Prover的具体瓶颈在polynomial commitment scheme。特别的，这些SNARK的prover会对某个或某些degree（最多）为 ∣ C ∣ |C| ∣C∣的多项式进行密码学承诺，其中 ∣ C ∣ |C| ∣C∣表示circuit C C C中的gate数。
继而，polynomial commitment scheme中的具体拼接在于：
但是polynomial commitment scheme中通常有如下3种操作之一：
基于某密码学群 G G G内的discrete logarithm problem难度的多项式承诺方案有：
Prover需要对多项式的系数计算Pedersen vector commitment。这包含了size等于多项式degree的multi-exponentiation运算。在SNARK中，多项式degree通常为circuit C C C的size ∣ C ∣ |C| ∣C∣。
直接计算的话，size为 ∣ C ∣ |C| ∣C∣的multi-exponentiation需要约 1.5 ⋅ ∣ C ∣ ⋅ log ∣ G ∣ ≈ 400 ⋅ ∣ C ∣ 1.5\cdot |C|\cdot \log |G|\approx 400\cdot |C| 1.5⋅∣C∣⋅log∣G∣≈400⋅∣C∣次群运算，其中 ∣ G ∣ |G| ∣G∣表示群 G G G内的元素数。但是，Pippenger算法可将其reduce大约 log ∣ C ∣ \log |C| log∣C∣因子。对于大电路（也就是说， ∣ C ∣ ≥ 2 25 |C|\geq 2^{25} ∣C∣≥225）， log ∣ C ∣ \log |C| log∣C∣因子具体为25或更多，即，对于搭电路，Pedersen vector commitment计算需约略多于 10 ⋅ ∣ C ∣ 10\cdot |C| 10⋅∣C∣次群操作。单个群操作要比单个慢约10x倍。采用这种多项式承诺机制的SNARK prover，需要约 100 ⋅ ∣ C ∣ 100\cdot |C| 100⋅∣C∣次域操作（昂贵的）。
除了以上100x倍因子的放大之外，现有的SNARK还有额外的开销，如：
总之，现有使用Pedersen vector commitment的SNARK后端开销至少要200x倍甚至多于1000x倍。
使用其它多项式承诺机制（如FRI 和 Ligero-commit：2017年论文 Ligero: Lightweight Sublinear Arguments Without a Trusted Setup）的SNARK，其prover瓶颈在于需要做large FFT计算。StarkWare部署的prover每列至少需要做2次FFT计算，每列的长度在 16 ⋅ T 16\cdot T 16⋅T至 32 ⋅ T 32\cdot T 32⋅T之间。其中常量 16 16 16和 32 32 32取决于StarkWare设置的FRI内部参数，可减少该常量值，但将增加验证开销。
乐观地是，长度 32 ⋅ T 32\cdot T 32⋅T的FFT约需 64 ⋅ T ⋅ log ( 32 T ) 64\cdot T\cdot \log(32T) 64⋅T⋅log(32T)次field multiplication。这意味着即使选择相对小的 T T T（如， T ≥ 2 20 T\geq 2^{20} T≥220），每列所需的field操作次数最少为 64 ⋅ 25 ⋅ T = 1600 ⋅ T 64\cdot 25\cdot T=1600\cdot T 64⋅25⋅T=1600⋅T，因此后端开销至少为千倍级。此外，large FFT更大的瓶颈可能来自于内存带宽而不是域操作。
在某些上下文，执行large FFT的SNARK的后端开销，可借助proof aggregation技术进行缓解。如，对于rollups，这意味着P（rollup service）将a big batch of transactions 切分为10个更小的batches。对于每个small batch i i i，P会为该batch的有效性生成SNARK证明 π i \pi_i πi。但P并不将这些证明提交到以太坊，因为这意味着近10倍的gas开销。相反，会再次应用SNARK，为“P knows π 1 , ⋯ , π 10 \pi_1,\cdots,\pi_{10} π1,⋯,π10”生成证明 π \pi π。P声称知道的witness为该10个证明 π 1 , ⋯ , π 10 \pi_1,\cdots,\pi_{10} π1,⋯,π10，且direct witness checking为 对每个证明应用SNARK验证流程。然后将证明 π \pi π提交到以太坊。
在类似FRI和Ligero-commit的多项式承诺机制中，P time 和 V cost 之间存在强烈的紧张关系，内部参数充当一个旋钮，可以相互权衡。由于 π 1 , ⋯ , π 10 \pi_1,\cdots,\pi_{10} π1,⋯,π10不提交到以太坊，因此可将旋钮调整，使得生成证明更快，证明更大。仅在最后一次应用SNARK aggregate π 1 , ⋯ , π 10 \pi_1,\cdots,\pi_{10} π1,⋯,π10为单一证明 π \pi π，使得其为small proof。
StarkWare计划近期部署proof aggregation，参见"Recursive STARKs with Cairo" (Avihu Levy & Shahar Papini)。
而Plonky2也关注proof aggregation。
本文主要关注prover time，但其它prover开销也可能是扩容瓶颈。如，很多SNARK后端的prover需为circuit C C C中的每个gate存储多个field elements，这样的space cost也很大。如，在笔记本上运行为1秒的程序 ψ \psi ψ，在中等处理器上可能需要执行10亿次primitive操作。正如我们所看到的，一般来说，我们应该期望 C C C在每次操作中需要超过100个gates。这意味着1000亿个gate，具体取决于SNARK，可能意味着P需数十或数百TB的空间。
另一个例子，很多流行SNARKs（如PlonK，Marlin，Groth16）需要复杂的“trusted setup ceremony”来生成结构化的“proving key”——必须由Prover存储。如：
这些大的ceremony生成的proving key支持的约 2 28 ≈ 250 2^{28}\approx 250 228≈250 million gates（2.5亿个gate）的circuit。相应的proving key size为几十GB。
若proof aggregation可行，这些瓶颈可大幅缓解。
前端和后端开销都可以是三个数量级或更多。我们能预期在不久的将来这些数字会大幅下降吗？
答案是肯定的：
[1] a16z团队2022年8月博客 Measuring SNARK performance: Frontends, backends, and the future
[2] a16z团队2022年9月博客 SNARK security and performance
[3] twitter SNARK security