# 递归与结算

> 由数百个分片组成的基础证明，如何变成一份由合约检查的 Groth16 证明。远地虚拟机证明它自己的验证者、让这件事变得低成本的 tape、贯穿整棵树的 transcript 链，以及不断折叠、直到只剩一个的配对。

一个以太坊区块的基础证明由 207 个分片证明组成：14.5 MB，每个分片都是一份 GKR 证明，带着它的承诺，以及一次以配对检查收尾的 Mercury 打开。合约无法直接检查其中任何一项。递归负责压缩它，而递归的做法，是仅次于 GKR 引擎本身的、影响最深远的设计选择。

## 基础证明保持不变

第一个决定，是递归*不*做什么。没有任何基础密钥、陈述或证明为了支持递归而改变：叶节点验证基础分片的方式，与原生验证者完全相同。递归所需的一切都添加在基础证明之上，从不进入其内部。同一个块（block）的同一份字节，可以原生验证，可以递归，也可以两者兼做。

## 远地虚拟机证明它自己的验证者

树的**节点**就是远地虚拟机在证明一个验证者程序。**叶节点**验证一段连续的基础分片，从 `from` 到 `to`；内部**节点**验证二到四个子节点，每个子节点都是叶程序或节点程序的一份完整证明；**根节点**覆盖全部基础分片。每个节点都由证明基础块的同一个流式证明者来证明。

把 Rust 验证者作为 RISC-V 指令运行是可行的，实测验证一个区块的 207 个分片需要 30 亿个周期：是该区块本身的十五倍。所以节点改为在**递归格式**中运行。

## 递归格式

当且仅当一个陈述的程序声明了域电路族时，该陈述采用递归格式。该格式增加一个地址空间和基于它的四个协处理器电路族，全部通过普通的委托 ABI 调用，除此之外不做任何改变：

| 电路族 | 一行是 |
| --- | --- |
| `FIELD_WINDOWS` | 一个**域单元**：存放一个完整 `Fr` 元素的内存单元，与 RAM 处于同一个内存多重集中 |
| `FR_OP` | 一次作用于单元的域运算：乘、加、减、乘累加、求逆、断言相等，以及构造常量的步骤 |
| `P2_FIELD` | 一次作用于单元的 Poseidon2 双工步骤，所以 transcript 以每次置换一行的速度运行 |
| `FIELD_IO` | 把八个 RAM 字装入一个单元，或把一个单元拆回八个字 |
| `FQ_OP` | 一次 BN254 基域运算，一个元素由四个存放 64 位 limb 的单元组成，所以曲线算术以每次域运算一行的速度运行 |

另有两处改动，让父节点验证递归分片的成本更低。它的内存列和见证列以至多 `2^24` 个求值的**堆叠**形式承诺，所以父节点只需折叠少数几个点，而不是数百个。此外，递归请求写回的帧基地址会越过该帧向前推进，所以首尾相接排布的帧可以作为首尾相接的 `ecall` 重放，每次调用一行。

## Tape

对给定的电路族和高度，一个分片的检查具有固定的形状。所以宿主程序（host）把它们一次性编译成一条 **tape**：一个作用于绝对单元地址的直线式协处理器调用列表，其中没有任何东西根据值来分支。分片的 tape 与原生验证者对该分片执行的步骤逐个调用对应：分片 transcript、GKR 反向过程、查找（lookup）与根的检查，以及 Mercury 打开的十二个标量。每项检查都是一次断言相等。

每个递归程序的 tape、折叠模板和常量，都在编译时由验证者 crate 自己构建，并放进程序的只读数据中。因此，程序身份绑定了该程序重放的每一条 tape：证明一个节点运行了它的程序，就是证明它恰好运行了这些检查。

## 贯穿整棵树的 transcript 链

基础陈述的全局 transcript 是覆盖整个陈述的一个海绵。递归树把它拆开，但不改变它。持有分片 0 的节点运行前缀部分，直到公开输入摘要为止；每个节点从其前驱留下的状态继续，吸收它自己那些分片的内存承诺；持有最后一个分片的节点运行后缀部分，并抽取内存挑战，而这些挑战此前在每个节点中都被当作断言接受。节点的公开输出（journal）记录链在其区间两端的状态，父节点要求其各个子节点的状态首尾相接。

节点还要求它的各个子节点彼此一致：退出状态为 0；同一个基础陈述（其形状、摘要、挑战、输入与公开输出的摘要、退出状态和分片数）；相邻的分片区间；首尾相接的链状态；跨越接缝处按顺序排列的时间窗口；以及递归程序的程序身份。持有整个陈述的节点完成内存论证。

## 折叠配对

没有任何节点计算配对。每个分片的 Mercury 检查都被延迟为十二个 `(side, scalar, point)` 条目；在分片的 tape 之后，节点自己的 transcript 吸收分片 transcript 的最终状态并抽取权重，每个条目经加权后累加进一对持续更新的点 `(A, B)`，它代表断言 `e(A, [1]_2) = e(B, [x]_2)`。把分片的组合承诺与其各列联系起来的批量检查，也在旁边一并折叠。一个电路族所有分片共享的点，例如 `[1]_1` 和设置承诺，各自只累积一个标量，并且只加入一次。子节点的 `(A, B)` 以一个在其完整公开输出之后抽取的权重加入。

每一侧都是在 `FQ_OP` 上执行的一次多标量乘法，以静态模板运行：基于 GLV 分解后的两半、采用 8 位数位的 Pippenger 算法，每个点都被约束在曲线上，每一步都事先固定。每个点的成本约为 400 次 `FQ_OP` 调用。

到了根节点，整棵树的全部内容都已坍缩：每个基础分片都已验证，transcript 已从头到尾运行完毕，内存论证已经完成，每次打开都已折叠成一个配对断言。剩下的只有这个断言和两个程序身份。

## 判定器

根节点仍然是一份 GKR 证明加上数百个点，合约无法检查。**判定器**是一个 Groth16 电路：它通过一个写出秩 1 约束（而不是协处理器调用）的驱动程序，对唯一的子节点，即根节点，运行节点流程，并要求根节点的公开输出对应全部基础分片区间。它不折叠任何东西：根节点欠最终配对的每个点连同其标量，都成为一条**绑定线**，即由验证者持有的一个值，在证明中以第五个陷门承诺，而不是作为公开输入传递。两个程序身份、基础退出状态，以及逐字节的基础公开输入和公开输出，也都是这样处理的。

远地虚拟机的 Groth16 与教科书版本有三处不同：绑定线承诺、没有盲化，以及证明密钥建立在 powers-of-tau 仪式已经公布的 Lagrange 基之上。它的密钥来自一个两阶段仪式：第一阶段就是承诺所依据的同一个仪式文件；第二阶段专属于这个电路，对 `α` 和 `β` 的贡献要在对 `γ`、`δ` 和 `η` 的任何贡献之前完成，而这个顺序本身就是可靠性的一部分。

`ApogeeVerifier.sol` 根据 calldata 重建被绑定的值，检查 Groth16 等式，用 `ecMul` 和 `ecAdd` 折叠两侧的点（这同时要求每个点都在曲线上），然后检查剩下的那一次配对。它的构造函数固定密钥、仪式的两个 G2 点以及两个递归程序的程序身份。一次部署服务于一个基础程序、一种根的形状和固定的公开值长度。

## 实测数据

第 257,510 号区块；递归树在一台 32 CPU 的机器上运行，仪式和判定器在一台 18 核笔记本电脑上运行：

| | |
| --- | --- |
| 基础证明 | 207 个分片，14.5 MB，2,481 s |
| 递归树 | 4 个叶节点（每个至多 64 个基础分片）和一个根节点：共 116 个分片 |
| 叶节点，四个同时进行 | 21、24、23 和 27 个分片；2,157 s；峰值 92 GiB |
| 根节点 | 21 个分片，460 s，1.03 MB |
| 判定器 | 7,896,686 个约束；证明耗时 18.5 s，占用 6.1 GB |
| 合约 | 358 个点；3,620,026 gas；34,980 字节 calldata |

规范见[递归与判定器](https://apogee.gweb3networks.com/docs/auditors/spec/recursion)。亲自运行一遍：[链上结算](https://apogee.gweb3networks.com/docs/launch/on-chain)。