Multi-Scalar Multiplication (MSM) is a computationally intensive task that operates on elliptic curves based onGF(P). It is commonly used in zero-knowledge proof (ZKP), where it accounts for a significant portion of the computation time required for proof generation. In this article, we present PriorMSM, an efficient acceleration architecture for MSM. We propose a Priority-Based Scheduling Mechanism (PBSM) based on a multi-FIFO and multi-bank architecture to accelerate the implementation of MSM. By increasing the pairing success rate of internal points, PBSM reduces the number of bubbles in the pipeline of point addition (PADD), consequently improving the data throughput of the pipeline. We also introduce an advanced parallel bucket aggregation algorithm, leveraging PADD’s fully pipelined characteristics to significantly accelerate the implementation of bucket aggregation. We perform a sensitivity analysis on the crucial parameter of window size in MSM. The results indicate that the window size of the MSM significantly impacts its latency. Area-Time Product (ATP) metric is introduced to guide the selection of the optimal window size, balancing the performance and cost for practical applications of subsequent MSM implementations. PriorMSM is evaluated using the TSMC 28 nm process. It achieves a maximum speedup of 10.9× compared to the previous custom hardware implementations and a maximum speedup of 3.9× compared to the GPU implementations.

Changxu Liu

Hao Zhou

Patrick Dai

Li Shang

Fan Yang

ACM Transactions on Design Automation of Electronic Systems

TODAES 是电子系统设计和自动化领域的一流 ACM 期刊。它出版的创新工作记录了电子系统规范、设计、分析、模拟、测试和评估方面的重大研究和开发进展，强调计算机科学/工程方向。欢迎理论分析和实际解决方案。

ACM Transactions on Design Automation of Electronic Systems is a leading journal in the field of electronic system design and automation. It publishes innovative work that documents significant research and development advancements in the specification, design, analysis, simulation, testing, and evaluation of electronic systems, with an emphasis on the intersection of computer science and engineering. We welcome submissions of theoretical analyses and practical solutions.

《ACM Transactions on Design Automation of Electronic Systems》是电子系统设计与自动化领域的顶尖期刊。该期刊发表的创新研究涵盖了电子系统的规范、设计、分析、模拟、测试和评估等方面的重大进展，强调计算机科学与工程的交叉领域。我们欢迎理论分析和实际解决方案的投稿。

Category	Quartile
计算机科学	4
计算机科学, 计算机硬件	4
计算机科学, 计算机软件工程	4

PriorMSM: An Efficient Acceleration Architecture for Multi-Scalar Multiplication

ivySCI AI Smartly Parses PDF, Answers Researchers' Questions, and Helps You Understand Papers in Seconds

Journal Info

Category	Quartile
COMPUTER SCIENCE, SOFTWARE ENGINEERING	2