在 P2P 网络中，"网络发现"是一个看似平凡却致命的难题：新节点上线时没有任何关于谁才是"邻居"的中央目录。Kademlia 用「距离即路由」的简洁哲学解决了这个问题——通过将节点 ID 和数据键映射到同一度量空间，让每次查询都向目标"走近"一步。

6.2.1 节点发现问题：没有 DNS 的互联网

在中心化网络中，新设备通过 DNS 解析服务端域名，获得 IP 地址后建立连接。区块链网络的困境在于：

1. 没有 DNS：不存在"blockchain.network"可被解析；
2. 没有固定 IP：节点可能位于 NAT 后、移动网络或频繁更换 IP；
3. 没有目录服务：任何中央目录都会成为信任瓶颈与 DDoS 目标。

解决方案：种子节点（Seed Nodes）。初始连接通过社区公开的少量种子节点获取第一批邻居，之后通过"邻居的邻居"机制自主扩展。此后，网络发现即转为完全去中心化。

6.2.2 Kademlia DHT：异或度量的几何

Kademlia 的核心创新是将节点间的"距离"定义为两个 160 位 ID 的按位异或（XOR），并使其满足度量空间的所有公理。

异或度量的性质：

1. 自反性：$d(x, x) = x \oplus x = 0$；
2. 对称性：$d(x, y) = d(y, x)$（异或天然对称）；
3. 三角不等式：$d(x, z) \leq d(x, y) + d(y, z)$（二进制前缀维度结论）。

这些性质保证了"最近"在二进制树结构中有明确定义。

k-bucket 树结构

Kademlia 为每个节点维护一个二叉树，按距离前缀分层组织邻居：

每个 k-bucket 最多存储 $k$ 个邻居（通常 $k=20$）。查找目标时，从最高位到最低位逐步缩小范围，每次至少缩小一半距离。

graph TD
    A[节点自身<br>ID=10101...] --> B[距离区间<br>[2^3,2^4)]
    A --> C[距离区间<br>[2^2,2^3)]
    A --> D[距离区间<br>[2^1,2^2)]
    A --> E[距离区间<br>[2^0,2^1)]
    B --> B1[节点B1]<br>ID=00101...
    B --> B2[节点B2]<br>ID=01101...
    D --> D1[节点D1]<br>ID=10011...
    D --> D2[节点D2]<br>ID=10111...
    style A fill:#ccffcc
    style D1 fill:#ffffcc

6.2.3 查找算法：并行异步的 $\alpha$ 路查询

Kademlia 的节点查找不是顺序的，而是并行发送查询请求（通常 $\alpha=3$）：

1. 从本地 k-bucket 中选出 $\alpha$ 个已知距离目标最近的节点；
2. 并行向这 $\alpha$ 个节点发 FIND_NODE 请求；
3. 收集返回的节点列表，更新"已见"集合；
4. 重复前 3 步，直到无法发现更近的节点。

路由收敛效率：

因为在每次迭代中，查询至少可以排除剩余空间的一半（最高不同位被确定）。对于百万节点网络，$\log_2(10^6) \approx 20$ 跳即可完成定位——这是去中心化网络中惊人的效率。

// kademlia-xor.ts
// 纯内置：模拟 Kademlia XOR 距离与最近节点查找

function xorDistance(a: string, b: string): bigint {
  const ba = BigInt('0x' + a);
  const bb = BigInt('0x' + b);
  return ba ^ bb;
}

// 生成伪节点 ID
function randomNodeId(): string {
  return Array.from({length: 40}, () => Math.floor(Math.random()*16).toString(16)).join('');
}

// 查找距离目标最近的 k 个节点
function kClosest(nodes: string[], target: string, k: number): string[] {
  return [...nodes]
    .map(id => ({ id, dist: xorDistance(id, target) }))
    .sort((a, b) => (a.dist < b.dist ? -1 : 1))
    .slice(0, k)
    .map(x => x.id);
}

// 模拟网络查找
function findNode(allNodes: string[], selfId: string, target: string, a: number, k: number): {
  iterations: number;
  found: string[];
} {
  const shortlist = new Set<string>(kClosest(
    allNodes.filter(id => id !== selfId), target, a
  ));
  let prevCount = 0;
  let iterations = 0;
  while (shortlist.size !== prevCount && iterations < 50) {
    prevCount = shortlist.size;
    // 模拟并行查询最靠前的 a 个节点，每个返回 k 个已知最近节点
    const toQuery = Array.from(shortlist).slice(0, a);
    for (const q of toQuery) {
      const closer = kClosest(allNodes.filter(id => id !== q), target, k);
      for (const c of closer) shortlist.add(c);
    }
    iterations++;
  }
  return { iterations, found: kClosest(Array.from(shortlist), target, k) };
}

// 实验：10,000 个节点中查找目标
const nodes = Array.from({length: 10000}, randomNodeId);
const self = nodes[0];
const target = nodes[5000];
const result = findNode(nodes, self, target, 3, 20);
console.log(`网络: 10000 节点, 迭代: ${result.iterations}, 最终找到${result.found.length} 个最近节点`);
// 输出：迭代约 5-7 次，远小于 log2(10000) ≈ 14 的理论上界

6.2.4 Kademlia 在比特币与以太坊中的应用

比特币的选择：比特币使用 Kademlia 做节点位置查找（谁在线），而非内容查找（数据在哪里）。这为轻量实现提供了合理性——不需要存储价值映射，只需维护路由表。

6.2.5 Sybil 防御：节点 ID 的成本化

攻击者可以轻易伪造大量节点 ID 填满受害者的 k-bucket，使其所有查询都指向恶意节点。防御核心：让 ID 生成变得不可忽略地困难。

比特币/以太坊的常见做法：

1. IP 地址绑定：记录节点的 IP+端口，限制同一 IP 的节点数；
2. 随机淘汰：新节点进入 k-bucket 时按 LRU（最近最少使用）淘汰旧节点；
3. Proof-of-IP/Identity：某些网络要求节点 ID 的哈希前缀满足 PoW 条件，增加批量伪造的成本。

攻击者必须控制网络中相当大比例的节点 ID，才能劫持查询路径。在百万节点网络中，这种控制在经济上是不可行的。

关键认知：Kademlia 将"分布式查找"这一看似需要中心目录的问题，转化为纯几何问题。通过将"距离"定义为异或，它赋予去中心化网络以 $O(\log N)$ 的查找效率——这是比特币、以太坊节点发现层不可或缺的基础设施。

← 6.1 P2P 网络模型 | 前往 → 6.3 Gossip 协议与消息广播