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

</aside>

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

</aside>

# Multi-scalar Multiplication (MSM)

## Goal

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.

</aside>

## Montgomery Multiplication