关于Nove 系列方案介绍

目前folding 方案取得了一系列进展，可以实现IVC (Incrementally Verifiable Computation)， 主要有以几种方案：

• Nova: 对R1CS实现folding；
• Sangria : Nova 方案推广到PLONKish 电路；
• SuperNova: 广义的Nova;
• HyperNova: 通过sum-checks和 CCS (customizable constraint system) 实现folding的方案；
• ProtoStar: 对于Nova 和 Sangria 实现高效广义化。

递归和聚合

递归SNARK 允许通过一个SNARK 证明另外SNARK 证明的验证。主要有三方面的应用：

• 证明其它证明的验证

其中内部电路一般比较大，主要生成知道witness的证明，一般证明生成速度比较快，证明比较大。对于外部电路，主要生成知道proof 的证明， 一般证明生成速度比较慢，证明比较小。

需要保证验证电路（外部电路）比statement 电路（内部电路）的尺寸非常小才行。

• 用生证明聚合

主要用于zkRollup之中，不必为所有的交易生成一个单一的证明，而是分组生成证明并聚合，直到最后的证明。

• IVC

IVC 可以将比较长的迭代计算聚合成一个证明，验证最终状态的正确性。

生成电路的证明包含两部分： 和

IVC 可以用在以下方面：

• 将一个长的证明分解成一系列相似的步骤，有效减少证明者的内存大小；
• 生成一个简法的证明，证明区块链当前的状态是正确的；
• 将F 当作一个或多个延迟函数，和IVC构成 VDF方案 (Verifiable Delay Function).
• ZK-VM: F 作为VM的一个计算步骤（例如一个OPCODE 码），例如EVM，LLVM, WASM等；
• zkBridge: F 根据状态验证区块链共识规则。

但是构建电路C 去验证 验证算法， 其中对多项式承诺的估计证明计算代码较高。

ZK-SNARKs的演化过程为：

Nova

Nova 通过对R1CS 进行folding 实现递归。通过Folding， 可以将两个实现压缩成一个，并生成压缩正确性的证明。

对于R1CS程序 ， 公开输入为， witness 为, ， 则 , 其中 是Hardmard 乘积。

为了方便folding， 引入Relaxed R1CS 方案，即：

• R1CS实例是为： R1CS 程序 A, B, C 和公开输入 ， 其中 为标量，E为向量，表示噪音参数；
• 公开输入为: 和 witness 为 ;
• 公开输入为: 和 witness 为 ;
• 对于都满足 .

Folding的过程为：

• 使用随机数, 使得：(1) ; (2) ; (3) , 其中 为cross-term。
• 计算 ;
• 计算 ;
• 则满足 ；

其中 是比较大，可以通过对于E进行承诺comm(E)进行优化。

基于Nova 设计的IVC 比基于可信设置的SNARK 计算量减少10倍，比无可信设计的SNARK 计算少100倍。

Sangria

Sangria 是实现Plonk 约束系统的folding 方案。

Plonk 电路为：

Plonk 电路的每一行需要满足如下约束：

为了方便 folding， 需要对Plonk电路进行 relaxation， 主要如下：

• 对于witness ， 添加噪音向量;
• 实例公开输入为：, 标量 ， 以及承诺.
• Relaxed 的门电路方程为：

SuperNova

对于Nova, 每个函数 都是一样的，SuperNova进一步扩展，每一个都是不同的处理函数， 即NIVC(Non-uniform IVC)。

参考

https://taiko.mirror.xyz/tk8LoE-rC2w0MJ4wCWwaJwbq8-Ih8DXnLUf7aJX1FbU