【完全保存版】マークルツリー(Merkle Tree)について、しっかりと理解しよう！
１ マークルツリー(Merkle Tree)とは
１ 構造について
マークルツリー(Merkle Tree)とは、下のような構造のものです。
ちょっとわかりにくいので、一つ一つ見ていきましょう。
２ 作成方法について
ハッシュ化して、連結して、ハッシュ化して。。を繰り返して、一番上の「Root」を導きます。
ハッシュ化についてご不明な場合は、この辺りの記事が参考になると思います。
３ 名称について
そして、一番下の情報を「データ」、それをハッシュ化した末端を「リーフ」と呼びます。
「ルート」が根っこで「リーフ」が葉っぱなので、木を逆さまにしたイメージです。
この辺りの情報はいろいろなところで見聞きするかもしれません。
４ 検証について
ただ、大切なのは、ルートの作成過程で特定のリーフが使われたかどうかを少ない情報から検証できる
ということだと思います。
この辺りを基礎からしっかりとみていきたいと思います。
まずは、先ほどのマークルツリーを一つ一つ見ていきましょう。
２ マークルツリーの作成方法について
１ データからリーフの作成について
「あ」というデータをハッシュ化すると、「55e…c1c」になりました。
（後から、「a」などのデータを使えばよかったなと思いましたが、このまま行きますね。）
つまり、このような感じです。
次に、「い」も同様にハッシュ化してみます。
こんな感じになりました。
２ ハッシュ値の連結について
次に、上でできた２つのハッシュを連結させます。
こんな感じです。
３ 連結値のハッシュ化について
それをまた、下のようにハッシュ化します。
こんな感じになりました。
あとは、同じことを、「う」と「え」というデータでもやってみました。
こんな感じになりました。
３ リーフの検証方法について
１ 証明に必要なハッシュ値（Proof）について
では、下にある「1a5…153」からルートを導くには、どのハッシュがあれば良いでしょうか？
前提として、全てのハッシュが保存されていると考えます。
下のようにある配列に０から６まで、全てのハッシュが格納されています。
答えは、下の２つです。
「55e…c1c」があれば、「91f…993」を導くことができます。
そして、「8b4…31a」があればルートを導くことができます。
では、もう少し数を増やしてみましょう。
下のリーフから、ルートに行くにはいくつのハッシュが必要でしょう。
なお、先ほどと同様に、0から14まで全てのハッシュは格納されています。
答えは、こちらの３つです。
先ほどと考え方は同じですね。
では、こちらはどうでしょう？
答えはこちらの４つです。
何となく見えてきましたね。
２ 検証の方法について
これは検証に使うことができます。
上の場合、「リーフ」と４つの必要なハッシュで「ルート」を導けます。
作成したルートと、与えられたルートが合致すれば、検証成功です。
３ 検証に必要なProofの数について
では、次に検証に必要な情報（Proof）の数を考えてみましょう。
例えば、下の場合、２つのProofが必要です。
この時のデータの数は、２の２乗の４つです。
下の場合は、３つ必要です。
この時のデータの数は、２の３乗の８個です。
下の場合は、４つ必要です。
この時のデータの数は、２の４乗の１６個です。
つまり、例えば、２の10乗の1024個のデータがあった時、10個のハッシュがあれば、検証が可能です。
このように、マークルツリーを使うことで、少ないハッシュ値で検証を行うことができます。
４ 検証時の順番について
では、実際の検証をもう少し詳しくみていきましょう。
下のリーフを検証するには、青の３つのProofが必要です。
下からたどっていくので、下のような順番で、「Proof」が必要になってきます。
５ 連結時の順番（左右）について
では、連結してハッシュ化するところを見てみましょう。
ここで大事なのは連結の順番です。
「Proof① ＋ Leaf」か「Leaf ＋ Proof①」で求まるハッシュが変わってしまいます。
ここで重要になるのが、リーフの順番である、「Index」です。
Indexは０から始まり、下の場合は「5」になります。
そして、下のように、奇数は右に配置されていることがわかります。
そのため、このリーフは右に配置されるので、下のように「Proof①＋Leaf」という順番になります。
６ 階層が変わった際のIndexについて
次は、一つ上の階層に行ってみましょう。
先ほどの階層では「Index」は「5」でしたが、今回の階層では、下のように「Index」は「2」になりました。
「Index」が２で偶数なので、下のように「結果① + Proof②」のように、リーフから来た結果が左に配置されました。
最後の階層を見ると、「Index」は「1」で奇数になっています。
そのため、今度は右に配置されます。
つまり、下のように、リーフ由来の結果が右に配置されました。
このようにして、Rootを求めることができました。
４ 検証をコードベースで確認してみよう
では、実際に、コードからマークルツリーを理解してみましょう。
こちらのコードを用いてみます。
１ 引数について
下のようなコントラクトがあります。
引数として必要な「①Proof」「②Root」「③Leaf」「④Index」があります。
「Proof」の中には、検証に必要な数の情報が格納されています。
２ 繰り返しの数について
次に、Proofの数だけ繰り返し処理を行います。
今回の例ですと、３回実行するのですね。
３ Proofの取得について
次に、使うProofを取り出していますね。
今回の例ですと、最初に、「Proof①」が取り出されます。
４ 左右の判断について
次に、「Index」が奇数か偶数かで左右を判断しています。
下の場合、「Index」は「5」で奇数なので、右に配置されます。
次に、「Index」が奇数か偶数かで場合分けを行い、連結して、ハッシュ化しています。
こちらですね。
５ 改装変更時のIndexの取得について
次に、新しい「Index」を取得しています。
今回の場合、５を２で割った結果の整数部分である、「2」を取得しました。
６ 最終検証について
これを最後まで繰り返し、最終のハッシュが与えられたルートと一致するかを確認します。
５ ハッシュの格納をコードベースで確認しよう
では、次に、上の「MerkleProof」コントラクトを継承した「TestMerkleProof」コントラクトを見てみましょう。
１ ハッシュ格納用の配列について
まず、「hashes」という配列を用意します。
ここにハッシュを格納していきます。
２ constructorについて
次に、こちらの「constructor」を見てみましょう。
こちらはコントラクトのデプロイ時に１度だけ行われる処理です。
３ テスト用データの格納について
下の部分でテスト用のデータを格納しています。
４つのトランザクションがあったことを想定しているようです。
４ データのリーフ化とその書くのについて
次に、それらのデータをハッシュ化して「hashes」に格納しています。
今は、この部分をやっています。
（簡易的にデータ４つのケースで見ていきます。）
５ データの数の取得について
次に、データの数を求めます。
今回は４つです。
６ オフセットの初期値の設定について
次に、オフセットを設定します。
後で、階層が変わる時に、「最初から数えて何番目か」を確認するために使います。
７ 生成したハッシュの格納について
次に、新しく生成したハッシュを「hashes」に格納していきます。
こちらの部分をやっています。
８ オフセットの更新について
次に、データの数（４）をオフセットにプラスしています。
これを行うことで、次の階層のデータは先頭から数えて何番目かを確認することができます。
９ 新しい階層のデータ数の取得について
その上で、新しい階層のデータの数を取得しています。
下のように、新しい階層の数は２つです。
１０ ルートの取得について
これを最後まで繰り返します。
それにより、最後に格納されるハッシュはルートになります。
そのため、ルートを取得するということは、「hashes」の最後を取得するということになります。
図で見る方がわかりやすいかもですね。
こちらの最後のハッシュがルートになります。
６ 実際のデータを使い、検証を行おう
では、理論はわかったので、実際に検証してみましょう。
１ ルートの取得について
「getRoot」関数でルートを求めます。
このようになりました。
なお、今回は元となるデータは４つです。
２ ルートの確認について
ということは「hashes」の６番目がルートになります。
（0から始まるので7番目ですが、この辺りはスルーします。以下同様です。）
実際、「hashes」に「6」を入れて、確認すると、ルートと一致することが確認できました。
３ リーフの取得について
では、こちらの２番目のリーフを検証してみましょう。
まずは、こちらのハッシュを下のように求めます。
下のようになりました。
４ Proofの取得について
そして、今回検証に必要なのは下の二つです。
まず、３番目は下のようになりました。
こんな感じです。
４番目は下のようになりました。
つまり、こんな感じです。
５ 検証の実施について
これで必要なものが全て揃いました。
これらを使って検証を行うと、下のように「true」となり、うまくいきました。
これで特定のリーフがルートの作成過程に含まれているかの検証を行うことができました。
今回は以上です。
サポートをしていただけたらすごく嬉しいです😄 いただけたサポートを励みに、これからもコツコツ頑張っていきます😊