BLS Curves (BLS12-381) and BLS Signatures

BLS12-381 椭圆曲线中的 BLS 是三个人名 Barreto-Lynn-Scott 的简写，来源于 Paulo S. L. M. Barreto, Ben Lynn, and Michael Scott 在 2002 年发表的论文 Constructing Elliptic Curves with Prescribed Embedding Degrees ；而 BLS12-381 名称中的 12 指的是该椭圆曲线的“Embedding Degree”。

BLS12-381 的参数中，模数 \({\scriptsize p = \texttt{0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab}}\) 占用了 381 个比特位， 这就是 BLS12-381 中 381 的由来。

BLS12-381 是一种 Pairing-Friendly 曲线，后文将介绍。

先介绍一下 Pairing 的概念。

一个 Pairing（也称为 Bilinear Map）是一个映射（分别从椭圆曲线 \(G_1\) 和 \(G_2\) 上取一点，然后映射到乘法群 \((G_T, \cdot)\) 上）： \[e: G_1 \times G_2 \to G_T\] 且需要满足下面条件：

1. 双线性（Bilinearity），即 \[\begin{aligned} e(P, Q+R) = e(P, Q) \cdot e(P, R) \\ e(P + S, Q) = e(P, Q) \cdot e(S, Q)\end{aligned}\] 由上面两个式子，可推出 \[e(aP, bQ) = e(P,Q)^{ab}\] 这些式子中，大写字母 \(P,S\) 椭圆曲线 \(G_1\) 上的点， \(Q,R\) 是椭圆曲线 \(G_2\) 上的点，而小写字母 \(a,b\) 是指整数。
   
2. 非退化性（Non-degeneracy）: \(\forall T \in G_2, e(S, T) = 1\) if and only if \(S = \mathcal{O}\). Similarly, \(\forall S \in G_1, e(S, T) = 1\) if and only if \(T = \mathcal{O}\). 也就是说 \(G_1\) 和 \(G_2\) 不能全都映射到 \(G_T\) 的单位元，我们对这种情况不感兴趣。
   
3. 可计算性（Computability）: 存在有效算法可以计算 \(e\) 。
   

并不是在所有椭圆曲线上都可以实现上面的 Pairing，我们把 能实现 Pairing 的椭圆曲线，称为 Pairing-Friendly Curves。Pairing-Friendly Curves 主要有两类：Barreto-Naehrig Curve（简称为 BN 曲线）和 Barreto-Lynn-Scott Curves（简称为 BLS 曲线）， 参考：https://www.ietf.org/archive/id/draft-irtf-cfrg-pairing-friendly-curves-08.html

为了进行有效地计算，Pairing-Friendly 曲线的“Embedding Degree”不能太大，如 BLS12-381 曲线的“Embedding Degree”为 12。

BLS12-381 中曲线 \(G_1\) 比较简单，就是定义在有限素域 \(\mathbb{F}_{p}\) 上满足 \(y^2 = x^3 + 4\) 的点，可记为 \(E_1(\mathbb{F}_{p})\) ： \[E_1(\mathbb{F}_{p}) = \{(x, y): x,y \in \mathbb{F}_{p} \;\text{satisfy}\; y^2 = x^3 + 4 \} \cup \{ \mathcal{O} \}\] 其中素数 \(p\) 为：

p = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab

曲线 \(G_1\) 中点的个数为 \(\#E_1(\mathbb{F}_{p}) = h_1 \cdot n\) ，其中 \(h_1,n\) 分别为：

h_1 = 0x396c8c005555e1568c00aaab0000aaab
n = 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001

曲线 \(G_1\) 的 Generator 为：

x = 0x17f1d3a73197d7942695638c4fa9ac0fc3688c4f9774b905a14e3a3f171bac586c55e83ff97a1aeffb3af00adb22c6bb
y = 0x08b3f481e3aaa0f1a09e30ed741d8ae4fcf5e095d5d00af600db18cb2c04b3edd03cc744a2888ae40caa232946c5e7e1

BLS12-381 中曲线 \(G_2\) 复杂一些，它是定义在域 \(\mathbb{F}_{p^2}\) 上满足 \(y^2 = x^3 + 4(u + 1)\) 的点，可记为 \(E_2(\mathbb{F}_{p^2})\) ： \[E_2(\mathbb{F}_{p^2}) = \{(x, y): x,y \in \mathbb{F}_{p^2} \;\text{satisfy}\; y^2 = x^3 + 4(u + 1) \} \cup \{ \mathcal{O} \}\] 上面写到的域 \(\mathbb{F}_{p^2}\) 和 \(u\) 分别是什么呢？

域 \(\mathbb{F}_{p^2}\) 是域 \(\mathbb{F}_{p}\) 的二次扩张域，可以类比为复数域是对实数域的扩展，通过引入一个符号 \(u\) （它满足 \(u^2+1=0\) ，它类似于复数里的 \(i=\sqrt{-1}\) ），来让其继续满足原来 \(\mathbb{F}_{p}\) 域上的模 \(p\) 的加减乘除四则运算。

域 \(\mathbb{F}_{p^2}\) 中的元素可以使用 \(a_0 + a_1 u\) 来表示，或者表示为 \((a_0, a_1)\) 。

域 \(\mathbb{F}_{p^2}\) 上的加法运算定义如下： \[(a,b) + (c,d) = a + bu + c + du = (a+c) + (b+d)u = (a+c, b+d)\]

域 \(\mathbb{F}_{p^2}\) 上的乘法运算定义如下： \[(a,b) \times (c,d) = ac + (ad + bc)u + bdu^2 = (ac-bd) + (ad+bc)u = (ac-bd, ad+bc)\]

曲线 \(G_2\) 中点的个数为 \(\#E_2(\mathbb{F}_{p^2}) = h_2 \cdot n\) ，其中 \(h_2,n\) 分别为：

h_2 = 0x5d543a95414e7f1091d50792876a202cd91de4547085abaa68a205b2e5a7ddfa628f1cb4d9e82ef21537e293a6691ae1616ec6e786f0c70cf1c38e31c7238e5
n = 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001

曲线 \(G_2\) 的 Generator 为：

x = 0x024AA2B2F08F0A91260805272DC51051C6E47AD4FA403B02B4510B647AE3D1770BAC0326A805BBEFD48056C8C121BDB8 + 0x13E02B6052719F607DACD3A088274F65596BD0D09920B61AB5DA61BBDC7F5049334CF11213945D57E5AC7D055D042B7E u
y = 0x0CE5D527727D6E118CC9CDC6DA2E351AADFD9BAA8CBDD3A76D429A695160D12C923AC9CC3BACA289E193548608B82801 + 0x0606C4A02EA734CC32ACD2B02BC28B99CB3E287E85A763AF267492AB572E99AB3F370D275CEC1DA1AAA9075FF05F79BE u

这些参数可以通过 Sage script 计算出来，可参考：https://github.com/relic-toolkit/relic/issues/55

一般地，对于 \(\mathbb{F}_{p}\) ，它的扩域 \(\mathbb{F}_{p^k}\) 中的元素可以使用 \(a_0 + a_1 u + \cdots + a_{k-1} u^{k-1}\) 来表示，或者表示为 \((a_0, a_1, \cdots, a_{k-1})\) 。

BLS12-381 的 Pairing 是从椭圆曲线群 \(G_1\) 中取一个点 \(P\) ，即 \(P \in G_1 \subset E_1(\mathbb{F}_{p})\) ，从椭圆曲线群 \(G_2\) 中取另一个点 \(Q\) ，即 \(Q \in G_2 \subset E_2(\mathbb{F}_{p^2})\) ，然后映射到群 \(G_T \subset \mathbb{F}_{p^{12}}\) 中的元素。需要说明的是 \(G_T\) 是个乘法群，它并不是一个椭圆曲线群。

这里不介绍这个 Pairing 的具体操作。

BLS 签名利用了 Pairing，记私钥为整数 \(k\) ，则公钥为 \(P=kG\) （这里 \(G\) 是曲线 \(G_1\) 的 Generator）；对消息 \(m\) ，将其映射到曲线 \(G_2\) 上的一个点，记为 \(H\) ，消息 \(m\) 的签名数据为 \(S=kH\) 。显然，公钥 \(P\) 是曲线 \(G_1\) 上的点，而签名数据 \(S\) 则是另一曲线 \(G_2\) 上的点。

要验证签名时，验证 \(e(P,H)=e(G,S)\) 是否成立即可（这里的 \(e\) 就是 Pairing 运算）。证明如下： \[e(P,H) = e(kG,H) = e(G, H)^k = e(G, kH) = e(G,S)\]

我们可以把多个 BLS 签名聚合到一起，只用一次签名验证即可。参考论文：Aggregate and Verifiably Encrypted Signatures from Bilinear Maps

假设有 \(n\) 个人，他们的私钥分别为 \(k_1,\cdots,k_n\) ，对应的公钥分别为 \(P_1=k_1 G,\cdots,P_n=k_n G\) ，他们分别生成了 \(n\) 个签名 \(S_1=k_1 H,\cdots,S_n=k_n H\) 。

把聚合公钥记为 \(P \triangleq P_1+\cdots+P_n\) ，而聚合签名 \(S \triangleq S_1+\cdots+S_n\) ，有 \[\begin{aligned} e(P,H) &= e(P_1+\cdots+P_n, H) \\ &= e((k_1+\cdots+k_n)G, H) \\ &= e(G,H)^{(k_1+\cdots+k_n)} \\ &= e(G, (k_1+\cdots+k_n)H) \\ &= e(G, S_1+\cdots+S_n) \\ &= (G, S) \end{aligned}\] 通过使用聚合公钥对聚合签名进行一次签名验证，就可以验证 \(n\) 个签名是否正确。

BLS 签名的优点：

1. 签名数据比较小；
   
2. 支持签名聚合；
   
3. 签名过程中不依赖于随机数，签名结果是确定的。
   

BLS 签名的缺点：

1. 签名验证的效率不高。在 https://lists.linuxfoundation.org/pipermail/bitcoin-ml/2018-April/000701.html 中有个测试例子：secp256k1 进行签名验证需要 75 us，而 BLS12-381 进行签名验证需要 7ms。