Distributed Hash Table (DHT) and Kademlia

Traditional Database:
  Client → Server → Database[key] → value

DHT:
  Client → Node_1 → Node_7 → Node_42 → value
          (each hop gets closer to the key's location)

distance(A, B) = A XOR B

Node A:  1010 1100
Node B:  1010 0011
         ─────────
XOR:     0000 1111  = distance 15

Node A:  1010 1100
Node C:  1010 1101
         ─────────
XOR:     0000 0001  = distance 1

Node C is much closer to A than B

If A XOR B has its highest set bit at position i:
  - A and B share their first (256-i) bits
  - They diverge starting at bit i

A: 1010 1100 0000 0000 ...
B: 1010 1000 0000 0000 ...
         ^
         First differing bit at position 5

XOR = 0000 0100 ... = 4 (2^2, but position 5 from left in 8-bit view)

                    Root
                   /    \
                  0      1
                 / \    / \
                00  01 10  11
               /\  /\ /\  /\
              ... ... ... ...

Node 1010... follows path: right → left → right → left → ...

From Node A's perspective (ID: 0...):

Subtree 0: All nodes starting with 1... (half the network)
           XOR distance: 1xxx... (very far)

Subtree 1: All nodes starting with 01... (quarter of network)
           XOR distance: 01xx... (far)

Subtree 2: All nodes starting with 001... (eighth of network)
           XOR distance: 001x... (medium)

...and so on

1. Calculate XOR distance to determine target bucket
2. If bucket has < k entries:
   → Add new contact
3. If bucket is full:
   → Ping least-recently-seen contact
   → If no response: replace with new contact
   → If responds: move to end of list, discard new contact

Node ID: 00101... (256 bits)

Bucket 255: [Nodes starting with 1...]     ← Far (half the network)
Bucket 254: [Nodes starting with 01...]    ← Far-ish
Bucket 253: [Nodes starting with 001...]   ← Medium
...
Bucket 2:   [Nodes starting with 00100...] ← Close
Bucket 1:   [Nodes starting with 001010...]← Very close
Bucket 0:   [Nodes starting with 0010100...]← Closest

Each bucket holds up to k=20 nodes

FIND_NODE(target):
  1. Initialize:
     - shortlist = k closest nodes from local routing table
     - queried = empty set
     - closest_seen = infinity

  2. Loop:
     - Select alpha (3) nodes from shortlist not yet queried
     - Send parallel FIND_NODE RPCs to selected nodes
     - Mark nodes as queried

  3. Process responses:
     - Each response contains k closest nodes the responder knows
     - Add new nodes to shortlist
     - Update closest_seen if closer node found

  4. Termination:
     - If no node closer than closest_seen found in a round
     - Query all remaining nodes in shortlist within k closest
     - Return k closest nodes seen

Start: Node A (ID: 0000...)
Target: 1111...
Initial distance: 1111... XOR 0000... = 1111... (very large)

Hop 1: A asks bucket 255 → gets node B (ID: 1000...)
       New distance: 1111... XOR 1000... = 0111... (halved!)

Hop 2: B asks its bucket → gets node C (ID: 1100...)
       New distance: 1111... XOR 1100... = 0011... (halved again!)

Hop 3: C asks its bucket → gets node D (ID: 1110...)
       Distance: 0001...

Hop 4: D asks its bucket → gets node E (ID: 1111...)
       Distance: 0000... (found!)

FIND_VALUE(key):
  1. Compute target = hash(key)

  2. Perform iterative lookup (like FIND_NODE)

  3. At each hop:
     - If node has value for key → return value immediately
     - Otherwise → return k closest nodes (continue lookup)

  4. If lookup completes without finding value:
     - Store value at closest node found (caching)
     - Return "not found"

Alpha = 1: Sequential lookups
  A → B → C → D (slow, but minimal bandwidth)

Alpha = 3: Parallel lookups
  A → B ─┐
  A → C ─┼→ best response → continue
  A → D ─┘
  (faster, more bandwidth)

JOIN(bootstrap_nodes):
  1. Generate node ID:
     - node_id = SHA256(public_key)
     - This binds ID to cryptographic identity

  2. Contact bootstrap node:
     - Send PING to verify connectivity
     - Receive initial contacts

  3. Self-lookup:
     - Perform FIND_NODE(own_node_id)
     - This populates routing table with nearby nodes

  4. Bucket refresh:
     - For each bucket, FIND_NODE(random_id_in_bucket)
     - Discovers nodes at all distance ranges

  5. Announce presence:
     - Stored data will be replicated to us automatically
     - Other lookups will discover us

STORE(key, value):
  1. Compute storage location:
     - target = hash(key)  // 256-bit ID

  2. Find storage nodes:
     - nodes = FIND_NODE(target)
     - Select k closest nodes to target

  3. Store value:
     - Send STORE RPC to selected nodes
     - Each stores (key, value, timestamp, TTL)

  4. Replication:
     - Value stored on k nodes for redundancy
     - Nodes periodically replicate to neighbors

REFRESH():
  Every hour, for each bucket:
    1. If no lookup touched this bucket recently:
       - random_id = generate ID in bucket's range
       - FIND_NODE(random_id)

    2. Ping least-recently-seen nodes:
       - If no response → remove from bucket
       - If response → move to end of bucket

REPUBLISH():
  Every hour:
    1. For each locally stored (key, value):
       - If originally_stored_by_us OR near_expiration:
         - STORE(key, value) to refresh

    2. Replicate to new close neighbors:
       - If new node joined closer to key:
         - Send them the data

Normal:
  Victim ──► Honest Node A
         ──► Honest Node B
         ──► Honest Node C

Eclipsed:
  Victim ──► Attacker Node 1 ──► Attacker controls
         ──► Attacker Node 2 ──► all information
         ──► Attacker Node 3 ──► victim receives

Honest network: 1000 nodes
Attacker adds: 10000 Sybil nodes

Result: Attacker controls 90% of routing table entries
        Attacker likely responsible for most keys

If attackers could choose IDs:
  - Position Sybil nodes near target key
  - Become responsible for any key they want
  - Intercept/modify stored data

node_id = SHA256(ed25519_public_key || creation_timestamp)

1. Node presents: (node_id, public_key, timestamp, signature)
2. Verifier checks:
   - node_id == SHA256(public_key || timestamp)
   - timestamp within acceptable window
   - signature valid

1. Client needs relay nodes for circuit
2. Query DHT for key: hash("relay:" || region || timestamp_bucket)
3. DHT returns list of available relays
4. Client selects relays for circuit building

Store key bundle:
  key = hash("keybundle:" || user_wallet_address)
  value = encrypted_and_signed_key_bundle
  STORE(key, value)

Fetch key bundle:
  key = hash("keybundle:" || recipient_wallet_address)
  bundle = FIND_VALUE(key)
  verify_signature(bundle)

Store encrypted media chunk:
  content_hash = SHA256(encrypted_chunk)
  storage_key = hash("media:" || content_hash)
  STORE(storage_key, encrypted_chunk)

Retrieve:
  storage_key = hash("media:" || known_content_hash)
  chunk = FIND_VALUE(storage_key)
  verify: SHA256(chunk) == content_hash

Lookup latency = hops * avg_rtt + processing_time

For 1M node network:
  - Hops: ~20
  - Avg RTT: 50ms (varies by geography)
  - Total: ~1 second typical

With alpha=3 parallelism:
  - Effective latency: ~300-500ms typical