{"content":{"title":"深入理解Nova IVC Scheme中的循环曲线和主从电路","body":"## IVC scheme基本思路\r\n本文假设读者已经对Nova的Relaxed R1CS和folding scheme已经有足够的了解，相关部分请参考[白菜的Nova NIFS系列讲解](https://learnblockchain.cn/article/5978)或[视频讲解](##视频讲解)。由于增量验证计算(IVC scheme)中有很多细节在论文中并未展开，本文则是深入解读如何基于Relaxed R1CS构造IVC scheme。\r\nIVC scheme可以让Prover向Verifier证明，当初始状态为 $z_0 $时，执行 $n $次函数 $F $运算后结果为 $z_n $， 即 $z_n= F^{(n)}(z_0) $。首先考虑一个最简单的IVC方案来对其有一个直观理解，和其他的IVC方案类似，如下图Nova通过构造一个校正函数(argument function) $F' $, 将业务电路 $F $和其他与folding proof相关的部分组合到一个电路中。\r\n\r\n![Pasted image 20230701135723](https://github.com/Antalpha-Labs/zkp-co-learn/assets/13568446/2c33fa0c-a2fc-491b-b79e-91514e866e68)\r\n\r\n其中 $i,z_0,z_i,u_i,U_i $为公共输出， $h_{i+1} $为整个 $F' $电路的输出(也可以看做是公共输入)，下面的三个小框则构成了整个**验证者电路**。\r\n校正电路 $F' $主要是干两个事儿：\r\n- 执行业务电路 $z_{i+1}= F(z_i) $,这里忽略其他会引入随机性的辅助输入.\r\n- 执行验证者电路\r\n\t1. 校验hash以验证上一步的 $U_i $是否fold正确\r\n\t2. 将 $U_i $和 $u_i$ fold成 $U_{i+1} $\r\n\t3. 根据 $z_{i+1}和U_{i+1} $生成新的hash: $h_{i+1} $，以便下一步将 $h_{i+1} $作为 $u_{i+1} $中的公共输入进行校验；其中 $u_{i+1} $实例由prover构造。\r\n\r\n> 注:  $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:\r\n\r\n![Pasted image 20230701144654](https://github.com/Antalpha-Labs/zkp-co-learn/assets/13568446/90db9d50-fbe8-46cb-8e4b-b2f047a16d67)\r\n\r\n> 即把 $U_{i+1} $和 $U_{i+1}.x $( $U_{i+1} $除了 $x $外，还包含 $\\overline{E},u,\\overline{W} $这三项)两种不同的数据结构进行混合，会导致没法继续进行IVC。\r\n\r\n因为 $F' $接受的公共输入 $U_i $和 $u_i$ 包含commit之后的值，其实可以 $F' $整个电路看做一个CommitedReleaxedR1CS, 而 $(u_{i+1}, w_{i+1}) $则是满足这个电路的trace(包含witness和public input)。\r\n\r\n不考虑 $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}) \\} $:\r\n1. 解析 $Π_{i}=\\{(U_i, W_i),(u_i, w_i) \\} $, 离线fold出新的instance,witness和proof:  $(U_{i+1},W_{i+1},\\overline{T}) $。离线fold指的是不经过电路，电路实际上是由verifier来执行的；\r\n2. 执行 $F' $电路并trace出 $(u_{i+1}, w_{i+1}) $\r\n3. 输出 $i+1 $步的IVC证明 $Π_{i+1}=\\{(U_{i+1}, W_{i+1}),(u_{i+1}, w_{i+1}) \\} $\r\n\r\n对于Verifier而言，则需要根据 $(i, z_0, z_i), Π_i) $验证是否满足所有电路约束:\r\n1. 解析 $Π_{i}=\\{(U_i, W_i),(u_i, w_i) \\} $;\r\n2. 验证 $u_i.x = hash(vk, i, z_0, z_i, U_i) $。这表明 $U_i $的folding是正确执行的;\r\n3. 验证 $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 $步执行正确;\r\n4. 验证 $(U_i,W_i) $满足ReleaxedR1CS约束，根据folding scheme的soundness可知，这表明 $F $从 $0 $到 $i $步均执行正确。\r\n\r\n这么做看起来没问题，但是实际上Verifier电路中验证的是U等包含承诺(在base field上)的约束，而 $F $电路则是在scalar field上验证约束，这导致直接在一个电路中同时验证Verifier电路和 $F $电路会存在field不匹配的问题。Nova源码中则采用了primary和secondary电路(后面将两者简称为*主从电路*)的方式来解决这一问题。这是最难理解的一部分，而整个论文只提到了可以使用循环曲线(cycle of curves)来解决IVC的证明问题，那么这两者到底有什么关联呢？\r\n为了理解这一问题我们首先需要搞清楚什么是base field和scalar field，其次是verifier电路的约束是什么，才好理解如何通过循环曲线解决这一问题。\r\n\r\n## IVC Scheme中的主从电路\r\n### 椭圆曲线的base field和scalar field\r\n首先需要理解椭圆曲线的base field和scalar field的定义，如定义在 $mod(p) $上的椭圆曲线:\r\n \r\n$$\r\ny^2 = (x^5 -x + 3) mod(p)\r\n $$\r\n\r\n质数 $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]$。\r\n\r\n### Verifier电路的约束\r\nVerifier电路主要包括三类约束:\r\n1. 验证 $u_i.x = hash(vk, i, z_0, z_i, U_i) $，这是一个hash电路约束\r\n2. 验证 $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运算)，再进行乘法运算，生成相应约束。\r\n\r\n![Pasted image 20230629100333](https://github.com/Antalpha-Labs/zkp-co-learn/assets/13568446/fc506471-0738-4dd9-9313-3275356fc461)\r\n\r\n3. 需要计算 $h_{i+1} $，这也是一个hash电路约束\r\n\r\n因此，当使用Pederson承诺实现IVC Sheme时，整个 $F' $电路规模为:  $|F'|=|F| + O(2 · G + 2 · H + R) $，其中 $|F| $为业务电路 $F $所需的R1CS约束数目， $G $为椭圆曲线上scalar multiplication所需的约束， $H $为hash运算所需的约束， $R $为random oracle call所需的约束。\r\n\r\n### 循环曲线\r\n\r\n需要注意的是第一节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} $等计算成本很高，那么自然有两种思路:\r\n1. 直接将Verifier电路从 $F' $电路中剥离出来，使其成为另外一个电路。但这不可行，因为F电路和Verifier电路都需要用到 $z_i $这个公共输入，这限制了他们的电路约束必须在同一个field上;\r\n2. 采用一个电路生成的proof由另外一个电路验证的思路，并保证一个电路所用曲线的base field和scalar field正好与另一个电路所用曲线的scalar field和base field匹配，这两组曲线称为循环曲线(cycle of curves)。如下图，循环曲线的概念最早是zcash团队在2016年的[Scalable Zero Knowledge via Cycles of Elliptic Curves这篇paper](https://eprint.iacr.org/2014/595.pdf)引入，其为了解决递归zk-snark中电路自身约束定义在scalar field上，直接采用该电路验证其产生的proof(在base field上)计算成本很高这个问题，更深入的讲解可参考[Alessandro Chiesa的讲解](https://www.youtube.com/watch?v=cLjfufsi2gM)。\r\n\r\n![Pasted image 20230702120728](https://github.com/Antalpha-Labs/zkp-co-learn/assets/13568446/7e37c8da-c2ec-443d-9f13-48957924b982)\r\n\r\nNova正是利用循环曲线，在实际实现中将Verifier电路拆成Primary电路和Secondary电路两个电路，两者的约束分别定义在两条曲线的scalar field上，并使得Secondary电路可将其commitment直接传递给Primary电路作为其电路约束，反之亦然。\r\n\r\n### 主从电路逻辑\r\n为便于后文描述，我们分别用 $上标^{(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个步骤。\r\n\r\nProver执行IVC scheme过程中，主从电路上的操作和两者整体的交互逻辑如下图：\r\n\r\n![Pasted image 20230702184915](https://github.com/Antalpha-Labs/zkp-co-learn/assets/13568446/fc4f4032-3e74-4ecd-ad04-5731c8c1df9c)\r\n\r\n如上图，对于Prover而言, 根据如下输入:\r\n\r\n![Pasted image 20230701155422](https://github.com/Antalpha-Labs/zkp-co-learn/assets/13568446/6d3b4757-0164-4c1f-8817-b5b94aafa2d9)\r\n\r\n生成第 $i+1 $步所需的IVC证明  $π_{i+1}:=\\{(𝕦_{i+1}^{(2)}, 𝕨_{i+1}^{(2)}), (𝕌_{i+1}^{(1)}, 𝕎_{i+1}^{(1)}),(𝕌_{i+1}^{(2)}, 𝕎_{i+1}^{(2)})\\} $, 具体执行的操作如下(对应于[Nova官方代码](https://github.com/microsoft/Nova)`lib.rs`中`RecursiveSNARK`的`prove_step`函数):\r\n1. 在Primary电路上fold来自Secondary电路committed instances，witness对  $(𝕦_i^{(2)}, 𝕨_i^{(2)}) 和(𝕌_i^{(2)}, 𝕎_i^{(2)}) $:\r\n   ![Pasted image 20230701160045](https://github.com/Antalpha-Labs/zkp-co-learn/assets/13568446/8e1cfca0-d20c-4212-8537-d3c7ab50b1d4)\r\n   得到folding证明 $\\overline{T_i}^{(2)} $, 并使得 $(U_{i+1}^{(2)}, W_{i+1}^{(2)}) $\r\n2. 在Primary电路上计算新的witness，instance对 $R1CS^{(1)} $:\r\n\t1. 将 $(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 $;\r\n\t2. 计算满足上述约束的相应extended witness:  $w_{i+1}^{(1)} $;\r\n\t3. 对 $w_{i+1}^{(1)} $承诺得到 $\\overline{w_{i+1}}^{(1)}<- Commit(pp_W^{(1)}, w_{i+1}^{(1)}) $\r\n\t4. 通过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 $\r\n\t5. 构造新的 $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)}) $\r\n3. 在Secondary电路上fold上述来自Primary电路的 $(u_{i+1}^{(1)}, w_{i+1}^{(1)}) $和comitted $((U_{i}^{(1)}, W_{i}^{(1)}))$:\r\n   ![Pasted image 20230701211726](https://github.com/Antalpha-Labs/zkp-co-learn/assets/13568446/b4234fd5-5bcd-4e7d-bf1f-cbdadca4a4e3)\r\n   得到folding证明 $\\overline{T_{i}}^{(1)}$, 新的  $(U_{i+1}^{(1)}, W_{i+1}^{(1)}) $\r\n4. 在Secondary电路上计算新的witness instance对 $R1CS^{(2)} $:\r\n\t1.  将 $(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 $\r\n\t2. 计算满足上述约束的相应extended witness:  $w_{i+1}^{(2)} $\r\n\t3. 对 $w_{i+1}^{(2)}$ 承诺得到 $\\overline{w_{i+1}}^{(2)}<- Commit(pp_W^{(2)}, w_{i+1}^{(2)}) $\r\n\t4. 通过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 $\r\n\t5. 构造新的 $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)}) $\r\n\r\n### Verifier相关验证\r\n对于Verifier而言，则需要验证下面6个条件：\r\n\r\n![Pasted image 20230702185242](https://github.com/Antalpha-Labs/zkp-co-learn/assets/13568446/b7f833d5-82ae-4f14-a94a-6bb6c563657c)\r\n\r\n这其中比较难以理解的是**knowledge soundness**，它要求能根据IVC scheme和当前给定的IVC证明 \r\n$π_i:=\\{({𝕦_i}^{(2)},{w_i}^{(2)}), (𝕌_i^{(1)}, 𝕎_i^{(1)}),(𝕌_i^{(2)}, 𝕎_i^{(2)})\\}$\r\n即从 $(i,z_0^{(1)},z_i^{(1)},z_0^{(2)},z_i^{(2)},π_i) $中提取出前一步满足所有约束的IVC证明，具体分析如下(这部分对应于[Nova官方代码](https://github.com/microsoft/Nova)`lib.rs`中`RecursiveSNARK`的`verify`函数):\r\n1.  条件6严格满足R1CS的条件表明他的witness包含一组 $(z_{i-1}^{(2)},aux_{i-1}^{(2)}, 𝕌_{i-1}^{(1)},u_i^{(1)},\\overline{T_{i-1}}^{(1)}) $\r\n2. 条件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过来的; \r\n3. 根据条件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)}$ 约束；\r\n4. 条件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)})$\r\n5. 根据 $`\\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)}) `$\r\n\r\n因此从步骤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。\r\n\r\n### Nova早期实现存在的Soundness漏洞\r\n需要注意的是Nova最开始的[实现](https://github.com/microsoft/Nova/commit/afd7403336fdf6625658108256f4b4163da197c9)存在soundness 漏洞，其Verifier采用的是如下检验条件:\r\n\r\n![Pasted image 20230702190134](https://github.com/Antalpha-Labs/zkp-co-learn/assets/13568446/8cf90955-6c1b-4fe2-a8f8-6c3278131344)\r\n\r\n通过对比上一节的条件，会发现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](https://eprint.iacr.org/2023/969)。\r\n\r\n> 注：当然也可以分别加上 $𝕦_i^{(1)}.x_0 $和 $𝕦_i^{(2)}.x_0 $的hash验证，但是没有必要，因为这样会增大proof大小。\r\n\r\n## 总结\r\n综上，可以看出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官方代码](https://github.com/microsoft/Nova)`lib.rs`中的`CompressedSNARK`相关部分)均给出了采用Spartan作为zksnark组件来实现的方案，可在迭代一定步数后生成zksnark proof。\r\n> 注1：为什么不直接在每一步迭代后立刻生成zksnark的IVC proof的呢？因为Prover若在每一步生成zksnark proof，成本会很高，这也是nova采用folding来延迟最终生成证明的基本思路，这可以平摊多步folding过程中Prover所需的少量计算开销。\r\n> 注2: Nova最新的Scheme由于有辅助输入 $aux_i^{(1)},aux_i^{(2)} $会导致出现延展性攻击，本文不对此展开，详见[其补充论文](https://eprint.iacr.org/2023/969)。\r\n## 参考资料\r\n### 视频讲解\r\n- [by 作者Srinath Setty [EN]](https://www.youtube.com/watch?v=mY-LWXKsBLc)\r\n- [by 郭宇@安比: A short introduction to Nova [EN]](https://www.youtube.com/watch?v=hq-1bLVz59w&t=324s)\r\n- [by 郭宇@安比: Nova - Recursive SNARKs without trusted setup [中文]](https://www.youtube.com/watch?v=l19roUItyUE)\r\n- [Nova Crash Course with **Justin Drake**  [EN]](https://www.youtube.com/watch?v=SwonTtOQzAk&t=2815s)\r\n### 论文\r\n- [Nova: Recursive Zero-Knowledge Arguments from Folding Schemes](https://eprint.iacr.org/2021/370.pdf)\r\n- [Revisiting the Nova Proof System on a Cycle of Curves](https://eprint.iacr.org/2023/969)\r\n### 椭圆曲线的base field和scalar field\r\n- [difference between base field and scalar field](https://crypto.stackexchange.com/questions/66436/for-an-elliptic-curve-what-is-the-difference-between-the-base-field-modulus-q)\r\n- [order of ecc](https://medium.com/asecuritysite-when-bob-met-alice/whats-the-order-in-ecc-ac8a8d5439e8)\r\n### 循环曲线\r\n- [Scalable Zero Knowledge via Cycles of Elliptic Curves](https://eprint.iacr.org/2014/595.pdf)\r\n- [The halo2 book](https://zcash.github.io/halo2/index.html)\r\n- [Nova based zk VM:循环曲线这一节讲解不错](https://hackmd.io/@monyverse/H1XSVmHNh#Curve-Cycling)\r\n### 代码\r\n- [Microsoft Nova implementation](https://github.com/microsoft/Nova)\r\n- [Middleware to compile Circom circuits to Nova](https://github.com/nalinbhardwaj/Nova-Scotia)\r\n- [HyperNova](https://github.com/privacy-scaling-explorations/Nova/tree/hypernova)\r\n### 其他\r\n- [用于生成Transcript的Sponge API ](https://hackmd.io/bHgsH6mMStCVibM_wYvb2w)"},"author":{"user":"https://learnblockchain.cn/people/720","address":null},"history":null,"timestamp":1688347650,"version":1}