STARK 基础 — FRI + Reed-Solomon

日期: 2026-12-05 方向: 零知识证明 / ZK理论 阶段: Phase 4 - ZK基础理论 (Day 209-222) 标签: #ZK #STARK #FRI #Reed-Solomon #post-quantum

---

今日目标

---

一、STARK 全称解析

Scalable Transparent Argument of Knowledge

主要优势 vs SNARK：

1. 无 setup（任何人都能 verify，无 ceremony 信任）
2. 后量子安全（仅基于哈希函数 collision-resistance）
3. 大 trace 友好（巨大计算证起来比 SNARK 快）

代价：proof size 大（10-200 KB），verifier 较慢。

---

二、Reed-Solomon Codes

2.1 定义

设有限域 $\mathbb{F}_q$，evaluation domain $D \subseteq \mathbb{F}_q$（$|D| = n$），rate $\rho = k/n$。

Reed-Solomon code $\text{RS}(\mathbb{F}_q, D, \rho)$ = 所有形如 "deg < $k$ 多项式在 $D$ 上的 evaluations" 的向量集合：

$$ \text{RS} = {(f(x_1), f(x_2), ..., f(x_n)) : \deg f < k} $$

2.2 关键性质

• 最小距离：$d = n - k + 1$（MDS code）
• 唯一解码：错误数 $\leq (d-1)/2 = (n-k)/2$ 时可恢复 $f$
• List decoding：错误数 $\leq n - \sqrt{nk}$ 时可恢复 $\leq O(1)$ 个候选

2.3 Low-Degree Test 的核心思想

陈述 "$\vec{v}$ 是 deg < $k$ 多项式的 evaluations"。Verifier 想 check：

• 直接：$O(k)$ 查询（插值 + 检查）
• STARK：$O(\log k)$ 查询（FRI）

---

三、FRI — Fast Reed-Solomon IOP

3.1 思路

把 deg-$k$ 多项式分解为 even/odd 部分：

$$ f(X) = f_E(X^2) + X \cdot f_O(X^2) $$

其中 $\deg(f_E), \deg(f_O) < k/2$。

新多项式：

$$ f^{(1)}(Y) := f_E(Y) + \alpha \cdot f_O(Y), \quad \alpha \stackrel{$}{\leftarrow} \mathbb{F} $$

$\deg(f^{(1)}) < k/2$。这是 FRI 的"折叠"。

3.2 协议（递归）

Initial: $f^{(0)} = f$ 在 $D_0$ 上的 evaluations（merkle commit）。

Round $i$ → $i+1$:

1. Verifier 给 challenge $\alpha_i$
2. Prover 计算 $f^{(i+1)}(Y) = f^{(i)}_E(Y) + \alpha_i \cdot f^{(i)}O(Y)$，commit Merkle root over $D{i+1} = {x^2 : x \in D_i}$
3. （domain 大小减半，degree bound 减半）

经过 $r = \log k$ 轮，degree bound 降到常数（比如 1），prover 直接发常数。

Query phase: Verifier 选 random index $j$，prover 给 Merkle path 揭示 $f^{(0)}(x), f^{(1)}(x^2), ..., f^{(r)}(x^{2^r})$。Verifier 检查每层折叠关系：

$$ f^{(i+1)}(x^{2^{i+1}}) \stackrel{?}{=} \frac{f^{(i)}(x^{2^i}) + f^{(i)}(-x^{2^i})}{2} + \alpha_i \cdot \frac{f^{(i)}(x^{2^i}) - f^{(i)}(-x^{2^i})}{2 \cdot x^{2^i}} $$

即 $f^{(i)}_E(y) + \alpha_i f^{(i)}_O(y)$ 在 $y = x^{2^{i+1}}$ 处求值。

重复 query 多次（典型 ~80 次）以放大 soundness。

3.3 安全性

• Completeness：诚实 prover 总通过
• Soundness：若 $f$ 不是 low-degree，每次 query 检测概率 $\geq \rho$（rate gap），多次重复 ⇒ $\rho^{\text{queries}}$ negl

DEEP-FRI (Ben-Sasson 2020) 把 soundness 提升到 unique decoding radius；fast-prover STARK (StarkWare) 用更激进的 list decoding bound。

3.4 复杂度

• Prover: $O(n \log n)$（FFT + Merkle）
• Verifier: $O(\log n)$ per query × #queries = $O(\lambda \log n)$
• Proof size: $O(\lambda \log^2 n)$

实践 ~50-200 KB（取决于电路 + soundness 目标）。

---

四、STARK 协议（高层）

4.1 输入

• AIR（trace + transition constraints + boundary constraints）
• Public input

4.2 Prover 步骤

1. Trace generation：执行计算，得到 trace 表 $T \in \mathbb{F}^{N \times w}$
2. Trace LDE：每列做 low-degree extension（在更大的域 $D$ 上 evaluations，$|D| = \rho^{-1} N$，blowup factor $\rho^{-1} = 2, 4, 8, 16$）
3. Commit trace: Merkle root of LDE columns
4. Random linear combination of constraints: 用 FS challenges 把所有 transition + boundary constraints 合并成单一多项式 $C(X)$
5. Quotient: $Q(X) = C(X) / Z_T(X)$（$Z_T$ vanish on trace domain）
6. Commit Q + DEEP composition polynomial
7. FRI on composition: 证明它是 low-degree
8. Query phase: verifier 取 random points, prover 给 Merkle paths

4.3 Verifier 步骤

1. Re-derive challenges (FS)
2. Check FRI consistency (folds)
3. Check constraint satisfaction at queried points
4. Check Merkle paths

4.4 Proof Structure (StarkWare ethSTARK 实测)

---

五、Hash-Based vs ECC-Based

STARK 只用 collision-resistant hash → 后量子安全（Grover 给 hash $\sqrt{N}$ speedup, 但 200-bit hash 仍 100-bit security）。

SNARK 基于 EC discrete log → Shor 算法 polynomial-time 破。

---

六、协议关系图

   Computation
        │
        ▼
   ┌─────────┐
   │   AIR   │ (trace + transition + boundary constraints)
   └────┬────┘
        │
        ▼
   Trace LDE (FFT)         ←─── domain D, blowup ρ^{-1}
        │
        ▼
   Merkle commit trace cols
        │
        ▼
   FS challenges → constraint composition C(X)
        │
        ▼
   Quotient Q(X) = C(X) / Z_T(X)
        │
        ▼
   FRI low-degree test on Q
        │
        ▼
   Merkle paths for queried indices
        │
        ▼
   π ≈ 50-200 KB

   Verifier:
     - Redo FS
     - Verify Merkle paths
     - Check FRI fold consistency
     - Check constraint at queries

---

七、代码 — FRI 折叠简化演示

"""
fri.py — FRI Fold 简化教学
不含 Merkle, 不含完整 query phase; 演示 fold step 数学
"""
import secrets
from numpy.polynomial import polynomial as P

P_MOD = (1 << 31) - 1  # Mersenne prime, FFT-friendly

def fri_fold(evals, alpha, domain):
    """
    输入: f 在 domain D 上的 evals; D = {x_0, ..., x_{n-1}}
    输出: f_new = f_E + alpha · f_O 在 D' = {x^2 : x ∈ D[:n/2]} 上的 evals
    使用关系: f_E(y) = (f(x) + f(-x))/2,  f_O(y) = (f(x) - f(-x))/(2x), where y = x^2
    """
    n = len(evals)
    half = n // 2
    new_evals = []
    for i in range(half):
        x = domain[i]
        f_pos = evals[i]
        f_neg = evals[i + half]  # 假设 domain 满足 D[i+half] = -D[i]
        x_inv = pow(x, -1, P_MOD)
        f_E = ((f_pos + f_neg) * pow(2, -1, P_MOD)) % P_MOD
        f_O = ((f_pos - f_neg) * pow(2, -1, P_MOD) * x_inv) % P_MOD
        new = (f_E + alpha * f_O) % P_MOD
        new_evals.append(new)
    return new_evals

# 演示
def main():
    # 选 deg < 4 多项式 f(X) = 1 + 2X + 3X^2 + 4X^3
    f_coefs = [1, 2, 3, 4]
    n = 8
    # 选 size-8 domain (multiplicative subgroup of order 8)
    # 用 toy: 取 8 个不同点 D = {1, g, g^2, ..., g^7} where g^8 = 1
    # 简化: 直接列点
    g = 7  # 假设 7^8 = 1 mod P_MOD; 真实需要找 8-th root of unity
    # 跳过严格 root, 用 [1, 2, 3, ...] 做演示 (非标准 FRI)
    domain = list(range(1, n + 1))
    evals = [P.polyval(x, f_coefs) % P_MOD for x in domain]
    print(f"Initial evals: {evals}")

    alpha = secrets.randbelow(P_MOD)
    folded = fri_fold(evals, alpha, domain)
    print(f"After 1 fold (length {n} → {n//2}): {folded}")
    print(f"alpha = {alpha}")
    # 期望: folded 是 deg < 2 多项式 f_E + alpha·f_O 的 evals

if __name__ == "__main__":
    main()

完整 STARK 实现见 winterfell (Rust)、stwo (Rust)、risc0 (Rust)、miden（Rust）、stark101 (教学 Python by StarkWare).

---

八、历史与论文

Quote (Eli Ben-Sasson): "We get to choose: do we want quantum-secure proofs from minimal assumptions, or short proofs from cryptographic assumptions? STARK chose the former."

---

九、应用对应

---

十、常见陷阱

1. Blowup factor 取舍：$\rho^{-1} = 2$ 紧但 soundness 弱 → 多 query；$\rho^{-1} = 16$ 松但 query 少。Trade-off
2. Field 选择：Mersenne prime $2^{31} - 1$ / Goldilocks $2^{64} - 2^{32} + 1$ 用于快速 FFT；BLS scalar 不适合 STARK
3. Hash 选择：链上 verify 要 EVM-friendly hash（Poseidon）vs 链下 Blake2/Rescue
4. Soundness 计算：要小心 list-decoding gap，不同分析下 query 数差 2-3x
5. FFT 内存爆炸：trace 大时 LDE 数据量是 trace 的 $\rho^{-1}$ 倍，10M trace × 32 B × blowup 16 = 5 GB
6. DEEP composition：现代 STARK 用 DEEP 技巧降 soundness loss，实现复杂

---

十一、关键速查

---

十二、面试题

Q1: STARK 相比 SNARK 的核心优势？

A1: (1) 无 trusted setup（仅靠 hash 抗碰撞）；(2) 后量子安全（基于 hash，非 ECDLP）；(3) prover 更快 for 大 trace（无 EC ops + FFT 友好的小 field）；(4) 天然 recursion（hash-based commitment 易在电路内验证）。代价：proof 大 ~50-200 KB，verifier 较慢。

Q2: FRI 协议每轮做什么？

A2: 每轮把 deg < $k$ 的多项式 fold 成 deg < $k/2$ 的多项式，方法：拆 even/odd $f = f_E(X^2) + X f_O(X^2)$，verifier 给 challenge $\alpha$，新 poly $f^{(1)} = f_E + \alpha f_O$。Domain 也减半。$\log k$ 轮后 deg 降到常数；query phase 检查每轮 fold 的一致性。

Q3: STARK 用什么 commitment？为什么不用 KZG？

A3: Merkle tree of evaluations（hash-based）。原因：(1) 无 trusted setup（KZG 需 SRS）；(2) 后量子（KZG 基于 pairing）；(3) recursion friendly（hash in-circuit 比 pairing 简单）；(4) prover 快（无 EC ops）。代价：proof 大约 5-20x 于 KZG。

Q4: AIR 与 R1CS 各自适合什么？

A4: AIR：天然适合重复执行的 trace（VM、Fibonacci、循环），转移约束复用，prover 高效。R1CS：通用电路（任意 NP 关系），但需要 unroll 重复结构 → 电路膨胀。zkVM 几乎都用 AIR（StarkNet, Risc Zero, Miden）；定制小电路（Tornado）用 R1CS。

Q5: STARK 的 soundness 与 query 数关系？

A5: 单 query 检测错误概率 $\geq \rho$（rate gap）。$\lambda$ queries 后 cheat 概率 $\leq \rho^\lambda$。例 $\rho = 1/4$，要 100-bit security → $\lambda \approx 50$ queries。这是 STARK proof size 的主要因子（每 query ~$\log n$ Merkle path × 32 B）。

---

十三、明日预告

Day 219 — SNARK vs STARK 全面对比：proof size、prover time、verifier time、setup、量子、用例 — 一篇详细对比报告。