Sparse Merkle Tree(SMT)
普通のMerkle Tree
アルファベット順に文字が格納されている木を想定する
普通のマークル木なら、Aがコミットされていることを証明するためにハッシュ関数を使い、H(B)とH(H(C)+H(D))からrootと比較して検証できる。
https://scrapbox.io/files/6218da83259409001d7f13d8.png
しかし、Aが木に含まれないことを証明することはできない。
内容をすべて明らかにすることはできるが、それではそもそもMerkle Treeを使う意味がない。
SMTはこのような課題を解決することができる。
つまり、SMTはInclusionの証明もnon-Inclutionの証明も可能
SMT
Sparse Merkle Treeは標準的なMerkle Treeと似ているが、含まれるデータにインデックスが付けられ、各データポイントはそのデータポイントのインデックスに対応する葉に配置される。
例えば、以下の木にいくつかの文字(A, D)を入れて考える。
2枚目と3枚目の葉は文字を置く代わりに特殊な値(nullなど)を置く
https://scrapbox.io/files/6218daf481c21c001d0d0659.png
Inclusionの証明
標準的なMerkle Treeと同じように、Merkle Proofを使って、A(もしくはD)がこの木の一部であることを証明することができる。
https://scrapbox.io/files/6218da83259409001d7f13d8.png
Non-inclusion proof
ツリーのリーフノードの値はkey-valueマップのエントリー値になっており、そしてキーに対応するエントリー(ツリーのリーフノード)がどこにあるかは、キーをビットに展開し、ツリーのルートを0としてその左の子ノードを0、右の子ノードを1として、ツリーを上から下にキーのビットに対してリーフノードまで降りていくことで特定することができる。
キーに対応するエントリーが存在しない場合は、空の値がリーフノードにセットされる。
各リーフノードは、キーと値(エントリーのキーと値に対応)、およびキーと値をハッシュ化して得られるハッシュプロパティを持つ。あるエントリーがマップに存在しない場合は、空のリーフノード(空の値と一定のハッシュを持つノード)を割り当てるだけ
データブロックの挿入順序は関係なく、木のルートはマップの最終状態にのみ依存する
証明者は、他の要素を明かすことなく、ある要素が基本データ構造に存在することを検証者に説得でき、証明サイズはデータブロック数に対して対数的に拡大する
履歴に依存しないため、SMTはKey-Value Mapを認証するのに適している。
ハッシュ関数の入力は基礎となるキー・バリュー・マップであり、出力はMerkleルートと言える
もしCが木の一部でないなら、3番目の葉は空でなければならない.あとは、3枚目の葉が空であることを示す標準的なMerkle Proofだけ。もし3枚目の葉がnullでなければrootの結果は異なる
https://scrapbox.io/files/6218dd3855e776001e9d23bd.png
必要なのは青いところだけ。普通のマークル木は全てのリーフを必要とする。また、3枚目の葉がnullであることを予め主張する必要がある
つまり、全てのkeyは0から始まる? rootではなくその下のノードによって最初の0/1 は変わる
通常のマークルツリーとの違い
RMT (left) and a SMT (right)
https://scrapbox.io/files/6319bb076f0cc50023585f42.png
Merkle木は、基礎となるデータ構造が配列であるため、ベクトルコミットメントの一例として考えられる。
つまり、Merkleルートは、配列内のデータブロックの順序も認証することになる。
この特性は、たとえばブロックに含まれるトランザクションや、一般に配列を扱う場合には非常に有用
しかし、特定の位置に新しいデータブロックを挿入することは、ツリー全体を再計算する必要があるため、効率的に行うことができない。
このため、通常のMerkle木はKey-Value Mapの認証には適さないが、新しいデータブロックが追加されるだけの配列の認証には適している。
つまり、SMTがMerkle木の上位互換とかではない
SMTは、key-valueのマップをマークルツリーにエンコードしたマークルツリーの一種と言える
incrusion-proof可能で挿入順序は関係ないなどの特徴からアキュムレータとも言える
↑の仕様から、Sparse Merkle Treeにはマークルツリーにはない以下の特性を持つ。
キーから、対応するエントリーがツリー内のどの位置にあるかが分かる。
効率的にNon-inclusion proofを作成できる。
エントリーの値が空であることと、その空の値までのマークルプルーフを提供することで、あるエントリーがツリー内に存在しないことを証明するNon-inclusion proofを提供できる。
通常のマークルツリーで、ある要素が含まれていないことを証明しようとすると、ツリーの全てのリーフを公開する必要があり効率的ではない。
ビットマップを利用した最適化
(リスクのブログより)
例えば、政府が先月にCovidの検査で陽性となった人の中央登録を行っているとします。各人には、国民ID番号と現在の月の組み合わせであるIDが割り当てられます。この中央登録簿はSMTで整理され、公共のイベントに参加するには、全員が自分のIDが中央登録簿に含まれていないことを非包括証明で示さなければなりません。
しかし、そこには落とし穴がある。前述したように、SMTには鍵の数だけノードがあり、256ビットの鍵の場合、$ 2^{256}のリーフノードと256のレイヤーが存在することになる。現実的なシナリオでは、これらのリーフノードの大部分は空であり、関連するマップの項目はない(そのため疎なMerkle木と呼ばれる)ことに注意してください。このような天文学的な数のノードを保存し、操作することは不可能である。そこで、以下のような最適化を行っている。
ちょうど1つの空でない葉を持つ各サブツリーは、その葉自体に置き換えられる。
空のノードのみを含む各サブツリーは、空のノード、固定ハッシュ値を持つ定数ノードに置き換えられる。
https://scrapbox.io/files/6319bc9de2ce650023801bec.png
この結果、鍵がランダムに分布している場合、マップのエントリ数をNとすると、Log(N)としてスケールする層数を持つ木が得られる。これにより、木に対する操作は平均でLog(N)のステップを要し、non-incrusion proofは平均でLog(N)のサイズとなることが保証される。
(安土さんブログ)
Non-inclusion proofは、キーに対応した空のリーフノードが存在することを証明するため、空のリーフノードまでの兄弟ノードのリスト(siblings)をマークルプルーフとして提供する。しかし、空のリーフノードのハッシュ値は既知のデータであり(H(nil || nil || 0)のように)、その空ノード同士の親ノードのハッシュ値も事前に計算可能な既知の値になるため、マークルプルーフから
空ノードのノード値を除外し
代わりに経路のどのノードが空でないかを示すビットマップを追加する
ことで、マークルプルーフのデータスペースを節約することができる
https://scrapbox.io/files/632669ddfaf9930022a7ed2a.png
赤がシビリング
参考文献