1个不稳定版本
| 0.3.0-alpha.1 | 2023年4月27日 |
|---|
#1227在密码学
50KB
967 行
ark-msm
ark-msm是一个将最先进的MSM优化集成到arkworks中的多标量乘法（MSM）模块。此实现有详细的文档，使开发者能够快速学习和实验最新的MSM优化技术。此外，代码设计为模块化，便于与其他库和项目集成。
请注意，当前实现仅用于研究和学习目的，尚未经过生产使用审计。请自行决定使用。
高达2倍的性能提升
下表比较了从2^8到2^18的输入大小下ark-msm和Arkworks 3.0（基线）的延迟。总体而言，ark-msm在基线上实现了高达2倍的速度提升。
| 输入大小（ms） | 2^8 | 2^9 | 2^10 | 2^11 | 2^12 | 2^13 | 2^14 | 2^15 | 2^16 | 2^17 | 2^18 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Arkworks 3.0 | 13.903 | 24.208 | 37.5 | 67.545 | 121.03 | 204.92 | 375.85 | 693.46 | 1268.6 | 2324.9 | 4391.9 |
| Arkmsm | 7.665 | 11.982 | 19.514 | 33.197 | 60.593 | 110.68 | 204.33 | 375.17 | 711.6 | 1372.1 | 2742.1 |
| 速度提升 | 1.81 | 2.02 | 1.92 | 2.03 | 2.00 | 1.85 | 1.84 | 1.85 | 1.78 | 1.69 | 1.60 |
在AMD EPYC 7282 16核处理器上测量的性能。
优化
在Arkworks中使用的Pippenger算法的基础上，使用了以下优化技术。
- 桶累积中的批量添加（批量累积）
- 桶减少中的批量添加（批量减少）
- 有符号桶索引（有符号索引）
- GLV分解（GLV）
每个优化都作为一个单独的提交实现，以便准确测量每个优化的影响。
下表展示了使用每种优化技术以及2^12输入大小所实现的性能提升的详细分解。
| 延迟（ms） | 改进 | |
|---|---|---|
| 基线 | 121.03 | |
| 批量累积 | 92.154 | 31.33% |
| 有符号索引 | 74.429 | 23.81% |
| 批量减少 | 65.023 | 14.47% |
| GLV | 60.593 | 7.31% |
| 总体 | 99.74% |
文档
有关每个优化的详细文档可在https://hackmd.io/@drouyang/msm找到
入门指南
-
安装Rust
curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh source $HOME/.cargo/env -
运行单元测试
cargo test -
运行基准测试
cargo bench -- bench_with_baseline cargo bench -- bench_window_size
致谢
ark-msm项目由MINA基金会的拨款资助。
我们的算法和实现基于Yrrid软件在C中编写的2022 zPrize提交。
我们感谢Gregor Mitscha-Baude（来自O(1) Labs）和Niall Emmart（来自Yrrid Software）慷慨地花时间回答我们的技术问题。
问题
关于技术问题，请联系 ouyang at snarikify.io
依赖项
~4MB
~83K SLoC