マークルツリー

暗号学とコンピュータサイエンスにおいて、ハッシュツリーまたはMerkle ツリーとは、すべての「リーフ」ノードにデータブロックの暗号ハッシュのラベルが付けられ、リーフでないすべてのノード (ブランチ、内部ノード、またはi ノードと呼ばれる) にその子ノードのラベルの暗号ハッシュのラベルが付けられるツリーです。ハッシュツリーを使用すると、大規模なデータ構造の内容を効率的かつ安全に検証できます。ハッシュツリーは、ハッシュリストとハッシュチェーンを一般化したものです。

リーフノードが与えられたバイナリハッシュツリーの一部であることを証明するには、ツリー内のリーフノードの数の対数に比例するハッシュの数を計算する必要があります。 ^[1]逆に、ハッシュリストでは、その数はリーフノードの数自体に比例します。したがって、マークルツリーは、ツリーのルートがコミットメントと見なされ、リーフノードが明らかにされ、元のコミットメントの一部であることが証明される、暗号化コミットメントスキームの効率的な例です。^[2]

ハッシュツリーの概念は、1979年に特許を取得したラルフ・マークルにちなんで名付けられました。 ^[3]^[4]

用途

ハッシュツリーは、コンピューター内およびコンピューター間で保存、処理、転送されるあらゆる種類のデータを検証するために使用できます。ハッシュツリーは、ピアツーピアネットワーク内の他のピアから受信したデータブロックが破損や変更なしに受信されたことを確認するのに役立ちます。また、他のピアが嘘をついて偽のブロックを送信していないことを確認することもできます。

ハッシュツリーは次の場合に使用されます。

ハッシュベースの暗号化。
惑星間ファイルシステム（IPFS）、
ビットトレント
BtrfsおよびZFSファイルシステム^[5]（データ劣化に対抗するため^[6]）
Datプロトコル;
Apache Waveプロトコル^[7]
GitおよびMercurial は分散リビジョン管理システムです (ただし、厳密に言えば、ツリーではなく有向非巡回グラフを使用します)。
Tahoe -LAFSバックアップシステム。
ゼロネット;
ビットコインとイーサリアムのピアツーピアネットワーク^[8]
証明書の透明性フレームワーク。
NixパッケージマネージャとGNU Guixのような派生製品^[9]
Apache Cassandra、Riak、DynamoなどのNoSQLシステムの数。^[10]

信頼できるコンピューティングシステムではハッシュツリーを使用するという提案がなされている。^[11]

サトシ・ナカモトによるビットコインの初期のマークルツリーの実装では、ハッシュ関数の圧縮ステップが過度に適用されていましたが、これは高速マークルツリーを使用することで緩和されました。^[12]

概要

ハッシュツリーはハッシュのツリーであり、そのリーフ (つまり、リーフノード、"リーフ" とも呼ばれる) は、たとえばファイルまたはファイルセット内のデータブロックのハッシュです。ツリーの上位のノードは、それぞれの子のハッシュです。たとえば、上の図では、ハッシュ 0 は、ハッシュ 0-0とハッシュ 0-1の連結をハッシュした結果です。つまり、ハッシュ 0 =ハッシュ(ハッシュ 0-0 +ハッシュ 0-1 ) であり、"+" は連結を表します。

ほとんどのハッシュツリー実装はバイナリ (各ノードの下に 2 つの子ノード) ですが、各ノードの下にさらに多くの子ノードを使用することもできます。

通常、ハッシュにはSHA-2などの暗号化ハッシュ関数が使用されます。ハッシュツリーで意図しない損傷から保護することのみが必要な場合は、 CRCなどのセキュリティ保護されていないチェックサムを使用できます。

ハッシュツリーの最上部にはトップハッシュ（またはルートハッシュ、マスターハッシュ）がある。P2Pネットワークでファイルをダウンロードする前に、ほとんどの場合、トップハッシュは信頼できるソース（たとえば、ダウンロードするファイルの推奨情報を提供していることで知られている友人やウェブサイトなど）から取得される。トップハッシュが利用できる場合は、P2Pネットワーク内のピアなど、信頼できないソースからハッシュツリーを受け取ることができる。次に、受け取ったハッシュツリーを信頼できるトップハッシュと照合し、ハッシュツリーが破損しているか偽物である場合は、プログラムがトップハッシュと一致するハッシュツリーを見つけるまで、別のソースからの別のハッシュツリーが試される。^[13]

ハッシュリストとの主な違いは、ハッシュツリーの 1 つのブランチを一度にダウンロードでき、ツリー全体がまだ利用できなくても各ブランチの整合性をすぐに確認できることです。たとえば、図では、ツリーにハッシュ 0-0とハッシュ 1がすでに含まれている場合、データブロックをハッシュし、その結果をハッシュ 0-0、ハッシュ 1と繰り返し結合し、最後に結果を最上位ハッシュと比較することで、データブロック L2の整合性をすぐに確認できます。同様に、ツリーにハッシュ1-1とハッシュ 0 がすでに含まれている場合、データブロック L3の整合性を検証できます。これは、ファイルを非常に小さなデータブロックに分割して、破損した場合に小さなブロックのみを再ダウンロードすればよいようにするのが効率的であるため、利点となります。ハッシュファイルが大きい場合、このようなハッシュリストまたはハッシュチェーンはかなり大きくなります。ただし、ツリーの場合は、1 つの小さなブランチをすばやくダウンロードし、ブランチの整合性を確認してから、データブロックのダウンロードを開始できます。^[^要出典^]

第二原像攻撃

マークルハッシュルートはツリーの深さを示さないため、攻撃者が同じマークルハッシュルートを持つオリジナル以外の文書を作成する第2原画像攻撃が可能になります。上記の例では、攻撃者は2つのデータブロックを含む新しい文書を作成できます。最初のブロックはハッシュ0-0 +ハッシュ0-1で、2番目のブロックはハッシュ1-0 +ハッシュ1-1です。^[14]^[15]

証明書の透明性では、1つの簡単な修正方法が定義されています。リーフノードのハッシュを計算するときは、ハッシュデータの先頭に0x00バイトが追加され、内部ノードのハッシュを計算するときは0x01が先頭に追加されます。^{[13]ハッシュツリーのサイズを制限することは、いくつかの}正式なセキュリティ証明の前提条件であり、いくつかの証明をより厳密にするのに役立ちます。一部の実装では、ハッシュの前にハッシュツリーの深さのプレフィックスを使用してツリーの深さを制限しているため、抽出されたハッシュチェーンは、プレフィックスが各ステップで減少し、リーフに到達したときにまだ正である場合にのみ有効であると定義されます。

タイガーツリーハッシュ

タイガーツリーハッシュは広く使われているハッシュツリーの形式です。バイナリハッシュツリー（各ノードの下に2つの子ノード）を使用し、通常1024バイトのデータブロックサイズを持ち、タイガーハッシュを使用します。^[16]

タイガーツリーハッシュは、Gnutella ^[17]、 Gnutella2、Direct Connect P2Pファイル共有プロトコル^{[18] 、および}Phex ^[19]、BearShare、LimeWire、Shareaza、DC++ ^[20]、gtk-gnutella ^[21]などのファイル共有アプリケーションで使用されています。

参照

参考文献

^ ベッカー、ゲオルグ (2008-07-18)。「マークル署名スキーム、マークルツリー、およびその暗号解析」(PDF)。ルール大学ボーフム校。 p. 16. 2014 年 12 月 22 日にオリジナル(PDF)からアーカイブされました。2013 年 11 月 20 日に取得。
^ 「応用暗号ハンドブック」cacr.uwaterloo.ca . セクション 13.4.1 . 2024 年 3 月 7 日閲覧。
^ Merkle, RC (1988)。「従来の暗号化関数に基づくデジタル署名」。暗号学の進歩 - CRYPTO '87。コンピュータサイエンスの講義ノート。第 293 巻。pp. 369–378。doi : 10.1007/ 3-540-48184-2_32。ISBN 978-3-540-18796-7。
^ 米国特許 4309569、ラルフ・マークル、「デジタル署名を提供する方法」、1982 年 1 月 5 日発行、リーランド・スタンフォード・ジュニア大学の理事会に譲渡
^ Bonwick, Jeff (2005-12-08). 「ZFS エンドツーエンドのデータ整合性」。blogs.oracle.com。2012年 4 月 3 日時点のオリジナルよりアーカイブ。2013 年 9 月 19 日閲覧。
^ Likai Liu. 「単一ドライブでのビットロット耐性」likai.org。
^ 「General Verifiable Federation」。Google Wave プロトコル。2018 年 4 月 8 日時点のオリジナルよりアーカイブ。2017年 3 月 9 日閲覧。
^ Koblitz, Neal; Menezes, Alfred J. (2016年1月). 「Cryptocash、暗号通貨、および暗号契約」. Designs, Codes and Cryptography . 78 (1): 87–102. CiteSeerX 10.1.1.701.8721 . doi :10.1007/s10623-015-0148-5. S2CID 16594958.
^ Dolstra, E. 純粋に機能的なソフトウェア展開モデル。オランダ、ユトレヒトの理学部博士論文。2006 年 1 月。p.21 ISBN 90-393-4130-3。
^ Adam Marcus. 「NoSQL エコシステム」. aosabook.org .レプリカが長時間ダウンした場合、または使用できないレプリカのヒント付きハンドオフを保存しているマシンもダウンした場合、レプリカは互いに同期する必要があります。この場合、Cassandra と Riak は Dynamo にヒントを得たアンチエントロピーと呼ばれるプロセスを実装します。アンチエントロピーでは、レプリカは Merkle ツリーを交換して、同期されていないレプリケートされたキー範囲の部分を特定します。Merkle ツリーは階層的なハッシュ検証です。キー空間全体のハッシュが 2 つのレプリカ間で同じでない場合、同期されていないキーが特定されるまで、レプリケートされたキー空間のより小さな部分のハッシュを交換します。このアプローチにより、ほとんどが同様のデータを含むレプリカ間の不要なデータ転送が削減されます。
^ Kilian, J. (1995). 「改良された効率的な引数（暫定版）」(PDF) . CRYPTO . doi : 10.1007/3-540-44750-4_25 .
^ マーク・フリーデンバッハ: 高速なマークルツリー
^ ab Laurie, B.; Langley, A.; Kasper, E. (2013 年 6 月). 「証明書の透明性」. IETF : RFC6962. doi :10.17487/rfc6962.
^ Elena Andreeva、Charles Bouillaguet、Orr Dunkelman、John Kelsey (2009 年 1 月)。「Merkle-Damgård を超える Herding、Second Preimage、Trojan Message 攻撃」。暗号化の分野選択。コンピュータサイエンスの講義ノート。第 5867 巻。SAC。pp. 393–414。doi :10.1007/ 978-3-642-05445-7_25。ISBN 978-3-642-05443-3。
^ Elena Andreeva、Charles Bouillaguet、Pierre-Alain Fouque、Jonathan J. Hoch、John Kelsey、Adi Shamir、Sebastien Zimmer (2008)。「ディザリングされたハッシュ関数に対する第 2 原像攻撃」。Smart、Nigel (編)。暗号学の進歩- EUROCRYPT 2008。コンピュータサイエンスの講義ノート。第 4965 巻。イスタンブール、トルコ。pp. 270–288。doi : 10.1007 /978-3-540-78967-3_16。ISBN 978-3-540-78966-6. S2CID 12844017。{{cite book}}: CS1 メンテナンス: 場所が見つかりません発行者 (リンク)
^ Chapweske, J.; Mohr, G. (2003 年 3 月 4 日). 「Tree Hash EXchange format (THEX)」。2009 年 8 月 3 日時点のオリジナルよりアーカイブ。
^ 「tigertree.c ファイルリファレンス」。Gtk -Gnutella 。 2018年9月23日閲覧。
^ 「監査: P2P DirectConnect アプリケーション」。Symantec。2015年1月29日時点のオリジナルよりアーカイブ。 2018年9月23日閲覧。
^ アルネ・バーベンハウザーハイデ (2007 年 1 月 7 日)。「Phex 3.0.0 がリリースされました」。フェックス。2018 年9 月 23 日に取得。
^ 「DC++ の機能リスト」。dcplusplus.sourceforge.net。
^ 「開発」。GTK-Gnutella 。2018年9月23日閲覧。

さらに読む

マークルツリー特許 4,309,569 – ハッシュツリー構造と、それを使用して多数のワンタイム署名を処理する方法の両方を説明します。
ツリーハッシュ交換フォーマット（THEX） – Tigerツリーの詳細な説明

外部リンク

この記事を聞く（5分）

この音声ファイルは、2013 年 9 月 17 日付のこの記事の改訂版から作成されたもので、その後の編集は反映されていません。

動的にサイズ変更可能なバイナリ SHA-256 ハッシュツリー (Merkle ツリー) の AC 実装
Java での Merkle ツリーの実装
C# の Tiger Tree Hash (TTH) ソースコード (Gil Schmidt 著)
C および Java での Tiger Tree Hash (TTH) 実装
RHashはオープンソースのコマンドラインツールで、TTHとTTHを使用したマグネットリンクを計算できます。

[1] ベッカー、ゲオルグ (2008-07-18)。「マークル署名スキーム、マークルツリー、およびその暗号解析」(PDF)。ルール大学ボーフム校。 p. 16. 2014 年 12 月 22 日にオリジナル(PDF)からアーカイブされました。2013 年 11 月 20 日に取得。

[2] 「応用暗号ハンドブック」cacr.uwaterloo.ca . セクション 13.4.1 . 2024 年 3 月 7 日閲覧。

[3] Merkle, RC (1988)。「従来の暗号化関数に基づくデジタル署名」。暗号学の進歩 - CRYPTO '87。コンピュータサイエンスの講義ノート。第 293 巻。pp. 369–378。doi : 10.1007/ 3-540-48184-2_32。ISBN 978-3-540-18796-7。

[4] 米国特許 4309569、ラルフ・マークル、「デジタル署名を提供する方法」、1982 年 1 月 5 日発行、リーランド・スタンフォード・ジュニア大学の理事会に譲渡

[endtoend-5] Bonwick, Jeff (2005-12-08). 「ZFS エンドツーエンドのデータ整合性」。blogs.oracle.com。2012年 4 月 3 日時点のオリジナルよりアーカイブ。2013 年 9 月 19 日閲覧。

[6] Likai Liu. 「単一ドライブでのビットロット耐性」likai.org。

[7] 「General Verifiable Federation」。Google Wave プロトコル。2018 年 4 月 8 日時点のオリジナルよりアーカイブ。2017年 3 月 9 日閲覧。

[8] Koblitz, Neal; Menezes, Alfred J. (2016年1月). 「Cryptocash、暗号通貨、および暗号契約」. Designs, Codes and Cryptography . 78 (1): 87–102. CiteSeerX 10.1.1.701.8721 . doi :10.1007/s10623-015-0148-5. S2CID 16594958.

[9] Dolstra, E. 純粋に機能的なソフトウェア展開モデル。オランダ、ユトレヒトの理学部博士論文。2006 年 1 月。p.21 ISBN 90-393-4130-3。

[10] Adam Marcus. 「NoSQL エコシステム」. aosabook.org .レプリカが長時間ダウンした場合、または使用できないレプリカのヒント付きハンドオフを保存しているマシンもダウンした場合、レプリカは互いに同期する必要があります。この場合、Cassandra と Riak は Dynamo にヒントを得たアンチエントロピーと呼ばれるプロセスを実装します。アンチエントロピーでは、レプリカは Merkle ツリーを交換して、同期されていないレプリケートされたキー範囲の部分を特定します。Merkle ツリーは階層的なハッシュ検証です。キー空間全体のハッシュが 2 つのレプリカ間で同じでない場合、同期されていないキーが特定されるまで、レプリケートされたキー空間のより小さな部分のハッシュを交換します。このアプローチにより、ほとんどが同様のデータを含むレプリカ間の不要なデータ転送が削減されます。

[11] Kilian, J. (1995). 「改良された効率的な引数（暫定版）」(PDF) . CRYPTO . doi : 10.1007/3-540-44750-4_25 .

[12] マーク・フリーデンバッハ: 高速なマークルツリー

[:0-13] Laurie, B.; Langley, A.; Kasper, E. (2013 年 6 月). 「証明書の透明性」. IETF : RFC6962. doi :10.17487/rfc6962.

[14] Elena Andreeva、Charles Bouillaguet、Orr Dunkelman、John Kelsey (2009 年 1 月)。「Merkle-Damgård を超える Herding、Second Preimage、Trojan Message 攻撃」。暗号化の分野選択。コンピュータサイエンスの講義ノート。第 5867 巻。SAC。pp. 393–414。doi :10.1007/ 978-3-642-05445-7_25。ISBN 978-3-642-05443-3。

[15] Elena Andreeva、Charles Bouillaguet、Pierre-Alain Fouque、Jonathan J. Hoch、John Kelsey、Adi Shamir、Sebastien Zimmer (2008)。「ディザリングされたハッシュ関数に対する第 2 原像攻撃」。Smart、Nigel (編)。暗号学の進歩- EUROCRYPT 2008。コンピュータサイエンスの講義ノート。第 4965 巻。イスタンブール、トルコ。pp. 270–288。doi : 10.1007 /978-3-540-78967-3_16。ISBN 978-3-540-78966-6. S2CID 12844017。{{cite book}}: CS1 メンテナンス: 場所が見つかりません発行者 (リンク)

[16] Chapweske, J.; Mohr, G. (2003 年 3 月 4 日). 「Tree Hash EXchange format (THEX)」。2009 年 8 月 3 日時点のオリジナルよりアーカイブ。

[17] 「tigertree.c ファイルリファレンス」。Gtk -Gnutella 。 2018年9月23日閲覧。

[18] 「監査: P2P DirectConnect アプリケーション」。Symantec。2015年1月29日時点のオリジナルよりアーカイブ。 2018年9月23日閲覧。

[19] アルネ・バーベンハウザーハイデ (2007 年 1 月 7 日)。「Phex 3.0.0 がリリースされました」。フェックス。2018 年9 月 23 日に取得。

[20] 「DC++ の機能リスト」。dcplusplus.sourceforge.net。

[21] 「開発」。GTK-Gnutella 。2018年9月23日閲覧。