多标量乘法：策略与挑战

介绍

生成一个 zk-SNARK（零知识简洁非交互式知识论证），就像 Aleo 使用的那种，涉及大量的密码学计算，几乎所有这些计算都发生在有限域上的椭圆曲线内部。

椭圆曲线

以下是 这篇文章 的简短版本。

椭圆曲线点是有限域中的一对数字 $(x,y)$（你可以将有限域视为 $Z_p$，即对某个巨大的质数取模的整数，尽管有时它们不止于此），它们满足以下形式的方程：

$y^2=x^3+ax+b$

对于有限域中的某些 $a$ 和 $b$。

你可以对椭圆曲线点求和，但不能以传统方式进行。不是执行

$(x_1,y_1)+(x_2,y_2)=(x_1+x_2,y_1+y_2)$

我们这样做：

$(x_1,y_1)+(x_2,y_2)=(x_3,−y_3)$

其中

$x_3=s^2−x_1−x_2$ $y_3=s(x_1−x_3)−y_1$ $s=\frac{y_2−y_1}{x_2−x_1}$

对此有两个例外：

1. 当 $(x_1,y_1)=(x_2,y_2)$ 时
2. 当 $x_1=x_2$ 但 $y_1≠y_2$ 时。在这种情况下，由于不存在其他解决方案，因此 $y_1=−y_2$。

在 1 和 2 中，上面的计算都未定义（我们将除以零），因此我们改为执行以下操作：

1. 一个点与其自身的和，和以前一样，是一个点 $(x_3,y_3)$，只是在这种情况下

$x_3=s^2−2x_1$ $y_3=(x_1−x_3)−y_1$ $s=\frac{3x_1^2+a}{2y_1}$

（这里，$a$ 是定义上述曲线方程的系数）。

2. 在这种情况下，求和的结果是一个我们任意添加到曲线的唯一点，称为无穷远点，记为 $O$。此点用作我们求和的零，即，

$O+(x,y)=(x,y)$

对于每个 $(x,y)$。

原始操作

椭圆曲线密码学最终依赖于两个原始操作，点加法（将两个不同的点相加）和点倍乘（将一个点加到自身），我们称之为 ECADD 和 ECDBL。

如果我们尝试将一个点多次加到自身，我们可以应用 double-and-add 算法。正如我们 发表的文章 中已经解释的那样，这个想法很简单：如果我们想计算，例如，对于某个曲线点 $P$ 的 $9P$，我们可以执行以下操作，而不是执行 9 次加法

$P+P=2P$ $2P+2P=4P$ $4P+4P=8P$ $4P+P=9P$

这只是四次加法运算。

当我们必须添加许多不同的点 $k_1P_1+k_2P_2+...+k_nP_n$ 时，大多数技术都假定给定了这些原语，并专注于如何执行标量乘法 $k_iP_i$ 和加法，从而最大限度地减少 ECADD 和 ECDBL 的数量。

MSM

多标量乘法问题包括，给定一个椭圆曲线，计算

$\sum_{i=1}^{n}k_iP_i$

对于某些标量（又名，模某个质数的整数）$k_i$，某些椭圆曲线点 $P_i=(x_i,y_i)$ 和某个 $n$（在 Aleo 的挑战中，它是 $2^{26}$）。

此处的求和运算是上一节中讨论的运算。类似地，$k_iP_i$ 表示“$P_i$ 加到自身 $k_i$ 次”，该求和再次是上面定义的求和。

生成 zk-SNARK 证明的时间大约 80% 用于执行 MSM，因此优化它对于性能至关重要。

分桶方法

我们可以将 MSM 分解为更小的和，并通过重复使用窗口技术来减少操作次数。如果我们想计算每个 $k_iP_i$，我们可以将其分解为大小为 $c$ 的窗口

$k_iPi=k{i0}Pi+k{i1}2^cPi+k{i2}2^{2c}Pi+...+k{i,m-1}2^{c(m-1)}P_i$

使用这个，我们可以将 MSM 问题重写为

$P=\sum_ik_iP_i=\sum_i\sumjk{ij}2^{cj}P_i$

我们现在可以更改求和的顺序，

$P=\sum_ik_iP_i=\sum_j2^{cj}(\sumik{ij}P_i)=\sum_j2^{cj}B_j$

换句话说，我们首先将标量分成窗口，然后组合每个窗口中的所有点。现在我们可以专注于如何有效地计算每个 $B_j$：

$$ Bj=\sum{i} k_{ij}Pi=\sum{\lambda=0}^{2^c-1} \lambda \sum_{u(\lambda)} P_u $$

wherethesummationover$u(λ)$isdoneonlyoverpointswhosecoefficientis$λ$.Forexample,if$c=3$andwehave$15$points,wherethesummationover$u(λ)$isdoneonlyoverpointswhosecoefficientis$λ$.Forexample,if$c=3$andwehave$15$points,

$B_1=4P_1+3P_2+5P_3+1P_4+4P_5+6P_7+6P8+3P{14}+5P_{15}$

Wecansplitthesummationbythecoefficients$λ$,takingvaluesfrom$1$to$7$.For$λ=1$,$∑uPu=P4$(because$P4$istheonlyonewithcoefficient$1$),for$λ=4$,$∑uPu=P1+P5$,etc.Weplaceallpointswithacommoncoefficient$λ$intothe$lambda$bucket.Thus,Wecansplitthesummationbythecoefficients$λ$,takingvaluesfrom$1$to$7$.For$λ=1$,$∑uPu=P4$(because$P4$istheonlyonewithcoefficient$1$),for$λ=4$,$∑uPu=P1+P5$,etc.Weplaceallpointswithacommoncoefficient$λ$intothe$lambda$bucket.Thus,

$$
B_j=\sum_\lambda \lambda S_{j\lambda}=S_{j1}+2S_{j2}+3S_{j3}+4S_{4j}+5S_{5j}+6S_{j6}+7S_{j7}
$$

Wecancalculatethiswithaminimumnumberofpointadditionsusingpartialsums.$Tj1=Sj7$$Tj2=Tj1+Sj6$$Tj3=Tj2+Sj5$$Tj4=Tj3+Sj4$$Tj5=Tj4+Sj3$$Tj6=Tj5+Sj2$$Tj7=Tj6+Sj1$Eachoftheseoperationsinvolvesdoingjustoneellipticpointaddition.Wecanobtainthefinalresultbysummingthesepartialsums:Wecancalculatethiswithaminimumnumberofpointadditionsusingpartialsums.$Tj1=Sj7$$Tj2=Tj1+Sj6$$Tj3=Tj2+Sj5$$Tj4=Tj3+Sj4$$Tj5=Tj4+Sj3$$Tj6=Tj5+Sj2$$Tj7=Tj6+Sj1$Eachoftheseoperationsinvolvesdoingjustoneellipticpointaddition.Wecanobtainthefinalresultbysummingthesepartialsums:

$$
B_j=\sum T_{jk}
$$

我们可以通过更改系数 $k_i$ 的展开来改进计算。在二进制表示中，汉明权重是非零位的数量。理想情况下，我们希望这个权重尽可能小，以减少加法的数量（例如，65537，即 $2^{16}+1$，在许多实现中用作 RSA 密码系统的公钥。平方和乘算法只需要两次乘法）。二进制表示中的平均汉明权重是 $1/2$；如果我们引入有符号二进制表示 $(-1,0,1)$，则平均权重将降低到 $1/3$，从而减少操作次数（平均而言）。

BLS 12-377

Aleo 使用的曲线称为 BLS 12-377。基域（有限域）的阶数为 $q$（一个 377 位质数），并且具有 12 的嵌入度。椭圆曲线群 $G_1$ 的阶数 $r$ 和有限域都是高度 2-adic 的（也就是说，$q$ 和 $r$ 都可以写成 $2^{\alpha}r+1$，其中 $r$ 是一个奇数，$α$ 大于 40）。阶数 $q$ 和 $r$ 通过嵌入度相关：$r∣q^{12}−1$。椭圆曲线的方程为

$$
y^2=x^3+1
$$

此外，我们可以在 $F_q$ 的二次域扩展上构建第二个群 $G_2$；曲线的方程为

$$
y^2=x^3+B
$$

其中 $B$ 是一个参数。有关曲线参数的更多信息，请参见此处。

BLS 12-377 双有理等价于 Montgomery 和 twisted Edwards 曲线。这使我们能够通过避免代价高昂的字段反转来更快地执行点加法和标量乘法。在 Montgomery 曲线的情况下，可以在恒定时间内执行标量乘法，从而使该操作能够抵抗时序攻击。

BLS 12-377 曲线和（双有理等价的）twisted Edwards 曲线的实现在此存储库中给出。

BLS 12-377 是配对友好的椭圆曲线之一；这些曲线具有诸如可有效聚合的短数字签名、多项式承诺方案和单回合多密钥交换之类的应用。

我们为 BLS 曲线提供两个方程和两个群的原因与配对有关。配对是一种双线性映射：它接受两个点，每个点来自一个素数阶 $r$ 的群。由于技术原因，这些群需要不同。由于原始曲线只有一个阶数为 $r$ 的群，因此我们需要扩展该域以找到其他阶数为 $r$ 的群。嵌入度给出了我们必须扩展该域以找到那些其他群的程度。作为奖励，扩展域包含所有 $r$ 次单位根。

关于域扩展的说明

嵌入度也是我们需要使用的域扩展的度数。域扩展的常见示例是实数 $R$（扩展有理数域 $Q$，这是一个超越扩展）和复数 $C$（扩展 $R$）。后者无法进一步扩展，因为 $C$ 中没有不可约多项式（我们说复数是代数闭的）。

如果我们想构建 $Fq$ 的二次扩展 $F{q^2}$，我们可以将其视为多项式 $a_0+a_1x$，其中 $a_0$ 和 $a_1$ 是 $F_q$ 中的元素。加法很简单，因为我们分别添加独立项和线性项。对于乘法，给定元素 $a$ 和 $b$

$a×b=a_0b_0+(a_0b_1+a_1b_0)x+a_1b_1x^2$

为了避免超出线性多项式的问题，我们可以使用不可约多项式（例如 $x^2+1$）并将 $x^2+1=0$ 来降低度数。如果我们替换上面的等式，

$a×b=a_0b_0−a_1b_1+(a_0b_1+a_1b_0)x$

这类似于复数中的乘法。

选择多项式的条件是：

1. 它必须具有与扩展域相同的度数（在我们的例子中是二次的）。
2. 它必须在我们正在扩展的字段中不可约，这意味着我们无法将其分解为更小 degree 的多项式。

$F{q^{12}}$ 中的算术运算既复杂又昂贵。幸运的是，我们可以执行六次扭曲，以便在 $F{q^2}$ 上定义群 $G_2$。

实际上，当我们想要构建诸如 $F_{q^{12}}$ 之类的字段扩展时，我们可以通过以顺序形式扩展较小的字段来进行，即扩展塔（例如 $Q→R→C$）。

使用 FFT 加速

FFT 的潜在用途是在实现原语 ECADD 和 ECDBL 时。我们可以在不同的坐标系中执行这些操作。正如此处所述，投影坐标通常要快得多，因为它们避免了执行有限域反转，这比乘法和加法昂贵得多。

当使用投影坐标时，计算速度更快，因为我们用乘法代替除法。这意味着有很多乘法运算要做，这就是为什么我们需要有效的方法来乘以整数，其中 Karatsuba、Toom 或 FFT 算法可能会变得有吸引力，因为我们正在处理大整数的乘法。最佳算法将取决于整数的大小。

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