MSM - Multi scalar multiplication

Problem: calculate ${\sum }_{i=0}^{n-1}{k}_i{P}_i$, where $k_i$ is a scalar and $P_i$ is point on an EC.

Scalar size: $b$ bits

Naive

Complexity: $N(b-1)$ squaring and $N(b-1)$ point additions

MSM can be divided into two main parts:

1. Modular multiplication
2. Point additions

Pippenger Bucketed Approach

Squaring: double add, i.e. $2\ast P$, where P is an EC point.

1. Divide scalar into windows of m, each with $w$ bits.
2. calculate: $P={\sum }_i{k}_i{P}_i={\sum }_j{2}^{cj}\left({\sum }_i{k}_{ij}{P}_i\right)={\sum }_j{2}^{cj}{B}_j$
3. $B_j={\sum }_i{k}_{ij}{P}_i={\sum }_{2^w-1}\lambda {\sum }_{u(\lambda )}{P}_u$
4. Example: c=3, j=15, $B_1=4P_1+3P_2+5P_3+1P_4+4P_5+6P_7+6P_8+\dots +3P_{14}+5P_{15}$
5. Now, group points with same coefficients together, i.e. create buckets of $2^c-1$, and $B_j={\sum }_{\lambda }\lambda S_{j\lambda }$
6. Take partial sums:

$$\begin{array}{rl}{T}_{j1}& =S_{j7}\\ T_{j2}& =S_{j6}+T_{j1}\\ T_{j3}& =T_{j2}+S_{j5}\\ & ⋮\\ T_{j7}& =T_{j6}+S_{j1}\end{array}$$

1. Sum each window.

Complexity: $\frac{b}{c}(2^c+N+1)$ additions +. $b$ squarings

• Part 1: window result calculation: $(2^c+N)b/c$
• Part 2: sum over all windows: each iteration require $1$ addition and $c$ squarings. $b/c$ windows → $\frac{b}{c}+\frac{b}{c}\ast c$ squarings

Point Addition Optimisations

Majority of complexity is due to point additions. Point addition complexity for affine coordinates is 1 division, 2 multiplications, 6 additions on $\mathbb{F}$. Division is very costly.

Use projective coordinates. Division can be deferred to when there is need for switch back to affine coordinates.

Complexity: 7 mults, 4 squarings, 9 additions, 3 mults by 2, 1 by 1. But no division is required.

Batch Affine

Can be used in cases where aim is to find: $G_i=P_i+Q_i$ where P, Q are points on EC.

Denote: $a_i=x_{i,2}-x_{i,1}$

• $s$: ${\prod }_{i=1}^n{a}_i$
• $l_i$: ${\prod }_{j=1}^{i-1}{a}_j$
• $r_i$: ${\prod }_{j=i+1}^n{a}_j$
• $G_i=\frac{1}{x_{i,2}-x_{i,1}}=s\ast l_i\ast r_i$

GLV with Endomorphism

Goal: accelerate single point scalar mult $k\ast P$

Naive Approach

1. Divide into windows of c bits
2. pre-compute $i\ast P\forall i\in [0,\dots ,2^c-1]$
3. compute $k_i$ for each window $i$
4. $d=b/c$
5. $R=0$
6. For i from d-1 to 0:
   1. $R=2^c\ast R$ (require c squaring)
   2. $R=R+(k_i\ast P)$ (require 1 point addition)
7. return $R$

Complexity: $2^c(precompute)+d$ point additions and $c\ast d=b$ squarings

Endomorphism

For some curves like BN254, we can use cube roots of unity to find new points on the curve for same y.

Equation of BN254: $y^2=x^3+b$.

So, $k\ast P$ can be divided into $k_1\ast P_1+k_2\ast P_2$, where

• $k=k_1+(s\ast k_2)$
• $P_2=s\ast P_1$

This reduces no of point doublings by half.

$k_1$ and $k_2$ are found using barret-reduction techniques.

Complexity: b/2 squaring and $d/2+2^{c+1}$ additions

WNAF (windowed Non-adjacent form)

Most of the time in MSM is spent in additions, and number of additions depend on hamming weight of the scalar. Less number of additions will have to be done if the number of 1’s in the scalar bits is less.

That’s exactly what NAF is used for in terms of MSM. Instead of representing number in bits 0, 1. It is represented in {-1, 0, 1}. This reduces the number of number of non-zero bits in the number by 1/3rd.

Also, when the b-bit scalars are divided into c-bit slices, value of each slice is used as bucket index. In total, we need $2^c-1$ buckets. Using NAF, we map $0,1,\dots ,2^c-1$ to $-2^{c-1},\dots ,-1,0,1,\dots ,2^{c-1}$. For example, for slice $s_i\in 1,2,3,4,5,6,7$ that needs $2^3-1=7$ buckets in total, if we map $s_i$ to $-4,-3,-2,-1,1,2,3$, only $2^{(}3-1)=4$ buckets are needed.

Pseudocode to find NAF:

Input: I = $(b_{n-1},b_{n-1},\dots ,b_0)$ Output O = $({\omega }_{n-1},{\omega }_{n-2},\dots ,{\omega }_0)$

i=0
while I > 0:
	if I is odd:
		w(i) = I mod 2^2
		I = I - w(i)
	else:
		w(i) = 0
	I = I/2
	i = i+1
return O

Let’s take a scalar $s$, with c-bit window size, $L=2^c$. Split scalar into K slices, where $K=ceil(b/c)$.

$$s=s_0+s_{1}L+\dots +s_{K-1}{L}^{K-1}=\sum _i{L}^i{K}_i$$

Now, to take advantage of wnaf, use following relation:

$$s_i{L}^i+s_{i+1}{L}^{i+1}=(s_i-L)L^i+(s_{i+1}+1)L^{i+1}$$

i.e. subtract $2^c$ from current slice and add 1 to next slice, whenever $s_i>=L/2$. After this, slice comes in range $[-L/2,L/2)$. To convert it into array form, whenever sign of $s_i$ is negative, subtract it from ith index in bucket array.

sequenceDiagram
Prover->>Verifier: Hello

Resources

• zkStudyClub: Multi-scalar multiplication
• Known optimisation for MSM
• Aztec’s wnaf
• Optimizing Multi-Scalar Multiplication (MSM): Learning from ZPRIZE
• EC arithmetic
• Hardware Review: GPUs , FPGAs and Zero Knowledge Proofs
• Optimisation of MSM
• Accelerating the PlonK zkSNARK Proving System using GPU Architectures
• FPGA Acceleration of Multi-Scalar Multiplication: CycloneMSM
• EdMSM: Multi-Scalar-Multiplication for SNARKs and Faster Montgomery multiplication
• cuZK: Accelerating Zero-Knowledge Proof with A Faster Parallel Multi-Scalar Multiplication Algorithm on GPUs
• PipeMSM: Hardware Acceleration for Multi-Scalar Multiplication
• DJB’s Pippenger logs