SNARK Design：Part I

SNARK最重要的特性就是其简洁性（Succinct），一般而言，简洁性有两个要求

• 证明应当比witness短：也即$|\pi|<|w|$
• Verifier验证$\pi$的开销要比验证$w$的开销少

标准的SNARK设计模式一般分为三步

1. 将一个计算问题用高级程序设计语言表达：比如计算某一消息的Hash，或者加解密算法之类的，可以用C/CPP，JAVA，Python等语言将这类计算问题描述出来
2. 将上述程序转换为等价的概率可检查模型：比如将其转化为电路可满足问题，或者转化为R1CS约束系统，这一步也成为SNARK的前端
3. 利用证明系统对上述概率可检查模型进行证明：这一步也称为SNARK的后端，目前常用的证明系统为多项式IOP，以前的方案如Groth16也有采用线性PCP的证明系统

由于SNARK的前端相对较为固定，因此对SNARK的研究主要集中在对后端的研究，具体可细分为后端的计算效率，证明大小，通信量，安全性等多个方向

由于SNARK的简洁性最为重要，因此后端有几个主要的目标

• Prover的效率要尽可能地达到线性时间：亚线性最好
• 证明大小尽可能地小：尽可能少的证明元素
• Verifier验证的开销尽可能的少，计算效率尽可能地快

此外SNARK后端通常还有几个额外的要求

• 透明性：无需可信设置
• 后量子安全性

现阶段SNARK方案的后端设计主要遵循下列范式：将多项式IOP和R1CS相结合，用多项式承诺方案实现其简洁性，用FS变换实现其非交互性

多项式IOP

总体而言，在IOP中，Prvoer在每轮交互中生成一个证明$\pi$，Verifier以随机预言的方式访问这个证明，且Verifier可以在任意时刻访问之前已收到的$\pi$

多项式IOP中，Prover的消息为一个多项式$h$，Verifier不知道该多项式的信息，但是Verifier可以要求Prover计算多项式在某个点$x$上的值$h(x)$，之后Verifier通过一些计算来验证Prover是否真的知道该多项式

多项式承诺

为了确保Prover发送的消息确实是与多项式$h$相关，需要某种方式将Prover与多项式相关联，这个方式就是多项式承诺方案

在多项式承诺方案中，Prover利用多项式承诺将其与多项式$h$绑定，得到承诺值$Com(h)$，后续Verifier请求计算$h(x)$时，Prvoer会发送多项式在该点的计算结果及其相关信息，Verifier通过少量计算即可验证Prover之前的消息是否与该多项式相关

这里可以看之前KZG多项式承诺那一篇博客

多项式承诺是SNARK中非常关键的一部分，不同的多项式承诺方案可以实现不同的性质，但是也有不同的代价，具体如下表所示

未知阶群的方案在采用class group时的Prover效率会很慢

SNARK方案

目前SNARK方案有三种主流的设计方式，不同的方案证明大小，Prover开销和Verifier开销之间有着不同的权衡

• 基于交互式证明（IPs）：经典方案包括Hyrax，vSQL，Libra，Virgo
• 基于多Prover的交互式证明（MIPs）：包括Spartan，Brakedown，Xiphos等等
• 基于常数轮多项式IOP：代表方案有Marlin，Plonk等

区别于前两种方案，在基于多项式的IOP协议中，Prover需要进行FFT运算，很可能会是效率瓶颈

将上述三种设计方式与多项式承诺相结合，可以得到现在常见的几种SNARK方案

• 基于线性PCP：以Groth16为代表的，优点在于其证明大小是所有方案中最小的（Groth16只需要3个群元素即可完成证明），Verifier的验证效率也非常高（Groth16只需要3次配对）
  但是此类方案的缺点也比较明显：最大的劣势在于其不具备通用性，在对不同的电路进行证明时都需要重新执行可信设置来生成相关参数，此外方案对Prover的空间开销较大，不满足后量子安全，不满足透明性
• 基于常数轮多项式IOP和KZG多项式承诺：以Marlin、Plonk为代笔，最大的优点在于其可信设置为通用的，只需要执行一次就可以完成多个不同电路的证明，而且此类方案具有较为灵活的中间表示法，在构造约束系统时比电路可满足性和R1CS更为灵活
  缺点在于证明大小会比较大（Groth16的4~6倍），Prover计算效率也会比较慢，也不满足透明性和后量子安全
• 基于MIP/IP和快速Prover多项式承诺：代表方案为Spartan、Brakedown、Xiphos、Hyrax，优点在于此类方案构造的Prover效率是目前已知所有方案中最快的，后量子安全性和透明性取决于采用的承诺方案
  缺点在于证明大小比上述两个都要大
• 基于多项式IOP和FRI多项式承诺：以Aurora、Virgo、Ligero++为例，优点在于其在满足后量子安全的前提下可以做到最短的证明大小
  缺点在于Prover效率很低，证明大小也很大

优化

不难看出，上述方案中大部分都存在证明大小较大的问题，尽管Groth16论文中给出了证明大小的下届为两个群元素（第一和第二源群各一个），但是目前而言并不知道这一下届是否可达，即便是下届可达，此类方式构造的SNARK也不具备通用性，对于证明不同电路时需要重复执行可信设置步骤，从而引入了大量不必要的开销

因此目前学术界在研究如何通过其他方式进一步减小证明大小，其中一个思路是将具有长证明的高效Prover方案与具有短证明的方案结合使用，此时Prover不需要将长证明发送给Verifier，而是通过再构造一个短证明，证明其知道证明，也即对证明的证明，也称为递归证明

这一思路的目的是既利用前者的高效Prover来生成证明，又利用后者来确保得到的证明长度不会太大，由于证明长度短，Verifier的开销也不会很大

但是这一思路得到的最终证明大小和Verifier效率基本取决于后者所采用的方案，此外为了确保效率和正确性，不仅要求前者生成的证明可以快速验证，还要求前者方案中的Verifier可以以电路的形式表示，以用于后者的SNARK

以太坊Rollup

现阶段对SNARK的研究主要是想将其用于各种区块链项目，通过SNARK来完成链上的各种验证工作

区块链的技术一个很重要的特性在于其应当可以被算力较弱的节点验证，因为根据区块链的特点，用户有理由不相信一个不由他验证的区块，此外，如果大部分以太坊的节点均运行在亚马逊的AWS服务器上，那么某种程度上而言亚马逊有权控制或销毁整个以太坊网络，因此区块链节点应当可以在手机或者笔电上进行验证

以太坊上运行一个验证节点主要有两方面的开销

• 验证交易的合法性：比如验证转账过程中金额的正确性和签名的正确性，或者用于验证运行在EVM上智能合约
• 下载、保存、访问所有链上数据：这些数据称为“世界状态”（the state of the world），可以将其视为所有用户的以太坊钱包

Rollup的目的是为了解决上述区块链中存在的问题，目前主要有两个解决思路

第一种方式是将区块链视为一个算力很弱的Verifier，并将Rollup视为一个不可信的Prover

此类方法中，节点无需直接验证签名，只需要验证链上的某个证明即可，若验证通过，则代表链上交易的签名均有效，从而有效地节约链上节点的计算开销

但是这一方法也有一个弊端：不能有效的减少或压缩链上的数据，也即无法解决上述的第二个开销

这里将链称为第一层（Layer 1，L1），将Rollup称为第二层（Layer 2，L2）

第二种方式是在链上保存状态的承诺，而非直接保存状态（比如在链上保存Merkle Tree的树根），利用承诺的绑定性来确保节点无法对已承诺的数据进行修改（无法在确保承诺值不变的情况下修改被承诺的数据）

利用这一方法，还可以做到不再需要共识机制来确保数据篡改行为

此外区块链上还需要确保数据可用性，也即需要确保在Rollup服务提供者跑路的情况下，其他用户仍然可以访问脸上数据，有两种方式确保数据可用性

• 在链上保存所有的数据：将其保存于CALLDATA中（一种开销更少的存储），且仅有全节点保存，但是此类方式会限制rollup的优势
• 引入激励模式，通过激励链下实体来保存数据并确保其可用

对于数据可用性，有一些额外的问题：是否允许除了rollup服务以外的其他实体来生成证明并更新系统状态，若不允许，则会导致中心化和审查之类的问题

若允许，如何避免针对数据可用性的攻击，比如生成了证明，但不公布交易的具体信息，或发布错误的信息，此时更新链上的承诺值，但是无人知道承诺值对应的数据，此时由于Prover不知道交易数据，因此无法完成对承诺值的更新，若需要更新承诺值，则至少需要知道Merkle Tree中除了根承诺以外的多个Hash值

针对数据可用性的攻击目前主要有两类解决方案

• 链上存储：Verifier需要将所有状态改变视为CALLDATA，这里可以借助$[SL20]$这篇paper中提出的Hash trick来降低开销
• 链下存储：保存于某些基于拜占庭容错的系统（BFT System）中，BFT可以对状态改变的Hash结果进行门限签名，从而证明其存储了该状态改变，此时Verifier在将状态更新至L1前获取对应的门限签名

因此，将上述两者结合在一起，就得到了rollup，如下：

L1总是保存世界状态的承诺值，每当rollup处理一批交易并得到新的世界状态后，将新的状态承诺并保存至L1
这里有一个关键点：为了使L1可以确保新的承诺值是正确的，rollup在承诺之后需要给出一个SNARK证明以证明其正确性，且该证明必须在链上完成验证（所有区块链节点都必须验证该证明）

延迟与吞吐量

延迟：主要来自于两部分

• 发布至L2的交易之间的延迟
• 发布至L1的证明

前者主要是需要确保有足够数量的交易来构造一次批处理，后者主要来自于Prover的效率，Prover效率越高延迟也越低

吞吐量指的是rollup在一段时间内可以处理的L2上的交易的数量，假设某个节点可以在$Y$秒内向L1上传一个包含$X$笔交易的证明，且L2每$Y$秒产生了$X$笔交易

则表明每$Y$秒可以向Prover发送一批新的交易，并对这些交易生成一个新的证明，此时对应的吞吐量为$X/Y$ TPS（trans per sec），这一过程与Prover的效率无关，仅取决于Verifier的开销（Verfier的开销与交易数量之间的比值）

吞吐量很大程度上决定了链的可扩展性，但是延迟又会限制每一批交易的数量，从而影响吞吐率

一种解决思路是通过递归证明或者证明聚合的方式来实现并行性，从而降低Prover的延迟，如下图所示

通过并行运行多个Prover，每个Prover仅处理一小部分的交易并得到对应的证明，之后再利用证明聚合/递归证明将这些小的交易聚合成一个大的证明并放到链上，从而达到降低延迟，提高吞吐量的目的

References

$[1]$ SNARK Design, Part I, with Justin Thaler | a16z crypto research talks