メルケルツリーとメルケルルートの詳しい説明

目次
マークルツリーとは何ですか?
マークルツリーはどのように機能するのでしょうか?
なぜメルケルルートがビットコインで使用されるのですか?
マイニング
確認する
要約する

マークルツリーとは何ですか?1980 年代初頭、公開キー暗号化の分野で著名なコンピューター科学者であるラルフ マークルは、マークル ツリーの概念を提案しました。
マークル ツリー構造はデータ セットの整合性を効果的に検証でき、参加者が情報を共有して個別に検証する必要があるピアツーピア ネットワークではより効果的です。
ハッシュ関数はマークル ツリー構造の中心です。したがって、この記事に進む前に、ハッシュとは何かを理解しておくことをお勧めします。

マークルツリーはどのように機能するのでしょうか?大きなファイルをダウンロードするとします。オープンソース ソフトウェアをダウンロードする場合、多くの場合、ダウンロードしたファイルのハッシュが開発者によって公開されているものと一致するかどうかを確認する必要があります。それらが一致する場合、2 つの文書には一貫性があります。
ハッシュが一致しない場合は、問題が発生します。ソフトウェアを装った悪意のあるファイルをダウンロードしたか、間違ってダウンロードしたため、最終的にそのファイルは使用できなくなります。ダウンロードが間違っていると、ファイルのダウンロードに長時間待たされることになり、イライラすることは間違いありません。もう一度やり直す場合は、同じ問題が再び起こらないことを祈る必要があります。
この問題をもっと簡単に解決する方法はないか、考えたことはありますか?ここでマークルツリーが登場します。マークル ツリーはファイルを複数のデータ ブロックに分割できます。たとえば、50 GB のファイルは、それぞれのサイズが 0.5 GB の 100 個のコピーに分割できます。その後、それらを 1 つずつダウンロードできます。これがトレントの仕組みです。
このときのファイルソースはマークルルートと呼ばれるハッシュ値です。この単一のハッシュ値は、ファイルを構成するすべてのデータ ブロックを表します。さらに、マークル ルートによりデータの検証が容易になります。
理解を容易にするために、例を挙げます。以下では、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 であることが判明したら、データ ブロックを再ダウンロードします。
要約すると、マークル ツリーの機能は、データを複数の部分に分割し、ハッシュ演算を繰り返し実行して最終的にマークル ルートを形成し、エラー データがどこで発生したかを効果的に検証できるようにすることです。次のセクションでは、その他の興味深いアプリケーションを紹介します。

暗号通貨の旅を始めてみませんか?今すぐBinanceにアクセスしてビットコインを購入してください!

なぜメルケルルートがビットコインで使用されるのですか?マークル ツリーの使用例は数多くありますが、この記事ではブロックチェーンにおけるマークル ツリーの重要な役割に焦点を当てます。ビットコインと多くの暗号通貨はマークル ツリーから切り離せません。マークル ツリーはすべてのブロックに不可欠な部分であり、通常はブロック ヘッダーに配置されます。ブロック内の各トランザクションのトランザクション ハッシュ値 (TXID) を通じて、リーフを取得できます。​
この文脈において、メルケルのルートはいくつかの目的を果たします。暗号通貨のマイニングとトランザクション検証におけるマークル ルートの応用を見てみましょう。

マイニングビットコインブロックは 2 つの部分で構成されます。最初の部分はブロック ヘッダーで、サイズが固定されており、ブロック メタデータが含まれています。 2 番目の部分はブロック本体で、サイズは可変ですが、通常はブロック ヘッダーよりもはるかに大きく、トランザクション リストが含まれます。
マイナーは、有効なブロックを掘り出す前に、特定の条件を満たす結果が生成されるまでデータを繰り返しハッシュする必要があります。正しい結果を得るには、何兆回も試行する必要があります。試行のたびに、マイナーはブロック ヘッダーの乱数、つまり Nonce 値を変更して、異なる結果を生成します。ただし、ブロックの残りの部分は同じままであり、ブロック内の数千のトランザクションは毎回ハッシュする必要があります。
メルケル首相はプロセスを大幅に簡素化した。マイニングが開始されると、すべてのトランザクション キューがパックされてマークル ツリーに構築され、生成された 32 ビットのルート ハッシュ値がブロック ヘッダーに配置されます。そうすれば、ブロック全体をハッシュする必要はなくなり、ブロック ヘッダーだけをハッシュするだけになります。
この方法はデータの改ざんを防止するため効果的であり、ブロック内のすべてのトランザクションをコンパクトな形式で効率的に要約できます。有効なブロック ヘッダーのトランザクション リストは変更できません。変更しないと、マークル ルートが変更されます。ブロックが他のノードに送信された後、トランザクション リストからルート ハッシュが計算されます。ブロックヘッダーの値と一致しない場合、ブロックは拒否される可能性があります。

確認するマークル ルートにはもう 1 つの興味深い特性があり、これは軽量クライアント (ブロックチェーンの完全なコピーを保持しないノード) のアプリケーションに関連しています。リソースが限られたデバイス上でノードを実行している場合は、ブロック内のすべてのトランザクションをダウンロードしてハッシュする必要はありません。代わりに、マークル証明を要求するだけです。マークル証明は、トランザクションが特定のブロックに含まれているという完全なノードによって提供される証明です。この証明は Simple Payment Verification (SPV) としてよく知られており、サトシ ナカモトによるビットコイン ホワイト ペーパーで詳しく説明されています。

hD を確認するには、赤いハッシュを確認するだけです。

TXID hD に関するトランザクション情報を取得するとします。 hC が既知であれば、hCD を計算できます。次に、hAB を介して、hABCD を計算できます。最後に、hEFGH を参照することで、計算されたマークル ルートがブロック ヘッダーのルート ハッシュと一致するかどうかを確認できます。異なるデータを使用して同じハッシュを生成することはほぼ不可能であるため、一致が成功すると、トランザクションがブロックに含まれていたことが証明されます。
上の例では、ハッシュ化は 3 回だけでした。メルケル首相の認証がなければ7年かかっただろう。現在のブロックには何千ものトランザクションが含まれており、マークル証明により時間と計算能力が大幅に節約されます。

要約するマークル ツリーはコンピューター サイエンスのアプリケーションで重要であることが証明されており、これまで見てきたように、ブロックチェーンでも価値があります。マークル ツリーにより、分散システムでの情報検証がより便利になり、ネットワーク内の冗長データの輻輳が回避されます。
マークル ツリーとマークル ルートがなければ、ビットコインやその他の暗号通貨ブロックは今日ほどコンパクトにはならなかったでしょう。軽量クライアントにはプライバシーとセキュリティの点で利点がありませんが、マークル証明を使用すると、ユーザーは最小限の手数料でトランザクションがブロックに含まれていることを検証できます。