Overview

考虑这样一个迭代计算$y=F(F(F(F(F(x)))))$，或者记为$y=F^5(x)$，对应的$x$为输入，$y$为输出，这里的函数$F$可能是非确定性的，此时需要证明存在这样的输入输出对$(x,y)$，满足这个等式

此类迭代计算常见于各类需要验证计算的应用中，比如下列几类

  • VDF：可验证延迟函数，最早由Dan Boneh教授于2018年提出，VDF即便是在使用少量CPU并行计算的情况下，该函数的计算也至少需要花费一段已知的时间
    在VDF中，上述函数$F$为某些延迟函数，比如$MinRoot$
  • Rollups：Rollup中的函数$F$会以Merkle Tree的根和部分交易作为输入，并输出一个更新后的Merkle Tree的根
  • Lurk：Lurk属于一种图灵完备的SNARK后端，Lurk中的函数$F$为程序的执行步

这里考虑迭代计算的一般情况：$y=F^{(n)}(x)$，验证此类迭代计算最朴素的方式是将$n$次迭代丢到一个单独的电路中，之后用SNARK来完成证明

不难看出，$n$次迭代丢到同一个电路中显然是一个不太好的做法，不仅会导致计算开销很大，而且Prover在构造证明的时候需要的内存开销为$\Omega(n\cdot |F|)$，Verifier的验证时间也与迭代次数$n$有关

还有一个最主要的问题：此类方式构造的证明不是增量可更新的，这意味着Prover构造了一个$n$次迭代的证明，如果说Prover后续希望构造一个$n+1$次迭代的证明，那么按照这个朴素的方法，则需要重新执行证明生成的所有步骤，时间和计算开销都很大

于是$[Val08,BCTV14]$引入了增量可验证计算的概念（Incrementally Verfiable Computation，IVC）

简单来说就是上面这个图，每次需要迭代计算$F$时都会生成一个证明

既然朴素的方法在不好处理IVC，那用一些现有的SNARK方案来处理IVC会如何呢

  • Pinocchio，Groth16：需要对配对友好的曲线（从而降低效率），需要可信设置，且Prover每一步都需要执行一个SNARK，Verifier在每一步都必须验证Prover的SNARK
  • $[Set19]$：此类方案无需可信设置，只需要基于DLOG假设的曲线即可，但是还是存在与Pinocchio和Groth16的第二个缺点
  • Halo$[BGH19]$：需要对FFT友好的基于DLOG的曲线，尽管无需可信设置，但是Prover仍然需要在每一步执行一个SNARK，不过Verifier只需要验证每一步中SNARK的一部分即可

不难看出，现有的SNARK方案都有不同的缺点，主要是Prover需要在每一步都执行一个SNARK

为了解决这些问题，Nova给出了解决方案，Nova采用了$[BCLMS21]$中的拆分累加（Split Accumulation）的概念，可以在任意基于DLOG假设的曲线上构建，无需可信设置，Prover在每一步中只需要对witness和相关的辅助向量进行承诺，Verifier验证时也只需要计算承诺的某个线性组合即可，因此Nova在处理IVC时更直接，更高效

当然Nova也有自己的缺点，如果Nova想要实现压缩证明，则需要其他证明系统来辅助（压缩后的证明不再是增量可验证的）

Floding Scheme for NP

NP问题的折叠证明？不知道是不是这个意思

考虑这样一个场景，Prover和Verifier基于两个NP实例$U_1,U_2$进行证明，利用Prover的相关提示，Verifier希望输出一个$U$，满足

  • 当且仅当$U_1,U_2$均是可满足时，$U$也是可满足的
  • 验证$U$要比单独验证$U_1,U_2$的开销要小

如果用SNARK来实现NP问题的Folding Schemes，可以让Prover的提示为一个SNARK证明，用于证明$U_1$为可满足的，之后Verifier验证这个证明，并令$U\larr U_2$

这里还是需要用到SNARK，Nova的想法是消除对SNARK的依赖

首先回顾一下R1CS，不记得的看$[2]$

R1CS说的是，对于给定的三个$m$阶方阵$A,B,C$，实例$x$，对应的witness为$W$，存在一个矩阵$Z=(W,x,1)$，满足

$$ (A\cdot Z)\circ (B\cdot Z)=C\cdot Z \tag 1 $$

如果我们希望实现R1CS的Folding Scheme，看看如何实现

记实例为$U_1=(\hat W_1,x_1),U_2=(\hat W_2,x_2)$，这里$\hat W_i$表示witness $W$的承诺（承诺满足同态），R1CS的Folding Scheme如下

  1. Verifier选择随机性$r$发送给Prover，Prover计算$W=W_1+r\cdot W_2$
  2. Verifier计算$U=(\hat W,x)=(\hat W_1+r\cdot \hat W_2,x_1+r\cdot x_2 )$

看上去好像像这么回事，但是这并不能实现R1CS的Folding Scheme，因为存在某些随机性$r$，会导致Folding之后无法满足式1

这里我们把Folding之后的式1的左右两侧展开，如下

$$ \begin{aligned} LHS&=(AZ)\circ (BZ)\\ &=A(Z_1+r\cdot Z_2)\circ B(Z_1+r\cdot Z_2)\\ &=(AZ_1+r\cdot AZ_2)\circ (BZ_1+r\cdot BZ_2)\\ &=(AZ_1\circ BZ_1)+r^2\cdot (AZ_2\circ BZ_2)+r\cdot (AZ_2\circ BZ_1+AZ_1\circ BZ_2)\\ \\ RHS&=CZ\\ &=C(Z_1+r\cdot Z_2)\\ &=CZ_1+r\cdot CZ_2 \end{aligned} $$

观察式1的左右两侧，即便有$AZ_1\circ BZ_1=CZ_1,AZ_2\circ BZ_2=CZ_2$，也会存在某些$r$，使得式1的左右两侧不等

为了解决这个问题，Nova采用了R1CS的变体，将$Z$修改为$Z=(W,x,u)$，此时式1对应修改为

$$ AZ\circ BZ=u\cdot CZ+E\tag 2 $$

对应的witness为$(W,E)$，实例$U=\big ((A,B,C),(\hat W,\hat E,u,x)\big )$

标准的R1CS和上述R1CS变体可以相互转换，只需要令上述变体中的$u=1,E=\vec 0$，就是标准的R1CS了

然后看一下如何实现R1CS变体的Folding，实例为$U_1=(\hat W_1,\hat E_1,u_1,x_1),U_2=(\hat W_2,\hat E_2,u_2,x_2)$，过程如下

  • Prover发送一个hint：$T\larr Commit(AZ_1\circ BZ_2+AZ_2\circ BZ_1-u_1\cdot CZ_2-u_2\cdot CZ_1)$
  • Verifier选择随机性$r$发送给Prover
  • Verifier计算$U\larr (\hat W,\hat E,u,x)$，其中

$$ \begin{aligned} \hat W&=\hat W_1+r\cdot \hat W_2\\ \hat E&=\hat E_1+r\cdot T+r^2\cdot \hat E_2\\ x&=x_1+r\cdot x_2\\ u&=u_1+r\cdot u_2 \end{aligned} $$

  • Prvoer计算$W=W_1+r\cdot W_2,E=E_1+r\cdot T+r^2\cdot E_2$

IVC from Folding Scheme

回到之前的IVC的图

这里我们可以用R1CS来表示需要计算的函数$F'$，此时在第$i$步中，Prover构造一个证明$\pi=\lang \hat W,\hat T\rang$，其中$W$为$F'$的witness

而对应的Verifier验证电路会维持一个运行中的R1CS变体的实例，该实例会将新的承诺值折叠进这个实例中

利用这个方法，在经过$n$次迭代之后，Prover就可以得到对应的实例和witness

此时Prover想要向Verifier证明这$n$次迭代计算，最朴素的方式是直接将实例和witness发送给Verifier，但是这样做不仅不是简洁的（IVC证明大小为$O(|F'|)$个群元素），且也不满足零知识性

不过可以用zk-SNARK来证明IVC的知识，这样简洁性和零知识性就解决了，但是这又会导致Prover需要证明很多额外的东西，比如证明$W$的承诺$\hat W$的对应关系

Nova采用了Spartan的变体$[Set19]$来解决上述问题，将证明大小降低至$O(\log |F'|)$​

但是Nova也有自己的局限性

  • Nova的零知识性局限于单个Prover
  • 压缩证明可以减小到$O(\log |F'|)$，但不再满足增量可验证

此外还有一个开放的问题：是否有一个具有简洁证明的IVC方案，同时还具备Nova的各种特性

Summary

总结一下Nova的特性

  • 无需可信设置
  • 无需（基于FFT的）多项式乘法/除法，因此Nova的实现可基于任意循环曲线（比如secp/secq）或者对FFT友好的曲线（比如Pasta-like的曲线，Pallas/Vesta）
  • 函数$F$由R1CS指定
  • 在论证最简单的系统可提供非常高的效率
    Nova的Prover Time仅取决于两个规模为$O(C)=O(|F|)$的群幂运算，理论上Nova的效率要比Groth16、Plonk、Halo等方案要高5-50倍

Nova的Verifier电路规模为常量：验证电路中仅包含两次标量乘法，因此递归的阈值可以达到最小
压缩的证明大小：仅包含$O(\log C)$个群元素，实践中大约是若干KB

References

$[1]$ Nova: Recursive Zero-Knowledge Arguments from Folding Schemes - Srinath Setty - YouTube

$[2]$ 零知识证明（13）：R1CS与QAP - 三两老友杂的小岛 (snowolf0620.xyz)

‍