Multi-Scalar Multiplication

• Bucket method

The Multi-Scalar Multiplication(MSM) problem involves calculating the sum of multiple elliptic curve points, represented ad:
$$P=\sum _{i=1}^n{k}_i{G}_i$$ Here, $k_i$ are scalars(integers modulo a prime), $G_i=(x_i,y_i)$ are elliptic curve points. $k_i{G}_i$ indicates that $G_i$ is added to itself $k_i$ times.
Given that about 75% of the time spent producing a zk-SNARK proof is dedicated to $MSM$, optimizing this operation is essential for enhancing overall performance.

Bucket method

We can break down the Multi-Scalar Multiplication problem into smaller sums and reduce the number of operations by applying the windowing technique. Before we compute $k_i{G}_i$,it's important to note that each scalar $k_i$ can be represented in binary. This representation allows us to express $k_i{G}_i$ in a more efficient manner.

For each $k_i$, we can segment its binary representation into windows of size $c$:
$$k_i=k_{i,0}+k_{i,1}{2}^c+k_{i,2}{2}^{2c}+\cdots +k_{i,m-1}{2}^{c(m-1)}.$$ Using this approach, we can express the scalar multiplication $k_i{G}_i$ as:
$$k_i{G}_i=k_{i,0}{G}_i+k_{i,1}{G}_i+k_{i,2}{G}_i+\cdots +k_{i,m-1}{2}^{c(m-1)}{G}_i.$$
This allows us to rewrite the MSM problem as:
$$P=\sum _{i=1}^n{k}_i{G}_i=\sum _{i=1}^n\sum _{j=0}^{m-1}{k}_{i,j}{2}^{cj}{G}_i$$
By changing the order of summation, we have:
$$P=\sum _{j=0}^{m-1}{2}^{cj}(\sum _{i=1}^n{k}_{i,j}{G}_i)$$

weher we first break the scalars into windows and then aggregate the points in each window. Now we can focus on efficiently calculating each $B_j:$
$$B_j=\sum _{i=1}^n{k}_{i,j}{G}_i=\sum _{\lambda =0}^{2^c-1}\lambda \sum _{u(\lambda )}{G}_u$$
with the inner summation over $u(\lambda )$ considering only points with the coefficient $\lambda$. This leads us to organize points into the corresponding lambda buckets（if $c=3$):
$$B_j=\sum _{\lambda =1}^{2^c-1}\lambda S_{j,\lambda }=S_{j,1}+2S_{j,2}+3S_{j,3}+4S_{j,4}+5S_{j,5}+6S_{j,6}+7S_{j,7}.$$
We can compute this with minimal point additions using partial sums:
$T_{j,1}=S_{j,7},T_{j,2}=T_{j,1}+S_{j,6},T_{j,3}=T_{j,2}+S_{j,5},T_{j,4}=T_{j,3}+S_{j,4},T_{j,5}=T_{j,4}+S_{j,3},T_{j,6}=T_{j,5}+S_{j,2},T_{j,7}=T_{j,6}+S_{j,1}.$
Each of these operations involves just one elliptic point addition. We can obtain the final result by summing these partial sums:
$$B_j=\sum _k{T}_{j,k}.$$