ICICLE-Snark 是一种快速的 Groth16 证明实现,适用于零知识证明的应用。文章详细论述了 Groth16 的原理、工作流程,以及 ICICLE 如何通过优化算法和缓存技术提升性能,达成记录-breaking 的速度提升,从而为区块链应用提供更高效的解决方案。
作者 Emir Soytürk
ICICLE-snark 现在是最快的 Groth16 证明者实现,提供破纪录的性能,从而为 ZK 应用程序打开新可能性。本笔记包含基准测试、手册和其他信息。
零知识证明近年来迅速发展,Groth16 作为最广泛使用的证明系统之一,具有理想的区块链特性:
Groth16 的最大权衡是每个电路都需要一个可信设置。虽然这一缺点仍然广受欢迎,但这使得 Groth16 非常适合区块链应用及其他领域——一个证明可以证明复杂计算的正确性,而不揭示输入,任何人只需三次配对即可验证。
生成 Groth16 证明需要在大型素数域和椭圆曲线上进行密集的算术运算。在本博客的范围内,我们不会深入探讨 QAP 和 R1CS。我们可以将剩余的证明过程分为两个步骤:评估商和证明。正如我们所见,这两个步骤包含 3 次 IFFT、3 次 FFT 和 5 次 MSM。除了这些,还有元素级的乘法和减法。这两个主要原语(MSM 和 NTT)主导了证明过程。多标量乘法(MSM)和基于快速傅里叶变换的多项式评估(FFT/NTT)。这两个原语负责大多数执行时间。MSM 大约消耗 ~60% 的证明时间,FFT 约 ~30%。
证明者需要两个文件:见证文件和 zkey 文件。
目前有许多 Groth16 实现。最流行的包括:
ICICLE 是一个前沿的加密库,旨在加速高级算法和协议——首先是 ZKP——以适应多种计算后端,包括 GPUs、CPUs、Metal 等。它支持 C++、Rust 和 Go 等多种前端,允许在不同的开发环境中无缝集成。通过一个代码库,你可以利用三种流行语言,并在多种硬件平台上运行。
我们首先通过仅集成 MSM 和 NTT 来接近这个问题。然而,由于数据传输和数据转换,我们未能达到想要的性能。作为解决方案,我们决定用 ICICLE 从零开始构建一个 Groth16 证明者。参考代码是 snarkjs 代码库,由 iden3 团队构建。这使我们能够构建一个优化的证明者,可以与现有的 zkey 文件一起工作。因此,任何人都可以轻松地从 snarkjs 或 rapidsnark 切换到 ICICLE-snark。在“Groth16 的工作原理”部分中解释的原语已经在 ICICLE 库中实现并进行了良好优化。
现有工具的另一个问题是它们被设计为命令行界面(CLI)使用。这意味着如果你多次使用这些工具证明相同的电路,那么有许多值可以缓存和重用,如证明密钥、基数和 NTT 域。为了利用这个缓存技巧,我们将证明者开发为后台工作程序和 Rust 库。
将任何代码移至 GPU 的最大问题之一是数据传输和转换。要能够使用 ICICLE 并利用 CUDA,你需要将数据转换为 ICICLE 类型并移动到设备。在大多数情况下,为 CUDA 内核准备数据的时间将比执行内核本身花费更多时间。
数据转换可能需要过长的时间,因为需要调用 from
函数 2^n 次。在大多数情况下,直接使用 Rust 中的 transmute
调用改变量的内存是可行的且更好。这允许开发人员在确保安全的情况下更改现有内存的类型。实际上,这几乎可以达到 100% 的性能提升,因为 transmute
调用仅需 20-30 ns,而同样的转换在初步方法中需要 100ms。
数据传输速度受硬件限制。因此,避免数据传输至关重要。如果有可能的话,这是我们从头构建 Groth16 的最初动机,而不是简单地替换现有实现中的 MSM 和 NTT 调用。
MSM 和 NTT 是许多证明系统(如 Groth16、Hyrax、Plonk 和 Libra)中使用的密码学原语。ICICLE 提供了对多个后端(CPU、CUDA、Metal 等)的快速实现。用 ICICLE MSM 替换 5 个 MSM,平均提高了 63 倍(大小=2²²),用 ICICLE FFT API 替换 3 个 IFFT 和 3 个 FFT 也平均提高了 320 倍(大小=2²²)。
在许多地方,我们需要逐元素相乘和相减两个向量。这些任务在 GPU 上可以高度并行化。在 ICICLE 中调用 VecOps API 而不是使用 CPU 处理长数组,平均提升了 200 倍(大小 2²²)。
在许多应用程序中(如证明服务或 L2 回滚),你将在多个证明中重用相同的电路和证明密钥。ICICLE 通过将数据保留在设备内存并缓存计算来利用这一点。为了利用这一点,我们引入了 CacheManager。它首先计算依赖于 zkey 文件的值,并通过映射与 zkey 文件保存。如果它以前已计算过,则代码将重复使用而不再计算。
缓存改进
我们在两种不同的配置上进行了基准测试:
我们使用 MoPro 的基准测试 repository 中的电路来比较证明系统。
如前所述,在生产中,项目更有可能证明相同的电路。为此,我们使用缓存系统。然而,我们比较的其他工具是 CLI,因此它们在一次证明后终止。为了保持公平,我们提供了带有缓存和不带缓存的基准测试。
你现在可以开始将 ICICLE-snark 集成到你的代码库中。根据你的代码库,你有两个选择。
如果你的代码库是用 Rust 编写的,那么最佳实践是将证明者作为 Rust Crate 使用。你只需通过调用 cargo add ICICLE-snark
将其添加到依赖项。之后,你可以导入证明功能并创建一个 CacheManager 实例,然后通过提供见证和 zkey 文件的路径开始证明。
use icicle_snark::{groth16_prove, CacheManager};
fn main() {
let mut cache_manager = CacheManager::default();
let witness = "witness.wtns";
let zkey = "circuit_final.zkey";
let proof = "proof.json";
let public = "public.json";
let device = "CUDA"; //如果需要,替换为 CPU 或 METAL
groth16_prove(
&witness,
&zkey,
&proof,
&public,
device,
&mut cache_manager
).unwrap();
}
如果你的代码库是用不同的编程语言编写的,你仍然可以使用 ICICLE 证明者。在这种方式下,你需要获取代码库并在 worker
模式下运行,然后在任何代码库中与其通信。我们在 ICICLE-snark/examples 目录下分享了如何做到这一点的示例。
我们在这里支持使用 ICICLE 的创新项目。如果你有独特的想法,让我们一起 探索资助的可能性 来加速你的工作。
选择任何研究论文,识别一个有报告基准的算法,并使用 ICICLE 重新实施它。你对原始实现的改进越多,你获得的资助就越大。
Twitter / X: https://twitter.com/Ingo_zk
YouTube: https://www.youtube.com/@ingo_zk
GitHub: https://github.com/ingonyama-zk
LinkedIn: https://www.linkedin.com/company/ingonyama
加入我们: https://www.ingonyama.com/career
Snark Chocolate: Spotify / Apple Podcasts
- 原文链接: medium.com/@ingonyama/ic...
- 登链社区 AI 助手,为大家转译优秀英文文章,如有翻译不通的地方,还请包涵~
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!