02. 有限域、多项式、FFT 与 Reed–Solomon 编码
1. 为什么在有限域里计算
有限域 $\mathbb F_q$ 是包含 $q=p^k$ 个元素的域。最简单的是素域
\[\mathbb F_p=\mathbb Z/p\mathbb Z.\]域的关键性质是每个非零元素都有乘法逆元。因此加、减、乘、除都能用代数恒等式描述，且不会遇到整数除法的截断。
例如在 $\mathbb F_{17}$：
\[13+7=3,\qquad 5^{-1}=7,\qquad 5\cdot7=1.\]1.1 电路语义不是整数语义
若电路约束 $c=a+b$，其真实含义是
\[c\equiv a+b\pmod p.\]它并不证明整数加法“没有溢出”。若应用需要 $0\le a,b,c<2^{32}$ 和无溢出，必须额外做 range check、bit decomposition 或 lookup。这是 ZK 电路中最常见的语义漏洞之一。
1.2 基域、扩域与 challenge field
工程实现常把大部分 trace 放在小素域 $\mathbb F_p$ 中，以利用 32/64 位机器运算；随机挑战与组合值则放在扩域
\[\mathbb F_{p^k}\cong \mathbb F_p[u]/(m(u))\]中，其中 $m$ 是 $\mathbb F_p$ 上不可约的 $k$ 次多项式。这样既保留小域 trace 的速度，又扩大随机挑战空间。
必须区分：
- 字段位数：$\log_2 \lvert \mathbb F \rvert$；
- soundness bits：由字段碰撞、proximity test、查询次数、哈希安全性等多个错误项共同决定；
- 目标安全级别：例如 128 bit，不等于“用了 128-bit 字段”。
2. 多项式的两个表示
设
\[f(X)=a_0+a_1X+\cdots+a_dX^d\in\mathbb F[X].\]2.1 系数形式
直接存 $(a_0,\ldots,a_d)$。适合求导、次数分析与多项式乘法的概念描述。
2.2 点值形式
在一组互异点 $D=(x_0,\ldots,x_{N-1})$ 上存
\[(f(x_0),\ldots,f(x_{N-1})).\]若 $N>d$，这些值唯一确定 $f$。STARK 的 oracle、PLONK 的 witness columns 通常都先以点值表出现。
flowchart LR
C["系数向量<br/>a_0 ... a_d"] -->|"FFT / evaluation"| E["点值向量<br/>f(x_0) ... f(x_N-1)"]
E -->|"IFFT / interpolation"| C
E --> O["Merkle oracle 或列承诺"]
C --> P["KZG / IPA MSM"]
两种表示描述的是同一个多项式，但操作成本不同：
| 操作 | 系数形式 | 点值形式 |
|---|---|---|
| 加法 | $O(N)$ | $O(N)$ |
| 在同一域逐点乘 | 需卷积 | $O(N)$ |
| 求某个点的值 | $O(N)$ | 若点已在域中则 $O(1)$ |
| degree 直观可见 | 是 | 否，必须插值或做低度测试 |
点值形式中的逐点乘法确实给出
\[(f(x)g(x))_{x\in D},\]但不能无条件把它解释为普通乘积 $f(X)g(X)$ 的唯一低次表示。记
\[Z_D(X)=\prod_{x\in D}(X-x).\]由 $N=\lvert D\rvert$ 个乘积值插值得到的是次数 $<N$、与 $fg$ 在 $D$ 上相同的代表元，也就是 $fg\bmod Z_D$。只有在
\[\deg f+\deg g<N\]时才没有 degree aliasing，插值结果才等于普通多项式乘积 $fg$。FFT 卷积中的 zero-padding 正是在为这个 degree 条件预留空间。
3. 插值与 Lagrange 基
给定互异点 $x_0,\ldots,x_{n-1}$ 和值 $y_0,\ldots,y_{n-1}$，唯一存在次数小于 $n$ 的多项式
\[f(X)=\sum_{i=0}^{n-1}y_iL_i(X),\]其中
\[L_i(X)=\prod_{j\ne i}\frac{X-x_j}{x_i-x_j}, \qquad L_i(x_j)= \begin{cases} 1,&i=j,\\ 0,&i\ne j. \end{cases}\]Lagrange 基让“第 $i$ 行的值”与“一个多项式”完全等价。PLONK 标题中的 L 就来自“在子群上的 Lagrange basis”。
4. 根单位子群与消失多项式
若 $n\mid(q-1)$，乘法群 $\mathbb F_q^*$ 中存在阶为 $n$ 的元素 $\omega$：
\[\omega^n=1,\qquad \omega^i\ne1\quad(0<i<n).\]于是
\[H=\langle\omega\rangle =\{1,\omega,\ldots,\omega^{n-1}\}.\]在 $H$ 上为零的最低次首一多项式是
\[Z_H(X)=\prod_{h\in H}(X-h)=X^n-1.\]因为
\[Z_H'(\omega^i)=n\omega^{-i},\]子群上的 Lagrange 基可写为
\[L_i(X) =\frac{Z_H(X)} {(X-\omega^i)Z_H'(\omega^i)} =\frac{\omega^i}{n}\frac{X^n-1}{X-\omega^i}.\]这个闭式公式是 PLONK 边界 selector、public input 与 quotient 推导的核心。
4.1 一个 $\mathbb F_{17}$ 例子
取 $\omega=4$。有 $4^2=16=-1$、$4^4=1$，因此
\[H=\{1,4,16,13\}.\]对 $f(X)=X^2+2$：
\[(f(1),f(4),f(16),f(13))=(3,1,3,1).\]四个值能唯一恢复次数 $<4$ 的插值多项式；若只承诺这四个值却不证明低度，恶意 prover 仍可把它们当成任意向量。因此“插值存在”不是低度证明：任意四个值总能插值成某个三次多项式。
5. “在整个域上成立”就是整除
设约束多项式 $P(X)$ 满足
\[P(h)=0\qquad\forall h\in H.\]因 $H$ 中元素互异，根据因式定理，
\[Z_H(X)\mid P(X).\]等价地，存在商多项式
\[t(X)=\frac{P(X)}{Z_H(X)}\in\mathbb F[X].\]这一步把 $n$ 条逐行约束压成一条 polynomial identity：
\[P(X)=t(X)Z_H(X).\]STARK 的 constraint quotient / composition polynomial 与 PLONK 的 quotient polynomial 都建立在这里。
5.1 约束只在部分行启用
若 transition 只应作用于前 $n-1$ 行，不能盲目除以 $X^n-1$。定义
\[H_{\mathrm{trans}}=H\setminus\{\omega^{n-1}\},\]则其消失多项式为
\[Z_{\mathrm{trans}}(X) =\prod_{h\in H_{\mathrm{trans}}}(X-h) =\frac{X^n-1}{X-\omega^{n-1}}.\]另一种常见写法是乘 selector $1-L_{n-1}(X)$，关闭最后一行。两种写法的 degree budget 不完全相同，不能只凭“最后一行不查”而省略。
6. 随机点为何足以检查恒等式
如果 $P,Q$ 是次数至多 $d$ 的不同多项式，则 $P-Q$ 最多有 $d$ 个根。因此
\[\Pr_{\zeta\leftarrow\mathbb F} [P(\zeta)=Q(\zeta)] \le \frac d{|\mathbb F|}.\]这就是 Schwartz–Zippel 在单变量情形的直接根计数证明。
6.1 顺序比公式更重要
安全协议必须按以下顺序：
- prover 先承诺 $P,Q$；
- verifier 再随机采样 $\zeta$；
- prover 打开 $P(\zeta),Q(\zeta)$。
若 prover 先看到 $\zeta$，完全可以临时选择一个只在 $\zeta$ 上相等的错误多项式。Fiat–Shamir 的职责，就是让非交互 transcript 中的挑战仍绑定到此前全部消息。
6.2 随机线性组合
若要同时验证 $m$ 个恒等式 $P_j=0$，常取随机 $\alpha$ 并检查
\[C(X)=\sum_{j=0}^{m-1}\alpha^jP_j(X)=0.\]固定一个至少有一项 $P_j(x)\ne0$ 的点 $x$ 后，$C(x)$ 是关于 $\alpha$ 的非零多项式，次数至多 $m-1$。若 $\alpha$ 在整个 $\mathbb F$ 中均匀采样，则精确的根计数上界为
\[\Pr_\alpha[C(x)=0] \le \frac{m-1}{|\mathbb F|}.\]这里也要求所有 $P_j$ 在 $\alpha$ 产生前已被绑定；若挑战从真子集采样，分母还必须换成实际挑战空间大小。
7. FFT 为何要求 smooth domain
朴素 evaluation 或 interpolation 是 $O(n^2)$。当 $n=2^k$ 且有根单位子群时，可写
\[f(X)=f_{\mathrm{even}}(X^2)+Xf_{\mathrm{odd}}(X^2),\]其中两个子多项式的次数约减半。对成对点 $x,-x$：
\[\begin{aligned} f(x)&=f_{\mathrm{even}}(x^2)+x f_{\mathrm{odd}}(x^2),\\ f(-x)&=f_{\mathrm{even}}(x^2)-x f_{\mathrm{odd}}(x^2). \end{aligned}\]递归分治得到
\[T(n)=2T(n/2)+O(n)=O(n\log n).\]flowchart TB
F["f(X)，次数小于 n"] --> S["偶次项 + X 乘奇次项"]
S --> E["f_even(X²)，规模 n/2"]
S --> O["f_odd(X²)，规模 n/2"]
E --> R1["递归 FFT"]
O --> R2["递归 FFT"]
R1 --> M["蝶形合并 x 与 -x"]
R2 --> M
所谓 “FFT-friendly field” 本质是 $q-1$ 含足够大的 2 次幂因子。Circle STARK 使用圆锥曲线
\[C(\mathbb F_p)=\{(x,y):x^2+y^2=1\}.\]必须限定：标准 Circle STARK 取 $p\equiv3\pmod4$，此时 $-1$ 在 $\mathbb F_p$ 中非平方，圆群阶才是 $p+1$；若 $p\equiv1\pmod4$，该曲线群阶为 $p-1$。因此“大小来自 $p+1$”不是对任意素域都成立，而是这条字段选择的结果。
8. 低度扩展 LDE
设 trace 在大小 $n$ 的域 $H$ 上给出 $f\restriction_H$。低度扩展不是“在尾部补零”，而是：
- 插值得到次数 $<n$ 的同一个 $f(X)$；
- 在更大的域 $D$ 上求值。
若 $\lvert D\rvert=N=bn$，$b$ 称 blowup factor。$D$ 只需由 $N$ 个互异 evaluation points 组成；LDE 的定义本身并不要求 $D\cap H=\varnothing$。工程上常取乘法子群的陪集
\[D=g\langle\eta\rangle,\]当同一个 domain 还用于逐点评估约束商 $P(X)/Z_H(X)$ 时，才通常进一步选择 $D\cap H=\varnothing$，以保证分母 $Z_H(x)$ 非零。若只做编码，$D$ 可以包含 $H$，甚至常见的系统式 LDE 正是如此。
LDE 引入冗余：原来 $n$ 个自由度被编码为 $N$ 个值，不同合法码字之间因此具有较大距离。但若从一个合法码字 $c$ 只修改 $t$ 个位置得到 $u$，则
\[\Delta(u,\operatorname{RS}) \le \Delta(u,c) =\frac{t}{N};\]所以少量修改后的 word 仍然接近原码字。FRI/IOPP 保证拒绝的是与所有目标低次码字都至少相距给定阈值 $\delta$ 的 word，而不是保证拒绝每一个“只错一格”的非码 word；完整 argument 还依赖先承诺 oracle，防止 prover 针对查询位置继续修改。
9. Reed–Solomon 码与 proximity
给定 evaluation domain $D$、$\lvert D\rvert=N$，定义
\[\operatorname{RS}(D,k) =\{(f(x))_{x\in D}:\deg f<k\}.\]它是长度 $N$、维数 $k$、码率
\[\rho=\frac{k}{N}\]的线性码。最小 Hamming 距离为
\[d_{\min}=N-k+1.\]证明很简单：两个不同的次数 $<k$ 多项式之差最多有 $k-1$ 个根，所以其 evaluation vectors 至少在 $N-k+1$ 个位置不同。
9.1 距离与接近
对两个 word $u,v\in\mathbb F^D$，相对 Hamming 距离为
\[\Delta(u,v) =\frac{|\{x\in D:u(x)\ne v(x)\}|}{|D|}.\]word 到码的距离是
\[\Delta(u,\operatorname{RS}) =\min_{c\in\operatorname{RS}}\Delta(u,c).\]FRI 是 IOP of proximity：它试图区分
- $u$ 是低次多项式的 evaluation；
- $u$ 与所有目标低次多项式都相距很远。
它不是仅凭几次查询绝对证明 $u$ 每个位置都正确。将 IOPP 编译成 argument 时，Merkle commitment、防碰撞哈希、Fiat–Shamir 和查询重复共同给出计算可靠性。
10. 单变量与 multilinear 两条路线
10.1 单变量编码
STARK 和原始 PLONK 把长度 $n$ 的列放在单变量子群上：
\[f(\omega^i)=v_i.\]优点是 FFT、rotation $X\mapsto\omega X$ 与消失多项式 $X^n-1$ 都非常自然。
10.2 multilinear extension
令 $n=2^\ell$，把表格索引看作布尔向量 $b\in{0,1}^\ell$。任意函数
\[v:\{0,1\}^\ell\to\mathbb F\]有唯一 multilinear extension
\[\widetilde v(X_1,\ldots,X_\ell) =\sum_{b\in\{0,1\}^\ell} v(b)\,\chi_b(X),\]其中
\[\chi_b(X) =\prod_{j=1}^{\ell} \bigl(b_jX_j+(1-b_j)(1-X_j)\bigr).\]它对每个变量的次数至多 1。HyperPlonk、Spartan、Binius、BaseFold、WHIR 的许多构造都利用 multilinear extension 与 sumcheck，避免单变量 FFT 或改善高次门。
两种路线不是简单优劣关系：
| 特征 | 单变量子群 | 布尔超立方 MLE |
|---|---|---|
| 自然工具 | FFT、vanishing quotient、FRI | sumcheck、folding、MLE PCS |
| 相邻行 | $f(\omega X)$ 很自然 | 需索引/shift 关系 |
| 高次 custom gate | degree 可能乘以 trace size | 每变量 multilinear，但约束组合仍需分析 |
| 字段要求 | 通常要求大 smooth subgroup | 某些 PCS 可 field-agnostic |
11. 一个贯穿全书的压缩链条
flowchart LR
V["n 个 witness 值"] --> I["插值为 f(X)"]
I --> C["约束得到 P(X)"]
C --> D["证明 Z_H 整除 P"]
D --> R["随机点检查恒等式"]
I --> L["在更大域上 LDE"]
L --> RS["RS codeword / oracle"]
RS --> Q["proximity queries"]
R --> A["最终接受条件"]
Q --> A
PLONK 更强调图的上半部，并用 PCS 打开随机点；STARK 更显式地使用下半部的 RS encoding 与 proximity testing。现代系统经常混合两者。
12. 边界与常见陷阱
- 值域不等于整数域。 所有整数范围、符号、除法语义都要约束。
- $n\mid(q-1)$ 才有乘法 $n$ 阶根单位。 “取一个 $2^k$ 大小的 FFT”不是任意域都能做。
- $n$ 个点只保证唯一的次数 $<n$ 插值。 若协议声称次数更低，需要独立 degree/proximity 证明。
- 商只有在整除时才是多项式。 prover 可以在扩展域上逐点伪造“分数值”，所以必须把 quotient 的 degree 与 commitment 一并检查。
- 不要在消失域上除以消失多项式。 STARK 常在 disjoint coset 上评估 constraint quotient。
- degree bookkeeping 是安全参数。 合并前各约束的次数、quotient 次数和 PCS degree bound 必须一致。
- 小域需要扩域或额外重复。 $d/\lvert\mathbb F\rvert$ 只是其中一个错误项，不能拿它单独宣称 128-bit soundness。
- 随机挑战必须晚于相关承诺。 transcript 顺序错一条，就可能把根计数论证完全破坏。
13. 自测
- 在 $\mathbb F_{17}$ 中验证 $4$ 的阶为 4，并写出 $Z_H(X)$。
- 证明若 $P$ 在 $H\setminus{\omega^{n-1}}$ 上为零，则 $Z_{\mathrm{trans}}\mid P$。
- 一个次数 $<2^{18}$ 的多项式在大小 $2^{21}$ 的域上 LDE，其近似码率与 blowup factor 是多少？
- 解释为什么任意 $n$ 个值都“来自某个次数 $<n$ 的多项式”，但 FRI 仍然有意义。
- 给出一个有限域约束正确、但整数语义错误的溢出例子。
参考
- Reed、Solomon，Polynomial Codes over Certain Finite Fields
- Ben-Sasson 等，Fast Reed-Solomon Interactive Oracle Proofs of Proximity
- Haböck 等，Circle STARKs
- Gabizon、Williamson、Ciobotaru，PLONK
- Chen 等，HyperPlonk
- Diamond、Posen，Succinct Arguments over Towers of Binary Fields / Binius
上一篇：技术全景与知识脉络 · 下一篇：多项式承诺与 Fiat–Shamir · 返回：总目录