Hi 游客

更多精彩,请登录!

比特池塘 区块链技术 正文

理解 BLS 签名算法

茵665
84 0 0
编者注:BLS 签名算法是一种可以实现签名聚合和密钥聚合的算法(即可以将多个密钥聚合成一把密钥,将多个签名聚合成一个签名)。在以太坊未来的 Casper 实现中,有非常多的验证者都要对区块签名,要保证系统的安全性,同时节约存储空间,就需要用到这类签名聚合的算法。
' n- }6 {, B+ L: B/ b. e
之前的文章中,我介绍了 Schnorr 签名算法和它的优势。现在,我来介绍下 BLS(Boneh-Lynn-Shacham)签名算法以及它相比 Schnorr 的优胜之处。
# b0 {0 e+ G: \1 U长话短说,我们已经知道:, Q8 V$ \1 ?/ \9 m/ S! e
ECDSA 签名算法已经足够胜任它的工作,但也仅限于此。它无法做签名聚合或者密钥聚合,因此只能挨个对签名进行验证。在验证多重签名的交易时,此举过于繁琐,我们需要逐个验证所有的签名及其对应的公钥,耗费大量的区块空间和交易费。
/ C4 @( G) s2 o4 l7 x) @Schnorr 签名算法就好多了,它可以把一笔交易中的所有签名和公钥合并成单个签名和公钥,且合并过程不可见(无从追溯这个签名或公钥是否通过合并而来)。另外,可以一次性对合并后的签名做验证,加快了区块验证的速度。当然,该算法也有一些不足:
2 w) A! s. f% t; b多重签名需要多次(签名者之间的)通信,这对冷钱包来说过于麻烦。聚合签名算法依赖随机数生成器,而不像 ECDSA 那样可以使用指定的随机点(R)m-n 多重签名机制比较取巧,需要构建公钥的默克尔树。当 m 和 n 较大时,树所占空间会相当大。无法把一个区块中的所有签名聚合成一个签名BLS 签名算法可以解决以上问题。它不需要随机数生成器,可以将区块中的所有签名聚合成一个,容易实现 m-n 多重签名,也可以避免签名者之间的多余通信。除此之外,BLS 签名的长度更短(签名为椭圆曲线上的一个点而非两个),是 Schnorr 或 ECDSA 的 2 分之一。听起来完美!那么让我们看看 BLS 签名算法的工作原理。1 m' V( Z$ _0 ~+ l' N/ y- d  G
BLS 签名算法的魔力进入正题前,我们先来了解两个基础概念,曲线哈希(hashingto the curve,或译作 “哈希成曲线上的点”)和曲线配对(curves pairing)。
, M5 T. h6 {8 R+ a4 ^0 m7 N' S8 [曲线哈希在 ECDSA 和 Schnorr 签名算法中,我们对消息进行哈希计算后,结果(哈希值)是数字。BLS 签名算法则不同,它略微修改了哈希算法,结果对应到椭圆曲线上(的一个点)。最简单的修改是:哈希函数保持不变,将得到的哈希值作为点的 x 值寻找椭圆曲线上的对应点。通常来说(比如比特币所用的曲线),椭圆曲线有 2??? 个点,而 SHA-256 哈希算法的值也恰好是 256 位。不过,一个有效的 x 坐标,会对应一正一负两个 y 坐标(因为(x, y)和(x, -y)都是曲线 y?=x?+ax+b 上的点)。换句话说,新的哈希算法大约有 50% 的概率在曲线上找到 2 个对应点,另 50% 的概率则一个点也找不到(校对注:因为椭圆曲线只有 2^256 个点,如果要让每个哈希值都能找到对应点,椭圆曲线得有 2^257 个点才行)。
4 ^+ w# K* `9 ~; B$ h! b以在模为23的有限域上定义的椭圆曲线 y?=x?+7 为例。只有一半的 x 坐标在曲线上能找到对应点。此例中,我们尝试三次才成功找到对应点。8 M! ~5 R/ |# M! U& D
对消息求哈希时,为确保能在曲线上找到对应的点,可以在消息体后附加一个数,若(寻找对应点)失败则累加该数并重新计算。即如果 hash(m||0) 没有找到对应点,则持续尝试 hash(m||1), hash(m||2) 等,直到找到为止。当找到对应点后,在 2 个点中选择 y 坐标较小的那个作为结果即可。
/ P1 x6 Y1 x2 |曲线配对我们还需要一个特殊的函数,能够把一条(或2条不同的)曲线上的两个点 PQ 映射为一个数:
) U) |5 D" y; ?e(P, Q) → n此函数还要有一个重要的特性。即对于未知数 x 和两个点 PQ ,无论哪个点乘以 x,结果相同,即
! j( [8 ^/ j2 ^1 h% L4 V# h: Ee(x*P, Q) = e(P, x*Q)如此,除了乘数交换仍能保持等式成立外,更进一步,以下所有的交换都要保持等式成立:
7 m  u% x  H' o3 r; Q% e1 K: \, se(a*P, b*Q) = e(P, ab*Q)
* M: c9 @3 B" ?            = e(ab*P, Q)
6 ]; C! b4 q; o9 _$ m            = e(P, Q)^(ab)我不准备解释这个函数是如何工作的。背后的数学原理相当复杂,如果你想知道所有 “令人厌烦” 的细节,我建议你参考这篇文章。如果你还想深入,可以研读这篇论文,它通篇讲述配对(pairings)理论。当前,我们只要假设这种函数存在,并且不会暴露 x 的任何相关信息。
  K2 `$ {$ F' d, b% W3 i( Y值得注意的是,配对函数中不能使用任何椭圆曲线(特别是比特币的 secp256k1 椭圆曲线)。我们必须使用非常特殊的曲线(通常出自易于配对的曲线簇),才能保证函数的效率和安全。+ M# ~8 l5 N: b% l% x( q6 N  j1 A
BLS 签名方案现在,所有构建 BLS 签名算法的基础知识已经齐备。我们用 pk 代表私钥,P = pk*G 代表公钥,m 代表要签名的消息。
+ x' Q5 H; p# O+ r: L4 K为了计算签名,先对消息求曲线哈希 H(m) ,再将获取的结果(曲线坐标点)乘以私钥即可:S = pk*H(m)。大功告成!不需要随机数,不需要额外的步骤,仅仅将哈希结果乘以私钥即可。签名结果是一个曲线上的点,用压缩的序列化格式保存,只占 33 个字节。, F2 q1 ^# g, v3 A5 m7 G
-生成 BLS 签名。将消息的哈希结果乘以私钥即可-我们可以使用公钥 P 来验证签名,即 e(P, H(m)) = e(G, S) 。这是为什么呢?
( p0 n6 z4 p; G9 c如前所述,配对函数的特性使得如下等式成立:
+ t6 g. X9 u& z: le(P, H(m))  = e(pk*G, H(m)) # U. A! W. C4 D- H2 X" ~
            = e(G, pk*H(m))
- ~6 J2 s5 K( D4 M            = e(G, S): ?& Q5 i# I0 V9 F
- BLS 签名验证。我们只需验证 公钥和消息的哈希值(曲线上两个点) 与 曲线生成点和签名(曲线上另两个点) 是否映射到同一个数(若是则说明这是一个有效的 BLS 签名)-这个签名方案优美简单。对于比特币来说,该方案还有以下更棒的特性。% \$ `/ S3 I( p% C$ w% k' B  L7 N
签名聚合现在让我们把区块中的签名都聚合在一起。假设一个区块中有 1000 笔交易,每笔交易都由 Si(签名),Pi (公钥)和 mi(消息)组成(i 在这里表示序号)。如果这些签名可以被合并,那又何必分开保存呢?毕竟,我们只关心区块中所有的签名(而不是每一个)是否正确。为获得聚合签名,只需要将区块中的所有签名加起来:2 d8 v& f1 s$ W3 k5 H' g
S = S1 + S2 +…+ S1000为验证该区块是否正确,我们需要保证以下等式成立:, J# o+ ^6 q, o% m3 L/ P5 P
为验证该区块是否正确,我们需要保证以下等式成立:
' d9 h2 q1 k" r9 A$ }# E% \e(G, S) = e(P1, H(m1)) * e(P2, H(m2)) *…* e(P1000, H(m1000))如果签名都有效,那么该等式的确是成立的:# `/ [9 R/ K1 k& m2 x/ ]" `
e(G, S) = e(G, S1+S2+…+S1000) - f7 f5 [$ P4 i: O1 t6 H% [3 u
        = e(G, S1) × e(G, S2) *…* e(G, S1000)
$ e5 B2 K' W3 }& Q: y        = e(G, pk1×H(m1)) *…* e(G, pk1000×H(m1000))
: Z0 O% V0 X7 p4 W9 V& f        = e(pk1×G, H(m1)) *…* e(pk1000×G, H(m1000))
3 i  g0 W; }0 o+ A5 v0 d        = e(P1, H(m1)) × e(P2, H(m2)) *…* e(P1000, H(m1000))这里我们仍需用到所有的公钥,并计算 1001 次配对函数,好处是,区块中的签名只占 33 字节了。签名聚合可以由矿工在挖矿时完成,节省大量的区块空间。, ^5 `1 L! |* g
密钥聚合和 n-n 多重签名使用多重签名的地址时,我们会对同一笔交易用不同的密钥进行签名。这种情况下,可以和 Schnorr 算法一样使用聚合密钥,把所有密钥和签名聚合成单个公钥和签名。下面我们以 3-3 多重签名方案为例(同理可推导任意数量的多重签名方案)。& I$ Y( T, O. }) p
一种简单的聚合方法,是把所有的签名和密钥加起来即可。如此,签名聚合结果为 S=S1+S2+S3,密钥聚合结果为 P=P1+P2+P3。可以验证以下等式依然成立:- u6 C8 [- m, G% A( Y
e(G, S) = e(P, H(m))因为:' ^: }$ D- E* m7 u
e(G, S) = e(G, S1+S2+S3) * R! u) o" {/ H. Z5 N
        = e(G, (pk1+pk2+pk3)×H(m))
# x% p6 R, F4 L3 ?% v1 R- O+ S) u; s        = e((pk1+pk2+pk3)×G, H(m))
( p+ ~; ?1 P% ]" e1 a$ U, e        = e(P1+P2+P3, H(m)) = e(P, H(m))和 Schnorr 一样,我们也需要杜绝伪造密钥攻击。一种方法是要求每个签名参与者证明它拥有公钥对应的私钥(用私钥给公钥签名)。另一种方法是加入非线性系数,使得攻击无法实施。要做到这一点,聚合不再是简单的将多个密钥和签名相加,而是将它们分别乘以某个系数后再相加:6 G: Z7 n9 A" I% q. Q2 m0 ^
S = a1×S1+a2×S2+a3×S3
  u9 x4 |$ [8 \% M; p, @' P5 Y/ BP = a1×P1+a2×P2+a3×P3
( k* a* K$ O, F, Z$ ~, z" m0 l0 a公式中签名和密钥的系数,可以通过签名者以及其它所有人的公钥计算得出,公式如下:+ b! w% [7 A; ~: [7 q1 o- M
ai = hash(Pi, {P1,P2,P3})举个例子,可以简单的将签名者的公钥和所有人公钥拼接在一起算出系数:; ~/ o+ q6 J: L! T
ai = hash(Pi||P1||P2||P3)此时,上面的验证公式依然成立。虽然多了系数 ai,但计算逻辑未变。
7 b3 e" j% F, w$ E8 c7 R# I7 ?该方案的好处是,无需在设备间进行多轮通信,只需知晓其它签名者的相应信息即可。它可比 Schnorr 算法(需要 3 轮通信)的多重签名方案简单多了。这个方案也不依赖随机性,是一种具有完全确定性的签名算法。
( N! l: y6 a9 w6 ^2 k6 w0 z子群多重签名方案(m-n 多重签名)n-n 多重签名并不常见,我们更倾向使用 m-n 多重签名(比如 2-3 多重签名)。我们不想因为丢失(n 个密钥中的)一个密钥而一无所有。密钥聚合非常适合这种场景。在 Schnorr 签名算法中,我们用公钥组成的默克尔树来实现密钥聚合,这种方式效率不高,但是将将堪用。不幸地是,当 m 和 n 的值变大时,默克尔树的大小会呈指数增长。" a4 h3 K5 ~  r/ Q- `1 A  A3 _
BLS 使用了另一种方法,不过略复杂。我们需要一个普通哈希函数 hash(x) (结果为一个数)和一个曲线哈希函数 H(x) 。开始多重签名时,还需要一个初始化过程,这之后,签名者之间就不再需要通信了,只需提供交易签名即可。  J1 B, U, s$ ^6 a; K: Q" X( J
举个简单的例子,我们要创建一个 2-3 多重签名,3 个签名存储在不同的设备上(这个例子可以扩展为任意的 m-n 多重签名)。7 o( G" K; w4 Q& f
初始化(生成成员密钥)用 i = 1,2,3 来表示集合中相应位置的设备,用 pki 表示私钥,用 Pi = pki×G 表示公钥。我们用前面说的方法来聚合公钥:: w' I5 H* U6 A* S8 g: l' R
P = a1×P1+a2×P2+a3×P3, ai = hash(Pi, {P1,P2,P3})
" R  ]( B4 U' B+ ?) X现在,每个设备都需要对每个 i 签名,以证明该 i 是聚合公钥中的一员。将签名聚合后,保存在对应的设备中:+ V3 E6 K( F8 Q! X
MKi = (a1*pk1)*H(P, i) + (a2*pk2)*H(P, i) + (a3*pk3)*H(P, i)这个签名被称作“成员密钥”,稍后签名时我们会用到。每个成员密钥都是对消息体 H(P,i) 的 n-n 多重签名,即:9 {( R8 b% v1 [+ c
e(G, MKi)=e(P, H(P,i))3 V2 d7 N8 P3 z2 g
因为:9 K" `) P, p# W
e(G,Mki) = e(G, (a1*pk1)*H(P, i) + (a2*pk2)*H(P, i) $ j! U4 |8 c, Q3 X
              + (a3*pk3)*H(P, i))
/ J" w; L8 z- |6 S, |+ f& `         = e(G, (a1*pk1 + a2*pk2 + a3*pk3)*H(P, i))
8 C$ V( X3 S6 p$ N8 m         = e(G*(a1*pk1 + a2*pk2 + a3*pk3), H(P, i))
- S; r/ T0 P7 p8 c4 g- X         = e((G*a1*pk1 + G*a2*pk2 + G*a3*pk3), H(P, i))! B! X2 ?: c' O
         = e(P, H(P,i))记住这个等式,稍后还会用到。它用来证明某个设备是多重签名中的合法参与者。
8 O$ ^# |' `) U7 V0 n签名假设只用私钥 pk1pk3 给交易签名,我们会生成 2 个签名 S1S39 ^9 R% R2 M1 f( d$ k
S1 = pk1×H(P, m) + MK1, S3 = pk3×H(P, m) + MK3将它们加起来,聚合成单一的签名和公钥:
. J0 i# x3 o2 \4 }  b6 u5 Z5 p(S’, P’) = (S1+S3, P1+P3)用 P’S’,是为了强调它们只是由部分签名者参与计算的(公钥和签名),而不像 P 那样是由所有签名者参与计算的(公钥)。为了验证 2-3 多重签名,需证明如下等式成立:
, v$ O# A/ `, _0 `3 Ze(G, S’) = e(P’, H(P, m)) * e(P, H(P, 1)+H(P, 3))上面说过,成员密钥 MK1MK3 是对消息 H(P, 1)H(P, 3) (消息本身由聚合公钥 P 签名)的签名,所以有:8 a" M& B, ]  c; [
e(G, S’) = e(G, S1+S3)3 ]* a  J% v) a
         = e(G, pk1*H(P, m)+pk3×H(P, m) + MK1 + MK3)
- v: [/ j7 I+ A) ^6 H         = e(G, pk1*H(P, m)+pk3×H(P, m)) * e(G, MK1+MK3)- n2 C2 T- N! L0 _: N  Y- R
         = e(pk1*G+pk3*G, H(P, m)) * e(P, H(P, 1) + H(P, 3))
8 e5 e/ w- O* N1 D  M  ^+ W         = e(P’, H(P, m)) * e(P, H(P, 1)+H(P, 3))证明完毕。比 n-n 多重签名复杂一些,但仍然可以理解。5 V3 K$ q' P9 N/ e3 _
在比特币中的实现要在比特币上部署一个 BLS 多签名钱包时,我们需要往某个地址(该地址由聚合公钥 P 生成)打钱。假设我们希望这是一个 2-n 多签名合约,那么可以用比特币的锁定脚本来描述,声明如下:
1 d* \* r2 S& k. C" Y, fOP_2  OP_CHECK_BLS_MULTISIGOP_2 表示需要2个密钥进行签名。这里没有指明总共有 3 个签名,因此它可以表示 2-3 或者 2-100 等不同的多重签名地址。如此,总签名数永远不会暴露。
' P% g7 v) ?5 o1 }1 b" i5 b) t  a为了花掉输出(output)地址中的钱,则需要提供 P’ (公钥),S’(签名 )以及参与签名者的编号(这个例子中是 1 和 3)。解锁脚本如下:
& |* r; u9 I  W: V$ O0 B; ROP_1 OP_3  脚本中有了这些信息,就足够用来验证交易了。其中,OP_1OP_3 告诉我们需要计算的曲线哈希为 H(P, 1)H(P, 3)7 a: R! H) u  j7 X- K  F
如此,对于任意 mn 的多重签名,我们只需要以下信息:
5 M4 W; e+ W  N一个用在加锁脚本中的聚合公钥 P一个由部分参与者(m 个)生成的聚合公钥 P’ (用在解锁中)一个聚合签名 S’解锁要求的参与者数量 m一切简单而优美!( s) q& L# X3 \; g4 ?; [6 C3 S
由于比特币地址通常只用一次,需要使用 BIP32 这种密钥推导算法生成新的私钥和地址。因此,每次生成新的私钥时,我们也需要生成对应的成员私钥,我不太喜欢这一点。为避免每次交易后都要初始化生成成员私钥,可以一次性地生成一批(比如 1000 个)成员私钥,毕竟每个私钥只占 32 字节。如此,当 1000 个地址用完后,我们才需要再次进行初始化。
1 i! A+ s$ V0 Y8 B, L' U缺点鉴于大家在评论和 twitter 的提醒,我认识到有些地方我考虑欠周,会让你们误以为 BLS 签名算法是完美的。它并不完美。谢谢你们的提醒!
1 k2 C7 |! _: b9 B我完全忽略了配对计算的高复杂度。我们曾认为配对函数 e(P, Q) 既高效又安全,实际上它并不完全是。% k$ _7 s3 T; C) ~9 b* e
配对函数并不那么高效BLS 签名验证的复杂度要比 ECDSA 高上一个数量级。在验证区块中 1000 笔交易的聚合签名时,仍需要进行 1000 次配对计算,这可能比使用 ECDSA 时(对 1000 个单独签名进行验证)还要慢。唯一的好处在于,可以在区块中放更多笔的交易,毕竟聚合签名只占 32 字节。
: V0 |5 k5 a; o( W7 H* q与 BLS 不同,Schnorr 验证算法的效率很高,它可以把签名放一起验证,效率是 ECDSA 算法的三倍。这样,问题来了,效率和安全哪个对我们更重要?
) j; [& x- Y' f3 I/ s3 q% I想要安全,更难!配对函数十分复杂,使用不当就会反受其累。一方面,我们希望用高效的配对函数来加快签名验证,另一方面,我们又希望密钥信息暴露越少越好。两者互相矛盾,我们需要异常小心地选择适宜配对的曲线。
: U% a" w5 o! d' l有一种针对椭圆曲线加密体系的攻击,叫 MOV 攻击(用攻击发现者 Menezes、Okamoto 和 Vanstone 的名字命名),它能利用配对函数来危害系统安全。所以,使用配对函数必须万分小心。
3 G/ U! u3 H  Q2 o9 r% O& C总结BLS 签名算法很出色——它能将区块中的签名聚合成单一签名;能进行密钥聚合和 m-n 多重签名(无需额外通信);能避免使用随机数生成器。这些优点使它显得如此简单优雅。当然,它仍有改进空间,标准化和优化也尚需时日。但我希望有朝一日,它能变得足够好,可以被纳入比特币协议中。这样的话,我们不但能获得它出色的功能,还可享受体积更小、聚合度更强的签名算法带来的好处。
  |* a5 y7 l) o, x* G8 VBLS 算法的第一作者 Dan Boneh,目前正投身于对加密货币的研究,这使我异常兴奋。他是一位杰出的密码学家,他所执教的密码学课程也很棒。在这里,我还要推荐下他尚未完成的密码学著作。相信不久的将来,他和他的团队会带来更多针对加密货币的有趣方案和协议改进。
BitMere.com 比特池塘系信息发布平台,比特池塘仅提供信息存储空间服务。
声明:该文观点仅代表作者本人,本文不代表比特池塘立场,且不构成建议,请谨慎对待。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

成为第一个吐槽的人

茵665 小学生
  • 粉丝

    0

  • 关注

    0

  • 主题

    1