BLS Curves (BLS12-381) and BLS Signatures
Table of Contents
1. BLS12-381 简介
椭圆曲线 BLS12-381 由 Zcash 的工程师 Sean Bowe 于 2017 年设计。
椭圆曲线的“Weierstrass normal”形式可以用下面式子表示:
对于 BLS12-381,其参数(摘自 https://github.com/J08nY/std-curves/blob/data/bls/curves.json )如下:
BLS12-381 也常用其它形式表示,设参数
1.1. BLS12-381 名称的由来
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 的参数中,模数
BLS12-381 是一种 Pairing-Friendly 曲线,后文将介绍。
1.2. Pairing-Friendly Curves
先介绍一下 Pairing 的概念。
一个 Pairing(也称为 Bilinear Map)是一个映射(分别从椭圆曲线
- 双线性(Bilinearity),即
由上面两个式子,可推出 这些式子中,大写字母 椭圆曲线 上的点, 是椭圆曲线 上的点,而小写字母 是指整数。 - 非退化性(Non-degeneracy):
if and only if . Similarly, if and only if . 也就是说 和 不能全都映射到 的单位元,我们对这种情况不感兴趣。 - 可计算性(Computability): 存在有效算法可以计算
。
并不是在所有椭圆曲线上都可以实现上面的 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。
1.3. BLS12-381 的
BLS12-381 中曲线
p = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
曲线
h_1 = 0x396c8c005555e1568c00aaab0000aaab n = 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001
曲线
x = 0x17f1d3a73197d7942695638c4fa9ac0fc3688c4f9774b905a14e3a3f171bac586c55e83ff97a1aeffb3af00adb22c6bb y = 0x08b3f481e3aaa0f1a09e30ed741d8ae4fcf5e095d5d00af600db18cb2c04b3edd03cc744a2888ae40caa232946c5e7e1
1.4. BLS12-381 的
BLS12-381 中曲线
域
域
域
域
曲线
h_2 = 0x5d543a95414e7f1091d50792876a202cd91de4547085abaa68a205b2e5a7ddfa628f1cb4d9e82ef21537e293a6691ae1616ec6e786f0c70cf1c38e31c7238e5 n = 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001
曲线
x = 0x024AA2B2F08F0A91260805272DC51051C6E47AD4FA403B02B4510B647AE3D1770BAC0326A805BBEFD48056C8C121BDB8 + 0x13E02B6052719F607DACD3A088274F65596BD0D09920B61AB5DA61BBDC7F5049334CF11213945D57E5AC7D055D042B7E u y = 0x0CE5D527727D6E118CC9CDC6DA2E351AADFD9BAA8CBDD3A76D429A695160D12C923AC9CC3BACA289E193548608B82801 + 0x0606C4A02EA734CC32ACD2B02BC28B99CB3E287E85A763AF267492AB572E99AB3F370D275CEC1DA1AAA9075FF05F79BE u
这些参数可以通过 Sage script 计算出来,可参考:https://github.com/relic-toolkit/relic/issues/55
一般地,对于
1.5. BLS12-381 的 Pairing
BLS12-381 的 Pairing 是从椭圆曲线群
这里不介绍这个 Pairing 的具体操作。
2. BLS Signatures
2001 年,Dan Boneh, Ben Lynn, Hovav Shacham 在论文 Short signatures from the Weil pairing 中提出了“Short Signatures”方案,被称为 BLS 签名方案,这种方案支持签名聚合,且生成的签名数据比较小, 如果签名数据需要在带宽受限的网络中传输,则这种签名方案具有优势。
需要说明的是,“BLS 签名方案”于 2001 年提出,比 2002 年提出的“BLS 曲线”要早,而且这两个缩写中只有 L 是同一个人,而缩写 B 和 S 分别是不同的人:
- BLS Signatures: Dan Boneh, Ben Lynn, Hovav Shacham
- BLS Curves: Paulo S. L. M. Barreto, Ben Lynn, Michael Scott
注: BLS 曲线可以和 BLS 签名方案很好地配合使用。不过,BLS 签名方案也可以使用除 BLS 曲线外的其它曲线;而 BLS 曲线也有其它的用途。
2.1. BLS 签名
BLS 签名利用了 Pairing,记私钥为整数
要验证签名时,验证
2.1.1. 和 ECDSA 比较
表 1 总结了 BLS 和 ECDSA 从公钥大小和签名大小的维度进行的比较。
公钥大小 | 签名大小 | |
---|---|---|
ECDSA | 33 bytes | 64 bytes |
BLS12-381 | 48 bytes | 96 bytes |
BLS12-381 | 96 bytes | 48 bytes |
注:其它资料一般都是说 BLS12-381 的公钥为 48 bytes,签名为 96 bytes。由于对 BLS 来说,公钥和签名分别是两个曲线上的点,它们是可以互换的,所以有了表 1 的最后一行数据。
参考:https://www.ietf.org/archive/id/draft-irtf-cfrg-bls-signature-05.html#name-comparison-with-ecdsa
2.2. Aggregation(签名聚合)
我们可以把多个 BLS 签名聚合到一起,只用一次签名验证即可。参考论文:Aggregate and Verifiably Encrypted Signatures from Bilinear Maps
假设有
把聚合公钥记为
2.3. BLS 签名的优缺点
BLS 签名的优点:
- 签名数据比较小;
- 支持签名聚合;
- 签名过程中不依赖于随机数,签名结果是确定的。
BLS 签名的缺点:
- 签名验证的效率不高。在 https://lists.linuxfoundation.org/pipermail/bitcoin-ml/2018-April/000701.html 中有个测试例子:secp256k1 进行签名验证需要 75 us,而 BLS12-381 进行签名验证需要 7ms。