03. 多项式承诺、Merkle oracle 与 Fiat–Shamir

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

作者 Chen Xichao

19 分钟阅读

1. PCS 的抽象接口

多项式承诺方案 Polynomial Commitment Scheme 至少提供：

\[\begin{aligned} \mathsf{pp}&\leftarrow\mathsf{Setup}(1^\lambda,d),\\ C&\leftarrow\mathsf{Commit}(\mathsf{pp},f;r),\\ \pi_z&\leftarrow\mathsf{Open}(\mathsf{pp},f,r,z),\\ b&\leftarrow\mathsf{Verify}(\mathsf{pp},C,z,y,\pi_z). \end{aligned}\]

目标是让短 commitment $C$ 绑定一个次数 $\le d$ 的多项式，并用短 opening proof 证明 $f(z)=y$。

必须分别检查以下性质：

commitment binding：不能把同一 $C$ 打开成两个不同多项式；
evaluation binding：不能在同一点打开成两个不同值；
degree binding：被绑定对象确实不超过声明次数；
hiding：$C$ 是否隐藏 $f$；这不是所有 PCS 的默认性质；
knowledge soundness：能否从成功 prover 中提取被承诺多项式或相应 witness。

许多论文在 algebraic group model、knowledge-of-exponent 类假设或 random oracle model 下证明不同版本；“使用 KZG”四个字不足以说明完整安全结论。

sequenceDiagram
    participant P as Prover
    participant V as Verifier
    P->>V: C = Commit(f)
    V-->>P: 随机点 z
    P->>V: y = f(z), opening proof
    V->>V: 检查 C 与 z,y 一致

核心顺序是 commit → challenge → open。后续所有 polynomial IOP 都围绕它编排 transcript。

2. KZG：在秘密点 $\tau$ 上“代入”

KZG 使用阶为素数 $r$ 的双线性群

\[\mathbb G_1,\mathbb G_2,\mathbb G_T\]

与 pairing

\[e:\mathbb G_1\times\mathbb G_2\to\mathbb G_T, \qquad e(g_1^a,g_2^b)=e(g_1,g_2)^{ab}.\]

2.1 Structured Reference String

setup 采样必须销毁的非零秘密 $\tau\leftarrow\mathbb F_r^*$，发布

\[\mathsf{SRS} = \left( g_1,g_1^\tau,g_1^{\tau^2},\ldots,g_1^{\tau^d}; g_2,g_2^\tau \right).\]

给定

\[f(X)=\sum_{i=0}^{d}a_iX^i,\]

prover 无需知道 $\tau$ 就能计算

\[C_f =\prod_{i=0}^{d}(g_1^{\tau^i})^{a_i} =g_1^{f(\tau)}.\]

commitment 只有一个群元素。直觉是：SRS 允许在指数里对秘密点求值，但不允许恢复 $\tau$。

2.2 单点 opening

声称 $f(z)=y$。由因式定理，

\[q(X)=\frac{f(X)-y}{X-z}\]

是多项式。opening proof 为

\[\pi=g_1^{q(\tau)}.\]

verifier 检查

\[e\left(C_f/g_1^y,g_2\right) \stackrel{?}{=} e\left(\pi,g_2^\tau/g_2^z\right).\]

正确性来自

\[f(\tau)-y=q(\tau)(\tau-z).\]

pairing 把指数里的乘法关系搬到 $\mathbb G_T$：

\[e(g_1,g_2)^{f(\tau)-y} =e(g_1,g_2)^{q(\tau)(\tau-z)}.\]

2.3 KZG 为什么短，代价在哪里

收益	代价
commitment 常数大小	SRS 必须覆盖最大 degree
单点 proof 常数大小	需要 pairing-friendly curve
多个多项式可随机线性批处理	prover 主要成本常含大 MSM 与 FFT
链上若有 pairing 预编译则 verifier 便宜	DLOG/pairing 路线不抗 Shor

2.4 universal、updatable 不等于 trustless

PLONK 常说 universal/updatable setup：

universal：同一 powers-of-$\tau$ 可服务所有不超过上限的电路；
updatable：任何参与者都可加入新随机性；只要至少一位诚实销毁其秘密，最终 toxic waste 未知；
circuit-specific key：可从 universal SRS 公开派生，并不需要新秘密仪式。

它降低了信任门槛，但没有把 SRS 变成“纯透明参数”。若 $\tau$ 泄露，攻击者能构造不受正确低次多项式约束的 opening 关系。

2.5 KZG commitment 默认不隐藏

$C_f=g_1^{f(\tau)}$ 是确定性的。同一 $f$ 总给出同一 commitment；若候选空间很小，观察者可枚举。完整 ZK-SNARK 通常通过：

给 witness polynomials 加不会改变约束域取值的随机 $Z_H$ 倍数；
使用带独立 hiding generator 的承诺变体；
在 protocol 层加入盲化项并证明 degree budget；

来获得零知识。不要把“离散对数难”误解为自动 hiding。

3. IPA：把 evaluation 变成内积

设系数向量

\[\mathbf a=(a_0,\ldots,a_{n-1})\]

和公开独立 generators $\mathbf G=(G_0,\ldots,G_{n-1})$。Pedersen 风格向量承诺可写为

\[C=\langle\mathbf a,\mathbf G\rangle+rH =\sum_i a_iG_i+rH.\]

在点 $z$ 的 evaluation 是内积

\[f(z)= \left\langle (a_0,\ldots,a_{n-1}), (1,z,\ldots,z^{n-1}) \right\rangle.\]

Inner Product Argument 递归把长度 $n$ 的向量折成两半。仅写向量折叠会漏掉关键的交叉项；为展示每轮保持的关系，考虑常见的双基 accumulator

\[\mathcal P =\langle\mathbf a,\mathbf G\rangle +\langle\mathbf b,\mathbf H\rangle +\langle\mathbf a,\mathbf b\rangle U.\]

把所有向量分成左右两半，prover 先发送

\[\begin{aligned} L={}&\langle\mathbf a_L,\mathbf G_R\rangle +\langle\mathbf b_R,\mathbf H_L\rangle +\langle\mathbf a_L,\mathbf b_R\rangle U,\\ R={}&\langle\mathbf a_R,\mathbf G_L\rangle +\langle\mathbf b_L,\mathbf H_R\rangle +\langle\mathbf a_R,\mathbf b_L\rangle U. \end{aligned}\]

transcript 在绑定 $L,R$ 后给出非零 challenge $x$，再按下面的同一 convention 折叠：

\[\begin{aligned} \mathbf a'&=x\mathbf a_L+x^{-1}\mathbf a_R,\\ \mathbf b'&=x^{-1}\mathbf b_L+x\mathbf b_R,\\ \mathbf G'&=x^{-1}\mathbf G_L+x\mathbf G_R,\\ \mathbf H'&=x\mathbf H_L+x^{-1}\mathbf H_R. \end{aligned}\]

对应的 group accumulator 必须同时更新为

\[\mathcal P'=x^2L+\mathcal P+x^{-2}R.\]

展开可见，$x^2\langle\mathbf a_L,\mathbf b_R\rangle$ 与 $x^{-2}\langle\mathbf a_R,\mathbf b_L\rangle$ 正是折叠后内积产生的两个交叉项。具体 PCS 可能把公开的 $\mathbf b$、hiding generator 或 evaluation claim 吸收到不同基中，但不能省掉等价的 $L,R$ 与 accumulator 更新。经过 $\log_2 n$ 轮只剩一个标量关系；每轮发送常数个群元素，所以 proof 大小是 $O(\log n)$ 群元素。

flowchart TB
    N["长度 n 的内积声明"] --> H1["发送 L_1,R_1 并采样 x_1"]
    H1 --> N2["折成长度 n/2"]
    N2 --> H2["发送 L_2,R_2 并采样 x_2"]
    H2 --> ND["继续对半折叠"]
    ND --> O["长度 1 的标量检查"]

3.1 IPA 的系统含义

不需要 powers-of-$\tau$ 这种结构化 trapdoor；generators 可由 domain-separated hash-to-curve 导出。
它仍依赖椭圆曲线离散对数，因此不具备后量子安全。
proof 比 KZG 大，为对数级群元素；verifier 通常需要相应 MSM。
additive homomorphism 很适合 accumulation 和 Halo 风格递归。
递归时要让外层 circuit 高效表达内层曲线运算，常用 curve cycle 或 endomorphism 优化。

Halo 2 与 Kimchi 常被概括为“PLONKish + IPA”，但两者具体 permutation、lookup、transcript 和递归层并不相同。

4. Merkle + FRI：承诺的是编码后的 evaluation oracle

4.1 Merkle commitment

prover 先在大域 $D$ 上计算 LDE：

\[\mathbf v=(f(x))_{x\in D}.\]

每个叶子做无歧义编码后哈希，内部节点递归

\[h_{\mathrm{parent}} =H(\mathsf{tag}_{\mathrm{node}}\|h_L\|h_R).\]

Merkle root 绑定整个 evaluation vector。打开一个位置需要该叶子与 $O(\log \lvert D\rvert)$ 个 sibling hashes。

4.2 Merkle 只绑定向量，不证明低度

任意随机向量都能建 Merkle tree。FRI 的工作是检查该向量是否接近低次 RS codeword。一个典型 hash-based PCS 组合：

对 LDE 求值并发送 Merkle root；
用 FRI / DEEP-FRI / WHIR 等证明 low-degree proximity；
用 DEEP quotient、batching 或 sumcheck 把声称的 $f(z)=y$ 连接到承诺 oracle；
对随机查询提供 Merkle authentication paths；
用 Fiat–Shamir 生成全部挑战与查询位置。

所以“FRI commitment”通常是简写。FRI 本身是 IOPP；成为非交互 PCS 还需要 commitment、evaluation reduction 与 transcript compiler。

flowchart LR
    F["f(X)"] --> L["在 D 上 LDE"]
    L --> M["Merkle root"]
    M --> B["绑定 evaluation vector"]
    L --> R["FRI / WHIR"]
    R --> D["证明接近低次编码"]
    B --> P["PCS opening"]
    D --> P
    E["evaluation reduction"] --> P

4.3 复杂度直觉

若 domain 大小为 $N$、查询数为 $s$：

prover 至少要处理 $O(N)$ 个编码值和哈希，若含 FFT 则常见 $O(N\log N)$ 域工作；
单轮查询 authentication 数据朴素为 $O(s\log N)$ 个哈希，但可用共享路径剪枝；
proof 通常明显大于 KZG/IPA；
verifier 以哈希和小域运算为主，没有 pairing；
透明且在选用合适 hash、编译器与 QROM 分析时具有 plausible post-quantum 路线。

这里没有一个对所有 STARK 都正确的固定 proof size。blowup、folding factor、查询数、leaf packing、hash digest、extension degree、grinding bits 都会改变结果。

5. 三类后端的横向比较

维度	KZG	IPA	Merkle + FRI/WHIR
主要对象	单变量 polynomial	coefficient/evaluation vector 内积	编码后的 evaluation oracle
setup	structured universal SRS	无结构化 toxic waste	transparent
commitment	1 个群元素	1 个群元素	1 个 hash root
opening proof	常数级	$O(\log n)$ 群元素	多轮值 + Merkle paths
verifier 核心	pairing	MSM / curve ops	hash + field ops
prover 核心	MSM、FFT	MSM	FFT/encoding、hash
post-quantum	否	否	可合理构造为是，但需完整模型分析
适合链上	有 pairing 预编译时很强	取决于曲线预编译	原生验证较贵，常递归压缩
递归	pairing inside circuit 较重	Halo 路线友好	小域/友好 hash 下可很快

“哪一个最快”没有脱离场景的答案。要同时给出：

\[(\text{circuit size},\text{field},\text{hardware}, \text{batch size},\text{proof size},\text{verifier target}).\]

6. 多项式批处理：随机组合再次出现

6.1 同一点打开多个多项式

若要证明

\[f_i(z)=y_i,\qquad i=0,\ldots,m-1,\]

先绑定所有 commitments，并把点 $z$ 与 prover 声称的全部 evaluations $y_i$ 吸收进 transcript；之后才能采样 batching challenge $v$，定义

\[F(X)=\sum_{i=0}^{m-1}v^if_i(X), \qquad Y=\sum_{i=0}^{m-1}v^iy_i.\]

只需证明 $F(z)=Y$。承诺的线性同态允许 verifier 同样组合 $C_{f_i}$。

正确依赖顺序是

\[(C_{f_0},\ldots,C_{f_{m-1}}) \longrightarrow z \longrightarrow(y_0,\ldots,y_{m-1}) \longrightarrow v \longrightarrow\pi_{\mathrm{open}}.\]

若 $y_i$ 在 $v$ 之后才确定，prover 可让多个错误声明在随机组合中相消。例如已知 $v\ne0$ 时取

\[y_0=f_0(z)+\delta, \qquad y_1=f_1(z)-\delta/v\]

便保持 $Y=F(z)$。因此“commitments 先于 $v$”仍不够，claimed evaluations 也必须先于 $v$。

这里的 random batching 只压缩一组已经定义好的 evaluation claims。对 Merkle + FRI 一类 oracle PCS，还需 DEEP quotient、folding/sumcheck 等独立的 evaluation reduction，把域外声明 $f(z)=y$ 连接到被承诺的 LDE oracle；随机线性组合本身不能替代这一步。

6.2 多点 opening

PLONK 常需在 $\zeta$ 与 $\omega\zeta$ 打开不同集合。可用：

分别生成两个 opening proofs；
先把同点多项式随机合并，再做 two-point aggregation；
使用专门的 multi-opening 协议。

具体 proof layout 取决于 KZG、IPA 或 FRI 后端。不能把某个实现的 opening 数量当作 PLONK 算术化的固定属性。

7. Fiat–Shamir：把 verifier 的随机性放进哈希

一个 public-coin 交互协议可能是：

\[P_1 \xrightarrow{\alpha} P_2 \xrightarrow{\beta} P_3 \xrightarrow{\zeta} \text{openings}.\]

Fiat–Shamir 令

\[\begin{aligned} \alpha&=H_{\mathsf{challenge}} (\mathsf{state}_0\|P_1),\\ \beta&=H_{\mathsf{challenge}} (\mathsf{state}_1\|P_2),\\ \zeta&=H_{\mathsf{challenge}} (\mathsf{state}_2\|P_3). \end{aligned}\]

prover 与 verifier 都从完整 transcript 重算挑战，从而得到 non-interactive argument。

7.1 transcript 应吸收什么

至少包括：

协议名、版本、curve/field/hash suite 的 domain separator；
public parameters 或 verification key 的唯一 digest；
statement 与全部 public inputs；
每一轮此前发送的 commitments、roots、evaluations；
batch 长度、类型标签与 canonical encoding；
若有 recursion，inner proof 与 accumulator 的明确边界。

sequenceDiagram
    participant P as Prover
    participant T as Transcript
    participant V as Verifier
    P->>T: 吸收协议版本、VK、public input
    P->>T: 吸收第一轮 commitments
    T-->>P: squeeze beta,gamma
    P->>T: 吸收 permutation / lookup commitments
    T-->>P: squeeze alpha
    P->>T: 吸收 quotient commitments
    T-->>P: squeeze zeta
    P->>T: 吸收 ζ 及各 rotation 的 claimed evaluations
    T-->>P: squeeze batching challenge v
    P->>T: 吸收 PCS 辅助 commitments / opening-proof 群元素 / FRI final object
    T-->>P: squeeze u 或 query seed（若协议需要）
    P->>T: 吸收其余 opening data / Merkle paths
    P->>V: proof bytes
    V->>T: 按相同类型与顺序重放
    T-->>V: 得到相同挑战并验证

7.2 不是“调用一次 SHA-256”那么简单

实现必须处理：

canonical serialization：群元素、字段元素只有一种合法字节编码；
长度前缀与类型标签：避免 $a\mathbin{\Vert}bc$ 与 $ab\mathbin{\Vert}c$ 歧义；
subgroup / on-curve check：无效群元素不能进入代数检查；
rejection sampling 或无偏映射：hash-to-field 不应引入可利用偏差；
domain separation：不同 challenge、协议版本、递归层不能共用含义不明的哈希状态；
statement binding：漏吸收 public input 会让证明可被移植到另一个 statement；
顺序一致：prover 和 verifier 必须对完全相同的 typed transcript 操作。

群点检查也必须按具体协议区分“单位元”和“无效点”。identity/infinity 是合法曲线群元素：零多项式的 KZG commitment、常数多项式的零 opening quotient，或某些 IPA 中间结果都可能合法等于单位元。parser 应始终检查 canonical encoding、on-curve 与 subgroup；只有 specification 明确要求某个位置非单位元时才拒绝 identity，不能全局套用“非无穷点”规则。

Fiat–Shamir 的经典安全论证通常在 Random Oracle Model；后量子声称还要核对 Quantum Random Oracle Model 中的变换和具体协议证明。使用后量子 hash 并不会自动补齐 QROM 证明。

8. “承诺隐藏”与“证明零知识”是两件事

8.1 PLONKish 的典型掩码

若 $a(X)$ 在 $H$ 上编码 witness，取随机低次 $r(X)$ 并设

\[\widehat a(X)=a(X)+Z_H(X)r(X).\]

由于 $Z_H(h)=0$，

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

所以门约束不变；但随机点 $\zeta\notin H$ 的值被掩盖。代价是 degree 增长，必须预留 PCS bound 和 quotient budget。

8.2 STARK 的典型问题

Merkle root 对整条 LDE 做确定性承诺，query phase 还会公开少量叶子。如果这些值是 witness 的直接编码，协议可能泄露统计信息。ZK-STARK 需要专门的 randomized encoding、masking polynomial、随机 padding/trace 或 ZK code 技术，并证明查询分布可模拟。

“verifier 只看几个点”不等于零知识；泄露一个精心选择的线性组合也可能泄露 secret。

9. 一次完整的安全归约应长什么样

最终接受概率通常由多项错误项组成：

\[\epsilon_{\mathrm{total}} \le \epsilon_{\mathrm{arith}} +\epsilon_{\mathrm{degree}} +\epsilon_{\mathrm{query}} +\epsilon_{\mathrm{commit}} +\epsilon_{\mathrm{FS}} +\epsilon_{\mathrm{hash}}.\]

它们大致对应：

随机合并时错误约束恰好抵消；
错误 quotient 通过随机点；
远离低度码的 word 躲过 proximity queries；
PCS binding / knowledge assumption 被攻破；
Fiat–Shamir compiler 的模型误差；
Merkle collision 或 transcript collision。

不能把“查询 30 次所以是 120 bit”或“字段是 128 bit 所以 soundness 是 128 bit”作为完整计算。各事件可能相关，尤其多轮 FRI 的 soundness 需要 round-by-round / correlated agreement 分析。

10. 边界与审计清单

SRS 的最大 degree 是否覆盖所有 quotient chunks 和 blinding 后 degree？
verification key、public input、协议版本是否都进入 transcript？
每个随机挑战是否在它要随机化的对象被承诺之后生成？
batching challenge 是否与被批对象 domain-separated？
群点是否做 canonical、on-curve、subgroup 检查，并按每个 proof 字段的协议规则决定 identity/infinity 是允许还是拒绝？
Merkle leaf 是否含列号、行号、宽度或无歧义结构编码？
query index 生成是否无偏，重复 query 如何计入 soundness？
proof parser 是否拒绝 trailing bytes、重复字段和非规范字段元素？
所谓 ZK 是否有 masking 构造与模拟论证，而不是只依赖 commitment？
后量子结论是否覆盖 Fiat–Shamir、hash、commitment 与知识可靠性的完整组合？

11. 自测

从 $f(X)-f(z)=(X-z)q(X)$ 推导 KZG pairing 等式。
解释为什么知道 $\tau$ 会破坏 KZG 的安全直觉。
为什么 Merkle root 无法单独证明 evaluation vector 来自低次多项式？
对三个 commitments $C_f,C_g,C_h$ 写出同点随机批处理公式。
举例说明 transcript 漏吸收 public input 会造成什么重放问题。
为什么 IPA 没有 structured toxic waste，却仍不是后量子方案？

参考

Kate、Zaverucha、Goldberg，Polynomial Commitments
Bowe、Grigg、Hopwood，Halo
Bowe、Grigg、Hopwood，Halo Infinite
Ben-Sasson 等，FRI
Ben-Sasson 等，DEEP-FRI
Arnon 等，WHIR
Halo 2 Book：Proving System

上一篇：有限域、多项式与编码基础 · 下一篇：PLONK 算术化基础 · 返回：总目录

zero-knowledge, stark

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