# Batch Addition for Multi-Scalar Multiplication (MSM)

## 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}\\
x_R=k^2-x_P-x_Q\\
y_R=k(x_P-x_R)-y_P
$$

We observe that each addition requires an **inversion** operation that is way more expensive than muliplication and addition [2].

Therefore, we want to reduce the number of inversions needed to caculate $\{R_i\}$.

## Batch Addition
Consider n pair of points,
$$P_i = (x_{P_i}, y_{P_i}), Q_1 = (x_{Q_i}, y_{Q_i}), i \in \{1,...,n\}$$
We want to calculate $$R_i = P_i + Q_i = (x_{R_i}, y_{R_i})$$
Denote
$$ \lambda_i = x_{Q_i} − x_{P_i} $$
The product of all $\lambda$s left to $\lambda_i$ yields
$$ L_i = \prod_{j=1}^{i-1} \lambda_j$$
Then, the product of all $\lambda$s right to $\lambda_i$ is
$$ R_i = \prod_{j=i+1}^{n} \lambda_j $$
With the results above, we can calculate **inversion** as the following
$$\frac{1}{x_{Q_i} − x_{P_i}} = \frac{1}{\lambda_i} \\
= \frac{L_i R_i}{\prod_i \lambda_i} $$

Since $\prod_i \lambda_i$ does not change with $i$ and can be precomputed, the same inversion result can be shared across $$R_i = P_i + Q_i$$.

**Therefore, we reduced the number of inversions required to calculate $N$ additions from $N$ to $1$**.

## References
[1] https://crypto.stanford.edu/~dabo/cs255/lectures/ECC.pdf
[2] https://www.notion.so/Known-Optimizations-for-MSM-13042f29196544938d98e83a19934305#9d8b79321f584477ac945a738042c396
[3]https://hackmd.io/@tazAymRSQCGXTUKkbh1BAg/Sk27liTW9#Optimization-1-Batch-Affine-for-Point-Addition

###### tags: `msm` `zkp` `public`