Rethinking Acceleration in Bulletproofs: Structural Limits of Polynomial Optimization

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.