08. FRI 与 DEEP-FRI：为什么折叠能检查低度

1. FRI 要解决的问题

给定 domain $D\subset\mathbb F$、$\lvert D\rvert=N$ 和 oracle

\[f_0:D\to\mathbb F,\]

verifier 要判断它是否接近

\[\operatorname{RS}(D,d) =\{p|_D:\deg p<d\}.\]

FRI 是 Interactive Oracle Proof of Proximity。它不要求 verifier 读取全部 $N$ 个值，而是让 prover 依次提交越来越短的折叠 oracle，最后随机抽查一小批贯穿所有层的路径。

两个关键词：

• low degree：真实低次多项式每轮 degree 约减半；
• proximity：即使初始对象只是任意 word，若它远离所有低次 polynomial，随机 folding 后通常仍不会伪装成低次 word。

第二点是 FRI soundness 中真正困难的部分。

2. 一次二元折叠的代数

先假设字段特征不是 2。任意多项式可按幂次奇偶分解：

\[f_i(X) =g_i(X^2)+Xh_i(X^2).\]

若 $\deg f_i<d_i$，则 $g_i,h_i$ 的次数大约小于 $d_i/2$。

verifier 采样随机 $\beta_i$，定义下一层

\[f_{i+1}(Y) =g_i(Y)+\beta_i h_i(Y).\]

于是

\[\deg f_{i+1} \lesssim \left\lceil\frac{d_i}{2}\right\rceil.\]

2.1 只靠点值完成 folding

对一对 $x,-x$：

\[\begin{aligned} f_i(x)&=g_i(x^2)+xh_i(x^2),\\ f_i(-x)&=g_i(x^2)-xh_i(x^2). \end{aligned}\]

因此

\[\begin{aligned} g_i(x^2) &=\frac{f_i(x)+f_i(-x)}{2},\\ h_i(x^2) &=\frac{f_i(x)-f_i(-x)}{2x}. \end{aligned}\]

下一层点值满足

\[\boxed{ f_{i+1}(x^2) = \frac{f_i(x)+f_i(-x)}{2} +\beta_i \frac{f_i(x)-f_i(-x)}{2x} }\]

verifier 打开三个值，就能检查一条 fold relation，无需知道完整 polynomial。

3. domain 也随之对折

设

\[D_i=g_iG_i\]

是大小 $N_i$ 的 2-power 乘法陪集，且 $-1\in G_i$。映射

\[x\mapsto x^2\]

把 pair ${x,-x}$ 映成同一个点。定义

\[D_{i+1}=\{x^2:x\in D_i\}, \qquad |D_{i+1}|=|D_i|/2.\]

因此 polynomial degree 与 evaluation domain 同时减半，码率大致保持不变。

flowchart TB
    D0["D_0：N 个点<br/>x 与 -x 成对"] -->|"β_0 folding"| D1["D_1：N/2 个点<br/>坐标 x²"]
    D1 -->|"β_1 folding"| D2["D_2：N/4 个点<br/>坐标 x⁴"]
    D2 -->|"继续"| DR["D_r：很小的 domain"]
    DR --> P["直接发送最终小多项式"]

3.1 一个 $\mathbb F_{17}$ 手算

取

\[f_0(X)=3+2X+5X^2+7X^3.\]

分解为

\[g_0(Y)=3+5Y,\qquad h_0(Y)=2+7Y.\]

若 $\beta_0=4$：

\[f_1(Y)=g_0(Y)+4h_0(Y)=11+16Y \quad\text{in }\mathbb F_{17}.\]

在 $x=1$：

\[f_0(1)=0,\qquad f_0(-1)=16.\]

于是

\[g_0(1)=\frac{0+16}{2}=8,\qquad h_0(1)=\frac{0-16}{2}=9,\]

并且

\[f_1(1)=8+4\cdot9=10 =11+16\pmod{17}.\]

这正是 query phase 会检查的一条路径。

4. COMMIT phase

令 $r$ 是 folding 轮数。简化的二元 FRI：

1. prover 已对 $f_0\restriction_{D_0}$ 做 oracle commitment；
2. verifier 采样 $\beta_0$；
3. prover 计算 $f_1\restriction_{D_1}$ 并发送 Merkle root $R_1$；
4. verifier 采样 $\beta_1$；
5. 重复，直到 $D_r$ 很小；
6. prover 发送 $f_r$ 的系数或完整小域点值；
7. verifier 检查最终 degree bound。

sequenceDiagram
    participant P as Prover
    participant V as Verifier或Transcript
    P->>V: root R_0
    V-->>P: challenge β_0
    P->>V: root R_1
    V-->>P: challenge β_1
    P->>V: root R_2
    V-->>P: 后续 folding challenges
    P->>V: 最终小多项式 f_r
    V-->>P: query indices

顺序的含义：

• $f_i$ 在 $\beta_i$ 之前已经绑定；
• $f_{i+1}$ 可以依赖 $\beta_i$，但在 $\beta_{i+1}$ 之前绑定；
• query indices 在所有 roots 与最终 polynomial 绑定后产生。

若 prover 先知道 query indices，就可只在这些路径上填一致值。

5. QUERY phase

verifier 采样一个起点 $x_0\in D_0$，递归定义

\[x_{i+1}=x_i^2.\]

第 $i$ 层打开：

\[f_i(x_i),\quad f_i(-x_i),\quad f_{i+1}(x_i^2),\]

验证 Merkle paths 与 folding 等式。最后检查 $f_r(x_r)$ 等于直接发送的小多项式在 $x_r$ 的 evaluation。

flowchart LR
    A["打开 f_i(x_i)"] --> C["fold equation"]
    B["打开 f_i(-x_i)"] --> C
    D["打开 f_{i+1}(x_i²)"] --> C
    C --> N["x_{i+1}=x_i²"]
    N --> R["下一层重复"]

实际会并行重复多个 query paths，并剪枝共享的 Merkle authentication nodes。

6. 对任意 word，fold 仍然有定义

若 $f_i:D_i\to\mathbb F$ 不是某个 polynomial 的 evaluation，仍可逐 pair 定义：

\[\begin{aligned} g_i(x^2)&=\frac{f_i(x)+f_i(-x)}2,\\ h_i(x^2)&=\frac{f_i(x)-f_i(-x)}{2x}. \end{aligned}\]

然后令 $f_{i+1}=g_i+\beta_i h_i$。因此 honest folding 算法可作用于所有 words。

soundness 要证明：

如果 $f_i$ 离目标 RS code 很远，那么除很小概率外，随机 $\beta_i$ 得到的 $f_{i+1}$ 仍离下一层 RS code 足够远。

困难在于，作弊 word 可能同时靠近多个候选 codewords；随机折叠可能偶然选中一个“pretender”。这牵涉 RS list decoding、worst-case-to-average-case reduction 与多轮相关性，不能只用一次 Schwartz–Zippel 草率代替。

7. 为什么随机 $\beta$ 能阻止两半独立作弊

若两个不同候选分解

\[(g,h)\ne(g',h')\]

在 folding 后相同，则

\[g+\beta h=g'+\beta h',\]

即

\[(g-g')+\beta(h-h')=0.\]

对固定对象，这只在少数 $\beta$ 上成立。随机线性组合迫使 even/odd 两个方向绑定为同一个低次解释。

但 proximity 场景中，prover 可能有一整个候选列表，而且“在多少坐标上接近”会随折叠变化。因此完整 theorem 要使用 agreement/list-decoding 分析；这个线性方程只提供核心直觉。

8. 码率、距离与查询数

令初始 degree bound $d$、domain size $N$，码率

\[\rho=\frac dN.\]

较小 $\rho$ 意味着更大冗余与更远的 RS code distance，通常让 proximity soundness 更好，但 prover 要处理更大的 LDE。

对一个与所有合法 codeword 相距至少 $\delta$ 的固定 word，若一次理想均匀查询命中错误位置的概率是 $\delta$，$s$ 次独立查询都漏掉的直觉概率为

\[(1-\delta)^s.\]

FRI 不能直接套这条式子，因为：

• 每层 oracle 由前层和随机 challenge 相关地产生；
• prover 可选择接近的候选 codeword；
• 多个 queries 共享 folding roots 与 Merkle paths；
• 非交互查询来自 random oracle；
• 某些参数使用 list-decoding conjecture，而非仅 unique-decoding bound。

生产参数必须使用目标 FRI 变体的正式 soundness bound 或经过审计的参数计算器。

9. DEEP：在盒子外采样，消灭 pretenders

DEEP 是 Domain Extending for Eliminating Pretenders。直觉是：在原 evaluation domain $D$ 外随机取 $z$，要求 prover 声称低次 interpolant 在 $z$ 的值。

9.1 单点 quotient 直觉

若 prover 声称 $f(z)=y$，构造

\[q_z(X)=\frac{f(X)-y}{X-z}.\]

若 $y$ 与某个低次 $f$ 一致，$q_z$ 的 degree 减 1。若一个 received word 靠近许多候选 polynomials，随机域外 evaluation $y$ 通常只能与很少候选一致，从而“钉住”一个解释。

9.2 DEEP-FRI 的对称版本

为配合 $x,-x$ folding，DEEP-FRI 可在 $z,-z$ 请求两个域外值。令 $U(X)$ 是通过这两点的次数至多 1 多项式：

\[U(z)=y_z,\qquad U(-z)=y_{-z}.\]

再定义

\[f'(X)= \frac{f(X)-U(X)} {(X-z)(X+z)} = \frac{f(X)-U(X)} {X^2-z^2}.\]

若域外声称来自同一个低次 $f$，分子可整除，degree 降 2；随后对 $f’$ 做 FRI folding。因为 $z\notin D$，原 domain 上分母不为零。

flowchart LR
    W["word f 在 D 上"] --> O["域外随机点 z 与 -z"]
    O --> U["声称值决定直线 U"]
    W --> Q["除以 X²-z²"]
    U --> Q
    Q --> F["对 f' 运行 FRI"]
    F --> S["更强的候选消歧与 soundness"]

9.3 DEEP-ALI

在 STARK linking 层，同样可把 trace/composition 在域外点的声称值混入 deep composition：

\[\frac{T(X)-T(z)}{X-z}, \qquad \frac{C(X)-C(z)}{X-z},\]

再随机组合并做 proximity test。目标不仅是加强 FRI 本身，还要让不满足 AIR 的实例产生离 RS code 足够远的 word。

现代实现中的 “out-of-domain sampling / OODS” 往往包含这一思想，但公式可能因多项式批处理、扩域和 folding factor 不同而变化。

10. FRI、DEEP-FRI 与后续分析的关系

文献中的命名容易造成误解：

• 初始 FRI 给出线性 prover、对数 verifier 的 RS IOPP；
• DEEP-FRI 用域外采样改善 list-decoding regime 的 soundness；
• 后续工作给出更紧的 FRI analysis，一些论文把经改进分析/参数化后的协议仍简称 FRI；
• 工程系统也常把含 OODS、batch reduction 的具体 PCS 整体称为 FRI。

因此比较两个实现时，要看 protocol transcript 与 soundness theorem，而不是只看配置字段写着 fri 还是 deep_fri。

11. 更高 folding factor

若一次按 $k$ 个 residue classes 分解

\[f(X) =\sum_{j=0}^{k-1}X^j f_j(X^k),\]

可采样 $\beta$ 并设

\[f_{\mathrm{next}}(Y) =\sum_{j=0}^{k-1}\beta^j f_j(Y).\]

domain 与 degree 约缩小 $k$ 倍，轮数从 $\log_2N$ 降到 $\log_kN$。代价是：

• 每轮需打开更多 sibling values；
• interpolation/folding 运算更复杂；
• query proof 与 leaf packing 权衡改变；
• soundness bound 要按该 folding arity 重新计算。

“轮数少”不自动等于 proof 更小或 prover 更快。

12. 多多项式批处理

STARK 常同时对 trace、composition 或多个 tables 做 low-degree test。可在 commitments 已绑定后采样 $\alpha$，组合

\[F(X)=\sum_{j=0}^{m-1}\alpha^j X^{s_j}f_j(X),\]

再运行一次 FRI。$s_j$ 可对齐不同 degree bound。

多表批处理引入新的 correlated agreement 问题：同一随机组合在不同 domains/码率下是否仍保留足够 proximity gap？S-two whitepaper特别系统化讨论了 cross-domain correlated agreement。这也是为什么不能把单表 soundness 数字直接乘到多表系统。

13. 实现布局为何影响 proof size

13.1 pair packing

把 $f_i(x)$ 与 $f_i(-x)$ 放在同一 Merkle leaf，可让一条 path 同时打开 folding pair。若 folding factor 为 $k$，也可把一个 fiber 的 $k$ 个值打包。

13.2 bit-reversed ordering

FFT 常用 bit-reversed order；若 Merkle layout 与 folding cosets 对齐，每轮 sibling 值天然相邻。错误的 index permutation 会让 prover/verifier 对“同一个 x”理解不同，属于可靠性漏洞而不只是性能 bug。

13.3 Merkle cap 与 path sharing

可把树顶若干层的节点整体放进 proof/key，减少每条 path 长度；多 query 也能合并重复 siblings。安全估计仍按实际独立 query positions 计算，不能因字节去重而误算独立性。

14. 特征 2 与二进制域

二元公式使用 $1/2$ 和 pair $x,-x$，在 characteristic 2 中

\[-x=x,\qquad 2=0,\]

所以不能原样使用。Binius 等二进制塔域协议采用适合 additive subspace / foldable code 的不同分解与 commitment。它们继承“编码 + folding + 查询”的精神，但不是把上述公式中的模数换成 2。

15. verifier 的伪代码

下面只表达结构，不可直接作为生产实现：

输入：roots R_0...R_r，challenges β_0...β_{r-1}，
      final polynomial p_r，query seeds

检查 deg(p_r) < d_r

对每条 query path：
    从 seed 得到 x_0
    对 i = 0...r-1：
        验证 f_i(x_i), f_i(-x_i) 对 R_i 的 Merkle path
        验证 f_{i+1}(x_i²) 对 R_{i+1} 的 Merkle path
        expected =
            (f_i(x_i)+f_i(-x_i))/2
            + β_i (f_i(x_i)-f_i(-x_i))/(2x_i)
        要求 expected == f_{i+1}(x_i²)
        x_{i+1} = x_i²
    要求打开的 f_r(x_r) == p_r(x_r)

全部通过则接受

真实协议还要检查 DEEP reduction、batch mixing、proof-of-work/grinding、domain separation、Merkle leaf 编码与 public statement binding。

16. 边界与常见陷阱

1. $R_i$ 是否在 $\beta_i$ 前绑定，$R_{i+1}$ 是否在 $\beta_{i+1}$ 前绑定？
2. query seed 是否在所有 FRI commitments 和最终 polynomial 后生成？
3. $x,-x$ 与 $x^2$ 的索引映射是否与实际 domain/coset 一致？
4. 最终 polynomial 是否检查 degree，而不只是检查几个 evaluation？
5. challenge 是否来自足够大的扩域？
6. batch 中不同 degree 的 polynomials 是否做正确 degree shift？
7. 重复 query 是否去重传输但仍正确计算有效独立查询数？
8. list-decoding conjecture、grinding bits 与 hash bits 是否在参数说明中明确？
9. DEEP point 是否确实在原 domain 外，所有 denominators 是否非零？
10. characteristic-2 系统是否误用了含 $1/2$ 的传统公式？

17. 自测

1. 从 odd/even decomposition 推导 boxed folding 等式。
2. 对一个四次多项式写出 $g(X^2)+Xh(X^2)$，并给出下一层最高 degree。
3. 解释为什么所有 rounds 后才生成 query indices。
4. “degree 每轮减半”为什么不足以证明任意作弊 word 的 soundness？
5. 从 $f(z),f(-z)$ 写出 $U(X)$ 的 Lagrange interpolation。
6. blowup 变大如何同时影响码率、prover、memory 与 soundness？

参考

• Ben-Sasson、Bentov、Horesh、Riabzev，Fast Reed-Solomon IOPP / FRI
• Ben-Sasson、Goldberg、Kopparty、Saraf，DEEP-FRI
• Ben-Sasson 等，ZK-STARK
• Arnon、Chiesa、Fenzi、Yogev，STIR
• Arnon、Chiesa、Fenzi、Yogev，WHIR
• Starknet S-two Book：Circle FRI

---

上一篇：STARK AIR / ALI · 下一篇：Plonky2 算术化与 FRI · 返回：总目录