Hi 游客

更多精彩,请登录!

比特池塘 区块链技术 正文
Schnorr签名算法最初是由德国密码学家Claus Schnorr于2008年提出的,而来自区块链协议公司Blockstream的密码学家Gregory Maxwell、Pieter Wuille等人,则在2018年提出了一种名为MuSig的Schnorr签名方案,这也是我们即将探索的签名方案。而BLS签名方案,最初是由斯坦福大学教授Dan Boneh等人于2001年便提出的一种方案,目前则在Boneh教授等人的完善下,变得更适用于区块链。
( S9 o$ K& q# ]  F0 T! d) \1 d8 M3 Y6 P! l. Z6 s
总的来说,两大签名方案各有千秋,它们在不同的场景下都有各自的优势。" F+ s* S( X4 B% _
7 G* [0 P: A0 [( m* m0 L8 @( }6 J
以下内容译自量子物理学家Stepan的两篇科普文章(part1和part2),总结部分略有改动:# f/ o0 D6 F" X- S( C$ T
- ^* K, M6 J, u$ s- ~/ [! J9 \
目录' R) W: |' k1 Z4 `, s
' F5 _- A2 r5 d0 Y6 t4 d; p
1、椭圆曲线数字签名算法(ECDSA)
6 V  E& g: M  b5 O+ F2、什么是Schnorr签名?; V9 U7 m: {3 t& z& r% f
3、Schnorr签名的批量验证  O) K1 X0 B8 K2 |
4、Schnorr签名的密钥聚合, h9 m. f1 w; b9 A3 h
5、MuSig:由Blockstream提出的Schnorr签名方案* ~+ A7 o, ^7 S  V+ g0 r
6、默克尔多重签名(Merkle Multisig)! O8 I/ _3 g/ W' S
7、什么是BLS签名方案?3 C, ?2 ?% |- y% D% |
8、BLS签名的魔法. r# I8 O3 H, ?/ |! V2 n) z
9、BLS签名方案的具体原理
, R# ^; g4 m2 F! A. L4 F# }10、BLS签名的签名聚合
$ M5 W+ z1 R. F+ |( F11、BLS签名的密钥聚合和n-of-n多重签名: _8 \$ p) ^4 |
12、子群多重签名方案(m-of-n multisig)% [. x' ?, z8 `+ F
13、BLS签名可能的应用场景# Z" i" x! m; j/ t3 c
14、BLS签名的弊端:配对效率低下, b9 y$ v! A% {* n
15、结论
3 u2 ]* O* I, K, h% T- \( X
# k6 \" T) g8 p' u2 b(图1:来自pxhere.com)
7 y/ N0 M/ P; e2 h, d9 l- C* @) w5 O
Blockstream曾在2018年初的时候发布了一份关于MuSig的论文,这是一种Schnorr签名方案,总的来说,这种签名方案的一些特征是非常好的,但其也存在着一些让人讨厌的其他特征。
( H  K1 G" x1 b6 H
9 Z2 E! [$ E) k0 Q+ t- \$ C7 P" c1.椭圆曲线数字签名算法(ECDSA)3 a4 @7 j3 _, U- F
首先,我们需要明白,比特币目前使用的是ECDSA椭圆曲线数字签名算法,要对消息m进行签名,我们需对其进行哈希操作,并将此哈希视为一个数字:z = hash(m)。我们还需要一个随机或随机查找的数字k。我们不喜欢信任随机数生成器(存在太多的故障,很多漏洞与糟糕的RGN有关),因此,我们通常会使用 RFC6979,并根据我们的秘密和我们要签名的消息,计算确定性K值。
0 |4 c( ?7 X2 e  u- C
- f" @4 H9 z2 {  B3 k使用私钥pk,我们可以为包含两个数字的消息m生成签名:r(随机点R的x坐标 = k×G) 和s = (z+r?pk)/k。然后,使用我们的公钥P = pk×G,任何人都可通过检查点 (z/s)×G+(r/s)×P的x坐标等于r,来验证我们的签名。, X9 Z/ @" N2 d6 `1 g
(图2: ECDSA算法的可视图)8 _( U6 l5 [6 U/ C/ d* |. q% ~# n

8 }/ d7 n7 K# J  A0 D9 p$ b. h这个算法很常见,也很棒,但它也是可改进的。首先,签名验证包括反转(1/s)和两点乘法,这些操作的计算量非常大。在比特币中,每个节点都必须验证所有交易。这意味着当你广播一笔交易时,数千台计算机将不得不验证你的签名。而简化验证过程将是非常有益的,即使签名过程会更加困难。
- L: S9 J* n2 M+ E% ]/ _( ]5 O! Y8 q4 m$ F& j
第二,每个节点必须分别验证每个签名。如果是m-of-n多重签名交易节点,则可能需多次验证相同的签名。例如,具有7-of-11多重签名输入的交易将包含7个签名,并且需要对网络中的每个节点进行7-11次的签名验证。同样,这样的交易会占用大量的空间,你必须为此支付大量的费用。
8 b/ x" _4 I" X+ p' x3 c5 Z+ ?' x5 x8 x
2.什么是Schnorr签名+ y" c, q! N2 l4 S. D
Schnorr签名的生成则略有不同,我们使用了一个点R和一个标量s来代替两个标量(r,s)。与ECDSA相似的是,R是椭圆曲线(R=K×G)上的一个随机点。签名的第二部分计算略有不同: s = k + hash(P,R,m) ? pk.这里的pk是你的私钥,而P = pk×G则是你的公钥,m是消息。然后可通过检查s×G = R + hash(P,R,m)×P来验证这个签名。2 N* c9 C  p3 G7 [1 ~9 X
(图3: Schnorr签名算法的可视图)  S% a% o; G2 u% d, h. W) m' P
; l- K2 ^: }* M- [6 {& U
这个方程是线性的,所以方程可互相加减,并且仍然有效,这就给我们带来了几大关于Schnorr签名的好处。9 @4 z0 U$ B" \% [' E7 A

1 r4 W( P; c! K) f) j( L0 _3.Schnorr签名的批量验证
% a4 |: v5 x3 H! F$ @& @1 _$ c要验证比特币区块链中的区块,我们需确保区块中的所有签名都有效。如果其中一个是无效的,我们不会在乎是哪个无效的,我们只会拒绝掉整个区块。
1 g& p4 @! R6 J
/ i1 W% d% L/ R对于ECDSA签名算法,每个签名都必须单独验证。也就是说,如果区块中有1000个签名,我们就需要计算1000次倒置和2000次点乘运算,总共约3000次繁重的计算任务。
: U; w& }. O  [; T/ q- D, t$ E' B' a
而通过使用Schnorr签名,我们可以将所有签名验证方程相加,从而节省一些计算能力。对于有1000个签名的区块而言,我们需验证:
) N  i; _% `+ V9 q& m( f! _$ u# u& H( [- m
(s1+s2+…+s1000)×G=(R1+…+R1000)+(hash(P1,R1,m1)×P1+ hash(P2,R2,m2)×P2+…+hash(P1000,R1000,m1000)×P1000)9 k0 G8 @4 N$ q/ m8 J5 q7 h

6 G( h$ `. g0 }- D+ E3 P这里我们有一堆加法(在计算能力上几乎是免费的)以及1001次点乘法。我们需要为每个签名计算大约一次繁重的计算。
1 G* Z' B. Q( g% W; q, I(图4:两个签名的批验证图,由于验证方程是线性的,只要所有签名都有效,几个方程的和就有效。我们节省了一些计算能力,因为标量和点加法比点乘法容易得多)( X! ^: U0 Q: i1 |

6 V5 Y  k# V6 j# w: A# Q( W4.Schnorr签名的密钥聚合1 H2 D4 x& d& }- W, G
我们希望让自己的比特币保持安全,所以我们可能希望使用至少2个不同的私钥来控制我们的比特币。比如说一个放在笔记本电脑或手机,另一个则放在硬件钱包/冷钱包。因此,当其中一个受到威胁时,我们仍然可以控制我们的比特币。
4 Q* J. d$ `9 d- y; g' B9 Z+ i* C% ^. n9 U# U
目前,它是通过2-of-2多重签名脚本来实现的,这需要在交易中包含两个单独的签名。( i* [* j  [, Y: x. i( ?# ~

, F! W0 q, ~8 s& R7 R6 H. i  }而使用schnorr签名,我们可以使用一对私钥 (pk1,pk2),并生成一个与共享公钥P=P1+P2=pk1×G+pk2×G对应的共享签名。要生成这个签名,我们需要在每个设备上选择一个随机数(k1,k2),生成一个随机点Ri=ki×G,将它们相加以计算一个公共哈希(P,R1+R2,m),然后从每个设备(si = ki + hash(P,R,m) ? pki)中获取s1和s2。然后我们可以将这些签名相加,并使用一对(R, s) = (R1+R2, s1+s2)作为我们对共享公钥p的签名。其他所有人都无法说出它是否是聚合签名,它看起来与普通schnorr签名完全相同。
$ e, H0 g% V2 D6 Y6 u6 V1 g4 g3 w
/ {% e9 i! s6 J0 O7 O0 o# B) u这种构造有3个问题,第一,从用户界面的角度来看,要进行交易,我们需要进行几轮通信,计算公共R,然后-签名。有了两个私钥,只需一次访问冷钱包就可以完成:我们在在线钱包上准备一个未签名的交易,选择k1,将R1=K1×G与未签名的交易一起记下。然后我们将这些数据传送到冷钱包并签名。因为我们已经有了R1,所以我们可以一次性在冷钱包上签署交易。从冷钱包中,我们得到了R2和s2,并将其传输回在线钱包。在线钱包使用之前选择的(k1, R1)签署交易,结合签名并广播签名交易。这与我们现在的情况非常相似,但一旦添加第三个私钥,一切就会变得更加复杂。比方说,你有一笔财富,它是由10个私钥控制的,它们存储在世界各地不同的安全位置,然后,你需要进行一笔交易。目前,你只需要浏览所有这些位置一次,但如果你使用的是密钥聚合,则需要执行两次,以组装所有RI,然后签名。在这种情况下,最好在不进行聚合的情况下保留单独的签名,然后我们就需要3轮通信:! y+ u- V1 b8 Z7 ^% L: ~
选择一个随机数ki和相应的Ri=ki×G,然后只告诉每个人其哈希ti=hash(Ri),这样每个人都可以确定在学习了其他随机数之后你不会改变主意;把所有的数字汇总起来,计算出共同的R;签名;
' c- C" U  e6 m8 v- [9 J# d. n* I
7 ~8 n2 o6 i: b( Y7 T第二个问题是已知的恶意密钥攻击。无论是在论文还是这篇文章中,都有很好的描述,所以我不想详细讨论。其想法是,如果你的某个设备被黑客攻击(比如说,你的在线钱包),并假装其公钥是(p1-p2),那么它可以用它的私钥pk1控制共享资金。一个简单的解决方案是,在设置设备时,需要使用相应的私钥对公钥进行签名。2 s4 V3 F& t  y, ~+ N; a

5 v1 p; n; n9 q8 _% n' e还有第三个重要问题。不能使用确定性k进行签名。有一种简单的攻击方式,如果你使用确定性K,它允许黑客获得我们的私钥。攻击看起来会是这样的:有人入侵了我们的笔记本电脑,并完全控制了两个私钥中的一个(例如pk1)。我们可能觉得是安全的,因为我们的比特币需要来自pk1和pk2的聚合签名。因此,我们尝试像往常一样进行交易,准备一个未签名的交易和R1值,将它们转移到我们的硬件钱包并在那里签名。然后返回(r2,s2)和……我们的在线钱包发生了一些事情,它无法签名和广播。我们再次尝试,但我们被黑的电脑这次使用了另一个随机值R1'。我们再次与我们的硬件钱包签署相同的交易,并将值(r2,s2)带回我们被黑的电脑。然后,糟糕的事就发生了,我们的比特币就丢失了。  B7 e% {/ @' V- u9 h/ Y# h7 t

$ N3 R0 C8 R6 J/ k- ]" y在这个攻击中,黑客为同一笔交易获得一对有效的签名: (R1, s1, R2, s2) 和(R1', s1', R2, s2'),这里R2是相同的,但R = R1+R2和R'=R1'+R2是不同的,这意味着黑客可以计算我们的第二个私钥:
% w: Y; k+ _0 @& w' |) \/ h( g0 v
6 Q$ J5 {5 U! d4 e9 v" _$ d6 W* Ks2-s2'=(hash(P,R1+R2,m)-hash(P,R1'+R2,m))?pk2 and pk2=(s2-s2')/(hash(P,R1+R2,m)-hash(P,R1'+R2,m))。
5 R% @9 f1 M8 ?9 f) A$ ]9 E% ~& G, k1 ^0 ?' ^" o+ r+ ?% `$ x
我发现这是密钥聚合最不方便的特性:我们需要在任何地方使用好的随机数生成器来使用密钥聚合。
* e: T7 w6 }9 O. a1 X! h* G
' D& Z( j( h: {6 w6 r/ R1 l5.MuSig:由Blockstream提出的Schnorr签名方案2 T" M1 U& U5 b% E! H- f) f

7 X+ D% Z* `" F$ w% U# g" D8 Y  `* hMuSig方案解决了其中一个问题,它使得密钥盗窃攻击成为了不可能。目标是将多个参与方/设备的签名和公钥聚合到一个参与方/设备,但不能证明你拥有与公钥对应的私钥。0 p1 T8 i. k9 h2 {* W

4 p9 M5 n6 D' h8 a$ I. j聚合签名对应于聚合公钥。但是,我们不只是将所有联合签名者的公钥相加,而是将它们乘以某个因子。聚合的公钥将是P=hash(L,P1)×P1+…+hash(L,Pn)×Pn。这里L=hash(P1,…,Pn)是一个取决于所有公钥的公用数字。这种非线性特性可以防止攻击者构造一个不好的公钥,例如在恶意密钥攻击当中。尽管攻击者知道自己的哈希(L,Patk)×Patk应是什么,但他不能从中派生Patk,这和从公钥派生私钥是相同的问题。7 T0 j# ]4 f+ e; Z5 T

2 s2 L9 @5 S3 h! r/ l剩余部分和前面的情况非常相似,为了生成签名,每个联合签名者选择一个随机数ki,并与其他人共享Ri=ki×G。然后将所有这些随机点相加到一个R=R1+…+Rn,生成签名 si = ki + hash(P,R,m) ? hash(L,Pi) ? pki。这个聚合签名是 (R, s)=(R1+…+Rn, s1+…+sn) ,验证方程与之前相同:s×G = R + hash(P,R,m)×P。
. _4 m. C) o' A6 A, h' l( M$ i" I- i: v9 a0 `0 ]- I5 F; `* V
6.默克尔多重签名(Merkle Multisig)0 k- I3 z; M4 ]$ `' S6 Y
你可能会注意到,MuSig和密钥聚合都需要所有签名者签署一笔交易。但是,如果你要的是一个2-of-3的多重签名呢?在这种情况下,是否可以使用签名聚合,或者我们必须使用我们通常使用的OP_CHECKMULTISIG和单独的签名?
0 \) ]+ h+ k$ B) z$ w0 a/ m2 ~* F& |4 b% r& N3 K
嗯,这是可能的,但是协议有一个小的改变。我们可以开发一个类似OP_CHECKMULTISIG的新op码,它检查聚合签名是否与公钥的默克尔树中的特定项对应。
7 u- [9 i; [1 i' B9 _
0 |4 Y: X7 C7 g: u4 y9 [# z" f/ q例如,如果我们使用带有公钥p1、p2和p3的2-of-3多重签名,那么我们需要为所有可使用的组合构造一个聚合公钥的默克尔树: (P1, P2), (P2, P3), (P1, P3) ,并将根放到锁定脚本中。为了使用比特币,我们提供了一个签名以及一个证明我们的公钥在默克尔树上的证据。对于2-of-3多重签名,默克尔树中只有三个元素,证明将由两个哈希组成,其中一个是我们想要使用的哈希,另一个则是其邻哈希。而对于7-of-11的多重签名,已经有11!/7!/4!=330种可能的密钥组合,而证明需要8个元素。一般来说,证明中的元素数量几乎与多重签名种的密钥数成线性关系( log2(n!/m!/(n-m)!)。# n" I, g4 G# `
! p& A* T) L4 ^
但是,有了公共密钥的默克尔树,我们不局限于m-of-n的多重签名。我们可以用任何我们想要的公共密钥制作一棵默克尔树。例如,如果我们有一台笔记本电脑、一部电话、一个硬件钱包和一个恢复种子,我们可以构建一个结构,允许我们将比特币与一台笔记本电脑、一个硬件钱包、一部电话和一个硬件钱包或仅与一个恢复种子一起使用。只有当你用分支和其他东西构造更复杂的脚本时,仅使用OP_CHECKMULTISIG会是不可能的。9 A+ [) i1 L& s9 m

6 ~0 g) F8 O) B1 z& c2 o; F& {) j(图5 : 聚合公钥的默克尔树,不仅仅是m-of-n多重签名)/ r% P) `8 p6 U0 N  B

( `; Q/ `) L$ ]" o9 u* j7.什么是BLS签名方案
% h; b: G( }4 }5 d( T  j. a/ ]BLS签名方案最初是由斯坦福大学教授Dan Boneh等人于2001年就提出的一种签名方案(原论文地址:5 j9 I/ y# {) W& K8 Q/ f
https://www.iacr.org/archive/asiacrypt2001/22480516.pdf),而在2018年,Boneh教授还与IBM研究机构的Manu Drijvers等人更新了这种签名方案
. f) {! k6 Y" s# Xhttps://eprint.iacr.org/2018/483.pdf)。
+ E- N( Q+ S# X  E( K  P( P0 X7 [- N) `
Schnorr签名方案是非常了不起的,如果我们做得对,我们可以将交易中的所有签名和公钥组合为一个密钥和一个签名,没有人会发现它们对应于多个密钥。区块验证也可以变得更快,因为我们可一次性验证所有签名。但它也存在着一些问题:
$ c) Q2 D- Q1 m9 P多重签名方案需要多轮通信,这会使冷存储变得非常烦人;对于签名聚合,我们必须依赖随机数生成器,我们不能像在ECDSA中那样确定地选择随机点R;m-of-n多重签名方案是棘手的,我们需要制作一个公共密钥的默克尔树(merkle tree),对于大数的m和n来说,这颗默克尔树可以变得相当大;我们不能将区块中的所有签名组合为单个签名;; a5 x/ W0 b* w/ n6 n

0 z0 W2 |" j( L: Z( {3 m) RBLS签名可修复上述所有问题,我们不需要随机数,区块中的所有签名都可以组合成单个签名,m-of-n类型的多重签名非常简单,我们不需要签名者之间进行多轮通信。此外,BLS签名相比Schnorr签名或ECDSA签名要小2倍,其签名不是一对,而是一个单曲线点。听起来似乎很棒,对吧,让我们看看它是如何工作的。9 P8 z6 g- O  l

, _% ]& T: Z5 R& R$ S, R8.BLS签名的魔法9 ]5 |/ R0 \. V. i7 b/ s8 e1 [% R
在开始之前,我们需要两个新的结构:哈希到曲线(hashing to the curve)以及曲线配对(curves pairing)。  K. l; f5 x  X# P% E" P8 y

2 i- z* J# [, a哈希到曲线(hashing to the curve)' L+ `! u% I: p+ U1 r+ s( w% W
4 D" |1 ~' e' _# x* }3 @
通常对于ECDSA签名以及Schnorr签名,我们会哈希一则消息,并在签名算法中使用此哈希作为一个数字。而对于BLS签名,我们需要一个稍修改过的哈希算法,它直接哈希到椭圆曲线。最简单的方法是像往常一样哈希一则消息,并将结果视为点的x坐标。椭圆曲线(就像我们在比特币中使用的曲线)通常有2???个点,而SHA-256哈希算法也给出了一个256位的结果。但是对于每个有效的x坐标,有两个点具有正和负的y坐标(因为如果(x,y)在曲线y?=x?+ax+b上,则 (x,-y)也在曲线上)。这意味着我们的哈希有大约50%的概率为一些x找到两个点,另有50%的概率无法找到。+ V, b  k; l0 l8 i* E5 [; {
(图6 : 在有限域模23上定义的椭圆曲线y?=x?+7的玩具哈希例子。只有一半的X坐标有点,这里只有第三次尝试是成功的)
, L% o) D% G" o; }$ C
9 @# R  l3 |  b/ j# a  _2 S要为任何消息找到一个点,我们可尝试哈希几次,方法是在消息中追加一个数字,并在失败时递增。如果hash(m||0) 找不到点,我们尝试hash(m||1)、hash(m||2)等等,直到最后得到一个匹配的点。然后我们选择两个对应点中的一个,比如y较小的那个,然后我们就完成了。; L! @) ?; Y9 p0 R, y
, t) T, y2 j3 C7 E4 M4 E
曲线配对(curves pairing)
: l$ m  W! z1 X+ }: W( i$ Q
! S2 k# [6 _/ f4 y& L我们需要的另一件事是一个非常特殊的函数,它在一条曲线(或两条不同的曲线)上取两点P和Q,并将它们映射至一个数字:/ k8 A: U/ ~# T2 e
1 i7 Q6 t+ ]6 h
e(P, Q) → n.
4 E6 l3 f# t% e1 v+ Z5 e  B0 l. i6 a, I* J) I: |
我们还需要这个函数的一个重要属性。如果我们有一些秘密数字x和两点P和Q,不管我们用哪个点乘以这个数字,我们都应得到相同的结果:8 N7 j. r1 z+ o  M
即:e(x×P, Q) = e(P, x×Q).
/ u& C3 K: D3 ?- n( o" u4 k0 ^; v
+ v+ l1 P' R' D) b6 P# o* t# |基本上,我们需要能够在不改变结果的情况下交换两个参数之间的点乘数。更普遍地说,所有这些互换都应产生相同的结果:/ z( Q, F& z1 ?/ H( x# e
e(a×P, b×Q) = e(P, ab×Q) = e(ab×P, Q) = e(P, Q)^(ab)8 \6 F6 \! Q4 k/ G2 n" R0 `
3 C8 K0 u4 a! ^) _" I
我不想描述这个函数是如何精确工作的。基础数学相当复杂,如果你想知道所有令人讨厌的细节,我建议你阅读这篇文章和其中的参考资料。如果你想更深入一些,那这篇论文
9 f( U* v: I7 I; ehttps://crypto.stanford.edu/pbc/thesis.pdf)会比较适合你。目前,我们只需要接受这种函数的存在,它们不会泄露关于我们的秘密数字X的任何信息。
1 t* _! c7 N. i5 y. X5 ~
3 e0 W" h* S* k- M' `' |; p一个重要的注意项是,我们不能在这里使用任何椭圆曲线(特别是标准比特币曲线secp256k1不起作用)。为了使这个函数高效和安全,我们必须使用来自“友好配对”家族非常特殊的曲线。
9 y. @: V2 i+ ^/ \' `; c" l& W, ^( }4 p- |" \1 ~
9.BLS签名方案的具体原理2 n: O! j* O% V+ y' S! N: N
现在我们有了构建BLS签名所需的一切。和往常一样,我们的私钥是一些秘密数字pk,我们的公钥是P = pk×G,我们要签名的消息则是m。: G' [' c9 D' ?4 ^
3 a) o- k( A5 r1 `1 z/ L/ G
为了计算签名,我们将消息哈希到曲线H(m) ,并将结果点乘以私钥: S = pk×H(m).就是这样了!没有别的东西,没有随机数,没有额外的操作,只有哈希乘以私钥!我们的签名只是曲线上的一个单点,在压缩序列化格式中只需要33个字节!  R2 c: _% Q5 E7 k
(图7 : BLS签名生成,为了获得签名,我们将消息的哈希值乘以私钥)2 Q' \8 ?2 l, ~0 R  o2 E8 G; b
8 D) W* ]/ F% Y1 p9 c/ ~
要验证此签名,可以使用我们的公钥P并检查:
, \+ a) }9 x- o& l: B" se(P, H(m)) = e(G, S)( n* ?9 U: M8 o# Q1 W7 X% n

/ \' J! Y) t0 w+ `( a( A0 f' I5 ^这为真,因为上面描述的配对函数的优良特性:
" I' T# g9 O) oe(P, H(m)) = e(pk×G, H(m)) = e(G, pk×H(m)) = e(G, S)& @2 k; |: B3 f- ~# l: N+ {4 ?6 U
(图8 : BLS签名验证,我们只需要检查公钥和消息哈希是否映射到与曲线生成器点和签名相同的数字)
9 i! B) r+ u) K4 H9 U, G6 L, N6 l& \! G$ M/ m/ c
这个签名方案既美观又简单,此外也有几个非常好的功能,特别是对比特币而言。% Q+ D* i! m4 n( E3 `: B

0 ?1 S* g+ t+ Z10.BLS签名的签名聚合
3 U: g0 `4 e0 z# c  J9 o* o3 \" Z现在,让我们组合区块中的所有签名!假设我们有一个包含1000笔交易的区块,每笔交易都包含一个签名Si、一个公钥Pi以及一个签名为mi的消息。如果我们可以合并所有签名,为什么要存储所有的签名?毕竟,我们只关心区块中的所有签名是否有效。聚合签名将只是区块中所有签名的总和:2 U; n8 C/ o7 x9 e( e0 \
S = S1+S2+…+S1000- ^1 q8 [* w" h7 N5 m) c
$ |: C9 S# T% [( ~: G) f) \
要验证区块,我们需要检查以下等式是否成立:
+ \* V7 S. k- ~e(G, S) = e(P1, H(m1))?e(P2, H(m2))?…?e(P1000, H(m1000))1 p0 z# }" L0 R# S+ X9 O$ P8 W
# V1 A# _; S; K/ D* W4 C
如果你仔细看,你会发现这是真的:
+ m6 l" |  u& g9 Z; f! ]% @; Ye(G, S) = e(G, S1+S2+…+S1000) = e(G, S1)?e(G, S2)?…?e(G, S1000) = e(G, pk1×H(m1))?…?e(G, pk1000×H(m1000)) = e(pk1×G, H(m1))?…?e(pk1000×G, H(m1000)) = e(P1, H(m1))?e(P2, H(m2))?…?e(P1000, H(m1000))
* t1 o3 y4 M7 p. T, R1 J8 G
4 f0 E( g, S* E我们仍然需要知道所有的公钥并计算1001个配对函数,但是至少区块中的所有签名只占用33个字节。签名聚合可以由矿工完成,并节省区块大量的空间。# J, f4 Y1 ]) g. I* r. a

$ n; {* J. K8 b11.BLS签名的密钥聚合和n-of-n多重签名4 `( \+ c( |3 w' `3 h/ Q. J
如果我们使用多重签名地址,我们将使用不同的密钥签署相同的交易。在这种情况下,我们可以像在Schnorr签名方案中那样进行密钥聚合,在Schnorr中,我们将所有签名和所有密钥组合到一对密钥和一个签名上。以常见的3-of-3多重签名方案为例(对于任何数量的签名者都可以这样做)。* [) C9 O# l2 Q* Z- s- W

) L) U+ }$ m. L6 P' r/ A组合它们的一个简单方法,是将所有签名和所有密钥添加到一起。结果将是签名S=S1+S2+S3和密钥P=P1+P2+P3。很容易看出,同样的验证方程仍然有效:% b( i1 j' g  J+ C  q8 W
+ L# x+ z  R1 [7 ^! e2 C0 `
e(G, S) = e(P, H(m))4 S- {4 r( r: A/ Y0 m
e(G, S) = e(G, S1+S2+S3) = e(G, (pk1+pk2+pk3)×H(m)) = e((pk1+pk2+pk3)×G, H(m)) = e(P1+P2+P3, H(m)) = e(P, H(m))$ M6 Z8 s. }! T% W1 r

3 n, V+ l8 w7 x9 T和Schnorr签名方案一样,运用BLS签名需要保护自己免受流氓密钥攻击。我们可通过要求每个联合签名者证明他们具有的公钥的私钥(通过签名他们的公钥),或者我们可以在方案中添加一些非线性元素,使恶意密钥攻击成为不可能。我们不是简单地将所有的密钥和签名相加,而是将它们乘以一个特定的数字,然后再相加:/ t. X4 O) h  u* T1 l

3 k4 y; Z( O$ K" SS = a1×S1+a2×S2+a3×S31 O4 d2 Y) s9 T6 j3 q  d0 s
P = a1×P1+a2×P2+a3×P3
3 w6 f8 i) i1 L. R  S5 S. C' p) y1 T# t& g' V# T) @0 D# y
在这里,签名和密钥的系数是根据签名者的公钥和所有其他公钥来确定计算的:
0 ]  |$ Q3 U$ wai = hash(Pi, {P1,P2,P3})% ^+ U& p( @' q( L; A4 e
4 f( u$ s8 E- l4 ^5 h: ^% \( D
例如,它可以只是签名者公钥和用于签名的整个公钥集的级联:ai = hash(Pi||P1||P2||P3).7 c9 d! s' ]* l2 `  H) w
" k" [; R% h6 r# E
同样的验证方程仍然有效。在证明中会有额外的系数ai,但逻辑仍然存在。/ @  A+ f% P) f, }! j

/ G6 O# z4 y+ K0 K2 Y# W; M- k$ c, ^这个方案的好处在于,你不需要在设备之间进行多轮通信。你只需要知道谁是其他签名者。这比Schnorr签名的3轮多重签名方案要简单得多。它也不依赖任何随机性,它是一种完全确定的签名算法。
: s# O' Y2 g9 j; C+ {* d3 K: }. ?7 l  H/ S" R8 [" S5 ?; m5 b
12.子群多重签名方案(m-of-n multisig)7 r2 m1 Z, D; K$ C
通常,我们不会想用n-of-n的多重签名方案,我们更喜欢使用m-of-n(比如说2-of-3)的多重签名方案。我们不想因为丢了一把私钥就把钱给弄丢。在这种情况下,最好使用密钥聚合。有了Schnorr签名方案,我们就可以通过使用公共密钥的默克尔树来做到这一点,它不是最有效的办法,但很管用,坏处在于一旦m和n值很大,默克尔树(merkle tree)的大小就会成倍放大。
, `0 U' \& @, p
: J* E, @) m( n+ E* F2 r3 |8 O5 z而对于BLS签名方案,还有另一种方法。不过也没那么简单,我们需要一个普通的哈希函数,它输出一个数字hash(x),以及一个到曲线的哈希 H(x)。当我们决定使用多重签名时,我们还需要一个“设置”阶段,但在此之后,我们不再需要通信,我们只需要签名来签署任何数量的交易。( v) I" [2 N1 Y7 T( Y/ Q

. I: S" @5 x; M' `再次,我将使用一个简单的例子,我们希望构建三个不同设备上存储密钥的2-of-3多重签名方案,但它可以扩展到任何值的m和n。
. u; N2 P: |% X$ I: Z+ Y
3 U1 D1 D. F$ J  Q: W' r# O6 @: B设置阶段
/ x& |0 G: Y3 C0 X2 J6 |& p我们的每个设备都有一个签名者编号i=1,2,3,代表其在集合中的位置,一个私钥pki以及一个对应的公钥Pi = pki×G。这里计算聚合公钥的方式与之前完全相同:
+ F. x# m8 i0 }3 F
, B% \( L4 a5 q2 }; s6 l) X$ ~P = a1×P1+a2×P2+a3×P3, ai = hash(Pi, {P1,P2,P3})
; x) i6 H9 p. ], Z" Z4 ]& Z% X! m( K! C
现在,每个设备都需要签名,而编号i是我们的聚合公钥的成员(对于每个i),聚合这些签名并将结果保存到相应的设备上:
* y/ {. f; I" o* z5 Z0 o) {* k. O# A7 A/ ^. f1 |
MKi = (a1?pk1)×H(P, i)+(a2?pk2)×H(P, i)+(a3?pk3)×H(P, i)
0 }0 K$ D6 H* ]( x+ L' Z1 E9 n' z: q3 C5 `% e% R
这个签名我们称为“成员密钥”,稍后我们将使用它进行签名。每个成员密钥都是消息H(P,i)的有效n-of-n签名,这意味着:
9 ~9 e6 \2 g; B2 _1 M- }. Q5 O* u% A- ^2 J* a1 C4 p
e(G, MKi)=e(P, H(P,i))
( r0 Z; D9 ]2 ?# u6 d
* [  h4 O4 g6 r& l0 f; t记住这个方程,我们以后会用到的。它将用来证明我们是多重签名方案的有效参与者。
/ d4 m5 J# I+ f/ Q9 u
" z8 H) B- [" l签名
7 K" t( n0 @, S现在假设我们只想用密钥pk1和pk3签署一笔交易。我们生成两个签名S1和S3:
2 [+ j3 L  O" q$ b2 t8 g/ C
# I, i/ y9 f" d/ n3 YS1 = pk1×H(P, m)+MK1, S3=pk3×H(P, m)+MK3
5 C" e; U8 S" R6 O
3 B5 o7 e" S- x, T: P并将它们相加以获得单个签名和密钥:) b) x0 ^9 Y- J! l( |
(S’, P’) = (S1+S3, P1+P3)
, e  f9 S3 n6 G5 f& @: e& E
2 l2 G3 o/ ]# R0 p9 F5 b1 n. Q我在这里写为P’和S’,来强调这个密钥和签名只由签名者的一个子集签名,它与P不同,P是所有签名者的聚合密钥。要验证这3个签名中的2个,我们需要检查:
0 U+ j0 d5 p% w& y, f8 l! W- B4 T$ A) \
e(G, S’) = e(P’, H(P, m))?e(P, H(P, 1)+H(P, 3))
% s4 y3 }3 Q2 G/ u2 Y# I- ^1 W6 x4 ?6 b% {1 j" F6 ]( v; l
我们记得成员密钥MK1和MK3 是由聚合密钥 P签名的消息H(P, 1)及 H(P, 3)的有效签名,因此:" v' t8 g) w0 s6 U) ^2 a% D$ n
4 |( `, F* ~8 j; v3 P5 t
e(G, S’) = e(G, S1+S3)=e(G, pk1×H(P, m)+pk3×H(P, m)+MK1+MK3) =e(G, pk1×H(P, m)+pk3×H(P, m))?e(G, MK1+MK3)=e(pk1×G+pk3×G, H(P, m))?e(P, H(P, 1)+H(P, 3))=e(P’, H(P, m))?e(P, H(P, 1)+H(P, 3)), k  w& l  w8 M2 A% l' q+ Z

* r7 P2 x7 v* ?; o! Z, [4 n7 {/ c. M就是这样,要比n-of-n复杂一点,但仍然是可被理解的。- ^/ R. ], Q* x; P  r3 |
; ?% z8 t7 o# V+ K; v6 O1 j  N
13.BLS签名可能的应用场景% A, _9 i3 [6 V- o  K2 j
要实现这个多重签名方案,我们需要将资金发送到与聚合公钥P对应的地址,并表示我们至少需两个签名。在比特币脚本语言中,锁定脚本可能如下所示:* W# k; N) G& a) r

4 r: H* {5 H- ?; m' P/ [3 e5 U6 uOP_2
* a0 y: |6 t) A' H- r0 SOP_CHECK_BLS_MULTISIG' m+ r: ]0 o4 E
8 k. E4 f. J) ]" w  j: X3 u& o, O
这里,OP_2告诉我们需要两个密钥来签署消息。我们不会说任何地方总共就只有3个签名者,所以不能说它是2-of-3还是2-of-100多重签名地址。
7 n+ R2 A- A+ N/ p1 B: {5 j$ _, U
, j" C  s. g; f9 f' a! O为了使用这个输出,我们需要在我们的案例1和3中提供参与签名者的密钥P’、签名S’以及索引。解锁脚本可能如下所示:( u7 n  u4 N! k# Z
/ R7 T5 Q) W" p+ v- y
OP_1 OP_3  
; c4 x5 S  @. p( t8 K4 o, N; S6 }. E
结合这些脚本,可以给我们提供所有必要的信息。从OP_1和OP_3,我们知道我们需要计算哈希H(P, 1)和H(P, 3),然后我们就拥有了验证交易所需的一切。
% s+ X7 c5 D1 I, h% C" l7 v) S% l9 L" ~4 x3 {
这意味着对于任何m和n,我们只需要:
: U, Z9 l/ U" e8 |锁定脚本中的一个聚合公钥P;参与签名者的一个聚合公钥P’一个聚合签名;带有签名者索引的m数字;% k' t3 l- T  ^' N! U- D6 j

4 J2 @& ^6 r. e3 E+ B但它也并非完美… 通常我们只使用一次地址(我们使用像bip32这样的密钥派生来生成新的私钥和地址),但是对于每一组新的私钥,我们也需要一组新的成员密钥。一种不用每次都运行设置阶段的方法是生成一组密钥,比如1000个密钥,并获得相应的成员密钥。毕竟,它们只有32字节大小,然后,只有在使用了所有1000个地址时,我们才需要再次运行设置阶段。3 m0 e6 {( v3 e- [. [7 J- p4 R/ V2 s
0 U0 C/ g  q9 X7 r
14.BLS签名的弊端:配对效率低下/ y) O/ T5 Y! @# f1 X' {
正如本文以及很多技术大佬在Twitter上所指出的,上面的讨论没有谈到一个重要的部分,而它可能是BLS签名方案最大的缺陷。5 Z& B+ L* W9 s- s
( |. J/ ^4 g$ S0 `0 k
BLS签名的配对是很难的,我们认为神奇的函数 e(P, Q)是有效和安全的,但事实并非如此。9 r. z$ Z" T* K3 Z$ e
% K( u% k3 `9 p. b0 T2 |( }4 }( b
BLS签名验证要比ECDSA签名验证的难度大上几个数量级。对于具有1000笔交易的整个区块的签名聚合,仍然需要计算1000次配对,因此验证一个区块中的一个小签名,可能比验证1000个单独的ECDSA签名需要更长的时间。这里BLS签名能够实现的唯一好处,在于我们可以在区块中容纳更多的交易,因为聚合签名只需要大约32个字节。* }+ P$ h9 q8 {$ S
与BLS签名不同,Schnorr签名是非常有效的,它们可以一起验证,而且这个过程比ECDSA效率高3倍。
! X8 j7 A1 r" k8 n) x/ N: r. z0 o9 \) ^2 l1 X/ Q9 f
另外,配对函数是复杂的,如果我们不够小心,它会成为我们的敌人。一方面,我们希望配对能够有效地、更快地验证签名,另一方面,我们不希望透露任何关于我们密钥的信息。这两大需求相互竞争,我们需要非常小心地选择对配对友好的曲线。/ _0 Q: l% G1 l6 b+ O

  M: W$ i' B$ ]/ h# o实际上有一种针对椭圆曲线加密系统的攻击方法称为MOV攻击(以Menezes, Okamoto和Vanstone命名),它允许使用我们的魔法配对函数来降低系统的安全性。所以我们真的需要小心。
. Z5 ^$ ]# A9 L, A然后问题就出现了:什么对我们而言会更重要?, V, B% H+ |1 A
  W$ i: g) S4 r7 Y! n: a
15.结论
, n0 o7 u$ }& \$ _7 fSchnorr签名和BLS签名方案都有自己的独特之处,前者的主要缺点在于需要额外的通信回合,以及不适合较大值m和n的多重签名方案,后者的验证时间则是最大的弊端,两者共同存在的好处都是可聚合签名,节省区块空间。
BitMere.com 比特池塘系信息发布平台,比特池塘仅提供信息存储空间服务。
声明:该文观点仅代表作者本人,本文不代表比特池塘立场,且不构成建议,请谨慎对待。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

成为第一个吐槽的人

123458275 小学生
  • 粉丝

    0

  • 关注

    0

  • 主题

    1