halo2 中文手册 (The halo2 Book · 简体中文版)

译自 halo2 book：background/recursion.md

递归(recursion)

替代术语：归纳(Induction)；累加方案(Accumulation scheme)；携带证明的数据(Proof-carrying data)

然而，$G$ 的计算需要一个长度为 $2^k$ 的多重幂运算(multiexponentiation) $⟨\mathbf{G},\mathbf{s}⟩,$ 其中 $\mathbf{s}$ 由按二进制计数结构排列的各轮挑战 $u_1,\cdots ,u_k$ 组成。这就是我们想要在一批证明实例上分摊(amortise)的线性时间计算。我们注意到，与其计算 $G,$ 不如把 $G$ 表达为对某个多项式的承诺

$$G=\text{Commit}(\sigma ,g(X,u_1,\cdots ,u_k)),$$

其中 $g(X,u_1,\cdots ,u_k):={\prod }_{i=1}^k(u_i+u_i^{-1}{X}^{2^{i-1}})$ 是一个次数为 $2^k-1$ 的多项式。

由于 $G$ 是一个承诺，它可以在一个内积论证中被检查。验证者电路见证(witness) $G$，并把 $G,u_1,\cdots ,u_k$ 作为公开输入(public inputs)带出到证明 $\pi .$ 下一个验证者实例使用内积论证检查 $\pi$；这包括检查 $G=\text{Commit}(g(X,u_1,\cdots ,u_k))$ 在某个随机点处求值为给定挑战 $u_1,\cdots ,u_k$ 所对应的期望值。回忆 上一节 中讲过，这个检查只需要 $\log d$ 的工作量。 在检查完 $\pi$ 和 $G$ 之后，电路剩下一个新的 $G^{\prime },$ 连同为该检查采样的 $u_1^{\prime },\cdots ,u_k^{\prime }$ 挑战。要完全接受 $\pi$ 为有效，我们应当执行 $G^{\prime }=⟨\mathbf{G},{\mathbf{s}}^{\prime }⟩$ 的线性时间计算。我们再次延迟这个计算，方法是见证 $G^{\prime }$ 并把 $G^{\prime },u_1^{\prime },\cdots ,u_k^{\prime }$ 作为公开输入带出到证明 ${\pi }^{\prime }.$ 这样从一个证明实例进行到下一个，直到我们对这批证明的规模感到满意为止。最后我们执行单个线性时间计算，从而判定整批证明的有效性。

我们回忆 曲线环(Cycles of curves) 一节，我们可以在一个 2-环上实例化这个协议，其中由一条曲线产生的证明能在另一条曲线的电路中被高效验证。然而，其中某些验证者检查实际上可以在本地电路(native circuit)中高效执行；这些检查被"推迟(deferred)"到下一个本地电路（见下图），而不是立即传递给另一条曲线。