MSM_blst

Credit: This is developed on top of a modified blst library. Check the original library at blst library.

Overview

The arithmetic of computing multiple scalar multiplications in an elliptic
curve group then adding them together is called multi-scalar multiplication (MSM).
MSM over fixed points dominates the time consumption in the pairing-based trusted
setup zero-knowledge succinct non-interactive argument of knowledge (zkSNARK),
thus for practical applications we would appreciate fast algorithms to compute it.
This paper proposes a bucket set construction that can be utilized in the context
of Pippenger’s bucket method to speed up MSM over fixed points with the help of
precomputation. If instantiating the proposed construction over BLS12-381 curve,
when computing n-scalar multiplications for n = 2e
(10 ≤ e ≤ 21), theoretical analysis
indicates that the proposed construction saves more than 21% computational cost
compared to Pippenger’s bucket method, and that it saves 2.6% to 9.6% computational
cost compared to the most popular variant of Pippenger’s bucket method. Finally, our
experimental result demonstrates the feasibility of accelerating the computation of
MSM over fixed points using large precomputation tables as well as the effectiveness
of our new construction.

Compilation

The code is tested on M1 Mac OS.

The implementation relies on SHA256 hash function in openssl library to generate the random scalars. Before running the subsequent code, one should first install openssl (For example, by running
brew install openssl), then modify openssl_include_directory and openssl_library_directory variables in makefile into the correct paths on your computer.

In the terminal under

MSM_blst

folder,
one directly runs

./run.sh group=1

or

./run.sh group=2

to build the modified blst library, complie and run the corresponding test in

\mathbb{G}_1

or

\mathbb{G}_2

respectively. The number of points $n$ is $2^{10}$ by default. Check the next part for setting configuration.

Note MSM_blst is not compatible with the original blst library since some of the source code in blst has been modified.

Bash script parameters:

group: Compile the corresponding group over in $\mathbb{G}_1$ or $\mathbb{G}_2$ respectively.

config: Select a list of config files to be included in the algorithm.

Examples:

The following command

./run.sh group=1 config=10,11,12 

execute the test for $n$-scalar multiplications in $\mathbb{G}_1$, and it will run through $n = 2^{10}, 2^{11}, 2^{12}$ sequentially.

The following command

./run.sh group=2 config=15,17

execute the test for $n$-scalar multiplications in $\mathbb{G}_2$, and it will run through $n = 2^{15}, 2^{17}$ sequentially.

We have config=10 by defualt.

Expected output

main_p1.cpp and main_p2.cpp have 4 methods to compute $n$-scalar multiplications. They are
1. Our Construction (CHES 'nh+ 0.21*q'),
2. Our Construction with integral scalar conversion,
3. Pippenger Variant (pippenger_variant_BGMW95),
4. Pippenger (pippenger_blst_built_in).

In

main_p1.cpp

and

main_p2.cpp

there is a

/***----***
Configuration
***----***/

snippet. One can decide whether to run the test for a specific algorithm by assigning bool values to
TEST_PIPPENGER_Q_OVER_5_CHES
and
TEST_PIPPENGER_BGMW95.