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