为什么零知识证明的 Nova 算法具备潜力？‍‍‍‍‍‍

1. Nova 论文：
   https://eprint.iacr.org/2021/370.pdf
2. Nova 潜在攻击和相应修正：
   https://eprint.iacr.org/2023/969.pdf
3. Nova 潜在攻击的理解总结：
   https://www.zksecurity.xyz/blog/posts/nova-attack/

Nova 算法是一种针对 IVC（增量可验证计算，Incrementally Verifiable Computation）的新型的零知识证明算法。IVC，即同一个函数把前一个输出作为下一个输入迭代计算。F 函数的迭代计算过程如下图：

z0 是最初的输入，通过 F 函数计算生成的结果，作为下一个 F 函数的输入。

松弛 R1CS 以及松弛承诺 R1CS

众所周知，R1CS 是零知识证明技术中电路约束表示形式。松弛 R1CS（Relaxed R1CS) 可以看成是 R1CS 的扩展形式。在 R1CS 的基础上，增加一个标量 u 以及一个错误向量 E。松弛 R1CS 的实例用 (E, u, x) 表示。

松弛承诺 R1CS 在松弛 R1CS 的基础上，将 E 以及 W 向量承诺。松弛承诺 R1CS 的实例用（\bar{E}, u, \bar{W}, x) 表示，其中 x 和 u 是公开变量。

从 R1CS 扩展到松弛 R1CS，是为了折叠方案。注意的是，从松弛 R1CS 的角度看，R1CS 是其的一种特例。也就是说，R1CS 也是一种“特别“的松弛 R1CS。

折叠方案（Folding Scheme）

直觉上来说，一个关系 R 的折叠方案就是将两个符合关系 R 的实例“折叠成”一个新的复合关系 R 的实例。松弛 R1CS/ 松弛承诺 R1CS 就能进行类似的折叠。两者的折叠过程类似。松弛承诺 R1CS 的折叠方案如下：

整个折叠方案由 4 步组成。第一步，证明者 P 发送一个交叉项 T 的承诺\bar{T}给验证者。第二步，验证者发送随机挑战 r 给证明者。第三步是证明者和验证者都需要执行的，承诺的折叠。第四步，证明者独自执行，将两个实例的 E 和 W 向量进行折叠。

增广函数 F'（Argumented Function）

折叠方案，折叠的是松弛 R1CS 实例。那这些松弛 R1CS 实例证明的计算是什么？显然，这些计算要包括折叠的计算。这些计算不仅仅是 IVC 计算中的 F 函数了，也就被称为增广函数 F‘。增广函数 F’的计算主要由两部分组成：

1/ IVC 中的 F 函数

2/ R1CS 实例的折叠计算

理想中的样子

有了上述的这些理解，可以想象出折叠的过程：

其中，circuit 就是增广函数 F’对应的电路。acc{1,2,3,4,5,6}是松弛承诺 R1CS 实例。circuit 有两个计算：1/ 松弛承诺 R1CS 实例的折叠，比如 acc1+acc2->acc3。2/ 计算 F 函数，将状态 state1 变为 state2，再从 state2 变为 state3 等等。

注意的是，增广函数 F’对应的 circuit，本身也是一个 R1CS 实例，其可以表示成松弛 R1CS 实例。也就是图中的 acc4 和 acc6。“summarize”是将松弛 R1CS 实例转换为松弛承诺 R1CS 实例。

仔细观察第二个电路的输入，acc3 是折叠后的松弛承诺 R1CS 实例，acc4 是证明 acc3 是正确折叠结果的松弛承诺 R1CS 实例。这两个实例会进入下一次的折叠，生成 acc5。你可以试想一下，如果 acc3 以及 acc4 是可满足的松弛承诺 R1CS 实例，意味着，acc3 是由两个可满足的松弛承诺 R1CS 实例折叠而来，也就是说，acc1 以及 acc2 是可满足的松弛承诺 R1CS 实例。这样的可靠性也就可以一步步“向”前推导，从而也证明了每一次 circuit 中的 F 函数计算是正确的。总的来说，就是通过某一个 circuit 对应的两个松弛承诺 R1CS 实例的可满足性，可以证明之前所有的 IVC 计算是正确的。

真实的样子

熟悉零知识证明的朋友，都知道多项式承诺方案中经常采用椭圆曲线。scalar 域上对应的多项式的承诺是用椭圆曲线的 base 域表示。R1CS 电路通常是采用 scalar 域来表示。仔细看，上图中的“summarize”的前后涉及到域的转换。也就是，要将 circuit 对应的松弛承诺 R1CS 实例进行折叠的话，必须在另外一个电路中去“折叠”。这时，需要引入椭圆曲线循环，两个或者多个椭圆曲线，其中一个曲线的 scalar 域，和另外一个曲线的 base 域相同，巧的是，该曲线的 scalar 域和之前曲线的 base 域相同。采用这样的椭圆曲线循环，可以将“理想中的样子”实现：

整个折叠过程，拆分成两个电路进行折叠。上部分可以称为 Circuit 1 的折叠，下部分可以称为 Circuit 2 的折叠。两个电路的关系的形式化表示在论文“Nova 潜在攻击和相应修正”的第 8 页。U 表示的是折叠后的实例，u 表示的是一个 R1CS 实例对应的松弛实例。注意的是，Circuit 1 折叠的是 Circuit 2 对应的松弛承诺 R1CS 实例，而 Circuit 2 折叠的才是 Circuit 1 对应的松弛承诺 R1CS 实例。Circuit 2 的主要目的就是折叠 Circuit1 对应的松弛承诺 R1CS 实例，其电路中的函数计算没有意义。相反，F 函数实现在 Circuit 1 中。结合“理想中的样子”，大致可以猜到 U{i+2}^2, u{i+2}^1, u{i+2}^2, U{i+2}^1 可满足性是证明的重要部分。

因为“电路”切割成两部分，并且各自的电路在另外的电路中进行折叠。存在几个实例之间的绑定问题：u 和 U 实例之间的绑定以及 u 实例在两个电路之间传递的绑定。为了解决这些绑定问题，在电路中引入了 x_0/x_1 公开变量，其中 x_1 指定了和 u 实例绑定的电路输出 U 实例和当前的 F 函数的输出（为了简化电路结构，在图中未体现）。你想，在电路中引入了 U 实例的 H_1 结果的话，如果 u 实例是可满足的，x_0/x_1 既是真实可靠的，即和 U 进行了“绑定”。x_0 建立的是输入的 u 和 U 的绑定关系，x_1 建立的是输出的 u 和 U 的绑定关系。

举个例子，u{i+1}^1 作为下半部分电路的输入时，经过 Circuit 2，其输出 u{i+1}^2.x0 = u{i+1}^1.x1，这样，再输入到上半部分电路时，如果 u{i+1}^2 可满足的话，则其的 x_0 应该等于 U_{i+1}^2 的 H1 的结果。这在 Circuit 1 电路中会进行检查。这样，就保证了正确的实例，在两个电路之间传递。

IVC 的证明

为了证明 IVC 在某个迭代正确计算，逻辑上需要证明如下信息：

除了证明四个实例可满足外，还需要证明两个 x1 的绑定关系，示意如下图：

这些信息是否正确，需要额外的证明电路实现。也就是说，IVC 计算的证明是该电路的证明。可想而知，如果是很多次迭代的计算，原本需要将这些迭代一个个地在电路中展开，现在只需要对 4 个电路实例进行可满足性以及绑定关系的验证即可。性能提升非常大。

攻击以及算法修正

看到上面的图，有个直觉，怎么感觉上下电路的实例是“割裂“的，没有什么绑定性。事实上，攻击就是这样构造的。

伪造 U_i^1 和 U{i+1}^2，虽然是伪造的，但是是可满足的实例。伪造 u{i+1}^1，修改 x_0 和 x_1 和伪造的 U 实例对应。显然，u{i+1}^1 实例不满足。虽然它不满足，但是 Circuit 2 的电路还是可以满足的，只是输出 U{i+1}^1 实例不满足而已。成功构造了 u{i+1}^2 的话，Circuit 1 就可以构造出可满足的 u{i+2}^1 以及 U_{i+2}^2，并且满足 x1 的绑定关系。这样就先构造出了最终伪造证明的一半内容。通过对称性，可以构造出下面一半的输出实例。通过两次构造的结果的“拼接”，可以伪造出 IVC 计算的证明。

修正后的检查逻辑如下：

“Nova 潜在攻击和相应修正”论文的第 6 章给出了详细的安全性分析。感兴趣的小伙伴，可以自行查看原论文。

Nova 的基本思想是通过折叠方案折叠电路实例。逻辑比较绕，需要仔细地思考电路折叠过程以及实现电路中的绑定关系。

Nova 具备长期爆发潜力！