マークル木
この記事を聞く
二分ハッシュ木の例。ハッシュ0-0と0-1はそれぞれデータブロックL1とL2のハッシュ値であり、ハッシュ0はハッシュ0-0と0-1を連結したハッシュです

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

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

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

用途

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

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

信頼できるコンピューティングシステムではハッシュツリーを使用するという提案がなされている。[ 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つのデータブロックを含む新しい文書を作成できます。最初のブロックはハッシュ0-0 +ハッシュ0-1、2番目のブロックはハッシュ1-0 +ハッシュ1-1です。[ 14 ] [ 15 ]

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

タイガーツリーハッシュ

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

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

参照

参考文献

  1. ^ Becker, Georg (2008-07-18). 「Merkle署名スキーム、Merkleツリー、およびそれらの暗号解析」(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日公開、リーランド・スタンフォード・ジュニア大学理事会に譲渡 
  5. ^ Bonwick, Jeff (2005年12月8日). 「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. ^ 「ZFS入門 — openzfs最新ドキュメント」 . openzfs.readthedocs.io . 2025年5月27日閲覧。
  9. ^ Koblitz, Neal; Menezes, Alfred J. (2016年1月). 「Cryptocash, cryptocurrencies, and cryptocontracts」. Designs, Codes and Cryptography . 78 (1): 87– 102. CiteSeerX 10.1.1.701.8721 . doi : 10.1007/s10623-015-0148-5 . S2CID 16594958 .  
  10. ^ Dolstra, E.純粋機能的ソフトウェア展開モデル。オランダ、ユトレヒト大学理学部博士論文。2006年1月。p.21 ISBN 90-393-4130-3。
  11. ^ Adam Marcus. 「NoSQLエコシステム」 . aosabook.org .レプリカが長時間ダウンした場合、または利用できないレプリカのヒント付きハンドオフを保存しているマシンもダウンした場合、レプリカは互いに同期する必要があります。この場合、CassandraとRiakはDynamoに着想を得たアンチエントロピーと呼ばれるプロセスを実装しています。アンチエントロピーでは、レプリカはマークルツリーを交換して、複製されたキー範囲の同期していない部分を特定します。マークルツリーは階層的なハッシュ検証です。2つのレプリカ間でキー空間全体のハッシュが同じでない場合、同期していないキーが特定されるまで、複製されたキー空間のより小さな部分のハッシュを交換します。このアプローチにより、ほとんどが類似したデータを含むレプリカ間の不要なデータ転送が削減されます
  12. ^ Kilian, J. (1995). 「改良された効率的な議論」(PDF) .暗号学の進歩 — CRYPT0' 95.コンピュータサイエンス講義ノート. 第963巻. pp.  311– 324. doi : 10.1007/3-540-44750-4_25 . ISBN 978-3-540-60221-7。
  13. ^ a b Laurie, B.; Langley, A.; Kasper, E. (2013年6月). 「証明書の透明性」 . IETF RFC6962. doi : 10.17487/ rfc6962
  14. ^エレナ・アンドリーバ、シャルル・ブイヤゲ、オール・ダンケルマン、ジョン・ケルシー（2009年1月）。「メルクル・ダムゴードを超えるハーディング、第二原像、トロイの木馬メッセージ攻撃」。暗号分野選択論。コンピュータサイエンス講義ノート。第5867巻。SAC。pp.  393– 414。doi : 10.1007 /978-3-642-05445-7_25。ISBN 978-3-642-05443-3。
  15. ^エレナ・アンドリーバ、シャルル・ブイヤゲ、ピエール＝アラン・フーク、ジョナサン・J・ホック、ジョン・ケルシー、アディ・シャミール、セバスチャン・ジマー (2008). 「ディザリングされたハッシュ関数に対する第2原像攻撃」。ナイジェル・スマート編『暗号学の進歩 - 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日閲覧。

さらに読む

「 https://en.wikipedia.org/w/index.php?title=Merkle_tree&oldid=1329495055」から取得