13. Plonky3 深入：高元 FRI、Batch-STARK、LogUp 与原生递归

发表于 2026/07/29 更新于 2026/07/29

作者 Chen Xichao

36 分钟阅读

版本口径：主仓库快照 66e2906；递归仓库快照 b36339709a7a67ee9760fb578b3d4339fd983709。后者处于 active development 且官方明确标注未审计、不建议生产使用。

1. 当前 Plonky3 的证明主线

一份典型当前系统可写为：

\[\boxed{ \text{AIR instances} \xrightarrow{\text{Uni/Batch STARK}} \text{PCS openings} \xrightarrow{\text{FRI/Circle/other PCS}} \pi. }\]

若有跨表交互：

\[\text{AIR} +\text{LogUp permutation trace}.\]

若做递归：

\[\pi_i \xrightarrow{ \text{fixed verifier circuit + circuit STARK} } \pi_{i+1}.\]

它与 Plonky2.5 的最大区别是：

Plonky2.5：外层是 Plonky2 PLONKish + FRI；
当前官方 Plonky3 recursion：外层仍由 Plonky3 STARK primitives 构造。

2. 当前 FRI 参数不只是 queries 与 blowup

FriParameters<M> 包含：

参数	含义
`log_blowup`	LDE blowup $B=2^{b}$，code rate $\rho=2^{-b}$
`log_final_poly_len`	early stopping 后 final polynomial length 的 log
`max_log_arity`	每轮最大 fold arity 的 log
`num_queries`	query indices 数
`commit_proof_of_work_bits`	每个 commit-phase round 在采样 fold challenge 前的 grinding
`query_proof_of_work_bits`	所有 query indices 采样前的 grinding
`mmcs`	FRI layer commitments

2.1 final height

若 final polynomial length：

\[L_f=2^{\ell_f},\]

FRI evaluation vector 最终高度是：

\[B L_f = 2^{b+\ell_f}.\]

因为即使 polynomial degree 已降到 $L_f$，codeword 仍按 blowup $B$ 编码。

2.2 为什么有两类 PoW

commit-phase PoW 的顺序：

\[C_i \to \mu_i^{\mathrm{commit}} \to \beta_i.\]

query-phase PoW：

\[\text{all commitments/final polynomial} \to \mu^{\mathrm{query}} \to q_0,\ldots,q_{k-1}.\]

第一类降低某些 round-by-round commit challenge grinding 风险；第二类在 queries 生成前加入独立工作量。

3. 动态高元 FRI

3.1 输入可有多个高度

PCS opening reduction 可能产生：

\[f^{(0)},f^{(1)},\ldots,f^{(s-1)}\]

且：

\[|f^{(0)}| \ge |f^{(1)}| \ge\cdots\ge |f^{(s-1)}|.\]

FRI 先折叠最高的 vector；当高度降到下一 input 的高度时，再把该 input 随机注入。

3.2 每轮 arity 不是任意 proof 数据

设当前 log-height 为 $h$，下一 input log-height 为 $h_{\mathrm{next}}$，final log-height 为：

\[h_f=b+\ell_f,\]

最大 log arity 为 $a_{\max}$。

当前实现选择：

\[a = \min\Bigl( a_{\max}, h-h_f, h-h_{\mathrm{next}} \Bigr),\]

若没有下一 input，则去掉第三项。

fold arity：

\[A=2^a.\]

这样保证：

不跨过 final height；
每到一个 input height 都产生 commitment/注入点；
每轮都有 $a\ge1$，持续下降。

3.3 commit 一整个 coset row

当前 evaluations 使用 bit-reversed order，使同一 $A$ 元 fold group 相邻。把 vector reinterpret 成 matrix：

\[M_i \in \mathbb E^{(|f_i|/A)\times A}.\]

每一 row 是一个 $A$ 元 coset 的全部 evaluations。MMCS 承诺：

\[C_i=\mathsf{MMCS.Commit}(M_i).\]

3.4 challenge 与 fold

吸收 $C_i$、验证 commit PoW 后采样：

\[\beta_i\in\mathbb E.\]

若：

\[f_i(X) = \sum_{j=0}^{A-1} X^j f_{i,j}(X^A),\]

定义：

\[f_{i+1}(Y) = \sum_{j=0}^{A-1} \beta_i^j f_{i,j}(Y).\]

3.5 注入下一高度 input

若 fold 后高度等于下一 input $g$ 的高度，当前实现更新：

\[f_{i+1} \leftarrow f_{i+1} + \beta_i^A g.\]

$\beta_i^A$ 让新注入 polynomial 与本轮已有 $A$ 个 coefficient classes 保持随机线性独立的直觉。

3.6 final polynomial

当 evaluation vector 长度降到：

\[B L_f\]

后：

截取足以恢复 degree $<L_f$ polynomial 的 evaluations；
恢复 normal order；
IDFT 得到 coefficients：

\[f_{\mathrm{final}}(X) = \sum_{j=0}^{L_f-1}c_jX^j;\]

transcript 吸收全部 coefficients。

4. 当前 query phase

4.1 arity schedule 也被 transcript 绑定

commit phase 得到：

\[(a_0,\ldots,a_{r-1}).\]

当前 prover 在 commit phase 结束后把这些 log arities observe 进 transcript；proof 中每轮也带 log_arity，verifier：

检查 $1\le a_i\le a_{\max}$；
检查它与由 heights/final target 导出的 schedule 一致；
重建相同 transcript。

4.2 query indices

完成 query PoW 后采样：

\[q_j \in [0,2^{h_{\max}+e}),\]

其中 $e$ 是 folding scheme 可请求的 extra query bits。

4.3 每轮 sibling 数

若 arity $A_i$，query 所在 group 需要：

\[A_i-1\]

个 sibling values。parent index：

\[q' = q\gg a_i.\]

4.4 multi-proof

对同一 FRI layer 的全部 query groups，MMCS 生成一个 shared multi-proof，而不是 $k$ 条完整 Merkle paths：

\[\pi_{\mathrm{MMCS},i}^{\mathrm{multi}}.\]

共享 ancestors 只发一次。这同时降低：

proof size；
重复 hash；
query collision 造成的冗余。

4.5 fold consistency

verifier：

把 queried value 插回 $A_i-1$ 个 siblings；
验证整 row 属于 $C_i$；
在 $\beta_i$ 下 fold；
shift query index；
必要时注入相应高度的 reduced opening；
最后与 $f_{\mathrm{final}}$ 在归约点的值相等。

flowchart LR
    IN["多个递减高度 inputs"] --> C["commit A 元 rows"]
    C --> POW["commit PoW"]
    POW --> B["sample beta"]
    B --> F["fold by A"]
    F --> J{"到下一 input 高度？"}
    J -->|是| ADD["注入 beta^A × next input"]
    J -->|否| N["下一轮"]
    ADD --> N
    N --> E{"到 final height？"}
    E -->|否| C
    E -->|是| FP["发送 final polynomial"]
    FP --> QP["query PoW + sample queries"]
    QP --> MQ["每层 MMCS multi-open"]

5. FRI 参数的旧 heuristic 与当前安全模型

5.1 简单 heuristic 仍存在

FriParameters::conjectured_soundness_bits() 仍给出：

\[\lambda_{\mathrm{simple}} = b\cdot k+w_q,\]

其中：

$b=\texttt{log_blowup}$；
$k=\texttt{num_queries}$；
$w_q=\texttt{query_pow_bits}$。

它对应：

\[\rho^k2^{-w_q}\]

式的简单 conjectural 直觉。

5.2 当前 random-words conjecture 更细

当前 p3-security 的 conjectured FRI 估计令：

\[\rho=2^{-b}\]

并引入：

\[\eta \approx \frac{ \log_2(e/\rho)\cdot\rho }{ \log_2|\mathbb E| }.\]

每个 query 的有效项是：

\[\rho+\eta,\]

所以：

\[\lambda_{\mathrm{conj}} \approx -k\log_2(\rho+\eta)+w_q.\]

最终还受：

\[\log_2|\mathbb E| \quad\text{和}\quad \lambda_{\mathrm{hash}}\]

截断。

5.3 proven model 分 UDR 与 LDR

当前实现依据 round-by-round 分析分别计算：

unique-decoding regime；
list-decoding regime，并搜索一个 proximity 参数 $m$。

对每个 regime，整体 error budget 至少包含：

\[\varepsilon_{\mathrm{ALI}}, \varepsilon_{\mathrm{DEEP}}, \varepsilon_{\mathrm{LDT}}, \varepsilon_{\mathrm{batch}}, \varepsilon_{\mathrm{extras}}, \varepsilon_{\mathrm{collision}}.\]

令 $J_R$ 是 regime $R$ 中所有可导致错误接受的坏事件。若没有一个更强定理证明这些事件彼此嵌套，则可认证的通用合成方式是 union bound：

\[\varepsilon_R^{\mathrm{cert}} \le \sum_{j\in J_R}\varepsilon_{R,j}, \qquad \lambda_R^{\mathrm{cert}} = -\log_2\!\left( \sum_{j\in J_R}2^{-\lambda_{R,j}} \right),\]

其中 $\lambda_{R,j}=-\log_2\varepsilon_{R,j}$。若有 $J$ 个同为 $\lambda$ bits 的项，合成结果是 $\lambda-\log_2J$，而不是仍为 $\lambda$。

固定快照中的 calculator 目前以

\[\lambda_R^{\mathrm{calc}} = \min_{j\in J_R}\lambda_{R,j}\]

作为该 regime 的 binding-term convention；这等价于只取最大的单项 error，而不是对不同坏事件的概率求和。源码同时实现了概率求和所需的 ErrorBits::sum，但 STARK report 当前调用的是 ErrorBits::min。因此 calc 输出应与上面的 strict certified union bound 分开报告；除非引用的 round-by-round theorem 明确给出 max/min 型界，不能把二者当成同一公式。参见固定快照的 error.rs 与 stark.rs。

若 UDR 与 LDR 的各自前提均成立，它们是对同一错误概率分别成立的两条上界，故可取较小 error，也就是较大的 bits：

\[\varepsilon_{\mathrm{proven}}^{\mathrm{cert}} = \min\!\left( \varepsilon_{\mathrm{UDR}}^{\mathrm{cert}}, \varepsilon_{\mathrm{LDR}}^{\mathrm{cert}} \right), \qquad \lambda_{\mathrm{proven}}^{\mathrm{cert}} = \max\!\left( \lambda_{\mathrm{UDR}}^{\mathrm{cert}}, \lambda_{\mathrm{LDR}}^{\mathrm{cert}} \right).\]

calculator 对两个 regime 也使用同样的外层 max(bits) 选择，但其每个 regime 内部仍是前述 min(bits) convention：

\[\lambda_{\mathrm{proven}}^{\mathrm{calc}} = \max\!\left( \lambda_{\mathrm{UDR}}^{\mathrm{calc}}, \lambda_{\mathrm{LDR}}^{\mathrm{calc}} \right).\]

5.4 AIR composition error

若合并 $m_c$ 个 constraints，list-size factor 为 $L^+$：

\[\varepsilon_{\mathrm{ALI}} \le \frac{L^+m_c}{|\mathbb E|}.\]

bits：

\[\lambda_{\mathrm{ALI}} = \log_2|\mathbb E| -\log_2L^+ -\log_2m_c.\]

5.5 DEEP-ALI error

当前 security crate 使用形如：

\[\varepsilon_{\mathrm{DEEP}} \le \frac{ L^+ \left[ d(k+c-1)+(k-1) \right] }{ |\mathbb E| },\]

其中：

$k$ 是 trace domain size；
$d$ 是 max constraint degree；
$c$ 是每列最大的 OOD point combo/rotation 数。

5.6 FRI commit/query error

UDR 下单轮 commit-phase 项粗略含：

\[\varepsilon_{\mathrm{commit}} \lesssim \frac{ (A-1)(n+1) }{ |\mathbb E| } \cdot2^{-w_c},\]

query phase 则形如：

\[\varepsilon_{\mathrm{query}} \le \alpha_{\mathrm{prox}}^k \cdot2^{-w_q}.\]

精确 $\alpha_{\mathrm{prox}}$ 依 UDR/LDR、rate、trace length 与 combo。

5.7 不能漏掉 batched functions

PCS 把多条 committed codewords 随机合并成一个 FRI instance，会增加 proximity-gap batching term。StarkSecurityParams::num_batched_functions 若错误留为 1，会高估安全。

6. Batch-STARK：多个 AIR 共用一份 opening

设有 $s$ 个 instances：

\[\mathcal I_i = (A_i,T_i,\mathbf{pv}_i,\mathcal L_i), \qquad 0\le i<s,\]

其中：

$A_i$ 可不同；
trace width 可不同；
trace height $N_i$ 可不同；
public values 不同；
lookups 可跨 instances。

6.1 proof object

当前 BatchProof 包含：

\[\pi_{\mathrm{batch}} = ( \mathsf{BatchCommitments}, \mathsf{BatchOpenedValues}, \pi_{\mathrm{PCS}}, \mathsf{LookupTerminals}, \mathbf{degreeBits} ).\]

6.2 shared commitments

commitments 包括：

所有 main traces 的单个 batch commitment $C_M$；
可选 permutation/lookup traces commitment $C_P$；
所有 quotient chunks commitment $C_Q$；
可选 ZK randomization commitment $C_R$。

6.3 不同高度

MMCS/PCS 用 mixed-height semantics：

\[q_i = q\gg(h_{\max}-h_i).\]

因此一个 global query block 可同时打开所有 AIR instances。

6.4 transcript structural binding

当前 batch transcript 显式 observe：

instance count；
每个 instance 的 extended/base degree bits；
width；
quotient chunk 数；
main commitment；
所有 public values；
preprocessed widths/commitment。

这防止同一 opened-value flat vector 被重新解释成不同 instance partition。

6.5 一次 PCS opening

所有：

main local/next；
permutation local/next；
quotient chunks；
preprocessed；
randomization

被组织进一个 shared PCS opening proof。

7. LogUp：从 multiset equality 到有理函数和

7.1 lookup 目标

要证明带 multiplicities 的 multisets 相同：

\[\{a_i\}_{m_i} = \{b_j\}_{n_j}.\]

乘积式是：

\[\prod_i(\alpha-a_i)^{m_i} = \prod_j(\alpha-b_j)^{n_j}.\]

取 logarithmic derivative 的代数对应：

\[\sum_i\frac{m_i}{\alpha-a_i} - \sum_j\frac{n_j}{\alpha-b_j} =0.\]

实现把 send multiplicity 记为正，receive 记为负，统一写：

\[\sum_u \frac{\mu_u}{\alpha-v_u} =0.\]

7.2 tuple compression

message 是 tuple：

\[\mathbf e =(e_0,\ldots,e_{w-1}).\]

用 $\beta$ 压成：

\[\phi_\beta(\mathbf e) = \sum_{j=0}^{w-1} e_j\beta^{w-1-j}.\]

denominator：

\[d(\mathbf e) = \alpha-\phi_\beta(\mathbf e).\]

7.3 bus domain separation

当前实现对多个 local/global buses 共用一对基础 challenges，再为 bus 添加 offset。security crate 给出的 fingerprint 形式可写为：

\[d_{b}(\mathbf e) = \alpha + (b+1)\beta^W - \phi_\beta(\mathbf e) = \alpha + (b+1)\beta^W - \sum_{j=0}^{w-1}e_j\beta^{w-1-j},\]

其中：

$b$ 是 bus id，使用该式还要求不同 bus ids 在 challenge field 中有不同编码；
$W$ 是全局最大 message width；
同一 bus 内必须使用固定的声明宽度 $w$；[x] 与 [0,x] 的 polynomial fingerprint 相同，不能靠 $\beta$ 自动区分；
$\beta^W$ bus offset 与最高为 $\beta^{W-1}$ 的 payload 在形式多项式层面分离不同 bus，但在随机抽到某个具体 $\beta$ 后仍可能落在差分多项式的根上。

因此这里的“分离”不是对每个 $\beta$ 都成立的有限域 injectivity。它的正确口径是：固定宽度、不同 bus id 与不同 payload 产生不同的形式多项式；除了 Schwartz–Zippel root event 外，随机 fingerprint 不碰撞。该 root event 已计入第 7.8 节的 LogUp error，而不能用“绝不会混淆”替代概率界。

7.4 每行多个 fractions

若一行有 $r$ 个 interactions：

\[\sum_{i=0}^{r-1} \frac{\mu_i}{d_i}.\]

AIR 不能直接使用除法，所以构造公共 denominator：

\[U=\prod_i d_i,\]

numerator：

\[V = \sum_i \mu_i \prod_{j\ne i}d_j.\]

并用 auxiliary fraction column $f$ 约束：

\[Uf-V=0.\]

prefix/suffix products 可在 $O(r)$ multiplications 内计算所有

\[\prod_{j\ne i}d_j.\]

7.5 running accumulator

每个 AIR 的 permutation trace：

column 0：共享 accumulator；
后续每列：一个 lookup fraction。

约束：

\[\begin{aligned} z_0&=0,\\ z_{r+1} &= z_r+\sum_c f_{c,r},\\ \tau &= z_{N-1}+\sum_cf_{c,N-1}. \end{aligned}\]

$\tau$ 是该 AIR 的 committed terminal。

7.6 cross-AIR 平衡

Batch verifier 检查：

\[\boxed{ \sum_{i=0}^{s-1}\tau_i=0. }\]

global bus 上不同 AIR 的 sends/receives 因此可以互相抵消；local bus 使用独立 id，只能在本 AIR 内平衡。

flowchart TB
    CPU["CPU AIR<br/>send memory tuple"] --> B["Global bus: memory"]
    MEM["Memory AIR<br/>receive tuple"] --> B
    B --> FP["tuple fingerprint<br/>alpha, beta, bus id"]
    FP --> F1["CPU fractions / terminal"]
    FP --> F2["Memory fractions / terminal"]
    F1 --> SUM["sum all AIR terminals"]
    F2 --> SUM
    SUM --> ZERO["constraint: total = 0"]

7.7 characteristic 与 multiplicity no-wrap

LogUp 的 rational identity 在特征为 $p$ 的 base field 上只看得到模 $p$ 的 multiplicity。若一个非法差额恰好是 $p$ 的倍数，它会在域中变成零；换到同特征的扩域并不能修复这一点。

对第 $i$ 个 AIR，令：

$h_i$ 为 trace height；
$w_i$ 为该 AIR 每行所有 query-side count_weight 的总上界。

必须在进入证明前检查严格不等式：

\[\boxed{ \sum_i w_i h_i<p. }\]

同时，AIR 必须逐行约束实际 count/multiplicity 不超过其声明的 weight。只有 host 侧填写 count_weight 元数据、却没有约束 witness 中的 count，并不能建立 no-wrap 结论。当前固定快照在 check_multiplicity_height_bound 中用公开 weights、heights 与精确 characteristic 做此检查；这是一项 soundness 前提，不是一个可忽略的小概率 error term。

7.8 LogUp fingerprint soundness term

设：

每行总 interactions 数为 $r$；
trace length 为 $N$；
最大 tuple width 为 $W$；
challenge field 为 $\mathbb E$。

清除 denominators 后，当前 security module 给出 union-bound 量级：

\[\varepsilon_{\mathrm{LogUp}} \le \frac{ (rN)(W+1) }{ |\mathbb E| }.\]

对应 bits：

\[\lambda_{\mathrm{LogUp}} \ge \log_2|\mathbb E| -\log_2(rN) -\log_2(W+1).\]

它必须作为 extras 纳入整个 STARK security report；没有 lookups 时不应添加一个伪 0-bit 项。

这个界只覆盖随机 $(\alpha,\beta)$ fingerprint 的 root event；它以第 7.7 节的固定宽度、count constraints 与 multiplicity no-wrap 条件成立为前提。

8. Plonky3-recursion 是独立官方项目

当前官方组织下有独立仓库：

\[\texttt{Plonky3/Plonky3-recursion}.\]

其目标是：

在 circuit 中验证 p3-uni-stark proof；
在 circuit 中验证 p3-batch-stark proof；
为该 circuit 生成新的 Batch-STARK proof；
支持多层 chaining；
支持 2-to-1 aggregation；
支持 ZK-enabled configurations。

8.1 不是 Plonky2 wrapper

官方 recursion book 明确区分：

\[\text{Plonky2} = \text{PLONKish outer wrapper},\]

而新 recursion stack：

\[\boxed{ \text{Plonky3 STARK} \text{ verifies } \text{Plonky3 STARK}. }\]

8.2 状态边界

官方 README 同时明确：

active development；
尚未审计；
不建议用于 production。

“官方仓库”不等于“production-ready cryptographic boundary”。

9. 固定 verifier circuit，而不是通用 zkVM

9.1 固定程序

递归 circuit 的程序是：

\[\mathcal P = \mathsf{VerifyP3Proof}_{A,\theta}.\]

其中 AIR、PCS config、proof shape 等在 build time 已知。

它没有通用 VM 的：

program counter；
instruction decoder；
arbitrary branches；
general memory execution semantics。

9.2 为什么固定更快

若每个 operation 已知：

\[o_0,o_1,\ldots,o_{m-1},\]

则：

selectors 可预处理；
witness indices 可预处理；
不必证明 opcode 合法；
不必证明 PC transition；
不必做动态 dispatch；
可针对 verifier 的 hash/field operations 优化 chips。

9.3 代价

固定 shape 意味着：

proof height/parameter 变化可能要新 circuit；
换 AIR/config 需要重建；
arbitrary-length 输入需 lifting/padding/multi-shape 方案；
circuit identity 必须成为公开 statement 的一部分。

10. 从 expression DAG 到 Execution IR

10.1 CircuitBuilder

CircuitBuilder<F> 创建 symbolic expression graph。节点可能是：

constant；
public input；
private input/operation result；
add/sub/mul；
equality connection；
non-primitive operation，例如 Poseidon2 permutation。

10.2 WitnessId

每个运行时 value 由：

\[\operatorname{WitnessId}(i)\]

标识。

例如验证：

\[37x-111=0\]

可 lower 成：

\[\begin{aligned} w_0&=0,\\ w_1&=37,\\ w_2&=111,\\ w_3&=x_{\mathrm{public}},\\ w_4&=w_1w_3,\\ w_4&=w_2+w_0. \end{aligned}\]

最后两条共同强制：

\[37x=111.\]

10.3 IR 本身不是 soundness 来源

Execution IR 是 prover/verifier 约定的固定执行描述，用于：

trace generation；
operation scheduling；
table layout。

真正的证明来自：

每个 operation-specific AIR；
cross-table LogUp consistency；
Batch-STARK；
PCS/FRI。

不能因为 host executor 按 IR 算对了，就省略 AIR/lookup constraints。

11. shared witness memory 没有单独 memory table

11.1 概念内存

把全部 values 看作：

\[\mathcal M = \{(i,w_i)\}.\]

不同 chips 读写同一 WitnessId。

11.2 operation tables

固定 verifier circuit 可产生：

Const table；
Public table；
ALU table；
Recompose table；
Poseidon/Poseidon2 table；
其他 NPO-specific tables。

例如 ALU row：

\[( i_a,a, i_b,b, i_o,o, s_+,s_\times ).\]

局部约束：

\[s_+(a+b-o) + s_\times(ab-o) =0,\]

并约束 selectors 合法/互斥。

11.3 index 预处理

固定 IR 已知每个 operation 使用哪些 ids，所以 index columns：

\[i_a,i_b,i_o\]

可以预处理。运行时只需 witness values。

11.4 LogUp 连接 chips

producer/consumer 各发送或接收：

\[(\operatorname{WitnessId},\operatorname{Value}).\]

跨表 LogUp 强制整个 multiset 平衡：

\[\mathcal S_{\mathrm{writes}} = \mathcal S_{\mathrm{reads}}.\]

不需要一个显式“大内存 trace table”；bus 本身提供 consistency。

flowchart TB
    IR["固定 verifier IR"] --> C["Const chip"]
    IR --> P["Public chip"]
    IR --> A["ALU chip"]
    IR --> H["Poseidon2 chip"]
    C --> B["Witness bus<br/>(id, value)"]
    P --> B
    A --> B
    H --> B
    B --> L["LogUp terminal balance"]
    C --> BS["Batch-STARK"]
    P --> BS
    A --> BS
    H --> BS
    L --> BS

12. 递归 verifier circuit 检查哪些东西

12.1 proof structural data

Uni/Batch proof shape；
degree bits；
AIR width；
quotient chunks；
public/preprocessed schema；
ZK presence fields。

12.2 transcript

commitments；
public inputs；
lookup terminals；
randomization commitments；
FRI commits/final polynomial；
PoW witnesses；
challenge/bit sampling。

12.3 MMCS

input commitments；
FRI layer commitments；
Merkle sibling ordering；
multi-opening roots；
verifier-known dimensions。

12.4 FRI

fold challenge；
dynamic arities；
sibling rows；
query index shifts；
final polynomial evaluation；
proof-of-work。

12.5 STARK identity

AIR at $\zeta$；
first/last/transition selectors；
quotient chunks recomposition；
$C_\alpha(\zeta)/Z_H(\zeta)=Q(\zeta)$；
Batch-STARK 的 lookup terminal balance。

12.6 输出

circuit runner 根据 proof witness 生成每个 chip 的 traces，再用 p3-circuit-prover 生成一个 Batch-STARK proof：

\[\pi_{\mathrm{out}}.\]

flowchart LR
    IN["Inner P3 proof"] --> VC["Fixed recursive verifier circuit"]
    VC --> IR["Execution IR + witness values"]
    IR --> TR["Const/Public/ALU/Poseidon2 traces"]
    TR --> LU["LogUp cross-table consistency"]
    LU --> BP["Batch-STARK prover"]
    BP --> OUT["Outer P3 proof"]

13. 统一递归 API 的层级

13.1 第一层

输入可为 Uni-STARK：

\[\operatorname{RecursionInput} = ( \pi_{\mathrm{uni}}, A, \mathbf{pv}, C_{\mathrm{pre}} ).\]

也可为 Batch-STARK。

13.2 输出

outer circuit 本身按多 chip AIRs 被证明，所以输出是：

\[\operatorname{RecursionOutput} = ( \pi_{\mathrm{batch}}, \mathsf{CircuitProverData} ).\]

13.3 后续层

将上一 output 转成新的 Batch-STARK recursion input：

\[\pi_{i+1} \leftarrow \mathsf{ProveNextLayer}(\pi_i).\]

13.4 statement projection

应用层必须明确决定递归 output 最终投影哪些 public inputs，例如：

inner proof 的公开 statement；
inner verifier/circuit identity；
aggregation children commitments；
layer/domain separator；
application state。

否则 outer proof 只能说明“某个固定 verifier 接受了某个私有 proof”。

但“应用希望只投影 root statement”不等于当前统一 API 已默认如此。固定递归快照的 verifier-input builder 会把上一层 proof 的 commitments、opened values 与 challenges 按固定顺序注册成递归 circuit 的 public inputs；aggregation 则按 left-first、right-second 拼接两边输入。因此这些值对 outer verifier 可见，并不受 outer ZK 的 private-witness hiding 保护。若应用要实现 root-only projection，必须另行设计并证明相应 circuit/interface，而不能只在文档中省略这些字段。参见固定快照的 Public Inputs。

14. 2-to-1 aggregation

一个 aggregation circuit 在同一 CircuitBuilder 中放两个 verifier subcircuits：

\[\mathsf{Verify}(\pi_L)=1, \qquad \mathsf{Verify}(\pi_R)=1.\]

它们可验证：

不同 AIRs；
一边 Uni-STARK、一边 Batch-STARK；
不同 trace shapes，只要 aggregation circuit 固定这些 shapes。

14.1 共享 chips

两边可以共享：

Poseidon2 table；
ALU table；
public table；
lookup buses。

所以总 trace 不一定严格等于两个单 verifier traces 之和，尤其 hash-heavy workload 可共享 table packing。

14.2 聚合树

对 $m$ 份 proofs：

\[\operatorname{depth} = \lceil\log_2m\rceil.\]

同一层的 pairs 可并行。

flowchart TB
    P0["π_0"] --> A0["Agg 0,1"]
    P1["π_1"] --> A0
    P2["π_2"] --> A1["Agg 2,3"]
    P3["π_3"] --> A1
    A0 --> R["Root aggregation proof"]
    A1 --> R
    R --> N["可继续递归/压缩"]

14.3 有序 statement

应使用 domain-separated ordered commitment：

\[h_{\mathrm{root}} = H( \texttt{"p3-agg-v1"}, h_L, h_R ).\]

若应用语义无序，也应明确 canonical sort 规则；不能让 left/right 交换含义不清。

15. TablePacking 的数学成本

设某 chip 有 $m$ 个 operations，分配 $\ell$ 个 lanes。未 padding rows：

\[r = \left\lceil\frac m\ell\right\rceil.\]

实际 STARK trace height padding 到：

\[N = 2^{\lceil\log_2r\rceil}.\]

对多个 chips：

\[N_{\max} = \max_i 2^{ \left\lceil \log_2 \left\lceil\frac{m_i}{\ell_i}\right\rceil \right\rceil }.\]

Batch-STARK 的最大 table height 往往主导：

最大 polynomial degree；
LDE size；
FRI rounds；
proving memory/time。

15.1 增加 lane 的收益

若一个 chip 正好从：

\[r=33{,}000\]

降到：

\[r=16{,}500,\]

padding height 可从：

\[2^{16}\]

降到：

\[2^{15}.\]

这是整整少一层 FRI/一半该表 evaluations。

15.2 lane 不是越多越好

更多 lanes 会：

增加 columns；
增加每行 hash/commit width；
增加 AIR width 与 memory traffic；
可能让另一个 chip 成为 bottleneck。

目标是平衡各 table heights，而不是单独把某张表做到最短。

16. 递归 field/hash 配置是快速演进的

当前 recursion repository 的 README/examples 提供：

KoalaBear；
BabyBear；
Goldilocks

等配置路径，并支持 Poseidon1/Poseidon2 选择。与此同时，book 中某些页面仍写“目前支持两个 31-bit base fields”。这类内部文档差异说明：

\[\boxed{ \text{支持矩阵应以目标 commit 的代码、tests、examples 为准。} }\]

16.1 常见 31-bit recursion config

book 列出的标准形状包括：

\[D=4,\qquad \text{Poseidon2 WIDTH}=16,\qquad \text{RATE}=8.\]

也有 width 24/rate 12 或 base-field challenge variants。

16.2 Goldilocks 形状

roadmap/source 还提到 Goldilocks 常用不同 width/rate，例如：

\[\text{WIDTH}=8,\qquad \text{RATE}=4\]

的方向。不能把 31-bit config constants 复制给 Goldilocks。

16.3 三处必须一致

Poseidon config 必须同时匹配：

native proof/MMCS/challenger；
FriVerifierParams；
circuit builder 启用的 Poseidon operation/AIR。

任何一处 width、rate、round constants 或 extension degree 不同，recursive transcript/commitment 都不兼容。

16.4 WHIR recursion 的状态

递归仓库当前包含 WHIR verifier modules 和 tests，但顶层 unified API/README 的成熟主线仍重点描述 FRI backend。对 WHIR：

“源码存在”；
“测试覆盖某些配置”；
“统一 API 全面支持”；
“审计/生产支持”

是四个不同事实，应逐项核对目标 commit。

17. ZK-enabled recursion

官方递归 README 声明支持 ZK-enabled STARK configurations，包括：

ZK Uni-STARK；
ZK Batch-STARK；
randomization transcript handling；
hiding MMCS paths；
ZK aggregation。

17.1 inner ZK

inner proof 可能包含：

\[C_R,\quad \mathbf r(\zeta)\]

等 randomization fields。recursive verifier circuit 必须像 native verifier 一样检查它们的 presence、transcript 顺序与 PCS opening。

17.2 outer ZK

outer circuit traces 含 inner proof、Merkle paths、challenger state 等输入的函数。只有被注册为 private witness 的部分，才由 outer ZK 隐藏；进入 outer public-input vector 的值不会因为 outer proof 使用 ZK backend 而变成秘密。

若完整 inner proof/view 都是 private witness，只向外安全投影应用 statement，则一个通用的充分条件是：

\[\mathsf{ZK}_{\mathrm{outer}} \land \mathsf{Private}(\operatorname{View}_{\mathrm{inner}}) \land \mathsf{SafeProjection}(\Phi) \Longrightarrow \mathsf{ZK}_{\mathrm{wrapper}}.\]

此时 inner proof 自身不必满足一个独立的 ZK 定义，因为它没有被单独公开。反之，若 $\operatorname{View}_{\mathrm{inner}}$ 的 commitments、openings、challenges 或 transcript 被直接公开，则还需证明 inner scheme 对实际暴露的 view 是 ZK，或把这些字段明确列为允许泄露：

\[\mathsf{ZK}_{\mathrm{inner,exposed}} \land \mathsf{ZK}_{\mathrm{outer}} \land \mathsf{SafeProjection}(\Phi) \Longrightarrow \mathsf{ZK}_{\mathrm{visible\ stack}}.\]

固定快照的统一 API 属于后一种需要单独审计的接口：上一 proof 的 commitments、opened values 与 challenges 会进入 recursive circuit public inputs。outer Batch-STARK 不使用 hiding/ZK PCS 时，连其余 private trace data 也不满足应用期待的隐私；即使 outer 已启用 ZK，上述 public projection 仍然可见。

17.3 聚合 ZK

在重新设计的 root-only aggregation interface 中，可以把 children proofs 全部作为 private witness，只公开 root statement commitment。此时必须确保：

root 不泄露 child order 之外的意外信息；
public-input packing 是 injective；
children statement hashes 有 domain separation；
outer ZK backend 对全部 circuit tables 生效。

当前 pinned recursion API 默认不是这种 root-only projection：它会公开两边 verifier-input builders 打包出的 proof commitments、openings 与 challenges，并按 left/right 顺序拼接。要得到 root-only 接口，需要显式改变 public/private allocation，并重新证明 verifier binding 与 aggregation statement；仅仅在最终应用对象中保存一个 root hash 不会自动隐藏已注册的 public inputs。

17.4 实现声明不替代模拟证明

递归仓库未审计，主仓库的不同 hiding backends 也可能有不同统计/完美 ZK 口径。生产文档应引用：

具体 backend；
具体 theorem/implementation；
具体 commit；
audit status。

18. 多层递归的 soundness 怎样组合

18.1 每层都是一个独立 argument

设第 $i$ 层由 security theorem 量化的密码学 soundness error 上界为：

\[\varepsilon_i^{\mathrm{crypto}}.\]

先定义实现正确性前提：

\[\mathcal A_{\mathrm{impl}} := \bigwedge_{i=0}^{d} \left( \mathsf{CircuitVerify}_i \equiv \mathsf{NativeVerify}_i \right) \land \mathsf{TranscriptBinding} \land \mathsf{StatementBinding}.\]

在该前提以及各层 security theorem 的其他假设下，深度 $d$ 的递归链可保守地按密码学坏事件做 union bound：

\[\Pr[ \mathsf{ForgeChain} \mid \mathcal A_{\mathrm{impl}} ] \le \sum_{i=0}^{d}\varepsilon_i^{\mathrm{crypto}}.\]

这里的 $\varepsilon_i^{\mathrm{crypto}}$ 应包含该层 theorem 真正量化的 ALI、DEEP、FRI、LogUp、Fiat–Shamir 与 hash 等坏事件。若某个 composition reduction 另有可证明的统计/计算误差，可以把该已证明项加入总和。

recursive verifier circuit bug、错误 transcript 顺序或 statement substitution 不是天然带有 bits 的随机事件。若 $\mathcal A_{\mathrm{impl}}$ 不成立，抽象 theorem 可能完全不适用，确定性漏洞甚至可能令错误接受概率为 1；除非另有明确的随机故障模型，不能把它们塞入一个 $\varepsilon_{\mathrm{composition}}$ 来“扣几 bits”。

因此外层 128-bit 并不会把一个 60-bit inner proof “升级”为 128-bit。若没有另计的 reduction term，共有 $d+1$ 个已合成项，且 $\lambda_i=-\log_2\varepsilon_i^{\mathrm{crypto}}$，则：

\[\min_i\lambda_i-\log_2(d+1) \le \lambda_{\mathrm{chain}}^{\mathrm{cert}} \le \min_i\lambda_i.\]

18.2 recursive circuit completeness

必须做 differential test：

\[\mathsf{NativeVerify}(\pi) = \mathsf{CircuitVerify}(\pi)\]

对：

所有合法 proof classes；
每一类 malformed proof；
boundary degrees；
ZK/non-ZK；
query collisions；
mixed heights；
lookup/no-lookup。

18.3 recursive circuit soundness

不仅要证明它对合法 proof 接受，还要确保不存在 circuit witness 绕开：

boolean constraints；
range checks；
proof shape；
MMCS path ordering；
PoW；
quotient identity；
public-input/VK binding。

18.4 intermediate parameter relaxation

递归 book 讨论中间层可使用较宽松参数以节省 in-circuit queries。但严格做法不是套一个固定“少两次 query”规则，而是对每层重新计算：

\[\varepsilon_i = \varepsilon_{\mathrm{ALI},i} +\varepsilon_{\mathrm{DEEP},i} +\varepsilon_{\mathrm{FRI},i} +\varepsilon_{\mathrm{LogUp},i} +\cdots.\]

然后按整个 aggregation/recursion topology 组合。

18.5 hash collision cap 跨层

若所有层使用同一 $c$-bit hash，系统安全不超过：

\[c\]

bits，且多目标/多 proof 环境可能需要考虑攻击者拥有的总 hash targets 数，而不只是单份 proof 的 collision resistance 标签。

19. Plonky2.5 与当前原生递归对比

维度	QED Plonky2.5	当前 Plonky3-recursion
时间/状态	2024 v0.1.0 prototype	2026 active official project
outer arithmetization	Plonky2 PLONKish	Plonky3 multi-chip Batch-STARK
inner support	固定旧版 Uni-STARK/Fibonacci 路径	Uni-STARK 与 Batch-STARK
AIR reuse	手工写 bridge AIR	recursive traits/circuit pipeline；仍需目标 AIR 集成
FRI	degree-2 Goldilocks、binary、固定 shape	dynamic arity FRI，当前 config abstractions
hash	bridge 自带 Goldilocks Poseidon2 gate	configurable Poseidon operations/chips
lookup	无 current LogUp/batch support	LogUp/CTL 用于 circuit chips 与 batch proofs
aggregation	概念可构建但 demo 非完整框架	unified 2-to-1 API
ZK	demo outer 默认非 ZK	声明支持 ZK configs
audit	未见 production audit 声明	官方明确未审计
compatibility	不兼容 current P3	跟随 current P3，但仍需 commit pin

两者共同教训：

\[\boxed{ \text{recursive verifier 是一套新的安全关键实现。} }\]

不能因为 native verifier 已审计，就把 circuit verifier 自动纳入原审计结论。

20. 示例：聚合 Keccak proof 与 Fibonacci proof

设：

$\pi_K$：Keccak AIR 的 Uni-STARK proof，公开值为 digest $d$；
$\pi_F$：Fibonacci Batch-STARK proof，公开值为 $(a,b,x,N)$。

20.1 左 verifier subcircuit

检查：

\[\mathsf{VerifyUni}_{A_K,\theta_K} (\pi_K,d)=1.\]

20.2 右 verifier subcircuit

检查：

\[\mathsf{VerifyBatch}_{A_F,\theta_F} (\pi_F,a,b,x,N)=1.\]

20.3 root statement

定义带 schema/version 的 statement hashes：

\[\begin{aligned} h_K &= H( \texttt{"keccak-stmt-v1"}, d, \operatorname{id}(A_K,\theta_K) ),\\ h_F &= H( \texttt{"fib-stmt-v1"}, a,b,x,N, \operatorname{id}(A_F,\theta_F) ). \end{aligned}\]

root：

\[h_R = H( \texttt{"p3-agg-v1"}, h_K,h_F ).\]

aggregation circuit 把 $h_R$ 注册为 public values，并证明两个 sub-verifiers 接受。

20.4 生成 outer proof

circuit lower 成：

transcript ALU operations；
Poseidon2 calls；
MMCS path operations；
FRI field operations；
quotient checks。

各 chip 生成 traces，通过 LogUp witness bus 连接，最终生成：

\[\pi_R.\]

外部 verifier 检查：

\[\mathsf{VerifyBatch}(\pi_R,h_R)=1.\]

它得到的精确结论是：

\[\exists\pi_K,\pi_F: \mathsf{VerifyUni}_K(\pi_K,d)=1 \land \mathsf{VerifyBatch}_F(\pi_F,a,b,x,N)=1 \land h_R=H_{\mathrm{agg}}(h_K,h_F).\]

21. 当前递归项目的限制

21.1 未审计

这是首要部署边界。单元测试、coverage 与 benchmark 不能替代独立密码学/实现审计。

21.2 fixed shape

新 proof height/config 通常需要新的 verifier circuit 或 lifting strategy。

21.3 extension/config 参数仍不完全动态

README/roadmap 明确仍有 fixed configurations 与可配置性计划。

21.4 文档与源码可能不同步

快速开发期应使用：

commit hash；
workspace lock；
passing integration tests；
serialized fixture vectors；
generated verifier manifest。

21.5 resource DoS

recursive verifier 接收复杂 proofs。必须在 circuit generation/witness loading 前限制：

proof bytes；
degree bits；
instance count；
lookup count/width；
FRI layers/arities；
Merkle dimensions。

21.6 backend support 不均匀

FRI 是主线；Circle/WHIR/不同 hash-field combinations 在 native 与 recursive paths 的支持程度可能不同。

22. 审计递归 stack 的分层清单

22.1 native protocol

AIR correctness；
Batch-STARK transcript；
LogUp terminal balance；
PCS/FRI verifier；
security parameters。

22.2 circuit compiler

expression DAG；
common-subexpression/dedup optimization；
lowerer；
witness id allocation；
public-input allocation order。

22.3 chips

ALU selectors；
Poseidon permutation AIR；
recompose/range/bit operations；
preprocessed indices；
padding rows。

22.4 buses/lookups

every producer/consumer interaction；
multiplicities；
bus id/domain separation；
terminal sum；
height/multiplicity bounds。

22.5 recursive verifier

transcript conformance；
MMCS/FRI；
proof shape；
public values；
verifier identity；
ZK branches。

22.6 serialization/operations

manifest/version；
untrusted parser；
panic isolation；
memory/time limits；
audit commit delta。

23. 总结

当前 Plonky3 的“第三代”含义主要是体系结构演进：

flowchart LR
    A["AIR instances"] --> B["Batch-STARK"]
    L["LogUp buses"] --> B
    B --> P["Modular PCS"]
    P --> F["Dynamic-arity FRI / Circle / other"]
    F --> S["Security report<br/>proven + conjectured"]
    B --> R["Fixed recursive verifier circuit"]
    R --> C["Multi-chip traces"]
    C --> L2["LogUp witness bus"]
    L2 --> O["Outer Batch-STARK"]

数学上最重要的四点是：

高元 FRI arity 根据 input heights 与 final target 动态确定；
Batch-STARK 用 MMCS/PCS 共享承诺与 opening，但必须 transcript-bind partition；
LogUp 把跨 AIR multiset equality 变成 extension-field rational sums 与 terminal balance；
原生递归把 verifier 编译为固定 multi-chip program，再用 Plonky3 Batch-STARK 证明它。

安全上最重要的三点是：

简单 $b\times q+\mathrm{PoW}$ 只是 conjectural heuristic；
proven report 必须纳入 ALI、DEEP、LDT、batch、LogUp 与 hash cap；
当前递归仓库未审计，不能因“原生递归已实现”就推断可生产部署。

24. 一手资料

主仓库

递归仓库

论文

LogUp
Circle STARKs
WHIR
STARK-based Signatures from the RPO Permutation：当前 p3-security 引用其中定理 2、3 进行 round-by-round 组合；IACR 元数据的真实标题并不是源码注释中的 On the Security of STARKs with FRI。
A note on adding zero-knowledge to STARKs
On the Distribution of the Distances of Random Words：说明 capacity/random-words 路径为何必须明确标成 conjectured。
On Reed–Solomon Proximity Gaps Conjectures
On Proximity Gaps for Reed–Solomon Codes：当前 proven LDR FRI 路径使用其改进 bound。

上一篇：Plonky3 模块化架构
下一篇：Circle STARK 与现代哈希型 PCS
返回：总目录

zero-knowledge, stark

本文由作者按照 CC BY 4.0 进行授权