FusionMSM：基于FPGA的无冲突算术优化多标量乘法加速器

摘要
零知识证明（ZKP）是一种有效的密码学原语，允许一方在不披露任何额外信息的情况下验证陈述的正确性。它在区块链交易和加密货币等应用中扮演核心角色。然而，ZKP实现中最耗时的任务是多标量乘法（MSM）。现有工作和评估标准主要强调速度提升，但忽略了面积开销的优化。本文设计了一款基于FPGA的加速器FusionMSM，旨在降低整体延迟并改善面积开销。

我们将MSM的瓶颈归因于三层金字塔结构：有限域运算、椭圆曲线点运算和调度。针对模运算，我们通过混合乘法策略和优化基于多比特LUT的模约减，提出了一种高效的非蒙哥马利模乘器。与ZKP加速工作中使用的模乘器相比，面积成本减少1.11倍，速度提升2.00倍。对于点运算，我们设计了一个统一的全流水点加单元，最高运行频率达500MHz，为已报道工作中的最高频率。在此基础上，我们提出贪心机制解决潜在冲突，减少点加单元的空闲周期并提升其利用率。

据我们所知，在2^18至2^26的输入规模下，FusionMSM相比其他基于FPGA和ASIC的工作实现了最佳性能。对于2^20规模，FusionMSM仅需Hardcaml方案12.4%的时间、FPGA上PipeMSM方案24.54%的时间，以及ASIC方案PipeZK36.41%的时间。同时资源利用率更低，URAM减少90.93%，FF减少35.24%，CARRY8减少47.59%。与基于GPU的实现相比，FusionMSM提供相当性能但功耗更低，仅为24.5W。