为想创建项目的朋友搭建创业平台，请感兴趣的朋友加乐乐微信：sensus113
NervosFans 微信公号：Nervosfans
谢谢！
Kademlia是一种在很多现代去中心化协议中有实现的分布式哈希表，譬如Storj V3网络、以太坊、BitTorrent、Swarm与IPFS等。
Kademlia为数以百万计的计算机提供了一种自我组织成网络并与网络上的其他计算机进行通信，以及计算机之间共享资源（如文件、blob、对象）的方法，所有这些都不需要通过中央注册表或由个人或企业运行的查找。
Kademlia的概念由Petar Maymounkov与David Mazières于2002年构思，常被认为是第三代扁平化计算协议（third generation of flat-hierarchy computing protocols）采用的推手，因为它比集中式或基于泛洪的节点发现与路由方法更为可靠、高效。
Kademlia的分布式特征意味着在‘NodeID被映射到自己的地址’这一点上不存在绝对的事实（即，路由表是分布式的），因此每个节点必须在自己的路由表中为网络上的节点子集保留此映射。
基于Kademlia的网络完全有能力正面刚拒绝服务攻击以及节点的情形，原因是协议会直接绕过这些不可用节点。
这也使得分布式系统有足够的弹性来抵御攻击、停机以及中央故障点。
Kademlia的一个重大突破在于使用了XOR尺度（后面会描述）作为定义密钥空间点与点之间距离的手段，进而实现了节点间消息传送的最小化。
因此，当距离表示为log2（n）个节点时，意味着对于一个有1000万Kademlia节点的网络，实现任何节点子集间的通信，最多只需要约20跳。
“两点之间并非直线最短”
Kademlia的另一个优点则是协议会自然的偏爱年长节点。下图（来自Kademlia论文）表明，节点存在时间越长，未来保持在线的可能性就越大。
这种对节点“活性”的偏爱也自然地体现在了我们的分布式存储系统中，原因是节点流失将会导致‘必须将维修成本最小化’的情形。
image.png
加入Kademlia网络，只需发现一个peer即可，节点凭借此向网络广播自己‘已入场’。随后，发起人从每个响应中收集NodeID，并将收集来的NodeID添加到自己的peer表中。（“分布式哈希表”这个术语就是这么来的。）
如此，出现第三个优势，Kademlia使用的并行与异步查询可以有效防止超时延迟或因节点丢失或退出导致的“检索滞留”。
下面，我们快速过一遍Kademlia网络的基本组件：
Kademlia NodeIDs
Kademlia视网络中的每节点为二叉树上的一个叶子。一般来说，每个Kademlia节点都有一个160位的NodeID（SHA-1），位置由节点ID的最短唯一前缀决定。
为特定节点分配键值对时，Kademlia会依赖‘两个标识符之间的距离’这个概念。假设有两个160位的标识符x和y，Kademlia会把它们（标识符）之间的距离定义为XOR。
从节点的角度来说，（二叉）树被分成了一系列连续的子树，单个节点由第160个子树包含。Kademlia协议确保每个节点知道自己的每个子树上的至少一个节点。有了这种保证，节点就能够通过其他节点的ID找到其他节点。
路由表与K-bucket
路由表是个二叉树，树的叶子就是k-buckets。Kademlia路由表的结构使得节点能够维护离它最接近的地址空间的详细知识，对于更远的地址空间，（维持的）知识则呈指数减少。
这种对称性是很有用的，原因是距离最近的各个节点所维持的地址空间的详细知识会比较类似。
K-bucket指网络中其他节点的路由地址列表，由每个节点维护，包含系统中peer参与者的IP地址、端口与NodeID。K-bucket偏爱寿命最长的节点，这就意味着不能通过让大量新节点涌入系统的这种方式来取代节点的路由状态（也就防止了某些类型的DDOS攻击）。
路由表大小渐近地受O（log2（n/k））的限制，其中n代表网络中实际的节点数，k代表桶大小，因此大一点的桶实现会略微减少路由表中桶的总数。
Peer间消息传送
类似Kademlia的去中心化协议都会规定，为便于找到彼此、识别彼此位置以及交换消息，peer必须使用相同的语言。
Kademlia 协议包含4个远程调用：
-
PING:试探节点是否在线
-
STORE:命令节点存储键值对
-
FIND_NODE:返回最接近目标id的k个节点的信息
-
FIND_VALUE: 与FIND_NODE远程调用类似，但是，若接收方已经接收了给定key的STORE时，调用直接返回存储的值。
Storj中的Kademlia（见Kademlia白皮书3.3、4.6节）
Storj V3网络是Storj备受期待的下个分布式、去中心化对象存储平台。
新网络利用了Kademlia的修改版本作为节点查找中类DNS功能的主要真相来源，但是，网络其实并不需要Kademlia的键/值存储。
构建上一个Storj网络时，我们对Kademlia的实现投入了相当的精力，甚至围绕协议构建了一个文件系统的概念（filesystem concept around the protocol）。很快，我们就意识到了在分布式存储网络中使用修改过的k-buckets存在的一些性能限制，并在随后的Storj V3的开发中绕过了这些问题。
只使用Kademlia做节点查找就不用担心需要满足Kademlia其他功能需求的问题，譬如基于所有者的密钥重新发布、基于邻居的密钥重新发布、存储和检索值等等这些。
此外，为了使节点通信能够以安全且完全隐私的方式进行，每个peer在通信时必须使用一种只有通信对方能够理解的加密语言（避免有人窃听或中间人攻击）。
出于这个原因，我们已经实现了多个S/Kademlia扩展，以便在适当的情况下启用基于密钥的安全路由协议。
S/Kademlia还对某些专门针对分布式系统的攻击提供了基础保护，具体来说：
-
女巫攻击— 用户生成极端数量的任意身份（NodeID）在网络中泛滥。
-
Eclipse****攻击—攻击者以确保所有出站连接都到达恶意节点的方式试图隔离网络图中的一个节点或一组节点。
S/Kademlia扩展为节点生成创建了一个最小工作量的阈值，以此防止地址空间上的女巫攻击。相较于比特币（及类似共识协议）中实现的工作量证明，存储NodeID生成需要补零，如此，支持继续使用Kademlia的XOR路由。
这样也减慢了添加新节点的过程，且需要为NodeID的生成付出计算，但是该工作的结果会被合并到NodeID中，如此支持继续使用XOR路由，不需要额外验证NodeID是否已完成工作量。
定义V3网络规范时，我们深入咨询了Kademlia的作者Petar Maymounkov，Petar也被列为V3白皮书的撰稿人之一（白皮书第4.6.1节）。
在预防eclipse攻击上，Storj使用了公钥哈希作NodeID并依据S/Kademlia与Maymounkov的贡献规定了基于这些公钥的签名、节点审查过程以及多个不相交网络的查找。
Storj V3中克服的Kademlia局限
为了设计出一个全局可扩展的高性能分布式对象存储层，有些局限还是要突破的。
首先，对于很多操作来说，Kademlia这样的DHT需要进行多次网络往返，如此很难实现毫秒级的响应时间。
Storj Satellite上的覆盖缓存会跟踪最新的在线节点。在覆盖缓存中找不到节点时，我们会将节点标记为离线，因此擦除份额（erasure shares）消失，随即进入数据修复过程。
有趣的是，存储节点本身被与DHT缓存层分离，意思是节点可以在不与Satellite接触的情况下进行通信与组织。但是，想要进行客户端上传/下载，就需要有协调代理人（也就是Satellite）介入并与之通信。
对于每个在覆盖层上共享的Kademlia FIND_NODE RPC，该消息包括存储节点的可用磁盘空间、每个Satellite的带宽可用性以及网络所需的其他元数据。节点发现缓存会收集节点提供的这些信息，进而优化查找速度。
随后，参与的存储节点与Satellite一起进行集约的审批过程，确保其宣传资源的可用性。这个过程会为存储节点设定一个基准信誉，并纳入盈利潜力。
由此，进入路由表的节点被网络视为“审批通过”，且查找仅在已审批的节点间进行。
如此，确保了只有那些磁盘空间经过验证的节点才能入场并参与到路由层中，同时还可以深入了解网络容量深入了解网络容并防止攻击发生。
下面，我们了解下Kademlia在各去中心化平台中的应用。
1. Ethereum协议中的Kademlia
以太坊区块链网络堆栈中的节点发现协议基于微修改的Kademlia实现。
以太坊利用了Kademlia的XOR尺度与k-bucket结构，类似Storj，查找主要用于发现新peer。
以太坊中，客户端把其他节点的相关信息存储在两种数据结构中。 第一种结构是个名为db的长期数据库，存储在磁盘上并在客户端重启后保存。第二种是个叫做table的短期数据库，包含类Kademlia的桶，这些桶在客户端重启时总是空的。
值得注意的是，以太坊最初的Kademlia实施易受eclipse攻击，攻击者会生成一组以太坊NodeID，然后使用协同策略从两台主机便便宜宜地发起eclipse攻击，（每台主机）只用一个IP地址。
上面提到过，Storj能够避免这种情形，原因是Satellite审批过程与工作量证明证书生成使得生成NodeID的成本不容小觑。
- IPFS协议中的Kademlia
IPFS中也有使用Kademlia，连同Coral DSHT与S/Kademlia扩展。IPFS的实现中，NodeID包含到IPFS文件哈希的直接映射。每个节点还存储了获取文件或资源位置的相关信息。
很多项目都希望利用Storj网络作IPFS的对象存储。其中值得一提的是RTrade，他们正在构建一个由Storj支持的IPFS节点，以确保其IPFS文件的可用性与持久性。
3. Swarm协议中的Kademlia
Swarm的主要目标是为以太坊的公共记录提供足够去中化的存储，主要是dApp代码、数据的存储与分布，还有区块链数据。
Swarm网络中的参与者在Kademlia DHT中的识别靠的是Swarm帐户以太坊地址的哈希。这个哈希被用作（节点的）覆盖地址。
不过，Swarm不太适合做大对象存储，用来做与以太坊智能合约相关的小数据位存储倒是蛮合适。
Swarm分片最大4k，TB约10亿kb。因此，想要把大一点的对象上传到Swarm，譬如1TB大小，需要2.5亿个节点（对比下，美帝人口总数也就这个意思了）。
相比之下，Storj更适合存储大型对象，只要找到足够多的节点来覆盖擦除份额即可。
Swarm还实现了一个叫做责任邻域（the neighborhood of responsibility）的概念，采用了一种新的冗余策略（redundancy strategy）来保证节点流失时的可用性。根据运行上一版Storj网络的经验，我们发现分片复制并非保证文件持久性的有效方法，尤其是在那种有节点流失与上游带宽限制的环境中。
结论
了解Kademlia的最佳方法就是实际操作。欢迎加入Storj网络来共享不用的存储与带宽，运行自己的网络节点。
希望这篇文章能够让各位盆友对Kademlia以及其在现代分布式平台中的应用有个清楚的了解。
简言之，Kademlia以及XOR尺度是用于查找、路由与节点发现的高效手段，在以太坊、IPFS以及Swarm等去中心化平台上均有使用。
相关链接：
- 中央故障点：
https://storj.io/blog/2018/11/the-benefits-of-decentralization-go-far-beyond-ideology/
- Maymounkov等：
https://pdos.csail.mit.edu/~petar/papers/maymounkov-kademlia-lncs.pdf
- 维修成本最小化：
网友评论