マークルツリーの概念は、
公開鍵暗号の研究で有名なコンピュータ科学者であるラルフ・マークル氏によって80年代初頭に発明されました。
マークルツリーは、セット内のデータの整合性を効率的に検証するために使用される構造です。参加者が情報を共有し、独立して検証する必要がある
ピアツーピアネットワークのコンテキストでは特に興味深いものです。
ハッシュ関数はマークルツリー構造の中核にあるため、この記事を読む前に
ハッシュとは何かをクリックし確認することを推奨しています。
大規模なファイルをダウンロードするとします。
オープンソースソフトウェアでは、ダウンロードしたファイルのハッシュが開発者の公開しているハッシュと一致しているかを確認するのが一般的です。一致しているのであれば、あなたのコンピュータにあるファイルは開発者のものと同一であることがわかります。
ハッシュが一致しない場合は問題があり、ソフトウェアを装った悪意のあるファイルをダウンロードしたか、正しくダウンロードがされなかったために動作しません。後者の場合、ファイルのダウンロードに時間がかかり、あなたはプロセスを再起動し、それが再び破損していないかを確認する必要があります。
もっと簡単な方法があればと思うでしょう。幸いなことにマークルツリーがあります。これらを使用し、ファイルをチャンクに分割することができます。50GBファイルの各サイズを0.5GBサイズする場合、100個に分割することができ、その後、ピースバイピースでダウンロードが行われます。これは基本的に、ファイルをトレントするときに行います。
この場合、ソースはマークルルートと呼ばれるハッシュを提供しています。この単一のハッシュは、ファイルを構成するすべてのデータのチャンクを表します。マークルルートを使用すると、データの検証が非常に簡単になります。
8GBファイルを8つのフラグメントに分割した例を見てみましょう。異なるフラグメントAからHを呼び出します。各フラグメントはハッシュ関数に渡され、8つの異なるハッシュが生成されます。
8つの各フラグメントをハッシュ関数に渡してハッシュを取得します。
これで少し意味のあるものができました。すべてのフラグメントにはハッシュがあるので、1つに欠陥がある場合、ソースのものと比較することで判明します。しかし、これは信じ難いほど非効率的です。例えば、あなたのファイルに何千ものフラグメントがあった場合、本当にすべてのフラグメントをハッシュ化し、その結果を注意深く比較するのでしょうか。
いいえ。代わりにハッシュの各ペアを組み合わせてからハッシュします。hA+hB、hC+hD、hE+hF、hG+hHをハッシュし、4つのハッシュにします。次に、これらを使用して別のハッシュ化を行い、最終的に2つにします。最後に、残りの2つをハッシュしてマスターハッシュであるマークルルート（またはルートハッシュ）を取得します。
構造は逆さまの木のように見えます。一番下の行には葉があり、結合されてノードを作成し、最後に根を生成します。
これで、ダウンロードしたファイルを表す、マークルルートが生成されました。このルートハッシュをソースによって提供されたものと比較することができます。一致すれば完璧です。しかし、ハッシュが異なる場合は、データが変更されていることがわかります。要するに、1つ以上のフラグメントが異なるハッシュを生成しています。つまり、データに少しでも手を加えれば、全く異なるマークルルートが得られるということです。
幸いなことにどのフラグメントに欠陥があるかを確認する便利な方法があります。この例では、hEとします。まず、マークルルートを生成した2つのハッシュ（hABCDとhEFGH） をピアに要求します。このサブツリーには間違いがないので、hABCDの値はこれらの値と一致するはずです。しかしhEFGHは一致しないので、そこを確認する必要があります。次にhEFとhGHを要求し、それらを自分のものと比較します。hGHは問題なさそうなので、hEFが原因だとわかります。最後に、hEとhFのハッシュを比較します。hEが正しくないことがわかったので、そのチャンクを再ダウンロードします。
要約すると、データを複数の部分に分割し、マークルツリーを作成し、それらを繰り返しハッシュ化してマークルルートを形成します。これにより、データの一部に何か問題があったかどうかを効率的に検証することができます。次のセクションで説明しますが、他にも興味深いアプリケーションが存在します。
仮想通貨の購入を検討していますか？バイナンスでビットコインを購入しましょう。
マークルツリーのユースケースはいくつかありますが、ここでは
ブロックチェーンにおける重要性に焦点を当てます。マークルツリーは
ビットコインや他の多くの仮想通貨に不可欠です。これらはすべての
ブロックに不可欠なコンポーネントであり、
ブロックヘッダーの中にあります。ツリーの葉を取得するには、ブロックに含まれるすべてのトランザクションのトランザクションハッシュ（
TXID）を使用します。
この場合、マークルルートには2つの目的があります。アプリケーションでの仮想通貨マイニングやトランザクション検証の用途を見てみましょう。
マイニング
ビットコインブロックは2つの部分から構成されています。最初の部分はブロックヘッダーで、ブロックの
メタデータを含む固定サイズのセグメントです。2つ目の部分は、サイズは可変ですが、ヘッダーよりもはるかに大きくなる傾向にあるトランザクションのリストです。
マイナーは、有効なブロックをマイニングし、特定条件に一致する出力を生成するためにデータを繰り返しハッシュする必要があります。有効なブロックを発見するまで何兆回も試行することができます。それぞれの試行で、ブロックヘッダー内の乱数（
ナンス）を変更して、異なる出力を生成します。しかし、ブロックの大部分は同じままです。何千ものトランザクションが存在する可能性はありますが、毎回ハッシュ化する必要があります。
マークルルートはプロセスを大幅に効率化します。マイニングを開始する際、含めるすべてのトランザクションを並べ、マークルツリーを構築します。その結果得られたルートハッシュ（32バイト）をブロックヘッダーに格納します。その後、マイニングを行う際には、ブロック全体ではなく、ブロックヘッダーをハッシュするだけ済みます。
これは改ざん防止機能を備えているためです。ブロックのすべてのトランザクションをコンパクトな形式で効果的に要約することができます。有効なブロックヘッダーの発見後、トランザクションリストを変更することはできません。ブロックが他のノードに送信されると、トランザクションリストからルートが計算されます。もしそれがヘッダ内のルートと一致しない場合、ブロックは拒否されます。
検証
私たちが活用できるマークルルーツにはもう1つ興味深い特性があります。これはライトクライアント（ブロックチェーンのフルコピーを保持していないノード）に関するものです。リソースが限られたデバイス上でノードを実行している場合、ブロックのトランザクションをすべてダウンロードしてハッシュ化することはできません。代わりにできることは、マークル証明を要求することです。これは、トランザクションが特定のブロック内にあることを証明する完全なノードによって提供される証拠です。これは、一般的にはSimplified Payment Verification（SPV）と呼ばれ、ビットコインのホワイトペーパーで
サトシ・ナカモトが詳細に説明しています。
hDを確認するためには、赤で表示されたハッシュのみが必要です。
TXIDがhDのトランザクションに関する情報を知りたい場合を考えてみます。hCが提供されていれば、hCDを計算することができます。次に、hABCDを計算するためにhABが必要です。最後に、hEFGHを使用して、結果のマークルルートがブロックヘッダーのものと一致するかどうかの確認ができます。もし一致していれば、そのトランザクションがブロックに含まれていることの証明になります。異なるデータで同一のハッシュを作成することはほとんど不可能です。
上の例では3回しかハッシュしていませんが、マークル証明がなければ、7回のハッシュ処理が必要でした。最近のブロックには何千ものトランザクションが含まれているため、マークル証明を使用することで、多くの時間と計算リソースを短縮することができます。
マークルツリーは、様々なコンピュータサイエンスのアプリケーションで非常に有用であることが証明されています。分散システムでは、マークルツリーを使用することで、ネットワークに不要なデータを氾濫させることなく、情報を簡単に検証することができます。
マークルツリー（マークルルーツ）がなければ、
ビットコインや他の
仮想通貨のブロックは、現在のようにコンパクトにはならなかったでしょう。また、ライトクライアントはプライバシーとセキュリティ面で不足していますが、マークル証明により、ユーザーは最小限のオーバーヘッドで自分の取引がブロックに含まれているかどうかを確認することができます。
