14. Circle STARK、STIR、WHIR 与现代哈希型 PCS

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

作者 Chen Xichao

16 分钟阅读

资料快照：2026-07-29。近年方案仍在快速演进，本篇明确标注论文性质与实现性质。

1. 传统 STARK 对字段的隐藏要求

经典 FFT/FRI 希望 $\mathbb F_p^*$ 中存在很大的 2-power 子群。因为

\[|\mathbb F_p^\*|=p-1,\]

需要

\[2^n\mid(p-1).\]

这让 root-of-unity FFT、rotation $X\mapsto\omega X$ 和 FRI 的 $x,-x\mapsto x^2$ 都很自然。

但有些机器友好的素数并不满足。例如 Mersenne-31

\[p=2^{31}-1\]

有

\[p-1=2(2^{30}-1),\]

所以 $p-1$ 只含一个因子 2，无法提供大型 radix-2 乘法子群。另一方面

\[p+1=2^{31}\]

却是纯 2 次幂。Circle STARK 的核心就是：把 domain 从大小整除 $p-1$ 的乘法群搬到大小整除 $p+1$ 的圆群。

2. 有限域上的圆群

定义圆锥曲线

\[\mathcal C(\mathbb F_p) =\{(x,y)\in\mathbb F_p^2:x^2+y^2=1\}.\]

群运算模拟复数乘法：

\[(x_1,y_1)\odot(x_2,y_2) = (x_1x_2-y_1y_2,\, x_1y_2+x_2y_1).\]

单位元与逆元：

\[\mathbf 1=(1,0),\qquad (x,y)^{-1}=(x,-y).\]

封闭性来自

\[(x_1x_2-y_1y_2)^2 +(x_1y_2+x_2y_1)^2 =(x_1^2+y_1^2)(x_2^2+y_2^2)=1.\]

2.1 为什么群大小是 $p+1$

当 $p\equiv3\pmod4$ 时，$-1$ 在 $\mathbb F_p$ 中不是平方。令 $i^2=-1$，扩域元素

\[z=x+iy\in\mathbb F_{p^2}\]

的 norm 是

\[N(z)=(x+iy)(x-iy)=x^2+y^2.\]

圆群正是 norm-one subgroup。norm map

\[\mathbb F_{p^2}^\*\to\mathbb F_p^\*\]

的 kernel 大小为

\[\frac{p^2-1}{p-1}=p+1.\]

对 M31，圆群因而有 $2^{31}$ 个元素，提供大型 2-power cyclic domains。

flowchart LR
    M["传统域<br/>F_p* 大小 p-1"] --> A["M31 只有很小的 2-adicity"]
    C["圆群 C(F_p)<br/>大小 p+1"] --> B["M31 得到 2^31 级链"]
    A --> S["传统 radix-2 STARK 不合适"]
    B --> T["Circle FFT / Circle FRI"]

3. 为什么 M31 算术快

因为

\[2^{31}\equiv1\pmod{2^{31}-1},\]

对较宽整数 $a$ 可把高 31 位折回低位。若

\[a=a_{\mathrm{lo}}+2^{31}a_{\mathrm{hi}},\]

则

\[a\bmod p \equiv a_{\mathrm{lo}}+a_{\mathrm{hi}}\pmod p.\]

重复一次并做条件减法即可归约许多乘法结果。它适合 32-bit words、SIMD 与 GPU；但“单次域乘法更快”不等于整个 proof system 必然更快，Circle FFT、扩域运算、hash 与 memory traffic 仍须整体 benchmark。

小基域也意味着 challenge 空间不够大。S-two 使用 M31 上的扩域来承载安全挑战与组合值；官方文档把相应 secure field 记为 QM31。最终 soundness 仍由完整错误项决定。

4. 从单变量多项式改为圆上的函数空间

传统 STARK 在

\[\mathbb F[X]\]

里工作。Circle STARK 在坐标环

\[\mathbb F[x,y]/(x^2+y^2-1)\]

里的受限二元函数空间工作。因为在圆上有 $y^2=1-x^2$，高次 $y$ 可消去，每个函数可理解为

\[a(x)+y\,b(x).\]

论文定义的完整 circle polynomial space $\mathcal L_N$ 维数是

\[\dim \mathcal L_N=N+1.\]

用于大小为 $N$ 的 FFT/evaluation code 的是其中的子空间 $\mathcal L’_N\subset\mathcal L_N$，满足

\[\dim \mathcal L'_N=N.\]

因此，真正扮演“次数小于 $N$ 的单变量多项式空间”角色的是 $\mathcal L’_N$；不能把完整 $\mathcal L_N$ 的维数也写成 $N$。这一处区分还会影响 interpolation 唯一性、rate 与 proximity code dimension 的计数。

4.1 domain 是 twin coset

设 $G_{n-1}$ 是圆群的 2-power 子群，论文使用形如

\[D =Q\odot G_{n-1} \;\cup\; Q^{-1}\odot G_{n-1}\]

的 twin coset，大小 $N=2^n$。两个 cosets 互为 inverse，恰好适合第一轮把

\[(x,y)\quad\text{与}\quad(x,-y)\]

配对。

4.2 FFT basis

若 $j=(j_0,\ldots,j_{n-1})$ 是二进制位，Circle STARK 论文的一组 FFT basis 形如

\[b_j^{(n)}(x,y) = y^{j_0} v_1(x)^{j_1} \cdots v_{n-1}(x)^{j_{n-1}},\]

其中 $v_k$ 是嵌套 circle domains 的 vanishing polynomials。它类比 monomial/FFT basis，但与 circle domain 的逐层折叠对齐。

Circle FFT 能在 $O(N\log N)$ 量级在点值和该 basis 的系数之间转换。重要的不是把“$X$ 换成 $(x,y)$”，而是同时替换：

polynomial space；
evaluation domains；
vanishing functions；
FFT basis；
FRI folding；
DEEP quotient。

5. Circle folding 的几何

圆群 doubling 为

\[\left[2\right]\!(x,y) =(x^2-y^2,2xy) =(2x^2-1,2xy).\]

第一轮可把 inverse pair

\[(x,y),\ (x,-y)\]

合并，消去 $y$ 方向；后续 $x$ 坐标递归遵循 Chebyshev 型映射

\[x\mapsto 2x^2-1.\]

这取代传统 FRI 的

\[x\mapsto x^2.\]

flowchart TB
    D0["circle twin coset"] --> P0["配对 (x,y) 与 (x,-y)"]
    P0 --> D1["降到 x 坐标的子问题"]
    D1 --> P1["映射 x ↦ 2x²-1"]
    P1 --> D2["更小的嵌套 domain"]
    D2 --> R["重复并最终直接检查"]

Circle FRI 同样遵循“每轮先绑定 oracle、再采样随机 folding challenge、最后抽查路径”的安全结构。只是 pair、basis 与 vanishing function 已不再是传统乘法子群版本。

6. Circle vanishing 与 DEEP quotient

单变量 DEEP quotient 是

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

圆上不能随意拿 $x-P_x$ 代替，因为一个 $x$ 坐标通常对应 $(x,\pm y)$ 两点，且函数空间的 pole/degree 结构不同。Circle STARK 为点 $P$ 定义适合圆曲线的单点 vanishing function $v_P$，使用

\[q=\frac{f-f(P)}{v_P}.\]

论文证明该 quotient 仍落入受控 circle function space；必要时先在扩域中表示，再拆成 base/secure field 上的分量。

这是一个普遍教训：PCS/FRI 的 DEEP reduction 必须与底层 polynomial/function space 的 divisor 结构兼容，不能只搬运单变量公式。

7. AIR 在圆上如何工作

trace 行沿圆群子群排列。若 generator 为 $G$，相邻行从点 $P$ 移到

\[P\odot G.\]

因此 transition constraint 由

\[C\bigl(T(P),T(P\odot G)\bigr)=0\]

描述。圆上函数空间对相应 translation 的控制性质，使 next-row relation 与 degree bookkeeping 仍可高效处理。

整体 STARK 流水线保持不变：

flowchart LR
    T["trace on circle domain"] --> I["Circle interpolation"]
    I --> Q["circle constraint quotient"]
    Q --> C["random composition"]
    C --> F["Circle FRI"]
    F --> M["Merkle queries"]

变的是代数几何底座，不是 AIR→quotient→proximity 的宏观架构。

8. S-two：Circle STARK 的系统化实例

2026 年的 S-two whitepaper描述：

M31 上的 Circle STARK；
“flat AIR” circuit model；
多 table/component 的 proof of proximity；
cross-domain correlated agreement 的安全分析；
在 Johnson bound 范围内的多表 Circle FRI 结论，以及更强参数所依赖的 list/line-decoding conjectures。

8.1 为什么多表不是简单批处理

zkVM 的 components 可能有不同 trace lengths 和 domains。随机合并

\[F=\sum_i\alpha^iF_i\]

后，需要保证“folded/combined word 接近某个 codeword”确实来自各原表上相互一致的候选，而不是不同 domains 上的错误恰巧相关。

cross-domain correlated agreement 正是在分析这种现象：

flowchart TB
    A["table A：domain D_A"] --> C["随机组合 / 多表 Circle FRI"]
    B["table B：domain D_B"] --> C
    C --> F["folded word 看似接近"]
    F --> Q{"是否来自 A、B 上相关且合法的候选？"}
    Q -->|"需要 correlated agreement 定理"| S["系统 soundness"]

8.2 S-two 与 zero-knowledge

S-two 是 validity proof system 与高性能 Circle STARK 实现，但其官方文档在本资料快照时明确说明相应系统不提供 witness-hiding 的 zero-knowledge。不要因为项目位于 “ZK” 生态就省略隐私属性核对。

9. STIR：通过 rate improvement 减少查询

传统二元 FRI 每轮 domain 与 degree 都约减半，所以码率 $\rho=d/N$ 大致不变。STIR 的名字是 Shift To Improve Rate：一轮把 degree 减少更大因子 $k$，同时 domain 只减少约 2 倍。

粗略地，

\[\rho_{\mathrm{next}} \approx \frac{d/k}{N/2} =\frac2k\rho.\]

当 $k>2$，码率逐轮下降，后续 code distance 更大，所需查询随层数减少。

论文给出的渐近对比是：对 $\lambda$ bit soundness，FRI 的查询量典型含

\[O\left( \lambda\frac{\log d}{\log(1/\rho)} \right),\]

而 STIR 达到形如

\[O\left( \log d+ \lambda\log \frac{\log d}{\log(1/\rho)} \right).\]

STIR 仍是 RS proximity test，而不是新的算术化。它可以替换 proof stack 中的 FRI 层，但实际收益取决于 field size、参数、Merkle layout 和 verifier/proof-size 目标。

10. WHIR：把 proximity 与约束一起折叠

WHIR 引入/使用 constrained Reed–Solomon code。令一个 smooth RS codeword 同时对应 multilinear polynomial $\widehat f$，定义

\[\operatorname{CRS} [\mathbb F,L,m,\widehat w,\sigma] = \left\{ f\in\operatorname{RS}[\mathbb F,L,m]: \sum_{b\in\{0,1\}^m} \widehat w(\widehat f(b),b) =\sigma \right\}.\]

这条 sumcheck-like constraint 很灵活：

可表达 multilinear evaluation $\widehat f(z)=y$；
可表达 polynomial IOP 的聚合约束；
folding 时不仅缩小 code，还递归更新 constraint。

WHIR 综合了：

BaseFold 中将 sumcheck 与 code folding 结合的思想；
STIR 的 rate-improving 思想；
out-of-domain sampling；
mutual correlated agreement 的 list-preservation 分析。

flowchart LR
    R["RS proximity"] --> C["constrained RS<br/>附带 sumcheck target"]
    C --> F["rate-improving folding"]
    F --> C2["更小 constrained RS"]
    C2 --> V["快速最终验证"]

它可以作为 univariate 或 multilinear PCS，并直接承载 evaluation query。论文报告的某组参数中，degree $2^{22}$、100-bit security 的 PCS opening 通信约 63 KiB、验证约 360 微秒；这是论文实例而非跨硬件保证，选型时应复现实测与安全模式。

11. BaseFold 与 Binius：边界已经超出传统 STARK

11.1 BaseFold

BaseFold 从 foldable codes 构造 field-agnostic multilinear PCS：

工作对象是 multilinear polynomial；
与 sumcheck 自然组合；
不要求特定 2-adic prime field；
仍采用编码/哈希型透明路线。

它与 FRI 共享 folding 思想，但不是经典单变量 RS-on-multiplicative-coset FRI。

11.2 Binius

Binius 论文在二进制塔域上构造高效 SNARK：

小到 $\mathbb F_2$ 的数据无需嵌入大素域后浪费表示；
使用适合小域的 multilinear PCS；
给出 HyperPlonk product/permutation 与 Lasso lookup 的二进制域适配；
对 Keccak 等 bit-oriented computation 特别有吸引力。

它说明现代 proof system 的分类更适合写为

\[(\text{arithmetization}, \text{polynomial space}, \text{code/PCS}, \text{field}),\]

而不是只分“SNARK”与“STARK”两个桶。

12. 2026 年的 ZK IOPP 前沿

2026/391 预印本 Zero-Knowledge IOPPs for Constrained Interleaved Codes 给出 honest-verifier zero-knowledge 的 constrained interleaved-code IOPP，并声称相对非 ZK 先进方案仅有可忽略级开销。核心部件包括：

ZK sumcheck interactive oracle reduction；
ZK code-switching；
可组合的 honest-verifier ZK 定义；
round-by-round knowledge soundness。

这条路线很重要，因为长期以来最快的 hash-based PCS/IOPP 往往先优化 soundness 与速度，隐私层需要额外高成本 masking。应同时注意：

它是 2026 年预印本，不能自动代表所有 FRI/WHIR 实现；
honest-verifier ZK、Fiat–Shamir 后 non-interactive ZK 与 malicious-verifier 安全需要按论文 compiler 条件区分；
使用某个含 zk-codes 模块的软件库，不等于上层 protocol 已正确启用和证明 ZK。

13. 当前技术谱系

方案	主要空间	核心创新	更像哪一层
FRI	单变量 RS	保持码率的低度折叠	IOPP
DEEP-FRI	单变量 RS	域外采样消歧	IOPP / opening reduction
Circle FRI	圆曲线函数空间	使用 $p+1$ 的 smooth group	IOPP
STIR	单变量 RS	递归降低码率	IOPP
WHIR	constrained RS + MLE	sumcheck constraint + rate improvement	IOPP / PCS
BaseFold	multilinear + foldable code	field-agnostic PCS	PCS
Binius	binary tower + multilinear	tiny-field 原生 arithmetization/PCS	完整 SNARK 路线
S-two	flat AIR + Circle FRI	M31、多表系统化与安全分析	proving system

14. 如何选择研究方向

目标是理解现有 AIR/STARK：先掌握 FRI/DEEP-FRI，再学 Circle FRI。
目标是高性能 M31 zkVM：研究 Circle FFT、QM31、LogUp 与多表 correlated agreement。
目标是 multilinear PCS 或 sumcheck-heavy SNARK：研究 BaseFold、WHIR。
目标是 bit-oriented computation：研究 binary tower fields、Binius 与相应 lookup。
目标是隐私而非只做 validity：单独核对 ZK encoding、模拟器和 non-interactive compiler。

15. 边界与常见陷阱

Circle group 的 smoothness 来自 $p+1$，不是突然让 $\mathbb F_p^*$ 变 smooth。
circle polynomial 的 degree/function space 不能按普通二元总次数随意替代。
next-row 是圆群 translation；domain/index order 错误会破坏 AIR 语义。
Circle DEEP quotient 必须使用适合曲线的 vanishing function。
M31 小域速度快，但 challenge/soundness 需扩域和完整参数分析。
STIR/WHIR 的论文 benchmark 不能直接外推到任意 circuit、hash 或硬件。
list-decoding conjecture 模式与 fully proven 参数必须明确区分。
多 table 不等于若干单表 soundness 的简单乘积。
“hash-based”只描述主要 commitment 路线；QROM、hash 实例和 transcript 仍需核对。
新 ZK IOPP 论文不自动给旧版 prover 增加零知识。

16. 自测

证明圆群运算保持 $x^2+y^2=1$。
用 norm map 解释为什么 M31 圆群大小为 $2^{31}$。
传统 FRI 的 $x^2$ 与 Circle folding 的 $2x^2-1$ 分别来自什么群映射？
为什么 circle function 不能只用 $x$ 坐标表示？
若 STIR 一轮 degree 降 4 倍、domain 降 2 倍，码率如何变化？
constrained RS code 如何把 evaluation claim 表成 sumcheck-like constraint？

参考

Haböck、Levit、Papini，Circle STARKs
Carmon 等，S-two Whitepaper
Starknet S-two Book：Circle Polynomials
Arnon、Chiesa、Fenzi、Yogev，STIR
Arnon、Chiesa、Fenzi、Yogev，WHIR
Zeilberger、Chen、Fisch，BaseFold
Posen、Diamond，Binius
Chiesa、Fenzi、Weissenberg，Zero-Knowledge IOPPs for Constrained Interleaved Codes
Plonky3 官方仓库

上一篇：Plonky3 的 FRI、LogUp 与原生递归 · 下一篇：递归、累积与折叠 · 返回：总目录

zero-knowledge, stark

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