网络与分布式2018pdos.csail.mit.edu编辑精选
Kademlia：基于 XOR 度量的大规模对等信息系统（2002）
Kademlia: A Peer-To-peer Information System Based on the XOR Metric (2002)
进阶 · 约 60 分钟读完前置知识：分布式哈希表基础、P2P 网络基础、哈希函数
导读
Kademlia 是 2002 年提出的基于 XOR 度量的 P2P 分布式哈希表（DHT）论文，节点按与目标 ID 的异或距离组织路由表，实现 O(log n) 的查询效率。它奠定了去中心化资源发现与检索的基础，被 BitTorrent、eD2k、I2P 等众多 P2P 系统采用。
HN 关注点：这篇经典论文，讨论焦点是 Kademlia 对 P2P 历史的深远影响，以及它在加密货币等现代去中心化系统中的应用与安全缺陷（如 eclipse 攻击）。
后来怎么样
Kademlia 成为事实上的 DHT 标准，被 BitTorrent、eD2k、I2P、IPFS(libp2p) 及众多区块链项目广泛采用，其 XOR 度量设计影响了后续几乎所有去中心化网络的路由协议。
HN 评论精选
这几条评论里：支持 1 质疑 1 补充 2
支持Kademlia 以 O(log n) 查询解决了第一代 P2P 的扩展性问题，拯救并塑造了后续几乎所有 P2P 协议
我很熟悉这篇论文，因为当年用 eMule——它的帮助窗口直接引用了这篇论文，否则 eD2k 无法实现去中心化。2000 年很特殊，Gnutella、eDonkey、Freenet 同年发布初版，P2P 网络仿佛从互联网中“涌现”。第一代 P2P 的 Gnutella 因无结构洪泛协议需要 O(n) 查询，用户超百万后就不稳定。然后 Kademlia 拯救了 P2P：BitTorrent、I2P、eD2k 等都基于 Kad。例如 eD2k 借助 Kad 实现了 P2P 资源发现和高效的去中心化关键词搜索（虽有垃圾信息但基本可用，BitTorrent 至今没有），查询只需 O(log n)。I2P 的 P2P 机制也完全基于 Kad。论文作者是少数对互联网做出巨大贡献的人。
bcaa7f3a8bbc查看英文原文
I'm familiar to this paper because I was using eMule. eMule has a direct citation to this paper in its "help" window, otherwise, the decentralization of eD2k would not be possible. The protocol is old, but still impressive. The year 2000 is special, within the same year, Gnutella, eDonkey and Freenet were all released its initial version, as if the P2P network "emerged" from the Internet. By 2004, eMule, I2P and BitTorrent (and BTW, Tor) were all here. At the very beginning, the first generation of P2P, Gnutella was suffering from its scalability problem - its simple unstructured, flooding protocol needs a number of O(n) queries, and becomes unstable once the users exceeded millions. Then, Kademlia almost saved P2P. BitTorrent, I2P, eD2k and many other P2P protocols are all Kad-based. For example, in eD2k, Kad allowed it to have P2P resource discovery, and also an efficient decentralized keyboard search engine (although there is spam, but mostly works, and in BitTorrent we still don't have it), all with only a O(log(n)) query, The P2P mechanism of I2P is also exclusively based on Kad. The authors of this paper are the few people who have made great contributions to the Internet.
补充加密货币的经济激励或可让上一代 P2P 的旧想法复兴
我很喜欢看到人们重新发现 15-20 年前的上一代 P2P 软件。读这些论文曾是我大学时代拖延时间的一大乐趣；也许现在加密货币提供了向贡献算力者支付经济激励的方式，这些旧想法可能会迎来复兴。
nostrademons查看英文原文
I love how people are rediscovering the previous generation of P2P software from 15-20 years ago. Reading through these papers was a huge part of my college procrastination; maybe now that cryptocurrencies give a way to provide economic incentives to those who contribute computing power, we might see a renaissance of some of these older ideas.
补充Kademlia 是 libp2p/DevP2P 的基础，但其拓扑假设并非适合所有场景，NuCypher 因此自研节点发现
Kademlia 很棒，它当然是 libp2p-kad-dht 和许多去中心化项目正在使用的 DevP2P 的基础。在 NuCypher，我们发现 Kademlia 核心有一些“星际”假设，虽然令人惊叹且适合许多场景，但并不符合我们“行星内”的分布式网络拓扑概念。如果 Kademlia 让你感兴趣，可以看看我们为什么自研节点发现的概述（附博客链接）。
jMyles查看英文原文
Kademlia is awesome and is, of course, the basis of libp2p-kad-dht and the DevP2P project that many decentralized projects are using at the moment. At NuCypher, we found that, all the way to the core of Kademlia, there were some "inter-planetary" assumptions that, while both mindblowing and fit for many use-cases, didn't fit our "intra-planetary" distributed notion of network topology. If Kademlia interests you, you might also be interested in this overview of what we did and why: https://blog.nucypher.com/why-were-rolling-our-own-intra-planetary-node-discovery-at-nucypher-beeb53018b0
质疑Kademlia 的确定性连接规则使其易受 eclipse 攻击，而基于 PoW 的 ID 防护在 ASIC 时代代价高昂
很多加密货币项目在用 Kademlia，但它容易受到 eclipse 攻击等漏洞影响。由于节点连接遵循确定性规则（常基于唯一 Node ID），网络拓扑可被分析并利用来破坏网络。有些方案让 ID 难以生成（如用哈希工作量证明生成节点 ID），但如今廉价 ASIC 矿机的算力远超普通电脑，这意味着节点 ID 需要用顶级 ASIC 生成才能真正安全，这大大增加了部署节点的复杂度。我不认为现有基于 Kademlia 的加密货币目前要求足够复杂的节点 ID。
jondubois查看英文原文
A lot of cryptocurrency projects are using Kademlia but it's prone to vulnerabilities such as eclipse attacks. Because peer connections are made according to deterministic rules (e.g. often based on unique Node IDs), the topology of the network can be analyzed and then the information can be exploited to disrupt the network. There are solutions which involve making it hard to generate IDs (I've seen it done with node IDs generated using hash-based proof of work) but nowadays with all the cheap ASIC miners, you could compute these hashes much faster than any regular computer could; this means that node IDs need to be generated using top-of-the-range ASICs in order to make the network truly secure; this adds a lot of complexity when it comes to deploying a node. I don't believe that any of the existing Kademlia-based cryptocurrencies currently require sufficiently complex node IDs.
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2018Hacker News 讨论帖191 分 · 40 评
同领域还值得读
Paxos vs. Raft：分布式共识是否已达成共识？
Paxos vs. Raft: Have we reached consensus on distributed consensus?
重新审视了 Paxos 与 Raft 两种分布式共识算法之间的差异，试图在一个统一的框架下比较它们，并论证二者的相似程度远高于通常的认知，许多所谓的差别只是表述层面的。
网络与分布式2020 · 343 分 · 65 评 · 引用 10进阶 · 约 28 分钟编辑精选Stellar 协议：互联网级共识的联邦模型
Stellar Protocol: A Federated Model for Internet-Level Consensus (2016)
提出 Stellar Consensus Protocol（SCP），一种面向互联网级共识的联邦拜占庭协议模型。
网络与分布式2018 · 301 分 · 61 评专业 · 约 90 分钟编辑精选拜占庭将军问题（1982）
The Byzantine Generals Problem (1982)
这篇 1982 年论文提出并形式化了拜占庭将军问题：在分布式系统中，部分节点可能叛变或故障、通信不可完全信任时，忠诚节点如何达成一致行动。
网络与分布式2018 · 290 分 · 77 评进阶 · 约 75 分钟编辑精选Google 变差了吗？对搜索引擎中 SEO 垃圾的纵向调查
Is Google Getting Worse? A Longitudinal Investigation of SEO Spam in Search
对搜索引擎结果中的 SEO 垃圾内容做了纵向追踪：作者团队在一段时间内持续采集 Google、Bing、DuckDuckGo 等引擎针对商品评测类查询的结果，用分类器识别联盟营销…
网络与分布式2024 · 276 分 · 274 评入门 · 约 45 分钟编辑精选使 CRDT 能够容忍拜占庭故障
Making CRDTs Byzantine Fault Tolerant
Martin Kleppmann 等人的论文研究如何让 CRDT（无冲突复制数据类型）抵御拜占庭故障节点，即部分参与者恶意篡改数据时仍能保证一致性。
网络与分布式2022 · 266 分 · 40 评进阶 · 约 90 分钟编辑精选