dusk-plonk的FFT模块剖析EvaluationDomain与多项式快速变换实现原理【免费下载链接】plonkPure Rust implementation of the PLONK ZKProof System done by the Dusk team项目地址: https://gitcode.com/gh_mirrors/plo/plonkdusk-plonk是 Dusk 团队用纯 Rust 实现的 PLONK 零知识证明系统而其 src/fft/ 目录下的FFT 模块正是整个证明引擎的性能核心。本文带你读懂EvaluationDomain评估域、快速傅里叶变换FFT/IFFT在有限域上的实现原理——为什么 PLONK 需要 O(n log n) 的多项式变换、2 的幂次域从何而来、蝶形运算如何并行加速。即使你是零知识证明新手也能快速建立完整认知。一、为什么 PLONK 离不开 FFTPLONK 证明的数学骨架是多项式。约束系统会把每一列witness、selector、permutation 等视为一个多项式证明过程中反复进行系数形式 ↔ 点值形式互相转换多项式的加法、乘法逐点相乘在随机点 τ 上求值如果直接在系数形式下做乘法复杂度是 O(n²)而把多项式变换到在 n 个特殊点上取值的形式后乘法退化为 O(n) 的逐点相乘。这种特殊点的选取就是 FFT 模块存在的全部意义。模块组织非常清晰文件职责src/fft.rs模块入口按 feature 条件编译导出子模块src/fft/domain.rsEvaluationDomain评估域 核心 FFT 算法src/fft/evaluations.rsEvaluations点值形式多项式带域信息src/fft/polynomial.rsPolynomial系数形式多项式模块头部注释点明了设计动机引自src/fft/domain.rs在基于配对的 SNARK 中我们需要在根为约束系统各约束对应点的目标多项式上计算商多项式。为了高效我们选这些根为有限域中 2^n 次单位根的幂。这样就能对该域做 O(n log n) 的 FFT从而以 O(n) 完成多项式运算。二、EvaluationDomain一个 2 的幂次的单位根子群EvaluationDomain定义于 src/fft/domain.rs是有限域上的乘法子群其成员形如1, ω, ω², ω³, …, ω^(n-1)其中 ω 是 n 次单位根ωⁿ 1。它本质上是一个查表友好的坐标网格所有点值运算都发生在这个网格上。1. 为什么必须是 2 的幂次构造入口EvaluationDomain::new(num_coeffs)的逻辑num_coeffs.next_power_of_two()—— 把系数个数向上取到 2 的幂次比如 100 个系数 → 128 点域校验log_size_of_group TWO_ADACITY—— 有限域BLS12-381 的标量域中 2 的幂次子群有大小上限超出即报InvalidEvalDomainSize错误见 src/error.rs从域常数ROOT_OF_UNITY最大 2 次幂次单位根出发连续平方(TWO_ADACITY - log_size_of_group)次得到刚好满足 ωⁿ 1 的子群生成元group_genROOT_OF_UNITY ──平方k次──▶ group_genn 次单位根这一步是预计算域内只需要保存 5 个标量字段size_as_field_element、size_inv、group_gen、group_gen_inv、generator_inv后续 FFT 全程复用避免重复求逆和取幂。2. 域元素迭代器domain.elements()返回一个轻量迭代器从 1 开始每步乘以group_genO(1) 时间推进常用于验证和调试点值序列。三、FFT 核心算法位反转 蝶形运算 Dusk 的 FFT 实现是迭代版 Cooley-Tukey 算法共两个阶段阶段 1位反转置换bitreverse_permuteDITDecimation-In-TimeFFT 要求输入按索引二进制位反转的顺序排列。例如 8 点域中原索引01234567二进制000001010011100101110111位反转后000100010110100101111011新位置04265371代码用bitreverse(k, log_n)逐位翻转只在k rk时交换一次保证 O(n) 完成且不重复交换。阶段 2逐级蝶形运算butterfly对m 1, 2, 4, …, n/2每一级计算本级单位根w_m ω^(n / 2m)把数组切成2m长度的块每块前后两半执行t w · right[i] right[i] left[i] - t ← 奇数项 left[i] left[i] t ← 偶数项 w ← w · w_m两级循环共执行 log₂n 级每级 O(n)总复杂度O(n log n)。这是所有现代 FFT 库的标准结构serial_fftsrc/fft/domain.rs 中的串行版本正是教科书式实现。3. IFFT换个根、乘个 1/n逆变换复用同一套代码只需两处变化用group_gen_invω 的逆代替group_gen结束后每个元素乘以size_inv即 1/n域内乘法pub(crate) fn ifft_in_place(self, evals: mut VecBlsScalar) { evals.resize(self.size(), BlsScalar::zero()); best_fft(evals, self.group_gen_inv, self.log_size_of_group); evals.par_iter_mut().for_each(|val| *val * self.size_inv); }domain.fft(coeffs)与domain.ifft(evals)就构成了一次完整的系数 ⇄ 点值往返往返测试roundtrip直接出现在模块的单测中。4. 并行加速策略 ⚡开启stdfeature 后best_fft会按输入规模自适应选择执行路径条件策略n 4096纯串行serial_fftn ≥ 4096 且块数 ≥ 4par_chunks_mut块级并行rayon块数不足 4 但 n ≥ 4096 且线程 ≥ 4parallel_butterfly_chunk在块内部按线程切分并行其余串行蝶形并行蝶形的巧思把每块按线程数再细分为每个子区间预先算好单位根种子w_m的幂各线程从自己的种子起步独立推进避免了加锁和归约——因为蝶形运算中同一块内不同位置的元素互不干扰。单元测试parallel_fft_matches_serial_fft_for_large_domain显式验证了 3/4/9 线程下并行结果与串行结果逐位相等这在高并发数值代码里是很关键的保证。四、Coset FFT商多项式的关键技巧 PLONK 中商多项式 q(·) 的度数会超过主域需要在8n 大小的域上求值。但直接扩大域代价高标准技巧是余弦集coset变换coset_fft先给系数逐位乘上G, G², G³, …G 为域乘性生成元即在余弦集上平移求值的预乘步骤再做普通 FFTcoset_ifft先做 IFFT再逐位乘上G⁻¹, (G⁻¹)², …把平移约掉coset_fft fft( coeffs · [G^i] ) coset_ifft ifft( evals ) · [G^(-i)]效果用 n 点 FFT 就能求出多项式在偏移后网格 8n 个位置上的值。quotient_domain.coset_fft / coset_ifft被大量用于商多项式的构造与还原见 src/proof_system/quotient_poly.rs。余弦集还配套了两个校验器matches_linear_poly_over_coset与matches_vanishing_poly_over_coset用于验证特定多项式的求值序列符合闭式解——这是防降级验证opening verification的重要组成。五、Polynomial 与 Evaluations两种表示的自由切换FFT 模块最优雅的设计是把表示形式抽象成两个结构体1.Polynomial系数形式—— src/fft/polynomial.rsstruct Polynomial { coeffs: VecBlsScalar } // coeffs[i] x^i 的系数from_coefficients_vec自动裁剪高位零系数evaluate(self, value)Horner 幂次法在任意点求值用于验证实现了Add / Sub / Mul等标准代数运算2.Evaluations点值形式—— src/fft/evaluations.rsstruct Evaluations { evals: VecBlsScalar, domain: EvaluationDomain, // 关键域信息内嵌 }域内嵌是亮点设计加法/乘法/除法逐点执行天然 O(n)实现里assert_eq!(self.domain, other.domain)直接拒绝跨域运算杜绝隐式错误interpolate()一行调用domain.ifft_in_place完成插值还原无需外部传参序列化to_var_bytes / from_slice会把域一并写入反序列化时重建标准域做一致性校验恶意构造的字节无法注入非法域参数3. 转换路径一览系数 [a₀, a₁, …] ── domain.fft ──────────▶ 点值 [p(1), p(ω), p(ω²), …] ◀── domain.ifft插值──┘在 src/compiler/prover.rs 的预处理阶段可以看到真实用法EvaluationDomain::new(constraints)依据约束数建主域EvaluationDomain::new(quotient_size)另建 8 倍域给商多项式对置换多项式s_sigma_1..4逐一domain.fft转入点值形式供后续逐点约束求值使用六、小结这套 FFT 设计的三个精髓 ✨设计点价值2^n 单位根子群 预计算域参数FFT 各阶段无需重复取幂/求逆纯查表式推进自适应并行4096 点阈值 线程数判断小电路零并行开销大电路2^16 约束约 7.9s 证明吃满多核余弦集 FFT 域内嵌的 Evaluations商多项式 8n 域高效求值类型系统层面杜绝跨域运算与恶意序列化对新手而言建议的阅读路线是先看 src/fft/domain.rs 中serial_fft和butterfly_range两个函数合计不到 30 行完整呈现 DIT-FFT再顺着best_fft理解并行调度最后到quotient_poly.rs看余弦集变换在证明流程中的落点。掌握这条主线你就读懂了 dusk-plonk 性能优化的发动机舱。 项目更多设计细节可参考规格文档 docs/dusk-plonk-specs.pdf基准测试可用cargo bench见 benches/plonk.rs。【免费下载链接】plonkPure Rust implementation of the PLONK ZKProof System done by the Dusk team项目地址: https://gitcode.com/gh_mirrors/plo/plonk创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 dusk-plonk的FFT模块剖析：EvaluationDomain与多项式快速变换实现原理
dusk-plonk的FFT模块剖析EvaluationDomain与多项式快速变换实现原理【免费下载链接】plonkPure Rust implementation of the PLONK ZKProof System done by the Dusk team项目地址: https://gitcode.com/gh_mirrors/plo/plonkdusk-plonk是 Dusk 团队用纯 Rust 实现的 PLONK 零知识证明系统而其 src/fft/ 目录下的FFT 模块正是整个证明引擎的性能核心。本文带你读懂EvaluationDomain评估域、快速傅里叶变换FFT/IFFT在有限域上的实现原理——为什么 PLONK 需要 O(n log n) 的多项式变换、2 的幂次域从何而来、蝶形运算如何并行加速。即使你是零知识证明新手也能快速建立完整认知。一、为什么 PLONK 离不开 FFTPLONK 证明的数学骨架是多项式。约束系统会把每一列witness、selector、permutation 等视为一个多项式证明过程中反复进行系数形式 ↔ 点值形式互相转换多项式的加法、乘法逐点相乘在随机点 τ 上求值如果直接在系数形式下做乘法复杂度是 O(n²)而把多项式变换到在 n 个特殊点上取值的形式后乘法退化为 O(n) 的逐点相乘。这种特殊点的选取就是 FFT 模块存在的全部意义。模块组织非常清晰文件职责src/fft.rs模块入口按 feature 条件编译导出子模块src/fft/domain.rsEvaluationDomain评估域 核心 FFT 算法src/fft/evaluations.rsEvaluations点值形式多项式带域信息src/fft/polynomial.rsPolynomial系数形式多项式模块头部注释点明了设计动机引自src/fft/domain.rs在基于配对的 SNARK 中我们需要在根为约束系统各约束对应点的目标多项式上计算商多项式。为了高效我们选这些根为有限域中 2^n 次单位根的幂。这样就能对该域做 O(n log n) 的 FFT从而以 O(n) 完成多项式运算。二、EvaluationDomain一个 2 的幂次的单位根子群EvaluationDomain定义于 src/fft/domain.rs是有限域上的乘法子群其成员形如1, ω, ω², ω³, …, ω^(n-1)其中 ω 是 n 次单位根ωⁿ 1。它本质上是一个查表友好的坐标网格所有点值运算都发生在这个网格上。1. 为什么必须是 2 的幂次构造入口EvaluationDomain::new(num_coeffs)的逻辑num_coeffs.next_power_of_two()—— 把系数个数向上取到 2 的幂次比如 100 个系数 → 128 点域校验log_size_of_group TWO_ADACITY—— 有限域BLS12-381 的标量域中 2 的幂次子群有大小上限超出即报InvalidEvalDomainSize错误见 src/error.rs从域常数ROOT_OF_UNITY最大 2 次幂次单位根出发连续平方(TWO_ADACITY - log_size_of_group)次得到刚好满足 ωⁿ 1 的子群生成元group_genROOT_OF_UNITY ──平方k次──▶ group_genn 次单位根这一步是预计算域内只需要保存 5 个标量字段size_as_field_element、size_inv、group_gen、group_gen_inv、generator_inv后续 FFT 全程复用避免重复求逆和取幂。2. 域元素迭代器domain.elements()返回一个轻量迭代器从 1 开始每步乘以group_genO(1) 时间推进常用于验证和调试点值序列。三、FFT 核心算法位反转 蝶形运算 Dusk 的 FFT 实现是迭代版 Cooley-Tukey 算法共两个阶段阶段 1位反转置换bitreverse_permuteDITDecimation-In-TimeFFT 要求输入按索引二进制位反转的顺序排列。例如 8 点域中原索引01234567二进制000001010011100101110111位反转后000100010110100101111011新位置04265371代码用bitreverse(k, log_n)逐位翻转只在k rk时交换一次保证 O(n) 完成且不重复交换。阶段 2逐级蝶形运算butterfly对m 1, 2, 4, …, n/2每一级计算本级单位根w_m ω^(n / 2m)把数组切成2m长度的块每块前后两半执行t w · right[i] right[i] left[i] - t ← 奇数项 left[i] left[i] t ← 偶数项 w ← w · w_m两级循环共执行 log₂n 级每级 O(n)总复杂度O(n log n)。这是所有现代 FFT 库的标准结构serial_fftsrc/fft/domain.rs 中的串行版本正是教科书式实现。3. IFFT换个根、乘个 1/n逆变换复用同一套代码只需两处变化用group_gen_invω 的逆代替group_gen结束后每个元素乘以size_inv即 1/n域内乘法pub(crate) fn ifft_in_place(self, evals: mut VecBlsScalar) { evals.resize(self.size(), BlsScalar::zero()); best_fft(evals, self.group_gen_inv, self.log_size_of_group); evals.par_iter_mut().for_each(|val| *val * self.size_inv); }domain.fft(coeffs)与domain.ifft(evals)就构成了一次完整的系数 ⇄ 点值往返往返测试roundtrip直接出现在模块的单测中。4. 并行加速策略 ⚡开启stdfeature 后best_fft会按输入规模自适应选择执行路径条件策略n 4096纯串行serial_fftn ≥ 4096 且块数 ≥ 4par_chunks_mut块级并行rayon块数不足 4 但 n ≥ 4096 且线程 ≥ 4parallel_butterfly_chunk在块内部按线程切分并行其余串行蝶形并行蝶形的巧思把每块按线程数再细分为每个子区间预先算好单位根种子w_m的幂各线程从自己的种子起步独立推进避免了加锁和归约——因为蝶形运算中同一块内不同位置的元素互不干扰。单元测试parallel_fft_matches_serial_fft_for_large_domain显式验证了 3/4/9 线程下并行结果与串行结果逐位相等这在高并发数值代码里是很关键的保证。四、Coset FFT商多项式的关键技巧 PLONK 中商多项式 q(·) 的度数会超过主域需要在8n 大小的域上求值。但直接扩大域代价高标准技巧是余弦集coset变换coset_fft先给系数逐位乘上G, G², G³, …G 为域乘性生成元即在余弦集上平移求值的预乘步骤再做普通 FFTcoset_ifft先做 IFFT再逐位乘上G⁻¹, (G⁻¹)², …把平移约掉coset_fft fft( coeffs · [G^i] ) coset_ifft ifft( evals ) · [G^(-i)]效果用 n 点 FFT 就能求出多项式在偏移后网格 8n 个位置上的值。quotient_domain.coset_fft / coset_ifft被大量用于商多项式的构造与还原见 src/proof_system/quotient_poly.rs。余弦集还配套了两个校验器matches_linear_poly_over_coset与matches_vanishing_poly_over_coset用于验证特定多项式的求值序列符合闭式解——这是防降级验证opening verification的重要组成。五、Polynomial 与 Evaluations两种表示的自由切换FFT 模块最优雅的设计是把表示形式抽象成两个结构体1.Polynomial系数形式—— src/fft/polynomial.rsstruct Polynomial { coeffs: VecBlsScalar } // coeffs[i] x^i 的系数from_coefficients_vec自动裁剪高位零系数evaluate(self, value)Horner 幂次法在任意点求值用于验证实现了Add / Sub / Mul等标准代数运算2.Evaluations点值形式—— src/fft/evaluations.rsstruct Evaluations { evals: VecBlsScalar, domain: EvaluationDomain, // 关键域信息内嵌 }域内嵌是亮点设计加法/乘法/除法逐点执行天然 O(n)实现里assert_eq!(self.domain, other.domain)直接拒绝跨域运算杜绝隐式错误interpolate()一行调用domain.ifft_in_place完成插值还原无需外部传参序列化to_var_bytes / from_slice会把域一并写入反序列化时重建标准域做一致性校验恶意构造的字节无法注入非法域参数3. 转换路径一览系数 [a₀, a₁, …] ── domain.fft ──────────▶ 点值 [p(1), p(ω), p(ω²), …] ◀── domain.ifft插值──┘在 src/compiler/prover.rs 的预处理阶段可以看到真实用法EvaluationDomain::new(constraints)依据约束数建主域EvaluationDomain::new(quotient_size)另建 8 倍域给商多项式对置换多项式s_sigma_1..4逐一domain.fft转入点值形式供后续逐点约束求值使用六、小结这套 FFT 设计的三个精髓 ✨设计点价值2^n 单位根子群 预计算域参数FFT 各阶段无需重复取幂/求逆纯查表式推进自适应并行4096 点阈值 线程数判断小电路零并行开销大电路2^16 约束约 7.9s 证明吃满多核余弦集 FFT 域内嵌的 Evaluations商多项式 8n 域高效求值类型系统层面杜绝跨域运算与恶意序列化对新手而言建议的阅读路线是先看 src/fft/domain.rs 中serial_fft和butterfly_range两个函数合计不到 30 行完整呈现 DIT-FFT再顺着best_fft理解并行调度最后到quotient_poly.rs看余弦集变换在证明流程中的落点。掌握这条主线你就读懂了 dusk-plonk 性能优化的发动机舱。 项目更多设计细节可参考规格文档 docs/dusk-plonk-specs.pdf基准测试可用cargo bench见 benches/plonk.rs。【免费下载链接】plonkPure Rust implementation of the PLONK ZKProof System done by the Dusk team项目地址: https://gitcode.com/gh_mirrors/plo/plonk创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考