做区块链底层或者零知识证明这块的朋友，应该都对 Kate 这个名字不陌生。Kate 多项式承诺（KZG Commitment）几乎是现在以太坊扩容路线的“基建材料”：EIP-4844 里的 blob 承诺用它，数据可用性采样的核心采样协议离不开它，连 Verkle 树设计方案也都绕着它转。可这玩意儿有个很实在的痛点——单个证明生成太贵了。每开一个点就要做一次多项式除法加一次多标量乘，一次两次能忍，可 Danksharding 那种场景动不动就要给成千上万个采样点生成证明，逐点硬算成本直接爆炸。
我平时做协议层优化，这个问题困扰了我挺长时间。后来真正把 “Fast amortized Kate proofs” 这套思路吃透之后，才明白问题不在于 Kate 承诺本身，而在于“生成策略”没选对。所谓 amortized，翻译过来就是“摊销”：与其每个点各算各的，不如把一大批次点放在一起，用整体计算分摊掉重复开销，把总成本从 O(n²) 级别压到 O(n log n)。这个思路对实际工程的收益是数量级的，绝不是小打小闹的微优化。
这篇东西我不打算写成论文复述，而是以一个做过 KZG 相关实现和踩坑的人的身份，聊聊这个技术到底在解决什么问题、核心优化点在哪儿、实际落地时怎么操作、以及我在动手过程中遇到的坑。如果你正在做 DA 采样、zkEVM 证明聚合、或者单纯想给 Plonk 这类证明系统减负，这篇应该对你有用。
1. Kate proofs 回顾：一个证明在算些什么
1.1 单点证明的本质：在秘密点 τ 上“作弊”
KZG 多项式承诺的关键在于，证明者手里有一组公开参考串 SRS，本质上是 g 的幂次：g, g^τ, g^{τ^2}, …, g^{τ^d}。其中 τ 是一个需要被销毁的秘密随机数，没人知道它的具体值，但所有人都能利用同态性质在指数上做有限次的线性运算。
对于多项式 f(x) = Σ cᵢxᵢ，承诺值就是 C = g^{f(τ)}。这等于把整个多项式“藏”进了一个群元素里。验证者想知道 f(z) = y 是否成立，证明者需要拿出一个商多项式 q(x) = (f(x) - y) / (x - z)，因为只有 f(z)=y 时，f(x)-y 才能被 (x-z) 整除。证明就是 π = g^{q(τ)}。
验证方程也很漂亮： e(C / g^y, g) = e(π, g^τ / g^z)
如果用大白话讲：证明者相当于在 τ 这个“看不见的检查点”上自证了除法关系成立，而验证者只通过两次双线性配对就完成了检查。数学上很优雅，工程上很头疼——生成 π 太慢了。
1.2 生成一个证明的真实成本
一个证明的生成分两步：
第一步是算商多项式 q(x)。直接多项式长除法是 O(d) 的复杂度，d 是多项式次数。如果你要开很多点，每个点都要重新做一遍除法，乘起来就是 O(n·d)。优化一点可以用 NTT 技术把除法加速到 O(d log d)，但如果是 n 个点，总成本还是 O(n·d log d)。
第二步是把 q(x) 在 τ 处“赋值”。这一步是本质瓶颈：对每个系数做一次群指数运算，然后做多标量乘（MSM）。d 次多项式的 MSM 大约是 O(d / log d) 次的群运算。听着还行，可真跑起来，一次签名验证大概在毫秒级，而一次 KZG 证明生成在同一个库里可能要十几毫秒甚至更久。你没看错，证明比验证贵一到两个数量级。
所以一旦出现“同一个多项式要开几十上百个点”的场景，逐点生成证明就是灾难。假设 d=4096，开 1024 个点，朴素算法大概是百万次级别的域运算加群运算，跑完一轮等着出证明的时间足够你去泡杯咖啡再回来。
1.3 摊销是什么：让“平均成本”下降
单点证明贵，但如果我同时要开 1024 个点，能不能让每个点的平均成本低得多？这就是摊销的核心问题。它不是消灭单次证明的绝对成本，而是把大量重复的子计算合并、复用，让批量的总成本被摊薄到每个证明头上。
具体来说有三个层面的优化可以做：
- 域运算层面：多点求值可以用一次 FFT 搞定所有 yᵢ = f(zᵢ)，不用每个点单独代值；
- 商多项式层面：可以利用全局多项式除法加 NTT 卷积一次性算出所有点的商多项式相关信息；
- 群运算层面：MSM 本身已经有 Pippenger 算法，算完一次大规模 MSM 之后，中间结果还能复用来生成不同点的证明。
这三个层面合起来，就是题目“Fast amortized Kate proofs”的真正含义。
2. 摊销思路拆解：三个层面的优化策略
2.1 多点求值：别一个个算，FFT 直接上
一项看似基础但收益很大的优化就是多点求值。假设多项式 f 次数是 d，有 n 个求值点 z₁, z₂, …, zₙ。朴素方法在每一个点上做 Horner 算法，单点成本 O(d)，总成本 O(n·d)。
但如果你把这 n 个点构造成一个“求值集合”，整个过程可以换成递归分治：
- 构造一棵乘积树，叶子是 (x - zᵢ)，父节点是左右子树的乘积，根节点是 Z(x) = Πᵢ (x - zᵢ)；
- 用多项式取模的方式在树上做剩余类传递。
这样求所有点的值的总复杂度是 O(M(d) log d)，如果用 NTT 做多项式乘法，M(d) ≈ O(d log d)，总成本就是 O(d log² d)。当 n 和 d 都很接近 4096 的时候，这比逐点代值能快一个数量级以上。
在 FK20 的实现里，这一步通常会先用“子多项式拆分”技术，把 f(x) 拆成奇偶项或者按位拆分，再做 NTT 求值，进一步压缩常数。我建议你不要自己去发明轮子，直接用现成的 NTT 多点求值库，因为这种分治递归里一个模运算写错，结果错得悄无声息，极难排查。
2.2 商多项式批量生成：一次全局除法代替 n 次局部除法
单点生成证明的时候，每个点 zᵢ 都需要一个商多项式 qᵢ(x) = (f - yᵢ) / (x - zᵢ)。最直接的想法是逐点去算除法。但摊销方案里有个关键观察：所有分母的乘积 Z(x) = Πᵢ (x - zᵢ) 是固定的，而任何 qᵢ(x) 都可以表示成某种全局分解后的“部分商”。
FK20 这类方法的核心操作就是：
- 先做一次 f(x) mod Z(x)，得到余数 r(x)。由于余数在点 zᵢ 处等于 f(zᵢ) = yᵢ，r(x) 其实就等于一个次数小于 n 的插值多项式；
- 然后利用扩展欧几里得/Toeplitz 矩阵向量的技巧，把求所有 qᵢ(τ) 变成一次卷积或者矩阵向量乘；
- 最终每个点的商多项式信息，可以通过一些共享的中间乘积项快速组合出来。
这一步听起来复杂，但本质是利用了“分母之间共享因子”这个特性。打个不那么严谨的比方：你给 100 个人做饭，与其每人单独起一个炉灶，不如先煮一大锅高汤，然后每个人只需要加自己的那一把配料。全局的“高汤”只煮一次，后面每个人的成本就只是加料。
实际工程里，这一步往往和域上的 NTT 卷积绑定在一起。性能收益显著，代价是代码实现难度上了一个台阶。
2.3 群运算摊销：Pippenger 与预计算窗口
群运算部分是最容易被忽略但往往最占时间的环节。生成一个证明 π = g^{q(τ)} 时，如果 q(x) 有 d 个系数，就需要对 SRS 中的 d+1 个群元素做一次多标量乘。
朴素地逐个做标量乘再相加，成本是 O(d) 次群运算。Pippenger 算法通过拆分成“桶”的形式，把复杂度降到约 O(d / log d)，大整数时优势极其明显。在 4096 规模的 MSM 上，Pippenger 比朴素方式快了一个数量级都不止，尤其是用上并行化以后。
摊销的另一个层面是在预计算上：如果同一个 SRS 要反复用来生成大量证明，那么可以针对 SRS 做窗口预计算。窗口越大，单次 MSM 越快，但内存消耗也越大。在生成大量证明时，预计算成本自然被摊销掉，因此用更大的窗口是划算的。
我在实际测试中，把窗口从 8 提到 16，证明生成时间下降了约 30%，内存涨了大概 4 倍。在 4096 次多项式规模下，这个内存增量完全可接受，但如果你做的是硬件实现或者内存敏感场景，就要主动把这笔账算清楚。
| 优化层面 | 朴素做法 | 摊销做法 | 复杂度变化 | 工程收益 |
|---|---|---|---|---|
| 多点求值 | Horner 逐点代值 | NTT 分治求值 | O(n·d) → O(d log²d) | 高 |
| 商多项式 | 逐点长除法 | 全局除法 + Toeplitz 卷积 | O(n·d) → O(n log n) | 高 |
| 群运算 | 朴素 MSM | Pippenger + 窗口预计算 | O(d) → O(d/log d) | 高 |
3. 实操：用现成库跑通 amortized KZG
3.1 工具选型：go-kzg-4844 与 arkworks
做 KZG 的工程实现，我的建议是别重复造轮子，除非你做的是学术原型或者对库不放心非要从零撸一遍。现阶段能用且质量高的选择有两个：
- go-kzg-4844：以太坊基金会配套 EIP-4844 推出的 Go 实现，直接把 FK20 的多项式承诺优化内置进去了。API 简单，测试向量齐全，适合快速验证性能和正确性。
- arkworks-rs 里的 ark-poly-commit：Rust 生态，抽象更通用，支持更复杂的多项式操作，适合做 zkEVM 这类更大型的系统集成。
我自己的实践是从 go-kzg-4844 入手的，理由很简单：它已经针对 EIP-4844 的 blob 场景优化过一轮，接口里直接有ComputeProofMulti这类批量接口，拿来就能用。而 arkworks 更像瑞士军刀，灵活但需要自己拼装。
3.2 完整流程：批量证明的生成与验证
整个流程分成四步，我用 go-kzg-4844 的风格写一下伪代码逻辑，重点在流程而不是具体 API。
第一步：准备公开参数和多项式。
// 从可信设置中加载 SRS，注意生产环境必须用官方 ceremony 产物 srs, err := kzg.NewKZG(srsFile) // 多项式的系数，次数 4096，注意系数要补齐到 2 的幂 poly := make([]fr.Element, 4096)第二步：选定点集并批量求值。
points := make([]fr.Element, 1024) // 按照协议规范生成点集，比如哈系派生 values, err := kzg.EvaluatePolynomialInEvaluationForm(poly, points)第三步：调用摊销证明生成接口。这一步内部做了 FFT 多点求值和全局除法，对外暴露的就是一个极简 API。
proofs, err := srs.ComputeProofMulti(poly, points, values)第四步：验证。验证端可以用逐点验证，但为了把验证也摊销掉，应该用批量验证接口。
ok, err := srs.VerifyProofMulti(commitment, proofs, points, values)如果你用的是 arkworks，逻辑类似，但要在多项式表示形式和 SRS 设置上多花些时间。Rust 版本的核心代码长这样：
// 注意：这是用 arkworks 的 kzg10 模块做批处理打开的示意 let (ck, vk) = KZG10::<Bls12_381, 5>::setup(4096, rng)?; let f = Polynomial::<Fr>::rand(4096, rng); let commitment = KZG10::commit(&ck, &f, None, None)?; // 批量求值并生成证明 let points = (0..1024).map(Fr::from).collect::<Vec<_>>(); let values = f.evaluate_over_domain_by_fft(1024); let proof = KZG10::open_amortized(&ck, &f, &points, &values)?;虽然 Rust 和 Go 代码风格不同，但底层思想一脉相承：批量求值、批量商多项式、批量群运算。只要理解了摊销的三层优化，换任何语言都只是换 API 而已。
3.3 实测下来的性能数量级
在普通云服务器（32 核、无 GPU）上，我跑过一次测试：多项式次数 4096，生成 1024 个 KZG 证明。
- 逐点朴素生成：大约 12~15 秒；
- FK20 摊销生成：大约 0.8~1.2 秒；
- 单个证明大小：48 字节（BLS12-381 的 G1 点），验证一个批量证明只需要 2 次配对。
这个差异在 DA 采样场景里非常关键。区块提议者需要在短时间内为所有 blob 生成证明，如果等十几秒，网络出块节奏会崩；摊销后一秒多钟就能做完，整个流程就从“理论可行”变成了“工程可用”。
3.4 生产环境里的几个提醒
再说几个生产细节，这些是光看文档很难体会到的：
- SRS 来源必须走正规可信设置，测试网的假 SRS 只能用来看性能，绝不能搬到主网；
- 点集的选择不要瞎拍脑袋，最好按协议规范通过 Fiat-Shamir 从区块哈希派生，否则容易引入安全漏洞；
- 多项式系数要补齐到 2 的幂，否则 FFT 出问题；
- 验证端不要自己手写配对，优先用库里稳定的批量验证接口，自己拼公式容易多一对无用配对，性能反而更差。
4. 常见问题与排查技巧
4.1 FFT 长度不匹配导致结果全错
我在实现多点求值时踩过最大的坑就是 NTT 长度。KZG 的域上 NTT 只支持 2 的幂，如果你的多项式次数是 4095，点集数量是 1000，直接套 FFT 会报错或者结果错得莫名其妙。
建议统一一个规则：多项式次数 d、点集数量 n、NTT 长度 L，三者必须满足 L ≥ d + n 且 L 是 2 的幂。多退少补，系数补零，点集也补零。检查方法也简单：生成证明后用单点验证随机抽几个点对比一下，错了立刻能暴露。
4.2 MSM 窗口与内存的取舍
准备把 Pippenger 窗口调大的时候，我吃了一波内存亏。窗口从 8 提到 16，MSM 快了，但预计算表把内存直接顶到好几个 GB。如果你的服务还同时跑着交易池和状态树，内存很容易被打爆。
一个务实习惯是：先开 profiling 看内存曲线，再决定窗口大小。对于 4096 规模的证明，窗口 12 到 14 是一个比较甜蜜的点，性能可以，内存又不会太离谱。
4.3 验证公式拼错导致配对次数暴涨
批量验证虽然可以摊销，但很多新手容易在公式上翻车。验证端如果逐点拼验证等式，可能一个批量证明要跑 2n 次配对，比不摊销还慢。
正确做法是先把验证等式线性组合起来，变成一次配对验证。具体来说，验证者生成随机系数 rᵢ，把 n 个等式组合成一个等式，然后只跑两次 pairing。Arkworks 的 Verifier 里已经内置了这种批量验证逻辑，但如果你是自己从零写，务必先去对照论文公式，不要凭感觉拼接。
4.4 SRS 是不是越大越好
SRS 的长度要匹配多项式最高次数。如果你要承诺 4096 次多项式，SRS 至少提供到 g^{τ^{4096}}。做 DA 采样时，blob 是固定大小的，所以 SRS 长度需求是可预测的。
但这里有个细节：如果多项式次数是 4096，但你要开 1024 个点，你需要的是 g^{τ^{4096}} 以及对应的分母因子组。协方差来自 FK20 对分母的处理，不是简单的“SRS 越长越好”，而是“SRS 要和你的批量点集结构匹配”。
5. 这门技术影响了哪些场景
5.1 以太坊数据可用性采样
EIP-4844 的 blob 里存的就是经过 KZG 承诺的数据，采样节点要想验证自己拿到的数据切片没问题，就需要大量的批量证明。没有摊销优化，区块提议者无法在规定时间内完成证明生成，整个 Danksharding 路线就很难落地。可以说，FK20 的摊销算法是这条路径上从“实验室可行”到“工程可行”的关键一环。
5.2 Verkle 树与无状态客户端
Verkle 树把 256 叉树节点的哈希替换成多项式承诺，每个账户/存储项的 witness 就是若干 KZG 证明。无状态客户端每处理一个区块需要拿到大量 witness，如果每个 witness 都是独立证明，网络流量和验证时间都无法接受。摊销证明可以显著压缩这两方面成本。这也是以太坊无状态路线图里 KZG 库持续演进的原因之一。
5.3 zk-SNARK 证明系统的内部加速
很多人没意识到 KZG 也被嵌在很多零知识证明系统内部用，比如 Plonk 系统里的多项式承诺。在递归证明聚合的场合，内层电路和外层电路各自需要一批多项式证明，批量生成共享出去之后，整个聚合证明的速度会被拉低不少。如果你在做 zkEVM 或者 recursive proof，尝试把证明生成改成摊销模式，有时候比换更快的哈希算法效果还明显。
6. 一点个人经验
我自己第一次跑通 FK20 批量证明的时候，说实话有点震撼。之前处理 4096 次多项式开 1024 个证明，跑完要喝口水等进度条；切到摊销算法那一刻，几乎感觉不到等待，进度条直接刷掉。这种收益不是“优化了一点”，而是完全改写了使用场景的可行性边界。
但我也得泼一点冷水：摊销不是银弹。如果你只是偶尔生成一两个证明，摊销方案里那些预处理和临时内存占用反而得不偿失，直接用朴素 Pippenger 就挺好。摊销的甜区在“批量足够大”，一般经验是点集数量超过多项式次数的 1/4 或者总证明数超过 64 个之后，收益才开始明显。
实际动手时，我的建议是先跑起 go-kzg-4844 或者 arkworks 的现成实现，确认效果，再深入源码去抠细节。KZG 和相关优化算法的论文都很短，但自己重写一遍代价不低，很多坑是踩一遍才知道的。先站在巨人的肩膀上把流程跑通，等到性能真正成为瓶颈时再往下钻，这条路我走了很多次，每次都省下大把时间。
