主にこのドキュメントの翻訳です。
Node Discovery Protocol v4
現在、メインで使われている。 v5もgethには入っている(起動時のフラグでonにできる)
- Kademlia likeなDHT(Distributed Hash Table)であるNode Discoveryプロトコル
Kademliaとはwikiより一部抜粋
Kademliaは分散 ピアツーピアコンピュータネットワークのための分散ハッシュテーブルである。
Kademliaはネットワーク構造およびノード検索による情報の送受信を規定している。KademliaのノードはUDPにより相互に通信を行う。
参加ノードにより仮想的なオーバーレイ・ネットワークが形成される。各ノードはノードIDと呼ばれる番号で管理されている。
ノードIDはノードの識別に用いるだけでなく、KademliaアルゴリズムではノードIDにより値を抽出するために使われる。
この値は通常ファイルのハッシュ値やキーワードである。実際には、ノードIDはファイルハッシュへの直接的なマッピングを与え、そのノードはファイルやリソースを取得する対象
ある値を検索する際、このアルゴリズムではそれに割り当てられたキーの情報が必要となり、ネットワークを数ステップかけて探索する。
各ステップにおいて、よりキーに近いノードが発見され、最終的に該当するノードが値を返すか、それ以上近いノードがない状態となる。
これは非常に効率が良く、他の多くの分散ハッシュテーブルのようにKademliaは nノードのシステムにおいて検索の間に合計O(log(n))ノードへの通信を行う。
ノードID
すべてのノードには、楕円曲線のsecp256k1の鍵である暗号識別情報があり、ノードの公開鍵は、その識別子または「ノードID」として機能する
2つのノードIDの間の「距離」は、ビット単位で排他的であるか、または公開鍵のハッシュとして数字とみなされます。
distance(n₁, n₂) = keccak256(n₁) XOR keccak256(n₂)
ノードテーブル
ディスカバリープロトコルのノードは、近隣の他のノードに関する情報を保持する。近隣ノードは、「k-buckets」で構成されるルーティングテーブルに格納される。各ノードは、自身との間の距離が2iから2i+1の間のノードをk-bucketに保持する。 (0 ≤ i < 256)
ノード探索プロトコルはk = 16を使う。つまり、すべてのk-bucketに最大16個のノードエントリを含む。エントリは、最後に見られた時間によってソートされる。最も最近に見られたノードは先頭になる。
新しいノードN1に遭遇するたびに、対応するバケットに挿入することができる。バケットがkエントリよりも少ない数を含む場合、N1を第1のエントリとして追加することができる。バケットが既にkエントリを含んでいる場合、バケット内の最も最近にみたノードN2は、pingパケットを送信することによって再確認し、N2から応答が受信されなければ死んだとみなされ、除去し、N1がバケットの前面に追加される。
k-Bucketとは
k個のデータしか入れないテーブル。n個以上になったらあふれた分を削除する
エンドポイントプルーフ
DNSアンプ攻撃を防ぐため、実装ではクエリの送信者がディスカバリープロトコルに参加していることを確認する必要がある。過去12時間以内にpingハッシュと一致する有効なpong応答を送信した場合、パケットの送信者は検証されたとみなされる。
再帰ルックアップ
「ルックアップ」は、最もkに近いノードをノードIDに位置付ける。
ルックアップイニシエータは、ターゲットを知っているα個の最も近いノードを選択することから始まる。イニシエータは、並行FindNodeパケットをそれらのノードに送信する。αはシステム全体の並列数として3とする。再帰的なステップでは、イニシエータはFindNodeを以前のクエリから学習したノードに再送信する。イニシエータがターゲットに最も近いと聞いたk個のノードのうち、まだクエリされておらず、それらにFindNodeを再送するというαを選ぶ。迅速に応答できないノードは、応答しない限り、 候補から除外されます。
もし。FindNodeクエリのラウンドで既に知っている最も近いものよりも近いノードを返すことに失敗した場合、イニシエータは、まだ問い合わせされていないk個の最も近いすべてのノードにfindノードを再送信する。ルックアップは、イニシエータが照会して、しっている最も近いk個のノードからの応答を得たときに終了する。
ワイヤプロトコル
ノード検出メッセージは、UDPデータグラムとして送信される。いずれのパケットの最大サイズも1280バイトである。
packet = packet-header || packet-data
すべてのパケットはヘッダで始まる：
packet-header = hash || signature || packet-type
hash = keccak256(signature || packet-type || packet-data)
signature = sign(packet-type || packet-data)
hashは同じUDPポート上で複数のプロトコルを実行する際のパケットフォーマットを認識するために存在する。他の目的を果たしません。
すべてのパケットは、ノードのIDキーによって署名される。signatureは、r・sそして「回復ID」vの値を連結した長さ65のバイト配列としてエンコードされる。
packet-typeはメッセージのタイプを定義する単一のバイト。有効なパケットタイプを以下に示す。ヘッダの後のデータは、パケットタイプに固有であり、RLPリストとして符号化される。EIP-8で定義しているように、実装はリスト内の追加要素とリスト後の追加データを無視する必要がある。
Pingパケット（0x01）
packet-data = [version, from, to, expiration]
version = 4
from = [sender-ip, sender-udp-port, sender-tcp-port]
to = [recipient-ip, recipient-udp-port, 0]
expirationフィールドは、U絶対時間のNIXタイムスタンプ。過去のタイムスタンプを含むパケットはの有効期限が切れているので実行されないかもしれない。
pingパケットが受信されると、受信者はpongパケットで応答する必要がある。また、送信者がノードテーブルに追加することも考えられる。
12時間以内に送信者との通信が行われなかった場合は、エンドポイントプルーフを受け取るためにpongに加えてpingを送信する必要がある。
pongパケット（0x02）
packet-data = [to, ping-hash, expiration]
Pongはpingへの応答。
ping-hashは対応するpingパケットのhashと等しくなければならない。実装は、最新のpingパケットのハッシュを含んでいない迷惑なpongパケットを無視しないといけない。
FindNodeパケット（0x03）
packet-data = [target, expiration]
FindNodeパケットは、targetの近くのノードに関する情報を要求する。targetは65バイトのsecp256k1公開鍵。FindNodeが受信されると、受信者は、ローカルテーブルにあるtargetに最も近い16ノードを含むNeighborsパケットを返信する必要がある。
DNSアンプ攻撃から保護するため、Neighbors応答は、FindNodeの送信者がエンドポイントプルーフ手順によって検証された場合にのみ送信する必要がある。
Neighborsパケット（0x04）
packet-data = [nodes, expiration]
nodes = [[ip, udp-port, tcp-port, node-id], ... ]
NeighborsはFindNodeへの返信。
既知の問題と実装に関するアドバイス
expirationフィールドはすべてのパケットに存在し、パケットの再送を防ぐ。絶対時間のタイムスタンプであるため、は正しく検証するためにノードの時計は正確でなけれならない。2016年のプロトコルのローンチ以来、ユーザーの時計に関連する接続の間違の問題について、無数の報告を受けている。
FindNodeの送信者は、受信者が最近の十分なpongを認識したかどうかを決して確かめることができないため、エンドポイントプルーフは不正確である。Gethは次のように処理する。受信者との通信が12時間以内に発生しなかった場合は、pingを送信して手順を開始する。相手側からのpingを待ってから返信し、FindNodeを送信する。