# Pippenger  Algorithm

Pipenger Algorithm or Bucket Method is an algorithm to compute MSM efficiently.

The **multi-scalar multiplication (MSM)** problem is: Given $$n$$ elliptic curve points $$G\_i$$ and $$n$$ scalars $$s\_i$$, compute:

$$
S = \sum\_{i=0}^{n} s\_iG\_i,
$$

where $$s\_iG\_i$$ denotes [scalar multiplication](https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication).

### Description

Let’s first partition each scalar into $$m$$ windows each has $$c$$ bits, then:

$$
s\_i = s\_{i,0} + s\_{i,1}2^c + ... + s\_{i,m-1}2^{c(m-1)}
$$

You can think of each scalar $$s\_i$$ as a big number so this is just a representation of it as a multi-precision integer with a limb size equal to $$c$$.

Then we have:

$$
S = \sum\_{i=0}^{n}s\_iG\_i = \sum\_{i=0}^{n}\sum\_{j=0}^{m-1}s\_{i,j}2^{jc}G\_i
$$

By reordering the sums and denoting $$W\_j = \sum\_{i=0}^{n}s\_{i,j}G\_i$$, we get:

$$
S = \sum\_{i=0}^ns\_iG\_i=\sum\_{j=0}^{m-1}2^{jc}\sum\_{i=0}^{n}s\_{i,j}G\_i=\sum\_{j=0}^{m-1}2^{jc}W\_j
$$

It means we can calculate the MSM for each window $$W\_j$$ first, and then aggregate the results.

Because each window has $$c$$ bits, $$s\_{i,j}$$ has a value in range $$\[0, 2^{c−1} ]$$. Therefore, we can put $$n$$ points into $$2^c$$ buckets according to the value of $$s\_{i, j}$$. Using this fact we can compute $$W\_j$$ in the following way:

1. for each bucket $$t \in {0, 2^c - 1}$$: calculate the sum of points in this bucket to get $$B\_t$$
2. for each $$j$$ compute $$W\_j$$: $$W\_j = \sum\_{t=0}^{2^{c}-1}tB\_t$$

For example, if $$c = 3$$ and $$n = 15$$, then we have 15 points and 8 buckets, such that:

$$
W\_j = 4G\_1 + 3G\_2 + 5G\_3 + 1G\_4 + 4G\_5 + 6G\_7 + 6G\_8 + 3G\_{14} + 5G\_{15} = \ =1G\_4 + 3(G\_2+G\_{14}) + 4(G\_1 + G\_5) + 5(G\_3 + G\_{15}) + 6(G\_7 + G\_8) = \ = 1B\_1 + 3B\_3 + 4B\_4 + 5B\_5 + 6B\_6
$$

### Algorithm

Here:&#x20;

* $$n$$ - number of terms
* $$c$$ - size of window in bits
* $$m$$ - number of windows

1. Init windows $$W\_j$$, $$j \in {0..m}$$ with additive identities
2. For each $$j$$ in $$0..m$$:
   1. Init buckets $$B\_t$$, $$t \in {0..2^c-1}$$with additive identities
   2. For each $$i$$ in $$0..n$$:
      1. Compute $$s\_{i,j}$$:
         1. Shift $$s\_i$$ right on $$cj$$ bits
         2. Compute remainder modulo $$2^c$$
      2. Add $$G\_i$$ to a bucket $$B\_{s\_{i,j}}$$
   3. Compute partial sum: $$W\_j = \sum\_{t=0}^{2^{c}-1}tB\_t$$
3. Compute final sum: $$S =\sum\_{j=0}^{m-1}2^{jc}W\_j$$

**Sage example:**

```python
# BN254
Fq = GF("21888242871839275222246405745257275088696311157297823662689037894645226208583")
E = EllipticCurve(Fq,[0,3])

def pippenger(s, G, c):
    m = (256 // c) + 1
    n = len(s)
    zero = E(0)
    W = [zero for k in range(0, m)]
    for j in range(0, m):
        B = [zero for k in range(0, 2**c)]
        for i in range(0, n):
            s_i_j = s[i] >> c * j
            s_i_j = Integer(s_i_j) % (2**c)
            B[s_i_j] += G[i] 
        
        # the code below is the more optimal way to compute
        # for t in range(0, 2**c):
        #     W[j] += t * B[t]
        
        running_sum = E(0)
        for t in range(2**c - 1, 0, -1):
            running_sum += B[t]
            W[j] += running_sum
    
    # the code below is the same as
    # S = zero
    # p = 1
    # for j in range(0, m):
    #     S += p * W[j]
    #     p *= 2**c
    
    S = zero
    for j in range(m-1, -1, -1):
        for k in range(0, c):
            S = S + S
        S += W[j]
        
    return S
    
n = 2**9
c = 13
s = [Fq.random_element() for i in range(0, n)]
G = [E.random_element() for i in range(0, n)]
%time pippenger(s, G, c)
```
