MSM

Multi-scalar multiplication (MSM) refers to calculating the following summation:

$$S = \sum_{i=1}^{n}k_iP_i$$

Or in other words, MSM calculates the sum of groups elements $P$ multiplied by scalars $k$, where $n$ is the total number of scalar $*$ element multiplications.

In terms of elliptic curve operations, we use MSM to calculate the sum of point-scalar multiplications. Since point addition operations are cheap based on the definition of elliptic curves, operation on points are best reduced to a series of additions (and/or doubles since they are also additions). The most naive reduction method for this purpose is "Double-and-add," though numerous additional approaches have been discovered to further reduce the total number of addition and double operations.

Here is a list of current optimizations done on MSM:

1. Pippenger's Algorithm (MSM optimization)

   1. Reduces number of additions and doubles in comparison to "Double-and-add"

2. Signed Bucket Index (optimization on Pippenger's or other naive bucket methods)

   1. Using NAF, the number of required buckets per window is reduced in half

3. Batch Inversion for Batch Additions (optimization for batch elliptic curve point additions)

   1. When calculating batches of point additions at once, batch inversion can be utilized to reduce the number of required field inverse operations to 1.

4. Montgomery Multiplication (optimization on field multiplications)

   1. Efficiently computes modular arithmetic using montgomery reduction

5. GLV Decomposition (optimization for point-scalar multiplication)

   1. GLV is often used to decompose MSM multiplications before running separate MSM's on the smaller parts. GLV generally reduces the total number of doubles operations needed; however, more significantly, if GLV is used before Signed Bucket Indexes, the number of buckets required is reduced to $\frac{1}{4}$ of the original number.

I also recommend reading section 1.1 of the paper Speeding Up Multi-Scalar Multiplication over Fixed Points Towards Efficient zkSNARKs. This section provides a very solid overview on lines of research for MSM optimization as of 2023.

Written by Ashley Jeong of A41