用于多标量乘法（MSM）的带符号桶索引
如果我们把桶索引当作有符号整数，我们就能在桶索引编码中节省一位，因此减少桶的数量，并将桶的内存使用量减半。这个方法被称为带符号桶索引方法，也被称为 NAF 方法。这个方法在 [1] 中被报告，并且被 zPrize MSM-WASM track 的前两名实施者实现。
NAF 代表 Non-Adjcent Form（非相邻形式）。NAF 的经典定义记录在 Textbook Definition of Non-Adjacent Form (NAF)。
直觉
在桶方法中，我们把每个标量
s 切分成
c-bit 的切片
si，并且使用
si 作为桶索引。如果我们忽略桶
0 (因为
0∗P=0)，那么我们有
si∈{1,...,2c−1}
所以，我们总共需要
2c−1 个桶。
但是，如果有一种方法（稍后解释）把
si 映射到以下范围
{−2c−1,...,−1,1,...,2c−1−1}
我们可以使用以下技巧，
if slice s_i > 0, add P to bucket // 如果切片 s_i > 0，则将 P 添加到桶中
if slice s_i < 0, add -P to bucket // 如果切片 s_i < 0，则将 -P 添加到桶中
然后，我们只需要桶
{1,...,2c−1}，也就是总共
2c−1 个桶。
例如，对于切片
si∈{1,2,3,4,5,6,7}，总共需要
23−1=7 个桶，如果我们把
si 映射到
{−4,−3,−2,−1,1,2,3}，只需要
2(3−1)=4 个桶。
解决方案
该部分从 Gregor Baude 在一个 slack 频道中的描述修改而来
给定窗口大小
c, 记
L=2c。
首先，把标量
s 切分成
K 个切片
si 在数学上意味着
s=s0+s1L+...+sK−1LK−1=∑isiLi
注意，在两个切片之间，我们有如下等式：
siLi+si+1Li+1=(si−L)Li+(si+1+1)Li+1
换句话说，我们可以把一个切片减少
L，通过把
1 进位到下一个更高的切片。
最初，
si 在 [0, L) 范围内，所以我们需要
L−1 个桶（忽略
0 桶）。我们想要摆脱上半部分。所以，无论何时
si>=L/2，我们把它替换成
si−L 并把 1 加到下一个切片
si+1。
在这次转换之后，
si 在
[−L/2,L/2) 范围内。如果
si 是负数，我们可以对切片和点都取反，因为
(−si)∗G=si∗(−G)。这样做会使我们的
si 非符号位进入
[0,L/2] 范围。所以得到一半大小的范围。确实，我们把
2c−1 个桶减少到
2c−1 个桶。
所以伪代码的算法是：
let carry = 0; // 设进位为0
for (i = 0,...,K-1) {
s[i] += carry; // we have to add the carry bit from last iteration! // 我们必须加上来自上次迭代的进位！
if (s[i] >= L/2) {
s[i] = L - s[i]; // note: we subtract L and negate at once // 注意: 我们同时减去 L 并取反
carry = 1;
addToBucket(-point, s[i]); // use negated point // 使用取反的点
} else {
carry = 0;
addToBucket(point, s[i]);
}
}
警告：如何处理最高切片
sK−1>=L/2 的情况？
处理最高切片的溢出
上面的实现忽略了最终的进位结果（我们没有把它加到任何地方）。所以，这里有一个隐含的假设：最终的进位是
0。如果最终的进位是
1，那么这个和就不对了。
什么时候最终的进位会是
1？
让我们首先假设窗口大小不能均分标量位长度。具体来说，对于标量长度
128 位（那是你在 GLV 分解后得到的），假设你的窗口宽度是
c=13。因为
13∗9=117，你会得到
10 个切片，但是最终的切片只有
11 位被设置
(128−117)，而不是完整的
13 位。这意味着在上面算法的最后一步，我们永远不会处于
s[i]>=L/2 的情况，所以最终的进位永远不会是
1。我们很好！
但是，如果 c 能均分标量位长度，大约一半的标量会有
1 的最终进位。所以，这会使算法不正确。这具体发生在
c=16 的情况，这是 MSM 大小为
218 的最佳窗口宽度。
一个简单的解决方案是把标量位长度设置为比实际值大一位，
129 而不是
128。然后，你保证永远不会有最终进位。但是，这很愚蠢，因为在
c=16 的情况下，这意味着你的最终切片只有
1 位，并且你为了这
1 个额外的位运行了一个完整的子 MSM。
一个改进的技巧是转换标量，使它们永远不会设置它们的 MSB。（注意：我们在这里谈论的是整个标量的 MSB，而不是单个切片的 MSB。这一切都是为了避免最终进位。）以下技巧在 Yrrid 的解决方案中实现。
如果标量的 MSB 被设置，我们对标量和点取反，并继续正常处理。这可以工作因为：（M - s）(-P) = -s (-P) = s P
如果没有 GLV 分解，标量有
255 位，也就是
15∗17，所以坏的情况是
c=15,17。我们可以简单地避免这些窗口大小，或者做一些天真的事情，假装标量大小是
256。在 GLV 分解后，我们需要处理两个标量的一半，两个都不能设置它们的 MSB。
参考文献
[1] Multi-scalar multiplication: state of the art & new ideas with Gus Gutoski [youtube 49:00]
####### tags: msm zkp public
