# 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