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. 接受者很难指定条件

• 当前主要是匹配公钥或者其哈希，然后花费时校验其签名

1. 大脚本占用更多的UTXO空间
2. 发送者付出更高的成本：交易体积大，通常需要付出更高的手续费
3. 为了防止潜在的DoS攻击，比特币对脚本设定了一些限制：脚本体积小于10KBytes，或小于201个OP码
4. 未执行的部分脚本，其非共识层面的数据都是公开的，即占用区块空间又暴露隐私

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

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

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

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为：

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的定义：

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”下的情况，假设一个花费条件可以设定为：

(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。

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码，甚至在未来引入其他脚本语言和系统。

一个示例

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）为：

scriptPubKey:
0x5120b4b706e0c02eab9aba58419eb7ea2a286fb1c01d7406105fc12742bf8a3f97c9

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

Witness为：

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的体积。

多重签名和过期

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

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

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

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

Hashed Time-Lock Contract

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
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