01. 技术全景：先把 STARK、PLONK 与 Plonky 放到正确坐标系
理解基础：知道“有限域”与“哈希承诺”的直觉即可。
资料快照：2026-07-29。
1. 所有协议都从关系开始
一个可验证计算最终描述为 NP 关系
\[R(x,w)=1,\]其中 $x$ 是 statement / public input，$w$ 是 witness。证明系统的三个核心算法可抽象为
\[\begin{aligned} \mathsf{pp} &\leftarrow \mathsf{Setup}(1^\lambda,\mathcal R),\\ \pi &\leftarrow \mathsf{Prove}(\mathsf{pp},x,w),\\ b &\leftarrow \mathsf{Verify}(\mathsf{pp},x,\pi). \end{aligned}\]至少要分清以下性质：
| 性质 | 准确含义 | 不保证什么 |
|---|---|---|
| 完备性 | 合法 witness 生成的证明被接受 | 不保证恶意 prover 无法作弊 |
| 可靠性 soundness | 对假 statement，作弊成功概率很小 | 不必提取 witness |
| 知识可靠性 | 接受证明意味着存在提取器可提取 witness | 不自动隐藏 witness |
| 零知识 | verifier 除 statement 真伪外学不到额外信息 | 不自动短，也不自动 transparent |
| succinctness | proof 短，验证远小于重算成本 | prover 不一定快 |
| transparency | setup 不含必须销毁的秘密 trapdoor | 不自动后量子安全 |
因此，“zk-STARK”“zk-SNARK”常被当产品类别使用，但做数学分析时必须逐项问：是哪一种 soundness？在哪个模型？有没有 ZK 模拟器？依赖哪些假设？
2. 一张比“STARK 对 PLONK”更准确的分层图
flowchart TB
R["关系层<br/>程序、状态转换、成员关系"] --> A["算术化层"]
A --> A1["AIR<br/>按时间相邻的轨迹约束"]
A --> A2["PLONKish<br/>表格、selector、copy constraint"]
A --> A3["R1CS / CCS<br/>矩阵或可定制约束"]
A1 --> P["多项式 IOP 层"]
A2 --> P
A3 --> P
P --> P1["ALI / quotient identity"]
P --> P2["permutation / lookup"]
P --> P3["sumcheck / multilinear identity"]
P1 --> C["承诺与低度检查层"]
P2 --> C
P3 --> C
C --> C1["KZG"]
C --> C2["IPA"]
C --> C3["FRI / Circle FRI"]
C --> C4["STIR / WHIR / BaseFold"]
C1 --> N["Fiat–Shamir 与非交互化"]
C2 --> N
C3 --> N
C4 --> N
N --> O["最终系统<br/>可再加入 ZK、递归、聚合"]
这张图解释了几个看似矛盾的名字：
- PLONK + KZG：原始 PLONK 的典型实例，证明很短，但需要 universal/updatable SRS，依赖 pairing 与离散对数类假设。
- PLONKish + IPA：Halo 2、Kimchi 一类路线，无结构化 toxic waste，opening 证明为对数级，仍依赖椭圆曲线离散对数。
- PLONKish + FRI：Plonky2 的典型描述；算术化像 PLONK，承诺后端像 STARK。
- AIR + FRI：最经典的 STARK 路线。
- multilinear IOP + WHIR/BaseFold：近年的 hash-based SNARK 路线，不宜简单叫“传统 STARK”，但与 FRI/STARK 共享编码承诺与透明性的核心思想。
3. PLONK 的核心骨架
原始 PLONK 把算术电路排成 $n$ 行、三条 witness wire：
\[\mathbf a=(a_i),\quad \mathbf b=(b_i),\quad \mathbf c=(c_i).\]每行用 selector 决定一个通用门：
\[q_La_i+q_Rb_i+q_Ma_ib_i+q_Oc_i+q_C=0.\]再用一个置换 $\sigma$ 编码“某个输出接到另一个输入”的 copy constraints。关键 grand product 把全局置换关系压成一条逐行递推。所有列在根单位子群 $H$ 上插值为多项式，门、置换和边界条件合并成一个可被 $Z_H(X)$ 整除的 numerator：
\[N(X)=Z_H(X)\,t(X).\]随机点 $\zeta\notin H$ 上检查 $N(\zeta)=Z_H(\zeta)t(\zeta)$，再由 PCS 证明打开值确实属于先前承诺的多项式。
4. STARK 的核心骨架
STARK 通常把 computation trace 记作矩阵
\[T\in\mathbb F^{n\times w},\]每一行是一拍状态，每一列插值为低次多项式 $t_j(X)$。AIR 给出：
- boundary constraints：第一行、最后一行或公开 I/O 必须取指定值；
- transition constraints：相邻行 $T_i,T_{i+1}$ 必须符合状态转移；
- 可选的 permutation / lookup / memory constraints：跨表数据必须一致。
这些约束被除以相应消失多项式并随机线性组合为 composition polynomial。prover 对其低度扩展求值并做 Merkle 承诺；FRI 一类 IOPP 检查该 oracle 是否接近 Reed–Solomon 码。
flowchart LR
E["执行程序"] --> T["trace 矩阵"]
T --> I["列插值"]
I --> Q["约束商多项式"]
Q --> C["随机组合"]
C --> L["低度扩展 LDE"]
L --> M["Merkle 承诺"]
M --> F["FRI / 新型 IOPP"]
F --> V["少量随机查询验证"]
“transparent”来自只需公开随机数、哈希和公开域参数；“scalable”来自 prover 近线性/拟线性而 verifier 与查询近似对数级。零知识则需要额外随机化，不是上述流水线的免费副产物。
5. 两族真正不同与真正相同的地方
| 维度 | 经典 STARK | 原始 KZG-PLONK | 结论 |
|---|---|---|---|
| 常见算术化 | AIR，强调相邻时间步 | 三列门 + permutation | 面向不同形状的计算 |
| 低度保证 | RS proximity / FRI | PCS degree bound + opening | 都归约到低次多项式 |
| 绑定方式 | Merkle + 哈希 | KZG 群元素 | 决定 proof size 与假设 |
| setup | transparent | universal/updatable SRS | PLONK 算术化本身不强制 KZG |
| 典型 proof size | 数十至数百 KB，参数相关 | 常为常数个群元素 + 标量 | 不应脱离参数报单一数字 |
| verifier 主要成本 | 哈希、域运算、Merkle path | pairing、MSM、域运算 | 硬件与链上预编译很关键 |
| 后量子 | 哈希型路线通常“可合理实例化为 PQ” | pairing/DLOG 不抗 Shor | Fiat–Shamir 的 QROM 证明仍需单独核对 |
| ZK | 需 masking / ZK code 等 | 需 witness polynomial blinding | 两者都不是自动 ZK |
共同的代数压缩模式
两个家族反复使用同一个技巧：
- 把很多局部条件写成多项式；
- 用随机系数合并，防止错误互相抵消；
- 用“在整个域上为零”等价于被消失多项式整除；
- 用随机点检查多项式恒等式；
- 用承诺保证 prover 不能看到挑战后换多项式。
如果 $P\neq Q$ 且 $\deg(P-Q)\le d$，Schwartz–Zippel 给出
\[\Pr_{\zeta\leftarrow\mathbb F}[P(\zeta)=Q(\zeta)] \le \frac d{|\mathbb F|}.\]协议的“魔法”主要来自如何把原始计算变成低 degree、如何在 challenge 之前绑定，以及如何把多个错误事件的概率严谨合成。
6. 2026 年视角下的演进主线
STARK / hash-based 主线
timeline
title 哈希型证明的主要研究节点
2018 : FRI 与首个 ZK-STARK 系统化论文
2019 : DEEP-FRI / DEEP-ALI
2023 : Binius 与二进制塔域路线
2024 : Circle STARK、STIR、WHIR
2025 : WHIR 会议版与多种工程集成
2026 : S-two whitepaper、近零开销 ZK code 路线
- Circle STARK 把 FFT 域从 $\mathbb F_p^*$ 的大 2-adic 子群迁到圆锥曲线 $x^2+y^2=1$ 的群，使 $p+1$ 很 smooth 的 Mersenne-31 可高效使用。
- STIR 通过递归提高/改变码率来减少 query complexity。
- WHIR 把 proximity test 与 constrained RS query、sumcheck 更紧地结合，目标是显著加速 hash-based PCS 的 verifier。
- Binius / BaseFold 等路线转向 multilinear polynomial 与小/二进制域，说明“透明哈希证明”已经超出经典单变量 AIR+FRI 模板。
- S-two 是 Circle STARK 的具体系统化；其 2026 whitepaper讨论 flat AIR、多表以及 correlated agreement。具体实现是否提供 ZK 必须查看对应版本，不能从 STARK 名字推断。
PLONKish 主线
timeline
title PLONKish 的主要研究节点
2019 : PLONK 通用可更新 SRS 与 permutation
2020 : Plookup、Halo Infinite
2021 : Halo 2 / Kimchi 等 IPA-PLONKish 系统成熟
2022 : Caulk、LogUp、HyperPlonk
2023 : HyperNova、ProtoStar、Binius
2024 : lookup 与折叠继续融合
2026 : 多后端、multilinear 与 hash-based 边界进一步模糊
- Turbo/UltraPLONK、Halo 2、Kimchi 扩展了列数、custom gate、rotation 与 lookup；“PLONKish”比“原始 PLONK”更适合描述它们。
- HyperPlonk 把单变量子群换成布尔超立方上的 multilinear extensions，以 sumcheck 消除 FFT 依赖并改善高次 custom gate 成本。
- Plookup / Halo 2 lookup 走“排序/置换 + grand product”；LogUp 用对数导数把 multiset equality 变成倒数和；Caulk/Baloo/Lasso 针对大表、稀疏查询或 zkVM 指令表优化。
- Halo、Nova、HyperNova、ProtoStar 分别从 proof recursion、accumulation、folding 角度降低长期计算的递归开销。
Plonky2、2.5、3 的汇合主线
Plonky 系列正好位于前述两条传统路线的交叉处：
| 名称 | 算术化与协议定位 | 在这些笔记中的作用 |
|---|---|---|
| Plonky2 | 具体的宽 PLONKish + permutation + Merkle/FRI 系统 | 展示 PLONK 前端如何脱离 KZG，并为递归共同选择 field/hash |
| QED Plonky2.5 | 在 Plonky2 circuit 中重演旧版 Plonky3 verifier 的第三方 bridge | 展示跨系统递归必须绑定全部 inner protocol 语义 |
| Plonky3 | Field、MMCS、PCS、Challenger、AIR、STARK 等可组合 primitives | 展示 proof system 如何由 concrete types 组装，而不是由单个品牌名决定 |
| Plonky3-recursion | 把固定 Uni/Batch-STARK verifier 编译为 multi-chip circuit | 展示 STARK-native recursion，不再以 Plonky2 作为外层 wrapper |
因此这些笔记先分别梳理 PLONKish 与 AIR/FRI，再在 Plonky2 中观察它们如何合流；随后用 2.5 记录跨版本边界，最后整理 Plonky3 的模块化设计。这个顺序表示理解依赖，不是三个 proof format 的版本升级链。
7. 项目名不能代替协议描述
阅读 benchmark 或安全公告时，至少写出如下五元组：
\[(\text{arithmetization},\ \text{PIOP},\ \text{PCS},\ \text{field/curve},\ \text{hash/transcript}).\]例如“PLONK proof”可能是：
- 原始 3-wire PLONK + KZG + BLS12-381；
- Halo 2 风格 PLONKish + IPA + Pasta curve；
- PLONKish + FRI + Goldilocks；
- HyperPlonk + multilinear PCS。
它们在 setup、proof size、递归、量子假设与 prover 瓶颈上都不同。反过来，“STARK prover”也可能使用经典 FRI、DEEP-FRI、Circle FRI 或不同 lookup/permutation 论证。
8. 后续阅读时不断追问的六个问题
- 对象是什么？ 单变量多项式、multilinear extension，还是 evaluation vector？
- 何时绑定？ 哪些 oracle/commitment 在挑战 $\alpha,\beta,\zeta$ 之前发送？
- degree budget 是多少？ 乘法、rotation、lookup 后次数如何增长？
- 检查的是 equality 还是 proximity？ FRI 证明的是接近某个低次多项式，不是直接交出该多项式。
- ZK 从哪里来？ 哪些随机多项式、盲行、masking code 支撑模拟？
- 安全定理依赖什么？ pairing/DLOG、collision resistance、random oracle、QROM、list-decoding conjecture，还是某种 algebraic group model？
9. 总结
最有用的心智模型不是“STARK vs PLONK”，而是：
\[\boxed{ \text{关系} \to\text{算术化} \to\text{PIOP} \to\text{PCS/IOPP} \to\text{Fiat–Shamir} \to\text{ZK/递归封装} }\]STARK 与 PLONK 只是这条流水线中若干常见组合的历史名称。掌握分层以后，Circle STARK、Plonky3、Halo 2、HyperPlonk、WHIR 等名词都会落到可比较的具体部件上。
参考
- Ben-Sasson 等，Scalable, transparent, and post-quantum secure computational integrity
- Gabizon、Williamson、Ciobotaru，PLONK
- Haböck、Levit、Papini，Circle STARKs
- Arnon 等，STIR 与 WHIR
- Carmon 等，S-two Whitepaper
- Halo 2 Book：PLONKish Arithmetization
- Plonky2 仓库弃用说明 与 Plonky3 仓库
上一篇：总目录 · 下一篇：有限域、多项式与编码基础 · 返回：总目录