Merkle Mountain Range (MMR)
概要
MMRはMerkle木のお友達で空間効率性が高いデータ構造であり、大規模なデータセットを効率的に保存・検証することができる
イメージとしてはMerkle木のリストと考えることができる。下図のようにリストの要素(各緑の山)がMMRそのものである
https://scrapbox.io/files/671445fce615b55ac7405401.png
Ethereumにおけるworld state trieのleafにAccount storage trieのrootが収まるデータ構造に近しく見えるが、MMRは全てのMerkle 木が一つのRootに集約される点で異なる。つまりMMRにおいて各Merkle 木は親子関係ではなく兄弟関係に近い。
ちなみに、MMR全体のrootは山にちなんでpeakと呼ばれる。
https://scrapbox.io/files/67144d8b04e137d1b67ea740.png
Block headerに複数の役割が異なるMerkle 木のrootが格納されているわけだが、このようなデータ構造はMerkle Patrisia TreeではなくMMRでも表現できると思う。
仕組み
picassoとかいうプロジェクトの解説がわかりやすかったので引用する。 ここでは例として以下のような構造を考える。
白とオレンジ、青のMerkle木(sub tree)が存在し、三つの木のroot nodeのhashがMMRのRoot hashとなる。
https://scrapbox.io/files/671459a3defba5b47ea4887f.png
新しい要素(leaf)をMMRに追加する場合を考える。
既存のMMRツリーに新しい葉を追加する際は、同じ高さの任意の2つのsub treeが存在すればそれらをマージすることから始める
なぜこうするかと言うと、より新しい葉が追加されるたびに以前の計算(root hash)を再利用することができるためである
https://scrapbox.io/files/671457b11418c274810ac077.pnghttps://scrapbox.io/files/671459a92cb9af1a724468ab.png
もし同じ高さの任意の2つのsub treeが存在しなければ、最も高さの低いMerkle木に要素を追加する。
https://scrapbox.io/files/67145a21e841d7a10bf55104.png
なのMMR全体として見ると一つの高さにつき、一つのsub treeが構成される形になる。
MMRのsub treeは高さの降順で表示されるため、最初の部分木は通常、計算が最も重くなる。
逆に言うとリストが大きくなるにつれて、新しい葉の挿入と証明のコストが低くなることを意味する。
https://scrapbox.io/files/67145ed3c57acf2c524bd532.png
単一のMerkle木におけるinclusion proofと同様に、関連するsiblingsを用意すればproofできる。
Merkle Proofに際し、最も多くの要素を必要とするsub treeは最初のsubtree(白)で、4 + 2 = 6ノード必要になる。
(白の黄色点線ノード+青、ピンクsubtreeのroot)
基本的にappend onlyのデータ構造だが、grinではpruneもサポートしているらしい。
計算コストはsub treeに依存するのでlog(n)となる
応用
上記で説明したように簡潔なinclusion proofが作成できたり、更新が容易である点がMMRの特徴である。
また、ピークの数は非常にゆっくりと増加する点も強調できる。
秘匿送金プロトコルGrinをはじめとするいくつかのプロジェクトでストレージ構造として採用されている。 参考