<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>
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.
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}$ .
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$.
<aside> 🚧 TODO: Fill out this section with my notes.
</aside>