随机数对签名的重要性与伪签名的构造

关于签名算法的一些基本变量定义:

  • G为椭圆曲线
  • 随机值k,R=kG
  • m,待签名消息哈希值
  • 私钥x,公钥P=xG
  • H(),哈希函数
  • r = R.x,表示r为R的x坐标值

Schnorr

  • 签名:(R, s)
  • 生成签名:s = k + H(R||P||m)*x
  • 验证签名:sG = R + H(R||P||m)P

ECDSA

  • 签名:(r, s)
  • 生成签名:s = m/k + r/k*x
  • 验证签名:sR = mG + rP
    • 先求得R值:R = m/s*G + r/s*P
    • 再求得r值:r = R.x ,即R的x坐标值,验证r是否一致

随机值k选取的重要性

Schnorr与ECDSA均对随机值强依赖,若任意两次签名之间采用了相同的随机值k,则暴露出私钥。下面我们演算在随机值相同情况下,各个算法暴露私钥的过程。

Schnorr暴露私钥过程

1
2
3
4
5
6
7
8
9
10
11
12
13
两次签名,随机值k相同,同一个把公钥P,两次签名消息分别为:m1, m2。
令 e1 = H(R||P||m1), e2 = H(R||P||m2)

s1 = k + H(R||P||m1)*x = k + e1*x
s2 = k + H(R||P||m2)*x = k + e2*x

有两个签名:(R, s1), (R, s2)

s1 - s2 = k + e1*x - (k + e2*x)
= (e1 - e2)*x

那么私钥就可以得出:
x = (s1 - s2) / (e1 - e2)

ECDSA暴露私钥过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
两次签名,随机值k相同,同一个把公钥P,两次签名消息分别为:m1, m2。

s1 = m1/k + r/k*x
s2 = m2/k + r/k*x

有两个签名:(r, s1), (r, s2)

第一步,将上述两个等式相减,先暴露出该随机值k,有:
k = (s1 - s2) / (m1 - m2)

根据k值,计算出其对应的r值:
r = R.x = (kG).x

第二步,反推出私钥:
x = (s1 - m1/k)*k/r 或
x = (s2 - m2/k)*k/r

根据上述过程,得出结论:相同私钥对任意数据签名,若任意两次签名采用相同的随机值,则立即暴露出私钥。

对于软硬件钱包来说,其随机数发生器将是非常重要的基石,绝不能出故障。

伪签名问题

ECDSA伪签名

之所以说是伪签名,因为是可以验证通过的签名,并不是“无效签名”。CSW曾经多次使用此伎俩,制造中本聪公钥对应的伪签名,甚至骗过了一些不太清楚签名机制的人。

生成ECDSA的伪签名的过程:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ECDSA验证签名的等式为:
R = m/s*G + r/s*P

令 u=m/s, v=r/s
即 R = uG + vP

随机生成u、v的值,则有:
u'G + v'P = R'

得到 r' = R'.x,// 求X坐标
得到 s' = r'/v
得到 m' = u*s'

那么对于消息m',其签名为:(r', s')。此签名是可以验证通过的,因为验证等式是平衡的。

防范ECDSA伪签名非常简单:不可由签名方提供消息m值,必须由验证方提供。因为在伪签名里,m值是随机生成的,一旦m值由其他人提供,则签名方是无法构造出平衡等式的。或者说伪签名里签名方是提供不了m值的消息原文的。

也就是说,由你写一句话下来,交给CSW去签名,他就无法提供出中本聪公钥下能够验证的签名了。

Schnorr是伪签名免疫的

Schnorr目前是无法构造出伪签名的,因为无法构造出平衡的验证等式。在Schnorr的验证等式中sG = R + H(R||P||m)P

  • 若尝试随机等式左侧值(即随机s值),则无法找到合适的R’和m’,因为R值在哈希函数里使用了
  • 若尝试随机等式右侧值(随机生成R和m值),sG是椭圆曲线乘法,曲线除法不可逆的情况下是无法找到对应的s’值

因此Schnorr签名算法是无法构造出能验证通过的伪签名的。


参考:

Taproot简介

Taproot的概念由Gregory Maxwell在2018年01月提出,Taproot: Privacy preserving switchable scripting,这个概念主要是他研究一番MAST后,发现可以与Schnorr签名一起构成一个特别简洁的输出模式。

定义

Taproot定义了一个输出,两个执行路径的实现方式。

  • N个参与方,构成组公钥C:C = A + B + … + N
  • N + 1个参与方,构成输出组公钥P:P = C + H(C||S)G
    • 多出的一个参与方是:H(C||S),组公钥C和脚本S的组合哈希。
  • 交易输出中填入组公钥P,格式类似Segwit:[ver] [P]
    • ver=0,segwit已经使用了。Taproot可用ver=1,软分叉来实现。
  • 花费路径有两个,二选一:
    1. 签名模式:N+1参与方全部签名
      • 可以聚合出组公钥P的签名。验证签名后即可花费,无需暴露脚本
    2. 脚本模式:N个参与方里,任意一个或以上拒绝签名。则走脚本模式:
      • 提供:组公钥C、脚本S、以及脚本S相应的数据,即可以花费

示例说明

为了搞清楚运作过程,我们举例说明一下。

  • 两个参与方,分别持有公钥A、B。那么其组公钥(聚合公钥)就是:C = A + B

  • 定义脚本S:<timeout> OP_CSV OP_DROP B OP_CHECKSIGVERIFY,这个脚本的含义是“N天过后,B一个人签名就可以花掉这个输出”。

那么把上面几个东西拧一起,定义一个新的公钥:P = C + H(C||S)G

放到输出里,[version] [P]:

  • version,版本号,用于表示taproot的版本
  • P:公钥

令:d = H(C||S),则有H(C||S)G = dG = D 。那么:

1
2
3
4
P = C + H(C||S)G
= C + D
= A + B + D
= aG + bG + dG

本例其实是三个私钥在参与,只是第三个私钥d是双方共同持有的,外界仅知道组公钥P。

Taproot的签名算法采用Schnorr Signature,然后定义两个花掉此输出的方式。

方式一、签名模式花费

合作模式利用了Schnorr签名的线性特性,若P = A + B + D,则公钥A、B、D的单独签名叠加起来就是公钥P的签名。

A、B都签名(D必然签名,因为私钥d是双方共享的,任何一方都可完成D签名),那么把A、B、D三个签名加起来就是P的签名。

双方合作的话,外界看上去就是一个正常的P的签名一样,这个交易也与普通的转账完全一样。其脚本信息则完全隐蔽掉了。

当然,参与方不限定两个,可以是N个。

方式二、脚本模式花费

若A或者B任何一方拒绝签名,则无法产生(叠加出)公钥P的签名(此时仅有A+D的签名,或者B+D的签名),也就无法花费此输出。

假设A拒绝提供签名,那么B就无法合成出P的签名,但B可选择执行脚本进行花费。B需要提供的有:

  • 公钥C
  • 脚本S
  • 符合脚本S的执行数据DATA(本例是B的签名)

其他节点收到这样一笔交易后,验证过程:

1
2
3
4
5
6
7
8
9
10
11
1. 计算出私钥d: d = H(C||S)

2. 计算出d的公钥: D = dG

3. 验证公钥: P == C + D

4. 构建出完整脚本:DATA || S

5. 执行脚本,并判断结果是否为True

// 上述过程都顺利通过的,则可以花费。

通常,脚本通常都是带延迟条件的,具备一定惩罚性质,例如N天后可以花费,或者多少高度后才可以进块等。当然,也可以不设置延迟条件,脚本内容是没有任何限定的。

总结

Taproot只有在非合作时下才会暴露并执行脚本,签名模式下看上去就是一个再普通不过的公钥签名交易而已。

  • 在Taproot里,是N方参与,N通常>=2。(N=1技术上可行,但没有太大意义)
    • N方参与,则必须有N方签名,签名数量小于N则无法验证通过。缺任意签名则合作模式失败。
  • 两个分支其实已经可以覆盖很多场景,甚至大部分场景。
  • 一般来说,N方大概率都是合作的。

Taproot一个典型应用场景就是闪电网络的交易。当然,Taproot是灵活的,更多应用场景等待挖掘。


参考:

Schnorr签名介绍

Schnorr签名算法是由德国数学家、密码学家Claus Schnorr提出。并于1990年申请了专利,U.S. Patent 4,995,082,该专利与2008年2月失效。目前该算法可以自由使用。

Schnorr签名算法几乎在各个层面均优于比特币现有的签名算法ECDSA:性能,安全,体积,扩展性等方面。

Schnorr Sig可以与ECDSA使用同一个椭圆曲线:secp256k1 curve,升级起来的改动非常小。

原理

我们定义几个变量:

  • G:椭圆曲线。
  • m:待签名的数据,通常是一个32字节的哈希值。
  • x:私钥。P = xG,P为x对应的公钥。
  • H():哈希函数。
    • 示例:写法H(m || R || P)可理解为:将m, R, P三个字段拼接在一起然后再做哈希运算。

生成签名

签名者已知的是:G-椭圆曲线, H()-哈希函数,m-待签名消息, x-私钥。

  1. 选择一个随机数k, 令 R = kG
  2. s = k + H(m || R || P)*x

那么,公钥P对消息m的签名就是:(R, s),这一对值即为Schnorr签名。

验证签名

验证者已知的是:G-椭圆曲线, H()-哈希函数,m-待签名消息, P-公钥,(R, s)-Schnorr签名。验证如下等式:

sG = R + H(m || R || P)P

若等式成立,则可证明签名合法。

我们推演一下,此过程包含了一个极其重要的理论:椭圆曲线无法进行除法运算。

  1. s值的定义:s = k + H(m || R || P)*x,等式两边都乘以椭圆曲线G,则有:
  2. sG = kG + H(m || R || P)*x*G,又因R = kG, P = xG,则有:
  3. sG = R + H(m || R || P)P,椭圆曲线无法进行除法运算,所以第3步的等式,无法向前反推出第1步,就不会暴露k值以及x私钥。同时,也完成了等式验证。

组签, Group Signature

一组公钥,N把,签名后得到N个签名。这个N个签名是可以相加的,最终得到一个签名。这个签名的验证通过,则代表N把公钥的签名全部验证通过。

有:

  • 椭圆曲线:G
  • 待签名的数据:m
  • 哈希函数:H()
  • 私钥:x1,x2,公钥:P1=x1*G, P2=x2*G
  • 随机数:k1, k2,并有 R1=k1*G, R2=k2*G
  • 组公钥:P = P1 + P2

则有:

  • 私钥x1和x2的签名为:(R1, s1), (R2, s2)。
  • 两个签名相加得到组签名:(R, s)。其中:R = R1 + R2, s = s1 + s2

推演过程:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1. 令 R = R1 + R2, s = s1 + s2

2. 已知:s1 = k1 + H(m || R || P)*x1,s2 = k2 + H(m || R || P)*x2

3. s = s1 + s2
= k1 + H(m || R || P)*x1 +
k2 + H(m || R || P)*x2
= (k1 + k2) + H(m || R || P)(x1 + x2)

4. 两边同时乘以G,则有:
sG = (k1 + k2)G + H(m || R || P)(x1 + x2)G
= (k1G + k2G) + H(m || R || P)(x1G + x2G)
= (R1 + R2) + H(m || R || P)(P1 + P2)
= R + H(m || R || P)P

5. 完成证明,并从两个合作方推演至N个合作方

组公钥(Group Key),是N把公钥进行相加后的值,又称聚合公钥(Aggregation Key)。需要指出的是,参与方需要先相互交换公钥和R值,然后再进行各自的签名。

应用

若使用在比特币上,相比ECDSA会有一些额外的显著优势:

  • 更安全。目前Schnorr签名有安全证明,而ECDSA目前并没有类似的证明。
  • 无延展性困扰。ECDSA签名是可延展性的,第三方无需知道私钥,可以直接修改既有签名,依然能够保持该签名对于此交易是有效的。比特币一直存在延展性攻击,直到SegWit激活后才修复,前提是使用segwit交易,而不是传统交易。BIP62BIP66 对此有详细描述。
  • 线性。Schnorr签名算法是线性的!这点非常牛逼,基于这点可衍生出许多应用。例如,N个公钥进行签名,采用ECDSA的话,则有N个签名,验证同样需要做N次。若使用Schnorr,由于线性特性,则可以进行签名叠加,仅保留最终的叠加签名。例如同一个交易无论输入数量多少,其均可叠加为一个签名,一次验证即可。以及GMaxwell提出的Taproot/Grafroot也是基于其线性特性。

Q&A

Q: Schnorr签名是否可以用在m of n多重签名上?
A: 当然可以。多重签名只是m of n的签名数量的模式。与签名算法无关。

Q: Schnorr的组签名特性是否可以做或模拟出m of n式的签名?
A: 无法做到。组内有N把公钥,则必须对应有N个签名,缺一不可。每个人在生成签名的时候,在哈希函数里都代入的都是组公钥P。

Q: 签名机制的安全性如何衡量?
A: 主要取决于两个:1. 签名算法本身 2. 椭圆曲线。目前,Schnorr与ECDSA都用的是曲线secp256k1,这个层面一样。至于签名算法本身安全性,Schnorr目前有安全证明,安全优于ECDSA。


参考:

MAST, Merkelized Abstract Syntax Tree

写在前面的话

个人认为比特币脚本发展有三个阶段:

第一阶段,原始脚本阶段,仅有脚本。典型的有:P2PH, P2PKH。Script = scriptSig + scriptPubKey构成。所有数据都是显式的,有诸多限制的。脚本升级比较困难。

第二阶段,半自由阶段:脚本+脚本哈希。脚本形式有所突破,变得更加灵活。从P2SH开始,以及后面的Segwit,都是采用这种形式构成,特征是输出里仅存放执行脚本的哈希。这一阶段的脚本依然受到一些限制,大小和OP操作数等,但灵活性已经大大增强,可轻松软分叉升级。脚本执行过程也变为两步:1. 验证哈希 2. 执行子脚本。

  • P2SH: 输出中存放的是RedeemScript脚本哈希
  • SegWit: 输出中存放的是witness脚本哈希

第三阶段,自由阶段:脚本+脚本哈希+语法树。在第二阶段的基础上,发展为语法树。输出依然存储的是哈希,但进化为脚本语法树的根哈希值,即MAST结构。MAST突破了诸多限制,大小和OP限制等。灵活性,扩展性均极大增强,可衍生出丰富的应用场景。MAST目前依然是处于提议阶段,尚未实施。

比特币的脚本输出

比特币通过定义一系列OP码,将输入、输出的脚本压栈运行,根据运行结果判定花费行为是否合法。通常花费条件全部记录在交易的输出中。这个模式有一些缺点:

  1. 接受者很难指定条件
    • 当前主要是匹配公钥或者其哈希,然后花费时校验其签名
  2. 大脚本占用更多的UTXO空间
  3. 发送者付出更高的成本:交易体积大,通常需要付出更高的手续费
  4. 为了防止潜在的DoS攻击,比特币对脚本设定了一些限制:脚本体积小于10KBytes,或小于201个OP码
  5. 未执行的部分脚本,其非共识层面的数据都是公开的,即占用区块空间又暴露隐私

P2SH的提出,解决了上述1、2、3三个问题。P2SH分离出RedeemScript,将其20字节Hash值放入输出,花费时提供出RedeemScript并执行。但依然有520字节限制,并需要公开完整的RedeemScript。

在Segwit里,定义了一个新的脚本输出格式,P2WSH,pay to witness script hash。与P2SH非常类似,但hash是32字节的,script存放在witness字段中(而不是原来的scriptSig字段)。

Merkelized Abstract Syntax Tree

抽象语法树, Abstract Syntax Tree

抽象语法树,或语法树,计算里非常常见。通过树形来表达编程语言的一种结构。

例如这段的代码展开后的语法树:

1
2
3
4
5
6
while b ≠ 0
if a > b
a := a − b
else
b := b − a
return a

400px-abstract_syntax_tree_for_euclidean_algorithm svg

MAST也是采用树状结构的一种语法树,但更加精简:去掉条件判断,每个独立脚本就是一个叶子节点,每一个叶子节点就是一个执行分支。

MAST

MAST的作者是Johnson Lau,于2016年04月由BIP114提出,相关贡献者有:Russell O’Connor, Pieter Wuille和Peter Todd。

MAST采用Merkle树将各个分支编码进脚本(Script)。花费时,仅需要提供执行的分支脚本和相关层的hash进行验证,不执行的分支脚本无需公开。需要验证的哈希层数是O(log N)复杂度,假设可执行的脚本分支多达1024个,那么层数也仅有10层,依然可以保持很小的体积。因无需展示出所有的脚本,实际也突破了脚本大小的520字节硬限制。

值得注意的是:MAST是二叉树,但无需平衡构造,形状任意。

在BIP141(Segregated Witness)里,设定了交易输出witness program的格式:

[version][program]

这里我们设定MAST类型输出的version为1,program的大小为32字节,其中witness program即为MAST Root

欲花费这种的输入,则输入witness为:

1
2
3
4
5
6
7
8
9
10
11
12
13
Script_stack_1
Script_stack_2
.
.
Script_stack_X (X ≥ 0)
Subscript_1
Subscript_2
.
.
Subscript_Y (1 ≤ Y ≤ 255)
Position
Path
Metadata (Y|MAST Version)

这些字段可以划分为三个部分:

  1. 脚本栈元素,即入栈的操作码和数据,早于MAST Script入栈
  2. sub_script,子脚本,MAST Script会拆分为N个子脚本,拆分规则非常的自由,当然也可以选择不拆分
  3. 三个描述字段:Postion, Path, Metadata

MAST witness中各字段含义

Metadata的长度是1~5字节:

  • 第一个字节表示Subscript的数量,范围是1~255
  • 接下来的N个字节(0<=N<=4)表示MAST version版本号,若版本为零,则可省略

Path表示Merkle树路径,用于Script Hash

  • Path大小必须是32的整数倍,但不超过1024字节
  • 每个32字节,是各层与这个路径相关分支的哈希值,哈希函数是double-sha256

Position表示叶子的位置,左侧开始,从零开始计数,长度通常小于4字节。若树的深度是4,那么可选范围是[0, 2^n-1]即[0, 15]。

Script Hash的定义:

1
2
Script Hash = H(Y|H(Subscript_1)|H(Subscript_2)|...|H(Subscript_Y))
H() = SHA256(SHA256())
  • Y是一个字节的数,表示脚本数量
  • 后面紧接着是每个子脚本的哈希值
  • 把N个SubScript_n连接起来就是完整的MAST Script,这里可以自由的对MAST Script进行拆分,增强隐私性

Script Root就是脚本树的树根哈希值。

MAST RootH(MAST Version|Script Root),数据长度是固定的36字节:前4字节表示版本,后32字节是脚本树的根哈希值。执行脚本前,需要验证MAST Root值,不相等则执行失败。

MAST Root哈希值验证相等,MAST Version大于零,则脚本无需执行便直接返回成功。SigOpsCost为零,这个设定可以用于未来的脚本升级。

约定

在BIP114中所表述的MAST,其实是限制版本。广义的MAST,可以自由选择脚本组合,构成更加复杂的情况。

我们先看看在“广义MAST”下的情况,假设一个花费条件可以设定为:

1
(A or B) and (C or D or E) and (F or G)

A~G一共七个脚本,构成三个主要条件(本例都是与运算),每个条件由各子脚本再布尔运算后返回结果。七个可构成一个三层的Merkle树,2^2=4 < 7 < 2^3=8。

在BIP114里,则限定为仅可执行单一脚本分支,那么欲实现上面的花费条件,则需要展开每个可能性,一共2*3*2=12个分支,则需要构造一个四层树,2^3=8 < 12 < 2^4=16。

1
2
3
4
5
6
A and C and F
B and C and F
A and D and F
.
.
B and E and G

也就是说,即使不允许脚本之间进行组合逻辑运算,通常也不过就是树多了一层深度而已。

实现广义MAST的一个方法是组合使用几个操作码:OP_EVAL, OP_CAT, OP_HASH256。不过,OP_EVAL的引入会带来诸多问题,例如可能陷入死循环、无法做静态程序分析。

当前设计方案的一些优点:

  • SubScript位于特定的堆栈位置,可以做静态程序分析,可以统计SigOps操作数,可以提前终止脚本如果遇到非法OP等
  • 不同的参与方仅需公布脚本哈希,H(SubScript),直到花费时暴露完整脚本,带来更好的隐私性
  • 如果需要公开最终的脚本,可以组合进一个子脚本里SubScript,稍微节约一些SigOps操作数

也有一些缺点:

  • 例如需要展开各种条件,以形成某个分支
  • 创建和存储MAST可能花费一些时间和空间,但这个仅影响合约中的相关参与方,不影响其他比特币用户

MAST Version

当前的提案中允许用户自己制定版本,比起scriptPubKeyscriptSig会相对廉价一些。未定义的版本,则依然保持人人可花费的特性,可用于未来做软分叉等。新版本可放宽限制(例如放开MAST Script的10K字节限制),添加或者重定义OP码,甚至在未来引入其他脚本语言和系统。

一个示例

Calculation of MAST Root

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
Subscript:
SA = OP_1 OP_EQUALVERIFY (0x5188)
SB = OP_2 OP_EQUALVERIFY (0x5288)
SC = OP_3 OP_EQUALVERIFY (0x5388)
SD = OP_4 OP_EQUALVERIFY (0x5488)
SE = OP_5 OP_EQUALVERIFY (0x5588)
SF = OP_6 OP_EQUALVERIFY (0x5688)
SG = OP_7 OP_EQUALVERIFY (0x5788)
SH = OP_8 OP_EQUALVERIFY (0x5888)
M = OP_RETURN "Hello" (0x6a0548656c6c6f)

Hash:
//
// Script Hash
//
HA = H(0x01|H(SA)) = H(0x015acb54166e0db370cd1b05a29120373568dacea2abc3748459ec3da2106e4b4e) = 0xd385d7268ad7e1ec51660f833d54787d2d8d79b6b1809d9c1d06c9e71f7be204
HB = H(0x02|H(SB)|H(SC)) = 0x7cbfa08e44ea9f4f996873be95d9bffd97d4b91a5af32cc5f64efb8461727cdd
HF = H(0x03|H(SD)|H(SE)|H(SF)) = 0x4611414355945a7c2fcc62a53a0004821b87e68f93048ffba7a55a3cb1e9783b
HG = H(0x01|H(SG)) = 0xaa5fbdf58264650eadec33691ba1e7606d0a62f570eea348a465c55bc86ffc10
HC = H(0x01|H(M)) = 0x70426d480d5b28d93c5be54803681f99abf4e8df4eab4dc87aaa543f0d138159
HD = H(0x0x|H(SH)) = 0x8482f6c9c3fe90dd4d533b4efedb6a241b95ec9267d1bd5aaaee36d2ce2dd6da

//
// Node Hash
//
HE = H(HA|HB) = 0x049b9f2f94f0a9bdea624e39cd7d6b27a365c6a0545bf0e9d88d86eff4894210
HH = H(HC|HD) = 0xc709fdc632f370f3367da45378d1cf430c5fda6805e731ad5761c213cf2d276e
HI = H(HE|HF) = 0xead5e1a1e7e41b77b794f091df9be3f0e9f41d47304eb43dece90688f69843b7
HJ = H(HG|HH) = 0xd00fc690c4700d0f983f9700740066531ea826b21a4cbc62f80317261723d477

//
// Root Hash
//
Script Root = H(HI|HJ) = 0x26d5235d20daf1440a15a248f5b5b4f201392128072c55afa64a26ccc6f56bd9

MAST Root = H(MAST Version|Script Root)
= H(0x0000000026d5235d20daf1440a15a248f5b5b4f201392128072c55afa64a26ccc6f56bd9)
= 0xb4b706e0c02eab9aba58419eb7ea2a286fb1c01d7406105fc12742bf8a3f97c9

交易输出(即scriptPubKey)为:

1
2
3
4
5
6
7
8
9
scriptPubKey:
0x5120b4b706e0c02eab9aba58419eb7ea2a286fb1c01d7406105fc12742bf8a3f97c9

// 0x51,即OP_1
// 0x20=32,表示witness_program为32字节长度
// 0xb4b706...3f97c9 即MAST Root Hash
//
// Decode:
// OP_1 0xb4b706e0c02eab9aba58419eb7ea2a286fb1c01d7406105fc12742bf8a3f97c9

Witness为:

1
2
3
4
5
6
7
8
9
Script_stack_1: 0x06
Script_stack_2: 0x05
Script_stack_3: 0x04
Subscript_1: 0x5488
Subscript_2: 0x5588
Subscript_3: 0x5688
Position: 0x01 (HF is the second hash in its level)
Path (HE|HJ): 0x049b9f2f94f0a9bdea624e39cd7d6b27a365c6a0545bf0e9d88d86eff4894210d00fc690c4700d0f983f9700740066531ea826b21a4cbc62f80317261723d477
Metadata: 0x03 (3 Subscript, version is 0 so ignore it)

非平衡式构造

在构造脚本树时,可以把执行概率大的脚本放在接近树根的层,执行概率低的分支脚本放到远离树根的层。这种有意的不平衡构造方式,可以有效减少花费时witness的体积。

多重签名和过期

1
2
3
4
5
6
IF
2 <Alice's pubkey> <Bob's pubkey> <Escrow's pubkey> 3 CHECKMULTISIG
ELSE
"30d" CHECKSEQUENCEVERIFY DROP
<Alice's pubkey> CHECKSIG
ENDIF

使用压缩公钥的话,那么上面脚本大小为150字节。采用MAST,可以把此脚本展开为两个分支:

1
2
3
4
5
// 105字节
2 <Alice's pubkey> <Bob's pubkey> <Escrow's pubkey> 3 CHECKMULTISIGVERIFY

// 42字节
"30d" CHECKSEQUENCEVERIFY <Alice's pubkey> CHECKSIGVERIFY

Hashed Time-Lock Contract

1
2
3
4
5
6
7
8
9
10
11
12
13
HASH160 DUP <R-HASH> EQUAL
IF
"24h" CHECKSEQUENCEVERIFY
2DROP
<Alice's pubkey>
ELSE
<Commit-Revocation-Hash> EQUAL
NOTIF
"Timestamp" CHECKLOCKTIMEVERIFY DROP
ENDIF
<Bob's pubkey>
ENDIF
CHECKSIG

采用MAST,展开为三个分支:

1
2
3
4
5
6
7
8
// 1
HASH160 <R-HASH> EQUALVERIFY“24h”CHECKSEQUENCEVERIFY <Alice's pubkey> CHECKSIGVERIFY

// 2
HASH160 <Commit-Revocation-Hash> EQUALVERIFY <Bob's pubkey> CHECKSIGVERIFY

// 3
"Timestamp" CHECKLOCKTIMEVERIFY <Bob's pubkey> CHECKSIGVERIFY

在提高可读性的同时,也可以显著减少witness体积。

大型多重签名合约

当前的多重签名最多允许20把公钥,通过CHECKSIGsIF/ELSE组合一下,可以突破20把公钥限制,但不会突破太多数量,因为很快就会受到10,000字节和201个sigops限制。

通过MAST,可以轻松的构造出 3 of 2000的大型多重签名。从2000人随时抽取3个,那么组合数量为:(2000*1999*1998)/(3*2*1)=1,331,334,000。即1,331,334,000个3 of 3的CHECKMULTISIGVERIFY多签验证。即使这么多可能性分支,也不过就是31层的MAST,2^30 < 1,331,334,000 < 2^31。输出依然是34字节,花费时的witness也不会超过1500字节。

非共识层面的强数据

当前,这些数据一般通过OP_RETURN进行提交,放到交易的输出中。例如存在证明,可以将某个哈希值通过放入交易的输出里,而提交至区块链存储。

通过MAST,可以包含进更多的数据,无需提交每一个值,将其作为MAST分支,那么永远只需要提交32字节即可。


参考:

bip143-新的交易签名摘要算法

现有四种ECDSA签名的验证OP码: OP_CHECKSIG, OP_CHECKSIGVERIFY, OP_CHECKMULTISIG, OP_CHECKMULTISIGVERIFY

还有四种签名的种类:ALL, NONE, SINGLE, ANYONECANPAY

但是存在至少两个缺陷:

  • 现在的验证交易存在潜在过于复杂的问题,验证过程的时间度复杂是O(n^2)。构造一个1MB大小的交易,则需要花费2秒左右才能完成验证。
  • 交易签名时,在不访问前向输出的情况下,是无法知道输入的金额的。因为交易输入里记录的前向交易的哈希值以及位于前向交易的第几个输出位置,其中并不包含金额。导致冷钱包或者分离式的签名器无法安全的进行签名操作,被迫信任传入的交易数据金额。

在原有的脚本上解决这个问题,并非易事。不过,在Segwit软分叉基础上,可以做到。

验证交易的时间复杂度缺陷

现有交易验证过程:

  1. 剔除交易其他输入的签名数据
  2. 替换当前输入的脚本scriptSig为前向交易对应输出的脚本scriptPubKey
  3. 对当前交易做哈希运算,double-SHA256后得到32字节的结果
  4. 对32字节结果进行签名
  5. 循环这个过程,直到遍历处理完所有输入

为何上述过程的时间复杂度是O(n^2)呢?很容易,两个线性叠加了:1. 交易越大,输入数量越多 2. 交易越大,单次交易哈希计算过程越长。

构建一个典型的交易:

  • 一个1MB的交易,输入3,300个,输出406,000 bytes,仅哈希计算则需要:3300 * 406,000,约1.34GB,需要时间10.9秒。
  • 一个8MB的交易,输入22,500个,输出3.95MB,仅哈希计算则需要:22500 * 3.95,大约是88.8GB,需要时间超过11分钟。

也就是说随着交易体积的线性增大,验证交易的时间呈指数级增长。

实施细节

重新定义一个交易哈希摘要算法,但新摘要算法仅与version为零的witness program一起工作:

1
2
3
4
5
6
7
8
9
10
11
Double SHA256一下字段序列化后的数据:
1. 交易版本号,nVersion (4-byte little endian)
2. 所有前向交易输出点(hash & position)哈希,hashPrevouts (32-byte hash)
3. 所有输入的序列值哈希,hashSequence (32-byte hash)
4. 当前输入的前向交易输出点,outpoint (32-byte hash + 4-byte little endian)
5. 当前输入的前向交易输出脚本,scriptCode of the input (serialized as scripts inside CTxOuts)
6. 当前输入的前向交易输出金额,value of the output spent by this input (8-byte little endian)
7. 当前输入的序列值,nSequence of the input (4-byte little endian)
8. 交易所有输出的哈希,hashOutputs (32-byte hash)
9. 锁定时间值,nLocktime of the transaction (4-byte little endian)
10. 签名哈希类型值,sighash type of the signature (4-byte little endian)

若只有1,4,7,9,10,则与旧签名算法中的含义一致。

对于解决复杂度问题,新摘要算法的解决办法很简单,把重复计算的数据先预计算为32字节的哈希值,那么整个新算法的序列化后数据长度则与交易大小基本没关系。

其中5,6保证了签名时,签名者可确认签名金额和脚本,解决了输入金额盲签的问题。


参考:

BIP141, Segregated Witness

Transaction ID

在新的结构下,每个交易将有两个ID.

txid保持不变,Double SHA256哈希以下序列化的数据:

[nVersion][txins][txouts][nLockTime]

新定义一个wtxid,Double SHA256哈希含有witness数据的序列化数据:

[nVersion][marker][flag][txins][txouts][witness][nLockTime]

其中:

  • nVersion, txins, txouts, and nLockTime保持不变
  • marker必须为一个字节的零值:0x00
  • flag必须为一个字节的非零值,目前使用0x01
  • witness为交易的所有见证数据
    • 起始用var_int表示有几个输入
    • 然后每个项的起始用var_int标识其数据长度
    • Witness数据并不是脚本

如果一个交易输入不含有任何的witness program(可以视为不带OP操作码的scriptPubKey),则交易的wtxid等于txid

Commitment

新增一个规则,coinbase交易的wtxid认为是0x0000...0000

新增一个witness root hash,每个交易的wtxid作为叶子计算而来。类似原块头中的merkle root hash

这个Commitment存在在coinbase交易的某个输出scriptPubKey中,长度必须至少为38Bytes,前六个字节内容固定是0x6a24aa21a9ed

1
2
3
4
5
6
 1-byte - OP_RETURN (0x6a)
1-byte - Push the following 36 bytes (0x24)
4-byte - Commitment header (0xaa21a9ed)
32-byte - Commitment hash: Double-SHA256(witness root hash|witness reserved value)

39th byte onwards: Optional data with no consensus meaning

如果交易的多个输出符合六个字节前缀,则认为序列最大的输出项为Commitment。

Coinbase交易5b298d2e51d996cf6f8f5b12f2c44fa3203b39e0514025268b55ddc46ac72e73,其Hex内容为:

1
010000000001010000000000000000000000000000000000000000000000000000000000000000ffffffff4d03819a08045cda6c5c2f706f6f6c696e2e636f6d2ffabe6d6db24bb958ea51e4bb25e0975c5ff65071a38f81d6e65a447105e1340b24171bee01000000000000009e2268d82707000000000000ffffffff025cac6d4b0000000017a914b757c3e4653706dd01f7b8345a6d71d96a7b136b870000000000000000266a24aa21a9ed5586b81f398ff1a8f20da1405bc92e6bbd2dda466414ca90bbd8215f77fe0c340120000000000000000000000000000000000000000000000000000000000000000000000000

分解Coinbase TX:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
01000000 - version
00 - marker
01 - flag

Inputs:
01 - 1 input
input[0].prev-txout-hash 0000000000000000000000000000000000000000000000000000000000000000
input[0].prev-txout-position ffffffff
input[0].sigScript:
4d - len, 0x4d=77Bytes
03819a08045cda6c5c2f706f6f6c696e2e636f6d2ffabe6d6db24bb958ea51e4bb25
e0975c5ff65071a38f81d6e65a447105e1340b24171bee01000000000000009e2268
d82707000000000000
input[0].sequence: ffffffff

Outputs:
02 - 2 outputs
output[0].value - 5cac6d4b00000000
output[0].scriptPubKey - 17a914b757c3e4653706dd01f7b8345a6d71d96a7b136b87

output[1].value - 0000000000000000
output[1].scriptPubKey -
266a24aa21a9ed5586b81f398ff1a8f20da1405bc92e6bbd2dda466414ca90bbd821
5f77fe0c34

Witness:
01 - 1 witness item
witness[0].len - 20
witness[0].data -
0000000000000000000000000000000000000000000000000000000000000000

00000000 - locktime

其实就是两套Merkle树,一套由txid作为叶子,一套由wtxid作为叶子。保持软分叉,块头不动,新的一套Merkle树根值,放入Coinbase交易里。Coinbase交易呢,走原来的Merkle树,根值放入块头。

Witness Program

Native Witness Program

此时输出的scriptPubKey内容为:

[version][witness_program]

  • version :1 bytes,表示版本,值范围是:[0, 16]
  • witness_program: 数据,长度2~40 Bytes

当前,version是0x00witness_program的长度为20或32字节。

比特币脚本中与version可能相关的OP操作编码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
OP_0 = 0x00

OP_1 = 0x51, // Alias OP_TRUE
OP_2 = 0x52,
OP_3 = 0x53,
OP_4 = 0x54,
OP_5 = 0x55,
OP_6 = 0x56,
OP_7 = 0x57,
OP_8 = 0x58,
OP_9 = 0x59,
OP_10 = 0x5a,
OP_11 = 0x5b,
OP_12 = 0x5c,
OP_13 = 0x5d,
OP_14 = 0x5e,
OP_15 = 0x5f,
OP_16 = 0x60

P2SH Witness Program

即通过P2SH进行包装一下:

OP_HASH160 [20 BYTES HASH] OP_EQUAL

其中:

1
2
3
20_BYTES_HASH = HASH160(redeemScript)

redeemScript = [version] + [witness_program]

P2WPKH

P2WPKH,即Pay to Witness Pubkey Hash。Witness Program长度为20字节。

其中:

  • version = 0
  • witness_program = hash160(pubkey)

脚本堆栈为:

1
2
3
4
5
6
7
8
Witness:
[signature] [pubkey]

scriptSig:
(empty)

scriptPubKey:
[0] [20_bytes]

通过执行CHECKSIG来完成签名验证:<signature> <pubkey> CHECKSIG。在验证脚本时,会先封装20bytes的数据为脚本:OP_HASH160 <20bytes> OP_EQUAL,并入栈执行。

若采用P2SH来包装的话,则有:

1
2
3
4
5
     witness: <signature> <pubkey>
scriptSig: <redeem_script>
scriptPubKey: HASH160 <20-byte-script-hash> EQUAL

redeem_script : [version] + [witness_program]

会先验证redeem_script的hash160,然后再分解redeem_script得到20Bytes,再包装为OP_HASH160 <20bytes> OP_EQUAL,并入栈执行。

P2WSH

P2WSH,即Pay to Witness Script Hash。Witness Program长度为32字节。

其中:

  • version = 0
  • witness_program = sha256(witnessScript)

脚本堆栈为(1/2多重签名):

1
2
3
4
5
6
7
8
9
10
11
Witness:
0 <signature1> <witness_script>

scriptSig:
(empty)

scriptPubKey:
[0] [32_bytes]

其中:
witness_script = 1 <pubkey1> <pubkey2> 2 CHECKMULTISIG

执行与P2SH的redeem_script一致,分为两步:

  1. 验证witness_script的sha256哈希值。
  2. 分解witness_script为子脚本,重新入栈并执行脚本。

其他共识规则

Block size 区块大小

原来的规则是单个区块大小最大值为1,000,000 Bytes,因剥离出Witness数据,这里提出一个新的单位Weight进行改进:

Block_Weight = Base_Size * 3 + Total_Size

  • Base_Size,基础大小,定义是:剥离witness相关数据后的大小,即未升级节点所看到的数据部分。
  • Total_Size,全大小,定义是:包含witness相关数据的所有数据大小。
  • Base_Size <= 4,000,000

Sigops 操作数

Sigops当前单个区块限制是 20,000,修改为:

用于pubkey script, signature script, 以及 P2SH check script的Sigops重新定义为原来的4倍。块限制亦同样的变为四倍 80,000.

Commitment结构可扩展性

现有commitment计算过程:

1
2
3
Commitment hash: Double-SHA256(witness root hash|witness reserved value)

witness reserved value: 当前是32 bytes的零值,存在在coinbase交易的witness里

例如我们新加了一个特性,其也有数据的commitment值,那么可以将原来的witness reserved value更新为:Hash(new commitment|witness reserved value),那么并不影响旧节点对commitment的校验。

1
Double-SHA256(Witness root hash|Hash(new commitment|witness reserved value))

这个方法可以扩展为多个commitment,未来可以用于其他的软分叉升级。

未来的扩展

减少SPV欺骗

SPV节点目前依然有几个问题无法验证:

  • 无法验证矿工是否在coinbase交易里增发币。不下载完整区块,就无法的得知所有交易的手续费,就无法得知块手续费。
  • 无法验证是否违反其他共识规则,例如块大小限制、sigops限制。
  • 无法验证输入交易是否存在,除非拿到直至coinbase交易的前向交易链条。

额外的数据可以采用commitment方式填入,借助软分叉升级。

新的脚本系统

scriptPubKey采用的版本号,若老节点看不懂这个新版本号,但会认为是任何人都可以花费的(因为脚本堆栈执行总是True),所以将来可以采用这种机制来新增脚本系统,并且都将是软分叉。

witness部分目前是没有任何限制的,也就是说可以完全绕开520字节的脚本大小限制。未来也可以轻松引入新的签名机制,例如Schnorr签名。


参考:

P2SH-为比特币赋能的脚本

P2SH即Pay to Script Key Hash,最常见的应用是多重签名,N把公钥,M人签名时才能花费这笔交易(M<=N, N<=16),地址通常是以3开头的格式。当然,p2sh除了用来做多重签名之外,能做的事情简直无数。

P2PK

比特币早期中本聪时期是P2PK(pay to public key)这种输出形式的,最早是直接放入一把公钥进去了,还是未压缩的,感受一下:

1
04678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5f OP_CHECKSIG
  • 0x04开头,表示是未压缩的
  • 0x04后面紧接这的是64字节是公钥内容
  • OP_CHECKSIG:操作码,用于花费的时执行验证签名

那么验证时(即花费这笔输出)堆栈内容为:

1
2
3
4
5
花费脚本为:
<signature>

连接前向的输出,完整的堆栈:
<signature> <pubkey> OP_CHECKSIG

OP_CHECKSIG执行签名检查,并返回检查结果,true则通过签名检查,可以花费。

P2PKH

后来发现公钥其实用哈希就可以了,没必要放出公钥内容,被称为P2PKH(pay to public key hash)。于是输出脚本演化为:

1
OP_DUP OP_HASH160 <public_key_hash> OP_EQUALVERIFY OP_CHECKSIG
  • OP_DUP: 操作码,复制栈顶元素
  • OP_HASH160:操作码,计算栈顶元素Hash,即计算公钥的哈希
  • public_key_hash:公钥的哈希值,20字节
  • OP_EQUALVERIFY:操作码,判断是否相等
  • OP_CHECKSIG:操作码,用于花费的时执行验证签名

此类型输出,就是最常见的1开头的地址输出。那么验证时的堆栈内容为:

1
2
3
4
5
花费脚本为:
<signature> <pubkey>

连接前向的输出,完整的堆栈:
<signature> <pubkey> OP_DUP OP_HASH160 <pubkey_hash> OP_EQUALVERIFY OP_CHECKSIG

验证运算过程:

  1. 从前往后找OP操作码,首先遇到OP_DUP
    • 执行后堆栈为:<signature> <pubkey> <pubkey> OP_HASH160 <pubkey_hash> OP_EQUALVERIFY OP_CHECKSIG
  2. 执行OP_HASH160
    • 执行后堆栈为:<signature> <pubkey> <pubkey_hash> <pubkey_hash> OP_EQUALVERIFY OP_CHECKSIG
  3. 执行OP_EQUALVERIFY,即验证该哈希是否与公钥匹配
    • 执行后堆栈为:<signature> <pubkey> OP_CHECKSIG
    • 到这里就与P2PKH一致了
  4. 执行OP_CHECKSIG,验证签名。

这个过程汪海波写过文章详细的阐述过:理解比特币脚本。p2pk改进为p2pkh后,输出长度缩小了一半多,同时隐私方面迈出了一小步:别人转给你的币在你未花费之前,别人是不知道你的公钥具体内容的。是不是很赞?

原始多重签名

随着社区快速发展,人们发现需要多重签名,很快就出现了多重签名的输出格式,Gavin在BIP11里描述了这种输出:

1
m {pubkey}...{pubkey} n OP_CHECKMULTISIG

2/2的一个原始多重签名示例:

1
2
3
4
2
04cc71eb30d653c0c3163990c47b976f3fb3f37cccdcbedb169a1dfef58bbfbfaff7d8a473e7e2e6d317b87bafe8bde97e3cf8f065dec022b51d11fcdd0d348ac4
0461cbdcc5409fb4b4d42b51d33381354d80e550078cb532a34bfa2fcfdeb7d76519aecc62770f5b0e4ef8551946d8a540911abe3e7854a26f39f58b25c15342af
2 OP_CHECKMULTISIG

验证时的堆栈内容为:

1
2
3
4
5
花费脚本为:
0 <sig_1> <...> <sig_M>

连接前向的输出,完整的堆栈:
0 <sig_1> <...> <sig_M> M <pubkey_1> <...> <pubkey_N> N OP_CHECKMULTISIG

OP_CHECKMULTISIG的运行过程稍微复杂一些:

  1. 弹出最后一个数,就是N,公钥总数。
    • 执行后堆栈为:0 <sig_1> <...> <sig_M> M <pubkey_1> <...> <pubkey_N>
  2. 弹出N个堆栈元素,就是这N把公钥。
    • 执行后堆栈为:0 <sig_1> <...> <sig_M> M
  3. 弹出签名数量M,即需要M个签名数量。
    • 执行后堆栈为:0 <sig_1> <...> <sig_M>
  4. 弹出M个堆栈元素,即需要M个签名。同时对M个签名进行验证。
    • 执行后堆栈为:0
  5. 弹出最后一个元素0
    • 0OP_0,为啥多这么一个奇怪的元素呢,因为早期实现OP_CHECKMULTISIG时,存在一个BUG,导致必须多放入一个元素到堆栈里。为了保持兼容性,则不得不放入OP_0,否则就是造成硬分叉。

这种类型的输出存在时间很短,大部分人几乎不知道它的的存在,如果你哪天看见某个交易的一个输出里冒出好几个地址,那就是这种古老原始的多重签名。早期主要应用于2/3的担保交易中。

P2SH

因为实在是又丑又笨,Gavin很快捣鼓出一个改进版本BIP16:

1
OP_HASH160 <redeem_script_hash> OP_EQUAL

其实不用把公钥放在输出里了,放入其HASH值即可,与早期P2PK进化为P2PKH一样,将这些公钥连接在一起并计算出其HASH160的值:

1
2
3
RedeemScript = OP_nRequired | PUBKEY_1 | ... | PUBKEY_N | N | OP_CHECKMULTISIG

20-byte-hash-value = RIPEMD-160(RedeemScript)

RedeemScript就是把参与的公钥以及m/n的设置值等连接在一起的内容,RedeemScript其实就是前面提到的“原始多重签名”的输出,哈希后产生的这20个字节刚好可以转为普通地址显示,就是现在最常见的3开头的p2sh多重签名地址。N最大为16把公钥。

验证时的堆栈内容为:

1
2
3
4
5
花费脚本为:
OP_0 <sig_1> <...> <sig_M> <redeemScript>

连接前向的输出,完整的堆栈:
OP_0 <sig_1> <...> <sig_M> <redeemScript> OP_HASH160 <redeemScriptHash> OP_EQUAL

验证过程分为两大步骤,第一步骤:

  1. 执行OP_HASH160,计算HASH值:<redeemScript> OP_HASH160
    • 执行后堆栈为:OP_0 <sig_1> <...> <sig_M> <redeemScriptHash><redeemScriptHash> OP_EQUAL
  2. 执行OP_EQUAL,验证两个哈希值是否相等
    • 执行后堆栈为:OP_0 <sig_1> <...> <sig_M>

第二步骤,将展开花费脚本中的RedeemScript展开得到子脚本,就得到与“原始多重签名”一致的堆栈数据格式,并执行类似的验证过程:

1
OP_0 <sig_1> <...> <sig_M> M <pubkey_1> <...> <pubkey_N> N OP_CHECKMULTISIG

当然,RedeemScript除了放多重签名脚本外,还可以放其他任何脚本,多重签名仅仅是一种应用而已,p2sh提供了无限可能性。

软分叉的关键点

在第一步骤中,redeemScript是作为一个整体数据进栈的,而在第二步里,redeemScript会按照脚本进行解析得到N个栈元素,然后再依次进栈进行验证。这个过程是非常巧妙的,在第一步里,仅验证了脚本的哈希值是否一致,并没有验证签名。真正的签名信息是在第二步骤里进行验证的。因为这点,所以可以软分叉实施P2SH,老节点仅执行第一步骤,新节点执行两个步骤。

当花费过一次后,redeemScript其实就公开了,那么对于老节点来说,任何人都可以用这个公开的redeemScript花掉相同地址的币(验证哈希值)。这就是被称为任何人可以花费(Anyone can spend)的原因。不过,特性激活后,新版全节点(出块节点必然是新版)会强制执行第二步验证,永远都不会被其他人偷花。

激活

P2SH的激活,其实算是UASF或者是GASF(Gavin Actived Soft Fork),那时也没有规范的软分叉升级方案,如BIP9。升级代码就直接发布了,并设立了激活信号日2012年04月01日(测试网是2月15日)。支持的用户直接升级代码,不支持的用户不升级代码。

为了防止潜在网络分叉,矿工在coinbase交易里打标识/P2SH/来标明支持P2SH。但这个仅供人为观察,并不是代码层面的。

影响深远

P2SH是一个高度灵活的脚本方案,意义重大,影响深远,简直像打开了宝藏一样。其为后面的SegWit,MAST都铺平了道路。

发展状况

数据来源:https://p2sh.info

截止2019年2月,全网大约32%的币存储在P2SH的输出里。

p2sh-values

P2SH的输出类型统计:

p2sh-types


参考

谈谈软分叉升级规范BIP8-后矿工时代的软分叉方式

版权声明:欢迎转载,请注明出处

之前说过软分叉升级规范BIP9,BIP9可以说是经过良好设计的软分叉升级方案,可同时进行多个分叉的升级并且流程也很科学合理。

BIP9

简单回顾一下BIP9的主要特性:

  1. 95%的高投票阈值,块投票必须达到95%以上的支持率才能进入锁定期,然后触发激活。
  2. 设定了投票时间窗口,有起始、终止时间,在窗口期内未激活的软分叉只能终止或者重新设定发起新一轮投票。
  3. 块时间采用相邻11个块的块中位数时间。

BIP9截止到当前(2019年02月)共使用过两次:

  1. CSV(BIP68, BIP112, and BIP113)
  2. SegWit(BIP141, BIP143, and BIP147)

在CSV软分叉中进展一切正常,但SegWit软分叉中却在投票阶段延迟了大半年,块投票一直无法达到95%的激活阈值,以至于后来出现了BIP148(即UASF,user-activated soft fork)和BIP91。SegWit在BIP9中设定的时间区间是:2016年11月15日~2017年11月15日。

这里我们稍微说一下BIP148和BIP91,只有理解了这个过程才能理解为何会有BIP8(这些事情其实已经发生挺久了,2017年中,快两年前的事情了)。值得一提的是,BIP148和BIP91的代码,从来没有进入Bitcoin Core版本的代码库。

BIP148

BIP148,更熟悉的名称是UASF,目的是强制性进行激活SegWit:若块时间处于2017年08月01日与2017年11月15日,且SegWit尚未激活或没有进入锁定期,则直接拒绝不支持SegWit投票的块。BIP148通过用户自行更新代码,下载Bitcoin Core的代码然后打补丁的方式,来声明和实施。

UASF是非常激进的升级方式,直接抛开了矿工算力的投票,不管算力是否投票支持SegWit,这些UASF全节点到时候会直接抛弃掉非SegWit的块。这在当时还非常认可矿工和算力的时代,对于矿工和算力来说简直是晴天霹雳:直接撇开了!

当然,很多交易所对这一事件进行了预演:假设分叉会发生,并上市了推演分叉后的两个币种期货,把价格交给市场去判断。

BIP91

BIP91,目的是也是激活SegWit,通过降低SegWit激活阈值至80%来间接完成,其自身采用类似BIP9的方式进行部署:

  1. 激活时间区间是:2017年06月1日 ~ 2017年11月15日。
  2. 块时间窗口非常短,不再是BIP9中的2016个块,而是336个块,大约2.33天。
  3. 激活阈值为80%,不再是BIP9的95%。

BIP148(UASF)直接撇开矿工由全节点直接激活,而BIP91依然把选择权给了矿工:通过块投票进行激活。最终,由UASF主导的强大社区压力下,BIP91很快通过80%的块投票阈值进入锁定并激活了。BIP91一旦激活,则意味着后面的块必须进行支持SegWit投票,间接促成了SegWit通过95%的块投票阈值并锁定激活了。

以上即是SegWit激活受阻大半年后,UASF&BIP91间接促成SegWit激活的历史过程。

BIP8

BIP8是在BIP9基础之上的改进:

  1. 采用更加精确的块高度窗口代替块时间窗口,消除了块时间的不稳定性。
  2. 统计周期依然是与BIP9一致的2016个块。
  3. 几乎不再有失败的状态,除非编码之初设定的高度已经是过去高度。
  4. 设立激活起始块高度,一旦当前高度大于起始块高度,则开始计算是否激活。起始块高度必须超过当前高度4320个块,约30天。
  5. 设立截止块高度,无论投票是否通过,都在截止块高度达到时进行强制激活。截止高度通常是起始高度的52416块之后,约一年。
  6. 在抵达截止块高度前,若投票超过阈值,阈值与BIP9一致为95%,则提前进入锁定期并随之激活。

BIP8 States

总结,如果某个软分叉遵循BIP8激活机制的话,一旦部署了,那么矿工可以进行投票提前激活,或者在一年后的截止高度抵达时自动激活。

BIP8的主要意义

  1. 取消了矿工的否决权:要么投票主动提前激活,要么不投票被动等抵达截止高度自动激活。
    • Vote转变成Signal。
    • 算力大小是价格高低的结果,严格来说是链的法币日产量决定算力规模。
    • 价格由市场供需决定,体现为共识主导价格。
  2. 社区的决策机制发生了根本性改变:从小圈子投票变成了一定程度上的普选。
    • 无论是算力投票还是持币投票,由于存在中间代理层(例如矿池、交易所、钱包等),均无法避免最终沦为一定程度上的小圈子投票。
    • 一个全节点即一张选票,全节点构成最广泛的共识。
    • 全节点一方面制约着算力,另一方面也制约代码。无论是矿霸还是码霸,均无法强制约束全节点的行为。

后记

从中本聪白皮书时代以来,大多数人坚信着“One CPU One Vote”的民主观念,在经历了2017的SegWit激活历程后,其中还硬分叉诞生了Bitcoin Cash(BCH),终于得到脱胎换骨的革新。大家发现只有全节点才是最终的堡垒和武器,运行全节点是平等自由的互联网所赋予的谁也剥夺不了的权利。


参考

新的软分叉升级规范BIP9

比特币的软/硬分叉升级一直采用块的version字段来完成。由于是一个分布式系统,必然需要采用灰度发布模式。

传统的升级过程

在实施BIP9前是这样升级的,当前块版本为version,那么新块版本是version + 1,当近1000个块中的版本超过95%都是新版本时,则触发启用新特性,同时不再接收旧版本号的块。由于中间存在1000个块的窗口期,大约一周,所以给出足够的时间给当前网络中的节点实施升级。

图1.0

上图是来自BTC.COM统计的比特币历史上几个升级过程,最近的v3升级v4的过程大约花费了一个半月左右。前面几次的升级时间更长。

这种依次递增版本号的方法,有一个明显的弊端:每次仅能进行一个特性升级。当需要同时进行多个升级时,则无法完成。BIP9的诞生就是为了解决这个问题的,同时把向下兼容性升级过程制定了规范。

BIP9特征

  1. 支持多个特性同时升级
  2. 新增投票时间区间
  3. 新增锁定期

块的version字段是4字节,意味着有32位比特,前三位目前固定为001,那么剩余29个比特可以用于特性设置,与激发某个特性,则将其对应的位设置为1

1
2
3
4
5
二进制格式:

001 0 0000 0000 0000 0000 0000 0000 0000
------ ------------------------------------
固定保留 29个特性标识位

状态变迁

BIP9某个特性的状态有:

  • DEFINED 定义。每个特性的升级设定会写到某一个版本的bitcoind中,并部署下去。
  • STARTED 启动。启动后会有两个可能的变迁状态:LOCKED_IN, FAILED
  • LOCKED_IN 锁定。一旦进入锁定态,则必然会激活。锁定期为2016个块。
  • ACTIVE 激活
  • FAILED 失败

图1.1

MTP是最近11个块的时间戳中位数。区块链上的块时间并不是按照高度递增而严格递增的,但MTP时间是严格递增的(早期可能不能严格遵守)。

能够进入锁定期(即得到全网同意)的条件是在2016个块中,支持的块数量达到95%,在测试网络上是75%。窗口期从之前的1000提升至2016个块,即一个难度周期,约两周。同时,还增加了2016个块的锁定期,之后才能正式激活特性。这比之前的升级,变得更加稳健,预留出充分的时间,同时意味着特性的落地周期变长。

首个采用BIP9的软分叉

BIP68/112/113是首个采用BIP9方式进行升级的软分叉,随bitcoind-v0.12.1发布。使能位采用最右侧位,起始时间(starttime)是2016-05-01 00:00:00,终止时间(timeout)是2017-05-01 00:00:00

若要支持BIP68/112/113软分叉,那么版本号应该是: 0x20000001,二进制为:0010 0000 0000 0000 0000 0000 0000 0001

另外BIP109(Classic 2MB HardFork)也是采用的是BIP9规范,使能位是最左侧位,但触发窗口期与锁定期的设定均未采用BIP9的定义。其版本号是:0x30000000,二进制为:0011 0000 0000 0000 0000 0000 0000 0000

如果版本号为:0x30000001,二进制为:0011 0000 0000 0000 0000 0000 0000 0001,则意味着同时支持BIP68/112/113BIP109