title | emoji | type | topics | published | |
---|---|---|---|---|---|
ゼロ知識でふんわり理解するマークルツリー |
🌲 |
tech |
|
true |
要約結果を格納する木構造の一種であり、データの検証を行う際に使用される。 https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E6%9C%A8
:::details 💡 木構造とは
・枝分かれして広がっていく構造 https://wa3.i-3-i.info/word14397.html :::
例としてマークルツリーを活用して配達物の中身が正しいことを検証します。
友人があなたに対して以下の物を送るとします。
この品物のデータに対してマークルツリーを利用すると以下のようになります。
赤字の0xe81..
が検証に利用する値です。
あなたは友人からこの値と検証の仕方を伝えられていますが、具体的に何が何個送られてくるかは知らないものとします。
友人は配送業者に配達を依頼しました。 しかしあなたに対して品物が送られてくる途中、 配達員は小腹が空いたために勝手にみかんを1つ食べてしまいました。
するとマークルツリーは以下のように変化します。
品物が届いたあなたは検証をしますが、友人から聞いていた0xe81..
と一致しません。
そのため届く品物の詳細を知らなくても友人が意図していた中身と違うことを知ることが出来ました。
上記の例では品物全ての元データがある状態で検証を行いましたが、以下の黄色背景の3つの値が分かれば同様に検証が可能です。
例ではデータが4つだけなのであまり変わりませんがデータが1000など莫大な数の場合検証に必要な値を減らすことが可能です。
:::details 💡 Root, Node, Leafはグラフの一般的な用語
-
根ノード、ルートノード
枝分かれが始まる最初の要素のこと 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
をハッシュ化した値 :::details 💡 ハッシュ化元の値を「ハッシュ関数」と呼ばれる「値を中に放り込むと適当な値(適当に見える値)を返してくれる関数」に入れて「ハッシュ値」と呼ばれる「適当な値(適当に見える値)」に変換すること https://wa3.i-3-i.info/word16973.html :::
Leaf
またはNode
を結合してハッシュ化した値- 非リーフノードとも呼ばれる
- 上記の図では1階層のみだが、データが多いと複数階層になる
- 全ての
Leaf
をハッシュ化し終えた値。検証時(Verify
)に用いる Root
の値はマークルルート、トップハッシュ、ルートハッシュ、マスターハッシュ等とも呼ばれる
- ある
Leaf
がRoot
を生成する一部であるか確認すること - 全ての
Leaf
は必要なくProof
があれば良い
Root
の再計算に必要な最小ノード群- 前述(補足)の図 薄い黄色背景の値を
Leaf
としたとき濃い黄色背景の値がProof
となる - マークルプルーフ、マークルパス等とも呼ばれる
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/