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$.

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. NAF stands for Non-Adjcent Form. The classic definition of NAF is documented in Textbook Definition of Non-Adjacent Form (NAF). Intuition In bucket method, we slice each scalar $s$ into $c$-bit slices $s_i$, and use $s_i$ as bucket indexes. If we ignore bucket $0$ (since $0*P=0$), then we have $$s_i \in {1, ..., 2^c-1}$$ Therefore, we need $2^c - 1$ buckets in total.

The following algorithms and techniques are used by the top-2 performers of ZPrize 2022 MSM-WSAM track. Pippenger Algorithm / Bucket Method Batch Addition Signed Bucket Indexes GLV Decomposition Montgomery Multiplication 30-bit Limbs of Multi-Precision Integers (WASM Specific) For more information, checkout

GLV 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\

Algorithm 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.

Multiplication of two 32-bit integers in WASM is implemented by the i64.mul instruction. In particular, we represent each 32-bit integer as an i64 type integer and store the result as a i64 type integer. We cannot use i32.mul because it only stores the lower half of the 64-bit multiplication result in a i32 type value, unlike in x86 where the mul instruction can store both the upper half and the lower half 32-bit values in two registers respectively. The iterative Montgomery product algorithm: S[j] = 0 for j in 0 to n-1 for i in 0 to n-1 t = S[0] + x[i] * y[0] (_, t') = t (_, q[i]) = u[0] * t' (c, _) = t + q[i] * p[0]

Problem Given two sets of EC points ${P_i}$ and ${Q_i}$, $i \in {1,...,n}$, calculate ${R_i = P_i + Q_i}$ Native Approach If $P = (x_P, y_P)$, $Q = (x_Q, y_Q)$, and $R = P+Q = (x_R, y_R)$, an addition operation on an elliptic curve in short Weierstrass form $y^2 = x^3+ax+b$ is defined as below [1], $$ k = \begin{cases} \frac{y_Q - y_P}{x_Q - x_P} &\text{if } P\not=\pm Q \ \frac{3x_P^2+a}{2y_P} &\text{if }P=Q \end{cases}\

What is NAF The non-adjacent form (NAF) of a positive number is a unique signed-digit representation, in which non-zero values are non-adjacent [1]. For example [2], among the representations of $11$ below, the third representation in red is the only NAF form. \begin{matrix} (0 & 1 & 0 & 1 & 1) & \equiv & (8+2+1)=11 \ (0 & 1 & 1 & 0 & -1) & \equiv & (8+4-1)=11 \ (\color{red}{1} & \color{red}{0} & \color{red}{-1} & \color{red}{0} & \color{red}{-1}) & \equiv & (16-4-1)=11 \ (1 & -1 & 1 & 0 & -1) & \equiv & (16-8+4-1)=11 \ (1 & -1 & 0 & 1 & 1) & \equiv & (16-8+2+1)=11 \