MSM - Multi scalar multiplication

MSM stands for Multi scalar multiplication, its defined as:

$MSM(a,G)=\sum _{j=0}^{n-1}{a}_j{G}_j$

Where

$G_j \in G$ - points from an Elliptic Curve group.

$a_0, \ldots, a_n$ - Scalars

$MSM(a, G) \in G$ - a single EC (elliptic curve) point

In words, MSM is the sum of scalar and EC point multiplications. We can see from this definition that the core operations occurring are Modular Multiplication and Elliptic curve point addition. Its obvious that multiplication can be computed in parallel and then the products summed, making MSM inherently parallelizable.

Accelerating MSM is crucial to a ZK protocol's performance due to the large percent of run time they take when generating proofs.

You can learn more about how MSMs work from this video and from our resource list on Ingopedia.

Supported curves

MSM supports the following curves:

bls12-377, bls12-381, bn254, bw6-761, grumpkin

Supported Bindings

• Golang
• Rust

Supported algorithms

Our MSM implementation supports two algorithms Bucket accumulation and Large triangle accumulation.

Bucket accumulation

The Bucket Accumulation algorithm is a method of dividing the overall MSM task into smaller, more manageable sub-tasks. It involves partitioning scalars and their corresponding points into different "buckets" based on the scalar values.

Bucket Accumulation can be more parallel-friendly because it involves dividing the computation into smaller, independent tasks, distributing scalar-point pairs into buckets and summing points within each bucket. This division makes it well suited for parallel processing on GPUs.

When should I use Bucket accumulation?

In scenarios involving large MSM computations with many scalar-point pairs, the ability to parallelize operations makes Bucket Accumulation more efficient. The larger the MSM task, the more significant the potential gains from parallelization.

Large triangle accumulation

Large Triangle Accumulation is a method for optimizing MSM which focuses on reducing the number of point doublings in the computation. This algorithm is based on the observation that the number of point doublings can be minimized by structuring the computation in a specific manner.

When should I use Large triangle accumulation?

The Large Triangle Accumulation algorithm is more sequential in nature, as it builds upon each step sequentially (accumulating sums and then performing doubling). This structure can make it less suitable for parallelization but potentially more efficient for a large batch of smaller MSM computations.

MSM Modes

ICICLE MSM also supports two different modes Batch MSM and Single MSM

Batch MSM allows you to run many MSMs with a single API call, Single MSM will launch a single MSM computation.

Which mode should I use?

This decision is highly dependent on your use case and design. However, if your design allows for it, using batch mode can significantly improve efficiency. Batch processing allows you to perform multiple MSMs leveraging the parallel processing capabilities of GPUs.

Single MSM mode should be used when batching isn't possible or when you have to run a single MSM.