一句话：提出多 GPU 专用 NTT 算法 UniNTT，通过无开销递归分解统一各层级优化，平均加速 4.26×。
零知识证明的证明生成耗时主要来自多标量乘法（MSM）和数论变换（NTT）。MSM 已借助多 GPU 系统高效加速，但 NTT 因置换式数据访问模式带来高昂的跨 GPU 通信开销，尚未获得同等支持。本文指出端到端证明生成亟需多 GPU NTT 支持，并提出 UniNTT——一种面向多 GPU 系统的 NTT 算法。其核心是无开销分解方法：递归地将一个 NTT 分解为更小的 NTT，使 warp、线程块、GPU 与多 GPU 各层级执行同一 NTT 计算的不同规模版本。基于抽象硬件模型，作者提出统一的 NTT 优化，再针对各层级定制应用，既简化优化过程，也表明通常仅适用于某一层级的优化可有效推广至其他层级。在 8-GPU 系统上，UniNTT 相比领先 NTT 实现平均加速 4.26×。
Zero-knowledge proofs validate statements without revealing any information, pivotal for applications such as verifiable outsourcing and digital currencies. However, their broad adoption is limited by the prolonged proof generation times, mainly due to two operations: Multi-Scalar Multiplication (MSM) and Number Theoretic Transform (NTT). While MSM has been efficiently accelerated using multi-GPU systems, NTT has not, due to the high inter-GPU communication overhead incurred by its permutation data access pattern. This paper identifies the necessity of multi-GPU NTT support for end-to-end proof generation. It introduces UniNTT, an NTT algorithm tailored for multi-GPU systems. The data access pattern of NTT incurs communication across all levels of the multi-GPU hierarchy (i.e., warp, thread block, GPU, and multi-GPU), complicating the implementation of multi-GPU NTT. To this end, UniNTT proposes a novel, overhead-free decomposition approach that recursively decomposes an NTT into smaller NTTs, enabling all hierarchy levels execute the same NTT computations at different scales. It promotes a uniform design of NTT optimizations based on an abstract hardware model, which are then tailored and applied to different levels of the hierarchy. UniNTT not only simplifies the optimization process but also shows that optimizations typically specific to one level can also be effectively generalized to others. Experiments show that UniNTT achieves an average 4.26× speedup compared to leading NTT implementations when both are executed on an 8-GPU system.
@inproceedings{JiZGY025,
title = {Accelerating Number Theoretic Transform with Multi-GPU Systems for Efficient Zero Knowledge Proof},
author = {Zhuoran Ji and Jianyu Zhao and Peimin Gao and Xiangkai Yin and Lei Ju},
booktitle = {ASPLOS},
year = {2025},
doi = {10.1145/3669940.3707241}
}