Merkle Sum Sparse Merkle Tree - Develop with pleasure!

先日、Olaoluwa Osuntokunが発表したTaprootを利用したアセットオーバーレイプロトコルTaro↓

https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-April/020196.html

今回はその構成要素の１つであるMerkle Sum Sparse Merkle Tree（MS-SMT）の仕様についてみてみる↓

https://github.com/Roasbeef/bips/blob/bip-taro/bip-taro-ms-smt.mediawiki

MS-SMTは、Sparse Merkle TreeとMerkle Sum Treeを組み合わせたマークルツリーの一種。これらそれぞれのツリー構造自体は、Plasmaなど既存のプロダクトで既に採用されてる仕組みでもある。

Sparse Merkle Tree

Sparse Merkle Tree（SMT）というのは、key-valueのマップをマークルツリーにエンコードしたマークルツリーの一種。

通常のマークルツリーとの違いは、

ツリーのリーフノードの値はkey-valueマップのエントリー値になっており、そしてキーに対応するエントリー（ツリーのリーフノード）がどこにあるかは、キーをビットに展開し、ツリーのルートを0としてその左の子ノードを0、右の子ノードを1として、ツリーを上から下にキーのビットに対してリーフノードまで降りていくことで特定することができる。
キーに対応するエントリーが存在しない場合は、空の値がリーフノードにセットされる。空のリーフノードにはTaroの場合H(nil || nil || 0)がセットされる。

Taroではキーの値はSHA256値なので、キーは256 bitの範囲の値になる。このキースペースを持つツリーの深さは256で、 ${2^{256}}$ 個のリーフノードを持つ。

↑の仕様から、Sparse Merkle Treeにはマークルツリーにはない以下の特性を持つ。

キーから、対応するエントリーがツリー内のどの位置にあるかが分かる。
効率的に非包含証明を作成できる。
エントリーの値が空であることと、その空の値までのマークルプルーフを提供することで、あるエントリーがツリー内に存在しないことを証明する非包含証明を提供できる。
通常のマークルツリーで、ある要素が含まれていなことを証明しようとすると、ツリーの全てのリーフを公開する必要があり効率的ではない。

ビットマップを利用した最適化

非包含証明は、キーに対応した空のリーフノードが存在することを証明するため、空のリーフノードまでの兄弟ノードのリストをマークルプルーフとして提供する。しかし、空のリーフノードのハッシュ値は既知のデータであり（H(nil || nil || 0)のように）、その空ノード同士の親ノードのハッシュ値も事前に計算可能な既知の値になるため、マークルプルーフから

空ノードのノード値を除外し
代わりに経路のどのノードが空でないかを示すビットマップを追加する

ことで、マークルプルーフのデータスペースを節約することができる。

Merkle-Sum Tree

Merkle Sum Sparse Merkle Treeのもう１つの特性がMerkle-Sum。

通常、マークルツリーのリーフノードの値は要素のハッシュ値で、親ノードは2つの子ノードのハッシュ値を連結してそれをハッシュした値を自身のハッシュ値として、これをルートまで繰り返すことでルートハッシュを得る。

Merkle-Sum Treeというのは、この時単に要素のみにコミットするのではなく、その要素の属性の合計にもコミットするタイプのマークルツリー。Taroでは、8バイトの合計値（sum）を持つ。

例えば要素Aが100、要素Bが50の2つのリーフがあるとすると、その親ノードのハッシュ値は、

ParentAB = SHA256(H(A) || H(B) || (100 + 50))

さらにその親ノードABCDがある場合、同様の計算が行われ、以下のようなツリーになる。

f:id:techmedia-think:20220410163812p:plain

MS-SMT

MS-SMTは、↑のSparse Merkle TreeとMerkle-Sum Treeを組み合わせたツリー。

Taproでは、↑のMS-SMTツリーを使ってアセットツリーを構成し、そのルートハッシュをコミットメントとしてTaprootのスクリプトツリーに配置するようになってる*1。

そんなアセットを保持したTaprootアウトプットを転送する際に、

アセットの以前の所有者がアセットツリー内でアセットにコミットしていないこと
新しいアセットが作成されていないこと（アセットのインフレーションが発生していないこと）

を証明するため、非包含証明と、Merkle-Sumの特性から非インフレーションの証明にMS-SMTを利用するっぽい。

Taroのこのあたりの仕様については、また別途。

*1:そのため、オンチェーン上でアセットツリーやアセットの情報が直接的に記録されることはない。この辺りのアプローチはRGBとかも同じ