1 Introduction

上一篇博客对Nova做了一些简介，这里看点效率分析

回顾上一篇博客的内容，Nova Verifier的验证电路大小决定了递归证明的开销，因为IVC中除了证明$F$的计算之外，Prover还需要在每个增量步骤中证明一些额外的约束数量

Nova的Verifier电路的约束数量大约为两万个R1CS约束，是目前最少的验证电路约束数量（约为可信SNARK的$1/10$，透明SNARK的$1/100$），因此Nova的递归开销可以很小，Nova的验证电路约束主要是群标量乘法，占了总约束数量的一半以上，具体如下图所示

效率对比和效率渐进分析分别如图2和图3所示

2 Preliminaries

  • $\mathbb F$：有限域，大小$|\mathbb F|=2^{\Theta (\lambda)}$
  • $\cong$：表示PPT敌手计算不可区分

本文需要用到一个域$\mathbb F$上的向量承诺方案，满足加法同态和简洁性，此加法同态记为算法三元组$(\mathrm{Gen},\mathrm{Com} ,\mathrm{Open} )$，承诺方案满足统计隐藏性和绑定性

2.1 Incrementally Verifiable Computation

增量可验证计算方案用于验证一个函数$F$的迭代计算，函数的初始输入记为$z_0$，第$i$次迭代记为$z_i=F^{(i)}(z_0)$，对应第$i$次迭代的证明为$\Pi_i$

IVC方案记为算法三元组$(\mathcal G,\mathcal P,\mathcal V)$和一个生成元$\mathcal K$

2.2 Folding Schemes

关系$\mathcal R$的Folding Schemes为一个协议，协议将检查$\mathcal R$中的两个实例简化为检查$\mathcal R$中的单个实例

Folding Scheme包含四个算法$(\mathcal G,\mathcal P,\mathcal V,\mathcal K)$，满足完美完备性和知识合理性

  • $\mathcal G(1^\lambda)$：生成公共参数
  • $\mathcal K(pp,s)\rarr (pk,vk)$：其中$s$为需要fold的实例的公共结构，生成证明密钥$pk$和验证密钥$vk$
  • $\mathcal P(pk,(u_1,w_1),(u_2,w_2))\rarr(u,w)$：输出一个新的实例-witness对$(u,w)$
  • $\mathcal V(vk,u_1,u_2)\rarr u$：输出一个新的实例$u$

这里记$(u,w)\larr \lang\mathcal P(pk,w_1,w_2),\mathcal V(vk) \rang(u_1,u_2)$表示双方经过交互后，Verifier输出实例$u$，Prover输出witness $w$，对应的交互脚本记为$\mathrm{tr}$

2.3 A Folding Scheme for NP

上一篇博客提到了，对于R1CS关系，如果只是单纯的引入随机性$r$，并不能很好的实现折叠，为了解决这个问题，这里考虑引入一个松弛向量$E\in \mathbb F^m$（或者称为误差向量，同上一篇博客中的式2），用于吸收折叠过程中产生的交叉项，之后修改原有的R1CS为松弛的R1CS，如下

Def 11（Relaxed R1CS）：对于有限域$\mathbb F$，整数$m,n,l\in\N$，且$m>l$，松弛的R1CS结构包含三个$m$阶稀疏方阵，每个方阵中包含至多$n=\Omega(m)$个非零元素，包含一个误差向量$E\in \mathbb F^m$，标量$u\in \mathbb F$，公共输出和输出$\mathrm{x}\in \mathbb F^l$，松弛R1CS的实例记为$(E,u,\mathrm x)$，Witness记为$W$，满足$(AZ)\circ(BZ)=u\cdot (CZ)+E$，其中$Z=(W,\mathrm x,u)$

和上一篇博客提到的一样，令$u=1,E=0$，松弛的R1CS就是标准的R1CS了

相关的内容上一节博客已经介绍过了，这里不再展开

类似的，折叠方案也可以通过FS变换转换为非交互式的

3 Nova：An IVC Scheme with Proof Compression

Nova是一种由非交互式折叠方案设计的IVC方案，并结合了一个有效的zkSNARK来简洁地和在零知识中证明有效IVC证明的知识，提供了有效IVC证据的知识的简洁、零知识证明

在Nova中，在每个增量步骤，Prover都会将增量计算的特定步骤（表示为已承诺的松弛R1CS instance-witness对）折叠为正在运行的已承诺的松弛R1CS instance-witness对，在增量计算的任何步骤，有效的IVC证明都是正在运行的已承诺的松弛R1CS instance-witness对

此外，在任何增量步骤中，Nova的Prover都可以使用现有zkSNARK的变体来构造一个满足零知识性和简洁性的证明

这里有一点需要注意，Nova本身不是零知识的IVC方案，不过问题不大，因为Nova可以使用zkSNARK来提供有效IVC证明的知识的零知识证明

Nova论文原话：we leave it to future work to achieve zero-knowledge IVC

3.1 Constructing IVC from a Folding Scheme for NP

本文基于SNARK的IVC方案中，Prover使用一个增强的函数$F'$，如图4所示

这里先看一个$F'$的简化版本：$F'$以两个已承诺的松弛R1CS实例$u_i,U_i$作为输入，假设$U_i$表示$F'$的前$i-1$次正确执行，$u_i$表示$F'$的第$i$次正确执行

对于第$i$次执行，$F'$有两件事情要做

  1. 执行一次增量计算：$u_i$包含$z_i$，因此$F'$输出$z_{i+1}=F(z_i)$
  2. 折叠：$F'$调用非交互式折叠方案的Verifier，将验证$u_i,U_i$的过程折叠为验证$U_{i+1}$

IVC Prover之后计算一个新的实例$u_{i+1}$，用于表明$F'$的第$i+1$次正确执行，此时$z_{i+1}=F(z_i),U_{i+1}$为$u_i,U_i$的折叠结果

这里注意一个细节：由于$F'$必须输出正在运行的实例$U_{i+1}$（$U_{i+1}$包含于$u_{i+1}.\mathrm x$中，下一次调用需要用到$U_{i+1}$），但是下一次迭代中$F'$需要折叠$u_{i+1}.\mathrm x,U_{i+1}.\mathrm x$，此时$F'$会在将$U_{i+1}$压缩至$U_{i+1}.\mathrm x$中时卡住，导致最终折叠结果不一致

为了解决这个问题，令$F'$输出一个关于公共输入输出的Hash值，而不是直接处理公共输入输出，之后对$F'$的调用时将这个Hash值得原像作为非确定性输入

Producing IVC Proofs

如何构造IVC证明，令$(u_\bot,w_\bot)$表示一对平凡的instance-witness对，$r_E=0,r_W=0$，$\bar E,\bar W$为$E,W$的承诺

对于第$i+1$次迭代，IVC Prover调用$F'$并利用$w_{i+1},W_{i+1}$计算$u_{i+1},U_{i+1}$，得到对应的证明$\Pi_{i+1}=((U_{i+1},W_{i+1}),(u_{i+1},w_{i+1}))$，函数$F'$的具体构造如下

图5
图5

由于函数$F'$可在多项式时间内计算，因此可以被表示为松弛R1CS结构的一个承诺$\mathbf s_{F'}$，这里引入一个记法

$$ (u_{i+1},w_{i+1})\larr \mathbf{trace}(F',(vk,U_i,u_i,(i,z_0,z_i),\omega_i,\bar T)) $$

用于表示可满足松弛R1CS承诺的instance-witness对$(u_{i+1},w_{i+1})$

对应的，IVC的构造如下

3.2 Compressing IVC Proofs with zkSNARKs

上一节介绍了如何构造并生成IVC证明，但是如果为了证明的话，Prover需要将证明和对应的witness发送给Verifier，因为上一节中的IVC证明并没有隐藏Prover的非确定性输入，不满足零知识性，且证明大小与$F$呈线性关系，也不满足简洁性

理论上可以用基于NP的zkSNARK来解决这个问题，比如让Prover利用zkSNARK来证明其知道一个$\Pi_i$，这样可以满足零知识性和简洁性

但是有一个问题，如果采用zkSNARK构造证明的话，Prover必须证明其承诺值与特定向量之间关联性的知识，这意味着需要zaizkSNARK模型中对线性数量的标量群乘法进行编码

为了解决这个问题，本文设计了一个特定的zkSNARK（详见原文第六节），这里先看一下如何使用zkSNARK来证明IVC的知识

记$\mathrm{IVC}$表示图5中的IVC方案，记$\mathrm{NIFS}$表示非交互式折叠方案，记$\mathrm{hash}$表示随机化的密码学Hash函数，考虑一个多项式时间可计算函数$F$，对于实例$(i,z_0,z_i)$，此时Prover希望向Verifier证明存在一个$\Pi_i$，使得$\mathrm{IVC.V}(vk,i,z_0,z_i,\Pi_i)=1$

简单来说，这里用到了一个点：$\Pi$是两个承诺的松弛R1CS instance-witness对，此时Prover首先利用$\mathrm{NIPS.P}$，对这两对instance-witness进行折叠，构造$(U',W')$，然后Prover调用zkSNARK的Prover，构造一个证明，来证明其知道$U'$

具体的方案如下

4 A zkSNARK for Committed Relaxed R1CS

Nova用了一个Spartan的变体来设计承诺的松弛R1CS的zkSNARK

这里需要多线性扩展和和校验协议的知识，具体可以看$[2]$，Spartan协议可以参考$[3]$

4.1 A Polynomial IOP for Idealized Relaxed R1CS

近几年的zkSNARK都是基于PIOP构建，回顾一下PIOP，Prover向Verifier发送的预言机为多项式，Verifier请求计算该多项式在一个随机点上求值

Nova考虑了PIOP的一个变体，使得Verifier可以访问R1CS结构和实例中的多项式

Nova首先考虑了一个理想的松弛R1CS，其和一般的松弛R1CS仅有一点区别：理想的松弛R1CS实例中包含witness，一般的版本不包含witness，基于这个理想的松弛R1CS，看看如何构建PIOP

首先考虑理想松弛R1CS的statement $\phi$，包含公共参数$(m,n,l)$，R1CS矩阵$(A,B,C)$，实例$(E,u,W,\mathrm x)$，不失一般性假设$m,n$均为2的幂，且满足$m=2\cdot(l+1)$​

这里记$s=\log m$，可以将三个矩阵视为$\{0,1\}^{\log m}\times \{0,1\}^{\log m}\rarr\mathbb F$的映射，此时这三个映射对应的多线性扩展记为$\tilde A,\tilde B,\tilde C$，根据之前松弛R1CS的定义，这三个都是包含$2\log m$个变量的稀疏多线性多项式

类似的，可以将$E$视为映射$\{0,1\}^{\log m}\rarr \mathbb F$，将$W$视为映射$\{0,1\}^{\log m-1}\rarr \mathbb F$，对应的多线性扩展记为$\tilde E,\tilde W$

对于$Z=(W,\mathrm x,u)$，类似的将其视为映射，这里将$Z$视为映射$\{0,1\}^s\rarr \mathbb F$，$(\mathrm x,u)$视为映射$\{0,1\}^{s-1}\rarr \mathbb F$，这里观察$Z$的多线性扩展$\tilde Z$

$$ \tilde Z(X_1,\dots,X_s)=(1-X_1)\cdot \widetilde W(X_2,\dots, X_s)+X_1\cdot \widetilde {(\mathrm x,u)}\cdot (X_2,\dots,X_s)\ \tag 1 $$

根据Spartan论文中的定理4.1，此时验证$\phi$是否可满足，等价于在一个随机向量$\tau\in\mathbb F^s$处验证下列式2

$$ \sum_{x\in \{0,1\}^s}\tilde {eq}(\tau,x)\cdot F(x)=0 \tag 2 $$

其中$F(x)$如下

$$ \begin{aligned} F(x)=&\Big( \sum_{y\in\{0,1\}^s}\tilde A(x,y)\cdot \tilde Z(y) \Big)\cdot \Big( \sum_{y\in\{0,1\}^s}\tilde A(x,y)\cdot \tilde Z(y) \Big)-\\ &\Big( \sum_{y\in\{0,1\}^s}\tilde C(x,y)\cdot \tilde Z(y)+\tilde E(x) \Big) \end{aligned} $$

对于随机向量$\tau$，式2的合理性误差为$\log m/|\mathbb F|$

为了计算式2的左侧，Prover和Verifier可以对多项式$g(x)=\tilde {eq}\cdot F(x)$执行一个和校验协议，此时对于Verifier而言，验证式2就转变为了在一个随机点$r_x\in \mathbb F^s$处对多项式$g$求值

和校验协议的最后，Verifier需要对这三个多项式进行一个最终检查，也即在一个随机向量$r_y$处计算上述的$\tilde A,\tilde B,\tilde C,\tilde Z$，对应的PIOP协议如下

​

最后再用密码学编译器将上述PIOP编译为zkSNARK就可以了，Nova的原文采用的是KZG10多项式承诺和Fiat-Shamir变换

References

$[1]$ Abhiram Kothapalli, Srinath Setty, Ioanna Tzialla:Nova: Recursive Zero-Knowledge Arguments from Folding Schemes. IACR Cryptol. ePrint Arch. 2021: 370 (2021)

$[2]$ 多项式扩展与和校验协议 - 三两老友杂的小岛 (snowolf0620.xyz)

$[3]$ Spartan：满足透明性的通用高效zkSNARK方案 - 三两老友杂的小岛 (snowolf0620.xyz)

‍