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

$$\begin{gathered} \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 \end{gathered}$$

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

$$\begin{gathered} W_j=4P_1+3P_2+5P_3+1P_4+4P_5+6P_7+6P_8+3P_{14}+5P_{15} \\ =1P_4+3(P_2+P_{14})+4(P_1+P_5)+5(P_3+P_{15})+6(P_7+P_8) \\ =1B_1+3B_3+4B_4+5B_5+6B_6 \end{gathered}$$

Therefore,

$$W_j=\sum _{t=0}^{2^w-1}t{B}_t$$

Step 3: reduce window results

$$\begin{gathered} P=\sum _{i=0}^n{k}_i{P}_i \\ =\sum _j{2}^{jw}{W}_j \end{gathered}$$

Reference

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

tags: msm zkp public