由于增量验证计算(IVCscheme)中有很多细节在论文中并未展开,本文则是深入解读Nova如何基于Relaxed R1CS构造IVC scheme。
本文假设读者已经对Nova的Relaxed R1CS和folding scheme已经有足够的了解,相关部分请参考白菜的Nova NIFS系列讲解或视频讲解。由于增量验证计算(IVC scheme)中有很多细节在论文中并未展开,本文则是深入解读如何基于Relaxed R1CS构造IVC scheme。 IVC scheme可以让Prover向Verifier证明,当初始状态为 $z_0 $时,执行 $n $次函数 $F $运算后结果为 $z_n $, 即 $z_n= F^{(n)}(z_0) $。首先考虑一个最简单的IVC方案来对其有一个直观理解,和其他的IVC方案类似,如下图Nova通过构造一个校正函数(argument function) $F' $, 将业务电路 $F $和其他与folding proof相关的部分组合到一个电路中。
其中 $i,z_0,z_i,u_i,Ui $为公共输出, $h{i+1} $为整个 $F' $电路的输出(也可以看做是公共输入),下面的三个小框则构成了整个验证者电路。 校正电路 $F' $主要是干两个事儿:
注: $F' $必须输出hash而不是直接输出 $U{i+1} $的原因为, $F' $在当前步 $i $直接输出 $U{i+1} $的话,则prover构造的 $u{i+1} $必须将 $U{i+1} $作为其公共输入放在 $u{i+1}.x $中,但是在下一步 $i+1 $中又必须将 $u{i+1}.x $和 $U_{i+1}.x $进行fold:
即把 $U{i+1} $和 $U{i+1}.x $( $U_{i+1} $除了 $x $外,还包含 $\overline{E},u,\overline{W} $这三项)两种不同的数据结构进行混合,会导致没法继续进行IVC。
因为 $F' $接受的公共输入 $U_i $和 $ui$ 包含commit之后的值,其实可以 $F' $整个电路看做一个CommitedReleaxedR1CS, 而 $(u{i+1}, w_{i+1}) $则是满足这个电路的trace(包含witness和public input)。
不考虑 $i=0 $的情况,对于Prover来说,他会根据 $(pk, (i, z_0, z_i), ω_i, Πi) $会生成一个IVC证明 $Π{i+1}={(U{i+1}, W{i+1}),(u{i+1}, w{i+1}) } $:
对于Verifier而言,则需要根据 $(i, z_0, z_i), Π_i) $验证是否满足所有电路约束:
这么做看起来没问题,但是实际上Verifier电路中验证的是U等包含承诺(在base field上)的约束,而 $F $电路则是在scalar field上验证约束,这导致直接在一个电路中同时验证Verifier电路和 $F $电路会存在field不匹配的问题。Nova源码中则采用了primary和secondary电路(后面将两者简称为主从电路)的方式来解决这一问题。这是最难理解的一部分,而整个论文只提到了可以使用循环曲线(cycle of curves)来解决IVC的证明问题,那么这两者到底有什么关联呢? 为了理解这一问题我们首先需要搞清楚什么是base field和scalar field,其次是verifier电路的约束是什么,才好理解如何通过循环曲线解决这一问题。
首先需要理解椭圆曲线的base field和scalar field的定义,如定义在 $mod(p) $上的椭圆曲线:
$$ y^2 = (x^5 -x + 3) mod(p) $$
质数 $p $构成的域为base field, $p $决定了 $x,y $的取值范围;椭圆曲线的阶(order): $r=E(F_p) $为椭圆曲线上点的个数(在[0,p]中任意给定点 $x $,有些 $y $不是该方程的整数解,所以 $p\ne r $), $r $也称为该曲线的scalar field。scalar field有个很重要的作用就是在该曲线的生成元 $G $上做commiment的时候,由于曲线上一共只有 $r $个点,超出部分则需要循环,所以当待commit的值 $x $大于 $r $时,则需要先取模再做曲线乘法: $(x \ mod(p))[G]$。
Verifier电路主要包括三类约束:
因此,当使用Pederson承诺实现IVC Sheme时,整个 $F' $电路规模为: $|F'|=|F| + O(2 · G + 2 · H + R) $,其中 $|F| $为业务电路 $F $所需的R1CS约束数目, $G $为椭圆曲线上scalar multiplication所需的约束, $H $为hash运算所需的约束, $R $为random oracle call所需的约束。
需要注意的是第一节IVC sheme中 $z_0,z_i,\overline{E},\overline{T},\overline{W},F中的约束 $等参数只有在同一个scalar field上,才能方便地将这些约束定义在同一个电路 $F' $上(否则需要进行field转化,non-native运算成本很高),但是目前为止我们假设的是 $\overline{E} $、 $\overline{T}和\overline{W} $是直接对F中参数(由 $AZ,BZ,CZ $等构成)所做的commitment上运算, $(z_0,z_i,AZ,BZ,CZ) $和 $(\overline{E},\overline{W}) $实际上不在一个field上,出现了field不匹配的问题。直接采用相同field的电路验证 $\overline{E},\overline{W} $等计算成本很高,那么自然有两种思路:
Nova正是利用循环曲线,在实际实现中将Verifier电路拆成Primary电路和Secondary电路两个电路,两者的约束分别定义在两条曲线的scalar field上,并使得Secondary电路可将其commitment直接传递给Primary电路作为其电路约束,反之亦然。
为便于后文描述,我们分别用 $上标^{(1)} $和 $上标^{(2)} $来分别表示Primary和Secondary电路中生成的instance、witness等参数及需满足的R1CS约束,用 $\mathcal{R}_1 $和 $\mathcal{R}_2 $分别表示Primary和Secondary上定义的所有R1CS电路约束;图中红色字体表示参数是从Primary生成或传递的参数及相应操作,蓝色字体则代表从Secondary生成或传递的参数及相应操作; $Fq $表示Primary电路所在的scalar field(即Secondary电路的base field,Secondary电路生成的commitment在这个field上),同理 $Fr $则表示Secondary电路所在的scalar field; ①-④则分别对应下述Prover执行的4个步骤。
Prover执行IVC scheme过程中,主从电路上的操作和两者整体的交互逻辑如下图:
如上图,对于Prover而言, 根据如下输入:
生成第 $i+1 $步所需的IVC证明 $π{i+1}:={(𝕦{i+1}^{(2)}, 𝕨{i+1}^{(2)}), (𝕌{i+1}^{(1)}, 𝕎{i+1}^{(1)}),(𝕌{i+1}^{(2)}, 𝕎_{i+1}^{(2)})} $, 具体执行的操作如下(对应于Nova官方代码lib.rs
中RecursiveSNARK
的prove_step
函数):
对于Verifier而言,则需要验证下面6个条件:
这其中比较难以理解的是knowledge soundness,它要求能根据IVC scheme和当前给定的IVC证明
$π_i:={({𝕦_i}^{(2)},{w_i}^{(2)}), (𝕌_i^{(1)}, 𝕎_i^{(1)}),(𝕌_i^{(2)}, 𝕎_i^{(2)})}$
即从 $(i,z_0^{(1)},z_i^{(1)},z_0^{(2)},z_i^{(2)},π_i) $中提取出前一步满足所有约束的IVC证明,具体分析如下(这部分对应于Nova官方代码lib.rs
中RecursiveSNARK
的verify
函数):
\mathcal{R}_2
$ 中的hash和folding约束,进一步确保了secondary电路中的 $z_i^{(2)}
$ 从前一步中的 $F_2(z_{i-1}^{(2)},aux_{i-1}^{(2)})
$ 函数计算而来, $𝕌_i^{(1)}
$ 是从前一步的 $(𝕌_{i-1}^{(1)},u_i^{(1)}, \overline{T_{i-1}}^{(1)})
$ 正确folding过来的; \mathcal{R}_1
$ 中对 $u_i^{(1)}.x_1
$ 的hash约束,以及 $\mathcal{R}_2
$ 约束 $u_i^{(2)}.x_0=u_i^{(1)}.x_1$ ,可以得出 $𝕦_i^{(1)}.x_1= H_1(vk, i^{(1)}, z_0^{(1)}, z_i^{(1)}, 𝕌_i^{(2)})$ ,参考第2和3步的推导,再根据条件5和 $\mathcal{R}_1
$ 中相应的约束,我们可以得出 $z_i^{(1)}=F1(z{i-1}^{(1)},aux{i-1}^{(1)})$ ,以及一定存在满足 $ReleaxedR1CS^{(2)}$ 的 $(U{i-1}^{(2)}, W{i-1}^{(2)})$ 和严格满足 $R1CS^{(2)}$ 约束的 $(u{i-1}^{(2)}, w_{i-1}^{(2)})$\mathcal{R}_1
$ 中对 $u_{i-1}^{(2)}.x_0
$ 的hash约束可以得出 $𝕦_{i-1}^{(2)}.x_0= H_1(vk, (i-1)^{(1)}, z_0^{(1)}, z_{i-1}^{(1)}, 𝕌_{i-1}^{(2)})
$ ;根据 $\mathcal{R}_1
$ 约束的 $u_i^{(1)}.x0=u{i-1}^{(2)}.x_1 $,以及 $\mathcal{R}_2
$ 对 $u_{i}^{(1)}.x_0
$ 的hash约束,可以推出 $𝕦_{i-1}^{(2)}.x_1= H_2(vk, (i-1)^{(2)}, z_0^{(2)}, z_{i-1}^{(2)}, 𝕌_{i-1}^{(1)})
$因此从步骤2中可提取出 $z_i^{(2)}=F2(z{i-1}^{(2)},aux{i-1}^{(2)}) $,步骤3中提取出 $(U{i-1}^{(1)}, W_{i-1}^{(1)}) $,这两者保证了业务电路F执行正确); 从步骤4中提取出 $z_i^{(1)}=F1(z{i-1}^{(1)},aux{i-1}^{(1)}) $和满足电路约束的 $(u{i-1}^{(2)}, w{i-1}^{(2)}) $、 $(U{i-1}^{(2)}, W{i-1}^{(2)}) $,从步骤5中提取出 $𝕦{i-1}^{(2)}.x_0= H_1(vk, (i-1)^{(1)}, z0^{(1)}, z{i-1}^{(1)}, 𝕌{i-1}^{(2)}) $和 $𝕦{i-1}^{(2)}.x_1= H_2(vk, (i-1)^{(2)}, z0^{(2)}, z{i-1}^{(2)}, 𝕌_{i-1}^{(1)}) $,即根据当前第 $i $步IVC证明是可以提取出满足所有约束的第 $i-1 $步证明,所以该IVC scheme满足Knowledge soundness。
需要注意的是Nova最开始的实现存在soundness 漏洞,其Verifier采用的是如下检验条件:
通过对比上一节的条件,会发现verifier验证的是 $𝕦_i^{(1)}.x_1= H_1(vk, i^{(1)}, z_0^{(1)}, z_i^{(1)}, 𝕌_i^{(2)})
$,而不是 $𝕦_i^{(2)}.x_0= H_1(vk, i^{(1)}, z_0^{(1)}, z_i^{(1)}, 𝕌_i^{(2)})
$,这会存在一个soundness漏洞。因为表面上,看对于 $\mathcal{R}_1
$而言同时验证了 $\{(𝕦_i^{(1)}, 𝕨_i^{(1)}), (𝕌_i^{(1)}, 𝕎_i^{(1)})\}
$,按照folding schem本身的soundness就可以推出 $\{(𝕦_{i-1}^{(1)}, 𝕨_{i-1}^{(1)}), (𝕌_{i-1}^{(1)}, 𝕎_{i-1}^{(1)})\}
$也会满足 $\mathcal{R}_1
$中定义的 $R1CS^{(1)}
$ 约束;但是实际上这里并未验证 $𝕦_i^{(1)}.x_0= H_2(vk, i^{(2)}, z_0^{(2)}, z_i^{(2)}, 𝕌_i^{(1)})
$,即没有任何的约束或者检查保证正确的 $u_i^{(1)} $被fold到 $𝕌_i^{(1)}
$ 中。那么根据 $\mathcal{R}_1
$ 和 $\mathcal{R}_2
$ 的对称性,恶意验证者可以构造自己选定的 $u_i^{(1)}
$ 以及任意满足R1CS约束的平凡解 $𝕌_⊥^{(1)}
$,按照前文所述的方式迭代计算两次IVC prover,就可以生成满足上述约束的IVC proof。具体的攻击过程可以参见Nova修订的论文:Revisiting the Nova Proof System on a Cycle of Curves。
注:当然也可以分别加上 $𝕦_i^{(1)}.x_0 $和 $𝕦_i^{(2)}.x_0 $的hash验证,但是没有必要,因为这样会增大proof大小。
综上,可以看出Nova的整个IVC proof是直接把witness( $𝕨{i+1}^{(2)},W{i+1}^{(1)},W_{i+1}^{(2)} $)作为IVC proof的一部分,因此Nova IVC scheme不是零知识的,这导致Nova只能允许一个prover来进行folding和生成证明。此外,IVC prover的计算成本为常数大小,且是文献中已知最低的,其主要取决于两个幂运算,运算规模为 $O(|F|) $( $F $为业务电路规模); proof size则是 $O(|F|) $大小的群元素。虽然Nova本身不具备零知识和简洁性特性,但如果想生成一个zksnark以证明Prover生成了有效的IVC proof,论文(对应于Construction5)和代码(对应于Nova官方代码lib.rs
中的CompressedSNARK
相关部分)均给出了采用Spartan作为zksnark组件来实现的方案,可在迭代一定步数后生成zksnark proof。
注1:为什么不直接在每一步迭代后立刻生成zksnark的IVC proof的呢?因为Prover若在每一步生成zksnark proof,成本会很高,这也是nova采用folding来延迟最终生成证明的基本思路,这可以平摊多步folding过程中Prover所需的少量计算开销。 注2: Nova最新的Scheme由于有辅助输入 $aux_i^{(1)},aux_i^{(2)} $会导致出现延展性攻击,本文不对此展开,详见其补充论文。
参考资料
视频讲解
- by 作者Srinath Setty [EN]
- by 郭宇@安比: A short introduction to Nova [EN]
- by 郭宇@安比: Nova - Recursive SNARKs without trusted setup [中文]
- Nova Crash Course with Justin Drake [EN]
论文
- Nova: Recursive Zero-Knowledge Arguments from Folding Schemes
- Revisiting the Nova Proof System on a Cycle of Curves
椭圆曲线的base field和scalar field
- difference between base field and scalar field
- order of ecc
循环曲线
- Scalable Zero Knowledge via Cycles of Elliptic Curves
- The halo2 book
- Nova based zk VM:循环曲线这一节讲解不错
代码
- Microsoft Nova implementation
- Middleware to compile Circom circuits to Nova
- HyperNova
其他
- 用于生成Transcript的Sponge API
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!