目前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
网友评论