Bitcoinの複雑な条件のコントラクトをコンパクトに実現するMAST

BitcoinのスクリプトはEthereumのコントラクトほどの自由度はないものの、コインのアンロック条件を複数持つコントラクトを書くことができる。

例えば以下のスクリプトにロックされているコインは：

IF 2 <アリスの公開鍵><ボブの公開鍵> 2 CHECKMULTISIGVERIFYELSE HASH160 <ｈ(x)> EQUAL <ボブの公開鍵> CHECKSIGVERIFYENDIF</ボブの公開鍵></ｈ(x)></ボブの公開鍵></アリスの公開鍵>

以下のいずれかの方法でアンロックできる。

• アリスとボブが協力してマルチシグの署名があればアンロック可能
• ある秘密の値xとボブの署名があればアンロック可能

通常こういったスクリプトにコインをロックする場合は、スクリプトのハッシュをロックスクリプト（scriptPubkey）に含めるP2SHアドレスを作成して、そのアドレス宛にコインを送る。コインを使用する場合は上記のいずれかの条件を満たすデータをトランザクションのインプットにセットする。この仕組みは今でも実際に利用できる。

ただ上記はIF/ELSEの２つの分岐だけだが、より複雑な条件を持つ巨大なスクリプトを作ろうとした場合、スクリプトのサイズ制限にひっかかる。また、実際にアンロックする際に使用する条件はどれか１つにも関わらず、使用しない条件も含めてスクリプトを開示する必要があり：

• 大きなスクリプトになるほど手数料が増える
• 使わない条件もブロックチェーンに記録され、無駄にブロックチェーンのスペースを使用する
• 使用しない条件もブロックチェーン上で公開されてしまう

といった課題がある。

Merkelized Abstract Syntax Tree

こういった課題を解消しようと、2016年4月にBIP-114としてMAST（Merkelized Abstract Syntax Tree ＝ マークル化抽象構文木）という仕組みが提案された。

Abstract Syntax Tree = 抽象構文木は、プログラムのソースコードを構文解析する際によく使われるプログラムコードを木構造で表現するデータ構造で、MASTではBitcoinのスクリプトをアンロック条件毎に分割し、分割した各条件を使ってマークルツリーを構成する。例えば、以下の４つのアンロック条件があるスクリプトを考える。

1. アリスとボブのマルチシグがあればアンロック可能
2. キャロルとマイクのマルチシグがあればアンロック可能
3. 秘密の値xを知っていればアリスの鍵だけでアンロック可能
4. ３ヶ月経過したらキャロルの鍵のみでアンロック可能

１〜4のアンロック条件をリーフノードとして、以下のようなマークルツリーを構成する。

既存のP2SHでは、スクリプト全体のハッシュ値をロックスクリプトにセットするが、MASTの場合はこの計算したマークルツリーのルートハッシュをロックスクリプトにセットする。ルートハッシュにロックされたコインを使用する際は、以下のデータを提供する。

• アンロックに使用する条件のスクリプト
• マークルツリー内のその条件までのパス（経路）と実行しないパスのハッシュ
• そのスクリプトの条件を満たすデータ

例えば条件２（キャロルとマイクのマルチシグがあればアンロック可能）を使ってコインをアンロックする場合は、以下のデータ要素をアンロックスクリプトにセットして検証を行う。

• まずアンロックスクリプト内の以下のデータを使ってマークルツリーを復元し、ロックスクリプトに記録されているルートハッシュと等しいか検証する。
• ルートハッシュから条件２のリーフノードへのパス（経路）情報
• 実行しないパスのハッシュ（条件２を使用する場合は、条件１のハッシュとハッシュ34のデータの２つが必要）
• これが等しければ、条件２のスクリプトをアンロック可能なデータが提供されているか検証する（この場合、有効な署名がそれぞれ提供されていればOK）。

以上をまとめると、MASTを利用する場合は、スクリプトの各条件をリーフノードにしたマークルツリーを構成し、そのルートハッシュにコインをロックする。コインをアンロックする場合は、アンロックに使用する条件がマークルツリーに含まれていることを証明して、そのアンロック条件を満たすデータを提供する。このMASTの仕組みを利用するとアンロック時に、使用する条件のみを開示すればいいため：

• 複雑で巨大なスクリプトでもサイズ制限にひっかかることなく実現できる
• トランザクションのデータサイズが削減できるので、手数料が低くなり、無駄にブロックチェーンのスペースを使用することがない
• 使用しない条件は公開されないので、プライバシーも向上する

といった恩恵が受けられる。

MASTの実現方法

BIP-114として提案されたMASTだが、実は2017年11月に新しい実現方式BIP-116が提案されている。両者には主に以下の違いがある。

• BIP-114
  Segwitで導入されたwitness versionを利用する。Segwitではwitness version 0 を使ってSegwitトランザクションを利用できるように拡張がされたが、witness version 1をMAST用に割り当てる。
  ロックスクリプトが”1 <32バイトのハッシュ値>” の場合、このハッシュ値をルートハッシュとして解釈し、witness領域に使用するスクリプトおよび経路、アンロックに必要なデータをプッシュする。</32バイトのハッシュ値>
• BIP-116
  OP_MERKLEBRANCHVERIFYというマークルツリーのブランチを検証することができる新しいopcodeを追加する。こちらは新しいopcodeによる拡張なのでSegwitの有無関係なく導入が可能。

いずれもソフトフォークでの導入だ。

MAST以外の選択肢

BIP-114とBIP-116でそれぞれBIP化されているが、まだBitcoin Coreにはコードがマージされておらず（BIP-116はプルリクエストがある）、ソフトフォークのデプロイスケジュールも現時点では決まっていない。

そんな中、Blockstreamの元CTOであるGreg MaxwellがGraftrootというまったく新しいコンセプトを発表した。詳細については省略するが、GraftrootにはMASTのプライバシーをさらに向上させ、さらに後からアンロック条件を追加できるという柔軟で強力な機能がある。このため、MASTに代わってGraftrootが導入されるということも考えられ、今後が注目される。