做区块链底层或者零知识证明这块的朋友应该都对 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 证明生成在同一个库里可能要十几毫秒甚至更久。你没看错证明比验证贵一到两个数量级。所以一旦出现“同一个多项式要开几十上百个点”的场景逐点生成证明就是灾难。假设 d4096开 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 中的 d1 个群元素做一次多标量乘。朴素地逐个做标量乘再相加成本是 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)高群运算朴素 MSMPippenger 窗口预计算O(d) → O(d/log d)高3. 实操用现成库跑通 amortized KZG3.1 工具选型go-kzg-4844 与 arkworks做 KZG 的工程实现我的建议是别重复造轮子除非你做的是学术原型或者对库不放心非要从零撸一遍。现阶段能用且质量高的选择有两个go-kzg-4844以太坊基金会配套 EIP-4844 推出的 Go 实现直接把 FK20 的多项式承诺优化内置进去了。API 简单测试向量齐全适合快速验证性能和正确性。arkworks-rs 里的 ark-poly-commitRust 生态抽象更通用支持更复杂的多项式操作适合做 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 提到 16MSM 快了但预计算表把内存直接顶到好几个 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 和相关优化算法的论文都很短但自己重写一遍代价不低很多坑是踩一遍才知道的。先站在巨人的肩膀上把流程跑通等到性能真正成为瓶颈时再往下钻这条路我走了很多次每次都省下大把时间。