ビットコインを送金するときは、ただ単に「アリスからボブに1BTC送金する」という単純な取引だけでなく「ボブがアリスからの1BTCを3ヶ月間受け取らなかったら、チャーリーとダンが受け取れる」といった少し複雑な取引を行うことも可能です。
このようにある条件と異なる条件で送金の挙動が異なるようなときは、当記事では「条件分岐があるトランザクション」と表現します。条件分岐があるトランザクションでは柔軟に送金の挙動を設定することができるのですが、条件分岐が複雑になればなるほどトランザクションのデータサイズが大きくなってしまうというデメリットがあります。
条件が増えれば増えるほどトランザクションのデータが大きくなってしまい、その結果取引手数料が増えてしまったり、ビットコインのスケーラビリティ問題を深刻化させてしまうのです。
こういった問題を解決するために、MAST(Merklized Abstract Syntax Tree、マークル化抽象構文木)という技術が提案され実装開発が進めれています。
つまり、MASTは複雑な条件分岐があるトランザクションのデータサイズをコンパクトにすることができるのです。ここではこのMASTの仕組みと得られるメリットについて解説していきます。
ビットコインのスクリプト
ビットコインを送金するときは、送金者が取引データであるトランザクションを作成することにより実行されます。トランザクションには、ビットコインの送金額やそのトランザクションが作成された時刻（タイムスタンプ）などさまざまなデータが保存されています。
ビットコインを送金するためには、上図のインプットにあるscriptSigに送信者の公開鍵と署名をセットし、アウトプットにあるscriptPubKeyに送信先のアドレスを指定することで相手にビットコインを送ることができます。
- scriptSig：送信者の署名と公開鍵が必要
- scriptPubKey：送信先のアドレスが必要
このような必要な情報をビットコイン専用のスクリプト言語で記述することで送金が実行されトランザクションとしてその取引データが保存されるのです。
ビットコインのトランザクションスクリプトについては以下の記事で詳しく書いています。
参考：ビットコインおけるトランザクションスクリプトの仕組みとその種類
これをさらに発展させて、送金の実行のために複数人の公開鍵を必要とさせることもできます。これがいわゆるマルチシグと呼ばれていて、P2SHという種類のトランザクションスクリプトです。
さらに、条件分岐を使ってある条件ごとに異なる送金先を指定することも可能です。例えば、送金先は指定されていて、その送金を実行するためにはアリスの公開鍵が必要となるトランザクションがあったとします。このトランザクションに対して、もし３ヶ月間トランザクションが実行されなかったらボブとチャーリーの２人の公開鍵をセットすることで送金を実行できるという条件を付け加えることができるのです。
つまり、トランザクションに記述されるスクリプトは以下のようになります。
- アリスの公開鍵で実行できる
- もし、3ヶ月間アリスの公開鍵がセットされない場合はボブとチャーリーの2人の公開鍵をセットすることで実行できる
OP_If
<アリスの公開鍵> OP_CheckSig
OP_Else
“3 months” OP_CSV OP_Drop
2 <ボブの公開鍵> <チャーリーの公開鍵> 2 OP_CheckMultiSig
OP_EndIf
現状のビットコインのプロトコルでは上記のスクリプト全てがトランザクションに記録されブロックチェーンに保存されます。つまり、アリス自身が公開鍵をセットしてトランザクションを実行したとしても、後半の不要な条件付けもデータとして保存されてしまうのです。
このようなトランザクションの実行に条件分岐を含む場合、「満たされなかった条件」の方のデータは余分でありブロックチェーンに保存する必要はないはずです。
この余分なデータを保存しないようにする技術がMASTです。上記は単純な例でしたが、さらに多くの複雑な条件分岐があるようなトランザクションの場合、データサイズはかなり大きくなってしまいます。実際に、満たされる条件はひとつだけであるにも関わらず、満たされない条件のデータも全てブロックチェーンに保存されてしまうのです。
MASTとは
MASTとはトランザクションスクリプトを従来とは異なった形式で保存する技術です。従来のでは、上記のような条件分岐があるスクリプトもそのままブロックチェーンに保存されていました。
MASTではこのスクリプトをデータサイズ的にもっと小さくして保存することができるのです。これにより、ビットコインのブロックチェーンにおけるスケーラビリティ問題に有効だと期待されています。
しかし、条件分岐のスクリプトをただコンパクトにまとめて保存するだけでは「特定の条件だけを実行する」といった器用な操作は行うことができません。例えば、スクリプト全体をSHA-256のハッシュ関数に通せばデータサイズを32バイトにまとめることができますが、実行時（送金時）には結局、全ての元スクリプトを公開する必要があるのでデータサイズは削減できず意味がありません。
このような問題に対し、MASTは条件分岐のスクリプトにおいて実際に実行する条件のスクリプトのみを公開し、他の実行しない条件スクリプトは公開しない（ハッシュ化されたまま）ようにすることができるのです。
これを実現するために、抽象構文木(abstract syntax tree, AST)とマークル木(merkle tree)という2つの技術が使われます。
つまり、MASTは抽象構文木とマークル木を組み合わせた技術になります。MASTの仕組みを理解するためにまずは抽象構文木とマークル木の仕組みについて見ていきましょう。
抽象構文木(AST)
抽象構文木とは、全体のコードを意味のある小さなコードごとに分割してそれらをツリー状にまとめることです。
例えば、上記で例をあげたアリスとボブとチャーリーの条件分岐のコードは以下の図のように構造化することができます。（イメージだけつかめればOKです）
(source: What is a Bitcoin Merklized Abstract Syntax Tree (MAST)?)
マークル木（ハッシュ木）
マークル木とは、以下の図のようなツリー状のデータ構造になっていて下層にある2つのデータのハッシュ値をとることで、複数のデータを頂点にあるひとつのデータとしてまとめる技術です。マークル木によって最終的に出力されるデータもハッシュ値であり非常に小さなデータサイズにまとめられています。
(source: Bitcoin: A Peer-to-Peer Electronic Cash System)
つまり、マークル木はたくさんのデータをひとつにまとめることができるのです。このマークル木の優れているところは、ツリーを構成するひとつひとつのデータがそのマークル木に含まれているか簡単にチェックできることです。
上図の例であれば、マークル木のデータさえあればそのデータにTx2が含まれているのか簡単に確認できるのです。（マークル木に含まれているデータ自体はハッシュ化されているのでTx2のデータはマークル木にないにも関わらず！）
MASTではマークル木のこの特性を活用しています。
MASTの仕組み
MASTは上記の抽象構文木とマークル木を組み合わせた技術です。抽象構文木で条件分岐したスクリプトをそれぞれの条件で分割し、マークル木で全てのスクリプトが提示されなくてもある条件がそのスクリプトに含まれているかどうか確認することができるのです。
具体的に見ていきましょう。例えば、冒頭で紹介した「アリスが3ヶ月間実行しなかったらボブとチャーリーが実行できる」という条件分岐の例を抽象構文木で分割すると以下の2つに分けることができます。（当然ですが、実際は日本語ではなくスクリプト言語で記述されています）
- アリスの公開鍵で実行できる
- もし、3ヶ月間アリスの公開鍵がセットされない場合はボブとチャーリーの2人の公開鍵をセットすることで実行できる
以上の抽象構文木で分割した2つの条件をそれぞれマークル木に入れると以下の図のようになります。
まず1つ目の条件からハッシュ値①を得て、2つ目の条件からハッシュ値②を得ます。そして、それらのハッシュ値からハッシュ値①②を得ます。この頂点にあるハッシュ値①②はマークルルートと呼ばれています。
MASTではこのような形式で条件分岐のスクリプトを保存しておくのです。より厳密には、マークルルートに送金する資金をあらかじめロックしておき送金を実行するときに、「実行する条件のスクリプト」と「実行しない条件のハッシュ」と「実行する条件のマークル木における位置（マークルパス）」を提示することで実行できます。
例えば、MASTにおいて条件①を実行したい場合は、条件①のスクリプトである「<アリスの公開鍵> OP_CheckSig」を公開するだけでよく、条件②はハッシュ化されたままになります。
このような仕組みによりMASTでは条件分岐スクリプトのデータサイズをコンパクトにすることができるのです。
MASTのメリット
MASTは抽象構文木とマークル木によって、条件分岐のスクリプトを分割してそれをマークル木構造に割り当てます。これにより、スクリプト全体のデータサイズを小さくできるとともに、実行しない条件をハッシュのままにできるので、実行しない条件の匿名化にもつながります。
これはビットコインで複雑な条件分岐を伴うスマートコントラクトが行えるようになったとき、データサイズの大幅な削減を行えることにもつながります。
要するにMASTのメリットは主に以下のことがあげられます。
- トランザクションのサイズを小さくできる
- プライバシー保護につながる
それぞれについて詳しく見ていきましょう。
トランザクションサイズの削減
繰り返しになりますが、MASTでは条件分岐のスクリプトのデータサイズを小さくすることで結果的に、トランザクションのデータサイズを削減することが可能です。トランザクションのデータサイズが小さくなると、ブロックチェーンに加えられるトランザクション数も増え、送金時間の送れや取引手数料の増加など、ビットコインで深刻化しているスケーラビリティ問題の解決にもつながります。
ただ、上記のようなたった2つの条件分岐だとMASTの力を有効に使うことはできません
上記の例で「４ヶ月後にはダンとイーディスが実行可能」「５ヶ月後にはフレッドとジョージが実行可能」というように条件分岐を増やしていくとその分、トランザクションのデータサイズも増えていきます。
つまり、条件分岐が複雑になればなるほどその分トランザクションのサイズも増えてしまうのです。それに対し、MASTを使用するとスクリプトが複雑になってもデータサイズはほとんど増えないので、結果的にトランザクションのデータサイズを劇的に削減することが可能になります。
下図のグラフを参考にすると、スクリプトの条件分岐数が増えていくに比例してMASTを使用しない場合のスクリプトデータサイズは増加していきます。一方、MASTを使用する場合はほとんど増加していないことが分かります。
(source: What is a Bitcoin Merklized Abstract Syntax Tree (MAST)?)
現在、ビットコインでこのような複雑な条件分岐を使って送金することは滅多にありませんが、将来的に複雑な送金実行時にもトランザクションのデータサイズを大きくすることなく作成することができるのです。
プライバシー保護
MASTは複雑な送金でデータサイズを大幅に削減できる他にも、プライバシー保護にもつながります。MASTの以下の図をもう一度見てみましょう。
この図においてもし条件①が実行されたら、条件②のスクリプトは公開されず他の人は条件②の内容を見ることはできません。より正確に言うと、他の人は「他の条件の存在」を知ることはできますが、その条件の内容を知ることはできません。
なぜなら、条件②のスクリプトはハッシュ化されたままであり、ハッシュ値から逆算して元のスクリプトを復元することは不可能であるからです。逆に、条件②が実行されたら条件①の内容が他の人に公開されることはありません。このような条件の秘匿化はビジネス上での利用などを考えると重要になってくるでしょう。
また、MASTのこのような性質は、ビットコインの「代替可能性」の欠如に対する対策にもなります。ビットコインの代替可能性(Fungibility)の欠如とは、そのビットコインが過去に誰から誰に支払われたという「お金の追跡」が可能になっているという問題です。
もし条件分岐のスクリプトにMASTを使っていなかったら、それぞれの条件は他の人にも公開されているので、ビジネス上の競合相手がマイナーに対してそのトランザクションを承認しないように圧力をかける、といったことも可能になってしまいます。
しかし、MASTを使えば実行しない条件は他の人に伝わることはないので、このようなことを防ぎお金の追跡ができないようになっているのです。
以上のことがMASTによって得られるプライバシー面でのメリットになります。
ここまでMASTの仕組みや得られるメリットについて紹介してきました。このMASTをビットコインに実装するためにBIP114、BIP116などのさまざまな提案がされています。
元々のMASTの提案はBIP114でJohnson Lau氏によって提案されました。BIP114ではSegwitの実装を前提としてMASTが機能します。一方BIP116ではSegwitは必要はありません。
他にもBIP98やBIP117でMASTの新たなプロトコルの定義が提案されています。ビットコインをスケールさせていくためにもMASTは非常に重要な技術となり、開発が着実に進められているのが現状です。
