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.

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:

• $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:

# 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)