Rethinking Acceleration in Bulletproofs: Structural Limits of Polynomial Optimization

Kaiyu Liu

doi:10.47297/wspeiWSP2516-253521.20261002

PDF
Export
Share
Collection
Album

Rethinking Acceleration in Bulletproofs: Structural Limits of Polynomial Optimization

Volume 10, Issue 2

Views: 0 Downloads: 0

Rethinking Acceleration in Bulletproofs: Structural Limits of Polynomial Optimization
Rethinking Acceleration in Bulletproofs: Structural Limits of Polynomial Optimization
College of Information Science and Technology, Beijing University of Chemical Technology, Beijing, 102200, China
Vol. 10, Issue 2, Pages: 94-104(2026)
Published：30 April 2026
DOI：10.47297/wspeiWSP2516-253521.20261002
Accepted：

Scan QR Code

Liu Kaiyu.Rethinking Acceleration in Bulletproofs: Structural Limits of Polynomial Optimization[J].Entrepreneurship and Innovation,2026,10(02):94-104.
DOI：

Liu Kaiyu.Rethinking Acceleration in Bulletproofs: Structural Limits of Polynomial Optimization[J].Entrepreneurship and Innovation,2026,10(02):94-104. DOI： 10.47297/wspeiWSP2516-253521.20261002.

摘要

Abstract

Bulletproofs is a widely used zero-knowledge range proof system with logarithmic proof size and no trusted setup

but its proving phase remains computationally expensive. This work demonstrates that NTT-based polynomial acceleration is ineffective for Bulletproofs due to fundamental structural mismatch. An NTT-integrated implementation is constructed and evaluated within the Bulletproof proving pipeline. Both theoretical analysis and empirical results show that NTT introduces additional overhead without improving performance. The dominant bottleneck is identified as multi-scalar multiplication (MSM) rather than polynomial computation. Further evaluation of MSM optimization strategies shows that simple analytical models fail to outperform existing heuristic implementations due to implementation-level constraints. Based on these observations

a unified analytical framework is proposed to explain optimization mismatch across protocols. The results demonstrate that effective optimization must align with the dominant computational structure of the protocol.

关键词

Keywords

references

Bünz B. , Bootle J. , Boneh D. , Poelstra A. , Wuille P. , & Maxwell G . ( 2018 ). Bulletproofs: Short proofs for confidential transactions and more . Proceedings of the IEEE Symposium on Security and Privacy , 315 – 334 .

Gabizon A. , Williamson Z. J. , & Ciobotaru O . ( 2019 ). Plonk: Permutations over Lagrange-bases for oecumenical noninteractive arguments of knowledge . IACR Cryptology ePrint Archive, Report 2019 / 953 .

Ben-Sasson E. , Bentov I. , Horesh Y. , & Riabzev M . ( 2018 ). Scalable, transparent, and post-quantum secure computational integrity . IACR Cryptology ePrint Archive, Report 2018 / 046 .

Bootle J. , Cerulli A. , Chaidos P. , Groth J. , & Petit C . ( 2016 ). Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting. In Advances in Cryptology – EUROCRYPT 2016 (pp . 327 – 357 ). Springer.

Möller B . ( 2001 ). Algorithms for multi-exponentiation. In Cryptographic Hardware and Embedded Systems – CHES 2001 (pp . 165 – 180 ). Springer.

Pippenger N . ( 1980 ). On the evaluation of powers and monomials . SIAM Journal on Computing , 9 ( 2 ), 230 – 250 .

Zhu X. , He H. , Yang Z. , et al . ( 2024 ). Elastic MSM: A fast, elastic and modular preprocessing technique for multi-scalar multiplication on GPUs . IACR Cryptology ePrint Archive, Report 2024 / 057 .

Samardzic N. , Langowski S. , Devadas S. , & Sanchez D . ( 2024 ). Accelerating zero-knowledge proofs through hardware–algorithm co-design . In Proceedings of the IEEE/ACM International Symposium on Microarchitecture (MICRO) .

Verma T. , Yuan Y. , Talati N. , & Austin T . ( 2025 ). ZKProphet: Understanding performance of zero-knowledge proofs on GPUs . IEEE International Symposium on Workload Characterization (IISWC) (to appear) .