概述

Multi-Scalar Multiplicatiton(MSM)是一个对群中元素的标量乘法求和的算法

若$\mathbb G$为循环群,$G_i\in \mathbb G$为群中元素,现有一系数向量$\vec a=(a_1,\dots a_n),a_i\in \Z$,MSM算法的目的是计算下列求和式

$$ \sum^n_{i=1} a_i\cdot G_i $$

不难看出这个式子需要的加法和乘法的次数均为$n$次,由于群上的加法和乘法比有限域上的要复杂的多,而且实际中采用的群又特别大(比如BLS或BN曲线的群,群的阶$p$​为256比特的素数)

MSM又是ZKP协议中非常常见的一个基本算法, 因此需要有一种方式来减少此类求和式的计算开销

优化的目标为减少加法的数量,如果采用朴素的方式计算每个$a_i\cdot G_i$(全部相乘再相加),此时每个群元素平均需要的群操作次数为$1.5b$次($b$为群的阶的比特数),$n$个元素就是$1.5bn$次,对于上面那种很大的群,需要$384n$次群操作

在Groth16算法中,MSM算法用于Prover计算证明元素(系数向量$\vec a$为秘密输入),$n$很大的时候开销也很大,Zcash中的$n$大约为$4\times 10^4$,Rollup方案中为了确保可扩展性,$n$也需要尽可能地大

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

优化方案

zkTeam利用bucket的思想(和桶排序的那个思想一致),开发了gnark库(Ref:ConsenSys / gnark-crypto),该方案可以将需要的群加法数量优化至$16n$加上一个恒定常数,对于BLS这种需要$384n$的ECC群而言,效率提高了约24倍

bucket的思想于2012/549这篇论文中的第四节提出,主要思想是首先将一个$b$比特的MSM拆分为若干个$c$比特的MSM并用类似于桶排序的思想分别处理这些小的MSM,最后再合并回$b$比特的MSM

接下来看一下如何进行

总体步骤

首先将系数向量$\vec a=(a_1,\dots a_n)$的各个元素以二进制形式表示,之后选择$c\leq b$,将二进制拆分成大小为$c$的块,该步骤记为$(b,c,b/c)$

举个例子,比如$b=12,c=3$,每一个12比特的系数均拆分成4个3比特的部分,比如系数$a=1368$,12比特的二进制表示为$010101011000$,将这12比特拆分成四组3比特并分别表示为十进制,也即拆分成$010\ 101\ 011\ 000$,每组用十进制表示就是$(2,5,3,0)$,因此将$a$表示为$a=(2,5,3,0)$,根据上面提到的记法,该步骤记为$(12,3,4)$

依次处理向量中的每个系数$a_i$,得到$a_i=(a_{i,1},a_{i,2},a_{i,3},a_{i,4})$​

之后对每个$a_{i,j}$,分别计算一个小的MSM,如下

$$ \begin{aligned} T_1=a_{1,1}\cdot G_1+\cdots+a_{n,1}\cdot G_n\\ T_2=a_{1,2}\cdot G_1+\cdots+a_{n,2}\cdot G_n\\ T_3=a_{1,3}\cdot G_1+\cdots+a_{n,3}\cdot G_n\\ T_4=a_{1,4}\cdot G_1+\cdots+a_{n,4}\cdot G_n\\ \end{aligned} $$

然后将这四个$T_i$组合起来,得到一个最终的$T$,如下

  1. $T = T_1$
  2. for $i = 2,3,4$:$T = 2^c* T,T = T+T_j$

上述过程中计算最终$T$需要的群加法操作次数为$(b/c-1)\times (c+1)=b-c+\frac{b}{c}-1$

处理方式

接下来介绍如何利用桶排序的思想处理每一个小的MSM,比如经过上面第二步的处理,我们可以得到$T_1$如下

$$ T_1=6G_1+2G_2+6G_3+G_4+7G_5+2G_6+3G_7+\cdots $$

然后我们构造$2^c-1$个桶,根据$G_i$的系数将他们分配到对应的桶里面,在上面的例子中,$c=3$,因此这里需要7个桶,注意,这里只是将系数所对应的群元素放到桶里面,系数本身不需要保存到桶里面

分配完毕后就是下面这个图的结果

之后我们记第$i$个桶的求和为$S_i$,比如$S_1=G_4+G_9+G_{14}$,$S_7=G_5+G_{12}$,计算这些桶需要的加法操作次数为$n-(2^c-1)=n-2^c+1$

然后我们再将所有的桶,根据其系数对其进行累加即可,也即计算

$$ S=\sum^7_{i=1}i\cdot S_i $$

由于每个$S_i$都是一个群元素,因此求和的过程本质上也是一个MSM,但是这个MSM的输入数量固定,为$2^c-1$个输入,群元素的规模也是已知的,为$1,\dots, 2^c-1$

上述例子中,我们有$c=3$,因此式1中需要计算$S=S_1+2S_2+\cdots+7S_7$,这里有个快速计算的方式,如下

$$ \begin{aligned} S=&S_7+\\ &S_7+S_6+\\ &S_7+S_6+S_5+\\ &S_7+S_6+S_5+S_4+\\ &S_7+S_6+S_5+S_4+S_3+\\ &S_7+S_6+S_5+S_4+S_3+S_2+\\ &S_7+S_6+S_5+S_4+S_3+S_2+S_1 \end{aligned} $$

需要的加法次数为$2*(2^c-2)+1=2^{c+1}-3$

因此整个方案需要的加法次数为

$$ \frac{b}{c} \times (n-2^c+1+2^{c+1}-3)+(b-c+\frac{b}{c}-1)\approx \frac{b}{c}\times (n+2^c) \tag 1 $$

若$c\approx \log n$,则方案的复杂度约为$O(\frac{bn}{\log n})$,由于上述优化方案要求$c\leq b$,因此当$n$很大时($n>2^b$)无法选择$c\approx \log n$来达到最优的效果,因此当$n>2^b$时,方案会退化回线性阶复杂度(比如$b=1$)

实际方案中,很可能会出现$n=10^7$的情况,此时取$c\approx \log n=23$即可,gnark中的曲线为$b=256$,此时取$c=16$即可,代入到式1中,可以得到方案需要的加法为$16n+2^{12}$次

这里有一点需要指出,为什么$b=256$时取$c=16$,因为内存大小总是2的幂次,一个256比特的数一般而言会保存为4个64比特的数,因此取$c=16$更好处理

进一步优化

并行计算

不难看出,上述方案是可以并行计算的,因此多核或多处理器环境中的实际计算效率会比较高

比如上面的例子中,$b=256,c=16$,此时可以充分利用系统中的$256/16=16$个核心,不过每个核需要$2^c=2^{16}$的额外内存开销

预计算

不过MSM有一个问题:不太能利用群元素$G_i$已预计算的优势,实际环境中群元素通常都是已经预计算好的,但是MSM不太能用上这个优势

因为MSM算法在处理大规模情况时,本来就需要大量的内存开销(BLS12-377,$n=10^8$情况下gnark需要58G内存),此时再对群元素进行一些预计算处理(比如预计算$G,2G,G_1+G_2,G_1+G_2+G_3$),此时会引入更大的内存开销,如果暂时丢到外存,大量的IO开销又是一个瓶颈

回顾一下前面的MSM步骤,将大的MSM(b比特)拆分为小的MSM(c比特)时,我们需要对小的MSM进行一个求和,也即在大小为c比特的系数上对$a_iG_i$求和,如果说这个步骤中$a_iG_i$已经计算好了(在内存中),我们就省去了对每个桶的求和步骤(无需计算$S_1,\dots,S_{2^c-1}$),从而也就省去了对所有桶的求和(无需计算$S=\sum^{2^c-1}_{i=1}i\cdot S_i$)

如果可以利用上面这一优势的话,需要的群加法可以减少至$\frac{b}{c}n+(b-c+\frac{b}{c}-1)\approx \frac{bn}{c}$,但是这么做需要$(2^c-2)n$的额外内存空间,极限情况下,对于$b=c=256$,保存所有的$2^{256}$个点的话只需要$n$次群加法,但是现实场景中,对于$(n,b,c)=(2^{23},256,16)$的情况,需要保存多达$5.5\times 10^{11}$个点(一个点512bit,可以算一下需要多少内存)

不过还有一种预计算的方法可以改善,具体如下

对于每个输入的$G$,预计算$k$个点:$(2^c-k)G,\dots,(2^c-1)G$,此时在往桶里面放群元素的时候只需要对前面的$2^c-1-k$个群元素进行处理就可以了,桶求和和桶累加也只需要对前$2^c-1-k$个桶进行处理,此时需要的加法数量减少至$\frac{b}{c}(n+2^c-k)$,额外的内存开销为$kn$个群元素,可以尽可能增大$k$的值来提高计算开销

不过这个方法最大的问题在于:如果系统的存储空间有限,这个方法并不会有很显著的优化效果,只有那种具有很大存储空间的系统适用这个方法

短汉明重量

考虑系数的二进制表示的汉明重量,是否可以减少需要的群加法的数量,比如下面这个例子

系数二进制表示群加法次数
1281000 00007
1701010 101010
2401111 000010
2551111 111114

考虑能否采用另一种编码方式来表示系数,使其可以具有更小的汉明重量,比如引入-1来表示系数,此时平均汉明重量可以降低为1/3

系数编码群操作次数
1280 1 0 0 0 0 0 0 07次加法
1700 1 0 1 0 1 0 1 010次加法
2401 0 0 0-1 0 0 0 08次加法,1次减法
2551 0 0 0 0 0 0 0 -18次加法,1次减法

不过有一点需要注意,ECC群中减法的计算开销和加法一样,所以只是减少了需要的操作次数,并没有降低每次操作的计算开销

或者通过引入双数表示法来表示系数,比如用$2^i3^j$来表示系数,但是问题在于此类表示法冗余度很高,每个系数可能有多种表示方式,比如127可以有下列三种表示方式

$$ \begin{aligned} 127&=2^23^2+2^13^2+2^03^0\\ 126 &= 2^23^3+2^43^0+2^03^1\\ 127 &= 2^53^1+2^03^3+2^23^0 \end{aligned} $$

此时平均汉明重量可以进一步的降低

但是降低汉明重量并不能有效改善MSM算法,因为在上述桶的思想中,桶的计算开销会随着系数的增多而增大,对于长度为$c$比特的小规模MSM,只需要考虑$2^c$个可能的系数,同时需要的桶的数量也仅为$2^c$(并行需要多一点),但是修改系数的编码方式并不能确保这一点

有符号位

考虑引入负数的方式来优化,根据椭圆曲线的对称性,给定群元素$G=(x,y)\in \mathbb G$,求其负元素$-G=(x,-y)\in \mathbb G$几乎不需要什么开销,这么一来,我们可以将规模为$c$比特的系数集合$\{0,\dots,2^c-1\}$修改为$\{-2^{c-1},\dots,2^{c-1}-1\}$​

此时需要修改一下往桶里面放入群元素的规则,如下

  • 若系数$a>0$,则将元素$G$放入第$a$个桶
  • 若系数$a<0$,则将元素$-G$放入第$|a|$个桶

这么一来,我们可以将桶的数量减少为原来的一半,就像下面这样

此外,桶的求和和累加方式不变,求和和累加的桶的数量也都仅为原来的一半

这个方式有两种优化方式,如果保持原来的$c$不变,则需要的群加法次数为$\frac{b}{c}(n+2^{c-1})$,若令$c=c+1$,则需要的次数为$\frac{b}{c+1}(n+2^c)$

但是第二个增加$c$的方式不一定适用,因为根据前面提到的,不太好在系统中把$c$改成一个不是2的幂的数(这里作者用第一种方式,在$n=10^6$的情况下可以有大约5~6%的效率提升,有点东西,但是不多)

后面不想看了,可以直接看PPT$[1]$,或者看原视频$[2]$,或者感兴趣的话可以看看这个算法的优化版本$[3]$,优化算法有一个视频讲解$[4]$,但是讲的可能比较乱

References

$[1]$ Multi-scalar multiplication: state of the art and new ideas Jun. 01, 2020 - Sildes

$[2]$ zkStudyClub: Multi-scalar multiplication: state of the art & new ideas with Gus Gutoski (Consensys) - YouTube

$[3]$ Efficient Multi-Exponentiation - Jonathan Bootle

$[4]$ $[MIT IAP 2023]$ Modern ZK Cryptography_ Lecture 6_ Algorithms for Efficient Cryptographic Operations