BLS12-381指南

• 原文：BLS12-381 For The Rest Of Us
• 作者：Ben Edgington
• 译者：Kurt Pan

开始鼓捣之前，我希望我知道的。 近年来，椭圆曲线BLS12-381逐渐火了起来。许多协议都将其应用到了数字签名和零知识证明中：Zcash、Ethereum 2.0、Skale、Algorand、Dfinity、Chia 等等。 不幸的是，现有的关于 BLS12-381 的资料里充满着晦涩的咒语，比如“实例化其六度扭”和“最优扩张域塔”。我就是来解决这个问题的。我不会对椭圆曲线及其令人兴奋的群的性质进行一般性介绍。这方面已经有一些很棒的入门资料了，我将假设读者具有这些基础知识。当然，这里的很多内容并非只特定于 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 标准的举措，例如Pairing-Friendly Curves、Hashing to Elliptic Curves和BLS signatures。这对于协议互操作性来说是个好消息！

命名

BLS12-381 是Barreto、Lynn 和 Scott描述的曲线簇的一部分（他们就是是此处的 B、L 和 S -稍后将出现不同的 BLS 三人组）。

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

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

曲线方程和参数

BLS12-381曲线的基础方程是$y^2=x^3+4$。

一条BLS 曲线的关键参数是由单个参数 $\mathbf{x}$ （与曲线方程中的 x 不同！）来设置的，可以通过选择该参数来为曲线提供对实现良好的性质。 BLS12-381 源自“分类法”论文中构造 6.6 的 k ≡ 0(mod 6)的情况。

BLS12-381 的具体设计目标如下：

• $\mathbf{x}$ 具有“低汉明权重”，即只有很少的位设置为1 。 这对于计算配对算法（米勒循环）的效率尤其重要。
• 上面提到的域模数 q 是质数且具有 383 位或更少，这使得在其上进行 64 位或 32 位算术更加高效。
• 使用的子群的阶 r 是质数且具有 255 位或更少，与上面的原因相同。
• 安全目标是 128 比特 - 见下文。
• 为了支持 zkSnark 方案，我们希望在 $F_r$ 域中具有大2的幂的单位根。 即对于一些较大的 n，我们希望 $2^n$ 成为 r-1 的因子。 （使 $\mathrm{x}$ 为 $2^{\frac{n}{2}}$ 的倍数即可实现此目的。）该性质是能够使用快速傅立叶变换来实现多项式乘法等有趣事物的关键。

值 $\mathbf{x}$= -0xd201000000010000 （十六进制，注意它是负数）给出了满足这些条件的最大 q 和最低汉明权重。 有了这个 $\mathbf{x}$ 值，我们就有，

参数		方程	值（十六进制）	注
域模数	q	$\frac{1}{3}(\mathbf{x}-1)^2\left(\mathbf{x}^4-\mathbf{x}^2+1\right)+x$	0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab	381 位, 素数
子群大小	r	$\left(\mathbf{x}^4-\mathbf{x}^2+1\right) $	0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001	255位，素数

本节大部分内容的参考。 IETF 标准中也包含大量曲线数据。

域扩张

域扩张是椭圆曲线配对的基础。 BLS12-381中的“12” 不仅是嵌入度，也是需要使用的（相对）域扩张度。

可以认为域$Fq$只是整数模 $q: 0,1, \ldots, q-1$。 但 $F{q^{12}}$ 是什么鬼，$F_q$ 的第十二个扩张吗？

我没在任何地方找到任何简单的关于域扩张的解释，以下是我在努力理解一段时间后的尝试。

我们来构造一个 $F_{q^2}$，$Fq$ 的二阶扩张。 在 $F{q^2}$ 中，我们将域元素表示为一次多项式，比如 $a_0+a_1 x$，如果愿意也可以更简洁地写为 $\left(a_0, a_1\right)$。

两个元素相加很容易： $(a, b)+(c, d)=a+b x+c+d x=(a+c)+(b+d) x= (a+c,b+d)$。 只需确保约简$a+c$ 和 $b+d$ 模 q。

相乘呢？ $(a, b) \times(c, d)=(a+b x)(c+d x)=a c+(a d+b c) x+b d x^2=???$。 糟糕 - 我们应该如何处理 $x^2$ 系数呢？

我们需要一个规则来约简多项式，使其阶数小于二。 此例中，我们将采用 $x^2+1=0$作为该规则，但也可以做出其他选择。 关于我们的规则只有两条原则：

1. 它必须是一个 k 次多项式，其中 k 是我们的扩张度，在本例中为 2；
2. 在扩张域中必须是不可约的。 意思是不可能将它分解为两个或多个较低次数的多项式。

应用我们的规则，通过代入 $x^2=-1$，得到最终结果 $(a, b) \times(c, d)= ac+(ad+bc)x+bdx^2=(ac−bd)+(ad+bc)x=(ac−bd,ad+bc)$。 这可能看起来有点熟悉，像复数算术：$(a+i b) \times(c+i d)=(a c-b d)+(a d+b c) i$。 这不是巧合！ 复数就是实数的二阶扩张。

复数无法进一步扩张，因为复数上不存在不可约多项式。 但对于有限域，如果我们可以在域 $Fq$ 中找到一个不可约的 k 次多项式（我们经常可以做到），那么我们就能够将域扩张到 $F{q^k}$，并表示扩张域的元素为 k-1 次多项式 $a_0+a1 x+\ldots+a{k-1} x^{k-1}$。 我们可以将其简洁地表示为 $\left(a0, \ldots, a{k-1}\right)$，只要我们记住这里面可能存在一些不寻常的算术就可以。

可以选择像这样的模约简（约简规则）使其可以很好地配合扭操作。

在实践中，像 $F_{q^{12}}$ 这样的大扩张域通常被实现为较小扩张的塔。 这和实现相关，我将其放在下文部分中。

两条曲线

关于BLS12-381 并不明显的一点就是我们实际上在处理的是两条曲线，而不是一条。 两条曲线或多或少共享相同的曲线方程，但在不同的域上定义。

更简单的那条曲线是在有限域 $F_q$（整数 mod q）上。 方程 $y^2=x^3+4$ 的 x 和 y 均小于 q 的整数的解构成了曲线上的点。 比如一个这样的点是(0,2) 。 我们将这条曲线称为$E\left(F_q\right)$。

另一条曲线是在 $F_q$ 的扩张 $F{q^2}$ 上定义的（想想复数）。 在这种情况下，曲线方程会稍微修改为 $y^2=x^3+4(1+i)$，我们将这条曲线称为 $E^{\prime}\left(F{q^2}\right)$. 我们将在下面的扭中解释其来源。

顺便说一句，$E^{\prime}\left(F_{q^2}\right)$ 的曲线阶数比 $E\left(F_q\right)$的阶数大得多：曲线方程有很多 当域扩展到复数时，会有更多解。 事实上，E的阶数接近q，而$E^{\prime}$的阶数接近$q^2$。 这并非偶然，而是哈塞束缚的结果。

$E^{\prime}\left(F_{q^2}\right)$ 的曲线阶数比 $E\left(F_q\right)$ 的阶数大得多：当域扩张到复数时，曲线方程会有更多的解。 事实上，E的阶数接近q，而$E^{\prime}$的阶数接近$q^2$。 这并非偶然，而是Hasse界的结果。

子群

本节和下一节中，我将解释 BLS12-381是如何最终得到两个而不是一个曲线方程的。

配对是双线性映射。 这意味着它需要两个点作为输入，各自取自相同阶r的群 r必须是素数，且为了安全性需要很大。 此外，出于技术原因，这两个群需要不同。 我们称它们为$G_1$ 和$G_2$。

不幸的是，简单曲线 $E\left(F_q\right)$ 只有一个阶 r 的大子群，因此我们不能仅基于 $E\left(F_q\right)$ 来定义配对。

然而，如果我们持续扩张E定义的域，可以证明我们最终会找到一条具有多个r阶子群的曲线（实际上有r+1个子群）。 也就是说，对于一个 $k，E\left(F_{q^k}\right)$ 包含可以用的其他 r 阶子群。 这些子群的其中一个仅包含迹为零的点，我们选择该子群为 $G_2$。

这个数字 k 是我们需要扩张基域以找到新群的量，称为曲线的嵌入度，在BLS12-381 中为“12”。 我们稍后将详细讨论嵌入度。

为完整起见，注意到 $G_1$ 和 $G_2$ 中的每一个都与其包含的曲线共享“无穷远点”。 这是椭圆曲线算术群的单位元，通常表示为$\mathcal{O}$。 对于任意点P，$P，P+\mathcal{O}=\mathcal{O}+P=P$。

到这里，我们在 $E\left(F_q\right)$ 中有一个阶 r 的群 $G1$，在 $E\left( F{q^{12}}\right)$中有一个不同的阶 r 的群 $G_2$。 很好 – 可以做配对了！

扭

但还有另一个挑战。 正如前面所讨论的，在 $F_{q^{12}}$ 中进行算术运算非常复杂且效率低下，而且曲线运算需要大量的算术运算。 看起来这就是卡住我们的地方。

真的这样吗？嗯，这里故事有一个转折…

扭（twist）类似于坐标变换。 更奇妙的是，可以用来将我们的 $E\left(F_{q^{12}}\right)$ 曲线转换为在仍具有阶 r 的子群的低阶域上定义的曲线。 此外，这个子群与我们的 $G_2$ 群 之间有一个简单的映射。

BLS12-381 使用“六度扭”（sextic twist），意思是它将扩张域的阶降低了六倍。 因此扭曲线上的 $G2$ 可以通过 $F{q^2}$ 而不是 $F_{q^{12}}$ 来定义，这大大节省了复杂性。

我还没有在任何地方看到这个被写下来 - 但这里的第 3 节在试图进行解释 - 如果我们找到一个 u 使得 $u^6=(1+i)^{-1}$ ，那么我们可以定义扭变换为$(x, y) \rightarrow\left(x / u^2, y / u^3\right)$。 这会将原始曲线 $E: y^2=x^3+4$ 转换为曲线 $E^{\prime}: y^2=x^3+4 / u^6=x^3+4(1 +i）$。 E 和 $E^{\prime}$ 看起来不同，但实际上是针对不同基域中的系数呈现的同一对象。

当扭正确完成时，得到的 $E^{\prime}$ 具有一个 r 阶子群，映射到我们的 $G2$ 群，反之亦然。 因此，事实证明，在大多数情况下，我们可以在 $E^{\prime}$ 上使用 $F{q^2}$ ，并仅在需要时（即实际计算配对时）将 $G2$ 映射回 $E\left(F{q^{12} }\right)$ 。

这是我们将使用的两个群：

• $G_1 \subset E \left(F_q \right)$ 其中 $E: y^2=x^3+4$
• $G2 \subset E^{\prime} \left(F{q^2} \right)$ 其中 $E^{\prime}: y^2=x^3+4(1+i)$

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

注意$G_1$ 群中的点的坐标是一对整数，$G_2$ 群中的点的坐标是一对复数，因此 $G_2$ 的点占用两倍的存储量，工作成本更高 。这导致了有趣的实现中的权衡。

配对

所以这个配对到底是怎么回事呢？

就 BLS12-381 而言，配对就是取点 $P \in G_1 \subset E \left(F_q \right)$ 和点 $Q \in G2 \subset E^{\prime}\left (F{q^2}\right)$ ，并输出群 $GT \subset F{q^{12}}$ 中的一个点。 也就是说，对于配对 $e， e: G_1 \times G_2 \rightarrow G_T$

配对通常表示为 e(P, Q) 并且具有一些特殊性质。 我不会去详细介绍所有细节（我们几乎可以将它们视为黑盒），Vitalik 的文章提供了很好的介绍，而对于所有精彩的细节，让我再次推荐“Pairings For Beginners”。

我们感兴趣的是：

• $e(P, Q+R)=e(P, Q) \cdot e(P, R)$，且
• $e(P+S, R)=e(P, R) \cdot e(S, R)$

由此，我们可以推断出以下所有等式都成立：

• $e([a] P,[b] Q)=e(P,[b] Q)^a=e(P, Q)^{a b}=e(P,[a] Q)^b= e([b] P,[a] Q)$

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

你可以大致将配对视为将 $G_1$ 中的点“乘以”$G_2$ 中的点的一种方法。 如果所有群都用加法符号，那么算术就会很好地运转。 然而我们通常将 $G_T$ 用乘法表示，因此这种表示法并不太正确。

嵌入度

我们已经多次提到嵌入度，它的重要性使得它足以出现在曲线的名称中。

嵌入度 k 为使 r 整除 $\left(q^k-1 \right)$ 的最小正整数。 因此，在 BLS12-381 的情况下，r 是 $\left(q^{12}-1 \right)$ 的因子，但不是任何更低幂的因子。

事实证明，这个数字给出了满足两个等价条件的最小域扩张 $F_{q^k}$：

• $F_{q^k}$ 包含多个 r 阶子群（用于构造 $G_2$，见上文；
• $F_{q^k}$ 包含所有 r 次单位根（用于构造 $G_T$，见下文

这些是使得配对成为可能必须满足的条件。

嵌入度的选择是安全和效率之间的平衡（一如既往）。 安全方面，嵌入度也称为安全乘子：较高的嵌入度使得$GT$中的离散对数问题更难解决。 然而，高嵌入度意味着我们必须在高阶扩展，例如$F{q^{12}}$，中进行域操作，这是笨重且低效的。 （即使使用扭也是如此：最大可用扭为六度，因此我们能做的最好的是将域扩张度减少六倍。并且无论如何，配对必须在大扩张域中完成。）

12 或 24 的嵌入度似乎是当前许多应用的最佳选择。 再次强调，BLS12-381 的嵌入度就是名称中的12。

安全级别

密码系统的安全性是以比特来衡量的。非正式地，我将 n 比特安全性理解为“需要大约 $2^n$ 个操作才能破解”。

对于椭圆曲线密码学，安全性就是要使离散对数问题困难。 也就是说，给定一个点 g 和一个点 $g^k$（以乘法群表示），在没有先验知识的情况下找到 k 必定是不可行的。 也就是说，至少需要 $2^n$ 次操作才能实现此目的，按今天的说法，$n>100$ 左右。

对于配对友好的曲线，离散对数问题在我们使用的三个群中的每一个中都必须是困难的。 因此，为了实现 n 比特安全性，

• 素数群阶 r 必须至少为 2n 位长，因为有些算法（例如 Pollard 的 rho 算法）的开销为 $O(\sqrt{r})$。
• 扩张域 $F_{q^k}$ 必须足够大，以免受到数域筛法等方法的影响。

BLS12-381 旨在根据这些原则提供大约 128 比特的安全级别，这得到了初步分析的支持。 例如，请参见分类法论文中的表 1.1。

然而，经过仔细检查，按照上述第二个标准，“大小为 $3072=12 \times 256$ 位的有限扩张域似乎不够大”（引用这里的第 2 节）。

根据 NCC Group 引用其他来源的一份报告，其实际安全级别可能在 117 到 120 比特之间（参见第 8 页）。 他们认为这是一个完全足够的安全级别：“达到‘128 比特’的价值主要是心理上的”。 Sean Bowe 还根据最初的设计目标对安全级别进行了评论。

协因子

一个子群的协因子是整个群的大小和子群大小的比。平常的椭圆曲线密码学要求协因子非常小，通常为一，以避免对离散对数的小子群攻击。 然而在基于配对的密码学中，情况并非如此，$G_1$ 和 $G_2$群的协因子可能会非常大。

事实证明，只要小心，我们可以在拥有大协因子的同时依然安全。 即当$G_1，G_2$ 和 $G_T$ 的协因子不包含小于r的素因子时。这篇论文的3.2节对此进行了详细讨论。然而这并非BLS12-381的情况 ，$G_1$ 和 $G_2$ 的协因子都有一些小因子。 因此，我们必须在实现中小心小子群攻击。

作为参考，$G_1$ 和 $G_2$ 的协因子如下。

群	协因子	方程	值（十六进制）
$G_1$	$h_1$	$(\mathrm{x}-1)^2 / 3 $	0x396c8c005555e1568c00aaab0000aaab
$G_2$	$h_2$	$\left(\mathrm{x}^8-4 \mathrm{x}^7+5 \mathrm{x}^6-4 \mathrm{x}^4+6 \mathrm{x}^3-4 \mathrm{x}^2-4 \mathrm{x}+13\right) / 9$	0x5d543a95414e7f1091d50792876a202cd91de4547085abaa68a205b2e5a7ddfa628f1cb4d9e82ef21537e293a6691ae1616ec6e786f0c70cf1c38e31c7238e5

这一切意义何在？ 事实证明，乘以协因子是将椭圆曲线上的任意点映射到相应子群 $G_1$ 或 $G_2$ 的直接方法。 这在进行“哈希到曲线”等操作时很重要：我们首先在曲线上取一个点，然后通过乘以协因子（所谓的协因子清除）将其映射到正确的群里。

单位根

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

首先，我们说为了用这条曲线支持 zkSnark 方案，对于一些较大的 n，我们希望在域 $F_r$（注意不是 $F_q$） 中有$2^n$ 次单位根。 这是为了使用高效的快速傅里叶变换，以在标量域 $F_r$ 上操作非常大的多项式。 从r-1的十六进制表示来看，它显然是$2^{32}$的倍数，因此存在$2^{32}$次单位根（事实上有$2^{32}$个）。 任务完成

其次，完全不相关地，配对的效果是将 $G_1$ 和 $G2$ 中的两个点映射到 $F{q^{12}}$ 中的 r 次单位根。 这些r次单位根实际上构成了$F_{q^{12}}$的阶r的子群，我们称之为$G_T$群。

让我们简要回顾一下将 E 的基域扩张到 $F{q^{12}}$ 的讨论，我们这样做是为了找到 r 阶的另一个子群。 而实际上被视为乘法群的 $F{q^{12}}$ 是包含域中第 r 个单位根的最小域扩张，12 再次来自嵌入度。 这就是为什么 $GT$ 是在 $F{q^{12}}$ 上定义的。

曲线BLS12-381的使用

本节是与实践中使用 BLS12-381 相关的内容的大杂烩。

BLS数字签名

现在是介绍另一个 BLS 的时候了：Boneh、Lynn 和 Shacham。（L 与 BLS12-381 中的 L 是一个人；B 和 S 不是。）

BLS 签名于 2001 年提出，比 2002 年BLS 曲线系列发布稍早一些。令人高兴的是，它们是携手共进的关系。（BLS 签名可以使用其他曲线；BLS 曲线也有签名以外的用途。但是当它们结合在一起时就挺不错。）

IETF 标准草案中对 BLS 签名方案有相当简洁明了的描述。另请参阅该GitHub 库。

公私钥

私钥（用于签名）就是一个1到r-1之间随机选择的一个数，称之为sk。

相应的公钥（如果我们对公钥使用$G_1$）为$p k=[s k] g_1$，其中$g_1$为对$G_1$选择的生成元。即用sk乘上$g_1$，就是把$g_1$ 自己相加sk次。

离散对数问题的意思是给定公钥pk恢复sk是不可行的。

签名

要对消息 m 签名，我们首先需要将 m 映射到群 $G_2$ 中的一个点（如果我们使用 $G_2$ 进行签名的话）。 对此实现方法的讨论，请参阅下面的哈希到曲线。 现在假设已经可以做到这一点，并将所得的 $G_2$ 上的点称为 H(m)。

我们通过计算签名$\sigma=[s k] H(m)$来对消息进行签名， 即是用私钥乘上哈希点。

验证

给定消息 m、签名 σ 和公钥 pk，我们想要验证它是否是用与 pk 对应的 sk 签名的。

这就是要用到配对的地方了。当且仅当 $e\left(g_1, \sigma \right)=e(p k, H(m))$ 时，签名才有效。

我们可以用配对的性质来确认这一点：

$e(p k, H(m))=e\left([s k] g_1, H(m)\right)=e\left(g_1, H(m)\right)^{(s k)}=e\left(g_1,[s k] H(m)\right)=e\left(g_1, \sigma\right)$

聚合

BLS 签名的一个非常好的特性是它们是可以聚合的（另请参阅原始论文），因此我们只需要两个配对来验证 n 方签名的单个消息，或 n+1 个配对来验证由 n 方签名的 n 条不同消息，而不是你可能天真地期望需要的 2n 个配对。 配对的计算成本很高，因此这非常有吸引力。

可以聚合不同消息上的签名，或同一消息上的签名。 对于以太坊 2.0 我们聚合相同的消息，因此为了简洁起见这里只考虑这种情况。

要聚合签名，我们只需将它们对应的 $G2$ 点相加即可：$\sigma{a g g}=\sigma_1+\sigma_2+\ldots+\sigma_n$。 我们还聚合了对应的$G1$公钥点 $pk{agg}=pk_1+pk_2+ \ldots +pk_n$

现在配对的魔法意味着我们可以通过验证 $e\left(g1, \sigma{a g g}\right)=e\left(p k_{a g g}, H(m)\right)$ 来验证所有的签名，总共仅包含两个配对。

恶意密钥攻击

正如这里面的 1.1 节所述，当聚合同一消息的签名时，我们需要去注意可能的“恶意公钥攻击”（Rogue public key attack）。

假设你的公钥是 $p k_1$，而我有一个私钥 $s k_2$。 但我没有发布我的真实公钥，而是发布 $p k_2^{\prime}=\left[s k_2\right] g_1-p k_1$ （即我的真实公钥加上你的公钥的逆）。 我可以用我的私钥签名消息H(m) ，生成 $\sigma=\left[s k2 \right] H(m)$ 。 然后我发布声明，声称这是你和我共同签署的聚合签名，聚合公钥是$p k{a g g}=p k_1+p k_2^{\prime}$。

在验证时，我的声明就得到了验证：在你实际没有时看起来你参与了对消息的签名。： $e(g 1, \sigma)=e\left(g_1,\left[s k_2 \right] H(m ) \right)=e \left( \left[s k_2 \right] g_1, H(m) \right)=e \left(p k_1+p k_2^{\prime}, H(m)\right)$

对此的一种相对简单的防御措施（在以太坊 2.0 中使用的防御措施）是强制验证者注册与其所声称的公钥相对应的私钥的“拥有证明”。 这里你也可以看到，攻击者是没有与$p k_2^{\prime}$对应的$s k_2^{\prime}$的。 这可以简单地通过让验证者在注册时对其公钥签名来完成：如果签名可以使用该公钥进行验证，那么一切就都好。

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

G1和G2对调

对于数字签名的目的来说，$G_1$ 和 $G_2$ 群是可以对调的。 我们可以选择公钥作为 $G_1$ 的成员，签名作为 $G_2$ 的成员，反之亦可。

权衡点是执行速度和存储大小。$G_1$的点小且速度快； $G_2$ 的点大且速度慢。 BLS12-381 最初是为了实现 Zcash 而设计的，出于性能原因，他们选择使用 $G_1$ 来表示签名，使用 $G_2$ 来表示公钥。

大多数其他实现都是和Zcash“相反的”。 在以太坊 2.0 中，我们使用 $G_1$ 作为公钥：一方面，公钥聚合比签名聚合发生得更频繁； 另一方面，验证器的公钥需要以状态存储，因此保持较小的表示很重要。 那么签名自然就是 $G_2$ 的点。

点压缩

注意，有时扭操作也被称为点压缩 - 这与我们在这里讨论的完全不是一回事。

为了存储和传输椭圆曲线点，通常会删除 y 坐标。 这使得数据量减半。 对于 BLS12-381，$G_1$ 的点从 96 字节 ($2 \times 381$ 比特四舍五入到字节) 减少到了 48 字节，$G_2$ 的点从 192 字节减少到 96 字节。

任何椭圆曲线点都可以通过使用相关的曲线方程 E 或 $E^{\prime}$ 从 x 坐标来重新生成。 对于曲线上任何有效的 x 坐标，y 要么为零，要么具有两个互为负的可能值：对于 $G_1，y= \pm \sqrt{x^3+4}， G_2$ 也类似。

由于域元素为 381 位，而 48 字节为 384 位，因此我们有一些空闲位用于标记。 最重要的一个标志用于显示该点对应于哪个 y 值（正值或负值）。 另一位用于表示这是否是无穷远点（无穷远点有许多可能的表示）。 第三个标记位只是简单地指示这是压缩的还是未压缩的表示，尽管在实践中上下文应当会处理这点。

对于 $G_1$ 和 $G_2$ 来说，大约一半的 x 值不在曲线上。 在这种情况下，该点通常被解码为无穷远点。 但除非设置了无穷标志位——这种情况下我们不会尝试解码该点——这是一个错误条件。

标志位和xxx值如何编码的具体细节见这里。

子群成员检验

当处理任何来源未知的点时，无论它是压缩的还是未压缩的，很重要的一点是去检查它是否位于正确的子群中。 上面描述的点解压缩只是得到了曲线上的一个点； 我们不知道它是否位于正确的$G_1$或$G_2$中。

主要的问题似乎在于 $E\left(Fq\right)$ 和 $E^{\prime}\left(F{q^2}\right)$ 都包含小子群（你可以通过分解协因子来看到这点，例如使用此工具。） 正如这篇论文所讨论的，无意中使用这些小子群中的点可能会导致漏洞。

原则上子群检验很简单：只需将我们的点乘以 r 即可。 对于 $G_1$ 或 $G_2$ 中的点，结果为相应的无穷远点； 对于这些群之外的点，则不会。

不幸的是，这在实践中很慢，特别是对于 $G_2$，因为 r 太大了。 作为替代方案，有一些新技术利用自同态来执行更快的子群检验。

生成元

$G_1$ 和 $G_2$ 是素数阶循环群，因此任何点（除了单位元/无穷远点）都是生成元。 因此，选定生成元只是惯例上的考虑。

$G_1$ 和 $G_2$ 的生成元点在这里以十进制给出，相同的点在这里以十六进制给出。

这些是根据如下选定的：

$G_1$ 和 $G_2$的生成元是通过查找字典序最小的有效 x 坐标及其字典序最小的 y 坐标并通过协因子对其进行缩放来计算的，以便结果不是无穷远点。

根据我的计算，$h_1$ 和 $h_2$ 分别为相应群的协因子时，这使得 $G_1$ 生成元 $g_1=\left[h_1\right] p_1$，其中 $p_1$ 如下，

p1 = (0x04, 0x0a989badd40d6212b33cffc3f3763e9bc760f988c9926b26da9dd85e928483446346b8ed00e1de5d5ea93e354abe706c)

且$G_2$的生成元$g_2= \left[h_2 \right] p_2$，其中$p_2$如下，

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

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

最终指数

配对的计算分为两个部分：米勒循环（Miller loop）和最终指数（final exponentiation）。 二者都相当昂贵，但是可以用一个不错的技巧来减少最终指数的影响。

通常我们会计算两个完整的配对来进行签名验证，检查是否$e\left(g_1, \sigma\right)=e(p k, H(m))$。

如果我们将没有最终指数的配对表示为 $e^{\prime}(\cdot, \cdot)$，那么对某个 x，我们检查是否 $e^{\prime}\left(g_1, \sigma\right)^x=e^{\prime}(p k, H(m))^x$。 （ x 恰好为 $\left(q^k-1\right) / r$，这是很大的。）

我们知道如何在群 $G_T$ 中相乘，因此我们可以将其重新组织为检查是否 $\left(e^{\prime}\left(-g_1, \sigma\right) e^{\prime}(p k, H(m))\right)^x=1$。 （我们可以给出任意点的负点：配对魔法使得这相当于在 $G_T$ 中取逆。）

因此，为了验证签名，我们执行两个米勒循环，其中一个具有负输入值，将结果相乘，然后进行一次最终求幂。 如果结果是$G_T$ 中的单位元，那么我们的配对就相匹配。 这应该会带来有价值的加速。

哈希到曲线

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

哈希并检验

Eth2 中的最初实现是“哈希并检验”。 这很简单。

1. 将消息哈希到模 q 的整数
2. 检验曲线上是否存在具有该 x 坐标的点（实部 x，虚部 0 ）。 如果没有，则加 1 并重复。
3. 我们在曲线上有一个点了！ 乘以 $G_2$ 的协因子，将其转换为 $G_2$ 中的点。

尝试的点大约有一半会得到曲线上的点，所以这不是一个常数时间——我们不知道需要多少次迭代才能找到一个点。某种意义上说这并不重要：所有信息都是公开的，所以我们没有泄露任何东西。然而这确实开启了令人悲伤的攻击的可能性。攻击者可以预先计算需要很长时间才能找到一个点的消息（例如，百万条消息中有 1 条需要 20 次尝试），以大大减慢我们的速度。

简化的 SWU 映射

我们现在采用一种更好的方法，该方法这篇论文中进行了描述，并用在新的哈希到曲线的IETF 标准（草案）中。 和以前一样（但有点不同，要确保输出点符合均匀分布），我们首先通过哈希消息模qqq以创建一个域点。

现在使用一个特殊的映射（SWU 映射），会保证将该域点转换为椭圆曲线上的有效点。 由于技术原因，这并不是曲线 $E^{\prime}\left(F{q^2}\right)$本身，而是一条与其同源 的曲线（即具有相同数量的点）。 然后我们使用另一个映射（3-同源）将其转换到 $E^{\prime}\left(F{q^2}\right)$ 上的点。 最后，我们使用协因子清除最终得到 $G_2$ 中的点。

你可以去查看我基于Python参考代码实现的Java实现。

我的想法是，普遍采用这种方法可以增强区块链的互操作性。

协因子清除

我们讨论了乘以协因子作为将 E 或 $E^{\prime}$ 上的任意点分别变为 $G_1$ 或 $G_2$ 中的点的方法。 例如，在哈希到曲线中这很有用。

$G_2$ 的协因子很大，因此乘以它很慢。 然而，有更快的方法使用自同态（群到自身的映射）将曲线点映射到 $G_2$ 中。 新标准中包含了这一点（参见第 7 节）。

我们想要使用的自同台受到一个专利保护，但这个现在所有地方都已经过期了。

作为绕过专利的方法，该标准建议不去乘以 $G_2$ 的协因子，而是乘以一个有效协因子（有关值请参阅第 8.9.2 节），这会给出与自同态相同的结果。 有效协因子甚至要大于 $G_2$ 的协因子，但可以使用加法链作为优化来实现乘法。

我的想法是，既然专利已经过期，自同态可以作为有效协因子乘法的替代品。

扩张塔

还记得我们对域扩张 的讨论吗？ 实践中，相比直接实现大规模的 12 阶扩张，从较小的扩张来逐渐构造要更高效：扩张塔

对BLS12-381，域$F_{q^{12}}$ 实现为一个位于$F_q$ 的二阶扩张之上的，三阶扩张之上的，二阶扩张。

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

具体来说：

1. $F_{q^2}$ 构造为 $F_q(u) /\left(u^2-\beta\right)$ ，其中 $\beta=-1$.
2. $F{q^6}$ 构造为$F{q^2}(v) /\left(v^3-\xi\right)$ 其中 $\xi=u+1$.
3. $F{q^{12}}$ 构造为 $F{q^6}(w) /\left(w^2-\gamma\right)$ 其中 $\gamma=v$

根据之前的理解来进行解释：

1. 将 $F_{q^2}$ 域的元素写为 u 中的一阶多项式，系数来自 $F_q$ ，并应用约简规则 $u^2+1=0$，该规则在$F_q$中是不可约的。

   • $F_{q^2}$ 的元素看起来像 $a_0+a_1 u$，其中 $a_j \in F_q$。

2. 将 $F{q^6}$ 域的元素写为 v 中的二阶多项式，其中的系数来自我们刚刚构造的 $F{q^2}$ 域，并应用约简规则 $v^ 3-(u+1)=0$，该规则在$F_{q^2}$中不可约。

   • $F_{q^6}$的元素看起来像 $b_0+b_1 v+b_2 v^2$，其中 $bj \in F{q^2}$。

3. 将 $F{q^{12}}$ 域的元素写为 w 中的一阶多项式，其中系数来自我们刚刚构造的 $F{q^6}$ 域，并应用约简规则 $w^2-v=0$，该规则在$F_{q^6}$中不可约。

   • $F_{q^{12}}$ 的元素看起来像 $c_0+c_1 w$，其中 $cj \in F{q^6}$。

这种塔式扩张可以取代直接扩张作为配对的基础，并且如果实现得当，可以在乘以$F_{q^{12}}$点时节省大量的算术量。有关这种优势的完整讨论，请参阅“Pairings for Beginners”的第 7.3 节。

坐标系

求域元素的逆（即除法）是一项昂贵的操作，因此椭圆曲线算术的实现里要尽可能避免该操作。 选择正确的坐标系来表示点会有所帮助。

仿射坐标

仿射坐标是点的传统表示形式，就是坐标对(x,y)，其中x和y满足曲线方程。 这是我们在存储和传输点时所通常使用的。

然而，在实际处理点时，这并不总是最有效的形式，据我所知在BLS12-381中还有另外两种方案。

基本思想是使用概念分数来表示坐标，从而减少实际所需除法运算的数量。 为此，引入了第三个坐标，使用(X, Y, Z) 作为点的内部表示。 就像我们熟悉的分数一样，同一个值有多种表示形式，都对应于一个实际值 （$\frac{1}{2}, \frac{3}{6}, \frac{197}{394 } $都是相同的数字）。

BLS12-381 中使用的两个系统是标准射影坐标和雅可比坐标。

标准射影坐标

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

这些也称为齐次射影坐标，因为曲线方程采用齐次形式 $Y^2 Z=X^3+4 Z^3$。 点在(X, Y, Z) 空间中变成了通过原点的直线，仿射点是该线与平面 Z=1 的交点。 “Pairing for Beginners” 中的图 2.10 给出了一个很好的说明。

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

雅可比坐标

另一种不同类型的射影坐标是雅可比坐标。 此方案中，雅可比点 (X, Y, Z) 代表仿射点$\left(X / Z^2, Y / Z^3\right)$。 曲线方程变为$Y^2=X^3+4 Z^6$

示例代码中的常数时间哈希到曲线在底层使用了雅可比坐标。

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

进一步阅读资源

上面已经有了很多参考链接，这里就不重复了。 我只会挑一些特别有用或有趣的。

有用的参考资料：

• 原始BLS12-381的发布
• 参数和序列化的简洁描述
• IETF 标准草案
• 一个上述内容的太长不看版：给大忙人的BLS

一般来说，配对库的实现往往是高度优化的且/或非常通用的（支持多曲线），这使得很难去学。 Paul Miller 使用 JavaScript/TypeScript 编写的 Noble BLS12-381 库绝对是最容易理解的库之一。

最后，还有一些有趣的读物：

• 这份关于 Curve9769 的全新白皮书与 BLS12-381 没有直接关系，但它是对设计和实现椭圆曲线（此例中不是配对友好的）的苦与乐写得很好的精彩探索。
• 配对没有死，只是在休息。 一个很好的概述介绍。 有一些 BLS12-381 的东西。

就这样吧，朋友们拜拜！

本文首发于：https://cryptography.land/2023/07/01/bls12381-restofus