论文精读 #3 — STARK / FRI

日期: 2027-01-22 方向: 零知识证明 / 论文精读 阶段: Phase 4 - 密码学工程 (Day 264-267 论文精读系列) 标签: #ZK #STARK #FRI #paper-reading #post-quantum #transparent

---

今日目标

---

〇、为什么要精读 STARK / FRI？

STARK 是 SNARK 的对立选择，核心吸引点是 3T：

• Transparent — 无 trusted setup
• Transpost-quantum — 仅依赖 collision-resistant hash function（如 Rescue, Poseidon）
• Transcalable — prover 时间近似线性，可扩展到亿级 constraint

精读到位的指标：

• 不看论文能写出 FRI 一轮 fold 的公式（$f' = f_e + \alpha f_o$）。
• 能解释 FRI commit / fold / query 三阶段。
• 能讲 AIR 与 R1CS / PlonkIsh 的差异。
• 能在白板上把 STARK 全 pipeline（trace → AIR → composition poly → FRI）画完。

---

一、论文基本信息

1.1 STARK 主论文

1.2 FRI 论文

历史背景：Eli Ben-Sasson 是 PCP/IOP 学派的代表人物，2014 年就在做"区块链上的可验证计算"（zk-SNARK 一文也是他和 Chiesa 等人定义）。STARK 是他在 2018 年提出的对 SNARK 的"transparent + 后量子"补救方案。

---

二、历史定位 — STARK vs SNARK 阵营

                  PCP'92 (Probabilistically Checkable Proofs)
                          │
                          ▼
              IOP'16 (Interactive Oracle Proofs)
              ┌───────────┼───────────┐
              ▼                       ▼
       SNARK 阵营                STARK 阵营
       (pairing-based)            (hash-based)
       │                           │
       Pinocchio'13              FRI'17 (今日精读)
       Groth16'16                STARK'18 (今日精读)
       PlonK'19                  DEEP-FRI'19
       Halo2'20                  Plonky2'22 (混合：Plonkish + FRI)
       Halo'19                   Plonky3'24 (Goldilocks + FRI)
                                 ↑
                     Risc Zero / StarkNet / Polygon zkEVM (Type-3)

2.1 SNARK vs STARK 经典对比

实际部署策略：

• 若要 L1 直接 verify：用 SNARK
• 若要内部证明 + 自定义硬件加速：用 STARK
• 若要 recursion + 后量子：用 Plonky2 / Plonky3
• 若要 L2 → L1 桥接：STARK 内部 + Groth16 包装（StarkNet 未来路线）

2.2 为什么 2020-2026 STARK 起飞？

1. StarkWare 商业化：StarkEx (dYdX, Immutable X) → StarkNet（2021 公测，2022 主网）
2. Risc Zero 出现：通用 RISC-V zkVM（不再需要写电路），让 STARK 应用门槛降低 10x
3. Plonky2 hybrid：用 PlonK 的 IR 表达，FRI 做 commitment，速度上达到 SNARK 水准
4. 后量子焦虑：随着 NIST PQC 标准化推进，"是否后量子安全"成为评估指标

---

三、核心贡献 — 一句话版本

STARK 用 Reed-Solomon code + Merkle tree 构造一个完全 transparent 的 IOP，把任意 computation 表达成 AIR (Algebraic Intermediate Representation)，再用 FRI 协议证明 composition polynomial 的 low-degree 性质——整个过程仅依赖 collision-resistant hash function。

拆开成 4 个贡献：

---

四、逐节精读

4.1 STARK 论文 — Section 1: Overview

STARK 论文 Intro 给出三个目标：

"We present a STARK proof system: succinct, transparent, post-quantum secure with quasi-linear prover."

并给出关键定义：

• succinct: verifier time = $\text{poly}(\log n)$
• transparent: 无 trusted setup（CRS 仅 = 公开随机 string）
• post-quantum: 安全性仅基于 collision-resistant hash

Intro 末尾给出对比表（Table 1），列出与 PCP / SNARK / Bulletproofs 的差异。

4.2 STARK Section 2: AIR (Algebraic Intermediate Representation)

4.2.1 Execution Trace

把 computation 看成一个矩阵 $T \in \mathbb{F}^{w \times n}$：

• $w$ 列 = 寄存器数（每个寄存器一列）
• $n$ 行 = 时间步

每一行 $T_i$ 是某时刻的状态（所有寄存器值）。

例：Fibonacci computation 的 trace（2 列：$a, b$）

4.2.2 Boundary Constraint

某些行的某些列必须等于固定值。例：$T_0[a] = 1, T_0[b] = 1$。

4.2.3 Transition Constraint

相邻行之间的关系。例 Fibonacci：

$$ T_{i+1}[a] = T_i[b], \quad T_{i+1}[b] = T_i[a] + T_i[b] $$

4.2.4 多项式化

把 trace 第 $j$ 列 interpolate 为多项式 $f_j: H \to \mathbb{F}$，$H$ 是 $n$-th roots of unity。

把 transition constraint 写成多项式 identity，例：

$$ C_1(X) = f_a(X\omega) - f_b(X) = 0 \quad \text{on } H \setminus {\omega^{n-1}} $$

$$ C_2(X) = f_b(X\omega) - f_a(X) - f_b(X) = 0 \quad \text{on } H \setminus {\omega^{n-1}} $$

每个 constraint 除以对应的 vanishing polynomial $Z(X)$，得到 quotient polynomial：

$$ q_1(X) = C_1(X) / Z(X) $$

如果 trace 满足 transition，$q_1$ 是 polynomial（degree $< n$）；否则 $q_1$ 不是 polynomial（在某些点 blow up）。

4.3 STARK Section 3: Composition Polynomial

把所有 quotient 用 random challenge $\alpha_i$ 合并成一个 composition polynomial：

$$ H(X) = \sum_{i=1}^{k} \alpha_i \cdot q_i(X) $$

如果 trace 正确，$H$ 是 polynomial（degree 约 $n$）；否则 degree 超过 $n$ 或不是 polynomial。

STARK 把"trace 正确"约简为"$H(X)$ 是 low-degree polynomial"——这就是 FRI 要解决的问题。

4.4 FRI 论文核心 — Low-Degree Test

4.4.1 问题陈述

给定 evaluation domain $L_0$（一般 $|L_0| = \rho^{-1} \cdot d$，$\rho$ 是 rate，$d$ 是要证明的最大 degree），prover 给 verifier 一个 oracle access to function $f: L_0 \to \mathbb{F}$。

verifier 想验证：$f$ 与某个 degree $\le d$ 多项式 "近似"（即 codeword in Reed-Solomon code $\text{RS}[L_0, d]$）。

4.4.2 FRI 三阶段

Commit phase:  prover 把 f 在 L_0 上的所有 evaluation 放入 Merkle tree，发送 root
               然后逐层 fold，每层 commit Merkle root

Fold phase:    每一轮 verifier 给 challenge α
               prover 计算 f' = f_even(X²) + α · f_odd(X²)
               域大小折半 |L_{i+1}| = |L_i| / 2
               degree 也折半

Query phase:   verifier 随机选若干个查询点 z_0
               检查 fold 关系在每一层是否正确

4.4.3 Fold 操作的精确定义

设 $f(X) = f_e(X^2) + X \cdot f_o(X^2)$（任何多项式都可以这样拆成 even + X·odd 部分）。

verifier 给 challenge $\alpha$，定义：

$$ \boxed{f'(Y) = f_e(Y) + \alpha \cdot f_o(Y)} $$

关键性质：

• 若 $\deg f \le d$，则 $\deg f' \le d/2$（degree 减半）
• $f'$ 在 domain $L_1 = {x^2 : x \in L_0}$ 上 evaluate（domain 减半）
• $f'$ 与 $f$ 的关系：在每个 $y = x^2 \in L_1$ 上： $$ f'(y) = \frac{f(x) + f(-x)}{2} + \alpha \cdot \frac{f(x) - f(-x)}{2x} $$

4.4.4 多轮 fold

每一轮 prover 取上一层的 codeword，应用 fold，commit 新 Merkle root。

经过 $\log n$ 轮后，剩下 constant polynomial（degree 0），prover 直接 reveal 这个常数。

4.4.5 Query phase

verifier 随机选 $\lambda$ 个 query position $z_0 \in L_0$（$\lambda$ 是安全参数，典型 40-80）。

对每个 $z_0$：

1. 沿着所有层 fold 得到 $z_1 = z_0^2, z_2 = z_1^2, \dots$
2. 在每一层取 Merkle proof，验证 $f_i(z_i)$ 和 $f_{i+1}(z_{i+1})$ 满足 fold 关系： $$ f_{i+1}(z_i^2) \stackrel{?}{=} \frac{f_i(z_i) + f_i(-z_i)}{2} + \alpha_i \cdot \frac{f_i(z_i) - f_i(-z_i)}{2 z_i} $$

Soundness：如果 $f$ 不是 low-degree codeword（far from RS code），则任意 prover 通过 query 检查的概率 $\le \rho^{\lambda/2}$（约 $2^{-\lambda \cdot \log(1/\rho)/2}$）。

对 $\rho = 1/8, \lambda = 80$，soundness error 约 $2^{-120}$。

4.4.6 DEEP-FRI 优化

DEEP-FRI (2019) 引入"DEEP"（Domain Extension for Eliminating Pretenders）技巧：

• 把 quotient 在 domain extension（$L_0$ 之外的"virtual" point）上 evaluate
• 通过 quotient polynomial 强制 prover commit 到正确的多项式
• 减少 query 数量（同样安全级下从 $\lambda$ 降到 $\lambda/(1-\rho)$）

DEEP-FRI 是工业部署的标准（StarkNet, Plonky2 都用）。

4.5 STARK Section 4: 完整 Pipeline

1. Computation              → execution trace T
2. Trace                    → polynomial f_j (column polynomials)
3. AIR constraints          → transition + boundary constraints
4. Quotient                 → q_i = C_i / Z_i
5. Random α                 → composition polynomial H = Σ α_i q_i
6. Commit H on L_0          → Merkle root via Reed-Solomon codeword
7. Run FRI                  → log n rounds of fold + query
8. Output proof             → all Merkle roots + selected query openings

4.6 Section 5: 安全性

STARK soundness 由两部分组成：

1. 代数 soundness: random challenge $\alpha$ 让 composition polynomial 与 quotient 一一对应（Schwartz-Zippel）
2. FRI soundness: low-degree test 拒绝 far-from-codeword input

总 soundness error 约 $\rho^{\lambda/2}$ + $\text{poly}(n) / |\mathbb{F}|$。

完美 transparent：所有 randomness 来自 hash function（Fiat-Shamir），无需 trusted parties。

---

五、关键数学速查（白板版）

5.1 AIR 三要素

5.2 Composition Polynomial

$$ H(X) = \sum_{k} (\alpha_k \cdot q_k(X) + \alpha'_k \cdot X^{D-d_k} \cdot q_k(X)) $$

第二项是 "degree adjustment"——把所有 quotient 的 degree 对齐到统一的 $D$。

5.3 FRI Fold（最重要的公式）

$$ f(X) = f_e(X^2) + X \cdot f_o(X^2) $$ $$ \boxed{f'(Y) = f_e(Y) + \alpha \cdot f_o(Y)} $$

在 domain 上 evaluate： $$ f_e(x^2) = \frac{f(x) + f(-x)}{2}, \quad f_o(x^2) = \frac{f(x) - f(-x)}{2x} $$

5.4 Soundness (典型参数)

---

六、直觉理解

6.1 为什么 fold 能减半 degree？

把 $f(X) = a_0 + a_1 X + a_2 X^2 + \dots + a_d X^d$ 写成： $$ f(X) = (a_0 + a_2 X^2 + a_4 X^4 + \dots) + X \cdot (a_1 + a_3 X^2 + a_5 X^4 + \dots) $$

设 $f_e(Y) = a_0 + a_2 Y + a_4 Y^2 + \dots$，$f_o(Y) = a_1 + a_3 Y + a_5 Y^2 + \dots$。它们的 degree 各为 $\lfloor d/2 \rfloor$。

verifier 给 $\alpha$，则 $f' = f_e + \alpha f_o$，degree 也是 $\lfloor d/2 \rfloor$。degree 减半。

经过 $\log d$ 轮，degree 降到 0（常数）。

6.2 为什么这个 fold 是"绑定"的？

如果 prover 在某层作弊（构造一个 fake $f'$），下一层的 $f'$ 就和上一层的 $f_e + \alpha f_o$ 不一致。verifier 通过 random query 在两层间 cross-check，发现不一致就拒绝。

这种 cross-check 在 $\lambda$ 个 query 下检测概率约 $1 - \rho^{\lambda}$——close to 1。

6.3 为什么 STARK 后量子？

STARK 不依赖 ECDLP / pairing / RSA 等会被 Shor 算法破解的假设。仅依赖 collision-resistant hash function（如 SHA256、Poseidon、Rescue）——目前所有 Grover-resistant 的 hash function 都是后量子安全的（Grover 只把 hash 攻击复杂度从 $2^n$ 降到 $2^{n/2}$，所以用 256-bit hash 仍有 128-bit 后量子安全）。

6.4 为什么 transparent？

Reed-Solomon code 本身只需要 evaluation domain（一组公开的点 $L_0$），无 trapdoor。Merkle tree 的 hash function 是公开标准。所有 randomness 用 Fiat-Shamir 从 transcript 派生。没有 trapdoor，不需要 trusted parties。

---

七、实施考量 — Risc Zero / StarkNet / Plonky2

7.1 StarkNet (StarkWare 主导, 2022 主网)

• AIR 写在 Cairo 语言（StarkWare 自家 DSL）
• Cairo VM 输出 trace → AIR → STARK proof
• Proof size: ~50-100 KB
• L1 verify gas: ~500K - 1M（用 Solidity verifier）
• TVL: $1B+ (2026)
• 部署：dYdX V3、Immutable X、StarkNet L2

7.2 Risc Zero (2022)

• 通用 RISC-V zkVM：跑任意 Rust/C/C++ 代码
• 内部用 STARK + FRI
• proof size: ~200 KB（直接），可压缩到 ~250 bytes（用 Groth16 wrap）
• 真实案例：zkLogin、Bonsai 网络
• 关键创新：开发者无需写电路，只需写普通代码

7.3 Plonky2 (Mir Protocol, 2022)

• Plonkish IR + FRI commitment + Goldilocks field
• 充分利用 64-bit Goldilocks field（$2^{64} - 2^{32} + 1$）做硬件友好运算
• Proof time: 约 0.3 秒生成 1M constraints proof（CPU 单机）
• 用于 Polygon zkEVM Type-1 / Type-2 的内部 proof
• recursion friendly（详见 Day 267）

7.4 Plonky3 (Polygon, 2024)

• Plonky2 的下一代
• 模块化设计：可选 KZG / FRI / IPA 任意 PCS
• 用于 Polygon zkEVM v2、Reth zkEVM
• field 选择：可选 BabyBear / Mersenne31 / Goldilocks

7.5 真实 prover 性能（2026）

---

八、被使用的真实案例

8.1 StarkEx → StarkNet

• StarkEx (2020-): dYdX V3, Immutable X, Sorare, ApeX
• 累计交易 $1T+ (2026)
• StarkNet 主网 TVL ~$1B (2026)

8.2 Polygon zkEVM (Type 2)

• 使用 Plonky2 内部
• 最终 L1 用 Groth16 包装
• TVL: $200M+ (2026)

8.3 Risc Zero / Bonsai

• 通用 zkVM 平台
• 应用：zkLogin（Sui 生态）、zkAuth、zkOracle
• 累计 proof 数千万

8.4 Mina Protocol

• 不是 STARK，但用 Halo2 IPA（与 STARK 风格类似的 transparent 思路）
• 22 KB blockchain（recursion 压缩）

8.5 Polygon Miden

• Miden VM + STARK
• 高级语言 Miden Assembly
• 用于 Polygon Miden L2（2024 上线）

---

九、局限性

应对：

• 用 SNARK wrap（StarkNet 路线、Polygon zkEVM 路线）
• 用 recursion 把多个 STARK proof 聚合（Plonky2/3）
• 换更安全的 hash function（Poseidon2, Monolith）

---

十、关键速查表

10.1 STARK 数字事实

10.2 SNARK vs STARK 全表

---

十一、面试题

Q1: 用一句话解释 FRI 的核心思想。

答：FRI 通过把多项式 $f(X) = f_e(X^2) + X \cdot f_o(X^2)$ 用随机 challenge $\alpha$ 折叠成 $f' = f_e + \alpha f_o$，每轮把 degree 和 domain 都减半，经过 $\log d$ 轮变成常数；verifier 通过 Merkle tree 在每层的 random query 之间 cross-check fold 关系，从而以高概率确认原 $f$ 是 low-degree polynomial。

Q2: 为什么 STARK 不需要 trusted setup？

答：因为 STARK 的"setup"只是公开的 hash function（如 Poseidon）。Reed-Solomon code 的 evaluation domain $L_0$ 是公开 fixed 的（如某个 $2^k$-th root of unity 的 coset），Merkle tree 用公开 hash function——没有任何"trapdoor"或"toxic waste"需要销毁。所有 verifier challenge 用 Fiat-Shamir 从 transcript hash 派生，因此整个过程只依赖公开数据。

Q3: AIR 与 R1CS / PlonkIsh 的区别是什么？

答：

• R1CS: 单个约束 $\langle a, z \rangle \cdot \langle b, z \rangle = \langle c, z \rangle$，每个约束独立。Groth16 用此。
• PlonkIsh: 5 selector + 1 row identity + permutation argument，每行独立但允许 cross-row copy。
• AIR: 用 trace matrix（每列一个寄存器），约束可以是 transition relation（涉及多行如 $f(X), f(X\omega)$）。AIR 天然适合表达 VM 执行（每行 = 1 个 cycle）。

R1CS / PlonkIsh 描述"electronic circuit"；AIR 描述"state machine / VM"。这就是为什么 STARK 适合 zkVM。

Q4: 为什么 STARK 后量子安全而 SNARK 不安全？

答：

• SNARK (Groth16/PlonK) 依赖 ECDLP（椭圆曲线离散对数）和 pairing-related 假设。Shor 算法在量子计算机上能在多项式时间破解 ECDLP。
• STARK 仅依赖 collision-resistant hash function。Grover 算法把 hash 攻击复杂度从 $2^n$ 降到 $2^{n/2}$，所以使用 256-bit hash function 仍保留约 128-bit 后量子安全。

Q5: 解释 FRI fold 公式 $f' = f_e + \alpha f_o$ 在 evaluation 上的形式。

答：在 domain 上 evaluate，对 $y = x^2$：

$$ f_e(y) = \frac{f(x) + f(-x)}{2}, \quad f_o(y) = \frac{f(x) - f(-x)}{2x} $$

所以： $$ f'(y) = \frac{f(x) + f(-x)}{2} + \alpha \cdot \frac{f(x) - f(-x)}{2x} $$

verifier 在每层查询 $f_{i+1}(y) = f_i(x), f_i(-x)$，验证此 fold 关系，确保 prover 没有作弊。

Q6: STARK proof size 50-200 KB 为什么这么大？

答：主要来自 Merkle authentication path。每个 query 需要在每层提供 Merkle proof，每层 path 长度 $\log |L_i|$ ≈ 20-30 hash。$\lambda = 80$ 个 query × $\log d \approx 20$ 层 × 32 byte hash ≈ 50 KB+。

优化：DEEP-FRI 减少 query；batched FRI 共享 path；STIR (2024) 进一步减少 proof size 30-50%。

---

十一·五、补充：FRI 完整流程伪代码 + 安全参数推导

A. FRI Commit 阶段（prover）

Input:  function f: L_0 → F (codeword on coset L_0), max degree d
        challenges α_0, α_1, ..., α_{k-1} (drawn one at a time via FS)

Layer 0: f^(0) := f, L^(0) := L_0
build Merkle tree over all evaluations f^(0)(x) for x ∈ L^(0)
send root_0 to verifier

For i = 0 .. log(d) - 1:
    receive challenge α_i from verifier
    L^(i+1) := { x² : x ∈ L^(i) }   # domain halving
    For each y ∈ L^(i+1):
        find x s.t. x² = y (two preimages: x and -x)
        f^(i+1)(y) = (f^(i)(x) + f^(i)(-x))/2 + α_i · (f^(i)(x) - f^(i)(-x))/(2x)
    build Merkle tree over f^(i+1)
    send root_{i+1}

Final layer: f^(k) is a constant (degree 0)
send the constant value c

B. FRI Query 阶段（verifier）

For each query repetition q = 0 .. λ-1:
    z_0 ← FiatShamir(transcript)  # uniformly random in L_0
    For i = 0 .. k-1:
        request from prover:
            f^(i)(z_i), Merkle proof
            f^(i)(-z_i), Merkle proof
            f^(i+1)(z_i²), Merkle proof
        verify Merkle proofs against root_i, root_{i+1}
        check fold relation:
            expected = (f^(i)(z_i) + f^(i)(-z_i))/2 
                       + α_i · (f^(i)(z_i) - f^(i)(-z_i))/(2 z_i)
            assert f^(i+1)(z_i²) == expected
        z_{i+1} := z_i²
    # final check
    assert f^(k)(z_k) == c   # constant from commit phase

C. 安全参数选择

Soundness error 分析：

设 $f$ 与 RS code 的最小距离比例为 $\delta$（即 $f$ 至少要改 $\delta \cdot |L_0|$ 个值才能成为 codeword）。FRI soundness theorem (Ben-Sasson et al.) 给出：

$$ \text{Soundness error per query} \le \rho^{1/2} + (\text{negligible}) $$

对 $\lambda$ 个 queries：

$$ \text{Total soundness error} \le \rho^{\lambda/2} $$

DEEP-FRI 进一步收紧到接近 $\rho^{\lambda(1-\rho)}$。

典型工业参数：

为什么 rate $\rho$ 越小越安全但越慢？：rate $\rho = d/|L_0|$ 越小（$|L_0|$ 越大）则 codeword 之间距离越远，攻击者越难混淆 → soundness 提升。但 prover 要算更长 codeword、更多 Merkle hash。

工业上典型权衡：$\rho = 1/8$（safety) vs $\rho = 1/2$（speed）。Plonky3 的 BabyBear 选 $\rho = 1/2$ 配大 $\lambda$ 以最大化 prover 速度。

D. Reed-Solomon Proximity 直觉

Reed-Solomon code RS$[L, d]$ = "所有 $L \to \mathbb{F}$ 的函数中，可被 degree-$d$ 多项式 evaluate 表达的那些"。

FRI 不直接证明"$f$ 是 codeword"，而是证明"$f$ 距离 codeword 不超过 LDT 阈值"——这就是 IOP-of-Proximity 的"of Proximity"含义。

---

十一·六、补充：从 STARK 论文到生产部署的工程 gap

A. AIR 设计模式

AIR 设计核心是减少 trace 列数 + 减少 transition constraint degree。

模式 1: 寄存器多项式重用

传统：每个 VM 寄存器一列 → 列数爆炸

技巧：phase encoding —— 把多个寄存器的状态编码进一列的不同行。例如 RISC-V 的 32 个 register 可以用 1 列 + cycle phase，每 32 cycle 完成一次完整状态遍历。

StarkNet Cairo VM 用 4-5 列就能 encode 完整 VM，靠的就是 phase encoding。

模式 2: Lookup Argument 引入

STARK 原论文不支持 lookup。但 LogUp-GKR (2023) 把 lookup 嵌入 STARK：

• byte range check 成本从 8 个 transition constraint 降到 1 次 lookup
• ECC scalar mul 通过 lookup pre-computed table 加速 5x

Plonky2/3 都采用 LogUp。

模式 3: Permutation Argument

借鉴 PlonK，证明 trace 中某些 wire 满足 copy constraint。Plonky2 把 Plonkish permutation argument 嵌进 STARK，统一称 "Plonky2 air"。

B. STARK Prover 内存优化

朴素 STARK prover 内存 = trace 大小 × Reed-Solomon blowup factor $1/\rho$。

10M cycle trace × 8x blowup = 80M field elements × 8 bytes (Goldilocks) = 640 MB

加上多个 column、commitment、intermediate, 实际内存 5-10 GB。

优化技巧

1. Streaming FFT: 不把整个 codeword 物化在内存，分块计算 NTT
2. Batch Merkle: 多列共享一个 Merkle tree（每行 = 多列 hash 后单独 leaf）
3. GPU offload: NTT/MSM 都搬到 GPU

工业部署典型机器：

• StarkNet prover: 64 vCPU + 256 GB RAM + 4x A100 GPU
• Risc Zero prover: 16 vCPU + 32 GB RAM + 1 GPU

C. STARK Soundness 在工业实践中的妥协

学术 STARK soundness 用 worst-case 分析，工业实现常用更乐观的 conjectured bounds：

"Conjectured" 假设：RS code 在 list-decoding region 内的 codeword 数比 worst-case bound 小。这是 Ben-Sasson, Carmon, Ishai, Kopparty, Saraf'2020 提出的猜想，未被证明但工业界普遍采用以提升性能。

如果保守用"provable" bound，prover 时间约多 50%。

D. 后量子 hash function 选择

STARK 需要 hash function 同时满足：

• collision-resistant
• arithmetic-friendly（在 $\mathbb{F}_p$ 上有低 multiplicative complexity）

真实事件：2023 年 7 月 ZK 社区发现 Poseidon 在某些 round 数下 collision attack 复杂度低于 estimated。Plonky2 / StarkNet 都紧急升级到 Poseidon2（增加 round 数）。这是后量子 hash 选择的重要教训：不要依赖最小参数。

---

十二、明日预告

明天 Day 267 我们精读最后一篇 — Halo / Halo2 (Bowe-Grigg-Hopwood 2019)：

• 为什么需要"recursion proof composition without trusted setup"？
• Cycle of curves（Pasta: Pallas + Vesta）的精确含义
• IPA-based polynomial commitment 的 amortization 技巧
• Halo2 book 的 Plonkish 改造和 zkSync/Scroll 的 fork

精读完这 4 天，你将拥有从 Groth16（pairing-based）→ PlonK（universal）→ STARK（transparent）→ Halo2（recursion + transparent）的完整 SNARK/STARK 演化全景。

---

今日心得：精读 STARK / FRI 最大的认知升级，是从"SNARK vs STARK 二选一"转变为"两个阵营的工具箱可以共用"。Plonky2 把 Plonkish 算术化（来自 SNARK 阵营）+ FRI commitment（来自 STARK 阵营）合并；StarkNet 用 STARK 内部生成 + Groth16 wrap 上链。两个阵营在工程上已经融合：SNARK 提供 succinctness 和 L1 verify 经济性，STARK 提供 transparency 和 后量子。下一个十年的密码学工程几乎就是这两个工具箱的不断混搭。