Load-Balanced Parallel Implementation on GPUs for Multi-Scalar Multiplication Algorithm

Yutian Chen, Cong Peng, Yu Dai, Min Luo, Debiao HeIACR 2024 · DOI

TL;DR

This paper introduces a highly optimized, load-balanced GPU implementation for Multi-Scalar Multiplication (MSM), the primary computational bottleneck in zero-knowledge proof systems like Groth16 and PLONK. By rethinking scalar mapping to reduce bucket counts and implementing a novel parallel accumulation strategy, the authors achieve up to a 2x speedup over the previous state-of-the-art implementation (cuZK) on high-end NVIDIA GPUs.

What Problem Does This Paper Address?

In the world of cryptography, Zero-Knowledge Succinct Non-interactive ARguments of Knowledge (zk-SNARKs) are essential for privacy-preserving technologies. However, generating these proofs is computationally expensive. The "heavy lifter" in this process is Multi-Scalar Multiplication (MSM)—calculating the sum of points on an elliptic curve, each multiplied by a different scalar.

While GPUs are naturally suited for this kind of parallel work, existing implementations often suffer from load imbalance. In the standard "Pippenger algorithm" used for MSM, points are sorted into "buckets." If some buckets receive many more points than others, certain GPU threads work overtime while others sit idle, leading to significant performance waste. Furthermore, the final "aggregation" of these buckets is often performed serially, creating a secondary bottleneck.

Methods

The authors propose several key innovations to the Pippenger algorithm framework:

  • Novel Scalar Mapping: They introduce a method to map scalars into bucket indices that reduces the total number of buckets to just 1/4 of the original Pippenger algorithm. This is achieved by recoding scalars into a "float-like" representation (an odd number, an exponent, and a sign bit).
  • Load-Balanced Accumulation: Instead of assigning a fixed range of buckets to each thread, they use a compact static buffer and a "binary sieving" technique. This ensures that work is distributed evenly across all available GPU threads, regardless of how "hot" or "cold" specific buckets are.
  • Coordinate System Optimization: The paper utilizes Cached Jacobian coordinates for typical memory scenarios but switches to Homogeneous coordinates when GPU memory is abundant. The latter saves one finite field multiplication for every two points added, providing a ~5% speed boost.
  • Parallel Layered Reduction: They replace the traditionally serial bucket aggregation phase with a parallel layered reduction algorithm. This moves the time complexity of this phase from linear to logarithmic relative to the number of buckets.

Datasets

As a cryptography research paper, the "datasets" consist of standard elliptic curves and varying scales of point/scalar sets:

  • Curves: BLS12-381 (the industry standard for Ethereum and Zcash), BLS24-315, and BLS12-377.
  • Scales: Performance was evaluated on MSM sizes ranging from $2^{19}$ to $2^{24}$ points.
  • Hardware Benchmarks: Testing was conducted on NVIDIA V100-SXM2 (32GB), RTX 3090, and RTX 4090 GPUs.

Key Insights and Ideas

  • The "Aha" of Scalar Recoding: By transforming scalars into a signed-digit representation and then into a "float" format, the authors realized they could drastically shrink the bucket search space without increasing the cost of the initial radix sort.
  • Static vs. Dynamic Buffers: To avoid the overhead of dynamic memory allocation (which is slow on GPUs), the authors designed a compact static buffer strategy that prevents write conflicts between threads while maintaining a nearly linear speedup ratio as thread counts increase.
  • Memory-Speed Trade-off: The insight that homogeneous coordinates—while memory-intensive—can reduce the total multiplication count per point addition allows the algorithm to "auto-scale" its performance based on the available VRAM of the user's hardware.

Key Results

The proposed implementation significantly outperforms cuZK, the previous benchmark for GPU-based MSM:

  • V100 Performance: Achieved speedups of 1.998x, 1.821x, and 1.818x compared to cuZK at scales of $2^{21}$, $2^{22}$, and $2^{23}$ points, respectively.
  • RTX 4090 Performance: On the BLS24-315 curve, the implementation processed $2^{23}$ points in just 90.35ms.
  • Scalability: The speedup ratio showed almost linear growth as the number of device threads increased, proving the effectiveness of the load-balancing strategy.

Limitations and Future Work

  • Constant-Time Execution: The basic version of the algorithm is not "constant-time," meaning its execution time varies based on the input scalars. While this is acceptable for many "Prover" scenarios, it could be a side-channel risk in others. The authors propose a constant-time variant in Section 5, though it comes with a slight performance penalty.
  • Memory Footprint: The highest-performance mode (using homogeneous coordinates) requires substantial GPU memory (e.g., ~12GB for $2^{23}$ points). This might limit its use on older or lower-end consumer hardware.
  • Future Directions: The authors suggest integrating more advanced modular multiplication techniques (like those proposed by Longa) and exploring even faster radix sort algorithms (like "Onesweep") to further shave milliseconds off the proof generation time.

Summary updated

Abstract

Multi-scalar multiplication (MSM) is an important building block in most of elliptic-curve-based zero-knowledge proof systems, such as Groth16 and PLONK. Recently, Lu et al. proposed cuZK, a new parallel MSM algorithm on GPUs. In this paper, we revisit this scheme and present a new GPU-based implementation to further improve the performance of MSM algorithm. First, we propose a novel method for mapping scalars into Pippenger’s bucket indices, largely reducing the number of buckets compared to the original Pippenger algorithm. Second, in the case that memory is sufficient, we develop a new efficient algorithm based on homogeneous coordinates in the bucket accumulation phase. Moreover, our accumulation phase is load-balanced, which means the parallel speedup ratio is almost linear growth as the number of device threads increases. Finally, we also propose a parallel layered reduction algorithm for the bucket aggregation phase, whose time complexity remains at the logarithmic level of the number of buckets. The implementation results over the BLS12-381 curve on the V100 graphics card show that our proposed algorithm achieves up to 1.998x, 1.821x and 1.818x speedup compared to cuZK at scales of 221, 222, and 223, respectively.
BibTeX
@inproceedings{chen2024load,
  author = {Yutian Chen and Cong Peng and Yu Dai and Min Luo and Debiao He},
  title = {{Load-Balanced Parallel Implementation on GPUs for Multi-Scalar Multiplication Algorithm}},
  booktitle = {IACR},
  year = {2024},
  doi = {10.46586/tches.v2024.i2.522-544},
}
Figure