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\times\{0,1\}^b\rightarrow\{0,1\}^a$ ，有公开值 $z_0,z_i\in\{0,1\}^a$ ，IVC方案是指Prover $\mathcal{P}$ 声称其知道辅助值 $\text{aux}_0,\cdots,\text{aux}_{i-1}\in \{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_1b_1,a_2b_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}'$ 称为基域（即point形式为 $(x,y)\in \mathbb{F}'\times \mathbb{F}'$ ）。
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$ 的约束。