マークルツリーとは何ですか? このブロックチェーンコンポーネントの初心者ガイド

マークル ツリーは、ブロックチェーンの機能を支える基本的なコンポーネントです。 これらにより、大規模なデータ構造、およびブロックチェーンの場合は無限のデータセットの効率的かつ安全な検証が可能になります。

ブロックチェーンにマークル ツリーを実装すると、複数の効果があります。 これにより、データの整合性を維持するためのハッシュ ベースのアーキテクチャと、データの整合性を検証する簡単な方法を提供しながら、拡張が可能になります。

暗号化ハッシュ関数は、マークル ツリーの動作を可能にする基盤となるテクノロジであるため、まず暗号化ハッシュ関数とは何かを理解することが重要です。

簡単な評決: マークル ツリーは、大規模なデータ セットの効率的な整合性検証とマッピングを可能にする暗号ハッシュで構成されるデータ構造であり、ブロックチェーンや分散バージョン管理などのシステムの不可欠なコンポーネントとなっています。

概要

暗号化ハッシュ関数

簡単に言えば、ハッシュ関数は、任意のサイズのデータ​​ (入力) を固定サイズの出力にマッピングするために使用される関数です。 ハッシュ アルゴリズムがデータ入力に適用され、その結果得られる固定長の出力はハッシュと呼ばれます。

多くのハッシュ アルゴリズムが広く公開されており、ニーズに基づいて選択できます。

任意の入力から得られるハッシュは、長さが固定されているだけでなく、入力に対して完全に一意であり、関数自体が決定的です。 つまり、同じ入力に対して関数を何度実行しても、出力は常に同じになります。

たとえば、入力として以下のデータ セットがある場合、結果として得られる出力は入力ごとに一意になります。 XNUMX 番目と XNUMX 番目の例では、入力の違いが XNUMX ワードだけであるにもかかわらず、結果の出力が完全に異なっていることに注目してください。

これはデータの「フィンガープリント」を可能にするため、非常に重要です。

暗号化ハッシュ関数、Wikipedia からの画像

出力 (この例ではハッシュ合計) の長さは、使用されるハッシュ アルゴリズムによって決定される長さと常に同じであるため、結果として得られるハッシュだけで大量のデータを識別できます。

大量のデータを含むシステムでは、固定長の出力でデータを保存および識別できる利点により、ストレージを大幅に節約し、効率の向上に役立ちます。

ブロックチェーン内では、ブロックチェーンの状態を判断するためにハッシュ アルゴリズムが使用されます。

ブロックチェーンは、データと前のブロックを指すハッシュ ポインターを含むリンクされたリストで、接続されたブロックのチェーンを作成するため、「ブロックチェーン」という名前が付けられています。

各ブロックは、前のブロック内のデータと前のブロックのアドレスのハッシュであるハッシュ ポインターを介して相互に接続されます。 この形式でデータのブロックをリンクすると、前のブロックのすべてのハッシュ データが XNUMX つのハッシュにハッシュされるため、結果として得られる前のブロックの各ハッシュはブロックチェーンの全体の状態を表します。

これは (SHA-256 アルゴリズムの場合)、次のような出力 (ハッシュ) で表されます。

b09a57d476ea01c7f91756adff1d560e579057ac99a28d3f30e259b30ecc9dc7

上記のハッシュは、その前のブロックチェーン全体の状態のフィンガープリントです。 新しいブロックの前のブロックチェーンの状態 (ハッシュされたデータとして) が入力であり、結果のハッシュが出力です。

マークル ツリーを使用せずに暗号化ハッシュを使用することも可能ですが、非常に非効率であり、スケーラビリティがありません。 ハッシュを使用してデータを一連の形式でブロックに保存するのは、時間がかかり面倒です。

ご覧のとおり、マークル ツリーでは、データの整合性を簡単に解決できるだけでなく、マークル証明を使用してツリー全体でそのデータをマッピングすることもできます。

マークル ツリーとマークル プルーフ

1979 年にこの概念の特許を取得した Ralph Merkle にちなんで名付けられたマークル ツリーは、基本的に、各非リーフ ノードがそれぞれの子ノードのハッシュであるデータ構造ツリーです。

リーフ ノードは、ツリー内のノードの最下層です。 一見、わかりにくいと思われるかもしれませんが、よく使われる以下の図を見ると、より理解しやすくなります。

バイナリ ハッシュ ツリーの例、Wikipedia からの画像

重要なのは、左側の非リーフ ノードまたは「ブランチ」 (ハッシュ 0-0 およびハッシュ 0-1 で表される) がそれぞれの子 L1 および L2 のハッシュであることに注目してください。 さらに、ブランチ ハッシュ 0 がその連結された子であるブランチ ハッシュ 0-0 とハッシュ 0-1 のハッシュであることに注目してください。

上の例は、バイナリ マークル ツリーとして知られるマークル ツリーの最も一般的で単純な形式です。 ご覧のとおり、ルート ハッシュとして知られる、ツリー全体のハッシュであるトップ ハッシュがあります。 基本的に、マークル ツリーは、「n」個のハッシュを受け取り、それを XNUMX つのハッシュで表すことができるデータ構造です。

ツリーの構造により、任意の大量のデータの効率的なマッピングが可能になり、そのデータの変更が発生した場所を簡単に識別できるようになります。 この概念により、マークル証明が可能になり、実際にハッシュのセット全体を確認することなく、データのハッシュがツリーの上に至るまで一貫しており、正しい位置にあることを検証できます。

代わりに、データセット全体ではなく、ハッシュの小さなサブセットのみをチェックすることで、データチャンクがルートハッシュと一致していることを検証できます。

ルート ハッシュが公に知られており、信頼されている限り、データベース上でキーと値のルックアップを実行したい人は誰でも、マークル証明を使用して、データベース内のデータの位置と整合性を検証することが可能です。特定のルート。

ルート ハッシュが利用可能な場合は、信頼できないソースからハッシュ ツリーを受信でき、ツリー全体がまだ利用できない場合でも、ツリーの XNUMX つのブランチを一度にダウンロードしてデータの整合性を即座に検証できます。

マークル ツリー構造の最も重要な利点の XNUMX つは、はるかに少量のデータを検証するために使用される同様のハッシュ メカニズムを通じて、任意の大規模なデータ セットを認証できることです。

ツリーは、大きなデータ セットを管理しやすい小さな部分に分散する場合に有利で、全体のデータ サイズが大きくなるにもかかわらず、整合性の検証の障壁が大幅に軽減されます。

ルート ハッシュは、データベース全体を含む、またはブロックチェーン全体の状態を表すデータ セット全体のフィンガープリントとして使用できます。 次のセクションでは、ビットコインやその他のシステムがマークル ツリーを実装する方法について説明します。

ビットコインのマークルツリー

ビットコインで採用されている暗号化ハッシュ関数は SHA-256 アルゴリズムです。 これは「Secure Hashing Algorithm」の略で、出力は固定長の 256 ビットです。 ビットコインのマークル ツリーの基本的な機能は、すべてのブロックにトランザクションを保存し、最終的にはプルーニングすることです。

前述したように、ブロックチェーン内のブロックは、前のブロックのハッシュを通じて接続されます。 ビットコインでは、各ブロックには、そのブロック内のすべてのトランザクションと、以下で構成されるブロック ヘッダーが含まれます。

• ブロックのバージョン番号
• 前のブロックハッシュ
• スタンプ
• マイニング難易度ターゲット
• ノンス
• マークルルートハッシュ

下の画像はビットコインのホワイトペーパーからのもので、マークル ツリーが各ブロックにどのように適合するかを示しています。

トランザクションはマイナーによってブロックに組み込まれ、マークル ツリーの一部としてハッシュされ、ブロック ヘッダーに保存されるマークル ルートにつながります。 この設計には多くの明確な利点があります。

最も注目すべき点は、ホワイトペーパーで概要が説明されているように、これにより「軽量クライアント」とも呼ばれる Simple Payment Verification (SPV) ノードの存在が可能になります。 これらのノードは、ビットコイン ブロックチェーン全体をダウンロードする必要はなく、最も長いチェーンのブロック ヘッダーのみをダウンロードする必要があります。

SPV ノードは、操作対象の格納されたブロック ヘッダーが最長のチェーンの一部であると確信するまでピア ノードにクエリを実行することでこれを実現できます。 SPV ノードは、マークル証明を使用してトランザクションを特定のマークル ツリーにマッピングし、最長チェーンの一部であるブロック ヘッダーにそれぞれのマークル ツリーのルート ハッシュを含めることで、トランザクションのステータスを判断できます。

さらに、ビットコインのマークルツリーの実装により、スペースを節約するためにブロックチェーンの枝刈りが可能になります。 これは、ルート ハッシュのみがブロック ヘッダーに格納されている結果であるため、マークル ツリーの不要な枝を削除し、マークル証明に必要な枝だけを保存することで古いブロックを枝刈りすることができます。

他のブロックチェーンおよびシステムへのマークル ツリーの実装

ビットコインはマークル ツリーを実装した最初のブロックチェーンですが、他の多くのブロックチェーンも同様のマークル ツリー構造、またはさらに複雑なバージョンを実装しています。

さらに、マークルツリーの実装はブロックチェーンに限定されず、他のさまざまなシステムにも適用されます。

もう 3 つの最もよく知られた暗号通貨であるイーサリアムも、別のマークル ツリー実装の好例です。 イーサリアムは、より複雑なアプリケーションを構築するためのプラットフォームとしてチューリング完全であるため、実際には XNUMX 種類のオブジェクトに使用される XNUMX つの別々のマークル ツリーであるマークル パトリシア ツリーと呼ばれるマークル ツリーのより複雑なバージョンを使用します。 これらの木について詳しくは、こちらをご覧ください。

最後に、マークル ツリーは、Git や IPFS などの分散バージョン管理システムの重要なコンポーネントです。 P2P 形式でコンピュータ間で共有されるデータの整合性を簡単に確保および検証できる機能は、これらのシステムにとって非常に貴重なものとなっています。

まとめ

マークル ツリーはブロックチェーンの不可欠なコンポーネントであり、ブロックチェーンが証明可能な不変性とトランザクションの整合性を持って機能することを効果的に可能にします。

暗号通貨がより大規模で複雑なシステムに発展し続けるにつれて、暗号通貨の基本概念を理解するには、分散ネットワークでそれらが果たす役割とその基盤となる暗号化ハッシュ関数のテクノロジーを理解することが重要です。