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

If we treat bucket indexes as signed integers, we are able to saves one bit in bucket index encoding, and therefore reduce number of buckets and bucket memory usage by half. The method is denoted as the signed-bucket-index method, and also known as NAF method. This method was reported in [1] and implemented by top-2 performers of the zPrize MSM-WASM track.

10/25/2023The following algorithms and techniques are used by the top-2 performers of ZPrize 2022 MSM-WSAM track.

10/25/2023GLV Decomposition is an efficient way to calculate point scaling $kP$. This method was originally published by Gallant, Lambert and Vanstone in 2001 [1], and was later integrated into the Bitcoin core code [2]. However, GLV Decomposition was not enabled in Bitcoin until a patent around the GLV method expired in 2020 [3]. A textbook introduction of enomorphisms of elliptic curves can be found in [4]. Problem Given scalar $k$ and EC point $P$, caculate $kP$. Property of Enomorphism Consider the elliptic curve over field $\mathbb{F}_p$ $$E: y^2 = x^3 + c\

3/29/2023Algorithm Consider prime field $\mathbb{F}_p$, select power of two $2^w$ such that $R=2^w > p$, we know that mod by R can be computed by bit shifting. Montgomery Form For $x \in \mathbb{F}_p$, define Montgomery form of $x$ as, $$\bar{x} = xR \pmod p$$ Transform To Montgomery Form Transforming $x$ to Montgomery form can be done by left-shift $x$ by $w$ and reduce modulo $p$. In practice, $x$ and $y$ are transformed to Montgomery form at the beginning of a computation, and transformed back at the end.

2/27/2023
Published on ** HackMD**

or

By clicking below, you agree to our terms of service.

Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet

Wallet
(
)

Connect another wallet
New to HackMD? Sign up