Bls 签名和基于 bls 签名的门限签名——密码学入门系列(二)


#1

在区块链的整个体系中大量使用了密码学算法,密码学是保证区块链安全的基石,而区块链的广泛应用也推进了密码学的发展。2003 年 Boneh 和 Franklin 提出了身份基加密,从此基于双线性映射的密码学算法走向了人们的视野,并且成为了密码学新兴的研究方向。BLS 签名算法就是基于双线性映射构造的。

继上一期 密码学入门系列(一)后,马宇峰老师又推出了密码学入门系列第二期,今天马老师要带我们学习 BLS 签名和基于 BLS 签名的门限签名,阅读本文将带领你步入基于双线性映射的密码学算法的大门。

2003 年 Boneh 和 Franklin 提出了身份基加密[1],从此基于双线性映射(也称为 Pairing 运算 / 对运算)的密码学算法走向了人们的视野,并且成为密码学新兴的研究方向。今天我们要学习的 BLS 签名算法[2]就是基于双线性映射构造的,在给出具体的签名算法之前,我们需要学习一下什么是双线性映射。

双线性映射

定义 1 双线性映射: 设群 G1,G2,GT 是阶为素数 p 的乘法循环群,如果映射 e: G1 ×G2→ GT 满足以下性质,就称映射 e 为双线性映射:

(1) 双线性:任意元素 u ∈ G1,v∈ G2 ,任意元素 a,b∈ Zp (Zp 指的是{0,1,…,p-1}),都有 e(ua,vb)=e(u,v)ab ;

(2) 非退化性:存在元素 m∈ G1,n∈ G2 使得 e(m,n)≠1;

(3) 可计算性:任意元素 u,v∈ G1,存在有效算法计算 e(u,v)。

可能有些读者还不知道群,循环群,乘法循环群,群的阶是什么意思,因此我下面介绍一下这些术语的定义,已经熟悉这些知识的读者可以直接跳过定义 2,定义 3 直接阅读后续签名算法部分。

定义 2 群 [3]:群是一个集合 G 和其上的二元运算,满足以下条件:

(1)封闭性:对于任意 x,y∈G,有

(2)结合率:对于任意的 x,y,z∈G,恒有

(3)存在单位元:存在 e∈G,对于 G 中任意元素 x,满足,e称为单位元,也称为幺元;

(4)存在逆元:对于任意 x∈G,都存在一个元素 h∈G,满足,这样的元素 h 称为 x 的逆元。

当二元运算为已知时,简单的将集合 G 称为群。

定义 3 循环群 [3]:若群 G 中存在元素 g 满足对群 G 中任意元素 f,都存在整数 t 使得 ,则群 G 是循环群,g 是群 G 的 生成元 ,若群 G 的阶为素数,则 G 中每一个非单位元元素都是生成元。群元素的个数称为 。二元运算为模乘法的循环群,称为 乘法循环群

有了以上知识,应该可以理解 BLS 签名算法了,这个算法包括:初始化,密钥生成,签名,验证,四个部分,具体构造如下:

1.初始化 G1, G2 是阶为 p 的乘法循环群,生成元分别是 g1,g2,e 是双线性映射:G1 * G2 -> GT,安全 hash 函数:h:{0,1}*-> G1,公开参数是(G1, G2, GT, e, g1, g2,p,h)

2.密钥生成

选择一个随机数 x∈ZP,计算 ,私钥 SK=x,公钥 PK=v

3.签名

对消息 M 签名

σ = h(M)x

4.验证

e(σ, g2)? = e(h(M), v)

门限签名的通俗理解是:在一个签名者群体中,有超过 t(门限)个签名者对一条消息进行签名就可以得到这个群体对这条消息的签名,这个签名是唯一的(即超过 t 个签名者的不同子集生成的签名是一样的)且任何人都可以验证。由门限签名的性质可知,少于 t 个签名者的群体是得不到群体签名的,因此在一个由 n 个节点组成的区块链系统中当恶意节点的数量小于 t 时,可以利用门限签名来做 可验证随机函数(Verifiable Random Functions)。

随机数在共识领域有着重要的应用, 本质上讲,共识问题就是随机选择出块人问题 ,并且这个随机性不能被提前预测,不能被操纵,并且需要可以被全网验证。PoW 方案通过计算满足一定条件的 Hash 来选取出块人,算力大的节点被选中的概率高,为了获取记账权,需要投入更多的算力。为了解决 PoW 方案算力浪费的问题,PoS 方案根据每个节点所拥有份额多少来随机选择出块人,份额越多的节点被选中的概率越大,门限签名可以作为 PoS 方案的随机性来源。

拉格朗日差值法

现在可以在 BLS 签名方案的基础上通过使 Shamir 秘密分享方法[4]来构造门限签名算法,为了便于理解,在给出具体构造算法之前,我先介绍一下拉格朗日差值法,这是 Shamir 秘密分享方法的核心。

已知一条 n-1 次曲线上的 n 个点 (x1,y1), (x2,y2), …, (xn,yn) , 我们可以使用拉格朗日插值法来恢复这条曲线方程,具体如下:

现在改变一下问题,想要实现 t-of-n 的秘密分享。t=3,n=4 时,先任意选择一条 t-1=2 次曲线,以这条曲线在 x=0 处的值作为秘密。然后任意取出曲线上的n=4个点 (1,2),(2,5),(3,10),(4,17) 后,任选其中三个点后恢复出来 t-1=2 次曲线是一样的。因此,我可以将这四个点(横坐标分别是 1、2、3、4)发送给四个不同的人,这样就是一个 3-of-4 的秘密分享了。

有了以上知识,应该可以理解基于 BLS 签名的门限签名算法,这个算法包括:初始化,密钥生成,签名,验证,四个部分,具体构造如下:

1.初始化

G1, G2 是阶为 p 的乘法循环群,生成元分别是 g1, g2 , e 是双线性映射:G1 * G2 -> GT,安全 hash 函数:h:{0,1} -> G1,公开参数是(G1, G2, GT, e, g1, g2, p, h)

2.密钥生成

这步由密钥生成中心完成
a.密钥生成中心选择随机数 x ∈ ZP,计算算,系统主私钥 MSK = x,系统主公钥 MPK = v

b.随机选择一个 ZP 上的 t-1 阶多项式 P, 满足 P(0)=x, 计算 xi = P(i) ,![](https://mmbiz.qpic.cn/mmbiz_png/l3BFoeeEDWBncz4ln74KcPjiczbQxvngwpBOXoEWhZyRyvyNFbLIdX0mAXSI9Bww3F1XzuFZZrhThXfxubIetJQ/640?wx_fmt=png),签名者 ui 的私钥为 xi, 公钥为 vi 

c.公开 MPK 及所有用户的公钥 ![](https://mmbiz.qpic.cn/mmbiz_png/l3BFoeeEDWBncz4ln74KcPjiczbQxvngwgSiaKX1C7t7lAjYXBSibJSG5TNOrwibsKBCUzicQ1ib0ic46icHnl5t0teq6g/640?wx_fmt=png)

3.签名

设对消息 M 签名
a.用户 ui 计算自己的签名,然后将 σi 广播出去

b.用户 ui 收到了来自 uj 的签名 σj 后,首先验证签名的正确性:![](https://mmbiz.qpic.cn/mmbiz_png/l3BFoeeEDWBncz4ln74KcPjiczbQxvngwT5N2icAP1ocY9TPQ7QzNUC2xSX4KeN8SFfiaV3cFPMyZFEgXuMcgdib8A/640?wx_fmt=png),如果签名正确则记录下来

c.待收集到 t 个不同用户的正确签名后,用户计算完整的签名:

由拉格朗日差值公式可知,任意 t 个用户所产生的完整签名相同

4.验证

e(σ, g2)? = e(h(M), MPK)

然而这个算法由于使用了密钥生成中心这样一个中心化机构,因此并不能直接用来做可验证随机函数,我们需要构造一个分布式密钥生成的门限签名算法,具体算法我会在下篇文章给出,感兴趣的读者可以先想想怎么做。(Tips:多个多项式之和作为秘密多项式)

ref

[1] Boneh D, Franklin M. Identity based encryption from the Weil pairing[J]. Siam Journal on Computing, 2003, 32(3):213-229.

[2] Dan B, Lynn B, Shacham H. Short Signatures from the Weil Pairing[C]// International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, Heidelberg, 2001:514-532.

[3] 陈恭亮. 信息安全数学基础[M]. 清华 学出版社, 2004.

[4] Shamir A. How to share a secret[J]. Communications of the ACM, 1979, 22(11): 612-613.


#2

如果要利用门限签名做 VRF,那么并不仅仅是恶意节点数量小于 t 就可以了,恶意节点数量还有一个 upper bound。因为如果 n-t 的值小于能够容忍的恶意节点数量(注意此时恶意节点数量可能并没有超过 t ),那么恶意节点可以拒绝服务,然后影响 VRF 的结果。


#3

并不是,Tendermint 就没有随机选择出块人,但是也不能说 Tendermint 就不是一个解决共识问题的算法。


#4

文中描述的方案是基于原本的 BLS 签名(也就是参考文献的第二个)直接构造的门限方案。但是这个方案有一个缺陷,那就是在 plain public key model 之下是不安全的。以 2-of-2 这种最简单的情况为例,如果攻击者可以选择注册的公钥(在分布式密钥生成中看起来就是这样的),那么他可以选择 {pk}_2 := g_2^\beta \cdot ({pk}_1)^{-1} \in \mathbb{G}_2{pk}_1 来自于某个诚实用户 P_2\beta \xleftarrow{R} \mathbb{Z}_q 由攻击者选择。这样,攻击者可以声称他和 P_2 对同一个消息 m \in \mathcal{M} 进行了签名,尽管事实上,用户 P_2 并没有对该消息签名。因为签名 \sigma = H(m)^\beta 可以被验证为是由 {pk}_1{pk}_2 签名的:
e(g_2, \sigma) = e\big(g_2, H(m)^\beta \big) = e\big(g_2^\beta, H(m)\big) = e\big({pk}_1 \cdot {pk}_2, H(m)\big).
而这种最简单的情况是可以被很容易推广到 t-of-n 的情况的。当然,可以让每一个用户对自己的私钥做 proof of knowledge。但是对于区块链的场景,这样的开销太大,不是很现实,我们有更好的方案:参见 Dan Boneh et al. Compact Multi-Signatures for Smaller Blockchains ,在方案中使用两个 Hash 函数 H_0 以及 H_1


#5

这个方案的公私钥分发由密钥生成中心来完成,不存在 rogue attack 的问题


#7

这里忘了说明了,t 是要小于 n/2 的


#8

这倒不是 t 的大小的问题,实际上,协议可以容忍的恶意节点数量 f 不一定和 t 相等。 t 可以取到 \lceil \frac{n}{2}\rceil 甚至更高都没有关系,而始终有 f \leqslant \lfloor\frac{n}{2}\rfloor


#9

不对,t 要大于 n/2,恶意节点小于等于 n/2


#10

为什么一定要大于啊?小于难道不行吗?这个难道不是拒绝服务重启和串谋预知随机数的一个 trade-off 吗?


#11

当恶意节点数 n/2 时,如果 t 小于 n/2 的话恶意用户共谋就可以恢复秘密了。


#12

当恶意节点数 n/2 时,如果 t 大于 n/2 的话恶意用户共谋就可以拒绝服务阻止协议进行了,在恢复阶段,恶意节点只需要再收集到 t-f 个诚实节点的份额就可以恢复出秘密,然后他们可以依此决定是否发动拒绝服务。也就是恶意节点可以进行 Adaptive Attack。