マークルツリーとは何ですか?
マークル木の概念は、公開鍵暗号の研究で有名なコンピューター科学者ラルフ・マークルによって 1980 年代初頭に提案されました。
マークルツリーは、セット内のデータの整合性を効率的に検証するために使用される構造です。参加者が情報を共有し、独立して検証する必要があるピアツーピアネットワークのコンテキストでは特に興味深いものです。
ハッシュ関数は Merkle ツリー構造の中核となるため、先に進む前に「ハッシュとは何か」を確認することをお勧めします。
マークルツリーはどのように機能しますか?
大きなファイルをダウンロードしたいとします。オープンソース ソフトウェアでは、通常、ダウンロードしたファイルのハッシュが開発者が公開しているハッシュと一致するかどうかを確認します。一致すれば、コンピューターにあるファイルは開発者のファイルとまったく同じであることがわかります。
ハッシュが一致しない場合は、問題が発生しています。ソフトウェアを装った悪意のあるファイルをダウンロードしたか、正しくダウンロードされなかったため動作しません。後者の場合、ファイルのダウンロードにしばらく待たなければならなかったら、おそらくあまりうれしくないでしょう。ここで、プロセスを再開して、再び破損しないことを祈る必要があります。
もっと簡単な方法があればいいのに、と思うかもしれません。幸いなことに、ここで Merkle ツリーの出番です。Merkle ツリーを使用すると、ファイルをチャンクに分割できます。50 GB のファイルであれば、100 個の断片に分割して、各断片のサイズを 0.5 GB にします。その後、断片ごとにダウンロードされます。これは基本的に、ファイルをトレントするときに行うことです。
この場合、ソースは Merkle ルートと呼ばれるハッシュを提供します。この単一のハッシュは、ファイルを構成するすべてのデータ チャンクを表します。ただし、Merkle ルートを使用すると、データの検証がはるかに簡単になります。
簡単にするために、8 GB のファイルを 8 つの部分に分割する例を見てみましょう。それぞれのフラグメントを A から H と呼びます。各フラグメントはハッシュ関数に渡され、8 つの異なるハッシュが生成されます。
8 つのフラグメントをそれぞれハッシュ関数に渡してハッシュを取得します。
わかりました。これで少しは意味が通るようになりました。すべてのフラグメントのハッシュがあるので、フラグメントの 1 つに欠陥があれば、ソースのフラグメントと比較すればわかりますよね? 可能性はありますが、それは非常に非効率的です。ファイルに何千ものフラグメントがある場合、本当にそれらすべてをハッシュして、結果を細かく比較するつもりですか?
いいえ。その代わりに、ハッシュの各ペアを取得し、それらを組み合わせて、一緒にハッシュします。つまり、hA + hB、hC + hD、hE + hF、hG + hH をハッシュします。最終的に 4 つのハッシュが作成されます。次に、これらを使用してハッシュをもう 1 回実行し、2 つのハッシュを作成します。最後に、残りの 2 つをハッシュして、マスター ハッシュ、つまり Merkle ルート (またはルート ハッシュ) を作成します。
この構造は逆さまの木のように見えます。一番下の行には葉があり、それが組み合わさってノードが形成され、最終的にルートが形成されます。
これで、ダウンロードしたファイルを表す Merkle ルートができました。このルート ハッシュをソースから提供されたものと比較できます。一致すれば完璧です。ただし、ハッシュが異なる場合は、データが変更されたことが確実です。つまり、1 つ以上のフラグメントが異なるハッシュを生成したということです。そのため、データが少しでも変更されると、まったく異なる Merkle ルートが生成されます。
幸いなことに、どのフラグメントに欠陥があるかを確認する便利な方法があります。今回の場合、hE だとしましょう。まず、Merkle ルートを生成した 2 つのハッシュ (hABCD と hEFGH) をピアに要求します。そのサブツリーには間違いがないので、hABCD の値はピアのハッシュと一致するはずです。しかし、hEFGH は一致しないので、そこをチェックする必要があります。次に、hEF と hGH を要求し、自分のハッシュと比較します。hGH は問題ないように見えるので、hEF が犯人であることがわかります。最後に、hE と hF のハッシュを比較します。hE が間違っていることがわかったので、そのチャンクを再ダウンロードできます。
まとめると、データを複数の部分に分割し、それらを繰り返しハッシュして Merkle ルートを形成することで、Merkle ツリーが作成されます。これにより、データの一部に問題がないかどうかを効率的に検証できます。次のセクションで説明するように、他にも興味深いアプリケーションがあります。
暗号通貨を始めませんか? Binance でビットコインを購入しましょう!
なぜビットコインでマークルルートが使用されるのですか?
マークルツリーの使用例はいくつかありますが、ここではブロックチェーンにおけるその重要性に焦点を当てます。マークルツリーは、ビットコインや他の多くの暗号通貨に不可欠です。マークルツリーはすべてのブロックの不可欠な要素であり、ブロックヘッダーに含まれています。ツリーのリーフを取得するには、ブロックに含まれるすべてのトランザクションのトランザクションハッシュ（TXID）を使用します。
この場合、マークルルートはいくつかの目的を果たします。暗号通貨のマイニングとトランザクション検証におけるその応用を見てみましょう。
鉱業
ビットコインのブロックは 2 つの部分から構成されています。最初の部分はブロック ヘッダーで、ブロックのメタデータを含む固定サイズのセグメントです。2 番目の部分はトランザクションのリストで、サイズは可変ですが、ヘッダーよりもはるかに大きくなる傾向があります。
有効なブロックを採掘するには、マイナーはデータを繰り返しハッシュして、特定の条件に一致する出力を生成する必要があります。有効なブロックを見つけるまでに何兆回も試行することがあります。試行ごとに、ブロック ヘッダー内のランダムな数字 (nonce) を変更して、異なる出力を生成します。しかし、ブロックの大部分は同じままです。トランザクションが何千もある場合があり、そのたびにハッシュする必要があります。
マークル ルートは、プロセスを大幅に効率化します。マイニングを開始するときは、含めたいすべてのトランザクションを並べてマークル ツリーを構築します。結果のルート ハッシュ (32 バイト) をブロック ヘッダーに配置します。その後、マイニングを行うときは、ブロック全体ではなく、ブロック ヘッダーのみをハッシュする必要があります。
これが機能するのは、改ざんが不可能だからです。ブロックのすべてのトランザクションをコンパクトな形式で効果的にまとめます。有効なブロック ヘッダーを見つけて、後でトランザクション リストを変更することはできません。そうすると、マークル ルートが変更されてしまうからです。ブロックが他のノードに送信されると、ノードはトランザクション リストからルートを計算します。それがヘッダーのものと一致しない場合、ノードはブロックを拒否します。
検証
マークルルートには、活用できる興味深い特性がもう 1 つあります。これは、ライト クライアント (ブロックチェーンの完全なコピーを保持していないノード) に関するものです。リソースが限られたデバイスでノードを実行している場合、ブロックのすべてのトランザクションをダウンロードしてハッシュすることは望ましくありません。代わりにできることは、マークル証明を要求することです。マークル証明とは、トランザクションが特定のブロックにあることを証明する、フルノードによって提供される証拠です。これは、より一般的には簡易支払い検証 (SPV) と呼ばれ、ビットコインのホワイトペーパーでサトシ ナカモトによって詳細に説明されています。
hD を確認するには、赤で表示されたハッシュのみが必要です。
TXID が hD であるトランザクションに関する情報を知りたいというシナリオを考えてみましょう。hC が提供されていれば、hCD を計算できます。次に、hABCD を計算するために hAB が必要です。最後に、hEFGH を使用して、結果の Merkle ルートがブロック ヘッダーのものと一致するかどうかを確認できます。一致する場合、トランザクションがブロックに含まれていたことが証明されます。異なるデータで同じハッシュを作成することはほぼ不可能です。
上記の例では、ハッシュを 3 回しか実行していません。Merkle 証明がなければ、7 回実行する必要があります。現在、ブロックには数千のトランザクションが含まれているため、Merkle 証明を使用すると、多くの時間とコンピューティング リソースを節約できます。
最後に
マークルツリーは、さまざまなコンピューターサイエンスのアプリケーションで非常に有用であることが証明されています。これまで見てきたように、ブロックチェーンでは非常に価値があります。分散システムでは、マークルツリーを使用すると、ネットワークに不要なデータを氾濫させることなく、情報を簡単に検証できます。
マークルツリー（およびマークルルート）がなければ、ビットコインやその他の暗号通貨のブロックは、今日ほどコンパクトにはならなかったでしょう。また、軽量クライアントはプライバシーとセキュリティの面で不足していますが、マークル証明により、ユーザーは最小限のオーバーヘッドで、自分のトランザクションがブロックに含まれているかどうかを確認できます。
