# Multiscalar Muforltiplication

The Multi-Scalar Multiplication (MSM) problem consists of, given an elliptic curve, calculating \[ \sum_{i=1}^{n} k_i P_i \] for some scalars \( k_i \), some elliptic curve points \( P_i = (x_i, y_i) \) and some \( n \) (For example, in the order of \( 2^{26} \)).

It is estimated that around 80% of the time to produce a zk-SNARK proof is spent doing MSM, so optimizing it is very important for performance.

## Bucketing method

We can break the MSM into smaller sums and reduce the total number of operations, by repeteadly using a method called the windowing technique. If we want to compute each \( k_iP_i \), we can break it into windows of size \( c \) \[ k_iP_i=k_{i0}P_i+k_{i1}2^{c} P_i+k_{i2}2^{2c} P_i+...+k_{i,m-1}2^{c(m-1)} P_i \] Using this, the MSM problem can be rewritten as \[P=\sum_{i} k_iP_i=\sum_{i}\sum_{j} k_{ij}2^{cj}P_i \] We can now change the order of the summations, \[ P=\sum_{i} k_iP_i=\sum_{j}2^{cj}\left(\sum_{i} k_{ij}P_i\right)=\sum_j 2^{cj} B_j \] In other words, we first divide the scalars into windows and then combine all the points in each window. Now we can focus on how to calculate each \( B_j \) efficiently: \[ B_j=\sum_{i} k_{ij}P_i=\sum_{\lambda=0}^{2^c-1} \lambda \sum_{u(\lambda)} P_u \] where the summation over \( u(\lambda) \) is done only over points whose coefficient is \( \lambda \). For example, if \( c=3 \) and we have \( 15 \) points, \[ B_1=4P_1+3P_2+5P_3+1P_4+4P_5+6P_7+6P_8+3P_{14}+5P_{15} \] We can split the summation by the coefficients \( \lambda \), taking values from \( 1 \) to \( 7 \). For \( \lambda=1 \), \( \sum_u P_u=P_4 \) (because \( P_4 \) is the only one with coefficient \( 1 \)), for \( \lambda=4 \), \( \sum_u P_u=P_1+P_5 \), etc. What we are doing is just placing all points with a common coefficient \( \lambda \) into the \( \lambda \)-bucket. Thus, \[ B_j=\sum_\lambda \lambda S_{j\lambda}=S_{j1}+2S_{j2}+3S_{j3}+4S_{4j}+5S_{5j}+6S_{j6}+7S_{j7} \] We can calculate this with a minimum number of point additions, using partial sums. \( T_{j1}=S_{j7} \) \( T_{j2}=T_{j1}+S_{j6} \) \( T_{j3}=T_{j2}+S_{j5} \) \( T_{j4}=T_{j3}+S_{j4} \) \( T_{j5}=T_{j4}+S_{j3} \) \( T_{j6}=T_{j5}+S_{j2} \) \( T_{j7}=T_{j6}+S_{j1} \) Each of these operations involves doing just one elliptic point addition. The final result can be obtained by summing these partial sums: \[ B_j=\sum T_{jk} \]

We can improve the calculations by changing the expansion of the coefficients \( k_i \). In binary representation, the Hamming weight is the number of non-zero bits; ideally, we would like this weight to be as small as possible to reduce the number of additions (For example, 65537, which is \( 2^{16}+1 \) is used as public key for the RSA cryptosystem in many implementations. The square and multiply algorithm requires only two multiplications). The average Hamming weight in a binary representation is \( 1/2 \); if we introduce a signed binary representation (\( -1,0,1 \)), the average weight is reduced to \( 1/3 \), with the consequent decrease in the number of operations (on average).