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