<aside> ✨ This page is originally based on the following HackMD, rewritten and expanded: https://hackmd.io/@tazAymRSQCGXTUKkbh1BAg/Sk27liTW9


<aside> 🗒️ This page represents operations in $\mathbb{G}$ using additive notation.


Multi-scalar Multiplication (MSM)


Let $(𝔾,+)$ be a abelian group of prime order $q$

Problem: Given $\vec{b}=g_0, ..., g_{N − 1} \in \mathbb{G}^n$ and $\vec{e}=e_0, ..., e_{N − 1} \in \mathbb{Z}^n_q$, compute:

$$ G = \sum_{i=0}^{N-1} [e_i]g_i $$

In fixed-base MSM, both $\vec{g}$ are assumed to be known ahead of time. In variable-base MSM, it is assumed that $\vec{g}$ is only made available at the time of computation.

Cost notation

In order to note operation costs, we use $\text{I, M, S, c, a}$ for field inversion, multiplication, squaring, addition, and multiplication by a constant respectively. In general, the cost of $\text{I ≫ M > S > c > a}$ .

Group Definition

Although some of the techniques described in this page are generic, most assume we are working over an elliptic curve defined over $\mathbb{Z}_p$ for odd prime-power $p$.

Curves we consider here may be represented in short Weierstrass form:

$$ y^2=x^3+ax+b $$

When referencing curve parameters $a$ and $b$, they are implicitly referring to the parameters in the curve’s short Weierstrass representation.

Note that for the pairings curves BN254 and BLS12-377, $a=0$.

Scalar Field Multiplication and Addition

<aside> 🚧 TODO: Fill out this section with my notes.


Montgomery Multiplication