07. STARK：从执行轨迹到 AIR、ALI 与 composition polynomial

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

作者 Chen Xichao

15 分钟阅读

1. STARK 不是单个公式，而是一条归约链

经典 STARK 把“程序执行正确”逐层归约为：

\[\begin{aligned} \text{valid computation} &\Longrightarrow \text{valid execution trace}\\ &\Longrightarrow \text{AIR constraints vanish}\\ &\Longrightarrow \text{constraint quotients are low degree}\\ &\Longrightarrow \text{composition oracle is low degree}\\ &\Longrightarrow \text{FRI accepts with high probability}. \end{aligned}\]

flowchart LR
    P["程序与输入"] --> E["执行"]
    E --> T["trace 矩阵"]
    T --> A["AIR 局部约束"]
    A --> Q["约束商多项式"]
    Q --> C["composition polynomial"]
    C --> L["LDE + Merkle"]
    L --> F["FRI / Circle FRI"]
    F --> V["随机位置的一致性检查"]

其中 AIR 负责语义，ALI/DEEP-ALI 一类 linking protocol 负责把语义约束连到一个或少数低度测试实例，FRI 负责 proximity。三层的 soundness 不能互相替代。

2. 一个可手算的 Fibonacci 状态机

令第 $i$ 拍状态为 $(a_i,b_i)$，初始值

\[(a_0,b_0)=(1,1),\]

状态转移

\[a_{i+1}=b_i,\qquad b_{i+1}=a_i+b_i.\]

若 $n=8$，trace 是

$i$	$a_i$	$b_i$
0	1	1
1	1	2
2	2	3
3	3	5
4	5	8
5	8	13
6	13	21
7	21	34

所有值实际都在 $\mathbb F$ 中；表中整数只为便于阅读。若 public statement 是“运行 7 步后输出 34”，还需 final boundary $b_7=34$。

2.1 AIR 的形式

AIR 包含：

trace width $w=2$；
trace length $n=8$；
boundary constraints；
transition constraints

\[\begin{aligned} C_1(a,b,a',b')&=a'-b,\\ C_2(a,b,a',b')&=b'-a-b. \end{aligned}\]

其中 prime 表示下一行。它们都是 degree 1 的局部约束。

真实 zkVM 会有数十到数百列，并用 selector 让不同指令激活不同 transition；但数学结构相同。

3. 把 trace 列插值为多项式

取大小为 $n$ 的子群

\[H=\{1,\omega,\ldots,\omega^{n-1}\}.\]

定义次数 $<n$ 的唯一多项式 $A,B$：

\[A(\omega^i)=a_i,\qquad B(\omega^i)=b_i.\]

“下一行”对应乘上生成元：

\[A(\omega\cdot\omega^i)=A(\omega^{i+1}).\]

所以 rotation $X\mapsto\omega X$ 把离散时间相邻关系变成普通多项式代入。

flowchart TB
    R0["行 i<br/>A(ω^i), B(ω^i)"] --> R1["行 i+1<br/>A(ω·ω^i), B(ω·ω^i)"]
    R0 --> C["检查 A(ωX)-B(X)=0"]
    R1 --> C
    R0 --> D["检查 B(ωX)-A(X)-B(X)=0"]
    R1 --> D

4. Boundary constraints 变成商多项式

初始条件只需在 $X=1$ 成立：

\[A(1)-1=0,\qquad B(1)-1=0.\]

因此

\[Q_{A,0}(X)=\frac{A(X)-1}{X-1}, \qquad Q_{B,0}(X)=\frac{B(X)-1}{X-1}\]

必须是多项式。

若 public output 为 $y$，final constraint

\[B(\omega^{n-1})-y=0\]

等价于

\[Q_{\mathrm{out}}(X) =\frac{B(X)-y}{X-\omega^{n-1}}\]

是多项式。

注意：这些 quotient 并不是说 verifier 要恢复全部系数再做除法。prover 通常在 extension domain 上计算其 evaluations 并承诺，verifier 只在随机查询点检查分子/分母关系。

5. Transition constraints 与最后一行

定义

\[\begin{aligned} P_1(X)&=A(\omega X)-B(X),\\ P_2(X)&=B(\omega X)-A(X)-B(X). \end{aligned}\]

它们应在

\[H_{\mathrm{trans}} =H\setminus\{\omega^{n-1}\}\]

上为零。最后一行被排除，因为 $\omega\cdot\omega^{n-1}=1$ 会 wrap 到第一行，而普通有限执行并不要求最后状态转回初始状态。

令

\[Z_{\mathrm{trans}}(X) =\frac{X^n-1}{X-\omega^{n-1}},\]

则合法 trace 满足

\[\begin{aligned} Q_1(X)&=\frac{P_1(X)}{Z_{\mathrm{trans}}(X)} \in\mathbb F[X],\\ Q_2(X)&=\frac{P_2(X)}{Z_{\mathrm{trans}}(X)} \in\mathbb F[X]. \end{aligned}\]

5.1 为什么不能把最后一行问题藏起来

若错误地用 $Z_H=X^n-1$ 作分母，就声称 $P_1,P_2$ 在全部 $H$ 上为零，额外强制

\[a_0=b_{n-1},\qquad b_0=a_{n-1}+b_{n-1},\]

把线性执行变成循环执行。若既不除正确 domain polynomial，也不乘 last-row selector，反而会漏查约束。两种错误方向都常见。

6. 一般 AIR 的代数化

设有 $w$ 个 trace polynomials

\[T_1(X),\ldots,T_w(X)\]

与第 $j$ 个 constraint

\[C_j: \mathbb F^{w\cdot |M_j|}\to\mathbb F.\]

$M_j$ 是 rotation mask，例如 ${1,\omega}$ 或 ${\omega^{-1},1,\omega}$。代入 trace 后：

\[P_j(X) = C_j\left( \{T_k(mX)\}_{k\in[w],\,m\in M_j} \right).\]

若它应在 domain $H_j$ 上为零，则

\[Q_j(X)=\frac{P_j(X)}{Z_{H_j}(X)}\]

应为低次多项式。

6.1 degree bookkeeping

若每个 $T_k$ 次数 $<n$，constraint 总次数为 $d_j$，则粗略有

\[\deg P_j\le d_j(n-1).\]

rotation $T_k(mX)$ 不改变次数。若 $\lvert H_j\rvert\approx n$，

\[\deg Q_j \lesssim d_j(n-1)-|H_j|.\]

因此高 degree constraint 会直接提高 composition degree、LDE 大小与 blowup 要求。实际实现常把高次表达式拆成低次中间列，以“更多 trace width”换“更低 constraint degree”。

7. 随机组合成 composition polynomial

若 prover 分别承诺许多 $Q_j$，proof 与 FRI 成本会随约束数增长。采样随机挑战 $\alpha$ 后，可构造

\[C(X) =\sum_{j=0}^{m-1}\alpha^j X^{s_j}Q_j(X).\]

其中 $s_j$ 是可选 degree adjustment，使不同 quotient 占用兼容的 degree range。也可为每项使用独立随机系数。

在 Fibonacci 例子中，一个简化 composition 为

\[\begin{aligned} C(X) ={}& \alpha_0\frac{A(X)-1}{X-1} +\alpha_1\frac{B(X)-1}{X-1}\\ &+\alpha_2\frac{B(X)-y}{X-\omega^{n-1}}\\ &+\alpha_3 \frac{A(\omega X)-B(X)}{Z_{\mathrm{trans}}(X)}\\ &+\alpha_4 \frac{B(\omega X)-A(X)-B(X)} {Z_{\mathrm{trans}}(X)}. \end{aligned}\]

若至少一个约束错误，固定 $X=x$ 后错误项恰被随机 $\alpha_j$ 抵消的概率很小。随后 FRI 检查 prover 提交的 $C$ oracle 是否接近声明 degree 的多项式。

7.1 “分式”只是表示法

在合法 trace 下，每一项本来就是多项式。prover 在 disjoint LDE domain $D$ 上逐点计算右式时，所有分母非零。verifier 对随机 $x\in D$ 检查

\[C(x) \stackrel{?}{=} \sum_j\alpha_j \frac{P_j(x)}{Z_{H_j}(x)}.\]

这条 local check 把 composition oracle 重新连接到 trace oracle。若只对 $C$ 做 FRI 而没有该连接，prover 可直接提交任意低次 $C$。

8. LDE、Merkle commitment 与 row packing

选择 blowup $b$，令 extension domain $D$ 大小

\[N=bn.\]

prover 在 $D$ 上求

\[\bigl(T_1(x),\ldots,T_w(x)\bigr) \qquad(x\in D)\]

并通常把同一行多列值打包成一个 Merkle leaf。这样打开位置 $x$ 时，一条 Merkle path 可同时提供全部当前行列值。

若 transition 需要 $\omega x$，domain 与索引布局必须让 verifier 找到对应 rotated leaf。leaf packing 降低 authentication path 数，却扩大每次打开的字段元素数，是 proof size 的重要工程权衡。

9. 一个典型 STARK transcript

不同 STARK 实现的顺序、DEEP composition 与 batching 会不同，下面是理解安全依赖的骨架：

sequenceDiagram
    participant P as Prover
    participant V as Verifier或Transcript
    P->>P: 执行程序并构造 trace
    P->>V: trace LDE Merkle root
    V-->>P: constraint-combination challenges
    P->>P: 构造 composition evaluations
    P->>V: composition Merkle root
    V-->>P: DEEP point z 与 mixing challenges
    P->>V: trace/composition 在 z 附近的声称值
    P->>V: FRI 各轮 roots
    V-->>P: 每轮 folding challenges
    V-->>P: query positions
    P->>V: queried leaves 与 Merkle paths
    V->>V: 检查 AIR identity、DEEP reduction、FRI folds

非交互版本用 Fiat–Shamir 从此前 transcript 派生每个 challenge。图中的箭头顺序就是 soundness 证明的一部分。

10. verifier 到底检查什么

对每个随机查询 $x$，verifier 大致：

验证 trace leaf、rotated leaf、composition leaf 的 Merkle paths；
从公开 AIR 重新计算每个 $P_j(x)$；
计算公开的 $Z_{H_j}(x)$；
检查 composition consistency；
沿 FRI 各层检查该位置的 folding relation；
检查最后小多项式的 degree 与最终 evaluation；
确认 public input / output boundary 已进入 constraint 和 transcript。

只做第 4 步不能证明 $C$ 低度；只做第 5 步不能证明 $C$ 来自 trace。STARK 的可靠性来自两条检查链相交。

flowchart TB
    T["trace openings"] --> A["AIR local identity"]
    C["composition opening"] --> A
    C --> F["FRI folding path"]
    A --> X["同一随机位置 x"]
    F --> X
    X --> OK["接受"]

11. AIR、APR、ALI 与 DEEP-ALI

原始 STARK 论文给出更一般的归约语言：

AIR：用局部多项式约束描述 trace；
APR：Algebraic Placement and Routing，把 witness polynomial、mask、constraint polynomial、constraint domain 系统化；
ALI：Algebraic Linking IOP，把 witness 与 composition/quotient oracle 连接到 RS proximity tests；
DEEP-ALI：在原 evaluation domain 之外采样点，提升错误实例到低度码的距离保证。

工程文档常把这些统称为“constraint composition”。但分析 soundness 时必须问：

一个不满足 AIR 的 trace，会让 composition word 离低度码多远？
random combination 是否可能把多个错误掩掉？
composition 与 trace 的一致性只查少量点时，gap 保留多少？
多表/多 component 的组合是否存在 correlated agreement 问题？

FRI soundness 很强并不自动回答前两问；DEEP-ALI 的价值正是改善 arithmetization-to-proximity 的 gap。

12. 非局部内存如何变回局部约束

CPU transition 只看相邻状态，但 RAM 语义要求：

read 必须返回该地址最近一次 write；
同一 memory event 在 CPU 表与 memory 表中一致；
range-check、opcode、bitwise 结果属于固定表。

常见做法：

在 execution trace 记录 memory events；
构造按 $(\text{address},\text{time})$ 排序的辅助表；
在排序表中用相邻行检查读写一致性；
用 permutation、grand product 或 LogUp 证明原表与排序表是同一 multiset。

flowchart LR
    C["CPU trace<br/>乱序 memory events"] --> P["multiset / permutation link"]
    P --> M["按 address,time 排序的表"]
    M --> L["相邻行局部检查"]
    L --> R["RAM consistency"]

这说明 AIR 并非只能表达简单递推；它通过辅助列和 multiset argument 把全局语义局部化。详细 lookup 数学见第 06 篇。

13. Zero-knowledge 从哪里来

13.1 一个通用掩码直觉

对 trace polynomial $T(X)$，可考虑

\[\widehat T(X)=T(X)+Z_H(X)R(X),\]

其中 $R$ 随机。对所有 trace rows，

\[\widehat T(h)=T(h),\qquad h\in H,\]

所以 AIR 语义不变；而 extension-domain 查询值会被随机化。必须同步：

提高允许 degree；
重新计算 composition degree；
证明被打开线性组合的分布可模拟；
处理 boundary 与所有 correlated queries。

真实 ZK-STARK 的 masking 方案比这个直觉更精细，可能使用随机 trace padding、ZK-friendly PCP/IOP 或 ZK encoding。

13.2 transparency、validity、ZK 三者分离

Merkle + public randomness 给出 transparency；
AIR + proximity + commitment 给出 validity/soundness；
randomized encoding 与模拟论证才给出 zero-knowledge。

截至本资料快照，S-two 官方文档明确提醒其相应实现状态不提供 zero-knowledge；因此它可用于证明 Starknet 状态转换有效，却不能据此推断隐藏 witness。协议论文、实现版本与产品营销必须分别核对。

14. 复杂度与主要旋钮

设 trace width $w$，原长度 $n$，LDE 大小 $N=bn$，查询数 $s$：

trace interpolation/LDE 常约 $O(wN\log N)$；
composition evaluation 常约 $O(mN)$，$m$ 为约束表达式成本；
Merkle 建树约 $O(wN)$ 或按 packed rows 计；
FRI prover 额外线性级 folding 与各轮哈希；
verifier 域运算近似随 $s\log N$；
proof authentication 数据近似随 $s\log N$，但受 path sharing、packing、folding factor 显著影响。

关键参数相互制约：

参数	增大后的典型效果
blowup $b$	码率下降、distance 增强；prover/内存变大
query count $s$	soundness 增强；proof/verifier 增大
folding factor	FRI rounds 减少；每轮打开与 degree 分析更复杂
trace width $w$	可降低 constraint degree；LDE 与 leaf 变宽
extension degree	challenge 空间增大；扩域乘法更贵
leaf packing	Merkle paths 减少；每个 query 暴露/传输更多值

15. 边界与常见陷阱

trace commitment 是否在所有 constraint-combination challenges 之前？
last row / first row / padding rows 的 selector 是否正确，rotation 会不会 wrap？
LDE domain 是否避开所有 quotient 分母的零点？
prover 声称的 composition degree 是否由最高 constraint degree严格推出？
public output 是否既进入 AIR 又进入 transcript？
FRI 查询用到的 trace、composition 和 rotated values 是否绑定到同一索引？
multiset/memory argument 的 challenge 是否晚于相关表 commitments？
padding 行是否被约束，还是可被恶意 prover 当自由 witness？
“STARK”实现是否真的启用 ZK masking？
security estimate 是否把 ALI gap、FRI proximity、Merkle/FS/hash 全部合成？

16. 自测

为 Fibonacci trace 写出 $a_0=1,b_0=1,b_{n-1}=y$ 的三个 boundary quotients。
为什么 $A(\omega X)$ 与 $A(X)$ degree 相同？
若 transition constraint degree 为 3，粗略估计 numerator 与 quotient degree。
说明只对一个低次 composition polynomial 做 FRI、却不检查它与 trace 的关系时如何作弊。
为“最后一行不应用 transition”分别写出 domain-polynomial 与 selector 两种方案。
transparency 为什么不能推出 zero-knowledge？

参考

Ben-Sasson、Bentov、Horesh、Riabzev，ZK-STARK 原始系统论文
Ben-Sasson 等，DEEP-FRI / DEEP-ALI
Ben-Sasson 等，FRI
Starknet 文档：S-two Book
Carmon 等，S-two Whitepaper

上一篇：PLONKish 自定义门与查表 · 下一篇：FRI 与 DEEP-FRI · 返回：总目录

zero-knowledge, stark

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