1. 引言

主要见斯坦福大学Wilson Nguyen、Dan Boneh和微软研究中心Srinath Setty 2023年论文《Revisiting the Nova Proof System on a Cycle of Curves》。

前序博客有：

• Nova: Recursive Zero-Knowledge Arguments from Folding Schemes学习笔记

在2021年Nova 论文中，基于relaxed R1CS statements的folding scheme，构建了针对IVC（Incrementally Verifiable Computation）的高效简洁证明系统——Nova证明系统。不过在该论文中，Nova的描述和分析都限制为single chain of incremental computation（$z_n=F^n(z_0)$，称为single IVC chain），即每个计算步骤完全相同，当前步骤的输出作为下一步的输入，每一步都运行某函数$F$，并将 关于之前步骤有效性的statement fold入 an ongoing statement中。在Nova论文中所展示的Nova证明系统使用的是order为$p$的单一椭圆曲线。

但实际实现时，为提升效率，在https://github.com/Microsoft/Nova代码中，采用的是 2-cycle of elliptic curves。在代码中对应的2条并行的IVC链，且二者必须连接在一起。但迄今为止，该修改方案仅在代码中体现了，并无任何公开的安全性证明。

本文将揭示在https://github.com/Microsoft/Nova的2-cycle Nova系统实现中存在的soundness vulnerability——见附录B。该漏洞使得攻击者可为false statement生成proof——如，在笔记本上仅需1.46秒就可生成 “$2^{75}$轮Minroot VDF的正确执行”的让人信服的Nova proof【事实上这应该是不可能的】。该攻击的核心问题在于原始的2-cycle Nova系统生成的IVC proof中包含了一个额外的R1CS instance-witness pair——Verifier未对其做足够约束。

修改了该可靠性漏洞之后的系统效率更高。特别是修改后，从recursive proof中移除了一个R1CS instance-witness pair——使得修订后的Nova具有更短的IVC proof。目前https://github.com/Microsoft/Nova中为修复了该漏洞的安全、优化好的代码。

同时，本文将展示Nova proof是可延展的，在某些应用中存在安全漏洞，并讨论了几个缓解措施。

1.1 IVC（Incrementally Verifiable Computation）

IVC（Incrementally Verifiable Computation）首次由Valiant在其2008年论文《Incrementally verifiable computation or proofs of knowledge imply time/space efficiency》中提出。

对于某函数 F : { 0 , 1 } a × { 0 , 1 } b → { 0 , 1 } a F:\{0,1\}^a\times\{0,1\}^b\rightarrow\{0,1\}^a F:{0,1}a×{0,1}b→{0,1}a，有公开值 z 0 , z i ∈ { 0 , 1 } a z_0,z_i\in\{0,1\}^a z0​,zi​∈{0,1}a，IVC方案是指Prover $\mathcal{P}$ 声称其知道辅助值 aux 0 , ⋯ , aux i − 1 ∈ { 0 , 1 } b \text{aux}_0,\cdots,\text{aux}_{i-1}\in \{0,1\}^b aux0​,⋯,auxi−1​∈{0,1}b，使得：

，并生成相应的简洁证明。

IVC方案定义为：

以上定义具有完备性和knowledge soundness属性：【其中knowledge soundness属性，是指可full extraction——提取execution chain中的所有辅助值。本文重点关注IVC方案的knowledge soundness属性。】

上述定义中，Verifier的输入中包含函数$F$的描述，即意味着Verifier running time 必须至少为linear in the size of $F$。可额外引入Keygen算法——输出专门针对$F$的prover-verifier key pair (pk, vk)，其中vk size为sub-linear in the size of $F$。这样就将处理函数$F$描述的工作 转移给了 预处理阶段。Verifier代替$F$以vk为输入，从而可由更快的线上Verifier。事实上在nova中包含了Keygen算法来实现succinct Verifier。

1.2 Committed Relaxed R1CS over a Ring

基于cycle of curves的Nova证明系统同时使用了2个有限域${\mathbb{F}}_1,{\mathbb{F}}_2$。因此可将Nova中的原语看成是基于有限交换ring $R:={\mathbb{F}}_1\times {\mathbb{F}}_2$，其中的加法和乘法运算是按元素进行的。即对于$R$中的$a=(a_1,a_2,),b=(b_1,b_2)$，有$a+b=(a_1+b_1,a_2+b_2),a\cdot b=(a_1{b}_1,a_2{b}_2)$。

承诺方案定义为：

承诺方案应满足：binding属性、加法同态属性，以及succinct属性。

限交换ring $R$，对Relaxed R1CS的承诺表示为：

注意，当$s=1$且$E$为零向量时，Relaxed R1CS对应为R1CS，即R1CS为Relaxed R1CS的特例情况。

Trivially Satisfiable Instance-Witness Pair定义：

• 以committed instance-witness pair $({\mathbb{U}}_{\perp },{\mathbb{W}}_{\perp })$表示某R1CS约束系统R1CS over $R$的trivially satisfying pair。
• 在Nova论文中，改建Trivially Satisfiable Instance-Witness Pair的方法为：【使得$0=0$恒成立。用作IVC的初始instance-witness pair。】
  • 设置$E,W,x$均为合适长度的零向量
  • $\bar{E},\bar{W}$均为对零向量的承诺值
  • $s=0$

1.3 针对Committed Relaxed R1CS over a Ring的Folding Scheme

Folding Schemes为IVC提供了高效方案。近期的一些研究成果[1,2,10-12,15]为不同的问题构建了高效folding方案。Nova论文则为2个committed relaxed R1CS的instance和witness 构建了优雅的folding方案。

Nova的folding scheme为public-coin、one-round交互协议，并可在random oracle model下使用Fiat-Shamir转换为来实现非交互式。此外，Nova启发式地将该random oracle实例化为具体的哈希函数，并假设该启发式生成的协议具有knowledge sound。类似的假设也用于[1,2,10]等其它递归系统中。

Committed Relaxed R1CS的非交互式folding scheme定义为：

该定义满足完备性和knowledge soundness属性：

Nova论文中采用了抗碰撞哈希函数。所谓抗碰撞哈希函数是指：

2. Nova证明系统实现预备知识

• cycle of elliptic curves：为减少与group运算相关的约束数，Nova实际实现时使用了满足DLP（discrete log problem）假设的cycle of elliptic curves。Nova实际实现时可采用实现了特定Rust trait（Nova为pasta cycle of two curves实现了相应trait）的任意cycle of elliptic curves。
  将椭圆曲线group表示为${\mathbb{G}}_1,{\mathbb{G}}_2$。将椭圆曲线group $\mathbb{G}$的order $|\mathbb{G}|$称为scalar域$\mathbb{F}$，该曲线基于的域${\mathbb{F}}^{\prime }$称为基域（即point形式为$(x,y)\in {\mathbb{F}}^{\prime }\times {\mathbb{F}}^{\prime }$）。
  cycle of elliptic curves是指：

  • group ${\mathbb{G}}_1$具有scalar域${\mathbb{F}}_1$和base域${\mathbb{F}}_2$。${\mathbb{G}}_2$具有scalar域${\mathbb{F}}_2$和base域${\mathbb{F}}_1$。
  • 对${\mathbb{G}}_1$的group运算，可高效表示为基于其base域${\mathbb{F}}_2$的约束。
  • 对${\mathbb{G}}_2$的group运算，可高效表示为基于其base域${\mathbb{F}}_1$的约束。
  • 基于${\mathbb{F}}_1$向量的vector commitment对应的承诺值空间为group ${\mathbb{G}}_1$。
  • 基于${\mathbb{F}}_2$向量的vector commitment对应的承诺值空间为group ${\mathbb{G}}_2$。

  定义ring $R:={\mathbb{F}}_1\times {\mathbb{F}}_2$为一组tuples，其中一个元素在${\mathbb{F}}_1$，另一个在${\mathbb{F}}_1$。域运算对应为每个元素的域运算。
  同理定义group $\mathbb{G}:={\mathbb{G}}_1\times {\mathbb{G}}_2$为一组tuples，其中一个元素在${\mathbb{G}}_1$，另一个在${\mathbb{G}}_1$。group运算对应为每个元素的group运算。

• commitments承诺值：Nova的folding流程中，要求（基于域$\mathbb{F}$的）向量承诺方案具有加法同态属性。在Nova论文中采用了Pedersen向量承诺方案，对应满足DLG假设的order为$|\mathbb{F}|$的group $\mathbb{G}$。不过在Nova代码实现中支持具有加法同态属性的通用承诺方案，可对向量采用不同的承诺方案，不过本文重点关注Pedersen向量承诺方案。
  对ring $R:={\mathbb{F}}_1\times {\mathbb{F}}_2$的承诺由 “基于${\mathbb{F}}_1$向量的Pedersen vector commitment对应的承诺值空间group ${\mathbb{G}}_1$” 和 “基于${\mathbb{F}}_2$向量的Pedersen vector commitment对应的承诺值空间group ${\mathbb{G}}_2$” 组成。对于某向量$x\in R^n$，分别以$x^{(1)}\in {\mathbb{F}}_1^n$ 和 $x^{(2)}\in {\mathbb{F}}_2^n$来表示其左右侧向量。对$x$的承诺对应为：对$x^{(1)}\in {\mathbb{F}}_1^n$的承诺 和 对$x^{(2)}\in {\mathbb{F}}_2^n$的承诺。即，对向量$x\in R^n$的承诺值为group $\mathbb{G}:={\mathbb{G}}_1\times {\mathbb{G}}_2$内元素。

• committed relaxed instance：有2个分别基于${\mathbb{F}}_1和{\mathbb{F}}_2$的R1CS约束系统：
  ${\text{R1CS}}^{(1)}:=(A_1,B_1,C_1\in {\mathbb{F}}_1^{n_1\times m_1})$ 和 ${\text{R1CS}}^{(2)}:=(A_2,B_2,C_2\in {\mathbb{F}}_2^{n_2\times m_2})$
  对${\text{R1CS}}^{(1)}$的committed relaxed instance为tuple：
  ${\mathbb{U}}^{(1)}:=({\bar{E}}^{(1)},s^{(1)},{\bar{W}}^{(1)},x^{(1)})$，其中${\bar{E}}^{(1)},{\bar{W}}^{(1)}\in {\mathbb{G}}_1,s^{(1)}\in {\mathbb{F}}_1,x^{(1)}\in {\mathbb{F}}^{l_1}$
  相应的relaxed witness $\mathbb{W}=(E^{(1)},W^{(1)})$具有error向量$E^{(1)}\in {\mathbb{F}}_1^{n_1}$ 和 extended witness $W^{(1)}\in {\mathbb{F}}^{m_1-l_1-1}$。
  对称地，对${\text{R1CS}}^{(2)}$的committed relaxed instance为tuple：
  ${\mathbb{U}}^{(2)}:=({\bar{E}}^{(2)},s^{(2)},{\bar{W}}^{(2)},x^{(2)})$，其中${\bar{E}}^{(2)},{\bar{W}}^{(2)}\in {\mathbb{G}}_2,s^{(2)}\in {\mathbb{F}}_2,x^{(2)}\in {\mathbb{F}}^{l_2}$
  相应的relaxed witness $\mathbb{W}=(E^{(2)},W^{(2)})$具有error向量$E^{(2)}\in {\mathbb{F}}_2^{n_2}$ 和 extended witness $W^{(2)}\in {\mathbb{F}}^{m_2-l_2-1}$。
  可将基于${\mathbb{F}}_1$的${\text{R1CS}}^{(1)}$约束系统 和 基于${\mathbb{F}}_2$的${\text{R1CS}}^{(2)}$约束系统 看成是 基于$R:={\mathbb{F}}_1\times {\mathbb{F}}_2$的单个约束系统$\text{R1CS}:=(A,B,C\in R^{n\times m})$。${\text{R1CS}}^{(1)}$ 和 ${\text{R1CS}}^{(2)}$分别对应$\text{R1CS}$的左右侧，二者可具有不同的dimension（即可以$n_1\ne n_2,m_1\ne m_2$），然后取$m=\max (m_1,m_2),n=\max (n_1,n_2),l=\max (l_1,l_2)$，对其填充dummy行列以具有相同的dimension。同理，instance-witness pair $({\mathbb{U}}^{(1)},{\mathbb{W}}^{(1)}),({\mathbb{U}}^{(2)},{\mathbb{W}}^{(2)})$ 对应为 $\text{R1CS}$的instance-witness pair $(\mathbb{U},\mathbb{W})$的左右侧。

• 哈希函数：哈希函数 $H_1:{\mathbb{F}}_1^{\ast }\to {\mathbb{F}}_1$ 和 $H_2:{\mathbb{F}}_2^{\ast }\to {\mathbb{F}}_2$ 为抗碰撞哈希函数，其输入为任意数量的域元素，输出为编码了其哈希值的单个域元素。在Nova中，编码了哈希值的单个域元素对应为某scalar值，该scalar值以二进制表示最多有250位长。不过该输出哈希值在${\mathbb{F}}_1,{\mathbb{F}}_2$这2个域都有唯一表示，这2个域内元素均为256位。【哈希摘要的长度可配置，不过当前选择的摘要长度为250位，以支持一些流行curve cycles，如：secp/secq、pallas/vesta（pasta curves）、BN254/Grumpkin。】
  定义$h_1:=H_1(\cdots )$为$H_1$对任意输入元素$(\cdots )\in {\mathbb{F}}_1^{\ast }$的输出。该哈希值可表示为$h_1={\sum }_{i\le 250}{b}_i^{(1)}\cdot (2^{(1)}{)}^i$，其中$2^{(1)}\in {\mathbb{F}}_1$，并对所有的$i\le 250$，$b_i^{(1)}\in {\mathbb{F}}_1$均为bits in { 0 , 1 } \{0,1\} {0,1}。域${\mathbb{F}}_1$内的哈希输出$h_1={\sum }_{i\le 250}{b}_i^{(1)}\cdot (2^{(1)}{)}^i$ 可表示为 域${\mathbb{F}}_2$内的某元素$h_1^{\prime }$。定义$h_1^{\prime }={\sum }_{i\le 250}{b}_i^{(2)}\cdot (2^{(2)}{)}^i$，其中对于所有$i\le 250$，bit $b_i^{(2)}\in {\mathbb{F}}_2$ 与 bit $b_i^{(1)}\in {\mathbb{F}}_1$ 完全相同（即若$b_i^{(1)}=1^{(1)}$，则定义$b_i^{(2)}=1^{(2)}$，反之则定义$b_i^{(2)}=0^{(2)}$）。同理对于域${\mathbb{F}}_2$内的哈希输出$h_2={\sum }_{i\le 250}{b}_i^{(2)}\cdot (2^{(2)}{)}^i$ 也可用相同方式表示为域${\mathbb{F}}_1$内的某元素$h_2^{\prime }$。
  抗碰撞哈希函数 H : { 0 , 1 } ∗ → { 0 , 1 } λ H: \{0,1\}^*\rightarrow \{0,1\}^{\lambda} H:{0,1}∗→{0,1}λ的输出哈希值可在2个域中唯一表示。为便于表示，忽略了$H$的参数。在Nova代码实现中：

  • 对$H_1$和$H_2$均使用了Poseidon哈希函数。
  • 对$H$采用了SHA-3函数。

2.1 基于cycle of curves的folding方案

在Nova论文中，通过对交互式folding方案 应用 Fiat-Shamir transform构建了random oracle model，从而实现了非交互式folding方案。通过使用合适的密码学哈希函数来实例化random oracle，可启发式地获得plain model下的非交互式folding方案。Nova论文中局限为基于单个域$\mathbb{F}$、承诺值属于某（scalar域为$\mathbb{F}）group $\mathbb{G}$的R1CS约束系统$\text{R1CS}$。

本文将R1CS约束系统$\text{R1CS}$ 扩展为基于ring $R:={\mathbb{F}}_1\times {\mathbb{F}}_2$，包含：

• 针对 基于域${\mathbb{F}}_1$的R1CS约束系统${\text{R1CS}}^{(1)}$的folding方案。
• 针对 基于域${\mathbb{F}}_2$的R1CS约束系统${\text{R1CS}}^{(2)}$的folding方案。

相应地：

• 当fold committed relaxed instances for ${\text{R1CS}}^{(1)}$时，暗示着对基于域${\mathbb{F}}_1$的系统运行folding方案。
• 当fold committed relaxed instances for ${\text{R1CS}}^{(2)}$时，暗示着对基于域${\mathbb{F}}_2$的系统运行folding方案。

但是，在这2个folding方案中调用random oracles时，需输入verification key $\text{vk}$作为参数，其中 $\text{vk}$参数派生自这2个系统。相应的folding setup和folding keygen定义如下：

Nova的folding scheme通过Fiat-Shamir transform，由交互式协议变为非交互式协议。因此对random oracle的queries中必须包含整个环境的描述。具体为，令$H$为合适的密码学哈希函数，可启发式实例化一个random oracle，$H$的输出可在两个域内唯一表示。如上面公式（1）所示，verification key $\text{vk}$元素表示的是该环境的哈希摘要。因这些摘要元素可看成是交互式协议中folding verifier的输入，为保留Fiat-Shamir transform的soundness，需强调：${\text{Fold}}_{\mathcal{V}}$中以$\text{vk}$、𝕦$、\mathbb{U}、\bar{T}$元素用作其random oracle的参数。

3. Nova中所使用的增强约束系统

Nova IVC方案基于一组函数$F_1,F_2$操作，每个函数对应一个域。可将Nova看成是combined函数$F:({\mathbb{F}}_1^{a_1}\times {\mathbb{F}}_2^{a_2})\times ({\mathbb{F}}_1^{b_1}\times {\mathbb{F}}_2^{b_2})\to ({\mathbb{F}}_1^{a_1}\times {\mathbb{F}}_2^{a_2})$的IVC方案：
$((z^{(1)},z^{(2)}),({\text{aux}}^{(1)},{\text{aux}}^{(2)}))\stackrel{F}{\to }(F_1(z^{(1)},{\text{aux}}^{(1)}),F_2(z^{(2)},{\text{aux}}^{(2)}))$
其中：

• $F_1:{\mathbb{F}}_1^{a_1}\times {\mathbb{F}}_1^{b_1}\to {\mathbb{F}}_1^{a_1}$为基于${\mathbb{F}}_1$的poly-size算术电路。
• $F_2:{\mathbb{F}}_2^{a_2}\times {\mathbb{F}}_2^{b_2}\to {\mathbb{F}}_2^{a_2}$为基于${\mathbb{F}}_2$的poly-size算术电路。

Nova IVC方案旨在证明$(z_i^{(1)},z_i^{(2)})$为：

• 基于初始输入$(z_0^{(1)},z_0^{(2)})$和某些辅助输入，迭代调用函数$F=(F_1,F_2)$ 共 $i$ 次的结果。

每次迭代，IVC使用2个R1CS约束系统（一个基于域${\mathbb{F}}_1$，另一个基于域${\mathbb{F}}_2$），来验证函数$F_1$和$F_2$在该轮迭代时计算正确。但是，Nova将这些核心约束系统做了增强——额外引入了2个增强约束系统来：

• 验证在每次迭代时folding是正确完成的。
• 之前迭代的输出正确forward到当前迭代。

3.1 增强约束系统

Nova中定义了2个分别基于域${\mathbb{F}}_1$和${\mathbb{F}}_2$的增强约束系统${\text{R1CS}}^{(1)}$和${\text{R1CS}}^{(2)}$。如上一章所示，${\mathbb{G}}_1$的group运算可高效表示为base域${\mathbb{F}}_2$的约束。由于folding操作中需要 ${\mathbb{G}}_1$的group运算，Nova代码实现时，会在${\text{R1CS}}^{(2)}$约束中 将${\text{R1CS}}^{(1)}$的committed instance 𝕦${}^{(1)}$、${\mathbb{U}}^{(1)}$进行folding；同理也会在${\text{R1CS}}^{(1)}$约束中 将${\text{R1CS}}^{(2)}$的committed instance 𝕦${}^{(2)}$、${\mathbb{U}}^{(2)}$进行folding。

增强约束系统${\text{R1CS}}^{(1)}$和${\text{R1CS}}^{(2)}$的定义为：

• ${\text{R1CS}}^{(1)}$对应为下图relation ${\mathcal{R}}_1$的R1CS约束系统：
  
• ${\text{R1CS}}^{(2)}$对应为下图relation ${\mathcal{R}}_2$的R1CS约束系统：
  

${\text{R1CS}}^{(1)}$和${\text{R1CS}}^{(2)}$约束系统的每一步，会：

• 执行函数：$z_{i+1}:=F(z_i,{\text{aux}}_i)$。
• 为对方约束系统，将之前的committed instance 𝕦 fold into a running committed instance $\mathbb{U}$。
• 维护原始输入$z_0$。
• 更新迭代索引$i$。

3.2 其它说明

• 非原生域元素和域运算的表示：
  对2个committed instances 𝕦${}^{(1)}$、${\mathbb{U}}^{(1)}$ folding过程中不仅需要基于${\mathbb{G}}_1$的group运算，还需要基于${\mathbb{F}}_1$的域运算。
  但是，基于${\mathbb{F}}_2$的R1CS约束系统${\text{R1CS}}^{(2)}$需将这些folding运算 编码为 基于${\mathbb{F}}_2$的约束。为此，${\mathbb{F}}_1$域元素被编码为合适的${\mathbb{F}}_2$元素，使得非原生域运算可表示为${\mathbb{F}}_2$约束。
  对${\text{R1CS}}^{(1)}$采用相同的策略。

• 哈希参数：
  对$H_1,H_2$的哈希参数$p{p}_{H_1},p{p}_{H_2}$被硬编码在相应的约束系统中。为便于标记，在本论文中忽略了这些参数，但在IVC Setup中暗含了以相应参数调用该哈希函数。

• 对称性：若忽略base case约束，${\text{R1CS}}^{(1)}$和${\text{R1CS}}^{(2)}$为对称约束系统。 𝕦${}_i^{(1)}$ VS. 𝕦${}_{i+1}^{(2)}$ 的索引号的差异，并不影响这种对称性。
  此外，需强调：
  如上一章所属，哈希值在两个域均具有唯一表示，因此对 𝕦${}_{i+1}^{(1)}.x_0$ 和 𝕦${}_{i+1}^{(2)}.x_0$的唯一约束为：

  • 𝕦${}_{i+1}^{(1)}.x_0$=𝕦${}_i^{(2)}.x_1$
  • 𝕦${}_{i+1}^{(2)}.x_0$=𝕦${}_{i+1}^{(1)}.x_1$

  这种equality，可通过copy constraints来将这些哈希值传递作为对方instance的public IO。详细将本论文5.3节。

4. 修订版Nova IVC方案

之前的two-cycle of curves Nova证明系统实现存在漏洞，相应的修改在本文以红色标识了。
整个算法的安全性证明见《Revisiting the Nova Proof System on a Cycle of Curves》第6章”Proof of security“。

4.1 Nova Setup算法

Nova Setup算法中，输入有：

• security参数$1^{\lambda }$
• poly-size bound $n\in \mathbb{N}$

输出为：

• $pp\leftarrow {\text{Fold}}_{\text{Setup}}(1^{\lambda },n)$

4.2 修订版Nova Verifier算法

Nova Verifier $\mathcal{V}$的输入有：

• IVC公共参数$pp$
• 函数描述：$F_1:{\mathbb{F}}_1^{a_1}\times {\mathbb{F}}_1^{b_1}\to {\mathbb{F}}_1^{a_1}$ 和 $F_2:{\mathbb{F}}_2^{a_2}\times {\mathbb{F}}_2^{b_2}\to {\mathbb{F}}_2^{a_2}$。
• 索引号 $i\in \mathbb{N}$。
• 起始值$z_0^{(1)}\in {\mathbb{F}}_1^{a_1}$和$z_0^{(2)}\in {\mathbb{F}}_2^{a_2}$
• 第$i$次迭代的IVC proof：${\pi }_i=(($𝕦${}_i^{(2)},$𝕨${}_i^{(2)}),({\mathbb{U}}_i^{(1)},{\mathbb{W}}_i^{(1)}),({\mathbb{U}}_i^{(2)},{\mathbb{W}}_i^{(2)}))$

Verifier $\mathcal{V}$首先会运行如下初始流程，可将其看成是预处理阶段：

• 1）已知函数$F_1,F_2$，确定性的生成 实现relation ${\mathcal{R}}_1$ 和 ${\mathcal{R}}_2$的增强约束系统${\text{R1CS}}^{(1)}$和${\text{R1CS}}^{(2)}$
• 2）计算folding verification key：
  $(\cdot ,\text{vk})\leftarrow {\text{Fold}}_{\mathcal{K}}(pp,\text{R1CS}:=({\text{R1CS}}^{(1)},{\text{R1CS}}^{(2)}))$

当满足以下6个条件时，Verifier验证通过：

• 1）索引值$i$必须大于0；
• 2）𝕦${}_i^{(2)}.x_0=H_1(\text{vk},i^{(1)},z_0^{(1)},z_i^{(1)},{\mathbb{U}}_i^{(2)})$
• 3）𝕦${}_i^{(2)}.x_1=H_2(\text{vk},i^{(2)},z_0^{(2)},z_i^{(2)},{\mathbb{U}}_i^{(1)})$
• 4）$({\mathbb{U}}_i^{(1)},{\mathbb{W}}_i^{(1)})$ pair 满足${\text{R1CS}}^{(1)}$
• 5）$({\mathbb{U}}_i^{(2)},{\mathbb{W}}_i^{(2)})$ pair 满足${\text{R1CS}}^{(2)}$
• 6）$($𝕦${}_i^{(2)},$𝕨${}_i^{(2)})$ pair 严格 满足${\text{R1CS}}^{(2)}$

4.3 修订版Nova Prover算法

修订版Nova Prover算法分为三大块：

• 1）初始流程
• 2）base case step：即针对$i=0$的情况
• 3）recursive step（即non-base case）：即针对$i\ge 1$的情况。

4.3.1 修订版Nova Prover算法——初始流程

Prover $\mathcal{P}$的初始流程 与 Verifier $\mathcal{V}$的初始流程相同：

• 1）已知函数$F_1,F_2$，确定性的生成 实现relation ${\mathcal{R}}_1$ 和 ${\mathcal{R}}_2$的增强约束系统${\text{R1CS}}^{(1)}$和${\text{R1CS}}^{(2)}$
• 2）计算folding verification key：
  $(\text{pk},\text{vk})\leftarrow {\text{Fold}}_{\mathcal{K}}(pp,\text{R1CS}:=({\text{R1CS}}^{(1)},{\text{R1CS}}^{(2)}))$

4.3.2 修订版Nova Prover算法——base case step

base case step，即针对$i=0$的情况，构建首次调用$F$后的状态——即相当于证明$z_1=F(z_0,{\text{aux}}_0)$。
Prover $\mathcal{P}$在base case step，输入有：

• IVC公共参数$pp$
• 函数描述：$F_1:{\mathbb{F}}_1^{a_1}\times {\mathbb{F}}_1^{b_1}\to {\mathbb{F}}_1^{a_1}$ 和 $F_2:{\mathbb{F}}_2^{a_2}\times {\mathbb{F}}_2^{b_2}\to {\mathbb{F}}_2^{a_2}$。
• 起始值$z_0^{(1)}\in {\mathbb{F}}_1^{a_1}$和$z_0^{(2)}\in {\mathbb{F}}_2^{a_2}$
• 辅助输入${\text{aux}}_0^{(1)}\in {\mathbb{F}}_1^{b_1}$ 和 ${\text{aux}}_0^{(2)}\in {\mathbb{F}}_2^{b_2}$

Prover $\mathcal{P}$在base case step主要执行3大步骤：

• 1）为${\text{R1CS}}^{(1)}$计算新committed pair $($𝕦${}_1^{(1)},$𝕨${}_1^{(1)})$
• 2）为${\text{R1CS}}^{(2)}$计算新committed pair $($𝕦${}_1^{(2)},$𝕨${}_1^{(2)})$
• 3）输出Prover State：为step 1输出IVC proof。

Prover $\mathcal{P}$在base case step的详细流程为：

• 1）为${\text{R1CS}}^{(1)}$计算新committed pair $($𝕦${}_1^{(1)},$𝕨${}_1^{(1)})$

  • 1.1）定义初始dummy instance 𝕦${}_0^{(2)}:=({\bar{0}}^{(2)},1^{(2)},{\bar{0}}^{(2)},x:=(x_0,x_1))$，其中：【即$i=0$的情况】
    $x_0=H_1(\text{vk},0^{(1)},z_0^{(1)},z_0^{(1)},{\mathbb{U}}_{\perp }^{(2)})$
    $x_1=H_2(\text{vk},0^{(2)},z_0^{(2)},z_0^{(2)},{\mathbb{U}}_{\perp }^{(1)})$
    该dummy instance不会与任何running instance fold。
  • 1.2）定义${\hat{w}}_1^{(1)}=(\text{vk},0^{(1)},z_0^{(1)},z_0^{(1)},{\text{aux}}_0^{(1)},{\mathbb{U}}_{\perp }^{(2)},$𝕦${}_0^{(2)},{\bar{0}}^{(2)})$为relation ${\mathcal{R}}_1$的witness。然后基于${\hat{w}}_1^{(1)}$，计算满足${\text{R1CS}}^{(1)}$约束系统所需的extended witness $w_1^{(1)}$。
  • 1.3）对extended witness $w_1^{(1)}$进行commit，有：${\bar{w}}_1^{(1)}\leftarrow \text{Commit}(p{p}_W^{(1)},w_1^{(1)})$。
  • 1.4）定义${\mathbb{U}}_1^{(2)}:={\mathbb{U}}_{\perp }^{(2)},{\mathbb{W}}_1^{(2)}:={\mathbb{W}}_{\perp }^{(2)}$。
  • 1.5）定义$x_0:=$𝕦${}_0^{(2)}.x_1$，并计算$x_1:=H_1(\text{vk},1^{(1)},z_0^{(1)},z_1^{(1)}:=F_1(z_0^{(1)},{\text{aux}}_0^{(1)}),{\mathbb{U}}_1^{(2)})$。
  • 1.6）设置 𝕦${}_1^{(1)}:=({\bar{0}}^{(1)},1^{(1)},{\bar{w}}_1^{(1)},x:=(x_0,x_1))$，𝕨${}_1^{(1)}:=({\vec{0}}^{(1)},w_1^{(1)})$。

• 2）为${\text{R1CS}}^{(2)}$计算新committed pair $($𝕦${}_1^{(2)},$𝕨${}_1^{(2)})$

  • 2.1）定义${\hat{w}}_1^{(2)}=(\text{vk},0^{(2)},z_0^{(2)},z_0^{(2)},{\text{aux}}_0^{(2)},{\mathbb{U}}_{\perp }^{(1)},$𝕦${}_1^{(1)},{\bar{0}}^{(1)})$为relation ${\mathcal{R}}_2$的witness。然后基于${\hat{w}}_1^{(2)}$，计算满足${\text{R1CS}}^{(2)}$约束系统所需的extended witness $w_1^{(2)}$。
  • 2.2）对extended witness $w_1^{(2)}$进行commit，有：${\bar{w}}_1^{(2)}\leftarrow \text{Commit}(p{p}_W^{(2)},w_1^{(2)})$。
  • 2.3）定义${\mathbb{U}}_1^{(1)}:=$𝕦${}_1^{(1)},{\mathbb{W}}_1^{(1)}:=$𝕨${}_1^{(1)}$。
  • 2.4）定义$x_0:=$𝕦${}_1^{(1)}.x_1$，并计算$x_1:=H_2(\text{vk},1^{(2)},z_0^{(2)},z_1^{(2)}:=F_2(z_0^{(2)},{\text{aux}}_0^{(2)}),{\mathbb{U}}_1^{(1)})$。
  • 2.5）设置 𝕦${}_1^{(2)}:=({\bar{0}}^{(2)},1^{(2)},{\bar{w}}_1^{(2)},x:=(x_0,x_1))$，𝕨${}_1^{(2)}:=({\vec{0}}^{(2)},w_1^{(2)})$。

• 3）输出Prover State：为step 1输出IVC proof为：
  ${\pi }_1:=(($𝕦${}_1^{(2)},$𝕨${}_1^{(2)}),({\mathbb{U}}_1^{(1)},{\mathbb{W}}_1^{(1)}),({\mathbb{U}}_1^{(2)},{\mathbb{W}}_1^{(2)}))$
  以及新的evaluation值：$z_1^{(1)}:=F_1(z_0^{(1)},{\text{aux}}_0^{(1)})$ 以及 $z_1^{(2)}:=F_2(z_0^{(2)},{\text{aux}}_0^{(2)})$
  这些输出就足以供Nova prover执行another step for Iteration 1。

4.3.3 修订版Nova Prover算法——recursive step（即non-base case）

即针对$i\ge 1$的情况。迭代过程是指重复调用本小节算法。

Prover $\mathcal{P}$在recursive step（即non-base case），输入有：

• IVC公共参数$pp$
• 约束系统${\text{R1CS}}^{(1)}$和${\text{R1CS}}^{(2)}$
• 索引值$i\in \mathbb{N}$，其中$i\ge 1$
• 起始值$z_0^{(1)}\in {\mathbb{F}}_1^{a_1}$和$z_0^{(2)}\in {\mathbb{F}}_2^{a_2}$
• evaluation值$z_i^{(1)}\in {\mathbb{F}}_1^{a_1}$和$z_i^{(2)}\in {\mathbb{F}}_2^{a_2}$
• 辅助输入${\text{aux}}_0^{(1)}\in {\mathbb{F}}_1^{b_1}$ 和 ${\text{aux}}_0^{(2)}\in {\mathbb{F}}_2^{b_2}$
• 对 Iteration $i$ 的IVC Proof：${\pi }_i=(($𝕦${}_i^{(2)},$𝕨${}_i^{(2)}),({\mathbb{U}}_i^{(1)},{\mathbb{W}}_i^{(1)}),({\mathbb{U}}_i^{(2)},{\mathbb{W}}_i^{(2)}))$

如上图所示，Prover $\mathcal{P}$在recursive step（即non-base case），针对$i\ge 1$情况，主要有5个step，其中“step(1)+(2) 与 “step(3)+(4)” 在每次迭代时会重复调用，而step(5)仅在达到目标迭代次数，确定要输出最终的IVC proof时才执行：

• 1）step(1)：为${\text{R1CS}}^{(2)}$ fold pair，计算新的committed relaxed instance-witness pair $({\mathbb{U}}_{i+1}^{(2)},{\mathbb{W}}_{i+1}^{(2)})$。
• 2）step(2)：为${\text{R1CS}}^{(1)}$计算新的committed relaxed instance-witness pair $($𝕦${}_{i+1}^{(1)},$𝕨${}_{i+1}^{(1)})$。
• 3）step(3)：为${\text{R1CS}}^{(1)}$ fold pair，计算新的committed relaxed instance-witness pair $({\mathbb{U}}_{i+1}^{(1)},{\mathbb{W}}_{i+1}^{(1)})$。
• 4）step(4)：为${\text{R1CS}}^{(2)}$计算新的committed relaxed instance-witness pair $($𝕦${}_{i+1}^{(2)},$𝕨${}_{i+1}^{(2)})$。
• 5）step(5)：输出Prover State：为step $i+1$ 输出IVC proof。

Prover $\mathcal{P}$在recursive step（即non-base case）的具体步骤为：

• 1）step(1)：为${\text{R1CS}}^{(2)}$ fold committed pairs $($𝕦${}_i^{(2)},$𝕨${}_i^{(2)})$ 和 $({\mathbb{U}}_i^{(2)},{\mathbb{W}}_i^{(2)})$：
  ${\text{Fold}}_{\mathcal{P}}(\text{pk},($𝕦${}_i^{(2)},$𝕨${}_i^{(2)}),({\mathbb{U}}_i^{(2)},{\mathbb{W}}_i^{(2)}))\to ({\bar{T}}_i^{(2)},({\mathbb{U}}_{i+1}^{(2)},{\mathbb{W}}_{i+1}^{(2)}))$
  获得folding proof ${\bar{T}}_i^{(2)}$ 以及 新的committed relaxed instance-witness pair $({\mathbb{U}}_{i+1}^{(2)},{\mathbb{W}}_{i+1}^{(2)})$。

• 2）step(2)：为${\text{R1CS}}^{(1)}$计算新的committed relaxed instance-witness pair $($𝕦${}_{i+1}^{(1)},$𝕨${}_{i+1}^{(1)})$：

  • 2.1）定义${\hat{w}}_{i+1}^{(1)}=(\text{vk},i^{(1)},z_0^{(1)},z_i^{(1)},{\text{aux}}_i^{(1)},{\mathbb{U}}_i^{(2)},$𝕦${}_i^{(2)},{\bar{T}}_i^{(2)})$为relation ${\mathcal{R}}_1$的witness。然后基于${\hat{w}}_{i+1}^{(1)}$，计算满足${\text{R1CS}}^{(1)}$约束系统所需的extended witness $w_{i+1}^{(1)}$。
  • 2.2）对extended witness $w_{i+1}^{(1)}$进行commit，有：${\bar{w}}_{i+1}^{(1)}\leftarrow \text{Commit}(p{p}_W^{(1)},w_{i+1}^{(1)})$。
  • 2.3）定义$x_0:=$𝕦${}_i^{(2)}.x_1$，并计算$x_1:=H_1(\text{vk},{i+1}^{(1)},z_0^{(1)},z_{i+1}^{(1)}:=F_1(z_i^{(1)},{\text{aux}}_i^{(1)}),{\mathbb{U}}_{i+1}^{(2)})$。
  • 2.4）设置 𝕦${}_{i+1}^{(1)}:=({\bar{0}}^{(1)},1^{(1)},{\bar{w}}_{i+1}^{(1)},x:=(x_0,x_1))$，𝕨${}_{i+1}^{(1)}:=({\vec{0}}^{(1)},w_{i+1}^{(1)})$。

• 3）step(3)：为${\text{R1CS}}^{(1)}$ fold 新计算的 $($𝕦${}_{i+1}^{(1)},$𝕨${}_{i+1}^{(1)})$ pair 和 $({\mathbb{U}}_i^{(1)},{\mathbb{W}}_i^{(1)})$ pair：
  ${\text{Fold}}_{\mathcal{P}}(\text{pk},($𝕦${}_{i+1}^{(1)},$𝕨${}_{i+1}^{(1)}),({\mathbb{U}}_i^{(1)},{\mathbb{W}}_i^{(1)}))\to ({\bar{T}}_i^{(1)},({\mathbb{U}}_{i+1}^{(1)},{\mathbb{W}}_{i+1}^{(1)}))$
  获得folding proof ${\bar{T}}_i^{(1)}$ 以及 新的committed relaxed instance-witness pair $({\mathbb{U}}_{i+1}^{(1)},{\mathbb{W}}_{i+1}^{(1)})$。

• 4）step(4)：为${\text{R1CS}}^{(2)}$计算新的committed relaxed instance-witness pair $($𝕦${}_{i+1}^{(2)},$𝕨${}_{i+1}^{(2)})$：

  • 4.1）定义${\hat{w}}_{i+1}^{(2)}=(\text{vk},i^{(2)},z_0^{(2)},z_i^{(2)},{\text{aux}}_i^{(2)},{\mathbb{U}}_i^{(1)},$𝕦${}_i^{(1)},{\bar{T}}_i^{(1)})$为relation ${\mathcal{R}}_2$的witness。然后基于${\hat{w}}_{i+1}^{(2)}$，计算满足${\text{R1CS}}^{(1)}$约束系统所需的extended witness $w_{i+1}^{(2)}$。
  • 4.2）对extended witness $w_{i+1}^{(2)}$进行commit，有：${\bar{w}}_{i+1}^{(2)}\leftarrow \text{Commit}(p{p}_W^{(2)},w_{i+1}^{(2)})$。
  • 4.3）定义$x_0:=$𝕦${}_{i+i}^{(1)}.x_1$，并计算$x_1:=H_2(\text{vk},{i+1}^{(2)},z_0^{(2)},z_{i+1}^{(2)}:=F_2(z_i^{(2)},{\text{aux}}_i^{(2)}),{\mathbb{U}}_{i+1}^{(1)})$。
  • 4.4）设置 𝕦${}_{i+1}^{(2)}:=({\bar{0}}^{(2)},1^{(2)},{\bar{w}}_{i+1}^{(2)},x:=(x_0,x_1))$，𝕨${}_{i+1}^{(2)}:=({\vec{0}}^{(1)},w_{i+1}^{(2)})$。

• 5）step(5)：输出Prover State：为step $i+1$ 输出IVC proof：
  ${\pi }_{i+1}=(($𝕦${}_{i+1}^{(2)},$𝕨${}_{i+1}^{(2)}),({\mathbb{U}}_{i+1}^{(1)},{\mathbb{W}}_{i+1}^{(1)}),({\mathbb{U}}_{i+1}^{(2)},{\mathbb{W}}_{i+1}^{(2)}))$

  以及新的evaluation值：$z_{i+1}^{(1)}:=F_1(z_i^{(1)},{\text{aux}}_i^{(1)})$ 以及 $z_{i+1}^{(2)}:=F_2(z_i^{(2)},{\text{aux}}_i^{(2)})$
  这些输出就足以供Nova prover执行another step for Iteration $i+1$。

Nova系列博客

• Nova: Recursive Zero-Knowledge Arguments from Folding Schemes学习笔记
• Nova 和 SuperNova：无需通用电路的通用机器执行证明系统
• Sangria：类似Nova folding scheme的relaxed PLONK for PLONK
• 基于Nova/SuperNova的zkVM
• SuperNova：为多指令虚拟机执行提供递归证明
• Lurk——Recursive zk-SNARKs编程语言
• Research Day 2023：Succinct ZKP最新进展
• 2023年 ZK Hack以及ZK Summit 亮点记