BLS12-381 对我们其他人来说

在我开始 fiddling 这个东西之前，希望我知道的一切。

椭圆曲线 BLS12-381 在近年来成为了一位名人。许多协议都在使用它进行数字签名和零知识证明：Zcash、Ethereum 2.0、Skale、Algorand、Dfinity、Chia 等等。

不幸的是，关于 BLS12-381 的现有材料充满了“实例化其六次扭曲”和“最佳扩展场塔”等晦涩的咒语。我在这里来修复这一点 :smile:[1]

我不会给出椭圆曲线及其激动人心的群体性质的一般介绍。已经有一些 很好的入门书，我将假设你具备这些基本知识。同样，这里有许多内容并不特定于 BLS12-381，而是适用于其他曲线。

动机

BLS12-381 是一种适合配对的椭圆曲线。

基于配对的加密技术 在过去的几十年中发展起来，使得许多新的实用应用成为可能，例如 短数字签名，这些签名是 有效聚合的，基于身份的加密、单轮 多方密钥交换，以及高效的多项式承诺方案，如 KZG 承诺。

适合配对的椭圆曲线是具有良好嵌入度（下面会解释）和大素数阶子群的曲线（见下文）。这种曲线比较少。如果你随机创建一个椭圆曲线，成为适合配对的几率微乎其微。然而，它们可以被构造，并且 BLS 曲线就是明确构造为适合配对的。其它几类适合配对的曲线也已被知晓。

如果你想要更深入了解基于配对的加密技术，这里有一些阅读材料：

• 一篇简短的（但技术性的）解释，还有另一篇。
• Vitalik 有一篇关于 椭圆曲线配对 的很好的概述。
• 这份 NIST 报告 读起来相当容易。我推荐第 2 节和附录。
• 还有非常好的背景是 草案 IETF 标准 适用于配对友好的曲线。

如果你真的想要 理解 这些内容，那么 Pairings for Beginners 是非常好的。仔细研究，结合实例学习，发现它比看起来要简单得多。我真的很推荐这本书（我总是半途而废…）。

关于曲线 BLS12-381

历史

BLS12-381 曲线是由 Sean Bowe 在 2017 年初设计的，作为 Zcash 协议升级的基础。它既适合配对（这使得它在数字签名方面高效），又有效地构造 zkSnarks。

一系列“下一代”可扩展区块链协议使得生成可高效聚合或容易阈值化的短数字签名变得非常重要。BLS12-381 的属性使其常常成为这些协议的曲线选择。

几个密码学库—如 Apache 的 Milagro、如 Herumi 和 Blst 的新兴库—都支持 BLS12-381。并且已经有相应的动作将 BLS12-381 纳入 IETF 标准，如 配对友好的曲线，哈希到椭圆曲线，和 BLS 签名。这对协议的互操作性是个好消息！

命名

BLS12-381 是由 Barreto, Lynn, and Scott 描述的曲线系列的一部分（他们是这里的 B、L 和 S - 另一个 BLS 三人组将在 下面 出现）。

12 是曲线的嵌入度：既不是太低，也不是太高。我们将在稍后讨论嵌入度 在下文 中。

381 是表示曲线坐标所需的比特数：场模数 q。点的坐标来自具有素数阶的有限域，而这个素数 q 则是 381 位。381 是一个相当实用的数字，因为我们可以使用每个字段元素 48 字节，还剩下 3 位用于实用的标志或算术优化。该数字的大小由 安全要求 和实现效率两个因素引导。

曲线方程和参数

BLS12-381 曲线的基本方程是 y²=x³+4。

BLS 曲线的关键参数是使用单个参数 x（与曲线方程中的 x 不同！）设置的，该参数可以选择使曲线具有良好的实现属性。BLS12-381 从 taxonomy 中的构造 6.6 的 k≡0(mod 6) 情况派生而来。

BLS12-381 的具体设计目标是：

• x 具有“低哈明权重”，意味着它具有非常少的位设置为 1。这对于计算配对（米勒循环）的算法的效率特别重要。
• 上面提到的场模数 q 是素数并且比特数不超过 383，这使得在其上进行 64 位或 32 位算术操作更高效。
• 我们使用的子群的顺序 r 是素数并且不超过 255 位，这原因与上面相同。
• 安全目标是 128 位 - 请参见下文。
• 为了支持 zkSnark 方案，我们希望在域 Fr 中有一个大的 2n 次单位根。这意味着我们希望 2n 是 r−1 的一个因子，某个较大的 n。（使 x 为 2n² 的倍数可以实现这一点。）这个属性是能够利用快速傅里叶变换进行有趣的事情（例如多项式乘法）的关键。

值为 x= -0xd201000000010000（十六进制，注意它是负数）的选择提供了满足这些条件的最大 q 和最低的哈明权重。采用这个 x 值，我们得到了：

参数		方程	值（十六进制）	备注
场模数	q	13(x−1)²(x⁴−x²+1)+x	0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab	381 位，素数
子群大小	r	(x⁴−x²+1)	0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001	255 位，素数

本节的大部分参考来自于GitHub。许多曲线数据也在IETF 规范中。

场扩展

场扩展是椭圆曲线配对的基础。BLS12-381 中的“12”不仅是嵌入度，它还是我们需要使用的场扩展的度数。

场 Fq 可以被视为仅是整数模 q：0,1,...,q−1。但 Fq12 的 twelfth 扩展是什么样的？

我完全找不到任何简单易懂的场扩展解释，因此这是我在斗争一段时间后的尝试。

我们构造一个 Fq2，即 Fq 的二次扩展。在 Fq2 中，我们将场元素表示为一阶多项式，例如 a0+a1x，如果我们愿意，可以更简洁地写作 (a0,a1)。

将两个元素相加是简单的： (a,b)+(c,d)=a+bx+c+dx=(a+c)+(b+d)x=(a+c,b+d)。我们只需要确保将 a+c 和 b+d 除以 q。

那乘法呢？(a,b)×(c,d)=(a+bx)(c+dx)=ac+(ad+bc)x+bdx²=??? 哦——我们该怎么处理那个 x² 系数呢？

我们需要一个规矩来简化多项式，以便它们的次数小于二。在这个例子中，我们将采取 x²+1=0 作为我们的规则，但我们可以做其他选择。我们关于这条规则有两个要求[2]:

1. 它必须是一个次数为 k 的多项式，这里 k 是我们的扩展程度，即 2；以及
2. 它必须是在我们扩展的领域中 不可约。这意味着它不能被因式分解为两个或更多的低次多项式。

应用我们的规则，通过替换 x²=−1，最终结果为 (a,b)×(c,d)=ac+(ad+bc)x+bdx²=(ac−bd)+(ad+bc)x=(ac−bd,ad+bc)。这可能在复数算术中看起来有些熟悉： (a+ib)×(c+id)=(ac−bd)+(ad+bc)i。这不是偶然！复数是实数的一个二次扩展。

复数无法进一步扩展，因为 在复数上没有不可约多项式。但是对于有限域，如果我们可以在我们的域 Fq 中找到一个不可约的 k 次多项式，而且我们通常可以找到，那么我们就能够将领域扩展到 Fqk，并将扩展域的元素表示为次数为 k−1 的多项式 a0+a1x+...+ak−1xk−1。我们可以将其紧凑地表示为 (a0,...,ak−1)，只要我们记住可能存在一些非常有趣的算术。

同样值得注意的是，像这样的模约简（我们的简化规矩）可以选择得与 twisting 操作相配合。

在实际操作中，像 Fq12 这样的大扩展域被实现为较小扩展的塔。这是实现方面的内容，因此我将其放在下文的更实用部分 Extension-towers 中。

曲线

BLS12-381 初看起来不明显的一点是我们实际上处理的是两条曲线，而不是一条。这两条曲线大致共享同样的曲线方程，但在不同的域上定义。

比较简单的是在有限域 Fq 上的曲线，仅是整数模 q。所以，在方程 y²=x³+4 有解决方案的地方，曲线才有点。(0,2) 是这样的一个点，例如[3]。我们称这条曲线为 E(Fq)。

另一条曲线是在 Fq 扩展到 Fq2（想想复数）的基础上定义的。在这种情况下，曲线方程略微修改为 y²=x³+4(1+i)[4]，我们将称这条曲线为 E′(Fq2)[5]。我们会在 下文 中解释这条曲线的来源。

顺便提一句，E′(Fq2) 的曲线阶比 E(Fq) 的要大得多：当域扩展到复数时，曲线方程有更多的解。事实上，E 的阶接近 q，而 E′ 的阶接近 q²。这并不是偶然，而是 Hasse 界限 的结果。

子群

在本节和下一节中，我将解释 BLS12-381 为什么有两个曲线方程而不是一个。

配对是一种双线性映射。这意味着它需要输入两个点，每个来自同一阶 r 的群。r 必须是素数，并且为了安全性需要足够大。此外，由于一些相当技术性的原因，这两个群需要是不同的。我们称它们为 G1 和 G2。

不幸的是，我们简单的曲线 E(Fq) 只有单个大阶 r 的子群，因此我们无法仅根据 E(Fq) 定义配对。

然而，如果我们不断扩展 E 定义的域，可以证明我们最终会发现一条具有多个阶 r 的子群的曲线（实际上是 r+1 个）。也就是说，对于某个 k，E(Fqk)[6] 包含我们可以使用的其它阶 r 子群。其中一个子群仅包含痕迹为零的点[7]，我们选择这个子群作为 G2。

这个值 k，即我们需要扩展基域以找到新群的程度，称为曲线的 嵌入度，在我们的例子中就是 BLS12-381 中的“12”。我们稍后会更详细地讨论嵌入度。

为了完整起见，值得注意的是每个 G1 和 G2 与其包含曲线共享“无穷大点”。这是椭圆曲线算术群的恒等元素，通常用 O 表示。对于任何点 P，P+O=O+P=P。

所以，到此为止，我们在 E(Fq) 中有一个阶为 r 的群 G1，而在 E(Fq12) 中有一个不同的阶为 r 的群 G2。太好了，我们可以进行配对了！

扭曲

但是还有另一个挑战。如之前所讨论，在 Fq12 中进行算术运算非常复杂且低效。而且曲线操作需要大量算术运算。但看起来我们就只能陷入这种困境了。

难道没有其他选择吗？好吧，这里有个扭曲的转折…[8]

一个 扭曲 类似于一种坐标变换。非常奇妙的是，这可以用于将我们的 E(Fq12) 曲线转换为在较低次数域中定义的曲线，仍然具有阶 r 子群。此外，这个子群与我们的 G2 群之间有简单的映射关系[9]。

BLS12-381 使用“六次扭曲”。这意味着它将扩展场的次数减少了六倍。因此，G2 现在可以在 Fq2 上定义，而不是 Fq12，这极大地简化了复杂性。

我没有看到任何地方写下这个内容，但尝试解读这段会发现，如果我们找到 u，使得 u6=(1+i)⁻¹，那么我们可以定义我们的扭曲变换为 (x,y)→(x/u²,y/u³)。这将我们的原始曲线 E:y²=x³+4 转换成曲线 E′:y²=x³+4/u⁶=x³+4(1+i)。E 和 E′ 看起来不同，但实际上是在不同的基域下发生的同一对象[10]。

当扭曲 正确完成 时，得到的 E′ 具有一个子群，阶为 r，映射到我们的 G2 群，并且反之亦然。因此，事实证明，我们大多数情况下可以在 Fq2 的 E′ 中工作，并在需要时只有在实际计算配对时才将 G2 映射回 E(Fq12)。

因此我们将使用这两个群：

• G1⊂E(Fq) 其中 E:y²=x³+4
• G2⊂E′(Fq2) 其中 E′:y²=x³+4(1+i)

这就是 BLS12-381 看起来像两条曲线而不是一条的原因。

请注意，G1 群中点的坐标为整数对，而 G2 群中点的坐标为复数对，因此 G2 点占用的存储是 G1 的两倍，并且计算成本更高。这引发了一些有趣的 实现权衡。

配对

那么，这个配对是做什么的？

就 BLS12-381 而言，配对简单地将一个点 P∈G1⊂E(Fq) 和一个点 Q∈G2⊂E′(Fq2) 作为输出，返回一个来自 GT⊂Fq12 的点。这意味着，对于一个配对 e，有: e:G1×G2→GT。

配对通常表示为 e(P,Q)，并具有某些特殊属性。我不会详细讲解这些细节——我们可以将它们视为黑盒——但一个很好的介绍是 Vitalik 的文章，如果你想了解所有的细节，再次推荐 Pairings for Beginners。

我们感兴趣的是：

• e(P,Q+R)=e(P,Q)⋅e(P,R)，和
• e(P+S,R)=e(P,R)⋅e(S,R)

由此，我们可以推导出以下所有身份成立：

• e([a]P,[b]Q)=e(P,[b]Q)ⁱa=e(P,Q)ab=e(P,[a]Q)b=e([b]P,[a]Q)[11]。

这正是我们在验证 数字签名 时所需的内容。

如果有帮助，你可以粗略地认为配对是一种方法，用于将 G1 中的点与 G2 中的点“相乘”。如果我们将所有群以加法形式书写，那么算术运算会非常漂亮。然而，我们通常以乘法书写 GT，因此符号并不完全正确。

嵌入度

我们多次提到嵌入度，它的重要性使其在曲名称中出现。

嵌入度 k 的计算是最小的正整数，使得 r 整除 (qk−1)。因此，对于 BLS12-381，r 是 (q12−1)[12] 的一个因子，但在任何低次幂中都不是。

结果证明，这个数字给出了满足两个等价条件的最小场扩展 Fqk：

• Fqk 包含一个以上的阶 r 子群（用于构造 G2，见 上文）；
• Fqk 包含所有 r 次单位根（用于构造 GT，见 下文）

这些条件是配对可能性的要求。

选择嵌入度是一种安全性与效率之间的平衡（仍然是这样）。在 安全 方面，嵌入度也被称为安全乘数：较高的嵌入度使得在 GT 中离散对数问题变得更加困难。然而，较高的嵌入度意味着我们必须在高次扩展中进行场运算，如 Fq12，这样很笨重且效率低下。（即使使用 twists 也是如此：可用的最大扭曲是六度，因此我们能做到的最好的情况只是将场扩展度减少六次。并且，实际上配对必须在较大的扩展场中进行。）

嵌入度为 12 或 24 的值似乎是当前的最佳选择。再次重申，BLS12-381 的嵌入度是 12——它在名称中体现了这一点。

安全级别

密码系统的安全性是 以比特为单位测量的。非正式地说，我将 n 位安全性理解为“破解它大约需要 2n 次操作”。

对于椭圆曲线密码学，安全性问题在于使离散对数问题变得困难。也就是说，给定一个点 g 和一个点 gk（以乘法群符号表示），在没有先前知识的情况下找到 k 必须是不可行的。也就是说，必须至少需要 2n 次操作来实现这一点，n 应在今天的标准下大于 100。

对于适合配对的曲线，离散对数问题在我们使用的三组三个群中都必须是困难的。因此，为了针对 n 位安全性，

• 大素数群的顺序 r 必须至少为 2n 位长，因为有一些算法，如 Pollard 的 rho 算法，耗时是 O(r)。
• 我们扩展的域 Fqk 必须足够大，以避免受到诸如 数域筛法 的攻击。

BLS12-381 的设计初衷是提供大约 128 位的安全级别，基于这些标准，这一说法在最初的分析中得到了支持。参见 Taxonomy 中的表 1.1。

然而，经过仔细检查，似乎“有限扩展域大小为 3072 = 12 × 256 位并不够大”，直接引用 这里 的第 2 条标准。

根据 NCC Group 的报告，引用其他来源，实际的安全级别可能在 117 到 120 位之间（见第 8 页）。他们认为这是一种完全足够的安全级别：“达到 '128 位' 的价值在于更多的是一种心理效应。” Sean Bowe 还评论了在 原始设计目标下的安全级别。

余因子

子群的余因子是整个群的大小与子群的大小之比。正常的椭圆曲线密码学要求余因子非常小，通常为一，以避免在离散对数上的小子群攻击。然而，在基于配对的密码学中，情况则不然，G1 和 G2 群的余因子可能非常大。

事实证明，在小心处理的情况下，我们可以拥有大的余因子，并且仍然安全。即，当 G1、G2 和 GT 的余因子均不含小于 r 的素因子时。第 3.2 节 这篇论文 中详细讨论了这一点。然而，这并不是 BLS12-381 的真实情况，G1 和 G2 的余因子均有几个小因子。因此，在我们的实现中需要注意小子群攻击 在我们的实现中。

作为参考，G1 和 G2 的余因子如下。

群	余因子	方程	值（十六进制）
G1	h1	(x−1)²/3	0x396c8c005555e1568c00aaab0000aaab
G2	h2	(x⁸−4x⁷+5x⁶−4x⁴+6x³−4x²−4x+13)/9	0x5d543a95414e7f1091d50792876a202cd91de4547085abaa68a205b2e5a7ddfa628f1cb4d9e82ef21537e293a6691ae1616ec6e786f0c70cf1c38e31c7238e5

这些内容有什么意义？好吧，乘以余因子发现是一种简单的方法来将任意椭圆曲线上的点映射到各自的子群 G1 或 G2[13]。这在进行“哈希到曲线”操作时非常重要：我们首先在曲线上生成一个点，然后通过乘以余因子将其映射到适当的群，这称为 余因子清除。

单位根

关于单位根的一点说明，因为它们出现在两个完全不同且不相关的上下文中，这可能会令人困惑。

首先，我们说，为了支持这条曲线的 zkSnark 方案，对于某个较大的 n，我们希望在域 Fr（而非 Fq）中有一个 2n 次的单位根。这是为了促进高效的快速傅里叶变换，以便对标量域 Fr 上的非常大的多项式进行操作。从 r−1 的十六进制表示来看，它明显是 2²³² 的倍数，因此存在 2²³² 次单位根（事实上有 2²³² 个）。任务完成，:thumbsup:

其次，完全不相关的是，配对的效果是将来自 G1 和 G2 的两个点映射到 Fq12 中的 r 次单位根。这些 r 次单位根实际上在 Fq12 中形成一个阶为 r 的子群[14]，即我们称之为 GT 的群。

让我们简要回顾一下 我们关于扩展基域的讨论，我们将 E 扩展到 Fq12，是为了找到一个阶为 r 的子群。结果，Fq12 作为乘法群观看，是包含域中 r 次单位根的最小场扩展，12 再次来自于嵌入度。这就是为什么 GT 被定义在 Fq12 上。

使用曲线 BLS12-381

本节是一些与实际使用 BLS12-381 相关的杂项。

BLS 数字签名

现在是介绍另一组 BLS 的时候了：Boneh、Lynn 和 Shacham。 (L 是 BLS12-381 中的那个相同的 L; B 和 S 是不同的。)

BLS 签名早在 2001 年就被引入2011，在 BLS 曲线系列2002 之前，但令人愉快的是，它们是结合在一起的。 （BLS 签名可以使用其他曲线；BLS 曲线也可以有其他用途。但它们结合在一起很不错。）

IETF 标准草案中提供了对 BLS 签名方案非常简洁但清晰的描述草案。另请查看 GitHub 仓库。

私钥和公钥

私钥（将用于签名）是 1 到 r−1 之间随机选择的数字。我们将其称为 sk。

相应的公钥（如果我们使用 G1 作为公钥）是 pk=[sk]g1，其中 g1 是选定的 生成元 的 G1。这就是：g1 乘以 sk，这相当于 g1 自身重复相加 sk 次。

离散对数问题意味着在给定公钥 pk 的情况下恢复 sk 是不可行的。

签名

要对消息 m 进行签名，我们首先需要将 m 映射到 G2 群中的点（如果我们使用 G2 进行签名）。请参见哈希到曲线， 下面 会讨论如何实现这个过程。无论如何，我们假设我们可以这样做，并将得到的 G2 点称为 H(m)。

我们通过计算 σ=[sk]H(m) 来签名消息。也就是说，通过将哈希点乘以我们的私钥。

验证

给定消息 m、签名 σ 和公钥 pk，我们希望验证该签名是用与 pk 相对应的 sk 签名的。

这时 配对 的作用就体现出来了。只有当且仅当 e(g1,σ)=e(pk,H(m)) 时，签名才是有效的。

我们可以使用配对的性质确认这一点： e(pk,H(m))=e([sk]g1,H(m))=e(g1,H(m))(sk)=e(g1,[sk]H(m))=e(g1,σ)。

聚合

BLS 签名一个非常巧妙的性质是它们可以被 聚合（另请参见 原始论文），因此我们只需两次配对即可验证由 n 个参与者签署的单个消息，或者为了验证 n 个不同消息的签名，我们则需要 n+1 次配对，而不是你可能天真的想象需要的 2n 次配对。配对计算起来很昂贵，因此这十分吸引人。

可以对不同消息进行签名聚合，或对相同消息的签名进行聚合。在以太坊 2.0 中，我们会对同一消息进行签名聚合，因此为简洁起见，我将仅考虑这一点。

要聚合签名，我们只需将它们对应的 G2 点相加： σagg=σ1+σ2+...+σn。我们还聚合相应的 G1 公钥点 pkagg=pk1+pk2+...+pkn。

现在配对的魔力意味着我们只需验证 e(g1,σagg)=e(pkagg,H(m)) 就能同时验证所有签名，只需两次配对。

rogue key attacks

正如第 1.1 节所指出的在这里，在聚合相同消息的签名时，我们需要考虑可能的“恶意公钥攻击”。

假设你的公钥是 pk1，而我有私钥 sk2。但我没有发布我的真实公钥，而是发布 pk2′=[sk2]g1−pk1（即，我的真实公钥加上你的公钥的逆）。我可以通过我的私钥签名消息 H(m)，产生 σ=[sk2]H(m)。然后我发布这个，声称它是一个你我都已签名的聚合签名，聚合的公钥是 pkagg=pk1+pk2′。

现在，在验证时，我的说法显得合情合理：看起来你签署了此消息的人实际上并非如此： e(g1,σ)=e(g1,[sk2]H(m))=e([sk2]g1,H(m))=e(pk1+pk2′,H(m))。

对抗这种攻击的一种简单防范措施，就是在以太坊 2.0 中使用的那种，强制验证者注册其声称公钥对应私钥的“持有证明”。你看，攻击者并没有 sk2′ 对应于 pk2′。这可以通过让验证者在注册时签名自己的公钥来简单做到：如果签名通过验证，那么一切就没问题。

更复杂的方案(不需要私钥知识证明) 可用。

G1 和 G2 的互换

在数字签名的目的下，G1 和 G2 群是可以互换的。我们可以选择将公钥作为 G1 的成员，而签名作为 G2 的成员，反之亦然。

权衡在于执行速度和存储大小。G1 具有小点且速度快；而 G2 具有大点但速度慢。BLS12-381 最初设计用于实现 Zcash，因此出于性能原因，他们选择使用 G1 代表签名，并使用 G2 代表公钥。

就 Zcash 而言，大多数其他实现是“反向”的。在以太坊 2.0 中，我们使用 G1 作为公钥：一方面，聚合公钥的情况远比单签名聚合更为频繁；另一方面，验证者的公钥需要存储在状态中，因此保持表示小型化非常重要。这样，签名便成为 G2 点。

点压缩

（注意，有时 扭曲 操作被称为点压缩——这与我们在这里讨论的完全不同。）

为了存储和传输椭圆曲线点，通常会丢掉 y 坐标。这一做法能够使数据量减半。在 BLS12-381 中，G1 点从 96 字节（2 × 381 位舍入到字节）减少到 48 字节，而 G2 点则从 192 字节减少到 96 字节。

任何椭圆曲线点都可以通过使用相应的曲线方程 E 或 E′ 从 x 坐标再生出。对于曲线上的任何有效 x 坐标，y 要么为零，要么具有两个可互为否定的值：G1 中的 y=±x³+4，同理也适用于 G2。

由于场元素为 381 位，而 48 字节为 384 位，因此我们有几个位可以保留用于标志。最重要的是一个标志，用于显示该点对应的 y 值（正或负）。另一个位用于信号表明这是无穷大点（这个点有许多可能的表示）。第三个位仅用于指示这是压缩表示还是未压缩表示，尽管上下文在实践中应该处理中。

对于 G1 和 G2，大约一半的 x 值不在曲线上。在这种情况下，点通常解码为驻点无穷大。但除非无穷大标志被设置——在这种情况下我们将不会尝试解码该点——这将被视为错误条件。

有关标志位和 x 值编码的具体细节，请参见 这里。

子群成员资格检查

在处理任何未知来源的点时，无论其是压缩还是未压缩，检查它是否位于正确的子群中是非常重要的。上述描述的点解压缩仅结果为曲线上的一个点；我们不知它位于适当的 G1 还是 G2 中。主要问题似乎在于，E(Fq) 和 E′(Fq2) 都包含小子群（你可以通过对共同因子进行因式分解来查看，例如使用 这个 工具）。无意中在这些小子群中的点上工作可能会导致漏洞，正如 这篇论文 中所讨论的。

子群检查原则上很简单：仅需将我们的点乘以 r。对于 G1 或 G2 中的点，这将导致相应的无穷大点；对于不在这些组中的点，则不会。

不幸的是，这在实际操作中很慢，特别是对于 G2，因为 r 是如此之大。作为替代办法，存在一些 新技术，利用自同构来进行更快速的子群检查。

生成器

G1 和 G2 是循环的质数阶群，因此任何点（除了恒等点/无穷大点）都是生成器。因此，选择生成器只是一种约定。

G1 和 G2 的生成点以十进制在 这里 指定，且相同的点以十六进制在 这里 指定。

这些生成点的选择 如下：

G1 和 G2 的生成器通过找到字典序最小的有效 x 坐标以及其字典序最小的 y 坐标并将其缩放到共同因子来计算，以确保结果不是无穷大点。

根据我的计算，h1 和 h2 分别是组的 共同因子，这使得 G1 生成器 g1=[h1]p1，p1 如下，

p1 = (0x04, 0x0a989badd40d6212b33cffc3f3763e9bc760f988c9926b26da9dd85e928483446346b8ed00e1de5d5ea93e354abe706c)

而 G2 生成器 g2=[h2]p2，p2 如下，

p2 = ([0x02, 0x00],[0x013a59858b6809fca4d9a3b6539246a70051a3c88899964a42bc9a69cf9acdd9dd387cfa9086b894185b9a46a402be73,0x02d27e0ec3356299a346a09ad7dc4ef68a483c3aed53f9139d2f929a3eecebf72082e5e58c6da24ee32e03040c406d4f])

（我认为“字典序最小”是指将基域中的所有数字视为非负并只取较小的一个，优先考虑实部而非虚部。）

最终指数运算

计算配对分为两个部分：米勒循环和最后的指数运算。两者都是相当昂贵的，但你可以进行一个巧妙的优化来减少最终指数运算的影响。

通常，我们会计算两个完整的配对来进行签名验证，以检查 e(g1,σ)=e(pk,H(m))。

如果我们用 e′(⋅,⋅) 表示没有最终指数运算的配对，那么对于某些 x，我们正在检查是否 e′(g1,σ)x=e′(pk,H(m))x。（x 恰好是 (qk−1)/r，这个值非常大。）

我们知道如何在组 GT 中进行乘法，因此我们可以重新组织这是否（e′(−g1,σ)e′(pk,H(m)))x=1。（我们可以否定其中一个点：配对的魔力使得这等同于在 GT 中取逆。）

因此，为了验证签名，我们执行两个米勒循环，一个与否定输入值一起，将结果相乘，然后执行单个最终指数运算。如果结果在 GT 中是单位，则我们的配对匹配。这有望带来显著加速。

哈希到曲线

要对消息计算数字签名，我们首先需要将任意消息（字节串）转换为 G2 曲线上的点（如果我们使用 G2 进行签名）。这有很多方法可以做到，各自具有不同的效率和安全性。

哈希并检查

Eth2 中的初始实现是“哈希-并-检查”。这非常简单。

1. 将你的消息哈希为一个取模 q 的整数
2. 检查是否存在具有此 x 坐标（实部 x，虚部 0）的曲线上的点。如果没有，则加一并重复[15]。
3. 我们在曲线上找到了一个点！乘以 G2 共同因子以将其转换为 G2 中的点。

大约一半我们尝试的点将导致曲线上的一个点，因此这不是恒定时间——我们不知道找到一个所需的迭代次数。在某种意义上，这并不重要：所有信息都是公开的，因此我们并没有泄露任何内容。然而，这确实带来了一个烦扰攻击。攻击者可以预先计算出需要很长时间才能找到一个点的消息（例如，每一百万条消息中有 1 条将需要进行 20 次尝试），并显著减缓我们的速度。

简化的 SWU 映射

我们现在正在采用一种更好的方法，描述于 这篇论文，并用于新的（草稿） IETF 哈希到曲线标准 中。与之前一样（但稍有不同以确保输出点的均匀分布），我们首先通过对消息进行哈希取模 q 创建一个域点。

现在我们使用一个特殊的映射（SWU 映射），它保证将该域点转换为椭圆曲线上有效点。出于技术原因，这 不是 曲线 E′(Fq2)，而是一个与之同构的曲线 示同构 （即拥有相同数目点的曲线）。然后我们使用另一映射（3-示同构）将其转移到 E′(Fq2) 上。最后，我们使用 共同因子清除 来得到 G2 中的一个点。

你可以查看我在 Java 中的 实现，基于 Python 中的参考代码。这个方法的意图是被广泛采用，以增强区块链的互操作性。

共同因子清除

我们讨论过通过 共同因子 的乘法将 E 或 E′ 中的任意点转换为 G1 或 G2 中的点。这在 哈希到曲线 时非常有用，例如。

G2 的共同因子非常大，因此乘以它的速度很慢。然而，使用 (一个映射到自身的群映射 ) 自同构有 更快速的方法 来将曲线点映射到 G2。它出现在新的 标准 中（见第 7 节）。

我们要使用的自同构曾受 专利 保护，但现在在任何地方都已过期。

作为对专利的变通办法，标准建议乘以一个有效的共同因子（请参见 第 8.9.2 节以获取该值），这个有效的共同因子提供的结果与自同构相同。有效共同因子的值 甚至还大于 G2 共同因子，但乘法可以通过 加法链 作为优化来实现。

这个思路是，现在专利已过期，自同构可以直接替代有效的共同因子乘法。

扩展塔

回忆一下我们关于 域扩展 的讨论？实际上，更有效的方法是从较小的扩展构建它，而不是直接实现一个巨大的 12 次扩展： 扩展塔。

对于 BLS12-381，Fq12 领域是作为一个二次（2 次）扩展实现的，位于一个三次（3 次）扩展的之上，位于 Fq 的一个二次扩展之上。

只要模块约减多项式（我们的约减规则）在每个阶段的扩展所处的域中是不可约的（不能被因式分解），那么这一切就很好。

具体而言：

1. Fq2 被构造为 Fq(u)/(u2−β)，其中 β=−1。
2. Fq6 被构造为 Fq2(v)/(v3−ξ)，其中 ξ=u+1。
3. Fq12 被构造为 Fq6(w)/(w2−γ)，其中 γ=v。

根据我们之前的说明进行解释：

1. 我们将 Fq2 领域的元素写成以 u 为一阶多项式，系数来自 Fq，并应用约减规则 u2+1=0，这在 Fq 中是不可约的。
   • Fq2 的一个元素看起来像 a0+a1u，其中 aj∈Fq。
2. 我们将 Fq6 领域的元素写成以 v 为二阶多项式，系数来自我们刚构建的 Fq2 领域，并应用约减规则 v3−(u+1)=0，这在 Fq2 中是不可约的。
   • Fq6 的一个元素看起来像 b0+b1v+b2v2，其中 bj∈Fq2。
3. 我们将 Fq12 领域的元素写成以 w 为一阶多项式，系数来自我们刚构建的 Fq6 领域，并应用约减规则 w2−v=0，这在 Fq6 中是不可约的。
   • Fq12 的一个元素看起来像 c0+c1w，其中 cj∈Fq6。

这样的扩展塔可以替代直接扩展作为配对的基础，并且当实现良好时，可以在乘以 Fq12 点时节省大量的算术运算。请参见 为初学者推荐的配对 第 7.3 节，获得有关其优势的完整讨论。

坐标系

找到一个域元素的逆（即除法）是一个昂贵的操作，因此椭圆曲线算术的实现尽量避免它。选择正确的坐标系来表示我们的点会很有帮助。

仿射坐标

仿射坐标是点的传统表示，只包含一个 (x,y) 坐标对，其中 x 和 y 符合曲线方程。我们通常在存储和传输点时会使用这种方式。

然而，当我们实际处理点时，它并不是最有效的形式，我知道有两种其他方案用于 BLS12-381。

基本思路是使用名义分数表示坐标，减少所需的实际除法运算数。为此，引入一个第三坐标，我们用 (X,Y,Z) 来表示点的内部表示。就像我们熟悉的分数一样，同一个值有多种表示形式，所有这些都对应同一个实际值（例如 12、36、197394 都是同一个数字）。

我知道用于 BLS12-381 的两个系统是标准射影坐标和雅可比坐标。

标准射影坐标

标准射影坐标 点 (X,Y,Z) 代表仿射坐标点 (X/Z,Y/Z)。

这些也称为无穷大射影坐标，因为曲线方程采纳了无穷大形式 Y2Z=X3+4Z3。点在 (X,Y,Z) 空间中变成了通过原点的直线，而仿射点则是线与平面 Z=1 的交点。PfB 中的图 2.10 给出了很好的插图。

标准射影坐标在 Apache Milagro BLS12-381 库底层使用。

雅可比坐标

另一种类型的射影坐标是 雅可比坐标。在该方案中，雅可比点 (X,Y,Z) 代表仿射点 (X/Z2,Y/Z3)。曲线方程变为 Y2=X3+4Z6。

示例代码 中的恒定时间哈希到曲线使用底层的雅可比坐标。

请注意，在这两种方案中，引入仿射点 (x,y) 的最简单方法是将其映射到 (x,y,1)。

资源和进一步阅读

上面提到的参考资料很多，我不打算在这里重复许多。让我只挑出一些特别有用或有趣的内容。

有用的参考材料：

• 最初的 BLS12-381 公告
• 简明 的参数和序列化说明
• 草稿 IETF 标准
• 以上内容的 tl;dr 版本， 忙碌人士的 BLS

总的来说，配对库的实现往往高度优化和/或十分通用（支持多条曲线），这使得它们的学习难度相当高。JavaScript/TypeScript 中的 Noble BLS12-381 库无疑是比较容易跟随的。

最后，有几个有趣的阅读材料：

• 这份关于 Curve9769 的全新白皮书与 BLS12-381 并不直接相关，但对设计和实现椭圆曲线的乐趣与痛苦进行了一次精彩的探讨（在这种情况下不是一条与配对友好的曲线）。
• 配对并未消亡，而是暂时休息。一份很好的概述报告以及一些 BLS12-381 相关的内容。

就这些了，各位！

非常感谢尊敬的同事 Olivier Bégassat、Thomas Piellard、Herman Junge、Błażej Kolad 和 Gus Gutoski 提供的审阅、理智检查和意见。（自你们上次看到后我进行了某些修改，任何错误皆为我的责任。）

Ben Edgington, ben@benjaminion.xyz

PegaSys, ConsenSys

---

1. 我多年前学习数学，但认真逃避与纯数学有关的任何内容，包括群论。我现在对此感到遗憾。无论如何，这不会太技术性，但我也不是专家，所以可能会错一些事情，且通常会有些含糊。如果显而易见的话，我并不是一个密码学家。↩︎

2. 我们的规则是“扩展域模约减”（术语来自 此处）。↩︎

3. E(Fq) 的另一个点是 (0x04,0x0a989badd40d6212b33cffc3f3763e9bc760f988c9926b26da9dd85e928483446346b8ed00e1de5d5ea93e354abe706c)。平均而言，大约一半的 x 值会导致曲线上的一个点，对于大多数这些点 (x,y) 和 (x,−y) 均在曲线之上（对某些点而言，y=0）。你会很快习惯这些极其庞大的数字。↩︎

4. 有时这里使用的是 u 而不是 i，以 u2+1=0。我使用的是 i。↩︎

5. 这里一个 E′ 曲线上的点是：(1+i, 0x17faa6201231304f270b858dad9462089f2a5b83388e4b10773abc1eef6d193b9fce4e8ea2d9d28e3c3a315aa7de14ca + i * 0xcc12449be6ac4e7f367e7242250427c4fb4c39325d3164ad397c1837a90f0ea1a534757df374dd6569345eb41ed76e) ↩︎

6. 请注意，我们在这里失去了 ′，这是原始曲线 y2=x3+4，但现在定义在 Fqk 上。↩︎

7. “零迹子群”符合一个晦涩的咒语。基本上，一个点的迹是 ∑i=0k−1(xqi,yqi)，在我们的情况下 k=12。了解这一点涉及到像 Frobenius 自同构这样的东西，这个兔子洞相当深。↩︎

8. :joy: 请原谅我。↩︎

9. …因为我们之前选择了零迹子群。为初学者推荐的配对 详细说明了这一点。↩︎

10. 特别感谢我的评审者提供的见解 ↩︎

11. [a]P 是将点 P 乘以标量 a。这是说将 P 加 a 次。传统上，G1 和 G2 的群操作是加法表示的，而在 GT 中是乘法表示的。↩︎

12. 这个世界中的数字真的很大。r 除以 (q12−1) 的次数在十进制中长达 1299 位。这个数字实际上是在计算配对时用于最后的指数运算。↩︎

13. 这一点很容易看出。子群 G 的阶为 r，其共同因子为 h，因此 hr=n，是整个椭圆曲线群的阶。考虑椭圆曲线群中的一个任意元素 P。我们有 O=[n]P=[r]([h]P)。因此，[h]P∈G。虽然这并不是特定于 BLS12-381，但这里有一篇 优秀的文章 关于共同因子清除。↩︎

14. 这是乘法群中的单位根的一个一般性特性，不特定于椭圆曲线或配对。↩︎

15. 这应该是在失败时“增加消息并返回到一” ，这更加安全。↩︎

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