Segwitで導入されたwitness programを使った拡張で、マークル化抽象構文木 = Merkelized Abstract Syntax Trees(MAST)という仕組みがBIP-114として定義されている。
bips/bip-0114.mediawiki at master · bitcoin/bips · GitHub
多数の異なる条件を持つBitcoinのスクリプトの条件部分を別々のセグメントに分割し、分割したセグメントをマークルツリーに配置して管理する手法で、MASTを導入することで、現在は実現できていない複雑な条件を設定したロックスクリプトの作成を可能にし、未実行のスクリプトを見えなくする(ハッシュ化する)ことで第三者に分からないようプライバシーを向上させ、トランザクションのサイズの削減にもなるとされている。
このMASTの仕様についてBIP-114を見ていく。
動機
Bitcoinのスクリプトシステムの進化
Bitcoinはトランザクションの出力の解除条件の指定方法としてスクリプトシステムを使用している。オリジナルの設計では、解除条件は資金の送信者が直接scriptPubKeyに記録している。このモデルには、(複雑なスクリプトを作ろうとすると)以下のような欠点がある。
- 受信者が条件を指定するのが困難
- スクリプトが大きくなると、より多くのUTXOのスペースが必要になる
- スクリプトが大きくなると送信者はその分追加のコストが必要になる
- DoS攻撃を防ぐため現在のスクリプトは1,000バイト以下で実行できるopcodeは201以下に制限されている
- スクリプト内の未実行なブランチやコンセンサスに関係ない任意のデータも公に公開されるため、プライバシーを損ない、ブロックスペースの浪費になる
BIP-16(Pay to Script Hash=P2SH)は、解除条件を記載した固定長20バイトのスクリプトのハッシュ値をscriptPubKeyに入れることで、↑の最初の3つの問題を解決するが、スクリプト内にプッシュできるデータのサイズに制限があり、P2SHのスクリプトは520バイトより大きくはできない。またP2SHは、スクリプトの解除条件の内、解除に使わなかった未実行の条件部分も公開する必要がある。
BIP-141では、segwitをサポートするため2つの新しいタイプのスクリプトを定義している。その内、pay-to-witness-script-hash (P2WSH)はベースがP2SH。新しいデータ構造であるwitness内にスクリプトを配置することで、P2WSHは10,000バイトまでのスクリプトを利用できるが、これでもまだ未実行の条件部分の公開はしなくてはならない。
Merkelized Abstract Syntax Tree
Merkelized Abstract Syntax Tree(MAST)の考え方は、スクリプト内のブランチをエンコードするのにマークルツリーを使うところにある。Bitcoinを使用する際(=ロックを解除する際)に、実行するブランチのみを提供するだけでよくなる*1。これによりロック解除のスクリプトのスタックもO(n)からO(log n)に減らせる(nはスクリプト内のブランチの数)。また、現在スクリプトのサイズやopcodeの実行数の制限により実現できないより複雑な解除条件が設定できるようになり、未実行ブランチを隠すことでプライバシーは向上し、任意のデータを追加のコスト無しor少量のコストで含められるようになる。
仕様
BIP-141にて、witness programのversion byteは1から16までが拡張用に確保されているので、version byteが1以上であれば誰もが利用できるスクリプトを構成できる。従って、version byteが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)
Metadata
は最後のwitnessの項目で、1〜5バイトのvector。最初のバイトはSubscript
(後で定義)の数を示す1〜255の符号なし整数になる。続く0〜4バイトはMAST version
を示す符号なしのリトルエンディアンの整数。MAST version
は最小限にエンコードされる必要がある。
Path
は、最後から2つめのwitnessの項目で、シリアライズしたScript Hash
(後で定義)のマークルパスである。パスのサイズは32バイトの倍数で、1024バイト以下。各32バイトの値はScript Root
(後で定義)に接続するマークルブランチのダブルSHA-256ハッシュである。(0〜32までの)ツリーのDepth
はパスのサイズを32で割った値になる。
Position
は最後から3つめのwitnessの項目で、マークルツリー内のScript Hash
の場所を示す。値は4バイト以下の符号無しのリトルエンディンの整数で、ツリーのDepth
によって許容される項目の最大数以下で、最上位バイトが0であってはならない。例えばDepth
が4の場合、有効なPosition
の範囲は0〜15(= 24 - 1)となる。
Metadata
の最初のバイトて指定された数分、Position
の前にSubscript
が存在する。
Script Hash
は以下のように定義される。
Script Hash = H(Y|H(Subscript_1)|H(Subscript_2)|...|H(Subscript_Y)) H() = SHA256(SHA256())
YはSubscript
の数を示す1バイトの値で各Subscript
のハッシュが続く。
Script Root
はScript Hash
やPath
、Position
を引数に取るComputeMerkleRootFromBranch
関数を使って計算されるマークルルートである。
MAST Root
はH(MAST Version|Script Root)
で求める。ハッシュの原像は32バイトの固定サイズで、4バイトのMAST Version
と32バイトのScript Root
からなる。
MAST Root
がwitness programと一致しない場合、スクリプトの評価は失敗する。
MAST Root
がwitness programと一致しMAST Version
が0より大きい場合、スクリプトはその後の評価を行わず成功とし、SigOpsCostは0とカウントされる。これは将来のスクリプトのアップグレードのために予約されている。
MAST Version
が0の場合、最終的なMAST Script
を形成するSubscript
がシリアライズされており、Subscript_1から始まる。Subscript_1の前に記載されている未使用のwitness programはMASTScript
に供給するInput Stack
として使われる。
以下のいずれかの上限に当てはまるとスクリプトは失敗する。
MAST Script
の形式が不正。個々のSubscript
はシリアライズしてMAST Script
に含まれるためSubscript
の形式が不正な場合もある。MAST Script
のサイズが10,000バイトを超えているInput Stack
のいずれかのサイズが520バイトを超えている- 非プッシュ操作の数(
nOpCount
)が201を超えている。nOpCount
はMAST Script
内の非プッシュ操作の数の合計で、Subscript
(Y)の数とマークルツリーのDepth
。(P2WSHのwitnessScript
と同じ方法でカウントされる)
その後MAST Script
はInput Stack
と一緒に評価される(この際いくつかの新しいもしくは再定義したopcodeが導入されるが、まだBIP化されてないっぽい)。評価は失敗してはならず、結果スタックは空になる。
SigOpsCost
の計算はBIPYYY(未定義)に定義されたMAST Script
をベースにしている。
理論的根拠
MASTの構造
この提案は一般的なMASTに制限を加えている。一般的なMASTの設計では、ユーザはスクリプトの実行において1つもしくは複数のスクリプトのブランチを自由に割り当てることができるが、この提案では1つのブランチのみを許可し、ユーザは複雑な条件をいくつかの排他的なブランチに変換することを求められる。例えば以下のような解除条件がある場合、
(A or B) and (C or D or E) and (F or G)
一般的なMASTの設計では、A〜Gの7つのブランチが3レベルのマークルツリーを形成し、"overall condition"が異なるブランチの関係を説明する。ロックを解除する際は、実行されたブランチ(例えばB,D,F)とマークルパスデータが検証のために提供される。
現在の提案では、ユーザは解除条件を12個の排他的ブランチに変換し、4レベルのマークルツリーを形成しなければならず、解除にあたってはその内の1つのブランチのみが現れる↓
A and C and F B and C and F A and D and F . . B and E and G
この提案のような制約を設けず、一般的なMASTの設計を実装する1つの方法は、OP_EVALやOP_CAT、OP_HASH256を使うというものだが、不確定のプログラムループと静的プログラム解析をできないリスクを含むOP_EVALの問題に直面する(そもそもOP_EVALのBIP-12は採用されていない)。複雑な実装ではこれらの問題の解決が必須であり、それは難しい。
現在の提案には以下のようなアドバンテージもある。
Subscript
がwitnessスタック内の固定位置に配置されている。このため静的なSigOpsCost
のカウントや、無効なopcodeを持つスクリプトの早期終了といった静的なプログラム解析を可能にする。- 契約上の当事者たちがお互いに自分のスクリプトを公開したくない場合、各当事者は
H(Subscript)
(=Subscriptのハッシュ)を提供するだけで、ロックを解除するまでSubscript
の内容は秘匿される。 - 契約上の当事者たちが実際のスクリプトを共有したい場合は、スクリプトを1つの
Subscript
に組み合わせることで、nOpCount
とwitnessスペースの節約にもなる。
解除条件が非常に複雑な場合は、以下のようなディスアドバンテージがある。
- 前述したように一般的なMASTの設計より多くのブランチを必要とし、解除の際により多くのwitnessスペースをとる。
- MAST構造の作成とストレージには、より多くの時間とスペースが必要になる。ただそれらの追加のコストはコントラクトに関連する当事者にのみ影響があることで、他のビットコインユーザには関係ない。
MAST Version
この提案では、scriptPubKeyやscriptSigで行うより簡単なwitness内のスクリプト言語のバージョン指定を提案している。未定義のバージョンは誰もが拡張できるよう将来のために確保されている。新しいバージョンは、(MAST Script
の10,000バイトのサイズ制限などの)制約の緩和や、opcodeの追加 or 再定義、或いは全く新しいスクリプティングシステムを導入するために使用することができる。
nOpCountの制限
バージョン0のMASTでは、MAST Root
計算時のハッシュ操作は、不正利用を防止するため、nOpCount
は201までと制限する。この制限は柔軟性を持たせるため未定義のMAST Version
には提供されないが、Subscript
は255まで、Depth
は32までという制約はある。
Scriptの評価
P2WSHではスクリプト評価が成功するとスタック上にはTRUEのみが残るが、この提案ではスクリプト評価の結果スタックは空になる必要がある。これによりコントラクトの各当事者がそれぞれSubscript
を提供し、そのSubscript
クリーンナップするのに必要なInput Stack
を証明することができるようにする。この場合、評価の後にスタックをクリーンナップするので、Subscript
の順序は重要ではない。
例
MAST Rootの計算
Subscript:
SA = 1 EQUALVERIFY (0x5188)
SB = 2 EQUALVERIFY (0x5288)
SC = 3 EQUALVERIFY (0x5388)
SD = 4 EQUALVERIFY (0x5488)
SE = 5 EQUALVERIFY (0x5588)
SF = 6 EQUALVERIFY (0x5688)
SG = 7 EQUALVERIFY (0x5788)
SH = 8 EQUALVERIFY (0x5888)
M = RETURN "Hello" (0x6a0548656c6c6f)
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
HE = H(HA|HB) = 0x049b9f2f94f0a9bdea624e39cd7d6b27a365c6a0545bf0e9d88d86eff4894210
HH = H(HC|HD) = 0xc709fdc632f370f3367da45378d1cf430c5fda6805e731ad5761c213cf2d276e
HI = H(HE|HF) = 0xead5e1a1e7e41b77b794f091df9be3f0e9f41d47304eb43dece90688f69843b7
HJ = H(HG|HH) = 0xd00fc690c4700d0f983f9700740066531ea826b21a4cbc62f80317261723d477
Script Root = H(HI|HJ) = 0x26d5235d20daf1440a15a248f5b5b4f201392128072c55afa64a26ccc6f56bd9
MAST Root = H(MAST Version|Script Root) = H(0x0000000026d5235d20daf1440a15a248f5b5b4f201392128072c55afa64a26ccc6f56bd9) = 0xb4b706e0c02eab9aba58419eb7ea2a286fb1c01d7406105fc12742bf8a3f97c9
ネイティブなwitness programのscriptPubKeyは以下のようになる。
1 <0xb4b706e0c02eab9aba58419eb7ea2a286fb1c01d7406105fc12742bf8a3f97c9> (0x5120b4b706e0c02eab9aba58419eb7ea2a286fb1c01d7406105fc12742bf8a3f97c9)
SD|SE|SF
ブランチでロックを解除する際の、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)
Imbalance MAST
MASTを構築する際、ユーザはどのロック解除に使われるブランチが想定できるのであれば、そのブランチをScript Root
の近い位置に配置してもいい。そのように優先したブランチが実行された際はwitnessスペースの節約になる。
タイムアウトを使ったエスクロー
BIP-112(OP_CSV)を使ったタイムアウトが設定された以下ようなエスクローがあるとして
IF 2 <Alice's pubkey> <Bob's pubkey> <Escrow's pubkey> 3 CHECKMULTISIG ELSE "30d" CHECKSEQUENCEVERIFY DROP <Alice's pubkey> CHECKSIG ENDIF
圧縮した公開鍵を使ったとして、このスクリプトのサイズは150バイトになる。
MASTを使うと、このスクリプトは以下の2つのブランチに分けることができる。
2 <Alice's pubkey> <Bob's pubkey> <Escrow's pubkey> 3 CHECKMULTISIGVERIFY (105 bytes) "30d" CHECKSEQUENCEVERIFY <Alice's pubkey> CHECKSIGVERIFY (42 bytes)
公開されるのはどちらか一方のブランチのみなので、ブロックチェーンを分析してエスクローの詳細を確認することは難しい。
Hashed Time-Lock Contract
同じくBIP-112の例に出てくる以下の"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 Root
を作成するには、以下のように3つのブランチにフラット化される。
HASH160 <R-HASH> EQUALVERIFY "24h" CHECKSEQUENCEVERIFY <Alice's pubkey> CHECKSIGVERIFY HASH160 <Commit-Revocation-Hash> EQUALVERIFY <Bob's pubkey> CHECKSIGVERIFY "Timestamp" CHECKLOCKTIMEVERIFY <Bob's pubkey> CHECKSIGVERIFY
読みやすくなるし、ロック解除時のwitnessのサイズも小さくなる。
大規模なマルチシグの構築
現在CHECKMULTISIGは最大20個の公開鍵をサポートしている。IF/ELSEの条件と複数のCHECKMULTISIGを使うことで20個を超える鍵を利用できるよう拡張することはできるが、構造が複雑になりすぐ10,000バイトの制限や201のnOpCount
制限に引っかかるだろう。
MASTにより、大規模で複雑なマルチシグの構築は、多くの単純なCHECKMULTISIGVERIFY条件にフラット化される。例えば、3-of-2000のマルチシグは、31レベルのMASTで1,331,334,000個の3-of-3のCHECKMULTISIGVERIFYで表現できる(2000の中から3つを選択するコンビネーションなので2000C3=1,331,334,000)。scriptPubKeyは34バイトの固定サイズで、ロック解除するwitnessは1,500バイト以下というコンパクトなサイズになる。
非コンセンサスデータのコミットメント
現在、コンセンサスと関係無い任意のデータをscriptPubKeyに入れようとするとOP_RETURNを使う必要があり、ブロックスペースを占有する。MASTでは、ユーザはそのようなデータをブランチとしてコミットすることができる。実行可能なブランチの数に依存するが、そのようなコミットメントを含めてもwitnessのスペースは消費されないか、最大でも32バイト増えるだけになる。
後方互換
ソフトフォークのように、本BIPに対応していない古いノードでも更新することなく動作することが可能。ただ更新していないノードではMASTのwitness programはanyone-can-spend スクリプトとして判定されるだろう。ウォレットはそれらanyone-can-spendの取り扱いには充分慎重になる必要がある。
デプロイ
このBIPはBIP-141に依存しているのでBIP-141が有効になった後で、BIP-9のversion bitを使ってデプロイされる。具体的な日付は未定。
クレジット
MASTのアイディアはRussell O’Connor, Pieter Wuille, そして Peter Toddによるもの。
参照実装
//New rules apply if version byte is 1 and witness program size is 32 bytes if (witversion == 1 && program.size() == 32 && (flags & SCRIPT_VERIFY_MAST)) { CHashWriter sRoot(SER_GETHASH, 0); CHashWriter sScriptHash(SER_GETHASH, 0); uint32_t nMASTVersion = 0; size_t stacksize = witness.stack.size(); if (stacksize < 4) return set_error(serror, SCRIPT_ERR_INVALID_MAST_STACK); std::vector<unsigned char> metadata = witness.stack.back(); // The last witness stack item is metadata if (metadata.size() < 1 || metadata.size() > 5) return set_error(serror, SCRIPT_ERR_INVALID_MAST_STACK); // The first byte of metadata is the number of subscripts (1 to 255) uint32_t nSubscript = static_cast<uint32_t>(metadata[0]); if (nSubscript == 0 || stacksize < nSubscript + 3) return set_error(serror, SCRIPT_ERR_INVALID_MAST_STACK); int nOpCount = nSubscript; // Each condition consumes a nOpCount sScriptHash << metadata[0]; // The rest of metadata is MAST version in minimally-coded unsigned little endian int if (metadata.back() == 0) return set_error(serror, SCRIPT_ERR_INVALID_MAST_STACK); if (metadata.size() > 1) { for (size_t i = 1; i != metadata.size(); ++i) nMASTVersion |= static_cast<uint32_t>(metadata[i]) << 8 * (i - 1); } // Unknown MAST version is non-standard if (nMASTVersion > 0 && flags & SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_WITNESS_PROGRAM) return set_error(serror, SCRIPT_ERR_DISCOURAGE_UPGRADABLE_WITNESS_PROGRAM); sRoot << nMASTVersion; // The second last witness stack item is the pathdata // Size of pathdata must be divisible by 32 (0 is allowed) // Depth of the Merkle tree is implied by the size of pathdata, and must not be greater than 32 std::vector<unsigned char> pathdata = witness.stack.at(stacksize - 2); if (pathdata.size() & 0x1F) return set_error(serror, SCRIPT_ERR_INVALID_MAST_STACK); unsigned int depth = pathdata.size() >> 5; if (depth > 32) return set_error(serror, SCRIPT_ERR_INVALID_MAST_STACK); // Each level of Merkle tree consumes a nOpCount // Evaluation of version 0 MAST terminates early if there are too many nOpCount // Not enforced in unknown MAST version for upgrade flexibility nOpCount = nOpCount + depth; if (nMASTVersion == 0 && nOpCount > MAX_OPS_PER_SCRIPT) return set_error(serror, SCRIPT_ERR_OP_COUNT); // path is a vector of 32-byte hashes std::vector <uint256> path; path.resize(depth); for (unsigned int j = 0; j < depth; j++) memcpy(path[j].begin(), &pathdata[32 * j], 32); // The third last witness stack item is the positiondata // Position is in minimally-coded unsigned little endian int std::vector<unsigned char> positiondata = witness.stack.at(stacksize - 3); if (positiondata.size() > 4) return set_error(serror, SCRIPT_ERR_INVALID_MAST_STACK); uint32_t position = 0; if (positiondata.size() > 0) { if (positiondata.back() == 0) return set_error(serror, SCRIPT_ERR_INVALID_MAST_STACK); for (size_t k = 0; k != positiondata.size(); ++k) position |= static_cast<uint32_t>(positiondata[k]) << 8 * k; } // Position value must not exceed the number of leaves at the depth if (depth < 32) { if (position >= (1U << depth)) return set_error(serror, SCRIPT_ERR_INVALID_MAST_STACK); } // Sub-scripts are located before positiondata for (size_t i = stacksize - nSubscript - 3; i <= stacksize - 4; i++) { CScript subscript(witness.stack.at(i).begin(), witness.stack.at(i).end()); // Evaluation of version 0 MAST terminates early if script is oversize // Not enforced in unknown MAST version for upgrade flexibility if (nMASTVersion == 0 && (scriptPubKey.size() + subscript.size()) > MAX_SCRIPT_SIZE) return set_error(serror, SCRIPT_ERR_SCRIPT_SIZE); uint256 hashSubScript; CHash256().Write(&subscript[0], subscript.size()).Finalize(hashSubScript.begin()); sScriptHash << hashSubScript; scriptPubKey = scriptPubKey + subscript; // Final scriptPubKey is a serialization of subscripts } uint256 hashScript = sScriptHash.GetHash(); // Calculate MAST Root and compare against witness program uint256 rootScript = ComputeMerkleRootFromBranch(hashScript, path, position); sRoot << rootScript; uint256 rootMAST = sRoot.GetHash(); if (memcmp(rootMAST.begin(), &program[0], 32)) return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_MISMATCH); if (nMASTVersion == 0) { stack = std::vector<std::vector<unsigned char> >(witness.stack.begin(), witness.stack.end() - 3 - nSubscript); for (unsigned int i = 0; i < stack.size(); i++) { if (stack.at(i).size() > MAX_SCRIPT_ELEMENT_SIZE) return set_error(serror, SCRIPT_ERR_PUSH_SIZE); } // Script evaluation must not fail, and return an empty stack if (!EvalScript(stack, scriptPubKey, flags, checker, SIGVERSION_WITNESS_V1, nOpCount, serror)) return false; if (stack.size() != 0) return set_error(serror, SCRIPT_ERR_EVAL_FALSE); } return set_success(serror); }
まとめ&所感
- segwitで導入されたwitness programを利用した仕組みになる。witness programのversion 1をMAST用に利用。
- ロックの解除条件のブランチ毎にセグメントを分け、実行する解除条件のブランチのみを公開すれば解除ができるようになる。今まではscriptSigの中にredeem scriptが含まれているため、scriptSigを見れば全ての解除条件が分かるようになっていたのが、解除に使われなかったブランチの条件はブロックチェーン上に記載されることがなくなるのでプライバシーの向上になると。
- 複雑なロック解除条件を設定する場合にサイズ削減も含めて有効な手段となるため、単純にP2PKH宛にBitcoinを送るようなケースでは特にメリットは無い。
- P2SHで良いのでは?と思うが、P2SHのスクリプトにプッシュできるのは520バイトまでという制限と、解除に使わなかった未実行の条件も公開されプライバシーの問題が残る。
- P2WSHで考慮するとMAST導入のメリットは未実行のブランチのプライバシーと、スクリプトのスタックのサイズの削減?
- まだいくつか未定義の部分がある?
(SigOpsCostの計算や、Mast Script
を評価する際に導入される新しいopcodeなど) - ロック解除の際に最終的に公開されるのはロック解除に使ったブランチで、使われなかったブランチが公開されないという特性を活かしたコントラクトとか作れないかな?
- 今までOP_RETURNを使って任意のデータを付与してたのを、ブランチに移行するアプローチはいろいろ使えるかも。
- SPVの検証の際にトランザクションハッシュのマークルツリーを利用したり、今回のようにスクリプトブランチにマークルツリーを利用するといったように、マークルツリーを使ったハッシュチェーンを使うアプローチはいろいろ応用が出来そう。