デジタル時代において、大規模なデータの整合性と検証を確保することは、分散システムにとって中心的な課題となっています。ハッシュ ツリーとしても知られるマークル ツリーは、単なる数学的なデータ構造ではなく、分散型ネットワークが効率的かつ安全に動作することを可能にする暗号化の「バックボーン」でもあります。 1979 年にラルフ マークルによって発明されたこの構造は、データ検証プロセスの最適化における画期的な進歩であり、ネットワークに参加しているエンティティが巨大なデータベース全体を保持することなく情報を検証できるようになります。
Tan Phat Digital の専門家チームによるこのレポートでは、ビットコインやイーサリアムなどのブロックチェーン プロトコルにおける技術的性質、高度なバリエーション、戦略的役割、および現代の Web3 で拡張されたアプリケーションについて詳細に分析します。
ハッシュ ツリーの歴史的起源と進化
マークル ツリーの概念は、ラルフ マークル博士による「従来の暗号化機能に基づくデジタル署名」というタイトルの科学論文で初めて導入されました。当時、マークル社の目標は、デジタル署名を処理し、公開鍵を安全に配布する効率的な方法を見つけることでした。ハッシュ ツリーが登場する前は、一連のデータの整合性を検証するには、すべてのデータをハッシュして順番に比較する必要がある線形手法が必要になることが多く、データの規模が増大するにつれて計算リソースと帯域幅の無駄が発生していました。
マークル ツリーは、ハッシュ関数を階層構造に編成することで状況を完全に変えました。この革新により、サイズ n のデータのリストをちょうど log2 (n) の深さのツリー構造に変換できるようになり、検証問題を線形の負担から非常に高速な対数演算に変えることができます。安全なファイル システムやピアツーピア (P2P) ネットワークでの最初のアプリケーションから 40 年以上を経て、マークル ツリーは 2008 年にビットコインの設計に不可欠な要素となり、イーサリアムのような現代のネットワークではマークル パトリシア トライやバークル ツリーなどのより複雑な構造に進化し続けました。
詳細を見る: ブロックチェーンはどのように機能しますか?
マークル ツリーの技術的メカニズムと構造
技術的には、マークル ツリーはバイナリ ツリーの一種で、各葉がノードはデータ ブロックのハッシュ関数でラベル付けされ、各非リーフ ノードはその子ノードのラベルの暗号化ハッシュでラベル付けされます。
マークル ツリーのコア コンポーネント
この構造がモバイル デバイスでどのように機能するかを理解するために、Tan Phat Digital はツリーの 3 つの主要な層を次のように要約しています。
リーフ ノード: これはツリーの最下位レベルであり、各ノードには生データの単位 (ブロックチェーン トランザクションなど) のハッシュが含まれます。データが L1、L2 の場合、対応するリーフ ノードは H1 = Hash(L1)、H2 = Hash(L2) になります。
中間ノード: これらのノードは、リーフ ノードをペアにしてハッシュすることによって作成されます。お互いに。たとえば、 ノードH12 は Hash(H1 +H2 ) の結果です。このプロセスは、最上部に到達するまでカスケードで繰り返されます。
マークル ルート: これはツリーの最上部にある単一のノードであり、データ セット全体を固定長のハッシュ文字列として表します。これは固有の「デジタル指紋」として機能します。リーフ レベルのデータが 1 ビットだけ変更されると、連鎖効果によりマークル ルートが完全に変化します。
暗号意味階層:
ピーク (レベル 0) - マークル ルート: データ セット全体へのコミットメント (単位: で測定)レイヤー下部のハッシュ(左+右)。
中間 - 内部ノード: ルートにつながる構造リンク。ハッシュ(子nuˊt のペア) によって計算されます。
下部 - リーフ ノード: から計算された個々の要素を表します。 Hash(Data tho^).
暗号ハッシュ関数の役割
ハッシュ関数は、マークル ツリーのセキュリティを推進するエンジンです。 SHA-256 などの一般的なハッシュ関数には、決定性、プリイメージ耐性、衝突耐性などの重要な特性があります。マークル ツリーでは、衝突耐性により、マークル ルートを保持しながら有効なトランザクションを偽のトランザクションに置き換えることができなくなります。
バイナリ構造での奇数データの処理
マークル ツリーでは通常、リーフ ノードの数が 2 のべき乗である必要があるため、データの数が奇数の場合、ほとんどの実装では最後の要素を 2 倍にして完全なペアを形成します。たとえば、トランザクション A、B、C がある場合、ツリーは A を B でハッシュして HAB を取得し、C を C 自体でハッシュして HCC を取得します。
ブロックチェーンの整合性と効率の重要性
マークル ツリーは、Tan Phat Digital が以下で分析する 2 つの重要な概念を通じてスケーラビリティの問題を解決します。ここ:
マークル証明: 対数検証メカニズム
マークル証明を使用すると、セット全体をロードせずに、データの一部がコミットされたセット内にあるかどうかを検証できます。ユーザーは、そのトランザクションからルートまでのパスに沿って「兄弟ハッシュ」を提供するだけです。たとえば、100 万を超えるトランザクションの場合、ユーザーはトランザクションを検証するために 20 の中間ハッシュだけが必要です。
ライト クライアント向けに最適化
ライト ノードは、非常に小さなブロック ヘッダー (ビットコインで 80 バイト) のみをダウンロードします。支払いを検証する必要がある場合、ライト ノードはフル ノードにマークル プルーフを要求します。最終的なハッシュ結果を保存されたマークル ルートと照合することで、ライト ノードはトランザクションの有効性を完全に確信できます。
線形とマークル ツリー検証の比較:
複雑さ: 線形は O(n) ですが、マークル ツリーはO(logn)。
データ トランスポート: 線形にはリスト全体が必要ですが、マークル ツリーにはパス上の姉妹ノードのみが必要です。
並列性: 線形は非常に低く、マークル ツリーは非常に高くなります。
影響変更: リニアには完全な再ハッシュが必要です。マークル ツリーは影響を受けるブランチを更新するだけです。
ビットコインとイーサリアムのマークル ツリー
ビットコイン: シンプルなバイナリ構造
ビットコインは単純なバイナリ マークル ツリーを使用します。マークル ルートはブロック ヘッダーに直接配置され、壊れない結合が形成されます。ただし、この構造は静的です。ブロックがマイニングされると、トランザクション リストは決して変更されません。
イーサリアム: マークル パトリシア トライ (MPT)
イーサリアムは MPT を使用して、トランザクションだけでなくネットワーク全体の状態 (アカウント残高、契約コード) も保存します。 MPT を使用すると、共通プレフィックス パスの効率的な更新と圧縮ストレージが可能になります。 Ethereum ブロックには 4 種類のマークル ルートが含まれます。
状態ルート: すべてのアカウントに関するグローバル情報が含まれ、ブロックごとに常に変化します。
トランザクション ルート: 現在のブロック内のローカルなトランザクションが含まれます。
領収書ルート: トランザクションの受信、実行結果、ログを保存します。
ストレージ ルート: スマート コントラクトごとに分離され、そのコントラクトの内部データを保存します。
高度なバリエーション: スパース マークル ツリーと MMR
スパース マークル ツリー(SMT)
SMT は巨大なアドレス空間 (2256 カード) 向けに設計されていますが、ほとんどのカードは空です。高速な計算が可能で、トランザクションが決して発生しなかったことを証明する「非存在証明」をサポートしています。
マークル山脈 (MMR)
MMR は、既存のノードを変更せずに新しい要素を追加できるツリー構造です。これは、追加専用データや SSD へのデータ書き込みの最適化に最適です。
Verkle Tree: ステートレス性の革命
Verkle Tree は、単純なハッシュの代わりに多項式コミットメントを使用する、従来の Merkle Tree のより効率的な代替品です。
MPT と比較した Verkle Tree の優れた機能:
構造: MPT はバイナリ ハッシュ ツリー、Verkle は多項式コミットメント ツリーです。
幅: MPT は 2 または 16 幅、Verkle は最大 256 または 1024 幅です。
プルーフ サイズ: MPT は約150 KB、Verkle はわずか 1 ～ 2 KB (50 ～ 100 分の 1) です。
ストレージ: Verkle では「ステートレス」操作が可能で、ノードが巨大な状態データ全体を保存する必要がなくなります。
計算: MPT は計算が簡単ですが、Verkle では複雑な楕円曲線計算が必要です。
暗号化セキュリティと脆弱性
マークル ツリーは強力ですが、ビットコインで発見されたトランザクション重複攻撃 (CVE-2012-2459) や 2 番目のプリイメージ攻撃などの弱点がまだあります。予防策として、Tan Phat Digital は、OpenZeppelin が提案しているダブル リーフ ハッシュ法またはドメイン分離を使用することを開発者に推奨しています。
拡張 Web3 アプリケーション
プルーフ オブ リザーブ (PoR): Binance のような取引所は、マークル ツリーと zk-SNARK を組み合わせて、顧客資産の十分なリソースを保持していることを証明します。プライバシーを保護しながら。
Airdrops 配布: プロジェクトは Merkle Origin を発表するだけで済み、ユーザー自身が証拠を添えて請求リクエストを提出することで、ガス料金を 99% 節約できます。
ファイル システム (IPFS/BitTorrent): Merkle Tree を使用してコンテンツを識別し、さまざまなソースからダウンロードされたデータが破損していないことを確認します。
Celestia: 名前空間マークル ツリー (NMT) を使用して各アプリケーションに従ってデータを配置し、ロールアップが関連するデータをダウンロードするだけで済むようにします。
マークル ツリー アプリケーションの典型的な 10 のケース スタディ
実際の適用性を実証するために、Tan Phat Digital最もよく描かれている 10 の典型的なケースを合成します。
ビットコイン (簡易決済検証): 軽量モバイル ウォレット (Electrum など) で、500 GB 以上のチェーン データ (80 バイトのブロック ヘッダーと約 12 ～ 20 の証明ハッシュのみ) をダウンロードせずにトランザクションを検証できるようにします。
イーサリアム(州管理):マークル パトリシア トライを使用して、何百万もの資産アカウントと残高を保存します。残高が変化すると、システムはデータベース全体を再構築することなく、対応するブランチを更新するだけです。
Binance (準備金証明): FTX イベント後、Binance は zk-SNARK を組み合わせたマークル ツリーを導入して 1:1 の資産準備率を証明し、ユーザーが身元を明らかにすることなく自分のお金を確認できるようにしました。
Celestia (モジュラー ブロックチェーン): 名前空間化されたマークル ツリーを使用するプロジェクトごとにデータを分類する（ロールアップ）。これにより、アプリケーションは「独自の」データのみをダウンロードするだけで済み、システム リソースの負荷が軽減されます。
Git (バージョン管理システム): Git のすべての「コミット」は、実際にはマークル ツリー (ツリー オブジェクト) です。 Git が何百万行ものコードを比較し、変更や重複ファイルを瞬時に検出するのに役立ちます。
BitTorrent (ピアツーピア ファイル共有): 映画をダウンロードする際、マークル ツリーはさまざまなソースからダウンロードされた各データ (チャンク) をチェックするのに役立ちます。フラグメントが破損している場合、システムはファイル全体ではなく、そのフラグメントのみをリロードします。
IPFS (分散ファイル システム): Merkle DAG を使用してコンテンツを識別します。同じ内容を持つ 2 つのファイルには同じアドレス (CID) が割り当てられるため、システムはネットワーク上の重複データを自動的に排除できます。
Apache Cassandra (データベース レプリケーション): マークル ツリーを使用して、レプリカ サーバー (レプリカ) 間の不整合を検出します。比較のためにデータ全体を送信する代わりに、サーバーはマークル ルートのみを交換して偏ったデータ領域を見つけます。
Starknet (ZK-Rollup Airdrops): Merkle Tree と Cairo 言語を使用して、数百万のユーザーにトークンを配布します。プロジェクトは、報酬イベント全体を実行するために、単一の 32 バイトのルート ハッシュをオンチェーンに保存するだけで済みます。
証明書の透明性:マークル ツリーを使用して、認証局 (CA) が検出されずに偽の証明書を Web サイトに発行するのを防ぐ、SSL/TLS 証明書のパブリック ストレージ システム。
よくある質問 (FAQ)
ここでは、Tan Phat がまとめたマークル ツリーに関する最も人気のある 10 の質問を示します。デジタル:
ブロックチェーンは単純なハッシュ リストの代わりにマークル ツリーを使用するのはなぜですか?
マークル ツリーを使用すると、O(n) ではなく O(log n) の複雑さで特定のトランザクションを検証できます。これは、100 万トランザクションの場合、100 万ステップではなく約 20 検証ステップだけで済み、帯域幅とリソースが大幅に節約されることを意味します。
ブロック内のトランザクション数が奇数の場合はどうなりますか?
バランスの取れたバイナリ ツリー構造を維持するために、リスト内の最後のトランザクションが複製され、それ自体でハッシュされて完全なペアが形成されます。
違い 実際の違いは何ですか。マークル ルートとマークル プルーフの間の違いは何ですか?
マークル ルートは、ツリーの最上部に位置する一意のハッシュであり、データ セット全体を表します。マークル証明は、ユーザーが特定のデータからマークル ルートを手動で再計算するために必要な中間ハッシュ (パス) のセットです。
攻撃者はマークル ルートを変更せずにデータを変更できますか?
暗号化ハッシュ関数の衝突耐性の性質により、理論的にはできません。リーフ ノードの小さな変更は、ルートのハッシュ コードを完全に変更する連鎖効果を作成します。
イーサリアムはなぜ Verkle Tree に移行するのですか?
Ethereum の Merkle Tree の最大の問題は、プルーフ サイズ (ウィットネス) が大きすぎることです (約 150 KB)。 Verkle Tree を使用すると、このサイズが 1 ～ 2 KB に削減され、ネットワーク ノードが「ステートレス」モードでより効果的に動作できるようになります。
アカウントがシステムに存在しないことを証明するにはどうすればよいですか?
これは、Sparse Merkle Tree (SMT) を通じて行われます。 SMT には固定アドレス空間があるため、値 0 のリーフ ノードにつながるマークル プルーフを提供して、そのデータが存在しないことを証明できます。
マークル ツリーはプライバシーの保護に役立ちますか?
はい。 Merkle Proof を使用すると、ブロック内の他のトランザクションを明らかにすることなく、ブロック内にトランザクションが存在することを証明できます。 ZK-SNARK と組み合わせると、取引所の Proof of Reserve のような非常に高度なセキュリティ システムが作成されます。
なぜビットコインはイーサリアムのマークル パトリシア トライのような複雑な構造を使用しないのですか?
ビットコインは静的台帳 (UTXO モデル) であるためです。ブロックがマイニングされると、トランザクションは決して変更されません。イーサリアムは動的ステート マシンであり、アカウント残高と契約コードがトランザクションごとに継続的に変化するため、MPT が必要です。
マークル ツリーの「2 番目のプレイメージ」攻撃とは何ですか?
これは、攻撃者が内部ノードをリーフ ノードの位置に挿入することによってシステムを騙す脆弱性です。これを防ぐために、OpenZeppelin のようなライブラリでは、葉を二重ハッシュするか ($H(H(\text{data}))$) するか、プレフィックスを追加してレイヤーを区別することがよくあります。
ブロックチェーン以外にマークル ツリーはどこで使用されますか?
マークル ツリーは、ソース コードのバージョン管理のために Git、ハード ドライブ データの破損を防ぐために ZFS/Btrfs、および BitTorrent や IPFS などの P2P ネットワークで広く使用されています。多くのソースからダウンロードされたファイル フラグメントの整合性を検証します。
Tan Phat Digital によると、マークル ツリーは数学における単純さの力の証です。データを改ざんから保護するだけでなく、脆弱なデバイスのネットワーク アクセスを拡張するツールでもあります。 Verkle Tree への進化は、ブロックチェーン技術が地球規模の問題を解決するために継続的に努力していることを示しています。マークル ルートは、ユーザーが人間ではなく数学の法則を信頼する分散型世界における「信頼の支点」であり続けます。
シェア
