マークルツリー証明

マークルツリー証明とは？

マークルツリー証明とは、データセット全体を公開したりダウンロードしたりせずに、特定のデータがより大きなデータセットに含まれていることを示す暗号学的証明です。

暗号資産分野では、トランザクション、アカウント、残高、ストレージ値、NFTの請求情報、ウォレットアドレスなどが検証済みデータセットに含まれていることを証明するために、よく利用されます。

マークルツリー（ハッシュツリーとも呼ばれます）のハッシュを使って機能します。

マークルツリーでは、多数のデータをリーフとしてハッシュ化し、それらのハッシュをペアにして組み合わせ、最終的に1つのハッシュだけが残るまで上位へとハッシュ化を繰り返します。

この最終ハッシュをマークルルートと呼びます。

マークルルートが信頼できる場合、ユーザーはデータセット全体を確認する代わりに、小さな証明だけで個々のデータを検証できます。

Bitcoinの開発者ガイドでは、ブロックヘッダーのマークルルートとピアから取得した中間ハッシュを使うことで、クライアントがトランザクションのブロックへの包含を検証できると説明されています。

このため、マークルツリー証明はブロックチェーンの効率化、ライトクライアント、トークンエアドロップ、NFTの許可リスト、ブリッジ、ステート証明、データ検証において重要です。

マークルツリーの仕組み

マークルツリーは、ツリーの最下部にある個々のデータ項目から始まります。

最下部の項目はリーフと呼ばれます。

ブロックチェーンでは、各リーフがトランザクションハッシュ、アカウント情報、ストレージ値、ウォレットアドレス、請求記録などを表す場合があります。

各リーフは暗号学的ハッシュ関数でハッシュ化されます。

次に、そのハッシュをペアにして、もう一度ハッシュ化します。

このプロセスを階層ごとに繰り返し、ツリーの最上部に1つのハッシュを生成します。

最上部のハッシュがマークルルートです。

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

その変化はツリーの上位へ伝わり、マークルルートも変化します。

このため、マークルルートは大規模なデータセットを表すコンパクトなフィンガープリントとして機能します。

マークルツリー証明の仕組み

マークルツリー証明は、特定のリーフが既知のルートを持つマークルツリーに含まれていることを証明します。

通常、証明には、リーフからルートまでの経路を再構築するために必要な兄弟ハッシュが含まれています。

検証者はリーフのハッシュから始めます。

次に、最初の兄弟ハッシュと組み合わせ、そのペアをハッシュ化します。

その結果を次の兄弟ハッシュと組み合わせ、再びハッシュ化します。

検証者が最終的なルートを計算するまで、このプロセスを続けます。

計算されたルートが信頼できるマークルルートと一致すれば、証明は有効です。

計算されたルートが一致しなければ、証明は無効です。

この方法なら、ツリー内のすべてのリーフを公開せずに検証できます。

マークルツリー証明の簡単な例

ウォレットアドレスが4つ登録されたNFTの許可リストを考えてみましょう。

各アドレスをハッシュ化してリーフを作成します。

リーフAとリーフBをハッシュ化して、親ハッシュを作成します。

リーフCとリーフDもハッシュ化し、別の親ハッシュを作成します。

この2つの親ハッシュをさらにハッシュ化し、マークルルートを作成します。

ウォレットAが許可リストへの登録を証明する場合、リスト全体を公開する必要はありません。

自身のリーフと、マークルルートを再構築するために必要な兄弟ハッシュだけで足ります。

スマートコントラクトは証明を検証し、保存されているルートと一致すれば、ウォレットによる請求やミントを許可できます。

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

ブロックチェーンでは大量のデータを効率的に検証する必要があるため、マークルツリー証明は重要です。

マークル証明がなければ、ユーザーやアプリケーションは、より多くの情報をダウンロードするか、その情報を信頼する必要が生じる場合があります。

マークル証明を使うと、検証に必要なデータをより小さく、より速く、より実用的なものにできます。

ストレージ、帯域幅、ガス代、デバイスのリソースに制約がある場合に特に役立ちます。

ライトウォレットは、フルノードを実行せずにデータを検証するため、証明を利用できます。

スマートコントラクトは、何千ものアドレスをオンチェーンに保存せずに、証明を使って許可リストを確認できます。

ブリッジやクロスチェーンシステムは、他のチェーン上のイベントや状態を検証するために証明を利用できます。

データ可用性やロールアップのシステムも、データがより大きなコミット済み構造に含まれていることを証明するため、マークル形式のコミットメントを利用できます。

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

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

マークルルートはブロックヘッダーに含まれています。

ライトクライアントは、ブロックのマークルルートに対してマークル証明を検証することで、トランザクションがブロックに含まれていることを確認できます。

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

SPVを使うと、ウォレットやクライアントは各ブロック全体をダウンロードせずに、トランザクションの包含を検証できます。

ただし、クライアントがフルノードと同じすべての項目を検証するという意味ではありません。

ブロックヘッダーと証明データを利用することで、より効率的に包含を確認できるということです。

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

Ethereumは、アカウントやストレージの検証に、マークル形式の認証済みデータ構造を使用します。

Ethereumのマークルパトリシアトライに関するドキュメントでは、Ethereumがハッシュで連結されたツリー構造を使用し、保存データの完全性を保証していると説明されています。

Ethereumの証明では、アカウントやストレージ値が特定のステートルートに含まれていることを示せます。

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

この種の証明は、アプリケーションがデータ提供者を無条件に信頼せずにアカウントの状態を検証したい場合に役立ちます。

Ethereumの証明システムは、Ethereumの状態がトライ形式の構造に保存されているため、単純な二分マークルツリーより複雑です。

ただし、基本的な考え方は同じです。小さな証明を使い、信頼できるルートに対して1つのデータを検証します。

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

NFTプロジェクトでは、許可リストやプレセールにマークルツリー証明がよく使われます。

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

承認された各ユーザーには、自身のウォレットアドレスが許可リストのツリーに含まれていることを示す証明が提供されます。

ユーザーが請求またはミントを行う際、スマートコントラクトは保存されたルートに対して証明を検証します。

ルートを1つ保存する方が、何千ものアドレスを保存するよりはるかに低コストなため、オンチェーンのストレージコストを削減できます。

許可リスト全体をコントラクトに直接記録する必要がないため、プライバシーの向上にもつながります。

ただし、ユーザーは公式プロジェクトがルートを作成したことと、請求ページがフィッシングサイトではないことを引き続き確認する必要があります。

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

エアドロップでは、トークンを請求できるユーザーを確認するためにマークルツリー証明がよく使われます。

プロジェクトは対象となるウォレットアドレスと請求額のデータセットを作成します。

各請求記録がマークルツリーのリーフになります。

スマートコントラクトにはマークルルートが保存されます。

ユーザーが請求する際は、自身のアドレス、請求額、証明を送信します。

コントラクトは、証明が保存されたルートと一致するかを確認します。

証明が有効で、ウォレットがまだ請求していない場合、コントラクトはトークンを払い出すことができます。

この設計により、プロジェクトは請求記録をすべてオンチェーンに保存せずに、大規模なエアドロップを実施できます。

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

ライトクライアントとは、ブロックチェーンの全データをダウンロードして処理せずに、ブロックチェーンデータを検証するウォレットまたはノードです。

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

Ethereumのライトクライアントに関するドキュメントでは、ライトクライアントを使うと、フルノードに必要なリソースのごく一部で受信データを検証できると説明されています。

これは、モバイル端末、ブラウザー、組み込みシステム、帯域幅が限られているユーザーにとって重要です。

ライトクライアントはフルノードと同じものではありません。

検証するデータは少なくなりますが、中央集権型のデータ提供者に全面的に依存する場合と比べ、信頼性を高めることができます。

スマートコントラクトにおけるマークルツリー証明

スマートコントラクトは、マークルツリー証明をオンチェーンで直接検証できます。

コントラクトが大規模なデータセットへの所属を確認する必要がある場合に便利です。

OpenZeppelinのMerkleProofドキュメントでは、スマートコントラクトでマークル証明を検証するためのツールが提供されています。

一般的なコントラクトのパターンでは、マークルルートを保存し、請求、ミント、報酬の受け取り、アクセス確認の際にユーザーが送信した証明を検証します。

これにより、対象となるアドレスや記録をすべてコントラクトに保存する必要がなくなります。

主なトレードオフは、オフチェーンで証明を正しく生成しなければならないことです。

ツリーの構築方法、ハッシュ化方式、ソート規則、リーフのエンコード方法に誤りがあると、有効なユーザーが検証に失敗したり、設計が不適切なシステムでは無効なユーザーが通過したりする可能性があります。

マークルツリー証明とマークルルートの違い

マークルルートは、ツリー全体を表す最終ハッシュです。

マークルツリー証明は、1つのリーフがツリーに含まれていることを証明するために使うハッシュと関連データの集合です。

ルートは、データセット全体のフィンガープリントのようなものです。

証明は、個々のデータをそのフィンガープリントに結び付ける証拠です。

ルートだけでは、ツリー内のすべてのデータは明らかになりません。

検証者が比較対象となる信頼できるルートを持っていなければ、証明だけでは役に立ちません。

検証には両方が必要です。

マークルツリー証明とゼロ知識証明の違い

マークルツリー証明とゼロ知識証明は、異なる暗号学的ツールです。

マークルツリー証明は、特定のデータがコミットされたデータセットに含まれていることを証明します。

ゼロ知識証明は、元となる非公開情報を明らかにせずに、ある主張が真であることを証明できます。

多くの場合、マークル証明はゼロ知識証明よりもシンプルで、低コストで検証できます。

ゼロ知識証明は、より複雑なプライバシー保護や計算の用途に対応できます。

システムによっては、マークル証明とゼロ知識証明を組み合わせて使います。

たとえば、ゼロ知識回路でマークル包含証明を非公開のまま検証できます。

マークルツリー証明とストレージ証明の違い

ストレージ証明は、ブロックチェーンの状態に保存された値を検証する、マークル形式の証明の一種であることがよくあります。

たとえばEthereumのストレージ証明は、特定のブロックのステートルートにおいて、スマートコントラクトのストレージスロットに特定の値があったことを示す場合があります。

マークルツリー証明は、より広い概念です。

ストレージ証明は、状態データやストレージデータを証明するための具体的な用途です。

この違いが重要なのは、ブロックチェーンごとにデータ構造、証明形式、ハッシュ化規則が異なるためです。

あるブロックチェーンの証明が、別のブロックチェーンでも同じように機能すると考えてはいけません。

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

1つ目のメリットは効率性です。

データセット全体を必要とせずに、証明によって個々のデータを検証できます。

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

スマートコントラクトは、何千、何百万もの記録の代わりに1つのルートを保存できます。

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

大規模なデータセットを小さなルートでコミットし、コンパクトな証明で検証できます。

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

リーフや証明のハッシュが変更されると、計算されたルートは一致しません。

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

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

リスクと制約

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

プロジェクトがツリーを誤って構築すると、証明が失敗したり、予期しない結果が生じたりする可能性があります。

2つ目のリスクは、リーフのエンコードが適切でないことです。

リーフが慎重にエンコードされていないと、異なる入力によって分かりにくく、安全でない証明動作が生じる可能性があります。

3つ目のリスクは、ソートに関する誤った前提です。

マークル証明システムによっては、ペアのソートが必要な一方、左右の順序に依存するものもあります。

4つ目のリスクは、信頼できないルートです。

有効な証明が示すのは、そのルートで表されるデータセットへの包含だけです。そのため、ルート自体が信頼できる、または検証済みの情報源に由来している必要があります。

5つ目のリスクは、リプレイや二重請求の問題です。

請求を1回に限定する場合、エアドロップや請求用コントラクトは、証明がすでに使用されているかを記録する必要があります。

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

詐欺師が偽の請求ページを作成し、証明の送信や危険なトランザクションへの署名をユーザーに求める場合があります。

マークルツリー証明を検証する方法

まず、検証対象となるリーフデータを用意します。

元のツリーの構築に使われたものと同じ方法で、リーフをハッシュ化します。

リーフのハッシュと証明に含まれる最初の兄弟ハッシュを組み合わせます。

組み合わせた値をハッシュ化します。

残りの兄弟ハッシュについても、このプロセスを繰り返します。

最終的に計算されたハッシュを、信頼できるマークルルートと比較します。

2つのルートが一致すれば、証明は有効です。

一致しなければ、証明は無効です。

スマートコントラクトでは、通常、検証コードが同じ処理を行います。

ユーザーにとって最も重要なのは、ルート、コントラクト、請求ページ、情報源が公式のものであることを確認することです。

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

よくある誤解の1つは、マークルツリー証明によって、あらゆる意味でデータが真実だと証明できるというものです。

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

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

通常、明らかになるのは対象のリーフと、検証に必要な兄弟ハッシュだけです。

3つ目の誤解は、すべてのマークル証明が同じ形式を使うというものです。

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

4つ目の誤解は、マークル証明によってあらゆる信頼が不要になるというものです。

データの受け渡しに対する信頼は軽減できますが、ユーザーには引き続き信頼できるルートと正しい検証規則が必要です。

5つ目の誤解は、マークル証明がトランザクションにしか使われないというものです。

許可リスト、エアドロップ、アカウント状態、ストレージ値、ロールアップデータ、クロスチェーンメッセージ、デジタルIDの請求などの検証にも利用できます。

FAQ

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

マークルツリー証明とは、マークルルートで表される大規模なデータセットに、1つのデータが含まれていることを示す暗号学的証明です。

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

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

マークル証明はどのようにデータを検証しますか？

検証者は対象のリーフと証明に含まれる兄弟ハッシュをハッシュ化し、最終結果が信頼できるマークルルートと一致するかを確認します。

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

すべてのユーザーやアプリケーションがデータセット全体をダウンロードしなくても、効率よくデータを検証できるためです。

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

エアドロップ用コントラクトは1つのマークルルートを保存し、対象データセットにウォレットと請求額が含まれていることを示す証明をユーザーが提出できるようにします。

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

NFTプロジェクトは、許可されたアドレスをすべてオンチェーンに保存せずに、マークル証明を使ってウォレットが許可リストに含まれていることを検証できます。

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

データセット全体を公開する必要がないため、プライバシーを部分的に保護できます。ただし、対象のリーフや証明データは引き続き公開される場合があります。

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

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

マークル証明を偽造できますか？

検証者が正しいハッシュ化規則を使い、正しい信頼済みルートと比較すれば、偽の証明は無効となります。

マークル証明を使う請求ページで、ユーザーは何を確認すべきですか？

公式コントラクト、公式サイト、信頼できるマークルルート、ウォレットの確認画面、請求ルール、ページの安全性を確認してください。

まとめ

マークルツリー証明は、暗号資産分野で特に重要な検証ツールの1つです。

ユーザー、ウォレット、スマートコントラクト、アプリケーションは、データセット全体をダウンロードまたは保存することなく、個々のデータがより大きなデータセットに含まれていることを証明できます。

これにより、ブロックチェーンシステムの効率性、スケーラビリティ、実用性が高まります。

マークルツリー証明は、トランザクションの包含、ライトクライアント、エアドロップ、NFTの許可リスト、アカウント状態の検証、ストレージ証明、ブリッジ、ロールアップシステムなどで使われます。

基本的な考え方はシンプルです。信頼できるマークルルートがデータセットを表し、証明によって1つのリーフからルートまでの経路を再構築します。

計算されたルートが一致すれば、そのデータはデータセットに含まれています。

一致しなければ、証明は無効です。

マークルツリー証明はデータ提供者への依存を減らしますが、あらゆるリスクをなくすわけではありません。

ユーザーや開発者には、正しいハッシュ化規則、安全なスマートコントラクト、信頼できるルート、慎重な証明生成、フィッシング対策が引き続き必要です。

適切に設計されたマークルツリー証明は、暗号資産システムをより軽量かつ低コストにし、検証しやすくします。