# Pippenger Algorithm for Multi-Scalar Multiplication (MSM)

## Problem
Give $n$ scalars ${k_i}$ and $n$ EC points ${P_i}$, calculate $P$ such that
$$P=\sum_{i=0}^n k_i P_i$$

## The Pippenger / Bucket Algorithm
### Step 1: partition scalars into windows
Let's first partition each scalar into $m$ windows each has $w$ bits, then
$$k_i = k_{i,0} + k_{i,1} 2^{w} + ... + k_{i,(m-1)} 2^{(m-1)w}$$

You can think each scalar $k_i$ as a bignum and representing it as a multi-precision integer with limb size $w$.

Then we have,
$$\sum_i k_i P_i
= \sum_i \sum_{j=0}^{m-1} k_{i,j} 2^{jw} P_i$$

By reordering the sums, we get
$$ \sum_i k_i P_i
= \sum_j 2^{jw} \left( \sum_i k_{i,j} P_i \right) \\
= \sum_j 2^{jw} W_j$$

It means we can calculte the MSM for each window $W_j$ first, then aggregate the results via $\sum_{j=0}^{m-1} 2^{jw} W_j$

Then, let's examine $W_j = \sum_{i=0}^n k_{i,j} P_i$

### Step 2: for each window, add points by bucket
Because each window has $w$ bits, $k_{i,j}$ has a value range of $[0, 2^w-1]$. Therefore, we can put $n$ points into $2^w$ buckets according to the value of $k_{i,j}$. We can first calculate $W_j$ by,
1. for bucket $t$, $t \in \{0, 2^w-1\}$, calculate the sum of points in this bucket and get $B_t$
2. $W_j = \sum_{t=0}^{2^w-1} t B_t$

For example, if $w=3$ and $n=15$, then we have $15$ points, $8$ buckets, such that
$$W_j = 4 P_1 + 3 P_2 + 5 P_3 + 1 P_4 + 4 P_5 + 6 P_7 + 6 P_8 + 3 P_{14} + 5 P_{15} \\
= 1 P_4 + 3 (P_2+P_{14}) + 4 (P_1+P_5) + 5(P_3+P_{15}) + 6 (P_7 + P_8) \\
= 1 B_1 + 3 B_3 + 4 B_4 + 5 B_5 + 6 B_6 $$

Therefore,
$$ W_j = \sum_{t=0}^{2^w-1} t B_t $$

### Step 3: reduce window results

$$P=\sum_{i=0}^n k_i P_i \\
= \sum_j 2^{jw} W_j $$

## Reference
https://www.notamonadtutorial.com/multiscalar-multiplication-strategies-and-challenges/

###### tags: `msm` `zkp` `public`