Kademlia
ノードIDとコンテンツのキーには160bitsのランダムな値を振る。アルゴリズム的に160bitsでないといけない理由はなく、単純に当時SHA-1が主流だったからこの長さになったんだろな 距離関数はIDとキーのXORをとった差分
利点1 : $ d(x,y)=d(y,x)より一方向性と対称性を持つ。Chordとかだと順方向と逆方向で距離が違って、単純に距離を測るだけでは本当に距離の近い$ k個を見つけることはできない 利点2 : The triangle property{$ d(x,y)+d(y,z)\geq d(x,z)}を持つ。
IDの頭文字を取ったPrefixをもとに二分木を生成し、それを経路表とする
各ノードについて、<IPアドレス, UDPポート, Node ID>の3つの情報を持つ
自分から$ 2^i \sim 2^{i+1}の範囲ごとにk-bucketなるバケットを持つ。なのでバケット数は最大で160個
バケット内には序列がある
動的にバケットを増やす場合、スタートは160bits全てをカバーする1つのk-bucketから始まり、リクエストかなんかでノードの情報を得るごとにそれをバケットにぶち込んでいく
https://scrapbox.io/files/617cd968fec602001dda854c.png
経路表の更新
あるノード情報を得た際...
そのノード情報をすでに持っていたらバケット内の最後尾に移す
そのノード情報が初耳だった場合...
該当するバケットが満タン（通常20ノード、以下$ k）でなければ最後尾に挿入する
該当するバケットが満タンだった場合、そのバケットの先頭のノードにPINGを送信する...
PINGへの応答がなかった場合、そのノード情報はバケットから削除し、新しく得たノード情報を最後尾に挿入する
PINGへの応答があった場合...
そのバケットが自分自身を含んでいたらバケットを1桁多いPrefixで分割する
そのバケットが自分自身を含んでいなかったら新しいノード情報は破棄する。
つまり大量のノードが生成されても自分に近くない限り破棄されていくため、DoS耐性がある また、古いノードほどオンラインで居続ける可能性が高い(Gnutellaの調査)のでPINGに反応があったら最後尾に移している
https://scrapbox.io/files/61ee0838f724690021f0f416.png
IPFSの場合10分に一度更新される
経路表における例外処理
ツリーに偏りができた際の処理。
例 : prefix 001のノードがすでに$ k個以上存在するネットワークの中で初めてprefix 000のノード$ uが参加したとする。$ uのツリーにおいてprefix 001のバケットには当然$ k個のノードしか存在し得ないと同時にまだそこまで多くのバケットが生成されていない状態のため、既にprefix 001のバケットに存在する$ k個のノードより遥かに$ uのnode IDに近いはずのノード情報が破棄される可能性が高くなる。
その解決策として提示されているのが、上の例の状態で新たなPrefix 001のノード情報を受け取った際、そのIDが$ uのIDに近い$ k個以内であればバケットを分割するという例外処理である。
ツリーが生成され始めたばかりの時点でこの例外処理を適用させると後に不要になるであろう大量のバケット分割が行われてしまうため、ある程度ツリーが成熟し、十分なノード情報を得てからこの処理を適用した方が良さそう
隣のPrefixでより近いノードを見つけたらバケット分割する代わりに一番遠いノード情報破棄して新しいのを保存するとかではダメなのか？
経路表は対称でないといけない
Kademliaのルーティング・テーブルの特徴は、その対称性で、ノードAのルーティング・テーブルにノードBが入っている場合は、ノードBのルーティング・テーブルにも通常ノードAが入っていることです（厳密にはkの大きさにより入らないこともある）。
これによって、ルーティング・テーブルの更新はメッセージの受信によって行うことができ効率が良いとされています。すなわち、ルーティング・テーブルの更新のための特別なメッセージを必要としません。
XOR metricのとこを読む必要がある
Every node with prefix 001 would have an empty k-bucket into which $ ushould be inserted, yet $ u's bucket refresh would only notify $ kof the node.
これの何が問題なのかわからない
When $ urefreshes the split buckets, all nodes with prefix 001 will learn about it.
$ uを知る全てのノードがリフレッシュ通知を受ける必要はあるのか？
k-bucketのリフレッシュ
ほとんどのケースではRPCを伝播する過程で経路表が更新されていくが、ノードのIDに偏りがある場合などにしばらくある範囲のIDを持つノードの情報が入ってこないことがある。1時間全く更新されなかったk-bucketがある場合、ノードはそのk-bucketのIDの範囲ないからランダムにIDを選び検索をかける。
これ絶対最適化の余地ある
Kademliaには4つのRPCがある。通信はUDPで行う PING (NODE_ID)
ノードがオンラインかどうか確認する。
STORE (NODE_ID, KEY, VALUE)
あるノードに<key, value>のペアを格納する。
FIND_NODE (NODE_ID)
引数のノードまたはそれに近いノードを見つける。
このRPCを受け取ったノードは引数のIDに最も近い$ k個のノードの<IPアドレス, UDPポート, Node ID>を返す。
FIND_VALUE(NODE_ID, KEY)
基本的にはFIND_NODEと同じ動作だが、このRPCを受け取ったノードが引数のキーに対応する値を持っていたらそれを返す。
上の4つのRPC全てにおいて、各RPCはIDを持つ。これにより（頑健なハッシュ関数を使っている限り）アドレス偽造への耐性がつく。SHA-1は使っちゃダメ！
またPINGの役割は他のRPCでも果たすことができる
Kademliaは検索、参加、値保存、キー再発行の4種類の手続きを持つ
検索手続き
まず、自分のバケットの中で、検索したいノードもしくはキーのIDに最も近い$ a個（通常3つ）のノードにFIND_*を送る。その返答で得たノードのうち最も近い$ k個のリストを$ lとする。
以下をループする
$ lの中から再び最も近い$ a個のノードにFIND_*を送る
ある一定時間が経ったら非同期に上のRPCで得たノードで$ lを更新する
ループの終了条件は...
$ l内の$ k個全てが初期の状態から更新された場合（つまり$ lが完全に新しいものになった場合）
もしくはそのループで$ lを全く更新できなかった場合
この場合、まだ$ l内でまだRPCを送ってないノード全てにFIND_*を送ったのち処理終了
参加手続き
この手続きは論文内で明記されておらず、実装や記事によってバラバラである。以下はその一例
新規ノードは唯一知っている既存ノードに自分自身を検索させる。その既存ノードはこの際自分の経路表に新規ノードを追加する
上の検索で得た$ k個のノードにPINGを送信し、返答があれば経路表に追加していく。
PINGを受けた各ノードは新規ノードを経路表に追加し、自分の持つ値のうちキーが自分のバケット内のどのノードよりも新規ノードに近いもののみ新規ノードにSTOREする
以下はこの記事の著者が独自に考案した新規ノードの経路表構築手順 現時点で存在するk-bucketそれぞれに対して以下を行う
あるバケットの範囲からランダムなIDを生成し、そのIDを検索にかける
検索によって得た$ k個のノードをそのバケットにぶち込む
これによって経路表がより充実する
値保存手続き
オリジナル発行者のノードはそのキーを検索にかける（lookupする）
lookupで得た$ k個のノードにSTOREを送信する
Republish手続き
レプリケーションを受けた値を持つノードは1時間ごとに値保存手続きを行い、その時点でキーに最も近い$ k個にSTOREを送る（なぜかここも論文ではめっちゃ端折られてる）
自分がすでに持っているキーのSTOREリクエストを受け取ったら、それはrepublishであり、その時点で他のキーに近い$ k-1個にもSTOREが送られていることがわかる。なのでそのキーに対しては1時間republishはしない。つまりしばらくの間は$ k個のノードのうち1つのノードのみがその値に対するrepublishを行う。
オリジナル発行者のノードは24時間ごとにrepublishを行う
key-valueのキャッシュ
FIND_VALUEで値を取得した際、リクエストを送ったノードは、RPCを送ったノードのうち最もキーのIDに近く、かつkey-valueを返さなかったノードにSTOREを送信してキャッシュ代わりにする
key-valueの期限切れ
全てのkey-valueは一定時間で期限切れし、ネットワークから削除される
期限切れの時間は現在のノードとそのkeyに最も近いノードのIDの差に指数関数的に反比例して短くなっていく
脆弱性
Kademliaの場合、ターゲットノードがpublishされる前にそのノードIDに近いIDを持っていれば、ブートストラップ時からターゲットに攻撃することができる。IDをランダムにアサインすることで防げるかつ、攻撃者が経路表に自分のノードを入れ込めない限りこの攻撃は難しい。後者の対策を破るためにブートストラップ直後のネットワークを狙うケースが多い
Kademliaの場合生存時間の長いノードを優先するためこの攻撃をかけることは難しい
悪意あるノードがネットワーク内の他のノードが持つIDを自分のものだと主張してネットワークに矛盾を起こす。通常この方法は長く存在するノードを正統とすることで防がれる
実装
定数
a...検索手続きの際（FIND_*）に使われる、一度にRPCを送るノードの数。並列処理の定数とも言える。通常は3
k...一つのバケットに入るノードの数。通常は20
B...キーの長さ。論文内では定数というよりハッシュ関数としてSHA-1が使われてるので自動的に160bitsになっていたが必ずしも160bitsである必要はない
tExpire...key-valueの有効期限。論文内のTTLは24時間（86400秒）
tRefresh...k-bucketのリフレッシュ間隔。論文内では1時間（3600秒）
tReplicate...レプリケートされたkey-valueをRepublishする間隔。論文内では1時間
tRepublish...key-valueのオリジナル発行者がRepublishする間隔。論文内では24時間
tExpireとtRepublishが同じ間隔だとRepublishと同じタイミングでExpireしてしまうので、tExpireは86410秒が下の文献では推奨されている。
The fact that tRepublish and tExpire are equal introduces a race condition. The STORE for the data being published may arrive at the node just after it has been expired, so that it will actually be necessary to put the data on the wire. A sensible implementation would have tExpire significantly longer than tRepublish. Experience suggests that tExpire=86410 would be sufficient.