Solidity でマークル ツリーを実装する方法

マークル ツリーは、大規模なデータ構造の内容を効率的かつ安全に検証できるようにするバイナリ ツリーです。このツリーの概念は、アメリカの暗号学者であるラルフ マークルによって提案され、1982 年に特許を取得しました。

ハッシュの長さは、入力データの量に関係なく同じままです。リーフ頂点にはデータ ブロックのハッシュが含まれますが、内部頂点には 2 つの子頂点の値の加算からのハッシュが含まれます。次に、ルート頂点はデータセット全体のハッシュを構成します。

理論

最初は、互いにまったく関連性のないデータのセットが存在します。データのブロックごとに (トランザクション ブロックチェーンのコンテキスト内で)、ブロックのハッシュを計算する必要があります。ツリーが構築されると、反復ごとに前のブロックがペアでハッシュされるため、データ ブロックの数は2^Nである必要があります。次に、ハッシュのペアがグループ化され、それらに基づいて新しいハッシュが作成されます。ハッシュ化は、各レベルでグループ化するものがある限り継続され、ルート ハッシュ (マークル ルート) を取得するペアが 1 つだけ残った時点で停止します。

H(1-2) = keccak256(H(1) + H(2))

H(3-4) = keccak256(H(3) + H(4))

H(5-6) = keccak256(H(5) + H(6))

H(7-8) = keccak256(H(7) + H(8))

H(1-2-3-4) = keccak256(H(1-2) + H(3-4))

H(5-6-7-8) = keccak256(H(5-6) + H(7-8))

H(1-2-3-4-5-6-7-8) = keccak256(H(1-2-3-4) + H(5-6-7-8))

ルートを取得したら、データを検証できます。ルート ハッシュが元のハッシュと一致する場合は、すべて問題なく、データは有効です。また、ツリー構造内に特定のデータが存在するかどうかを効率的に確認することも可能である。

H2ハッシュがツリー内に存在することを確認したいとします。証明はデータの配列になります: H1 、 H3-4 、 H5-6-7-8 。これらのハッシュのおかげで、ルート ハッシュを再構築できます。

H(1-2-3-4-5-6-7-8) = keccak256(keccak256(keccak256(H(1) + H(2)) + H(3-4)) + H(5-6-7-8))

次に、結果のハッシュを元のハッシュと比較します。それらが一致する場合、それはハッシュH2ツリー内に存在することを意味します。

練習する

次に、Solidity でマークル ツリーとデータ検証を実装する方法を見てみましょう。

簡単にするために、トランザクションの配列とハッシュの配列をブロックチェーンに直接書き込みます。 32 バイトのハッシュを返す組み込みkeccak256関数を使用するため、ハッシュ配列のデータ型はbytes32になります。配列には動的な長さもあります。一般に、ハッシュ配列の長さは、生成されたハッシュを保持するため、トランザクション配列の長さと同じにはなりません。事前に長さを計算することもできますが、コードを簡素化するために計算しません。必要に応じて、これらの配列をそれぞれpublic 、トランザクションのハッシュを読み取ることができます。

コンストラクターでhashes生成します。最初のステップは、ループ内のtransactions含むブロックのハッシュをカウントすることです。次に、ツリーの各レベルで、ハッシュの数が 2 分の 1 に減ります。ハッシュをハッシュ配列に保存するため、インデックス オフセットは個別に保存する必要があります。ハッシュを計算して追加するときにいくつかの要素を取得するため、内側のループの反復子は 2 ずつ増加します。今回はabi.encodePackedで 2 つのハッシュを追加し、それぞれにインデックスを正しく設定します。左側の要素については、現在のシフト オフセットの値 + 現在のツリー レベルのインデックス、右側の要素については同じです。 +1。

これでツリーを構築しましたが、重要なのはデータを検証することにあります。これを行うには、トランザクションとそのインデックスを取得するvalidateTransaction関数を作成しましょう。残念ながら、Solidity には配列のfindメソッドがないため、トランザクション インデックスを渡すだけの方が簡単です。

まず、トランザクションのハッシュを計算し、プルーフの配列を作成しましょう。トランザクション配列の長さに応じてプルーフの数を見つけ、 proofsIndexesの長さを設定します。その後、ツリーの各レベルで、インデックスに応じて、 hashes内のオフセットを考慮して右または左の要素を取得し、必要な要素を見つけます。次に、証明インデックスの配列を調べて、パリティのインデックスをチェックし、要素がペアの左か右かに応じてハッシュを計算します。最後に、結果のハッシュをルート ハッシュと比較し、結果を返します。

応用

ブロックチェーンにはマークル ツリーの応用例がいくつかあります。

• トランザクションストレージ: たとえば、ビットコインでは、トランザクションブロックはトランザクションの merkle_root のみを保存します。これにより、ブロックのサイズが軽減され、ネットワーク上の負荷が軽減されます。一定数のトランザクションが蓄積された後、スペースを節約するために古いトランザクションを削除することができますが、ブロック自体はツリーのルートのみを保存するため変更されません。
• マイニング: ビットコイン ブロックは、ブロック ヘッダーとトランザクションのリストの 2 つの部分で構成されます。毎回トランザクション ハッシュを再計算する必要を避けるために、トランザクション ハッシュはマークル ツリーに並べられ、その後、ブロック全体ではなくブロック ヘッダーがハッシュされ、ランダムなナンス番号が取得されます。ブロックが他のノードに送信されると、トランザクション リストのルートが計算され、ヘッダーのルートと一致しない場合、ブロックは拒否されます。
• 検証: 検証の本質は、ブロックチェーン全体をダウンロードすることなく監査を行うことです。プロセスが大幅に簡素化され、データに関する情報を開示することなくデータの存在を確認できるため、機密情報の検証に役立ちます。

まとめ

マークル ツリーがなければ、ブロックチェーンは非常に煩雑になるため、マークル証明によりデータの信頼性をコスト効率よく検証できます。

マークル ツリーは、トランザクションを効率的に保存するためにブロックチェーン (ビットコイン、イーサリアムなど) で積極的に使用されていますが、これが唯一の用途ではありません。たとえば、FTX 取引所の崩壊後、多くの取引所はマークル ツリーを利用する Proof-of-Reserve メカニズムを実装しました。