Distributed Hash Table DHT

Chord Protocol

Based on consistent hashing, maintains a ring structure similar to a doubly linked list where nodes can join, transfer data, and exit.

Joining process:

1. Any new node (let’s call it A) needs to first establish a connection with any existing node in the DHT (let’s call it B)
2. A randomly generates a hash value as its own ID (for sufficiently large hash value spaces, the probability of identical IDs is negligible)
3. A finds its contact person on the ring by querying through B. In other words - find the “successor” (let’s call it C) and “predecessor” (let’s call it D) corresponding to its own ID, finding its predecessor and successor nodes
4. A needs to interact with C and D so that it becomes the predecessor of C and the successor of D

Kad

Kad uses an algorithm to map keys to a binary tree, where each key is a leaf of this binary tree. Before mapping, preprocessing is performed:

1. First represent the key in binary form
2. Shorten each key to its shortest unique prefix Each leaf uniquely corresponds to a binary prefix, facilitating XOR-based distance calculation between nodes After splitting subtrees from a particular node’s perspective, a K-bucket must be maintained (the routing table contains K elements) to record K nodes in the subtree

Joining process:

1. Any new node (let’s call it A) needs to first establish a connection with any existing node in the DHT (let’s call it B)
2. A randomly generates a hash value as its own ID (for sufficiently large hash value spaces, the probability of identical IDs is negligible)
3. A initiates a query request (protocol type FIND_NODE) to B, requesting its own ID (in simple terms, querying itself)
4. After B receives the request, (as mentioned above) it will first add A’s ID to one of its K-buckets. Then, according to the FIND_NODE protocol specification, B will find K nodes closest to A and return them to A
5. After A receives these K node IDs, it can begin initializing its own K-bucket (based solely on these ID values)
6. Then A will continue sending query requests (protocol type FIND_NODE) to the nodes just obtained, repeating this process recursively until A establishes a sufficiently detailed routing table

BEP-09 Protocol

This protocol enables downloading torrent files after obtaining many peer address information. Through the BEP-09 protocol, handshake and TCP connection establishment with peers allows resource downloads. After each block is downloaded, SHA1 values are calculated to verify integrity.