# MSM算法优化

Multi-Scalar Mul­ti­pli­cati­ton（MSM）是一个对群中元素的标量乘法求和的算法

若G为循环群，G_i∈G 为群中元素，现有一系数向量a=(a1,…an),ai∈Z,MSM 算法的目的是计算下列求和式

$\sum_{i=1}^{n} ai*Gi$。采用朴素的方法计算等式，即全部相乘然后求和，每个群平均1.5b次，b为群的阶的比特数

在 Groth16 算法中，MSM 算法用于 Prover 计算证明元素（系数向量*a* 为秘密输入），n 很大的时候开销也很大，Zcash 中的n* 大约为4×10⁴，Rollup 方案中为了确保可扩展性，*n* 也需要尽可能地大

当*n* 非常大的时候，MSM 算法占据了 Prover 计算开销中的很大一部分，而 Prover 开销又是 ZKP 协议开销的大头，所以优化 MSM 方案对于提高 ZKP 协议的计算开销非常有帮助

## 基于bucket的pippenger

bucket 的思想于 [2012/549](https://eprint.iacr.org/2012/549.pdf) 这篇论文中的第四节提出，主要思想是首先将一个*b* 比特的 MSM 拆分为若干个c* 比特的 MSM 并用类似于桶排序的思想分别处理这些小的 MSM，最后再合并回b* 比特的 MSM，步骤如下

①b比特的MSM拆分为c比特的MSM

首先将系数向量a*=(*a*1,…*an*) 的各个元素以二进制形式表示，之后选择*c*≤*b*，将二进制拆分成大小为c 的块，该步骤记为(*b*,*c*,*b*/*c)

举例：设a=1368 ，二进制表示为010101011000，将这 12 比特拆分成四组 3 比特并分别表示为十进制，也即拆分成010 101 011 000，每组用十进制表示就是(2,5,3,0)，因此将*a* 表示为a*=(2,5,3,0)。

②处理c比特的msm

仍按照上述例子进行，能够得到

然后构造2^c−1 个桶，根据G_i的系数分配到对应的桶里面，在上面的例子中，c=3，因此这里需要 7 个桶，注意，**这里只是将系数所对应的群元素放到桶里面**，**系数就是桶的index。**


之后我们记第i*个桶的求和为S_i,比如S1=G4+G9+G14，S7=G5+G12，计算这些桶需要的群操作次数为

然后求和所有的桶



## Signed Bucket Indexes for MSM

signed Bucket indexes also known as NAF method。This method was reported in [1] and implemented by top-2 performers of the [zPrize MSM-WASM track](https://www.zprize.io/blog/announcing-zprize-results).NAF stands for Non-Adjcent Form.

The classic definition of NAF is documented in [Textbook Definition of Non-Adjacent Form (NAF)](https://hackmd.io/HkVWGwsRTM2HeBL1VN0lAw).

思想如下：**引入符号位，将最高位作为符号位**

考虑引入负数的方式来优化，根据椭圆曲线的对称性，给定群元素G=(x,y)∈G，其对应的负元素 -G=(x,y)∈G

然后将系数集合{0，，，2^c-1} 修改为{-2^c-1，-1，1，2^c-1-1}，**把0跳过**，**减少了一半的桶的数量**。

此时群元素进桶的规则如下：

​ 如果系数a>0,则将元素G放入第a桶中

​ 如果系数a<0,则将元素G放入第|-a|桶中 情况如下


**对于桶减半之后的处理思想如下：**

## **Batch Addition for (MSM)**

**problem**：Given two sets of **EC points** {Pi}and {Qi}, i∈{1,...,n}∈{1,...,n}, calculate {Ri=Pi+Qi}

**Native Approach**：


易观察得出每一次加法都需要一次求逆的操作。

**cost of operation in field**：求逆 >> 乘法 > squaring >加法 >标量 * 元素

**Affine**：仿射坐标是一种表示椭圆曲线上点的方式，用两个有理数来表示一个点

在 BLS12-381 曲线上，一个 Affine 点可以被表示为 P = (x, y)

考虑以下点序列

$P_1 = (x_{1,1}, y_{1,1}), Q_1 = (x_{1, 2}, y_{1, 2}), ⋯, P_n = (x_{n, 1}, y_{n, 1}), Q_n = (x_{n, 2}, y_{n, 2})$

想要计算

$P_1 + Q_1, P_2 + Q_2, ⋯, P_n + Q_n$

**Denote**：$λ_i = x_{i, 2} − x_{i, 1}$,即Q的x坐标减去P的x坐标

①计算The product of all λ_j **left** to **λ_i**,$\forall i \in \{1,2, \cdots, n\}, \ d_i = \prod _{j=1}^{i-1}λ_j$

②计算The product of all λ_j **right** to **λ_i**,$\forall i \in \{1,2, \cdots, n\}, \ e_i = \prod _{j=1}^{i-1}λ_j$

然后计算逆元：

$\frac{1}{λ_i} = \frac{1}{x_{i,2}-x_{i,1}} =\frac{d_i*ei}{\prod _{λ_i}}$

由于$\prod _{λ_i}$ **不会改变**，所以可以提前计算，这样在整个过程中，可以把**求逆元的操作从n次降到1次**。

## GLV Decomposition for Multi-Scalar Multiplication (MSM)

**Problem:**Given **scalr k** and **EC point P**,calculate **kP**

**Property of Enomorphism**


> **On a particular elliptic curve, λ and β have to be known before GLV method can be applied, where λ and β are certain cube roots of 1 in their respective fields.**

**GLV Decomposition**


**Decomposition of Scalars**



## 整体梳理


### 参考
https://hackmd.io/@drouyang/msm
https://snowolf0620.xyz/index.php/zkp/1023.html
https://github.com/snarkify/arkmsm
https://www.youtube.com/watch?v=Bl5mQA7UL2I
**同样代码也是参考Arkmsm库，对于初学的我来说受益匪浅**
自己带注释的代码：[liujianwei12/Arkmsm-learn (github.com)](https://github.com/liujianwei12/Arkmsm-learn)

---

## MIT《Efficient Multi Exponentiation》by Jonathan

### Goal


### Reduction to Multi-Products

当e₀, . . . , e_N−1 ∈ {0, 1}时，我们把这种情况称为multi-product而不是multi-exponentiation.

第一步把群G的运算规约至许多multi-products的计算，步骤如下!

先只看ei项


这一步可以理解成是将$e_i$转化为2进制表示，其中$e_{i,l}$是第$l$位(从低位往高位数)的比特值

称 $e_{i,l}*2^l$ 为 $ e_i $的表示中的一项


这一步是将所有的 $e_{i,l}2^l$ 写成放到 $s*t$==($st=\lambda$)的矩阵中，然后重排求和顺序，如 $11=1*2^0+1*2^1+0*2^2+1*2^3$ ，我们将其项放到 $2*2$的矩阵中

然后逐列求和 $11=e_i=\sum_{j=0}^1\sum_{k=0}^1 2^{j+2*k}e_{i,j+2*k}$;其中 $e_{i,0}=1,e_{i,1}=1,e_{i,2}=0,e_{i,3}=1$

即求和顺序为 $11=(1*2^0+0*2^2)+(1*2^1+1*2^3)$


将 $e_i = \sum_{l=0}^{\lambda-1}e_{i,l}2^l$代入**$g_i^{e_i}$ 得 $g_i^{\sum_{l=0}^{\lambda-1}2^le_{i,l}}=\prod \limits_{l-0}^{\lambda-1}g_i^{2^le_{i,l}}$

将 $\prod \limits_{l-0}^{\lambda-1}g_i^{2^le_{i,l}}$ 按**矩阵方式**重排得 $\prod\limits_{j=0}^{s-1}\prod\limits_{k-0}^{t-1}g_i^{2^{j+s*k}e_i,j+s*k}$

### 转化为一个新的multi-product problem

设定一些符号


那么问题转化为


我们对这个过程进行可视化表示


G'₀的计算过程就是图中对应位置相乘的结果 依次类推 可以得到G‘₁......G't-1

**Efficiency**：

**最简单**的计算g'_i,j的过程就是对g_i进行s次的平方运算，整个过程需要进行√ λN次 群运算


### Computing the Multi-Products


简化符号，然后对问题再次转化


对群元素进行分组，每组包含b个。对于每个Si，计算Si的所有可能Ti。

通过Ti计算得到G'i。e'_i,j只能为0或者1 。那么对于G'_j就是g’_i的连乘结果，这结果一定包含在Ti中，所以计算G'i每次只需要每个Ti的一个元素。

**过程的视图如下：**


**分析效率**


### Recombining Inputs


### 整个流程的复杂度分析


### 参考
https://www.youtube.com/watch?v=bTiNNw8lHpc&feature=youtu.be
https://jbootle.github.io/Misc/pippenger.pdf
https://www.notion.so/Known-Optimizations-for-MSM-13042f29196544938d98e83a19934305#9d8b79321f584477ac945a738042c396
https://hackmd.io/@drouyang/msm

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