Abstract
HyperNova是一种用于IVC的递归论证，步骤以Setty等人提出的定制化约束系统（Customizable Constraint System，CCS）表示，可以在无开销的情况下同时扩展Plonkish、R1CS和AIR
HyperNova的优点在于，Prover每一步的开销都由一个大小等于约束系统中变量数量的多标量乘法决定，当使用基于MSM的承诺方案时，效率可达到最优
本文扩展了Crypto22中的Nova，使得其可以折叠两个不同的NP实例（Nova只能折叠相同的NP实例），本文称之为多折叠方案（Multi-Folding Schemes）
此外，本文为CCS和线性CCS（Linear CCS）设计了一个公共掷币的多折叠方案，此类方案可以被视为Spartan的早期停止版本（Early Stopping Version），Prover在多折叠方案中的开销线性数量的域运算，Verifier的开销为对数数量的域运算和群乘法，本文还用最低的Prover开销和递归开销，从非交互式多折叠方案中构建了IVC
本文还提供了HyperNova的另一种实现方式，也即将Nova视为黑盒，从而几乎消除了用椭圆曲线循环群实例化时对延迟运算的需求
本文还描述了一个称为nlookup的查找论证方案，其非常适用于基于折叠方案的递归论证，具体而言，在IVC的特定步骤，对于大小为$n(m\ll n)$的表中进行$m$个查找，Prover的工作主要包含$O(n)$次有限域运算，并且在增量计算过程中只需要$O(m\cdot \log n)$次阶为2的约束和$O(\log n)$次Hash计算
然而nlookup目前仍不适合有效编码位运算，但是可以有效编码（大型）有限状态机，并用递归SNARK为此类状态机提供证明
1 Introduction
本文基于Nova和SuperNova的工作，该方向的工作主要有两个方面
- 为半结构、非确定性计算提供了最快的简洁论证，且待证明的计算可以分解为多个步骤（这里要求这些步骤具有相同的电路表示），
- 提供了最有效的递归论证方案，具有最低的递归开销
（Super）Nova的计算模型支持IVC，其中特定步骤调用一些预定义的指令，该模型可以捕获许多事件中常出现的结构化或半结构化的语句，例如VDF中可能只有一条指令，用于验证延迟函数的迭代（比如验证MinRoot是否正确执行，或者执行zkVM中的预定义指令）
为了验证此类IVC，Nova提出了折叠方案，将证明程序执行的$N$个步骤（递归的）转换为单个步骤，然后再利用一个zkSNARK来证明这个单个步骤，其特点在于折叠的过程中不依赖于zkSNARK（甚至可以不依赖于NARK）
与直接使用多项式IOP和多项式承诺方案投建的通用zkSNARK来证明整个增量计算相比，只要每一步增量计算足够大，大到可以抵消递归的开销，Nova的方法的开销就要小得多，具体而言，每个增量步骤中，Nova的Prover只需要两次MSM，MSM的规模与所证明的电路大小相关（如果采用通用zkSNARK，则需要更多的MSM，比如Marlin需要22个，以及一些额外的FFT）
在设计上，Nova的证明生成是增量的（为每个步骤生成一个整蒙，然后使用递归来构造单个证明），因此其可以比非递归zkSNARK更容易进行分布式和并行执行，而非递归的zkSNARK中必须将程序执行展开到单个电路中，而且此类方式不仅不能静态展开程序（不能展开VDF之类的程序），也不够方便（难以在EVM或者RISC上执行），不过Nova并不立即支持并行证明生成，其需要一个通用编译器来转换Nova的结构（从而支持并行证明）
Problem Statement
Nova中的IVC的每一步都是用R1CS描述的，实践中的单个zkSNARK用于大型程序执行时，参与方通常使用针对特定应用类别定制的自定义约束系统（比如Plonkish，其中的约束时多元高阶多项式，可以用于自定义高阶多项式门），而R1CS仅限于特定形式的二次约束
关键点在于：是否可以为Plonkish构建一个递归论证，使其具有类似于Nova的性质，尤其是本文的目标是证明Setty等人的CCS（一个可定制的约束系统，其可以在无开销的情况下同时推广Plonkish、R1CS和AIR）
Prior approaches and challenges
Halo2取代了Halo中Snoic到Plonk的多项式IOP，转而使用Plonkish，但是这也为Halo2引入了大量的Prover开销（Prover必须在程序执行的每一步使用Plonk构造一个SNARK），而且Prover需要包含$O(nd)$次密码运算，其中$n$为电路大小，$d$为约束的最大阶，从Plonk到HyperPlonk可以将密码运算的数量减少至$O(n)$，但是仍然不能避免构造SNARK
$[BCL+21]$提出了分割累加的思想（Split Accumulation），此类思想见笑了Halo类型方法的递归开销，同时避免了构造递归SNAKR时需要的简洁论证，但是现有的从分割累加构造的SNARK仅限于R1CS，且仍不清楚如何在不让Prover执行$O(nd)$次加密运算的情况下处理Plonkish，换言之，分割累加的思想也存在Halo2中的问题
Sangria$[Moh23]$中提到了一点：Nova的R1cS折叠可以适用于Plonkish，但是Prover对交叉项承诺的数量会与$d$呈线性关系，而且也需要执行$O(nd)$次加密运算来对这$O(d)$个交叉线进行承诺，通常来说，用Nova来证明阶为2的约束比Sangria的开销要小（MinRoot延迟函数的单次迭代可以用Plonkish中的单个阶为5的约束来表示，如果用R1CS则需要三个约束条件，用Sangria来证明阶为5的Plonkish中的MinRoot，与Nova中的R1CS证明MinRoot相比，其Prover需要更多的开销）
1.1 Our Approach:HyperNova
HyperNova的目标是证明增量计算，其中增量计算的每个步骤都用CCS表示
但是这里有一个问题，如果只是简单地为CCS构建一个折叠方案（比如CCS的松弛变体，类似于Nova中对R1CS的松弛），则会存在上述Sangria提到的效率问题
为了避免效率问题，HyperNova采用和校验协议（及其最近的扩展，SuperSpartan$[STW23]$）来处理CCS，本文提供了两个实例，一个用于直接构建HyperNova，另一个将Nova视为黑盒来使用，两种变体都可以使用ECC循环有效实例化，且具有相同的Prover效率，不过后者具有最小的延迟算术（Deferred Arithmetic，为了确保效率，算术运算必须传递到曲线循环中的另一条曲线），当实现递归论证时，会出现此类情况
Multi-Folding Schemes
为了构建HyperNova，这里介绍一种广义化的折叠方案，本文称为Multi-Folding（多重折叠）
Nova中提到了关系$\mathcal R$的折叠方案可以将两个实例折叠为一个实例，而多重折叠则是定义在一对关系$(\mathcal R_1,\mathcal R_2)$上的折叠方案，Prover可以将证明与验证具有相同结构$\mathrm s$的两个关系$\mathcal R_1,\mathcal R_2$折叠至证明与验证关系$\mathcal R_1$的结构$\mathrm s$中
Remark 2：多重折叠方案和分割累加的方案相关，但是前者使用NP关系，且在标准交互模型中定义（无需辅助决策器算法与相关的复杂性）
此外，通过NP关系的语言，折叠方案和多重折叠方案的概念中，witness和instance是独立的（从而使得定义、安全概念和证明在概念上更简单）
A multi-folding scheme for CCS
本文注意到Spartan中将检查CCS势力的可满足性转换为了检查阶为$d+1$的多元多项式$g$（$d$为CCS中约束的阶）是否在某一布尔超立方上的求和为零，然后调用和校验协议来证明关于$g$的Statement，尽管和校验协议结束时，双方仅能检查部分Claim，但是这些Claim涉及到CCS的限制形式（本文将此类限制性的CCS称为线性CCS），Spartan随后通过额外调用一个和校验协议来证明这些线性CCS
虽然早期停止版本的Spartan提供了从CCS到线性CCS的归约，但是它本质上还不是折叠方案，因此本文的第二个想法是对$g$进行修改，从而可以让Verifier发起一个额外的随机挑战来包括正在执行的线性CCS的Clai（这里要求正在运行的实例和正在折叠的CCS实例具有相同的结构）
这样一来，我们就获得了一个公共掷币的多重折叠方案，该方案可以将具有结构$\mathrm s$的CCS实例折叠为具有相同结构的线性CCS实例，Prover在折叠过程中的开销为线性数量的有限域运算（不需要对任何交叉项进行承诺），Verifier的开销为对数数量域运算，方案可用FS变换来转变为RO模型中的非交互式协议
Remark 3：本文的多重折叠CCS比描述的更为强大，可以用$\mu$个运行的线性CCS实例和$\nu$个具有相同结构的CCS实例，输出单个线性CCS实例，因此本文的多重折叠方案可以用参数$(\mu,\nu)$进行描述
IVC and its generalizations from multi-folding schemes
和Nova一样，本文的多重折叠方案也从一个“默认”运行的实例开始，然后IVC的每一步中，Prover都会对一个增广的CCS（Augmented CCS）实例的witness进行承诺
增广CCS不仅执行IVC，还会执行非交互式多重折叠方案的Verifier
然后Prover执行非交互式多重折叠方案，将CCS实例折叠为正在运行的实例，同时将CCS实例和多重折叠实例的输出作为输入发送到扩展电路的下一次调用，然后证明IVC的下一步
在Nova中，结束阶段（或增量计算的某一个时刻），Prover会留下一个正在运行的实例$U$（HyperNova中这个实例为线性CCS）和一个CCS实例$u$，后者表示IVC的最后一步，并用验证电路进行了扩充，Prover通过调用CCS的多重折叠方案将$U,u$折叠为$U'$，输出记为$\pi_{fs}$
而在HyperNova中，对应的递归证明为$\pi=(U,u,\pi_{fs},w)$，其中$w$表示$U'$的witness，由于这个$\pi$的大小和IVC的步骤呈线性关系，因此Prover的做法为构造一个zkSNARK，来证明这个$\pi$的有效性
A Construction of IVC with a black box use of Nova
除了从CCS的非交互式多重折叠方案直接构建IVC外，本文还描述了一种利用Nova作为黑盒的方法构建，其思想史将CCS的非交互式多重折叠方案的Verifier表示为Nova中的step circuit（步进电路？），步进电路会保存一个正在运行的实例，每个步骤中，Prover首先将IVC的一个步骤折叠为运行实例$u$，然后将其与运行实例$U$一起折叠，得到一个新的运行实例$U'$（及其对应的witness）和对应的证明$\pi_{fs}$，步进电路将$u$折叠成一个运行实例，并利用证明$\pi_{fs}$，通过公共IO跟踪该实例
IVC的结束阶段（或某一时刻），Verifier可以验证与IVC相关的Nova证明，并使用Prover的witness检查步进电路的公共IO中的运行实例是否是合法的（和上面一样，最后的验证可以用zkSNARK来得到一个简洁的证明）
这个版本的HyperNova的优点是只需要实现一个步进电路，而且非交互式折叠方案的Verifier的大部分开销在对数数量的域运算和Hash计算（这两个部分都可以用R1CS来表示），但不过步进电路还是需要计算一些群标量乘法， 如果使用椭圆曲线循环时，可以将其推迟（Deferred）到另一条曲线中
2 Preliminaries
- $\mathbb F_p$：由素数$p$确定的有限域
- $\lambda$：安全参数
需要的前置知识包括：多项式及其低阶扩展、多线性多项式的密集表示法、和校验协议、SZ引理、SNAKR，具体可以看$[2,3]$以及之前的相关博客，这里不再展开
本文需要用到两个密码学原语，如下
- IVC方案：记为算法四元组$(\mathcal G,\mathcal K,\mathcal P,\mathcal V)$，满足完美完备性，知识合理性和简洁性
- 多项式承诺方案：记为算法四元组$(\mathrm{Gen},\mathrm{Commit},\mathrm{Open},\mathrm{Eval})$，满足完备性，绑定性，加法同态性，知识合理性
3 Multi-folding schemes
本节正式介绍多重折叠方案，该方案由两个参数$(\mu,\nu)$定义，目的是将一对关系$(\mathcal R_1,\mathcal R_2)$进行折叠
具体而言，协议将$\mathcal R_1$中的$\mu$个实例和$\mathcal R_2$中的$\nu$个实例（均具有相同的结构$\mathrm s$）折叠成$\mathcal R_1$中的实例，具体定义为下列四个算法
- $\mathcal G(1^\lambda)\rarr pp$：输出公共参数$pp$
- $\mathcal K(pp,\mathrm s)\rarr(pk,vk)$：生成Prover和Verifier的密钥
- $\mathcal P(pk,(\vec u_1,\vec w_1),(\vec u_2,\vec w_2))\rarr (u,w)$：输入$\mathcal R_1,\mathcal R_2$中的两个实例向量$\vec u_1,\vec u_2$，大小分别为$\mu,\nu$，及其对应的witness向量$\vec w_1,\vec w_2$，算法将其折叠为$\mathcal R_1$中的instance-witness对$(u,w)$
- $\mathcal V(vk,\vec u_1,\mathcal u_2)\rarr u$：输入两个实例向量，算法输出一个新的实例$u$
这里记$(pp,\mathrm s,\vec u,\vec w)\in \mathcal R^{(n)}$，表示当且仅当对于所有的$i\in [n]$，均有$(pp,\mathrm s,\vec u_i,\vec w_i)\in \mathcal R$
对于上述多重折叠方案，要求其满足完美完备性、知识合理性，高效性（Efficiency），其中高效性要求通信开销和Verifier的计算很小（至少要比检查原来的实例要小）
上述多重折叠方案可以用FS变换转换为非交互式协议，下面将非交互式协议记为$\Pi'=(\mathcal G',\mathcal K',\mathcal P',\mathcal V')$
4 Customizable constraint systems
Setty等人在$[STW23]$中提出了CCS的概念，本节介绍一下CCS的定义，及其两个扩展CCCS和LCCCS
Def 1（CCS）：与CCS相关的关系记为$\mathcal R_{CCS}$，其对应的（公共）规模参数为$m,n,N,l,t,q,d\in \N$，满足$n>l$
$\mathcal R_{CCS}$的公共输入和witness分别定义为$x,w$，$\mathcal R_{CCS}$的结构$\mathrm s$定义如下
- $t$个$m\times n$的域元素矩阵，记为$M_1,\dots,M_t$，每个矩阵包含至多$N$个非零域元素
- $q$个多重集，记为$S_1,\dots,S_q$，每个多重集的元素均来自集合$\{1,\dots,t\}$，多重集的大小不超过$d$
- $q$个约束集合，记为$c_1,\dots,c_q$，每个约束均来自于域$\mathbb F$
多重集的意思是：集合中的元素可以出现超过一次
对于$(\mathrm s,x)$和witness $w$，$\mathcal R_{CCS}$要求对于$z=(w,1,x)$，满足下列等式
$$ \sum_{i=1}^qc_i\cdot \bigcirc_{j\in S_i} M_j\cdot z=\mathbf 0 $$
其中$\bigcirc$表示向量的哈达玛积，$\mathbf 0$表示0向量
4.1 Committed CCS
承诺的CCS，其实就是对矩阵$M_i$做一个多线性扩展，记为$\widetilde M_i$，这里不失一般性假设$|w|=l+1$，对应的CCCS定义如下
Def 2（Committed CCS）：记$PC=(Gen,Commit,Open,Eval)$为一个满足加法同态的多线性多项式承诺方案，CCCS的关系记为$\mathcal R_{CCCS}$
规模参数为$m,n,N,l,t,q,d\in \N$，满足$n=2\cdot (l+1)$，记$s=\log m,s'=\log n$，记$pp\larr Gen(1^\lambda,s'-1)$，$\mathcal R_{CCCS}$的结构$\mathrm s$定义如下
- $t$个多线性多项式$\widetilde M_1,\dots \widetilde M_t$，变量数量为$s+s'$，每个多项式在至多$N$个点（布尔超立方）处求值为非零
- 其余两个（多重集和约束集合）与CCS一致
$\mathcal R_{CCCS}$的实例记为$(C,x)$，其中$C$表示多线性多项式的承诺，witness $\tilde w$为一个包含$s'-1$个变量的多线性多项式
$\mathcal R_{CCCS}$要求对于承诺$C=Commit(pp,\tilde w)$，对于任意的$x\in \{0,1\}^s$，有下列等式成立
$$ \sum^q_{i=1}c_i\cdot \Big( \Pi_{j\in S_i} \Big(\sum_{y\in \{0,1\}^{\log m}}\widetilde M_j(x,y)\cdot \tilde z(y) \Big) \Big)=0 $$
这里$\tilde z$是$z$的多线性扩展
4.2 Linearized committed CCS
基于CCCS，再做一个改进，称为线性化的CCCS，对应的关系记为$\mathcal R_{LCCCS}$
LCCCS的结构与CCCS一致，不过实例变为了$(C,u,x,r,v_1,\dots,v_t)$，其中$C$还是承诺，witness也还是$\tilde w$
LCCCS要求对于承诺$C=Commit(pp,\tilde w)$，对于任意的$i\in [t]$，有下列等式成立
$$ v_i=\sum_{y\in\{0,1\}^{s'}}\widetilde M_i(r,y)\cdot \tilde z(y) $$
5 A multi-folding scheme for CCS
本节介绍如何为LCCCS和CCCS构造多重折叠方案，这里假设$\mathcal R_1=\mathcal R_{LCCCS},\mathcal R_2=\mathcal R_{CCCS}$，并且假设$\mu=\nu =1$（后续可扩展到任意的$\mu,\nu$值）
各个算法流程如下所示
- $\mathcal G(1^\lambda):$输出$pp=(m,n,N,l,t,q,d,pp_{PC})$
- $\mathcal K$：输出$pk=(pp,([\widetilde M_1,\dots,\widetilde M_t),[S_1,\dots,S_q],[c_1,\dots,c_q])$，$vk=\bot$
之后对于$\tilde z_1=\widetilde{(w_1,u,x_1)},\tilde z_2=\widetilde{(w_2,u,x_2)}$，双方执行下列步骤
- Verifier向Prover发送随机值$\gamma$，长度为$s$的随机向量$\beta$，同时Verifier选择长度为$s$的随机向量$r'_x$
- 双方基于多项式$g$，随机向量$r'_x$和值$\sum_{j\in[t]}\gamma^j\cdot v_j$，执行和校验协议，其中多项式$g$如下
$$ \begin{aligned} g(x)&=\Big( \sum_{j\in [t]} \gamma^j\cdot L_j(x) \Big)+\gamma^{t+1}\cdot Q(x)\\ L_j(x)&=\widetilde {eq}(r_x,x)\cdot \Big(\sum_{y\in \{0,1\}^{s'}}\widetilde M_j(x,y)\cdot \tilde z_1(y) \Big)\\ Q(x)&=\widetilde{eq}(\beta,x)\cdot \Big( \sum^q_{i=1}c_i\cdot \prod _{j\in S_i}\Big( \sum_{y\in \{0,1\}^{s'}} \widetilde M_j(x,y)\cdot\tilde z_2(y) \Big) \Big) \end{aligned} $$
- Prover返回$(\sigma_1,\dots,\sigma_t),(\theta_1,\dots,\theta_t),i\in [t]$，$\sigma_i,\theta_i$如下
$$ \begin{aligned} \sigma_i&=\sum_{y\in \{0,1\}^{s'}}\widetilde M_i(r_x',y)\cdot \tilde z_1(y)\\ \theta_i&=\sum_{y\in \{0,1\}^{s'}}\widetilde M_i(r_x',y)\cdot \tilde z_2(y) \end{aligned} $$
- Verifier计算$e_1=\widetilde{eq}(r_x,r_x'),e_2=\widetilde{eq}(\beta,r_x')$，并验证下列等式（等式不成立则Verifier终止协议）
$$ c=\Big( \sum_{j\in [t]} \gamma^j\cdot e_1\cdot \sigma_j+\gamma^{t+1}\cdot e_2\cdot \Big( \sum^q_{i=1}c_i\cdot \prod_{j\in S_i}\theta_j \Big) \Big) $$
- Verifier向Prover发送随机值$\rho$，之后Prover输出折叠后的witness $\tilde w'=\tilde w_1+\rho\cdot \tilde w_2$
- 双方输出折叠后的LCCCS实例$(C',u',x',r_x',v'_1,\dots,v'_t)$，其中
$$ \begin{aligned} C'=C_1+\rho\cdot C_2\\ u'=u+\rho\cdot 1\\ x'=x_1+\rho\cdot x_2\\ v_i'=\sigma_i+\rho\cdot \theta_i \end{aligned} $$
这里分析一下$\mu=\nu =1$时协议的完美完备性
考虑敌手输出的任意结构$\mathcal S$
$$ \mathcal S=(\widetilde M_1,\dots,\widetilde M_t),(S_1,\dots,S_q),(c_1,\dots,c_q) $$
根据第四节提到的内容，若LCCCS是可满足的，则对于$\tilde z_1=\widetilde{(w_1,u,\mathrm x_1)}$，有下列等式成立
$$ \begin{aligned} v_j& = \sum_{y\in\{0,1\}^{s'}}\widetilde M_j(r_x,y)\cdot \tilde z_i(y)\\ &= \sum_{x\in\{0,1\}^s}\widetilde{eq}(r_x,x)\cdot \Big( \sum_{y\in\{0,1\}^{s'}}\widetilde M_j(x,y) \Big)\\ &= \sum_{x\in\{0,1\}^s}L_j(x) \end{aligned}\tag 1 $$
同理，若CCCS是可满足的，则对于任意的$x\in \{0,1\}^s$和$\tilde z_2(x)=\widetilde{(w,1,\mathrm x)}(x)$，有
$$ 0=\sum_{i= 1}^qc_i\prod_{j\in S_i}\Big(\sum_{y\in\{0,1\}^{s'}}\widetilde M_j(x,y)\cdot \tilde z_2(y) \Big) $$
这里观察上述等式的右侧，注意到其是关于$x$的多项式，且其对于所有的$x\in \{0,1\}^s$，该多项式求值均为零，因此对于Verifier选择的随机值$\beta$，上述式子可以改写为
$$ \begin{aligned} 0&=\sum^q_{i=1}c_i\prod_{j\in S_i}\Big(\sum_{y\in \{0,1\}^{s'}}\widetilde M_j(\beta,y)\cdot \tilde z_2(y)\Big)\\ &=\sum_{x\in\{0,1\}^s}\widetilde{eq}(\beta,x)\cdot \sum^q_{i=1}c_i\prod_{j\in S_i}\Big(\sum_{y\in \{0,1\}^{s'}}\widetilde M_j(x,y)\cdot \tilde z_2(y)\Big)\\ &=\sum_{x\in\{0,1\}^s}Q(x) \end{aligned}\tag 2 $$
然后对于Verifier选择的随机性，根据线性性质，将式1和式2组合起来，得到下面这个多项式等式
$$ \begin{aligned} \sum_{j\in[t]}\gamma^j\cdot v_j&=\sum_{x\in\{0,1\}^s}\Big(\Big(\sum_{j\in[t]}\gamma^j\cdot L_j(x)\Big)+\gamma^{t+1}\cdot Q(x)\Big)\\ &=\sum_{x\in\{0,1\}^s}g(x) \end{aligned} $$
然后根据和校验协议的完美完备性，这里有$e_1=\widetilde{eq}(r_x,r_x'),e_2=\widetilde{eq}(\beta,r_x')$，以及
$$ \begin{aligned} \sigma_i&=\sum_{y\in\{0,1\}^{s'}}\widetilde M_i(r_x',y)\cdot\tilde z_1(y)\\ \theta_i&=\sum_{y\in\{0,1\}^{s'}}\widetilde M_i(r_x',y)\cdot\tilde z_2(y) \end{aligned} $$
从而有
$$ \begin{aligned} c&=g(r_x')\\ &=\Big(\Big(\sum_{j\in[t]}\gamma^j\cdot L_j(r_x')\Big)+\gamma^{t+1}\cdot Q(r_x')\Big)\\ &=\Big(\Big(\sum_{j\in[t]}\gamma^j\cdot e_1\cdot \sigma_j\Big)+\gamma^{t+1}\cdot e_2 \sum_{i\in[q]}c_i\cdot \prod_{j\in S_i} \theta_j\Big) \end{aligned} $$
至此，根据协议的步骤4，若有上述等式成立，则意味着Verifier没有终止协议
然后考虑一个线性化CCS的实例$(C_2,1,\mathrm x_2,r_x',\theta_1,\dots,\theta_t)$，根据CCCS的定义，$\tilde w_2$满足CCCS的实例$(C_2,\mathrm x_2)$，然后根据$(\theta_1,\dots,\theta_t)$的定义，$\tilde w_2$也满足线性化的CCS
因此对于Verifier选择的随机值$\rho$，输出线性化之后的CCS实例$(C',u',x',r_x',v'_1,\dots,v'_t)$即可，且该实例可被witness $\tilde w'=\tilde w_1+\rho\cdot \tilde w_2$满足（这里要求承诺方案满足加法同态即可），证毕
部分概率分析可以参考基于分叉引理的折叠方案$[KST22,BCC+16]$
协议的知识合理性可以看原文，主要思路是假设恶意Prover $\mathcal P^*$成功的概率记为$\epsilon$，通过构造一个期望多项式时间的抽取器$\mathcal E$，其以$\epsilon-negl(\lambda)$的概率来成功抽取witness==不难，主要是太长了==
6 HyperNova: IVC from multi-folding schemes
6.1 A direct approach
最直接的方案是将Nova中的IVC方案改成多重折叠的情况
首先考虑一个多项式时间函数$F$和一个密码学Hash函数，记为$\mathrm{hash}$，本文定义$F$的增广函数$F'$如下
之后记$(\mathrm u_{i+1},\mathrm w_{i+1})$表示满足$\mathcal R_{CCCS}$的instance-witness对，其由$F'$执行得到，也即
$$ (\mathrm u_{i+1},\mathrm w_{i+1})\larr \mathrm{trace}(F',(vk,U_i,u_i,(i,z_0,z_i),\omega_i,\pi)) $$
对应的IVC算法如下图所示
完整性和知识合理性分析可以看原文，这里不再赘述
6.2 A simple approach to build HyperNova:Use Nova as a black box
本节介绍另一种HyperNova的构造，也即将Nova视为黑盒来构建HyperNova
前面提到了步进电路（Step Circuit），该电路用R1CS进行编码，并用Nova进行证明，不过步进电路仅执行非交互式折叠方案中的Verifier
在Nova中，每个步进电路将前一步的输出作为输入，同时产生当前步骤的输出，在HyperNova中，除了应用程序的IO以外，还需要一个最新运行的实例来对其进行增广
在每个递归步骤中，步进电路将CCCS的实例$u$和多重折叠方案中Prover的输出$\pi$作为输入，并检查$u$的公共输入是否与提供给步进电路的输入匹配，如果相匹配，则步进电路对$(vk,U,u,\pi)$执行折叠方案的Verifier，并使用$u$的公共输出和折叠方案的Verifier的输出来得到步进电路的输出
记$\mathrm{IVC}$为Nova中的IVC方案，记$\mathrm{step}$表示非确定性多项式时间函数的步（step），用于迭代折叠$\mathcal R_{CCCS}$中的实例
对应的构造如下图如所示
7 nlookup: A lookup argument for Nova
本节介绍一种适用于Nova和HyperNova等方案的查找论证
假设表$T$的大小为$n$，要查找的值为$m$个CCS中的变量$(v_1,\dots,v_m)$
如果需要完成查表，最简单的方法是将$T$用Merkle Tree的方式保存，此时电路只需要将树根的承诺作为输入即可，但是这个方式需要$O(m\log n)$次Hash计算
如果采用Plookup来完成的话，约束数量为$O(\max[m,n])$，如果$m,n$差不多大的话还可以接受，但是Nova之类的递归SNARK中的查找操作数量有$m\ll n$，因此不太实用
最近有一个基于缓存商的方案cq$[EFG22]$（或者看之前的博客$[6]$），cq考虑了$m\ll n$的情况，但是仍然不太清楚如何在不引起高递归开销的情况下将其用于递归SNARK
本文提出了一种高效的查找论证，称为nlookup，计算开销包括$O(m\log n)$次乘法和$O(\log n)$次Hash运算，且Prover无需承诺额外的多项式
nlookup可用于Nova和HyperNova的高效表示，但缺点在于其无法处理电路中的位运算
nutshell
不失一般性假设$n=2^l$，并将查找表$T$视为一个映射$\{0,1\}^l\rarr \mathbb F$，其对应的多线性扩展为$\tilde T$
为了完成$m$个查找，Prover选择$m$个求值点$(q_1,\dots,q_m)$，满足$\forall i\in[m],\tilde T (q_i)=v_i$，然后对于多重折叠方案，双方需要将这$m$个查找折叠为$\tilde T$的但点查询
假设刚开始的claim为检查等式$\tilde T(q_r)=v_r$是否成立（初始化的时候随便选一个$q_r$，然后令$\tilde T(q_r)=v_r$即可），然后Verifier选择随机值$\rho$，通过折叠方案将下列claim转换为$\tilde T$上的求值
$$ v_r+\sum_{i\in[m]}\rho^i\cdot v_i=\sum_{j\in\{0,1\}^{\log n}}\widetilde{eq}(q_r,j)\cdot \tilde T(j)+\sum_{i\in[m]}\rho^i\cdot \sum_{j\in\{0,1\}^{\log n}}\widetilde{eq}(q_i,j)\cdot \tilde T(j) $$
折叠方案用和校验协议来得到一个新的claim，并输出新的claim：$\tilde T(q_r')=v_r'$
7.1 Details and Security proofs
这里记多项式求值关系为$\mathcal R_{poly}$，查表关系记为$\mathcal R_{lookup}$，查表实例的多重折叠方案构造如下（这里假设$\mu=1$，参数$\nu$任意）
首先是初始化算法和密钥生成算法
- $\mathcal G\rarr pp$：这里初始化算法选择大小参数$l$，令$pp=l$即可
- $\mathcal K(pp,\tilde T)\rarr (pk,vk)$：令$pk=(pp,\tilde T),vk=pp$即可，实际上$pk=(l,\tilde T),vk=l$
然后Verifier选择一个多项式求值实例$(q_r,v_r)$，以及一个查找向量$(v_1,\dots,v_m)$，Prover对应的witness向量为$(q_1,\dots,q_m)$，协议流程如下图所示
这里可以看一下协议的完美完备性，假设双方刚开始的$\mathcal R_{poly}$的实例为$(q_r,v_r)$，根据nutshell中提到的点，此时有$v_r=\tilde T(q_r),v_i=\tilde T(q_i)$，此时对于Verifier选择的随机值$\rho$，根据定义，有
$$ \begin{aligned} v_r+\sum_{i\in[m]}\rho^i\cdot v_i&=\tilde T(q_r)+\sum_{i\in[m]}\rho^i\cdot \tilde T(q_i)\\ &=\sum_{x\in\{0,1\}^l}\Big( \widetilde{eq}(q_r,x)\cdot \tilde T(x)+\sum_{i\in[m]}\rho^i\cdot\widetilde{eq}(q_i,x)\cdot \tilde T(x)\Big)\\ &=g(x) \end{aligned} $$
和CCS的完备性一样，根据和校验协议的完备性，此时有$c=g(q_r')$，因此对于$v_r'=\tilde T(q_r')$，记$e=\widetilde{eq}(q_r,q_r'),e_i=\widetilde{eq}(q_i,q_r')$，此时有
$$ \begin{aligned} c&=g(q_r')\\ &=\widetilde{eq}(q_r,q_r')\cdot \tilde T(q_r')+\sum_{i\in[m]}\rho^i\cdot \widetilde{eq}(q_i,q_r')\cdot \tilde T(q_r')\\ &=e\cdot v_r'+\sum_{i\in[m]}\rho^i\cdot e_i\cdot v_r' \end{aligned} $$
根据协议，上述等式成立意味着Verifier没有终止协议，此时根据协议构造，有$v_r'=\tilde T(q_r')$，从而满足多项式求值的实例，证毕
知识合理性的分析可以看原文，大致思路和CCS的一样，通过构造抽取器来抽取出知识
References
$[1]$ HyperNova: Recursive arguments for customizable constraint systems (iacr.org)
$[2]$ 多项式扩展与和校验协议 - 三两老友杂的小岛 (snowolf0620.xyz)
$[3]$ Spartan：满足透明性的通用高效zkSNARK方案 - 三两老友杂的小岛 (snowolf0620.xyz)
$[4]$ Nova：Overview - 三两老友杂的小岛 (snowolf0620.xyz)