之前写过一篇从技术层面解读Taproot：《Taproot简介》，这次再多啰嗦解读几句（不带公式的）。

生活中的合约、合同通常有以下一些特征：

• 通常，合约是双方或多方的。
• 合约的双方并不绝对信任对方，如果可以绝对信任对方，则不需要合约。
• 合约的双方一般假设对方大概率会履约：如果还没交易就已经认为对方不会履约，可能会选择不交易，或使用一些合约条款（如惩罚）保证对方履约。
• 设计正确的合约，应该让双方在履约的情况下均会得到较大利益（或较少损失）
• 因此在绝大部份情况下，合约都不会有争议，双方都会合作实行合约条款。在这种情况下，合约条款一般会得到保密，不为第三方所知。
• 若过程中出现争议（不合作）的情况，需要由第三方机构（如法院）进行仲裁。在这种情况下，合约条款需要公开，提供给律师、法官等。

比特币链上是可以写简单合约的，例如n/m式的多重签名机制、闪电网络等。区块链的合约通常称为智能合约。

• 所有合约的特性都适用于智能合约，只是区块链规则担当了仲裁的角色，换言之Code is Law。
• 但现在比特币的智能合约，不论是2009年中本聪的原始设计，2012年出现的P2SH，还是2017年的隔离见证(P2WSH)，都有一个共同的问题：无论立约双方是否合作，合约内容必须完全公开，即合约脚本必须公开。当花费时必须提供合约脚本全部内容才能进行校验。
• 公开合约内容主要带来两个问题
  • 交易成本：智能合约一般都需要多个签名，加上合约内容本身，占用更多区块空间，令交易手续费上升。
  • 隐私问题：第三方可以监察区块链，通过合约内容的特征，追踪资金的流向和推断合约参与者的身份。

ECDSA

ECDSA是比特币诞生到现在唯一的签名验证机制。

• 数字签名是比特币认证交易合法性的最重要手段，确权的唯一标准。
• 自2009年以来，比特币均使用ECDSA为数字签名标准（包括P2PK, P2PKH, 2012年的P2SH, 2017年的P2WPKH和P2WSH）。
• 比特币的公/私钥系统是线性的，因此我们可以把多个私钥相加，也可以把对应的多个公钥相加，这样产生的新私钥和新公钥仍然是一对。这是HD钱包的理论基础。
• 但ECDSA的签名是非线性的，因此简单的把多个签名结果加起来，则不再是有效的签名
• 因此一直以来，比特币的多签署交易均需要在区块链公开多个签署，问题和智能合约相同（交易成本，隐私问题）。
• 201方的多方签署人数的理论极限（P2SH大概只容许最多16方）。

Schnorr

再说一下Schnorr签名算法。

• Schnorr签署的专利于2008年才失效，当时没有广泛的开源实现及应用，所以2009年诞生的比特币也没有使用。签名算法通常是需要深厚的数学理论基础才能设计。一个小的理解偏差，编码错误则可能导致严重问题。
• Schnorr 签署使用的公/私钥系统和ECDSA相同，因此现有的私钥管理(如BIP32)可以继续使用
• Schnorr和ECDSA的区别在于：Schnorr签名是线性的。对于同一内容X，如果用多个私钥各自签名，然后把对应的多个公钥相加，再把多个签名相加，得出的新签名会是新公钥对内容X的有效签名。
  • 利用这个特性，签名人数没有理论极限。只要各方一致合作，就可以把签名相加起来，看起来和单方签名无异。
• Schnorr签名算法的安全性于2012年得到数学证明。

Taproot

Taproot解决的问题

• Taproot以Schnorr签名算法为基础
• 以Taproot进行的智能合约，如果双方合作，不但无需公开合约内容，而且交易会和最简单普遍的单方签名交易看起来没有分别。即交易成本极小化及隐私极大化。
• 如果双方不合作，申诉方仍需要公开合约脚本内容以供区块链仲裁。
  • 但通过使用MAST（Merklized Alternative Script Trees），申诉方只需要公开合约的相关部份，而非所有合约条款，也因此尽量降低交易成本和对隐私的影响。即合约可能有多条执行路径，仅公布即将执行的路径即可。

Taproot没有解决的问题

• Taproot没有把交易金额隐藏，因此仍可以通过分析输入和输出金额估计资金流向。
• Taproot地址和旧式地址一样，会在区块链公开。如果使用者重覆使用Taproot地址，那和重覆使用旧式地址有相同的隐私问题。

总结

比特币在隐私方向上，有两大待攻克的难题。一是流向隐匿，这在UTXO系统里是比较棘手的；二是金额隐匿，可以通过类似Grin的技术来解决，需要扩展区块或分叉来实现。

即使上述两大难点并没有解决掉，但Taproot对于比特币合约来说，即实现了交易成本极小化，又使得隐私极大化。还是一个显著的小小进步。

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

• 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签名算法是无法构造出能验证通过的伪签名的。

参考：

• https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki
• How Perfect Offline Wallets Can Still Leak Bitcoin Private Keys
  • https://bitcointalk.org/index.php?topic=883793.0
    • https://bitcointalk.org/index.php?topic=285142.msg3077694#msg3077694
    • https://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg02721.html

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是灵活的，更多应用场景等待挖掘。

参考：

• [bitcoin-dev] Taproot: Privacy preserving switchable scripting
  • https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-January/015614.html

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交易，而不是传统交易。BIP62 和 BIP66 对此有详细描述。
• 线性。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。

参考：

• Schnorr signature，https://en.wikipedia.org/wiki/Schnorr_signature

• BIP-Schnorr,Pieter Wuille，https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki

• Simple Schnorr Multi-Signatures with Applications to Bitcoin，https://eprint.iacr.org/2018/068

写在前面的话

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

第一阶段，原始脚本阶段，仅有脚本。典型的有：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

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 Root是H(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

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

一个示例

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把公钥，通过CHECKSIGs和IF/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字节即可。

参考：

• https://github.com/bitcoin/bips/blob/master/bip-0114.mediawiki
• https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki

现有四种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保证了签名时，签名者可确认签名金额和脚本，解决了输入金额盲签的问题。

参考：

• https://github.com/bitcoin/bips/blob/master/bip-0143.mediawiki

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是0x00，witness_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签名。

参考：

• https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki

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。
   • 0即OP_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的输出类型统计：

参考

• https://github.com/bitcoin/bips/blob/master/bip-0011.mediawiki
• https://github.com/bitcoin/bips/blob/master/bip-0016.mediawiki
• https://github.com/bitcoin/bitcoin/blob/v0.6.0/src/main.cpp#L1281

版权声明：欢迎转载，请注明出处

之前说过软分叉升级规范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激活机制的话，一旦部署了，那么矿工可以进行投票提前激活，或者在一年后的截止高度抵达时自动激活。

BIP8的主要意义

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

后记

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

参考

• BIPs
  • https://github.com/bitcoin/bips/blob/master/bip-0009.mediawiki
  • https://github.com/bitcoin/bips/blob/master/bip-0008.mediawiki
  • https://github.com/bitcoin/bips/blob/master/bip-0148.mediawiki
  • https://github.com/bitcoin/bips/blob/master/bip-0091.mediawiki

这是在2018年3月在三里屯WeWork一次分享，主要讲了闪电网络的基础知识，以及扩容的发展历程。

视频地址： https://www.yizhibo.com/l/jW2SzxIVFOzKF4k_.html
PDF地址：https://github.com/bitkevin/blog.biqu.io/files/1845471/default.pdf