深入理解Nova IVC Scheme中的循环曲线和主从电路

[dajuguan]

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,U_i $为公共输入， $h_{i+1} $为整个 $F' $电路的输出(也可以看做是公共输入)，下面的三个小框则构成了整个验证者电路。
校正电路 $F' $主要是干两个事儿：

• 执行业务电路 $z_{i+1}= F(z_i) $,这里忽略其他会引入随机性的辅助输入.
• 执行验证者电路
  1. 校验hash以验证上一步的 $U_i $是否fold正确
  2. 将 $U_i $和 $u_i$ fold成 $U_{i+1} $
  3. 根据 $z_{i+1}和U_{i+1} $生成新的hash: $h_{i+1} $，以便下一步将 $h_{i+1} $作为 $u_{i+1} $中的公共输入进行校验；其中 $u_{i+1} $实例由prover构造。

注: $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 $和 $u_i$ 包含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}) } $:

1. 解析 $Π_{i}={(U_i, W_i),(u_i, w_i) } $, 离线fold出新的instance,witness和proof: $(U_{i+1},W_{i+1},\overline{T}) $。离线fold指的是不经过电路，电路实际上是由verifier来执行的；
2. 执行 $F' $电路并trace出 $(u_{i+1}, w_{i+1}) $
3. 输出 $i+1 $步的IVC证明 $Π_{i+1}={(U_{i+1}, W_{i+1}),(u_{i+1}, w_{i+1}) } $

对于Verifier而言，则需要根据 $(i, z_0, z_i), Π_i) $验证是否满足所有电路约束:

1. 解析 $Π_{i}={(U_i, W_i),(u_i, w_i) } $;
2. 验证 $u_i.x = hash(vk, i, z_0, z_i, U_i) $。这表明 $U_i $的folding是正确执行的;
3. 验证 $u_i.\overline{E}=\overline{0} $和 $u_i.u=1 $，并验证 $(u_i,w_i) $满足ReleaxedR1CS约束，这表明 $(u_i,w_i) $严格满足普通的R1CS约束(即 $Az◦Bz=Cz $，用严格满足以区分RelaxedR1CS约束 $Az◦Bz=uCz+E $)，即当前第 $i $步执行正确;
4. 验证 $(U_i,W_i) $满足ReleaxedR1CS约束，根据folding scheme的soundness可知，这表明 $F $从 $0 $到 $i $步均执行正确。

这么做看起来没问题，但是实际上Verifier电路中验证的是U等包含承诺(在base field上)的约束，而 $F $电路则是在scalar field上验证约束，这导致直接在一个电路中同时验证Verifier电路和 $F $电路会存在field不匹配的问题。Nova源码中则采用了primary和secondary电路(后面将两者简称为主从电路)的方式来解决这一问题。这是最难理解的一部分，而整个论文只提到了可以使用循环曲线(cycle of curves)来解决IVC的证明问题，那么这两者到底有什么关联呢？
为了理解这一问题我们首先需要搞清楚什么是base field和scalar field，其次是verifier电路的约束是什么，才好理解如何通过循环曲线解决这一问题。

IVC Scheme中的主从电路

椭圆曲线的base field和scalar field

首先需要理解椭圆曲线的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电路的约束

Verifier电路主要包括三类约束:

1. 验证 $u_i.x = hash(vk, i, z_0, z_i, U_i) $，这是一个hash电路约束
2. 验证 $U_{i+1} ← NIFS.V(U_i,u_i) $，即下图中的四个等式，其中 $r $为从random oracle获取的随机数，这里random oracle通过波塞冬hash函数实现的，在论文图1中称为预言机(random oracle call)约束；第1个和第3个等式是scalar和椭圆曲线的点做乘法，需要scalar multiplication约束；第4个约束则是两个hash相乘后做加法，由于hash后的值与 $z_0 $不在同一个field中，需要先把他们分别进行field转换(non-native运算)，再进行乘法运算，生成相应约束。

3. 需要计算 $h_{i+1} $，这也是一个hash电路约束

因此，当使用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} $等计算成本很高，那么自然有两种思路:

1. 直接将Verifier电路从 $F' $电路中剥离出来，使其成为另外一个电路。但这不可行，因为F电路和Verifier电路都需要用到 $z_i $这个公共输入，这限制了他们的电路约束必须在同一个field上;
2. 采用一个电路生成的proof由另外一个电路验证的思路，并保证一个电路所用曲线的base field和scalar field正好与另一个电路所用曲线的scalar field和base field匹配，这两组曲线称为循环曲线(cycle of curves)。如下图，循环曲线的概念最早是zcash团队在2016年的Scalable Zero Knowledge via Cycles of Elliptic Curves这篇paper引入，其为了解决递归zk-snark中电路自身约束定义在scalar field上，直接采用该电路验证其产生的proof(在base field上)计算成本很高这个问题，更深入的讲解可参考Alessandro Chiesa的讲解。

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函数):

1. 在Primary电路上fold来自Secondary电路committed instances，witness对 $(𝕦_i^{(2)}, 𝕨_i^{(2)}) 和(𝕌_i^{(2)}, 𝕎_i^{(2)}) $:
   
   得到folding证明 $\overline{T_i}^{(2)} $, 并使得 $(U_{i+1}^{(2)}, W_{i+1}^{(2)}) $
2. 在Primary电路上计算新的witness，instance对 $R1CS^{(1)} $:
   1. 将 $(vk,i^{(1)},z_0^{(1)},z_{i}^{(1)},aux_{i}^{(1)}, 𝕌_{i}^{(2)},u_i^{(2)},\overline{T_{i}}^{(2)}) $作为电路约束，即构造Primary上的 $\mathcal{R}_1 $;
   2. 计算满足上述约束的相应extended witness: $w_{i+1}^{(1)} $;
   3. 对 $w_{i+1}^{(1)} $承诺得到 $\overline{w_{i+1}}^{(1)}<- Commit(pp_W^{(1)}, w_{i+1}^{(1)}) $
   4. 通过hash计算 $x_1^{(1)}:=H_1(vk, (i+1)^{(1)}, z_0^{(1)}, z_{i+1}^{(1)}:=F_1(z_{i}^{(1)},aux_{i}^{(1)}), 𝕌_{i+1}^{(2)}) $, 并使得 $x_0^{(1)}:=u_i^{(2)}.x_1 $
   5. 构造新的 $u_{i+1}^{(1)}=(\overline{0}^{(1)},\overline{1}^{(1)},\overline{w_{i+1}}^{(1)},(x_0^{(1)},x_1^{(1)})) $和 $w_{i+1}^{(1)}=(\vec{0}^{(1)},w_{i+1}^{(1)}) $
3. 在Secondary电路上fold上述来自Primary电路的 $(u_{i+1}^{(1)}, w_{i+1}^{(1)}) $和comitted $((U_{i}^{(1)}, W_{i}^{(1)}))$:
   
   得到folding证明 $\overline{T_{i}}^{(1)}$, 新的 $(U_{i+1}^{(1)}, W_{i+1}^{(1)}) $
4. 在Secondary电路上计算新的witness instance对 $R1CS^{(2)} $:
   1. 将 $(vk,i^{(2)},z_0^{(2)},z_{i}^{(2)},aux_{i}^{(2)}, 𝕌_{i}^{(1)},u_i^{(1)},\overline{T_{i}}^{(1)}) $作为电路约束，即构造Secondary上的 $\mathcal{R}_2 $
   2. 计算满足上述约束的相应extended witness: $w_{i+1}^{(2)} $
   3. 对 $w_{i+1}^{(2)}$ 承诺得到 $\overline{w_{i+1}}^{(2)}<- Commit(pp_W^{(2)}, w_{i+1}^{(2)}) $
   4. 通过hash计算 $x_1^{(2)}:=H_2(vk, (i+1)^{(2)}, z_0^{(2)}, z_{i+1}^{(2)}:=F_2(z_{i}^{(2)},aux_{i}^{(2)}), 𝕌_{i+1}^{(1)}) $, 并使得 $x_0^{(2)}:=u_i^{(1)}.x_1 $
   5. 构造新的 $u_{i+1}^{(2)}=(\overline{0}^{(2)}, \overline{1}^{(2)}, \overline{w_{i+1}}^{(2)}, (x_0^{(2)}, x_1^{(2)}) )$ 和 $w_{i+1}^{(2)}=(\vec{0}^{(2)}, w_{i+1}^{(2)}) $

Verifier相关验证

对于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函数):

1. 条件6严格满足R1CS的条件表明他的witness包含一组 $(z_{i-1}^{(2)},aux_{i-1}^{(2)}, 𝕌_{i-1}^{(1)},u_i^{(1)},\overline{T_{i-1}}^{(1)}) $
2. 条件3和 $\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过来的;
3. 根据条件4和folding scheme的knowledge soundness可知，一定可以为 $𝕌_{i-1}^{(1)}和u_i^{(1)}$ 分别提取出满足 $R1CS^{(1)}$ 约束的witness: $W_{i-1}^{(1)}和w_i^{(1)}$，由于 $\mathcal{R}_2$ 中约束了普通R1CS电路中 $u_i^{(1)}.\overline{E}=\overline{0}^{(1)}$ 和 $u_i^{(1)}.s=1^{(1)}$，因此可以推出 $(u_i^{(1)}, w_i^{(1)})$ 一定严格满足 $R1CS^{(1)}$ 约束；
4. 条件2和 $\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)}=F_1(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)})$
5. 根据 $\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)}.x_0=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)}=F_2(z_{i-1}^{(2)},aux_{i-1}^{(2)}) $，步骤3中提取出 $(U_{i-1}^{(1)}, W_{i-1}^{(1)}) $，这两者保证了业务电路F执行正确); 从步骤4中提取出 $z_i^{(1)}=F_1(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)}, z_0^{(1)}, z_{i-1}^{(1)}, 𝕌_{i-1}^{(2)}) $和 $𝕦_{i-1}^{(2)}.x_1= H_2(vk, (i-1)^{(2)}, z_0^{(2)}, z_{i-1}^{(2)}, 𝕌_{i-1}^{(1)}) $，即根据当前第 $i $步IVC证明是可以提取出满足所有约束的第 $i-1 $步证明，所以该IVC scheme满足Knowledge soundness。

Nova早期实现存在的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