BLS Curves (BLS12-381) and BLS Signatures

Table of Contents

1. BLS12-381 简介

椭圆曲线 BLS12-381 由 Zcash 的工程师 Sean Bowe 于 2017 年设计。

椭圆曲线的“Weierstrass normal”形式可以用下面式子表示:
y2=x3+ax+b

对于 BLS12-381,其参数(摘自 https://github.com/J08nY/std-curves/blob/data/bls/curves.json )如下:

p(field modulus)=0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaaba=0x00b=0x04xG(generator)=0x17f1d3a73197d7942695638c4fa9ac0fc3688c4f9774b905a14e3a3f171bac586c55e83ff97a1aeffb3af00adb22c6bbyG(generator)=0x08b3f481e3aaa0f1a09e30ed741d8ae4fcf5e095d5d00af600db18cb2c04b3edd03cc744a2888ae40caa232946c5e7e1n(order)=0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001h(cofactor)=0x396c8c005555e1568c00aaab0000aaab

BLS12-381 也常用其它形式表示,设参数 z=0xd201000000010000 ,则有:
p=(z1)2(z4z2+1)/3+z=0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaabn=z4z2+1=0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001h1=(z1)2/3=0x396c8c005555e1568c00aaab0000aaabh2=(z84z7+5z64z4+6z34z24z+13)/9=0x5d543a95414e7f1091d50792876a202cd91de4547085abaa68a205b2e5a7ddfa628f1cb4d9e82ef21537e293a6691ae1616ec6e786f0c70cf1c38e31c7238e5 h1,h2 分别是 G1,G2 的 cofactor,可参见节 1.31.4

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 的参数中,模数 p=0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab 占用了 381 个比特位, 这就是 BLS12-381 中 381 的由来。

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

1.2. Pairing-Friendly Curves

先介绍一下 Pairing 的概念。

一个 Pairing(也称为 Bilinear Map)是一个映射(分别从椭圆曲线 G1G2 上取一点,然后映射到乘法群 (GT,) 上): e:G1×G2GT 且需要满足下面条件:

  1. 双线性(Bilinearity),即 e(P,Q+R)=e(P,Q)e(P,R)e(P+S,Q)=e(P,Q)e(S,Q) 由上面两个式子,可推出 e(aP,bQ)=e(P,Q)ab 这些式子中,大写字母 P,S 椭圆曲线 G1 上的点, Q,R 是椭圆曲线 G2 上的点,而小写字母 a,b 是指整数。
  2. 非退化性(Non-degeneracy): TG2,e(S,T)=1 if and only if S=O. Similarly, SG1,e(S,T)=1 if and only if T=O. 也就是说 G1G2 不能全都映射到 GT 的单位元,我们对这种情况不感兴趣。
  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。

1.3. BLS12-381 的 G1

BLS12-381 中曲线 G1 比较简单,就是定义在有限素域 Fp 上满足 y2=x3+4 的点,可记为 E1(Fp)E1(Fp)={(x,y):x,yFpsatisfyy2=x3+4}{O} 其中素数 p 为:

p = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab

曲线 G1 中点的个数为 #E1(Fp)=h1n ,其中 h1,n 分别为:

h_1 = 0x396c8c005555e1568c00aaab0000aaab
n = 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001

曲线 G1 的 Generator 为:

x = 0x17f1d3a73197d7942695638c4fa9ac0fc3688c4f9774b905a14e3a3f171bac586c55e83ff97a1aeffb3af00adb22c6bb
y = 0x08b3f481e3aaa0f1a09e30ed741d8ae4fcf5e095d5d00af600db18cb2c04b3edd03cc744a2888ae40caa232946c5e7e1

1.4. BLS12-381 的 G2

BLS12-381 中曲线 G2 复杂一些,它是定义在域 Fp2 上满足 y2=x3+4(u+1) 的点,可记为 E2(Fp2)E2(Fp2)={(x,y):x,yFp2satisfyy2=x3+4(u+1)}{O} 上面写到的域 Fp2u 分别是什么呢?

Fp2 是域 Fp 的二次扩张域,可以类比为复数域是对实数域的扩展,通过引入一个符号 u (它满足 u2+1=0 ,它类似于复数里的 i=1 ),来让其继续满足原来 Fp 域上的模 p 的加减乘除四则运算。

Fp2 中的元素可以使用 a0+a1u 来表示,或者表示为 (a0,a1)

Fp2 上的加法运算定义如下: (a,b)+(c,d)=a+bu+c+du=(a+c)+(b+d)u=(a+c,b+d)

Fp2 上的乘法运算定义如下: (a,b)×(c,d)=ac+(ad+bc)u+bdu2=(acbd)+(ad+bc)u=(acbd,ad+bc)

曲线 G2 中点的个数为 #E2(Fp2)=h2n ,其中 h2,n 分别为:

h_2 = 0x5d543a95414e7f1091d50792876a202cd91de4547085abaa68a205b2e5a7ddfa628f1cb4d9e82ef21537e293a6691ae1616ec6e786f0c70cf1c38e31c7238e5
n = 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001

曲线 G2 的 Generator 为:

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

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

一般地,对于 Fp ,它的扩域 Fpk 中的元素可以使用 a0+a1u++ak1uk1 来表示,或者表示为 (a0,a1,,ak1)

1.5. BLS12-381 的 Pairing

BLS12-381 的 Pairing 是从椭圆曲线群 G1 中取一个点 P ,即 PG1E1(Fp) ,从椭圆曲线群 G2 中取另一个点 Q ,即 QG2E2(Fp2) ,然后映射到群 GTFp12 中的元素。需要说明的是 GT 是个乘法群,它并不是一个椭圆曲线群。

这里不介绍这个 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,记私钥为整数 k ,则公钥为 P=kG (这里 G 是曲线 G1 的 Generator);对消息 m ,将其映射到曲线 G2 上的一个点,记为 H ,消息 m 的签名数据为 S=kH 。显然,公钥 P 是曲线 G1 上的点,而签名数据 S 则是另一曲线 G2 上的点。

要验证签名时,验证 e(P,H)=e(G,S) 是否成立即可(这里的 e 就是 Pairing 运算)。证明如下: e(P,H)=e(kG,H)=e(G,H)k=e(G,kH)=e(G,S)

2.1.1. 和 ECDSA 比较

1 总结了 BLS 和 ECDSA 从公钥大小和签名大小的维度进行的比较。

Table 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

假设有 n 个人,他们的私钥分别为 k1,,kn ,对应的公钥分别为 P1=k1G,,Pn=knG ,他们分别生成了 n 个签名 S1=k1H,,Sn=knH

把聚合公钥记为 PP1++Pn ,而聚合签名 SS1++Sn ,有 e(P,H)=e(P1++Pn,H)=e((k1++kn)G,H)=e(G,H)(k1++kn)=e(G,(k1++kn)H)=e(G,S1++Sn)=(G,S) 通过使用聚合公钥对聚合签名进行一次签名验证,就可以验证 n 个签名是否正确。

2.3. BLS 签名的优缺点

BLS 签名的优点:

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

BLS 签名的缺点:

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

3. 参考

Author: cig01

Created: <2020-08-03 Mon>

Last updated: <2023-01-12 Thu>

Creator: Emacs 27.1 (Org mode 9.4)