主なポイント

• マークルツリーは、データをハッシュのペアに整理し、それらを上方向に結合して、最終的に単一のハッシュ（マークルルート）がデータセット全体を表す暗号学的データ構造です。

• マークルルートは、トランザクション数に対して対数的にスケーリングするコンパクトなマークル証明を使用することで、ブロックチェーンネットワークがブロック全体をダウンロードすることなく、トランザクションがブロックに含まれているかどうかを検証することを可能にします。

• ビットコインは、すべてのブロックヘッダーにマークルルートを埋め込んでいるため、軽量クライアントはブロックチェーン全体ではなく、ブロックヘッダーのみを使用してトランザクションを検証できます。

• イーサリアムは、アカウント残高とスマートコントラクトの状態を保存するために、より複雑なマークル・パトリシア・トライを使用しており、ライトクライアントやレイヤー2ロールアップでの状態証明を可能にしている。

導入

マークルツリーは、ブロックチェーンシステムを大規模かつ効率的で検証可能なものにするための基礎となる概念の一つです。マークルツリーを用いることで、ネットワークはデータセット全体を単一の暗号化フィンガープリントに集約できると同時に、特定のトランザクションや情報が含まれていることを証明できます。ブロックチェーン設計においてマークルツリーが重要な理由を理解するために、その仕組み、様々なネットワークにおける利用方法、そして将来的にVerkleツリーのような新しい構造がどのようにマークルツリーを改良していく可能性があるのか​​を見ていきましょう。

マークルツリーの仕組み

マークルツリーは、1979年にこの概念の特許を取得したコンピュータ科学者ラルフ・マークルにちなんで名付けられたデータ構造で、大規模なデータセットを効率的に要約し、その整合性を検証するために使用されます。ブロックチェーンでは、マークルツリーは何千ものトランザクションを圧縮し、ブロックヘッダーに格納される単一のコンパクトな値にします。

このツリーは、暗号学的ハッシュ関数を用いて下から上に構築されます。各リーフノードには、トランザクションなどの単一データのハッシュが格納されます。これらのリーフハッシュはペアにされ、各ペアのハッシュは、2つの子ハッシュを連結し、その結果をハッシュ化することによって計算されます。このプロセスは、最上位のマークルルートに単一のハッシュが残るまで、階層ごとに上方向に繰り返されます。

各親ノードは両方の子ノードに依存しているため、単一の葉ノードに変更を加えると、その変更は上位ノードに波及し、全く異なるマークルルートが生成されます。この特性により、マークルツリーは改ざん検出に効果的なツールとなります。つまり、データセットの2つのコピーが同じマークルルートを生成する場合、それらのデータセットは極めて高い確率で同一であると言えます。

マークルルーツ

マークルルートは、ブロックチェーンアプリケーションでは通常32バイト（256ビット）の固定サイズのハッシュであり、データセット全体のデジタル指紋として機能します。ほとんどのブロックチェーンネットワークのブロックヘッダーには、タイムスタンプや前のブロックのハッシュなどのメタデータとともにマークルルートが含まれており、ヘッダーのサイズを小さく保ちながら、ブロック内のすべてのトランザクションを暗号的にコミットします。

分かりやすく説明するために、8GBのファイルを8つの断片に分割した例を見てみましょう。それぞれの断片をAからHとします。各断片はハッシュ関数にかけられ、8つの異なるハッシュ値が得られます。

すべてのフラグメントのハッシュ値があれば、どれか一つに欠陥があれば、元のフラグメントのハッシュ値と比較することでわかる、そうですよね？確かにそうかもしれませんが、これは非常に非効率的な方法でもあります。ファイルに何千ものフラグメントがある場合、それらすべてをハッシュ化して、結果を綿密に比較するのでしょうか？

マークルルートはより洗練された解決策を提供する。各ハッシュのペアを取り出し、それらを結合し、さらにそれらをハッシュ化する。すると、hA + hB、hC + hD、hE + hF、hG + hHというハッシュが得られ、最終的に4つのハッシュが生成される。

次に、もう一度ハッシュ化すると、hABCDとhEFGHの2つが得られます。最後に、残りの2つをハッシュ化してマスターハッシュを取得すると、マークルルート（またはルートハッシュ）であるhABCDEFGHが得られます。

マークル証明と検証

マークルツリーの最も実用的な機能の1つは、データセット全体を公開することなく、特定のデータがデータセットに属していることを証明できることです。これはマークル証明と呼ばれます。トランザクションがブロックに含まれていることを検証するために、ライトクライアントはトランザクション自体、ルートまでのパス上の少数の兄弟ハッシュ、およびブロックヘッダーからのマークルルートのみを必要とします。検証者はパス上のハッシュを再計算し、結果が既知のルートと一致するかどうかを確認します。一致する場合、そのトランザクションはブロックの一部であることが数学的に証明されます。

トランザクションIDがhDであるトランザクションを検証するシナリオを考えてみましょう。hCが提供されていれば、hCDを計算できます。次に、hABを使用してhABCDを計算します。最後に、hEFGHを使用して、結果として得られるマークルルートがブロックヘッダーのマークルルートと一致するかどうかを確認します。一致すれば、トランザクションがブロックに含まれていたことの証明となります。異なるデータで同じハッシュを作成することはほぼ不可能です。

上記の例では、ハッシュ化は3回だけで済みます。マークル証明を使用しない場合は、7回行う必要があります。現在ではブロックには数千件のトランザクションが含まれているため、マークル証明を使用することで、時間と計算リソースを大幅に節約できます。

証明のサイズは葉の数に対して対数的に増加します。100万件のトランザクション（深さ20の二分木）の場合、必要なハッシュは約20個、つまり約640バイトで済みます。これにより、軽量ノード（簡易決済検証（SPV）クライアントと呼ばれることもあります）は、ブロックチェーン全体をダウンロードすることなくトランザクションを検証できます。そうでなければ、数百ギガバイトものデータが必要になります。

ブロックチェーンネットワークにおけるマークルツリー

ビットコインと取引の検証

ビットコインでは、各ブロックヘッダーに、そのブロック内のすべてのトランザクションをコミットする32バイトのマークルルートが含まれています。ビットコインマイナーは、自身が含めたトランザクションからマークルツリーを構築し、その結果得られたルートをプルーフ・オブ・ワーク（PoW）ソリューションとともにブロックヘッダーに埋め込みます。この設計により、通常約80バイトのブロックヘッダーだけで、他のトランザクションを必要とせずに、特定のトランザクションがブロックに含まれていることを検証できます。

ビットコインもまた、MAST（Merkelized Abstract Syntax Trees：マークル化抽象構文木）という提案の中でマークル木を利用しており、ビットコインスクリプト内の複雑な支出条件をマークル木として表現できる。実行されたスクリプトの分岐のみを公開すればよく、未使用の条件は非公開のままにし、トランザクションサイズを削減できる。

イーサリアムとステートプルーフ

イーサリアムは、アカウント残高、コントラクトコード、ストレージデータを格納する六角形（16分岐）ツリー構造であるマークルパトリシアトライと呼ばれる、より高度なバリアントを使用しています。ビットコインのトランザクションで使用される単純なバイナリマークルツリーとは異なり、マークルパトリシアトライは状態の頻繁な更新をサポートするように設計されています。アカウント残高が変更された場合、ツリー全体を再構築するのではなく、そのリーフからルートまでのパスのみを再計算する必要があります。

Merkle Patricia Trieから生成されるステート証明により、イーサリアムのライトクライアントやレイヤー2ロールアップは、フルノードを実行することなく、アカウント残高やコントラクトのストレージを検証できます。これらの証明は、あるチェーン上のイベントを別のチェーンから検証する必要があるクロスチェーンブリッジにとっても不可欠です。

限界と今後の展開

マークルツリーは効率的な検証手段を提供するものの、証明のサイズはデータセットの規模に応じて対数的に増加します。イーサリアムの場合、ステートが大きくなるにつれて、ブロックの検証に必要な証明であるブロックウィットネスは数メガバイトに達する可能性があります。これは、すべてのブロックに対してこれらの証明を受信して​​検証する必要があるステートレスクライアントにとって、スケーラビリティ上の課題となります。

従来のハッシュではなく、多項式（Kate-Zaverucha-Goldberg、略称KZG）コミットメントに基づくベクトルコミットメントを使用するVerkleツリーは、有望な解決策となる可能性があります。Verkleツリーは、各ノードの下に多数の子ノードをグループ化することで（分岐係数256）、データセットのサイズに関わらず、約170バイトというほぼ一定のサイズの証明を生成します。イーサリアムはVerkleツリーの統合を積極的に開発しており、将来のアップグレードで実装される予定です。この移行により、軽量クライアントのデータ負荷が大幅に軽減され、ネットワーク全体の拡張性が向上します。

よくある質問

簡単に言うと、マークルツリーとは何ですか？

マークルツリーとは、単一の小さな情報（マークルルート）で大量のデータを表現できるようにデータを整理する方法です。これは、データのペアを繰り返しハッシュ化し、最終的に1つのハッシュ値だけを残すことで機能します。これにより、個々の項目をすべて確認することなく、特定の項目がデータセットに属しているかどうかを検証することが可能になります。

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

マークルルートとは、マークルツリーの最上位にある単一のハッシュ値です。これは、その下にあるすべてのデータのコンパクトなデジタル指紋として機能します。ブロックチェーンネットワークでは、マークルルートはブロックヘッダーに格納され、そのブロック内のすべてのトランザクションにコミットされるため、トランザクションがブロックの一部であることを効率的に検証できます。

マークル証明はどのように機能するのですか？

マークル証明では、トランザクションと、そのトランザクションからマークルルートまでのパスを再計算するために必要な最小限の兄弟ハッシュのセットが提供されます。検証者はトランザクションをハッシュ化し、提供された兄弟ハッシュと正しい順序で結合し、最終結果がブロックヘッダー内の既知のマークルルートと一致するかどうかを確認します。一致すれば、トランザクションが含まれていることが証明されます。

ブロックチェーンにおいてマークルツリーが重要な理由は何ですか？

マークルツリーは、ブロックチェーンネットワークにおいて、ブロックヘッダーとトランザクションデータ全体を分離することを可能にします。軽量クライアントは、ブロックヘッダー（1ブロックあたり約80バイト）のみをダウンロードし、コンパクトなマークル証明を用いてトランザクションが含まれていることを検証できます。マークルツリーがない場合、トランザクションを検証するには、ブロック全体またはチェーン全体をダウンロードする必要があります。

MerkleツリーとVerkleツリーの違いは何ですか？

どちらもデータのメンバーシップを証明するために使用される暗号学的アキュムレータですが、使用する数学が異なります。マークルツリーはハッシュ関数を使用し、データセットのサイズに応じて対数的に増加する証明（O(log n)）を生成します。一方、バークルツリーは多項式（KZG）コミットメントを使用し、データセットのサイズに関係なく数百バイトというほぼ一定のサイズの証明を生成するため、大規模なブロックチェーンの状態証明に適しています。

最後に

マークルツリーはブロックチェーンアーキテクチャの基盤であり、大規模なトラストレス検証を可能にします。トランザクションブロック全体を単一の32バイトハッシュに圧縮することで、参加者はすべてをダウンロードすることなくデータを検証できます。この原理は、ビットコインのSPVウォレットからイーサリアムのステートプルーフ、クロスチェーンブリッジに至るまで、あらゆるものの根底にあります。ブロックチェーンネットワークが成長を続けるにつれ、ヴァークルツリーなどの新しい暗号構造がマークルツリーを補完または置き換える可能性がありますが、効率的なハッシュベースのデータ整合性という根底にある概念は、今後何年にもわたって分散システムの基本的な構成要素であり続けるでしょう。

さらに読む

• ブロックチェーンのコンセンサスアルゴリズムとは何ですか？

• 暗号学の歴史

• ブロックチェーンのレイヤー1とレイヤー2のスケーリングソリューション

• シャーディングとは何か、そしてどのように機能するのか？

免責事項：このコンテンツは、いかなる表明または保証もなく、一般的な情報および教育目的のみで「現状のまま」提供されます。これは、財務、法律、またはその他の専門的なアドバイスとして解釈されるべきではなく、特定の製品またはサービスの購入を推奨する意図もありません。適切な専門家のアドバイスを各自で求めてください。コンテンツが第三者の寄稿者によって提供されている場合、表明された見解は第三者の寄稿者のものであり、必ずしもBinance Academyの見解を反映するものではないことにご注意ください。デジタル資産の価格は変動する可能性があります。投資の価値は上下する可能性があり、投資額を取り戻せない場合があります。投資判断はすべてお客様の責任であり、Binance Academyはお客様が被る可能性のある損失について一切責任を負いません。詳細については、利用規約、リスク警告、およびBinance Academyの利用規約をご覧ください。