【密码学（2）】-BLS聚合签名

hotstuff中相比PBFT来说，复杂度从平方级变成单级，这里就必须提到关键的一步，即BLS聚合签名。所以本期将介绍BLS相关原理知识。

BLS字母代表Boneh–Lynn–Shacham，最初是由斯坦福大学教授Dan Boneh等人于2001年提出的一种签名方案，最新是在2018年，Boneh教授与IBM研究机构的Manu Drijvers等人更新了这种签名方案。

与以往签名方案不同的是，BLS采用了基于双线性映射的椭圆曲线配对技术，来实现签名验证与聚合。

BLS签名过程

1. 准备阶段，秘密选取随机数字作为私钥pk，计算公钥P = pk × G，待签名的消息m。

2. 签名与验证：将消息哈希H(m)映射到曲线上的点,记为q，将结果点乘以私钥得到签名: S = pk × q

3.验证签名： 按照步骤1同样计算出映射到曲线点q,检验 e(P, q) = e(G, S)

为什么可以这样验证？函数e是什么？这里就用到了上面略过的曲线配对函数，简介如下：

有一个（或一种）特殊的函数记为e，它可以接受输入一条（或两条不同）曲线上两点P和Q，输出至一个数字，如式：e(P, Q) → n

之所以说这个函数特殊，是因为它有一些特殊性质。例如我们有一个数x和两点P和Q，无论哪一个点乘以这个数字，函数结果相同即：

e(x P, Q) = e(P, x Q)

更进一步： e(a P, b Q) = e(P, ab Q) = e(ab P, Q) = e(P, Q)^(ab)

当然还有其他性质，但是对于我们用来验证签名，主要用到以上性质。

要验证签名： e(P, q) = e(pk G, q) = e (pk G, q) = e (G, pk * q) = e (G, S)

有了单个签名，我们再来看下聚合签名。

BLS聚合签名

区块链应用场景下，通常用于压缩区块内交易的签名大小，假设我们有一个包含10笔交易的区块，每笔交易i有自己的签名S_i、公钥P_i以及一个签名消息为m_i。

聚合签名是将区块中所有交易签名的打包成一个签名，同时验证所有交易的签名正确性。 令最终签名结果为S, S =S_1 +S2 + ... +S{10}

要验证区块所有交易签名，需检查下式成立：

e(G, S) = e(P_1,q_1)e(P_2,q_2)...e(P{10},q{10})

推导如下：

e(G, S)=e(G,S_1 +S2 + ... +S{10})

=e(G, S_1)e(G, S_2)...e(G, S_{10})

=e(G,pk_1q1)...e(G,pk{10}q_{10})

=e(pk_1G,q1)...e(pk{10}G,q_{10})

=e(P_1,q_1)e(P_2,q2)...e(P{10},q_{10})

这里依然使用了配对函数性质，仍需用到所有的公钥，并计算10次配对函数，交易量越多计算量越大，好处是，区块中的签名字节大大减少了。

BLS密钥聚合

根据前面多签的介绍，可以知道使用多重签名的地址，会对同一笔交易用不同的密钥进行签名。接下来说明BLS聚合密钥过程。

一种简单的聚合方法，把所有的签名和公钥加起来。这样，签名聚合结果为： S =S_1 +S_2 +S_3

密钥聚合结果为 ：P =P_1+P_2+P_3 。

令q为消息m哈希映射到曲线上的点，是一个确定的值。可以验证以下等式成立：e(G, S) = e(P, q)

验证如下：

符号同上文，利用配对函数e的性质。

抗密钥攻击聚合

上述的方案理论上可行，但实际上可能受到密钥攻击，例如伪造签名，如何防范呢？

一种方法是要求每个签名参与者证明它拥有公钥对应的私钥（用私钥给公钥签名或者随机指定消息签名）。 另一种方法是加入非线性系数，使得攻击难以实施。当然就不能使用上面提到的简单的将多个公钥和签名相加的方法，而是将它们分别乘以某个系数后再相加：

S =a_1 × S_1 +a_2 × S_2 + a_3 × S_3

P =a_1 × P_1 + a_2 × P_2 + a_3 × P_3

公式中签名和公钥的系数，可以通过签名者以及其它所有参与者的公钥计算得出，公式如下：

a_i = hash(P_i,P_1,P_2,P_3)

最简单的做法是将签名者的公钥和所有参与者公钥拼接在一起：

a_i = hash(P_i||P_1||P_2||P_3)

此时，上面的验证公式依然成立。虽然多了系数 a_i，但计算逻辑未变。

具体代码实现可以多种，只要是可验证的,确定性的即可。

单就该方案的好处是，无需多轮通信，只需知晓其它签名者的信息即可。它可比 Schnorr 算法（需要 3 轮通信）的多重签名方案简单。且不依赖随机性，是一种具有完全确定性的签名算法。