ゼロ知識でふんわり理解するマークルツリー

マークルツリー

マークルツリーとは

要約結果を格納する木構造の一種であり、データの検証を行う際に使用される。
https://ja.wikipedia.org/wiki/ハッシュ木

💡 木構造とは

・枝分かれして広がっていく構造
https://wa3.i-3-i.info/word14397.html

例：配達物の中身が正しいか検証する

例としてマークルツリーを活用して配達物の中身が正しいことを検証します。

友人があなたに対して以下の物を送るとします。

この品物のデータに対してマークルツリーを利用すると以下のようになります。

赤字の0xe81..が検証に利用する値です。
あなたは友人からこの値と検証の仕方を伝えられていますが、具体的に何が何個送られてくるかは知らないものとします。

友人は配送業者に配達を依頼しました。
しかしあなたに対して品物が送られてくる途中、
配達員は小腹が空いたために勝手にみかんを1つ食べてしまいました。

するとマークルツリーは以下のように変化します。

品物が届いたあなたは検証をしますが、友人から聞いていた0xe81..と一致しません。
そのため届く品物の詳細を知らなくても友人が意図していた中身と違うことを知ることが出来ました。

(補足)

上記の例では品物全ての元データがある状態で検証を行いましたが、以下の黄色背景の3つの値が分かれば同様に検証が可能です。

例ではデータが4つだけなのであまり変わりませんがデータが1000など莫大な数の場合検証に必要な値を減らすことが可能です。

マークルツリー関連用語説明

(参考のmerkletreejsにある図をベースに作成)

💡 Root, Node, Leafはグラフの一般的な用語

• グラフ
  https://ja.wikipedia.org/wiki/グラフ_(データ構造)

• 根ノード、ルートノード

  枝分かれが始まる最初の要素のこと
  https://wa3.i-3-i.info/word18991.html

• ノード

  点と線で構成図を書いたときの点の部分
  https://wa3.i-3-i.info/word1300.html

• 葉ノード、リーフノード

  枝分かれしていない端っこの要素のこと
  https://wa3.i-3-i.info/word18992.html

Data

• 要約・検証したい元データ

Leaves(Leaf)

• Dataをハッシュ化した値
  💡 ハッシュ化

  元の値を「ハッシュ関数」と呼ばれる「値を中に放り込むと適当な値（適当に見える値）を返してくれる関数」に入れて「ハッシュ値」と呼ばれる「適当な値（適当に見える値）」に変換すること
  https://wa3.i-3-i.info/word16973.html

Nodes(Node)

• LeafまたはNodeを結合してハッシュ化した値
• 非リーフノードとも呼ばれる
• 上記の図では1階層のみだが、データが多いと複数階層になる

Root

• 全てのLeafをハッシュ化し終えた値。検証時(Verify)に用いる
• Rootの値はマークルルート、トップハッシュ、ルートハッシュ、マスターハッシュ等とも呼ばれる

Verify

• あるLeafがRootを生成する一部であるか確認すること
• 全てのLeafは必要なくProofがあれば良い

Proof

• Rootの再計算に必要な最小ノード群
• 前述(補足)の図 薄い黄色背景の値をLeafとしたとき濃い黄色背景の値がProofとなる
• マークルプルーフ、マークルパス等とも呼ばれる

その他：Solidityでマークルツリーを利用する(openzeppelin)

https://docs.openzeppelin.com/contracts/4.x/api/utils#MerkleProof

参考

https://www.npmjs.com/package/merkletreejs
https://www.smacon.dev/merkle-tree
https://prsarahevans.com/page-629/page-656/