BLS签名算法 _生活百科

前言[失踪人口回归 (*/ω＼*)] 真的好久好久没有更新了，因为自己也还在找方向，但还是把新学的知识记录在博客里。今天要介绍的是BLS签名算法。
一、BLS签名算法简介BLS签名算法[1]是由斯坦福大学的 Dan Boneh、Ben Lynn 和 Hovav Shacham一同提出的。
一般将 ECDSA签名算法、Schnorr签名算法和BLS进行对比。
ECDSA签名算法局限性：
无法进行签名聚合和密钥聚合。换句话说，当我们验证多重签名交易的时候，我们只能逐个对签名进行验证，显然这会耗费大量的区块空间和交易费。因此并不适用于多重签名场景。
Schnorr签名算法：
可以将一笔交易中的所有签名和公钥合并成单个签名和公钥，其过程是不可见的（即无法判断该签名或公钥是否通过合并得到的）。这样就可以实现只需要一次就可以对合并后的签名做验证，加快了区块验证的速度。
但其仍然存在着局限性：

多重签名需要多次（签名者之间的）通信，这对冷钱包来说过于麻烦；
聚合签名算法依赖随机数生成器，而不像 ECDSA 那样可以使用指定的随机点（R）；
m-n 多重签名机制比较取巧，需要构建公钥的默克尔树。当 m 和 n 较大时，树所占空间会相当大；
无法把一个区块中的所有签名聚合成一个签名。

与这两个签名算法作比较， BLS有如下优点：
（1）不需要随机数生成器，可以将区块中的所有签名聚合成一个；
（2）容易实现 m-n 多重签名，也可以避免签名者之间的多余通信；
（3）签名的长度更短（签名为椭圆曲线上的一个点而非两个），是 Schnorr 或 ECDSA 的 2 分之一。
二、基础知识在对BLS算法进行阐述之前，首先了解一下曲线哈希和曲线配对。
2.1 曲线哈希Hashing to the curve 一般可以翻译为曲线哈希或者是哈希成曲线上的点。没了解之前听到曲线哈希可能会不知道是啥，但听到哈希成曲线上的点就大概知道意思了。
在一般的哈希计算中，常常是对于不定长的输入最终输出一个定长的数值。但曲线哈希就不一样，其输出结果会对应到椭圆曲线上的一个点。
具体做法如下：
哈希函数保持不变，将得到的哈希值作为点的 x 值寻找椭圆曲线上的对应点。
通常来说（比如比特币所用的曲线），椭圆曲线有 2256 个点，而 SHA-256 哈希算法的值是 256 位。不过，一个有效的 x 坐标，会对应一正一负两个 y 坐标（因为（x, y）和（x, -y）都是曲线y2=x3+ax+b上的点）。换句话说，新的哈希算法大约有 50% 的概率在曲线上找到 2 个对应点，另 50% 的概率则一个点也找不到。因此，在应用过程中会出现需要尝试多次才能找到对应点的情况。
· 有两个对应点怎么解决呢？
选择y坐标较小的作为结果即可。
· 那出现找不到对应点的情况怎么办呢？
可以在消息体后面附加一个数。当找不到对应点的时候，将该数加一再重新计算直到找到对应的点。
下面给出一个例子。
以在模为 23 的有限域上定义的椭圆曲线 y2=x3+7为例。只有一半的 x 坐标在曲线上能找到对应点。
① 计算 hash(m||0)，没有对应的点。
② 计算 hash(m||1)，没有对应的点。
③ 计算 hash(m||2)，发现对应的点。对应的点有两个，选择y坐标较小的作为结果。

文章插图
2.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的任何信息。