多标量乘法（MSM）的Pippenger算法

用于多标量乘法 (MSM) 的 Pippenger 算法

问题

给定

n 个标量

ki 和

n 个 EC 点

Pi, 计算

P 使得

P=∑i=0nkiPi

Pippenger / 桶算法

步骤 1：将标量划分为窗口

首先将每个标量划分为 m 个窗口，每个窗口有 w 位，则

ki=ki,0+ki,12w+...+ki,(m−1)2(m−1)w

你可以将每个标量 ki 视为一个大数，并将其表示为具有 limb 大小 w 的多精度整数。

然后我们有，

∑ikiPi=∑i∑j=0m−1ki,j2jwPi

通过重新排序求和，我们得到

∑ikiPi=∑j2jw(∑iki,jPi)=∑j2jwWj

这意味着我们可以首先计算每个窗口 Wj 的 MSM，然后通过 ∑j=0m−12jwWj 聚合结果。

接下来，让我们检查一下

Wj=∑i=0nki,jPi

步骤 2：对于每个窗口，按桶添加点

因为每个窗口有 w 位，ki,j 的值范围为 [0,2w−1]。 因此，我们可以根据 ki,j 的值, 将 n 个点放入 2w 个桶中。 我们可以先计算 Wj 通过，

1. 对于桶 t, t∈{0,2w−1}, 计算此存储桶中点的总和并获取 Bt
2. Wj=∑t=02w−1tBt

例如，如果 w=3 且 n=15，那么我们有 15 个点，8 个桶，这样

Wj=4P1+3P2+5P3+1P4+4P5+6P7+6P8+3P14+5P15=1P4+3(P2+P14)+4(P1+P5)+5(P3+P15)+6(P7+P8)=1B1+3B3+4B4+5B5+6B6

因此，

Wj=∑t=02w−1tBt

步骤 3：减少窗口结果

P=∑i=0nkiPi=∑j2jwWj

参考

https://www.notamonadtutorial.com/multiscalar-multiplication-strategies-and-challenges/

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

• 原文链接： hackmd.io/lNOsNGikQgO0hL...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～