This library is a GPU Implemetation of MSM for ZPrize Competition.
Following the ZPrize specification, this library is specifically designed for the fixed-base point MSM with 2^26 randomly sampled scalars from the BLS12-377 scalar field. Due to the deadline of the competition, GPU implemetations for MSM on other elliptic curves will be released later.
This GPU implemetation of MSM is developed by Tao Lu with the template from the reference provided by ZPrize.
Copyright (c) 2022 Tao Lu and contributors to the reference.
This library is licensed under the Apache License Version 2.0 and MIT licenses.
If there are any questions about this library, please contact Tao Lu: lutaocc2020@gmail.com
Here, we use a new faster parallel Pippenger-based MSM algorithm, which is equivalent to the one from our paper "cuZK: Accelerating Zero-Knowledge Proof with A Faster Parallel Multi-Scalar Multiplication Algorithm on GPUs". The full version of this paper can be downloaded here.
Details of our MSM implementation are described here (doc.md).
We evaluate our implementation on a dedicated instance of baseline image consisting of an AMD Epyc Milan CPU (8 cores), an A40 NVIDIA GPU with 48 GB of RAM.
Given input vectors consisting of 2^26 fixed elliptic curve points (bases), we compute a scalar multiplication of those bases with a set of four vectors of randomly sampled scalar elements from the associated BLS 12-377 G1 field in succession.
| Ours | Reference | Speedup |
|---|---|---|
| 3.38 s | 5.65 s | 1.67x |
Our GPU Implemetation of MSM relies on CUB, which provides state-of-the-art, reusable software components for every layer of the CUDA programming model.
By default, CUB is included in the CUDA Toolkit. If there is no CUB after installing the CUDA Toolkit, it is no need to build CUB separately. CUB is implemented as a C++ header library. To use CUB primitives in your code, simply:
- Download and unzip the latest CUB distribution
- #include the <cub/cub.cuh> header file in your CUDA C++ sources.
- Compile your program with NVIDIA's nvcc CUDA compiler, specifying a -I include-path flag to reference the location of the CUB header library.
The CUDA sppark from Supranational has a Rust binding. To install the latest version of Rust, first install rustup. Once rustup is installed, install the Rust toolchain by invoking:
rustup install stable
After that, use cargo, the standard Rust build tool, to build the libraries:
git clone https://github.com/speakspeak/msm-gpu.git
cd msm-gpu
cargo build --release
To run a test of an MSM of 2^26 random points and scalars on the BLS12-377 curve, run:
cargo test --release
To run the fixed-base point MSM (2^26 random points on BLS12-377) with four randomly selected test scalar vectors across ten trials in total, run:
cargo bench