多项式承诺的统一看法：KZG、IPA、FRI
Scope: KZG、IPA 与 FRI 在 commitment、claim、proof、verify 四个接口上的差异。
前一篇已经把 computation 变成了多项式对象：QAP 里有 \(A_{\mathbf{w}}, B_{\mathbf{w}}, C_{\mathbf{w}}, H, Z\)，AIR 里有 trace polynomials 与 composition polynomial。到了这里，问题不再是“如何把程序写成多项式”，而是“如何承诺这些多项式，并在不泄露全部系数的前提下证明某些点值或低度性声明”。
三种方案都回答同一个问题，但使用不同 machinery。先固定最小形式：
我已经对一个多项式 \(f(X)\) 做了承诺。现在我要证明在点 \(z\) 上，它的取值确实是 \(y = f(z)\)，或者至少证明它来自某个低度多项式家族。
在这个统一接口下：
- KZG 把 opening 变成 pairing verification equation
- IPA 把 opening 变成 coefficient vector 和 evaluation vector 的 inner-product proof
- FRI 把 low-degree claim 变成 repeated folding and query consistency checks
下面比较各自的 evaluation evidence，以及对应的 setup、proof size 和 verifier cost。1 2 3
Polynomial Commitment 的统一接口
先定义抽象接口。一个 polynomial commitment scheme 通常包含：
Commit(f)：对多项式 \(f(X)\) 生成承诺 \(C\)Open(f, z)：给出点 \(z\) 处的 opening proof，证明 \(f(z)=y\)Verify(C, z, y, \pi)：检查证明 \(\pi\) 是否接受
核心 instance 是：
\[ \text{given } C \text{ and } z,\ \text{prove that } y = f(z). \]这里有两个最基本的性质。
Correctness
若承诺确实来自某个多项式 \(f\)，且 prover 用正确 witness 生成 opening proof，那么 verifier 应当接受：
\[ \mathrm{Verify}(C, z, f(z), \pi) = 1. \]Binding
若一个承诺 \(C\) 可以被打开成同一点上的两个不同值
\[ f(z) = y \neq y' = f'(z), \]且两边都能通过验证，那么 scheme 的 binding 就崩了。不同方案对 binding 的来源不同：
- KZG 依赖 structured reference string 和代数假设
- IPA 依赖离散对数类假设与向量承诺 binding
- FRI 更偏向“oracle codeword 确实接近某个低度多项式”的查询式绑定
也就是说，三者都在提供“你不能随便把同一个 commitment 开成互相冲突的 claim”的保证，但对象和证明方法并不一样。
Evaluation Proof Is The Real Interface
多项式承诺的主要技术负担落在 evaluation proof。
后续 SNARK / STARK 需要验证：
- 它在某个点的值是什么
- 它是否满足某个商多项式关系
- 它是否低度
- 多个承诺对象之间是否在随机点上一致
因此本篇围绕 opening contract 展开。
KZG：把开点变成配对检验方程
KZG 利用隐藏点 \(\tau\) 的 powers-of-tau 结构，在群中编码 \(f(\tau)\)。
Setup And Commitment
设多项式次数上界为 \(d\)。structured reference string 提供
\[ g_1, g_1^\tau, g_1^{\tau^2}, \dots, g_1^{\tau^d} \]以及另一组配对群元素
\[ g_2, g_2^\tau. \]这里的 toxic waste 就是 \(\tau\)。若有人知道它，系统会出大问题。
对
\[ f(X) = \sum_{i=0}^d f_i X^i, \]KZG commitment 定义为
\[ C = g_1^{f(\tau)} = \prod_{i=0}^d \left(g_1^{\tau^i}\right)^{f_i}. \]prover 在不知道 \(\tau\) 的前提下，利用 SRS 对 \(f(\tau)\) 做群编码。
Opening At \(z\)
若要证明
\[ f(z) = y, \]先构造 quotient polynomial
\[ q(X) = \frac{f(X) - y}{X - z}. \]这一步的意义非常关键。因为“在点 \(z\) 上取值为 \(y\)”当且仅当
\[ X-z \mid f(X)-y. \]也就是商多项式 \(q(X)\) 存在。
prover 然后给出 witness
\[ \pi = g_1^{q(\tau)}. \]Verification Equation
现在把 evaluation claim 推到验证方程。
由
\[ f(X)-y = q(X)(X-z) \]在 \(X=\tau\) 处代入，得
\[ f(\tau)-y = q(\tau)(\tau-z). \]转成群与 pairing 语言，就是
\[ \begin{aligned} e\!\left(C / g_1^y,\ g_2\right) &= e\!\left(\pi,\ g_2^{\tau-z}\right). \end{aligned} \]通常也写成
\[ \begin{aligned} e\!\left(C / g_1^y,\ g_2\right) &= e\!\left(\pi,\ g_2^\tau / g_2^z\right). \end{aligned} \]左边编码的是 \(f(\tau)-y\)，右边编码的是 \(q(\tau)(\tau-z)\)。两边相等，就等价于 quotient relation 成立。
这就是 KZG opening equation。
Key Observation. KZG 用商多项式把 evaluation claim 变成秘密点 \(\tau\) 上的等式，再用 pairing 检查该等式。
What KZG Buys
KZG 最吸引人的地方很明确：
- proof size 常数级
- verifier 工作量基本是常数个 pairings
- 非常适合 QAP / PLONKish 这类大量依赖多项式开点的系统
代价也同样明确：
- 需要 structured setup
- toxic waste \(\tau\) 不能泄露
- 透明性差于 FRI
KZG 以结构化 setup 换取紧凑开点。
IPA：把开点变成内积证明
IPA 系 polynomial commitment 的出发点不同。它不依赖秘密点 \(\tau\)，而是把多项式看作系数向量，并把“在点 \(z\) 求值”看成一个内积。
Coefficient Vector View
设
\[ f(X) = \sum_{i=0}^{n-1} a_i X^i, \]把系数写成向量
\[ \mathbf{a} = (a_0, a_1, \dots, a_{n-1}). \]若用固定生成元向量 \(\mathbf{G} = (G_0, \dots, G_{n-1})\) 构造系数承诺，常见形式可写成
\[ C = \langle \mathbf{a}, \mathbf{G} \rangle \]或在需要 hiding 时再加 blinding term。这里不展开 hiding 细节，先盯 evaluation contract。
Evaluation Is An Inner Product
在点 \(z\) 处，多项式取值可写成
\[ f(z) = \sum_{i=0}^{n-1} a_i z^i. \]定义 evaluation vector
\[ \mathbf{b}(z) = (1, z, z^2, \dots, z^{n-1}), \]则
\[ f(z) = \langle \mathbf{a}, \mathbf{b}(z) \rangle. \]因此“证明 \(f(z)=y\)”就变成了：
我已经承诺了向量 \(\mathbf{a}\)，现在证明它与公开向量 \(\mathbf{b}(z)\) 的内积恰好是 \(y\)。
这一步就是 IPA-based evaluation proof 的核心直觉。
Folding The Dimension
内积证明的强项在于它能递归折叠维度。把向量拆成左右两半：
\[ \mathbf{a} = (\mathbf{a}_L, \mathbf{a}_R),\qquad \mathbf{b} = (\mathbf{b}_L, \mathbf{b}_R), \]然后通过一轮挑战把长度 \(n\) 的内积证明压缩成长度 \(n/2\) 的新内积证明。重复下去，最终把“高维内积正确”收束成若干轮 transcript 加一个很小的终点检查。
标准 IPA 同时承诺两组向量和内积值。写
\[ P=\langle\mathbf{a},\mathbf{G}\rangle+\langle\mathbf{b},\mathbf{H}\rangle+\langle\mathbf{a},\mathbf{b}\rangle U. \]将向量与基底分成左右两半后，prover 发送交叉项
\[ 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. \]verifier 从 transcript 采样 \(x\in\mathbb{F}^{*}\)，双方折叠
\[ \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} \]更新后的 commitment 为
\[ P'=x^2L+P+x^{-2}R. \]展开两边可验证
\[ P'=\langle\mathbf{a}',\mathbf{G}'\rangle+\langle\mathbf{b}',\mathbf{H}'\rangle+\langle\mathbf{a}',\mathbf{b}'\rangle U. \]一轮后维度减半，重复 \(\log_2 n\) 轮到标量终点。proof 含 \(2\log_2n\) 个主要轮消息；verifier 仍要完成与原向量长度相关的 MSM，不能把“对数轮数”直接写成“总验证工作量对数级”。该方案无需 powers-of-tau toxic waste。
What IPA Buys
IPA 系方案更接近“transparent or hash-derived generators, logarithmic proof”这一侧。相比 KZG：
- proof 更长
- verifier 更重
- 但 setup 边界通常更干净，不需要 powers-of-tau 式秘密结构
这也是为什么 IPA 系方案在递归、无 pairings 场景下很有吸引力。
FRI：把低度性变成折叠与查询
FRI 从 evaluation domain 上的 codeword 出发：
我给出某个 evaluation domain 上的 codeword，并声称它来自一个低度多项式。
所以 FRI 的主叙事是 low-degree testing contract，而不是单点开值方程。
Codeword View
设域上有评估域 \(D\)，prover 持有某个函数表
\[ \{f(x)\}_{x \in D}. \]它会先把这份 codeword 通过 Merkle tree 之类的 oracle commitment 固定下来。verifier 接着要检查：
- 这份 codeword 是否接近某个低于给定次数界的多项式
- 若还附带 evaluation claim，则这些查询是否与目标点值或 composition relation 一致
也就是说，FRI 的 commitment 更像“承诺一张评估表”，然后通过查询证明“这张表确实来自低度对象”。
Even/Odd Decomposition And Folding
FRI 的直觉核心是 even/odd decomposition。任意多项式都可写成
\[ f(X) = f_0(X^2) + X f_1(X^2), \]其中 \(f_0\) 收集偶次项，\(f_1\) 收集奇次项。
取一个随机挑战 \(\beta\)，定义新多项式
\[ g(X) = f_0(X) + \beta f_1(X). \]于是如果知道 \(f(x)\) 和 \(f(-x)\)，就能把它们折叠成关于 \(g(x^2)\) 的信息。更显式地，常见写法是
\[ g(x^2) = \frac{f(x)+f(-x)}{2} + \beta \cdot \frac{f(x)-f(-x)}{2x}. \]这一轮 folding 会把“度数上界 \(d\) 的低度性问题”压到“大约度数上界 \(d/2\) 的新问题”。
重复多轮后，verifier 得到一个很小的最终多项式，并通过随机查询检查各轮局部一致性。
Oracle Commitment 与 Query Consistency
每一轮的顺序属于 soundness contract：
- prover 先对当前 codeword \(f_i|_{D_i}\) 建立 Merkle commitment；
- verifier 在 commitment 固定后采样 folding challenge \(\beta_i\)；
- prover 计算下一轮 codeword \(f_{i+1}|_{D_{i+1}}\) 并再次承诺；
- 所有轮 commitment 固定后，verifier 才采样 query 位置。
对一条查询路径，prover 打开
\[ f_i(x),\qquad f_i(-x),\qquad f_{i+1}(x^2) \]及相应 Merkle authentication paths。verifier 先验证叶子属于已承诺的 oracle，再检查
\[ f_{i+1}(x^2)=\frac{f_i(x)+f_i(-x)}{2}+\beta_i\frac{f_i(x)-f_i(-x)}{2x}. \]最终轮多项式足够小，可直接发送系数并检查次数界与所有终点 opening。Merkle binding 阻止 prover 在看到 query 后改写 codeword；随机 \(\beta_i\) 阻止提前选择能在所有折叠轮抵消的高次项；重复独立 query 将 Reed-Solomon 距离界转化为目标 soundness error。单条路径只提供一次抽查，不能单独支撑生产参数。
What FRI Is Really Proving
FRI 证明以下三项：
- codeword 在各轮 folding 下保持一致
- 最终缩小后的对象确实低度
- 因而原始 codeword 也应接近某个低度多项式
其接口是 query-based oracle proof of low degree。
如果在 STARK 场景里还要证明某个 evaluation claim，通常会先把 claim 合并进 composition polynomial 或 quotient-style low-degree object，然后再交给 FRI 去证明低度与一致性。
What FRI Buys
FRI 的优势也很明确：
- transparent setup
- 不需要 toxic waste
- 非常适合 AIR / trace polynomial / low-degree testing 场景
代价则是：
- proof 通常比 KZG、IPA 更大
- verifier 需要做多轮查询和哈希验证
- claim 更偏向“低度 oracle 是否一致”，而不是单个 pairing equation
FRI 以 oracle/query machinery 实现 transparent low-degree testing。
统一比较：KZG、IPA、FRI
现在可以把三者拉回同一表面。
统一问题
三者都在回答：
\[ \text{What evidence convinces the verifier that a committed polynomial object satisfies the claimed evaluation or low-degree property?} \]不同点在于“证据”长什么样。
KZG
- 对象：\(f(\tau)\) 的结构化承诺
- opening 证据：quotient polynomial at \(\tau\)
- verifier machinery：pairing equation
- 典型特征：常数大小 proof，常数级验证，trusted setup
IPA
- 对象：系数向量承诺
- opening 证据：inner-product relation transcript
- verifier machinery：对数轮折叠与 MSM 检查
- 典型特征：对数 proof，无 toxic waste，pairing-free
FRI
- 对象：评估域上的 codeword oracle
- opening / low-degree 证据：folding transcript + query consistency
- verifier machinery：随机查询、Merkle 验证、低度检查
- 典型特征：transparent，proof 较大，验证偏 query-based
Trusted Setup Versus Transparency
三者的 setup 条件可以精确写成：
- KZG 需要结构化参考串，因为 verifier 最终要利用 \(\tau\) 的代数结构
- IPA 通常只需公开 generators，可由 hash-to-curve 派生，不需要 toxic waste
- FRI 依赖公开评估域、随机挑战和 oracle commitment，因此是 transparent
transparent 表示安全性不依赖某个隐藏结构参数保持秘密。
What They Naturally Pair With
这三类方案也自然对应不同的证明系统接口：
- KZG 很自然地配 QAP、PLONKish 与 pairing-based SNARK
- IPA 很自然地配向量系数承诺、递归友好和 pairing-free 系统
- FRI 很自然地配 AIR、STARK、低度测试型协议
这种对应由各方案消费的 polynomial surface 决定。
Summary
三种方案共享以下 interface：
- 先承诺一个多项式对象
- 再证明它满足 evaluation 或 low-degree claim
- verifier 只通过简化后的代数或查询对象完成检查
KZG 用的是 quotient polynomial 和 pairing equation：
\[ e(C/g_1^y, g_2) = e(\pi, g_2^{\tau-z}) \]IPA 用的是
\[ f(z) = \langle \mathbf{a}, \mathbf{b}(z) \rangle \]再加 inner-product folding transcript。
FRI 用 even/odd decomposition、repeated folding 与认证查询检查低度性。
所以：
- 若你想要极短开点证明并接受 trusted setup，KZG 很强
- 若你想要 pairing-free、对数级证明和更干净的 setup 边界，IPA 很自然
- 若你要 transparent low-degree testing，并且能接受更大的 proofs 与查询式验证，FRI 是自然答案
下一篇的 Groth16 将消费 KZG/QAP 接口：商多项式在秘密点评估后如何进入 pairing check。
References
-
Aniket Kate, Gregory M. Zaverucha, and Ian Goldberg, Constant-Size Commitments to Polynomials and Their Applications, 2010. ↩︎
-
Benedikt Bünz et al., Bulletproofs: Short Proofs for Confidential Transactions and More, 2018. Inner-product argument sections. ↩︎
-
Eli Ben-Sasson et al., FRI / STARK related references on low-degree testing and transparent proof systems. ↩︎