BLS 签名算法

BLS 签名算法 2022-10-10 前言

【失踪人口归来(*/ω＼*)】好久没有更新了，因为还在找方向，不过还是把新的知识记录在博客里。 今天要介绍的是BLS签名算法。

一、BLS签名算法介绍

BLS 签名算法 [1] 是由斯坦福大学的 Dan Boneh、Ben Lynn 和 Hovav Shacham 提出的。

一般比较ECDSA签名算法、Schnorr签名算法和BLS。

ECDSA 签名算法的局限性：

无法进行签名聚合和密钥聚合。 也就是说，我们在验证多重签名交易时，只能一个一个地验证签名，这显然会消耗大量的区块空间和交易手续费。 因此不适合多重签名场景。

Schnorr签名算法：

一笔交易中的所有签名和公钥可以合并为一个签名和公钥，过程是不可见的（即无法判断签名或公钥是通过合并得到的）。 这样，合并后的签名只需验证一次比特币密钥生成器，加快了区块验证的速度。

但它仍然有局限性：

与这两种签名算法相比，BLS具有以下优势：

(1) 不需要随机数生成器，可以将区块中的所有签名聚合为一个；

(2) 易于实现mn多重签名，也可以避免签名者之间的冗余通信；

(3)签名的长度更短（签名是椭圆曲线上的一个点而不是两个），是Schnorr或ECDSA的1/2。

二、基础知识

在讲解BLS算法之前，我们先了解一下曲线哈希和曲线配对。

2.1 曲线哈希

散列到曲线一般可以转化为曲线散列或者散列到曲线上的点。 如果不理解，之前听到曲线hash可能不知道是什么意思，但是听到hash变成曲线上的一个点大概就知道什么意思了。

在一般的哈希计算中，对于一个变长的输入，往往是最终输出一个固定长度的值。 但是曲线哈希不同，它的输出会对应椭圆曲线上的一个点。

具体方法如下：

哈希函数不变，将得到的哈希值作为该点的x值，在椭圆曲线上找到对应的点。

一般来说（比如比特币使用的曲线），椭圆曲线有2256个点，SHA-256哈希算法的值是256位。 但是，有效的 x 坐标对应于正负 y 坐标（因为 (x, y) 和 (x, -y) 都是曲线 y²=x³+ax+b 上的点）。 换句话说，新的哈希算法有大约 50% 的机会在曲线上找到 2 个对应点，也有 50% 的机会找不到。 因此，在应用过程中，可能需要多次尝试才能找到对应点。

· 如何解决两个对应点？

选择 y 坐标较小的那个作为结果。

· 找不到对应点怎么办？

可以在消息正文中附加一个数字。 当找不到对应点时，将数字加一，重新计算，直到找到对应点。

下面给出了一个例子。

以定义在有限域模23上的椭圆曲线y²=x³+7为例。 只有一半的 x 坐标找到曲线上的对应点。

① 计算hash(m||0)，没有对应点。

② 计算hash(m||1)，没有对应点。

③ 计算hash(m||2)，找到对应点。 对应点有两个，选择y坐标较小的作为结果。

2.2 曲线配对

在曲线哈希中，我们将输入（值）映射到椭圆曲线上的点。 显然，我们还需要将点映射到数字的函数。 下面介绍一个特殊的函数，可以将一条（或两条不同的）曲线上的两点P和Q映射为一个数：

e ( P , Q ) → n

这个函数还有一个更重要的属性。 即对于一个未知的x和两点P、Q，无论哪一点乘以x，结果都是一样的，即：

e(xP, Q) =e(P, xQ)

此函数还具有以下属性：

e(aP , bQ) =e(P , abQ) =e(abP , Q) =e(bP , aQ) =e(P , Q) ab

这个函数的原理这里就不详细介绍了，涉及到很多数学原理。 不过如果不出意外的话，后面我会更新一个关于pairings的理论。 有兴趣的可以关注一下。

现在只知道存在这样的函数，并且它们具有上述属性。 除此之外，它不会公开有关 x 的任何信息。

值得注意的是，配对函数中不能使用任何类型的椭圆曲线（特别是比特币的 secp256k1 椭圆曲线）。 我们必须使用非常具体的曲线（通常来自易于配对的曲线系列）来保持功能的高效和安全。

3. BLS签名方案

现在我们终于可以进入正题了！

其中pk代表私钥，P代表公钥，m代表待签名的消息。 其中 P = pk × G。

3.1 签名

① 对消息m进行曲线哈希得到H(m)。

② 使用私钥签名。 将刚刚得到的结果乘以私钥。

S = pk × H(m)

3.2 验证签名

在验证签名时，使用公钥P进行验证。 验证过程如下：

e(P, H(m)) =e(G, S)

3.3 原理

下面证明e(P , H(m)) = e(G , S) 这个等式成立。

已知：P = pk×G , e(xP , Q) =e(P , xQ) 。

e(P, H(m)) =e( pk × G, H(m)) =e( G , pk ×H(m)) =e( G , S)

下图可以很直观的表示。 对于BLS签名验证，我们只需要验证公钥和消息的哈希值（曲线上的两点）和曲线生成点和签名（曲线上的另外两点）是否映射到同一个数（如果是比特币密钥生成器，则表示这是一个有效的 BLS 签名）。

4. 签名聚合

前面提到，BLS签名算法可以实现签名聚合。 让我们介绍一下这个很棒的功能。

现在假设在区块链场景中，有一个区块有1000笔交易，每笔交易由签名Si、公钥Pi和消息mi组成。 现在我们只关心块中的所有签名（不是每个）是否正确。 要获得聚合签名，只需将块中的所有签名相加即可：

S=S1+S2+...+S1000

为了验证区块是否正确，需要保证以下等式成立。

e(G , S) =e(P1 , H(m1)) ×e(P2, H(m2)) × ... ×e(P1000, H(m1000))

如果签名有效，则等式成立。 证明如下：（这里我直接在word中截图）

这里我们仍然需要使用所有公钥并计算配对函数 1001 次。 优点是区块中的签名只占33字节。 签名聚合可以由矿工在挖矿时完成，节省大量区块空间。

4.1 nn 多重签名

当使用多重签名地址时，我们使用不同的密钥签署相同的交易。 在这种情况下，可以像 Schnorr 算法一样使用聚合密钥将所有密钥和签名聚合成一个公钥和签名。

我们以3-3多重签名方案为例（同样可以推导出任意数量的多重签名方案）。 一种简单的聚合方法是将所有签名和密钥相加。 这是：

签名聚合结果：S=S1+S2+S3

关键聚合结果：P=P1+P2+P3

可以验证以下等式仍然成立：

e(G, S) =e(P, H(m))

证明如下：（这里我直接在word中截图）

和 Schnorr 一样，我们也需要防止密钥伪造攻击。 一种方法是要求每个签名参与者证明其拥有公钥对应的私钥（使用私钥对公钥进行签名）。 另一种方法是添加非线性系数，使攻击变得不可能。 为此，聚合不再是简单地将多个密钥和签名相加，而是将它们乘以某个系数并相加：

S = a1×S1+a2×S2+a3×S3

P = a1×P1+a2×P2+a3×P3

公式中签名和密钥的系数可以由签名者和其他人的公钥计算得到，公式如下：

ai=hash(Pi, {P1,P2,P3})

例如，可以通过简单地将签名者的公钥与所有者的公钥连接起来来计算系数：

ai=哈希（Pi||P1||P2||P3）

此时，上述验证公式仍然成立。 虽然系数ai多了，但是计算逻辑不变。

这种方案的优点是设备之间不需要进行多轮通信，只需要知道其他签名者的相应信息即可。 它比 Schnorr 算法的多重签名方案（需要 3 轮通信）要简单得多。 该方案也不依赖于随机性，是一种完全确定性的签名算法。

420 万多重签名

上面介绍了nn多重签名，但是在实践中并不是很常用，mn多重签名是比较常用的。

在 Schnorr 签名算法中，我们使用由公钥组成的默克尔树来实现密钥聚合。 这种方法效率不高，但会很有用。 不幸的是，随着 m 和 n 的值变大，Merkle 树的大小呈指数级增长。

BLS 使用另一种方法，但稍微复杂一些。 我们需要一个普通的散列函数 hash(x)（产生一个数字）和一个弯曲的散列函数 H(x)。 在启动多重签名时，还需要一个初始化过程，之后签名者之间就不需要再进行通信，只需要提供交易签名即可。

举个例子，我们要创建一个2-3个多重签名，3个签名分别存储在不同的设备上（这个例子可以扩展到任意mn个多重签名）。

(1) 生成成员密钥

用i=1,2,3表示集合中对应位置的设备，用pki表示私钥，用Pi=pki×G表示公钥。 我们使用上面提到的方法聚合公钥：

P = a1×P1+a2×P2+a3×P3

其中，ai=hash(Pi, {P1,P2,P3}) 。

现在，每个设备都需要对每个 i 进行签名，以证明 i 是聚合公钥的成员。 签名聚合后，保存在对应的设备中：

MKi = (a1×pk1) × H( P , i ) +(a2×pk2) ×H( P , i ) +(a3×pk3) ×H( P , i )

此签名称为“成员密钥”，我们稍后将在签名时使用它。 每个成员密钥是消息体 H( P , i ) 的 nn 个多重签名，即：

e(G, MKi) = e(P, H(P , i))

证明如下：

记住这个等式，你以后会用到它。 它用于证明设备是多重签名的合法参与者。

(2) 签字

假设现在使用 pk1 和 pk3 对交易进行签名，将生成两个签名 S1 和 S3：

S1 = pk1×H(P,m) +MK1

S3= pk3×H(P,m) +MK3

将它们相加并将它们聚合成一个签名和公钥：

(S', P') = (S1+S3, P1+P3)

P'和S'用来强调它们只是被部分签名者（公钥和签名）计算出来的，而不是像P一样被所有签名者（公钥）计算出来的。为了验证2-3多重签名，有必要来证明以下等式成立：

e(G,S')= e(P',H(P,m)) ×e(P,H(P,1)+H(P,3))

如前所述，成员密钥MK1和MK3是消息H(P,1)和H(P,3)的签名（消息本身由聚合公钥P签名），因此有：

证明结束了。 比 nn multisig 复杂一点，但仍然可以理解。

5.缺点

① 配对功能效率不高

② 存在一种针对椭圆曲线加密系统的攻击——MOV 攻击。 这种攻击可以利用配对功能来破坏系统安全。 所以谨慎使用配对功能。

参考

[1]Boneh D、Lynn B、Shacham H。 Weil 对的短签名[J]． 斯普林格，柏林，海德堡，2001 年。

[2] 理解BLS签名算法