カデムリア

Kademliaは、 2002年にPetar MaymounkovとDavid Mazièresによって設計された、分散型ピアツーピアコンピュータネットワーク用の分散ハッシュテーブルです。 ^{[1] [2]}これは、ネットワークの構造とノード検索による情報交換を指定します。KademliaノードはUDPを使用して相互に通信します。仮想ネットワークまたはオーバーレイネットワークは、参加ノードによって形成されます。各ノードは、番号またはノードIDによって識別されます。ノードIDは識別として機能するだけでなく、KademliaアルゴリズムはノードIDを使用して値（通常はファイルハッシュまたはキーワード）を検索します。

特定のキーに関連付けられた値を検索するために、アルゴリズムはネットワークをいくつかのステップで探索します。各ステップでは、接続されたノードが値を返すか、より近いノードが見つからなくなるまで、キーに近いノードを検索します。これは非常に効率的です。他の多くのDHTと同様に、Kademlia は検索中にシステム内のノード 全体からノードのみに接続します。${\displaystyle O(\log n)}$${\displaystyle n}$

さらなる利点は、特に分散構造にあり、サービス拒否攻撃に対する耐性が高まります。ノードのセット全体がフラッディングされた場合でも、ネットワークはこれらの「穴」の周囲にネットワークを編み込むことで回復するため、ネットワークの可用性への影響は限定的です。

I2PのKademlia実装は、Sybil攻撃などのKademliaの脆弱性を軽減するように変更されています。^[3]

ピアツーピア ネットワークは、設計上、ノードで構成されています。これらのノードが通信や情報の検索に使用するプロトコルは、時間の経過とともに効率化されています。Napster などの第 1 世代のピアツーピア ファイル共有ネットワークでは、ネットワーク上の検索を調整するために中央データベースに依存していました。Gnutella などの第 2 世代のピアツーピア ネットワークでは、ネットワーク上のすべてのノードを検索して、フラッディングを使用してファイルを検索していました。Bittorrent などの第 3 世代のピアツーピア ネットワークでは、ネットワーク内のファイルの検索に分散ハッシュ テーブルを使用します。分散ハッシュ テーブルには、ネットワーク全体のリソースの場所が格納されます。

Kademlia は、2 つのノード間の「距離」計算を使用します。この距離は、 2 つのノード ID の排他的論理和 (XOR)として計算され、結果は符号なし整数になります。キーとノード ID は同じ形式と長さであるため、それらの間の距離はまったく同じ方法で計算できます。ノード ID は通常、特定のノードに対して一意となるように選択される大きな乱数です ( UUIDを参照)。たとえばドイツとオーストラリアなど、地理的に離れたノードが同様のランダム ノード ID を選択した場合は、「近隣」となることがあります。

XORが選択されたのは、すべてのノード ID 間の 距離関数として機能するためです。具体的には、次のようになります。

• ノードとノード自体の間の距離はゼロです
• 対称的である: AからBまでとBからAまでの計算された「距離」は同じである
• これは三角不等式に従います。A、B、C が三角形の頂点(点)である場合、A から B までの距離は、A から C までの距離と C から B までの距離の合計よりも短くなります (または等しくなります)。

これら3つの条件は、 XORが「実際の」距離関数の本質的で重要な特徴をすべて捉え、しかも計算が安価で簡単であることを保証するのに十分です。 ^[1]

Kademlia 検索の各反復は、ターゲットに 1 ビットずつ近づきます。基本的なKademlia 検索アルゴリズムの複雑さはO(log ₂  (n))です。つまり、ノードを持つネットワークでは、そのノードを見つけるのに最大でステップ数がかかります。 ${\textstyle 2^{n}}$ ${\displaystyle n}$

^{固定サイズのルーティングテーブルは、元の論文[4]}の事前手続き版で提示され、その後のバージョンではいくつかの数学的証明にのみ使用されています。実際のKademlia実装では、固定サイズのルーティングテーブルはなく、動的にサイズが調整されるルーティングテーブルがあります。

Kademlia ルーティング テーブルは、ノード ID の各ビットのリストで構成されています (たとえば、ノード ID が 128 ビットで構成されている場合、ノードは 128 個のこのようなリストを保持します)。リスト内のすべてのエントリには、別のノードを見つけるために必要なデータが保持されます。各リストエントリのデータは、通常、別のノードのIP アドレス、ポート、およびノー​​ド IDです。すべてのリストは、ノードからの特定の距離に対応しています。n^番目の リストに入れることができるノードは、ノードの ID とは異なる n^番目のビットを持っている必要があります。つまり、候補 ID の最初の n-1 ビットは、ノードの ID のビットと一致している必要があります。つまり、ネットワーク内のノードの 1/2 は遠く離れた候補であるため、最初のリストを作成するのは非常に簡単です。次のリストでは、ネットワーク内のノードの 1/4 のみを使用できます (最初のリストより 1 ビット近く)。

128 ビットの ID を使用すると、ネットワーク内のすべてのノードは、ビットごとに 1 つの特定の距離、つまり 128 の異なる距離のいずれかで他のノードを分類します。

ネットワーク上でノードが検出されると、それらはリストに追加されます。これには、保存および取得操作や、他のノードがキーを見つけるのを支援することも含まれます。検出されたすべてのノードは、リストに追加されるかどうか検討されます。したがって、ノードがネットワークについて持つ知識は非常に動的です。これにより、ネットワークは常に最新の状態に保たれ、障害や攻撃に対する耐性が高まります。

Kademlia の文献では、リストはk バケットと呼ばれます。kは20 のようなシステム全体の数字です。すべてのkバケットは、内部に最大k 個のエントリを持つリストです。つまり、k=20 のネットワークの場合、各ノードには、特定のビット (それ自体からの特定の距離) に対して最大 20 個のノードを含むリスト があります。

各k バケットの可能なノードは急速に減少するため (非常に近いノードはほとんどないため)、下位ビットのk バケットはネットワークのそのセクション内のすべてのノードを完全にマップします。可能な ID の数はノードの集団よりもはるかに大きいため、非常に短い距離に対応するkバケットの一部は空のままになります。

右のシンプルなネットワークを考えてみましょう。ネットワークのサイズは 2^3 または最大 8 つのキーとノードです。参加しているノードは 7 つあり、下部に小さな円があります。検討中のノードは、黒で示されたノード 6 (バイナリ 110) です。このネットワークの各ノードには 3 つのk バケットがあります。ノード 0、1、2 (バイナリ 000、001、010) は、最も遠いk バケットの候補です。ノード 3 (バイナリ 011、図示せず) は、ネットワークに参加していません。中央のk バケットには、ノード 4 と 5 (バイナリ 100 と 101) が配置されます。最後に、3 番目のk バケットにはノード 7 (バイナリ 111) のみを含めることができます。3 つのk バケットはそれぞれ灰色の円で囲まれています。kバケットのサイズが2 だった場合、最も遠い2 バケットには 3 つのノードのうち 2 つしか含めることができません。たとえば、ノード 6 の最も遠い 2 バケットにノード 1 と 2 がある場合、ノード 0 の場所 (IP アドレス) を見つけるには、これらのノードにノード ID ルックアップを要求する必要があります。各ノードは近隣をよく知っており、遠く離れたいくつかのノードと接続しているため、遠く離れた他のノードを見つけるのに役立ちます。

ネットワーク内で長期間接続されているノードは、将来も長期間接続されたままになる可能性が高いことが知られています。^{[5] [6]}この統計分布により、Kademliaは長期間接続されているノードを選択してkバケットに保存します。これにより、将来のある時点で有効なノードの数が増加するため、より安定したネットワークが実現します。

k-bucketがいっぱいで、そのk-bucketに新しいノードが検出されると、 k-bucket内で最も最近確認されていないノードに対してPING が実行されます。ノードがまだ生きていることが判明した場合、新しいノードはセカンダリ リスト (置換キャッシュ) に配置されます。置換キャッシュは、 k-bucket内のノードが応答を停止した場合にのみ使用されます。つまり、新しいノードは、古いノードが消えた場合にのみ使用されます。

Kademlia には 4 つのメッセージがあります。

• PING — ノードがまだ動作しているかどうかを確認するために使用されます。
• STORE — 1 つのノードに (キー、値) ペアを保存します。
• FIND_NODE — リクエストの受信者は、要求されたキーに最も近い k 個のノードを自身のバケット内で返します。
• FIND_VALUE — FIND_NODE と同じですが、リクエストの受信者がストア内に要求されたキーを持っている場合は、対応する値を返します。

各RPCメッセージには、イニシエーターからのランダムな値が含まれます。これにより、応答が受信されたときに、それが以前に送信された要求に対応することが保証されます (マジック クッキーを参照)。

ノード検索は非同期で実行できます。同時検索の数は α で示され、通常は 3 です。ノードは、自身のk バケット内の目的のキーに最も近い α 個のノードにクエリを実行して、FIND_NODE 要求を開始します。これらの受信ノードは要求を受信すると、自身のk バケットを調べ、目的のキーに最も近いk個のノードを返します。要求者は、受信した結果 (ノード ID) で結果リストを更新し、クエリに応答する最良のk個の結果 (検索されたキーに近いk個のノード) を保持します。次に、要求者はこれらの最良のk 個の結果を選択して要求を発行し、このプロセスを何度も繰り返します。各ノードは自身の周囲について他のどのノードよりもよく知っているため、受信される結果は、検索されたキーにどんどん近づいている他のノードになります。この繰り返しは、以前の最良の結果よりも近いノードが返されなくなるまで続きます。反復が停止すると、結果リスト内の最適な k 個のノードは、ネットワーク全体で目的のキーに最も近いノードになります。

ノード情報には、ラウンドトリップ時間(RTT) を追加できます。この情報は、参照されるノードごとに固有のタイムアウトを選択するために使用されます。クエリがタイムアウトすると、別のクエリを開始できますが、同時に α クエリを超えることはありません。

情報はキーにマッピングすることで検索されます。マップには通常ハッシュが使用されます。ストアノードには以前の STORE メッセージによる情報があります。値の検索はキーに最も近いノードの検索と同じ手順に従いますが、ノードのストアに要求された値があり、その値を返すと検索が終了します。

値は複数のノード (k 個) に保存され、ノードが入れ替わっても、一部のノードで値を利用できるようになります。定期的に、値を保存するノードはネットワークを探索し、キー値の近くにある k 個のノードを見つけて、それらのノードに値を複製します。これにより、消えたノードが補われます。

また、リクエスト数が多い可能性のある人気の値については、リトリーバーがこの値を k 個の最も近いノードの外側の近くのノードに保存することで、保存ノードの負荷が軽減されます。この新しい保存方法はキャッシュと呼ばれます。このように、リクエストの量に応じて、値はキーからどんどん離れた場所に保存されます。これにより、人気の検索で保存場所をより迅速に見つけることができます。値はキーから離れたノードから返されるため、潜在的な「ホット スポット」が軽減されます。キャッシュ ノードは、キーからの距離に応じて、一定時間後に値を削除します。

一部の実装 (例: Kad ) には、レプリケーションもキャッシュもありません。その目的は、システムから古い情報をすばやく削除することです。ファイルを提供しているノードは、ネットワーク上の情報を定期的に更新します (FIND_NODE および STORE メッセージを実行します)。ファイルを持つすべてのノードがオフラインになると、誰もその値 (ソースとキーワード) を更新しなくなり、情報は最終的にネットワークから消えてしまいます。

ネットに参加したいノードは、まずブートストラッププロセスを実行する必要があります。この段階では、参加ノードは、Kademlia ネットワークにすでに参加している別のノード (ブートストラップ ノード (ユーザーから取得、または保存されたリストから取得)) のIP アドレスとポートを知る必要があります。参加ノードがまだネットワークに参加していない場合、ランダムID 番号を計算します。この ID 番号は非常に大きなランダム番号であるため、他のノードにまだ割り当てられていない可能性が極めて高くなります。この ID は、ネットワークを離れるまで使用されます。

参加ノードは、ブートストラップ ノードをそのk-bucketsの 1 つに挿入します。参加ノードは、次に、ブートストラップ ノード (参加ノードが認識している唯一の他のノード) に対して、自身の ID のノード検索を実行します。「自己検索」により、他のノードのk-bucketsに新しいノード ID が設定され、参加ノードのk-bucketsに、参加ノードとブートストラップ ノード間のパスにあるノードが設定されます。その後、参加ノードは、ブートストラップ ノードが含まれるk-bucketsよりも遠いすべてのk-buckets を更新します。この更新は、そのk-buckets の範囲内にあるランダム キーの検索にすぎません。

最初は、ノードには 1 つのk-bucketがあります。k -bucketがいっぱいになると、分割できます。分割は、k-bucket内のノードの範囲がノード自身の ID (バイナリ ツリーの左と右の値) にまたがる場合に発生します。Kademlia は、1 つの「最も近いノード」k-bucketに対してもこのルールを緩和します。これは、通常、1 つの単一のバケットがこのノードに最も近いすべてのノードの距離に対応し、それらのノードがk を超える場合があり、それらすべてを把握する必要があるためです。ノードの近くに、非常に不均衡なバイナリ サブツリーが存在することが判明する場合があります。k が 20 で、プレフィックスが "xxx0011....." のノードが 21 個以上あり、新しいノードが "xxx0000 11001 " である場合、新しいノードには他の 21 個以上のノード用の複数のk-bucket を含めることができます。これは、ネットワークが最も近い領域内のすべてのノードを把握していることを保証するためです。

Kademlia は、距離を定義するためにXOR メトリックを使用します。2 つのノード ID またはノード ID とキーが XOR され、その結果がそれらの間の距離になります。各ビットについて、XOR 関数は 2 つのビットが等しい場合は 0 を返し、2 つのビットが異なる場合は 1 を返します。XOR メトリックの距離は三角形の不等式を満たします。A、B、C が三角形の頂点(ポイント) である場合、A から B までの距離は、A から C までの距離と C から B までの距離の合計よりも短い (または等しい) です。

XORメトリックにより、 Kademlia はルーティング テーブルを 1 ビットを超えて拡張できます。ビットのグループはk バケットに配置できます。ビットのグループはプレフィックスと呼ばれます。mビットのプレフィックスの場合、2 ^m -1 個のk バケットがあります。不足しているk バケットは、ノード ID を含むルーティング ツリーのさらなる拡張です。mビットのプレフィックスにより、最大検索回数がlog ₂ nからlog _{2 ^m} nに減少します。これらは最大値であり、平均値ははるかに小さくなるため、プレフィックスだけでなく、ターゲット キーとより多くのビットを共有するk バケット内のノードが見つかる可能性が高くなります。

ノードは、 eMuleで使用されるKad ネットワークのように、ルーティング テーブルでプレフィックスの混合を使用できます。^[要出典] Kademlia ネットワークは、ルーティング テーブルの実装が異種である可能性もありますが、ルックアップの分析が複雑になります。

XOR メトリックは Kademlia を理解するためには必要ありませんが、プロトコルの分析には不可欠です。XOR 演算はアーベル群を形成し、閉じた分析を可能にします。他の DHT プロトコルとアルゴリズムでは、ネットワークの動作と正確性を予測するために、シミュレーションまたは複雑な形式分析が必要です。ビットのグループをルーティング情報として使用すると、アルゴリズムも簡素化されます。

アルゴリズムを分析するには、 ID を持つノードの Kademlia ネットワークを考えます。各 ID は長さ の文字列で、0 と 1 のみで構成されています。これはトライとしてモデル化でき、各リーフはノードを表し、ルートからリーフへのラベル付きパスはその ID を表します。ノード について、長さ のプレフィックスを共有するノード (ID) の集合を とします。すると、 の- 番目のバケットを埋めることは、リーフ から、 から一様にランダムに選択されたリーフ (ID)へのポインタを追加することとしてモデル化できます。したがって、ルーティングは、各ステップが可能な限りターゲット ID に向かうように、つまり貪欲な方法で、これらのポインタに沿ってリーフ間をジャンプすることと見なすことができます。 ${\displaystyle n}$${\displaystyle x_{1},\ldots ,x_{n}}$${\displaystyle d}$${\displaystyle x\in \{x_{1},\ldots ,x_{n}\}}$${\displaystyle {\mathcal {D}}_{i}(x)}$${\displaystyle x}$${\displaystyle ディ}$${\displaystyle i}$${\displaystyle x}$${\displaystyle x}$${\displaystyle k}$${\displaystyle {\mathcal {D}}_{i}(x)}$

を葉からターゲットID まで移動するために必要なジャンプの数とします。 がから決定論的に選択されると仮定すると、次のことが証明されています。 ${\displaystyle T_{xy}}$${\displaystyle x}$${\displaystyle y}$${\displaystyle x_{1},\ldots ,x_{n}}$${\displaystyle \{0,1\}^{d}}$

${\displaystyle \sup _{x_{1},\ldots ,x_{n}}\,\sup _{x\in \{x_{1},\ldots ,x_{n}\}}\,\sup _{y\in \{0,1\}^{d}}\mathbb {E} [T_{xy}]\leq (1+o(1)){\frac {\log n}{H_{k}}},}$

ここで は- 番目の調和数です。 であるため、が大きい場合、は約 によって上方から制限されますが、ID とターゲットが選択されます。^[7]これは、Kademlia ではターゲットノードの検索でノードのみがアクセスされるという直感を正当化します。 ${\displaystyle H_{k}}$${\displaystyle k}$${\displaystyle H_{k}/\log k\to 1}$${\displaystyle k\to \infty }$${\displaystyle k}$${\displaystyle \mathbb {E} T_{xy}}$${\displaystyle \log_{k}n}$${\displaystyle O(\log n)}$

モデルを実際のKademliaネットワークに近づけるために、は から置換なしで一様にランダムに選択されると仮定することもできます。すると、すべてのおよびに対して、 ${\displaystyle x_{1},\ldots ,x_{n}}$${\displaystyle \{0,1\}^{d}}$${\displaystyle x\in \{x_{1},\ldots ,x_{n}\}}$${\displaystyle y\in \{0,1\}^{d}}$

${\displaystyle {\begin{aligned}&T_{xy}{\xrightarrow {p}}{\frac {\log n}{c_{k}}},\\&\mathbb {E} [T_{xy}]\to {\frac {\log n}{c_{k}}},\end{aligned}}}$

ここで はとのみに依存する定数です。したがって、 が大きい場合、は に近い定数に収束します。これは、ターゲットノードを検索する際に接触する必要があるノードの数が実際には平均であることを意味します。^[8]${\displaystyle c_{k}}$${\displaystyle k}$${\displaystyle c_{k}/H_{k}\to 1}$${\displaystyle k\to \infty }$${\displaystyle k}$${\displaystyle \mathbb {E} T_{xy}/\log _{k}n}$${\displaystyle 1}$${\displaystyle \Theta (\log n)}$

Kademlia はファイル共有ネットワークで使用されます。Kademlia キーワード検索を行うことで、ファイル共有ネットワーク内の情報を検索し、ダウンロードすることができます。既存のファイルのインデックスを保存する中央インスタンスがないため、このタスクはすべてのクライアント間で均等に分割されます。ノードがファイルを共有する場合、ファイルの内容を処理し、そこからファイル共有ネットワーク内でこのファイルを識別する番号 (ハッシュ) を計算します。ファイル ハッシュとノード ID は同じ長さであるため、クライアントは XOR 距離関数を使用して、ID がハッシュに近い複数のノードを検索し、それらのノードに、実装定義の方法で発行者の IP アドレスを保存するように指示することができます。したがって、ファイル ハッシュに最も近い ID を持つノードには、このファイルのピア/発行者の IP アドレスのリストがあり、クライアントは実装定義の方法でそこからファイルをダウンロードできます。

この発行元からファイルをダウンロードしたいクライアントは、発行元の IP アドレス (発行元は多数存在する可能性があります) を知る必要はなく、ファイルのハッシュだけを知る必要があります。検索クライアントは、Kademlia を使用して、ファイル ハッシュとの距離が最も小さい ID を持つノードをネットワークで検索し、そのノードに格納されているソース リストを取得します。

キーは多くの値に対応できるため (たとえば、同じファイルの多くのソース)、各格納ノードは異なる情報を持つ可能性があります。次に、キーに近いすべての k 個のノードからソースが要求されます (k はバケットのサイズ)。

ファイル ハッシュは通常、他の場所にある特別に形成されたインターネットマグネット リンクから取得されるか、他のソースから取得されたインデックス ファイル内に含まれています。

ファイル名の検索は、キーワードを使用して実装されます。ファイル名は、構成語に分割されます。これらの各キーワードはハッシュ化され、対応するファイル名とファイル ハッシュとともにネットワークに保存されます。検索では、キーワードの 1 つを選択し、そのキーワード ハッシュに最も近い ID を持つノードに接続し、キーワードを含むファイル名のリストを取得します。リスト内のすべてのファイル名にはハッシュが添付されているため、選択したファイルを通常の方法で取得できます。

Kademliaアルゴリズムを使用するパブリック ネットワーク(これらのネットワークは互いに互換性がありません):

• I2P :匿名オーバーレイネットワーク層。^[9]
• Kad ネットワーク: もともとeDonkey ネットワークのサーバーベースのアーキテクチャを置き換えるためにeMuleコミュニティによって開発されました。
• イーサリアム：イーサリアムブロックチェーンネットワークスタックのノード検出プロトコルは、Kademliaのわずかに修正された実装に基づいています。^[10]
• Overnet : KadC では、Kademlia を扱うための C ライブラリが利用可能です。(Overnet の開発は中止されています)
• メインライン DHT :トラッカーレス トレント用の、Kademlia アルゴリズムの実装に基づいたBitTorrent用の DHT 。
• Osiris (全バージョン): 分散型および匿名の Web ポータルを管理するために使用されます。
• Retroshare : 安全な VOIP、インスタント メッセージング、ファイル転送などを備えた F2F 分散型通信プラットフォーム。
• Tox : 完全に分散されたメッセージング、VoIP、ビデオチャットプラットフォーム
• Gnutella DHT: 元々はLimeWire ^{[11] [12]}がGnutellaプロトコルを拡張して代替ファイルの場所を見つけるために考案したもので、現在は他のgnutellaクライアントでも使用されています。^[13]
• IPFS : libp2pをベースにしたピアツーピア分散ファイルシステム。^[14]
• TeleHash：Kademliaを使用してパーティ間の直接接続を解決するメッシュネットワークプロトコル。^[15]
• iMule: I2P用のファイル共有 ユーティリティ ソフトウェア。
• OpenDHT: Jamiらが使用するKademliaの実装を提供するライブラリ。 ^[16]
• GNUnet : 安全で分散化されプライバシーを保護する分散アプリケーションを構築するための代替ネットワークスタック。R5Nと呼ばれるKademliaのランダム化バージョンを使用します。^[17]
• Dat : Hypercoreプロトコルに基づいたピアツーピアのファイル共有ツール^{[要出典] [要説明] 。 [18]}

• コンテンツアドレスネットワーク
• Chord（ピアツーピア）
• タペストリー (DHT)
• ペストリー（DHT）
• コーデ

• Xlattice プロジェクトの Kademlia 仕様と定義。