マークルツリー

マークルツリーとは？

マークルツリーとは、多数のデータをハッシュのツリー構造に整理する暗号学的データ構造です。

暗号資産分野では、ブロックチェーンがトランザクション、残高、アカウント、ストレージ値、エアドロップの請求、NFTの許可リスト、その他の大規模なデータセットを効率よく検証するために利用されます。

マークルツリーは、各階層が暗号学的ハッシュ値で構成されるため、ハッシュツリーとも呼ばれます。

最下層には、リーフと呼ばれる個々のデータ項目が含まれています。

各リーフをハッシュ化し、別のハッシュとペアにして再びハッシュ化することで、次の階層を作成します。

このプロセスを繰り返し、最上部に1つの最終ハッシュを生成します。

この最終ハッシュがマークルルートです。

Bitcoinの開発者ガイドでは、トランザクションハッシュをペアにして繰り返しハッシュ化し、ブロックヘッダーに1つのマークルルートを生成すると説明されています。

基本的な考え方はシンプルです。1つの小さなルートで大規模なデータセットを表せます。

データセット内の項目が1つでも変わると、その上位にあるハッシュも変わり、マークルルートが変化します。

マークルツリーの仕組み

マークルツリーは、トランザクション、ウォレットアドレス、アカウント記録、請求情報などの生データから始まります。

各項目に暗号学的ハッシュ関数を適用し、リーフハッシュを生成します。

2つのリーフハッシュを組み合わせてハッシュ化し、親ハッシュを作成します。

次に、親ハッシュをペアにして再びハッシュ化し、さらに上位のハッシュを生成します。

ハッシュが1つだけになるまで、このプロセスを続けます。

この最終ハッシュがマークルルートです。

マークルルートは、データセット全体を表すコンパクトなフィンガープリントとして機能します。

データが変更されていなければ、同じツリー構築方法によって同じルートが生成されるはずです。

トランザクション、アドレス、残高、請求額のいずれかが変わると、最終ルートも変わるはずです。

暗号資産分野でマークルツリーが重要な理由

ブロックチェーンでは、すべてのユーザーが常にすべてのデータを処理しなくても、大量のデータを検証する必要があるため、マークルツリーは重要です。

ブロックチェーンのブロックには、多数のトランザクションが含まれる場合があります。

トークンエアドロップには、対象となるウォレットが数千、数百万含まれる場合があります。

ブロックチェーンの状態データベースには、アカウント、残高、コントラクトのストレージ、コードなどが含まれる場合があります。

マークルツリーを使うと、システムは大規模なデータセットを1つのルートでコミットし、後から個々の項目を検証できます。

これにより、効率性、スケーラビリティ、データの完全性が向上します。

また、多くの暗号資産アプリケーションで、ストレージや帯域幅の要件を軽減できます。

マークルツリーや同様の認証済みデータ構造がなければ、多くのブロックチェーン検証は処理が遅く、負荷が大きく、コストも高くなります。

マークルルート

マークルルートは、マークルツリーの最上部にある最終ハッシュです。

その下にあるすべてのデータを表します。

ブロックチェーンのブロックでは、マークルルートによって、そのブロックに含まれるすべてのトランザクションを要約できます。

エアドロップ用コントラクトでは、マークルルートによって、対象となるすべてのウォレットアドレスと請求額を要約できます。

ステートツリーでは、ルートによって多数のアカウントやストレージ値を要約できます。

ルートだけでは、データセット全体は明らかになりません。

ルートは、そのデータセットに対する暗号学的コミットメントとして機能します。

1つの項目がツリーに含まれることを確認するには、ユーザーは適切な証明と検証規則も必要です。

マークルツリーのリーフとブランチ

リーフは、マークルツリーの最下層にあるハッシュです。

通常、各リーフは1つのデータ項目を表します。

たとえば、トランザクションハッシュ、ウォレットアドレス、請求記録、NFTのミント許可、アカウント値などをリーフで表すことがあります。

ブランチは、リーフとルートの間にある中間ハッシュです。

ブランチによって個々のリーフが最終的なマークルルートにつながります。

マークル証明は、これらのブランチハッシュを使い、1つのリーフがツリーに含まれていることを証明します。

この設計により、他のすべてのリーフを表示またはダウンロードせずに検証できます。

マークルツリー証明

マークルツリー証明とは、既知のルートを持つツリーにリーフが含まれていることを証明するために必要な兄弟ハッシュの集合です。

検証者は対象のリーフから始め、証明に含まれるハッシュを正しい順序で組み合わせます。

最終的に計算されたハッシュが信頼できるルートと一致すれば、証明は有効です。

最終的に計算されたハッシュが信頼できるルートと一致しなければ、証明は無効です。

OpenZeppelinのMerkleProofドキュメントでは、ルートで定義されたマークルツリーの一部であることをリーフが証明できるか、スマートコントラクトで検証するためのツールが説明されています。

このため、マークルツリーはオンチェーンの許可リスト、請求、報酬、アクセス確認に役立ちます。

Bitcoinにおけるマークルツリー

Bitcoinは、ブロック内のトランザクションを整理するためにマークルツリーを使用します。

各トランザクションをハッシュ化し、トランザクションハッシュをペアにして上位へとハッシュ化を繰り返し、1つのマークルルートを生成します。

マークルルートはブロックヘッダーに保存されます。

これにより、Bitcoinのノードはトランザクションデータが変更されたかどうかを検出できます。

また、軽量なトランザクション検証にも利用されます。

ライトクライアントは、ブロック内のすべてのトランザクションをダウンロードせずに、マークル証明を使ってトランザクションがブロックに含まれているかを確認できます。

これは、一般にSPVと呼ばれる簡易支払い検証を支えています。

SPVはフルノードによる検証ほど完全ではありませんが、リソースが限られたデバイスやウォレットで、より効率的に利用できます。

Ethereumにおけるマークルツリー

Ethereumは、マークルパトリシアトライと呼ばれる関連する認証済みデータ構造を使用します。

Ethereumのマークルパトリシアトライに関するドキュメントでは、Ethereumの構造が決定論的で、暗号学的に検証可能だと説明されています。

この構造により、Ethereumはアカウント状態、ストレージ、その他のキー・バリュー形式のデータを表せます。

状態が変わると、ステートルートも変わります。

そのため、Ethereumのクライアントやアプリケーションは、既知のルートに対して状態データを検証できます。

EIP-1186のeth_getProof標準では、Ethereumのアカウントやストレージ値のマークル証明を取得するRPCメソッドが定められています。

Ethereumの構造は単純な二分マークルツリーとは異なりますが、ハッシュで連結されたデータを検証するという基本的な考え方は共通しています。

エアドロップにおけるマークルツリー

暗号資産のエアドロップでは、大規模な請求対象リストを管理するためにマークルツリーを使うことがよくあります。

プロジェクトは対象となるウォレットアドレスとトークン数量のリストを作成します。

アドレスと数量の各組み合わせが、マークルツリーのリーフになります。

プロジェクトは、マークルルートのみをスマートコントラクトに保存します。

ユーザーがエアドロップを請求する際は、マークル証明を提出します。

コントラクトは、ウォレットと数量が保存されたルートで表されるツリーに含まれていることを検証します。

対象となるすべてのウォレットをオンチェーンに直接保存する必要がないため、ガス代を節約できます。

また、大規模な請求キャンペーンをより実施しやすくなります。

NFTの許可リストにおけるマークルツリー

NFTプロジェクトでは、許可リスト、プレセール、早期ミントアクセスにマークルツリーがよく使われます。

承認済みのウォレットアドレスをすべてコントラクトに保存する代わりに、プロジェクトは1つのマークルルートを保存します。

承認された各ウォレットには、許可リストに含まれていることを示す証明が提供されます。

ミント時に、スマートコントラクトは保存されたルートに対して証明を確認します。

証明が有効であれば、ウォレットは許可リストのルールに従ってミントできます。

これにより、オンチェーンのストレージコストを削減し、許可リストの検証を効率化できます。

ユーザーは、ミントページ、コントラクトアドレス、マークルルートが公式の情報源に由来することを引き続き確認してください。

ライトクライアントにおけるマークルツリー

ライトクライアントは、ダウンロードするブロックチェーンデータの量を減らすため、コンパクトな検証方法を利用します。

マークルツリーを使うと、ライトクライアントは信頼できるブロックヘッダーやルートに対して、特定のトランザクションや状態データを検証できます。

これは、モバイルウォレット、ブラウザー、ストレージや帯域幅に制約のあるデバイスで役立ちます。

ライトクライアントは、すべての検証を行うノードと同じセキュリティモデルを提供するものではありません。

ただし、マークルツリーを使った検証は、単一のデータ提供者を無条件に信頼するよりも強固な場合があります。

このため、マークルツリーは、より多くのユーザーが利用しやすい暗号資産インフラを支える重要な要素です。

ブロックチェーンゲームやメタバースアプリにおけるマークルツリー

ブロックチェーンゲームやメタバースアプリは、大規模なアセット、報酬、プレイヤー、権限のリストを検証するためにマークルツリーを利用できます。

ゲームでは、シーズン中の報酬対象を確定するためにマークルルートを使う場合があります。

メタバースアプリでは、イベントバッジの請求や仮想土地の権限を検証するためにマークルルートを使う場合があります。

NFTプロジェクトでは、特性の公開やホワイトリストへのアクセス管理にマークルツリーを使う場合があります。

これにより、アプリは大規模なデータセットをオフチェーンに保ちながら、個々の項目をオンチェーンで検証できます。

その結果、コスト削減やスケーラビリティの向上につながる可能性があります。

一方で、オフチェーンでのツリー構築プロセスが透明かつ正確である必要があります。

マークルツリーとデータの完全性

マークルツリーは、データの変更を検出しやすくすることで、データの完全性を保ちます。

リーフが1つ変わると、そのハッシュも変わります。

その変化は親ハッシュ、さらに上位の親ハッシュへと伝わり、最終的にマークルルートも変わります。

そのため、検証者はルートを比較して、データセットが同一かどうかを確認できます。

マークルツリーは、誰かが誤ったデータセットを作成することを防ぐものではありません。

特定のコミット済みルートとデータが一致するかを証明するものです。

そのため、ルートは信頼できる情報源、またはコンセンサスによって検証された情報源に由来する必要があります。

マークルツリーとハッシュリストの違い

ハッシュリストは、ハッシュを単純に並べたリストです。

マークルツリーは、コンパクトな証明を可能にする、構造化されたハッシュのツリーです。

ハッシュリストでは、1つの項目を検証するために、リスト全体からより多くのデータが必要になる場合があります。

マークルツリーでは通常、検証者が必要とするのは対象のリーフと少数の兄弟ハッシュだけです。

このため、大規模なデータセットではマークルツリーの方が効率的です。

データセットが大きくなるほど、この効率上のメリットは重要になります。

マークルツリーとマークルパトリシアトライの違い

マークルツリーは、ハッシュツリー全般を指すデータ構造です。

マークルパトリシアトライは、キー・バリュー形式のデータに使われる、より特化した構造です。

Ethereumは、状態を効率的に保存および検証するため、修正版のマークルパトリシアトライを使用します。

単純なマークルツリーは、トランザクションの包含、NFTの許可リスト、エアドロップの請求などでよく使われます。

アカウントアドレスやストレージスロットなど、キーを使ってデータを検索する必要がある場合は、トライがより適しています。

どちらの構造も、暗号学的ハッシュを使ってデータの改ざんを検出できるようにします。

マークルツリーとバークルツリーの違い

バークルツリーは、ハッシュのペアだけではなくベクトルコミットメントを使う、新しい認証済みデータ構造です。

一部の証明をより小さくできることから、バークルツリーはブロックチェーンの状態管理における将来的な改善策としてよく議論されています。

Ethereumのドキュメントによると、Ethereumは将来的に現在のマークルパトリシアトライ構造からバークルツリー構造へ移行する計画です。

だからといって、マークルツリーが時代遅れになるわけではありません。

マークルツリーはシンプルで信頼性が高く、広く理解されているため、引き続き広く使われています。

エアドロップや許可リストなど多くの用途では、マークルツリーは今も実用的で効率的です。

マークルツリーのメリット

1つ目のメリットは、効率的に検証できることです。

ユーザーはデータセット全体をダウンロードせずに、個々の項目を検証できます。

2つ目のメリットは、データの完全性です。

元のデータが変更されると、その上位にあるハッシュもすべて変わります。

3つ目のメリットは、オンチェーンのストレージコストを抑えられることです。

スマートコントラクトは、個々の記録を大量に保存する代わりに、1つのルートを保存できます。

4つ目のメリットは、スケーラビリティです。

大規模なデータセットを、コンパクトな1つのルートで表せます。

5つ目のメリットは、プライバシーを部分的に保護できることです。

ユーザーは、データセット内の他の項目をすべて明らかにせずに、包含を証明できます。

マークルツリーのリスクと制約

1つ目のリスクは、不適切なルートです。

マークル証明が証明するのは、そのルートで表されるデータセットへの包含だけです。そのため、ルートは信頼できる、または検証済みである必要があります。

2つ目のリスクは、ツリーの構築が正しくないことです。

誤ったハッシュ化方式、エンコード、ソート規則、リーフ形式を使うと、証明が失敗したり、安全でなくなったりする可能性があります。

3つ目のリスクは、リプレイや二重請求のエラーです。

請求を1回に限定する場合、請求用コントラクトはウォレットがすでに証明を使用したかどうかを記録する必要があります。

4つ目のリスクは、フィッシングです。

詐欺師がマークル証明を使っているように見せかけた偽の請求サイトを作り、ユーザーに有害なトランザクションへの署名を求める場合があります。

5つ目のリスクは、誤解です。

マークルツリーが証明するのはデータの包含であり、プロジェクトが誠実であること、価値があること、安全であることではありません。

マークルツリーシステムの評価方法

まず、マークルルートが公式またはコンセンサスによって検証された情報源に由来するかを確認します。

リーフがどのようにエンコードされているかを確認します。

どのハッシュ関数が使われているかを確認します。

ツリーでソート済みのペアを使うのか、左右の順序を固定しているのかを確認します。

証明が公式ツールまたはオープンソースコードで生成されているかを確認します。

スマートコントラクトについては、証明検証関数と請求状況の追跡ロジックを確認します。

エアドロップやNFTの許可リストでは、証明を送信したりトランザクションに署名したりする前に、公式コントラクトアドレスを確認してください。

適切に設計されたマークルツリーシステムでは、ルート、規則、検証プロセスが明確に示されているはずです。

マークルツリーに関するよくある誤解

よくある誤解の1つは、マークルツリーがすべてのデータをオンチェーンに保存するというものです。

多くの暗号資産アプリでは、オンチェーンに保存されるのはマークルルートのみで、データセット全体はオフチェーンで構築・保存されます。

もう1つの誤解は、マークルルートからデータセット全体が明らかになるというものです。

ルートは暗号学的コミットメントであり、それだけでリーフ全体が明らかになることはありません。

3つ目の誤解は、有効なマークル証明があれば、ユーザーが道徳的または法的に報酬を受け取る資格があると証明できるというものです。

証明できるのは、提出されたデータがルートで表されるデータセットに含まれていることだけです。

4つ目の誤解は、すべてのマークルツリーが同じ方法で構築されるというものです。

システムによって、ハッシュ関数、エンコード方法、ソート規則、ツリー構造が異なる場合があります。

FAQ

マークルツリーを簡単に説明すると何ですか？

マークルツリーとは、少量の証明を使って、大規模なデータセット内の個々のデータを検証できるハッシュのツリーです。

マークルルートとは何ですか？

マークルルートは、マークルツリーの最上部にある最終ハッシュで、データセット全体を表すコンパクトなフィンガープリントとして機能します。

ブロックチェーンでマークルツリーが使われるのはなぜですか？

ブロックチェーンでは、大規模なデータセットを効率よく検証し、必要なデータ量を減らし、トランザクションや状態データの変更を検出するために使われます。

Bitcoinはマークルツリーをどのように使いますか？

Bitcoinは、ブロック内のトランザクションを要約するためにマークルツリーを使い、マークルルートをブロックヘッダーに保存します。

Ethereumはマークル形式の構造をどのように使いますか？

Ethereumは、修正版のマークルパトリシアトライを使って、アカウント状態やコントラクトのストレージデータを保存・検証します。

マークルツリー証明とは何ですか？

マークルツリー証明とは、特定のリーフが既知のマークルルートを持つツリーに含まれていることを示す兄弟ハッシュの集合です。

エアドロップでマークルツリーはどのように使われますか？

エアドロップ用コントラクトは1つのマークルルートを保存し、対象となるすべてのウォレットをオンチェーンに保存する代わりに、マークル証明でユーザーの請求を検証できます。

NFTの許可リストでマークルツリーはどのように使われますか？

NFTプロジェクトは、マークルルートで承認済みウォレットを表し、ミント時に証明を使って各ウォレットを検証できます。

マークルツリーにはプライバシーがありますか？

データセット全体を公開せずに包含を証明できる場合があるため、マークルツリーはプライバシーを部分的に保護できます。

マークルツリーはゼロ知識証明と同じですか？

いいえ。マークルツリーはコミット済みデータセットへの包含を証明し、ゼロ知識証明は非公開の入力を明らかにせずに、より幅広い主張を証明できます。

まとめ

マークルツリーは、大規模なデータセットの検証を容易にする、暗号資産分野の中核的なデータ構造です。

多数のデータ項目をハッシュのツリーに変換し、最後に1つのマークルルートを生成します。

このルートで、トランザクション、残高、アドレス、請求、ストレージ値、その他のブロックチェーンデータを表せます。

マークルツリーは、効率的な検証、ストレージコストの削減、データの完全性、ライトクライアント、エアドロップ、NFTの許可リスト、ブロックチェーンのステート証明を支えるため重要です。

Bitcoinは、ブロック内のトランザクションを要約するためにマークルツリーを使用します。

Ethereumは、アカウントやストレージの状態管理に、関連するマークルパトリシアトライ構造を使用します。

暗号資産アプリケーションでは、データセット全体をオンチェーンに置かずに、個々の項目が大規模なデータセットに含まれていることを証明する必要がある場合、マークルツリーが使われます。

マークルツリーは強力な仕組みですが、正しいハッシュ化、安全なエンコード、信頼できるルート、安全な証明検証に依存します。

適切に利用すれば、暗号資産システムをより軽量かつ低コストにし、検証しやすくできます。