Abstract
之前已知的递归证明方案都需要基于配对的椭圆曲线，且需要可信设置
本文利用基于ECC的DLOG假设，实现了Halo协议，可在无需可信设置的条件下实现递归证明
1 Introduction
zk-SNARK的一个典型应用场景是可验证计算，利用这一特点，可以将计算委托给不受信的第三方，之后第三方返回计算结果以及对应的正确性证明
理想情况下，zk-SNARK希望证明大小比直接完成计算要小得多，验证证明也要比直接计算的计算开销要小得多，这也是zk-SNARK最主要的特性——简洁性的要求，利用这一点我们甚至可以证明一个包含大量计算量的计算任务
zk-SNARK的另一个场景是IVC（增量可验证计算），IVC在区块链场景中用的比较多，因为区块链中通常只需要验证和处理更新的状态变化，利用SNARK可以解决区块链上可扩展的问题（相关内容可以看之前的Nova系列）
基于此，本文提出了Halo协议，可在无需可信设置的条件下实现递归证明组合，Halo协议采用循环椭圆曲线（cycle of elliptic），可以使得用一条曲线构造的证明可以有效的验证另一条曲线上的证明
2 Preliminaries
需要知识论证的相关前置知识，具体可以看之前的博客
- $\lambda$：安全参数
- $p$：大素数
- $\mathbb F_p$：素数域
- $\mathbb G$：阶为$p$的群
- $\mathbb I\sub\mathbb F^\times$：Verifier的挑战空间，大小为$2^\lambda$
- $a,b,c$：小写字母表示标量
- $G,H$：大写字母表示群元素
- $\mathbf a,\mathbf G$：加粗表示对应的向量
- $\mathcal O$：群$\mathbb G$的加法单位元
- $\lang \mathbf a,\mathbf b \rang$：标量向量内积
- $\lang \mathbf a,\mathbf G \rang$：标量与群元素向量内积
- $\mathbf G_{lo},\mathbf G_{hi}$：lo表示向量的前半部分，hi表示后半部分
此外，本文采用DLOG假设，要求对于$n\geq 2$，任意敌手$\mathcal A$满足下列不等式
$$ Pr[\mathbf G\larr \mathbb G^n;\mathbf a\in \mathbb F^n\larr \mathcal A(\mathbb G,\mathbf G):\exist \mathbf a_i\neq 0\wedge \lang \mathbf a,\mathbf G\rang=\mathcal O]\leq negl(\lambda) $$
3 Polynomial Commitments
多项式承诺为一个算法四元组$(\mathrm {Setup},\mathrm {Commit},\mathrm {Open},\mathrm {VerifyOpen})$，
- $\mathrm {Setup}(1^\lambda,d)$：$d$表示多项式阶的界，算法输出CRS串$\sigma=(\mathbb G,\mathbb F_p,\mathbf G,H)$，其中$\mathbf G$为长度为$d$的随机群元素向量
- $\mathrm{Commit}(\sigma,p(X);r)=\lang \mathbf a,\mathbf G\rang+[r]\cdot H$：利用盲因子$r$对多项式$p(X)$进行承诺，其中$\mathbf a$为多项式$p$的系数向量
- $\mathrm {Open}$
- $\mathrm{VerifyOpen}$
上述承诺方案为Pedersen承诺，满足完美隐藏性和加法同态
此外，这个方案还可以是一个关于下列关系的知识论证
$$ \big\{ ((P,x,v);(\mathbf a,r)):P=\lang \mathbf a,\mathbf G\rang +[r]\cdot H\wedge v=\lang \mathbf a,(1,x,x^2,\dots,x^{d-1})\rang \big\} $$
利用上述承诺方案，Prvoer可以证明多项式在点$X=x$处的求值
3.1 Protocol Description
对于多项式承诺$P$，和声明的在点$x$处揭示的值$P(x)=v$，Verifier首先选择一个随机群元素$U$发送给Prover，双方计算$P'=P+[v]\cdot U$
之后Prover证明其知道一个向量$\mathbf a$和标量$r,v'$，满足
$$ P'=\lang \mathbf a,\mathbf G \rang+[r]\cdot H+[v']\cdot U \tag 1 $$
其中$v'=\lang \mathbf a,(1,x,x^2,\dots,x^{d-1}) \rang$，由于$U$是Verifier随机选择的，Prover事先不知道，因此有$v=v'$
这里回顾一下Bulletproof中的内积论证，主要是证明Prover知道两个向量$\mathbf a,\mathbf b$，满足
$$ P'=\lang \mathbf a,\mathbf G\rang + \lang \mathbf b,\mathbf H\rang +[\lang \mathbf a,\mathbf b\rang ]\cdot U $$
不难看出Bulletproof和上面的式1很像，只不过上面式1中的向量$\mathbf b=(1,x,x^2,\dots,x^{d-1})$，且$\mathbf b$是双方已知的（因为需要在点$x$处揭示该多项式）
不过这样一来式2第二项中的生成元向量$\mathbf H$就不是必须的了，这里将其替换为一个生成元$H$即可，同样可以实现完美绑定性
假设$d=2^k$，Prover首先构造$\mathbf G'=\mathbf G,\mathbf a'=\mathbf a,\mathbf b'=\mathbf b$，和Bulletoproof类似，需要递归进行若干轮的处理，在第$j$轮中，Prvoer选择盲因子$l_j,r_j$，计算$L_j,R_j$如下
$$ \begin{aligned} L_j&=\lang\mathbf a'_{lo},\mathbf G'_{hi} \rang+[l_j]\cdot H+[\lang\mathbf a'_{lo},\mathbf b'_{hi} \rang]\cdot U\\ R_j&=\lang\mathbf a'_{hi},\mathbf G'_{lo} \rang+[r_j]\cdot H+[\lang\mathbf a'_{hi},\mathbf b'_{lo} \rang]\cdot U \end{aligned} $$
之后Verifier选择一个挑战元素$u_j\in \mathbb I$并发送给Prover，Prover根据$u_j$计算下列三个元素
$$ \begin{aligned} \mathbf a'&\larr \mathbf a'_{hi}\cdot u^{-1}_j+\mathbf a'_{lo}\cdot u_j\\ \mathbf b'&\larr \mathbf b'_{lo}\cdot u^{-1}_j+\mathbf a'_{hi}\cdot u_j\\ \mathbf G'&\larr \mathbf a'_{lo}\cdot u^{-1}_j+\mathbf a'_{hi}\cdot u_j \end{aligned} $$
这三个元素会用于下一轮的计算
经过$j$轮的迭代，最后$\mathbf a',\mathbf b',\mathbf G'$的长度会减小至1，这里注意一点，Verifier可以利用内积式$\lang\mathbf s,\mathbf G \rang,\lang\mathbf s,\mathbf b \rang$自己计算$G=\mathbf G'_0,b=\mathbf b'_0$，其中$\mathbf s$如下
然后Verifier计算一个$Q$如下
$$ Q=\sum^k_{j=1}([u^2_j]\cdot L_j)+P'+\sum^k_{j=1}([u^{-2}_j]\cdot R_j) $$
Prover计算盲因子$r'$如下
$$ r'=\sum^k_{j=1}(l_j\cdot u^2_j)+r+\sum^k_{j=1}(r_j\cdot u_j^{-2}) $$
满足
$$ \begin{aligned} Q&=[a]\cdot G+[r']\cdot H+[ab]\cdot U\\ &=[a]\cdot (G+[b]\cdot H)+[r']\cdot H \end{aligned}\tag 2 $$
如果需要让揭示满足零知识性的话，Prover上述通过式2，在不揭示$a,r'$的情况下证明了$a,r'$的知识，这里可以用一个广义化的Schnorr协议来提高效率
首先Prover选择随机性$d,s$，计算并向Verifier发送$R=[d](G+[b]\cdot U)+[s]\cdot H$，Verifier返回一个随机挑战$c\in \mathbb I$，Prover随后计算
$$ \begin{aligned} z_1=ac+d\\ z_2=cr'+s \end{aligned} $$
Verifier验证等式$[c]Q+R=[z_1]\cdot (G+[b]U)+[z_2]H$，当且仅当等式成立时接受Prover
上述协议满足完美完备性，计算证据扩展仿真性和特殊诚实Verifier零知识性，证明可参考原文附录A
3.2 Amortization Strategy
上述协议中尽管通信开销与多项式的阶呈对数关系，但是其渐进性比较差，因为Verifier的验证过程中需要计算$G=\lang \mathbf s,\mathbf G\rang,b=\lang \mathbf s,\mathbf b\rang$
为了优化这一问题，利用$\mathbf s,\mathbf b$的结构，定义一个新的多项式
$$ g(X,u_1,u_2,\dots,u_k)=\prod^k_{i=1}(u_i+u^{-1}_i\cdot X^{2^{i-1}}) $$
满足$b=b\lang \mathbf s,\mathbf b\rang=g(x,u_1,u_2,\dots,u_k)$，这样一来，Verifier就可以在对数时间内计算$b$
注意到$G=\mathrm {Commit}(\sigma,g(X,u_1,u_2,\dots,u_k))$，因此与其让Verifier自己为多个论证分别计算$G$，不如让一个不可信的第三方计算来计算$G_1,G_2,\dots,G_m$，然后通过这些$G_i$的揭示的随机线性组合来证明计算的正确性
4 Nested Amortization
实现递归证明组合的一般方法是首先获得算术电路可满足性的非交互式知识自变量，然后将该自变量的验证算法编码到对应的算术电路中
假设证明的验证电路在证明所引起的电路大小上是亚线性的，那么在某个阈值下，就有可能递归地验证证明
尽管本文没有可以在亚线性时间内完成验证的协议，但是本文提出了一种新的技术，可以避免在递归的每一层完全验证证明
由于算术电路需要编码至约束系统中，但是这个过程会有一些不确定性，比如可能包含一些昂贵开销的运算，不过这也意味着Prover在允许协助的时候，这些计算可以更有效地执行
举个例子，比如电路中需要计算$u$的逆，此时直接计算$u^{p-2}$的开销为$\log p$，不过Prover可以令$v=u^{-1}$作为witness，然后证明$u\cdot v=1$即可
本文利用这个思想：当$f$中包含一些昂贵开销的运算时，令Prover构造一个witness $y=f(x)$，然后将$(x,y)$作为电路的公共输入，此时电路可以在“假设$y$正确”的条件下执行，并将检查$y$正确性的任务委托给Verifier
本文利用这一优化，确保证明的验证电路不会执行任何的线性时间的运算，而是将这些运算的输入和对应的witness $(x,y)$作为电路的公共输入
不过有一点需要注意：随着证明的不断组合，$(x,y)$的数量也会不断增加，由于验证电路不会检查这些$(x,y)$，而是将检查委托给Verifier
为了防止这种不断增加的情况，本文给出了一种摊销策略：对于给定的实例$(x,y),(x',y')$，Prover提供一个非交互式的证明，以证明$y=f(x),y'=f(x')$作为验证电路的witness，后续Verifier会验证这两个证明
不过新的问题来了，完全检查这些摊销的情况，验证电路可能需要线性时间的操作，不过如果这个操作相当于调用$f$，则意味着Verifier已经将两个实例$(x,y),(x',y')$折叠成一个新的实例$(x'',y'')$，从而允许我们在编写证明时不断摊销$f$的调用开销，最终结果是，只有在电路的外部$f$才会被Verifier调用一次，本文将这种策略称为嵌套摊销（Nested Amortization）
5 Main Argument
本文利用了Sonic协议的一个变体来构建论证
本节中记三个整数$N,Q,k$，满足$d=4N=2^k,3Q<d$，记CRS串$\sigma\larr Setup(1^\lambda,d)$
5.1 Central Argument
回顾一下约束系统，对于witness $\mathbf a,\mathbf b,\mathbf c$和实例$\mathbf k$，第$i$个乘法约束为$\mathbf a_i\cdot \mathbf b_i=\mathbf c_i$，此外还有$Q$个线性约束
$$ \Big( \sum^N_{i=1}\mathbf a_i\cdot (\mathbf u_q)_i\Big)+\Big( \sum^N_{i=1}\mathbf b_i\cdot (\mathbf v_q)_i\Big)+\Big( \sum^N_{i=1}\mathbf c_i\cdot (\mathbf w_q)_i\Big)=\mathbf k_q $$
其中$\mathbf u_q,\mathbf v_q,\mathbf w_q$为编码电路的向量
这两个约束条件可以整合为一个约束等式
$$ \sum^N_{i=1}\mathbf a_i\cdot Y^Nu_i(Y)+\sum^N_{i=1}\mathbf b_i\cdot Y^Nv_i(Y)+\sum^N_{i=1}\mathbf c_i\cdot (Y^Nw_i(Y)-Y^i-Y^{-i})+\sum^N_{i=1}\mathbf a_i\mathbf b_i\cdot (Y^i+Y^{-i})-Y^Nk(Y)=0\tag 4 $$
其中
$$ \begin{matrix} u_i(Y)=\sum^Q_{q=1}Y^q(\mathbf u_q)_i &v_i(Y)=\sum^Q_{q=1}Y^q(\mathbf v_q)_i \\ w_i(Y)=\sum^Q_{q=1}Y^q(\mathbf w_q)_i&k(Y)=\sum^Q_{q=1}Y^q(\mathbf k_q) \end{matrix} $$
这里根据Sonic中的定义，引入第二个变量$X$，并构造下列四个多项式
$$ \begin{aligned} r(X,Y)&=\sum^N_{i=1}\mathbf a_iX^iY^i+\sum^N_{i=1}\mathbf b_iX^{-i}Y^{-i}+\sum^N_{i=1}\mathbf c_iX^{-i-N}Y^{-i-N}\\ s(X,Y)&=\sum^N_{i=1}u_i(Y)X^{-i}+\sum^N_{i=1}v_i(Y)X^i+\sum^N_{i=1}w_i(Y)X^{i+N}\\ s'(X,Y)&=Y^Ns(X,Y)-\sum^N_{i=1}(Y^i+Y^{-i})X^{i+N}\\ t(X,Y)&=r(X,1)(r(X,Y)+s'(X,Y))-Y^Nk(Y) \end{aligned} $$
这里把$t(X,Y)$展开就是式4的左侧
根据Sonic论文里面的结论，由于$r(X,Y)=r(XY,1)$，Prover可以对$r(X,Y)$进行承诺，由于$r(X,Y)$不取决于witness向量$\mathbf a,\mathbf b,\mathbf c$，一般的策略是Prover向Verifier发送$r(X,Y)$的承诺，并证明$t(X,Y)$的常数项为零多项式
此时Verifier会选择随机性$y\in \mathbb I$，并要求Prover对$t(X,y)$承诺，之后Verifier选择随机性$x\in \mathbb I$，Prover揭示$a=r(x,1),b=r(x,y),t=t(x,y)$，Verifier验证等式
$$ t=a(r+s'(x,y))-k(y) $$
若Prover可以向Verifier证明$r(X,Y)$的承诺在$N$上有界，则表明$t(X,Y)$的常数项为式4的左侧，若该常数项为零，则表明式4成立
接下来看一下如何承诺这三个多项式
对于$r(X,Y)$，Prover选择盲因子$\delta_R$，计算承诺值$R=\mathrm {Commit}(\sigma,r(X,1)X^{3N-1};\delta_R)$，此时阶会被限制为$d-1=4N-1$，后续揭示承诺时Verifier只需要对揭示值缩放一个$X^{-3N+1}$即可
对于$t(X,y)$，注意到$t(X,y)$中$X$的幂次范围为$X^{-4N}$到$X^{3N}$，且常数项为零，这里可以令两个阶为$d-1$的多项式$t_{lo}(X,y),t_{hi}(X,y)$，满足
$$ t(X,y)=t_{lo}(X,y)X^{-d}+t_{hi}(X,y)X $$
此时Prover选择盲因子$\delta_{lo},\delta_{hi}$，分别计算承诺值$T_{lo}=\mathrm {Commit}(\sigma,t_{lo}(X,y);\delta_{lo}),T_{hi}=\mathrm {Commit}(\sigma,t_{hi}(X,y);\delta_{hi})$，由于多项式承诺方案的界，这两个承诺可以视为常数项为零的洛朗多项式的承诺，与$r(X,Y)$类似，Verifier需要对承诺的揭示进行一些缩放
对于$k(Y)$，本文的方法可以让双方更有效地计算$K=\mathrm{Commit}(\sigma ,k(Y))$，这样Prover可以代替Verifier在点$y$处揭示承诺，而非要求Verifier计算$k(y)$
此外，还需要关注$s'(x,y)$的求值摊销，由于Verifier必须对$s'(x,y)$求值才能接受Prover，这里本文的方案是引用了Sonic中的方法
Sonic中，Prover在Verifier选择$x$之前发送承诺值$S=\mathrm {Commit}(\sigma,s(X,y)X^N)$，并在点$x$处揭示承诺值，Verifier将揭示值缩放$x^{-N}$后即可得到$s(x,y)$，并利用这个值计算$s'(x,y)$，不过这里仍然需要Verifier检查承诺值$S$是否正确，这个检查过程的开销通常与电路大小呈线性阶
本文的解决方案是引用了Sonic中第八节的方法：每个论证都会产生一个值$y_{new}$和声称等于承诺值$\mathrm{Commit}(\sigma,s(X,y_{new}X^N)$的值$S_{new}$，这里记上一个论证的值为$(y_{new},S_{new})$
然后Prover利用Verifier选择的随机性$x$，计算并发送承诺值$C=\mathrm{Commit}(\sigma,s(x,Y)x^N)$，并在$y_{old},y$处揭示$C$，在$x$处揭示$S_{old},S$，此时假设$C$为正确多项式的承诺，则以高概率意味着每个承诺都是对正确多项式的承诺值
此时Verifier需要选择随机性$y_{new}\in \mathbb I$，并请求Prover计算承诺值$S_{new}=\mathrm {Commit}(\sigma,s(X,y_{new})X^N)$，之后Prover证明$S_{new}$在$x$处揭示的值与在$y_{new}$揭示$C$的值相同，然后Verifier采用这两个新的值$(y_{new},S_{new})$进行后续的论证
5.1 Combining Poly Comm Opening Argument
目前为止，协议的双方都必须参与几个独立的多项式承诺揭示论证，承诺值$R,S_{old},S,S_{new},T_{lo},T_{hi}$都需要在点$x$处揭示，承诺值$K,C$需要在$y$处揭示，$R$需要在$xy$处揭示，$C$需要在$y_{old},y_{new}$处揭示
这里本文利用KZG10中的批量承诺揭示，Verifier选择一个随机性$z_1$，并构造线性组合如下
$$ \begin{aligned} P&=R+[z_1]S_{old}+[z_1^2]S+[z_1^3]S_{new}+[z_1^4]T_{lo}+[z_1^5]T_{hi}=\mathrm {Commit}(\sigma,p(X))\\ Q&=K+[z_1]C=\mathrm{Commit}(\sigma,q(X)) \end{aligned} $$
这里为了将五个不同的揭示减少至一个，本文引入了[3]中的技术，对于$m$个承诺$(E_0,\dots,E_{m-1})$对应的$m$个不同的求值点$(x_0,\dots,x_{m-1})$，其中$E_i=\mathrm {Commit}(\sigma,e_i(X))$，定义多项式$h(X,Y)$如下
$$ h(X,Y)=\sum^{m-1}_{i=0}Y^i\frac{e_i(X)-v_i}{X-x_i} $$
其中每个承诺值$E_i$在对应的点$x_i$处的揭示值为$v_i$
Prover发送每个揭示值$v_i=p_i(x_i)$，并给出一个随机挑战$z_2$，Prover利用盲因子$\delta_H$，计算并发送承诺$H=\mathrm{Commit}(\sigma,h(X,z_2);\delta_H)$
为了证明$H$与之前承诺的正确性，Prover需要在Verifier的随机挑战$z_3$下揭示$P,Q,R,C,H$，由于$P,Q,R,C$在挑战$z_2,z_3$选择之前是固定的，因此$H$有极高概率是正确的承诺值
为了将$z_3$处的$P,Q,R,C,H$承诺揭示合并为单次揭示，这里利用了之前的方法，由Verifier选择随机挑战$z_4$，然后Prover在$P+[z_4]Q+[z_4^2]R+[z_4^3]C+[z_4^4]H$处揭示即可
5.2 Amortizing the Eval of G
回顾一下3.2节，Verifier需要计算内积$G=\lang \mathbf s,\mathbf G\rang$，注意到$G$的计算与$|C|$呈线性关系，采用与之前类似的思想来降低计算开销
首先Prover声称$G\in \mathbb G$，对于每个论证中的值$G_{new}=G$及其对应的挑战$(u_{new})_1,(u_{new})_2,\dots,(u_{new})_k$，此时Verifier不检查承诺值$G_{new}$，而是要求Prover在下一个论证中，在一个随机点$x\in \mathbb F$处揭示承诺值
这里记$(G_{old},(u_{old})_1,(u_{old})_2,\dots,(u_{old})_k)$为$(G_{new},(u_{new})_1,(u_{new})_2,\dots,(u_{new})_k)$之前的值，此时将$P$修改为
$$ P=R+[z_1]S_{old}+[z_1^2]S+[z_1^3]S_{new}+[z_1^4]T_{lo}+[z_1^5]T_{hi}+[z_1^6]G_{old} $$
此时也可以在一个式子内将$G_{old}$在点$x$处揭示
5.3 Protocol
协议如下图所示（有点小，可以看原文第17页的图1），这里协议经过FS变换得到的非交互式协议
References
$[1]$ Sean Bowe, Jack Grigg, Daira Hopwood:Halo: Recursive Proof Composition without a Trusted Setup. IACR Cryptol. ePrint Arch. 2019: 1021 (2019)
$[2]$ Doubly-efficient zkSNARKs without trusted setup (iacr.org)
$[3]$ Dan Boneh, Justin Drake, Ben Fisch, Ariel Gabizon:Efficient polynomial commitment schemes for multiple points and polynomials. IACR Cryptol. ePrint Arch. 2020: 81 (2020)