隐私加密系列|详细介绍了分布式哈希表DHT

哈希表是一种将键映射到值的数据结构。哈希函数用于计算插入到表中的键，以后可以从中检索值。顾名思义，分布式哈希表(DHT)是分布在多个链接节点之间的哈希表，这些节点协作形成一个内聚的哈希表服务。这些节点连接在一个称为覆盖网络的网络中。覆盖网络就是建立在另一个网络之上的通信网络。互联网就是一个例子，它最初是一个覆盖在公共交换电话网上的网络。

价值⟩⟨键的一个子集通常存储在网络中,通常在一些AMPL;关闭AMPL在;的存储方式。

DHT网络设计允许网络容忍失败的节点而不发生故障，并且允许网络无限地增长。

对DHT的需求源于早期的文件共享网络，如Gnutella、Napster、FreeNet和BitTorrent，这些网络能够利用互联网上的分布式资源来提供单一的内聚服务。

这些系统使用不同的方法来定位网络上的资源:

Gnutella搜索是低效的，因为查询充斥着web信息。

Napster使用中央索引服务器，这是一个单点故障，容易受到攻击。

FreeNet使用基于密钥的路由。但是它的结构比DHT少，并且不能保证找到数据。

2001年，DHT推出了四个项目:CAN、Chord、Pastry和Tapestry。他们的目标是利用去中心化网络的优点，使查询效率(O (log (n))类似于中心化式索引。

DHT根据给定的算法使用各种技术来实现这一目标。但他们有很多共同点:

每个参与者都有一些唯一的网络标识符。

它们执行点对点查找、数据存储和检索服务。

有一些隐式或显式连接过程。

通信只需要在由某种算法确定的邻居之间进行。

在本文中，我们将讨论所有DHT的一些共同之处，并深入研究一种名为Kademlia的流行DHT实现。

DHT网络的特点

同行的发现

对等发现是在分布式网络中定位节点进行数据通信的过程。这是通过每个节点维护一个节点列表并与网络上的其他节点共享这个列表来实现的。新参与者将首先联系一组预定义的启动节点，以查找网络上的节点。这些节点是正常的网络参与者，恰好是某个动态或静态列表的一部分。网络中每个节点的工作是促进对等点发现。

当对等节点彼此通信时，更新这些列表以确保网络完整性。

可扩展性和容错性

DHT网络有效地分配了复制、存储和检索路由信息和数据的职责。这种分布允许节点连接和离开，以最小的中断或不中断。一个网络可以有大量的节点(在BitTorrent的情况下，有数百万个节点)，而每个节点都不需要知道网络中的每个其他参与者。通过这种方式，DHT天生就比典的中心化式系统更能抵御恶意攻击。

BitTorrent是现存最大的分布式网络之一，拥有数千万并发用户和数亿活跃用户。据估计，比特流网络每个月有25亿用户。截至2019年，Tor拥有约9000个中继服务器和超过200万用户。

分布式数据存储

节点的子集可以存储和复制任意数据供以后检索。使用一致的哈希函数(如SHA256)对数据进行哈希，以生成数据的键。数据被传播并最终存储在一个节点ID中，节点ID的键是distance函数中的数据。更近期和贯穿;在一个或多个节点上。

分区数据存储在典的区块链中用途有限，因为每个完整节点需要保留所有事务和块的副本以进行验证。

Kademlia

Kademlia被设计为一种在分布式对等网络中存储和查找内容的有效方法。它具有许多其他DHT无法同时提供的核心功能，如:

1. 最小化节点需要相互了解的消息数量。

2. 节点有足够的信息来通过低延迟路径路由流量。

3.并行和异步查询用于避免失败节点的超时延迟。

4. 节点存在算法抵抗一些基本的分布式拒绝服务(DDoS)攻击。

节点ID

节点选择一个n位ID，该ID将提供给网络上的其他节点。网络设计依赖于节点id通过一些随机过程的均匀分布。节点的位置由其ID的最短唯一前缀决定，该前缀形成树结构，节点ID是叶子。当节点重新加入网络时，应该重用这个ID。下图为三位数密钥空间的二叉树结构:

节点ID的位长应该足够大，以便在使用均匀分布的随机数生成器时不太可能发生冲突。

引导一个节点

想要加入网络的节点没有已知的联系人。为了让一个节点在网络上建立自己，它必须联系一个或多个引导节点。这些节点并不特殊，只是在一些预定义的列表中列出。它们只是作为请求节点的第一个接触点，以便更多的网络可以知道并找到它们最接近的对等节点。

获取启动节点的方法有很多，包括向配置中添加地址和使用DNS种子。连接过程描述如下:

1. 连接节点以生成一个随机ID。

2. 它会联系它所知道的节点。

3.它为新生成的节点ID发送一个FIND_NODE查找请求。

4. contact节点返回它们知道的最近的节点。新发现的节点被添加到连接节点的路由表中。

5. 然后将节点连接到它所知道的一些新节点。然后迭代地继续这个过程，直到连接节点无法找到任何更近的节点为止。

这种自查找有两个效果:它允许节点了解离它更近的节点;它使用节点的ID填充其他节点的路由表。

XOR规

2002年发表的Kademlia论文提供了XOR的使用。算子是一种确定网络中节点距离和位置的新方法。定义为:

这是因为XOR具有与任何距离函数相同的数学属性。

具体地说,

身份:a⊕一个= 0

非负性:a⊕Bgt;0为围护结构;b

对称:a⊕B = b⊕一个。

三角不等式:a⊕B + b⊕C≥A⊕c

XOR度量隐式地捕获了前面树结构中的距离概念。

协议

Kademlia是一个相对简单的协议，它只包含四个远程过程调用(RPC)消息，这有助于解决两个独立的问题:对等发现和数据存储/检索。

以下RPC消息是Kademlia协议的一部分:

同行的发现

乒乓球-用来确定一个伙伴的活动状态。

FIND_NODE—返回更接近给定查询值的多个节点。

数据存储/检索

商店-请求存储⟩⟨键和值。

FIND_VALUE—通过返回一个较近的节点，其行为与FIND_NODE相同。如果节点请求⟨关键值⟩吧,它将返回的值存储。

注意，这里没有连接消息。这是因为在卡迪姆利亚没有明确的参与。当RPC消息在节点之间发送/接收时，每个节点都有机会被添加到另一个节点的路由表中。这样，节点就被网络所知。

查找程序

给定节点ID，查找过程允许节点定位其他节点。此过程同时从发起者查询最接近已知目标节点ID的α(并发参数)节点启动。查询节点返回它所知道的最近的k个节点，然后查询节点轮流查询越来越近的节点，直到找到节点为止。在此过程中，查询节点和中间节点相互认识。

数据存储和检索程序

存储和检索过程确保⟨键,值⟩存储在一个可靠的方式,能够参与到网络检索:

存储过程使用查找过程来定位最靠近键的节点，并向其发出存储RPC消息。每个节点将重新分配⟨键,值⟩,为了提高数据的可用性。根据实现的不同，数据最终可能会过期(例如，24小时)。因此，原始发布者可能需要在过期日期之前重新发布数据。

除了发出FIND_VALUE RPC和接收数据之外，检索过程遵循与存储相同的逻辑。

路由表

每个节点将联系人组织成一个称为路由表的列表。路由表是一个二叉树，其中叶子是;Bucket”，包含最多k个节点。K是一个网络范围的参数，它应该足够大，以确保查找和数据具有高概率。这些桶被恰当地命名为k桶，并包含一些具有公共节点ID前缀的节点。

应该注意的是，这是由XOR度量捕获的。例如，假设节点A(1100)有节点B(1110)、节点C(1101)、节点D(0111)和节点E(0101)，则节点A到节点A的距离为:

A⊕B = 0010 (2)

A⊕C = 0001 (1)

A⊕D = 1011 (11)

A⊕E = 1001 (9)

A、B和C在前两个最重要的位(MSB)之前共享相同的前缀。但是A、C和D没有共享前缀位，所以它们相距很远。在这个例子中，A、B和C在同一个桶中，D和E在它们自己的桶中。

最初，节点的路由表不填充k-bucket，但是可以在k-bucket中包含节点。随着更多节点的出现，它们被添加到k-bucket，直到k-bucket满为止。此时，节点将bucket分为两部分:一部分用于与它共享相同前缀的节点，另一部分用于所有其他节点。

这保证了对于桶j，其中= jlt;节点A在其路由表中至少有一个节点N

K -桶排序

k-bucket中的对等节点按照最近看到的次数排序。节点从对等节点接收到请求或应答后，将检查对等节点是否包含在适当的k-bucket中。根据对等点是否已经存在，条目将被移动或添加到列表的末尾(如最近所见)。如果某个桶的大小已经为k，节点将尝试PING列表中的第一个对等点(最近看到的最小值)。如果这个对等点没有响应，它就会被抛出，新的对等点就会被附加到存储桶中，否则新的对等点就会被丢弃。通过这种方式，该算法有利于具有长寿命和高可用性的对等点。

Kademlia攻击

一些著名的攻击:

节点插入攻击

由于无法验证节点的ID，攻击者可以选择其ID来占据网络中的特定密钥空间。一旦攻击者以这种方式插入自己，他们就可以查看或操作该密钥空间或eclipse节点中的内容。

日食袭击

卡德姆利亚很容易受到日蚀的影响。这将在下一节中讨论。

DHT漏洞和攻击

日食袭击

Eclipse攻击是对等同性(或点对点)网络的一种攻击:攻击者通过特使的方式从整个网络中消失，从而完全控制特定节点对信息的访问。

攻击者利用了这样一个事实，即在160位密钥空间的大部分地方实际上节点相对较少。攻击者比群体的其他成员更接近目标，最终获得优势。如果网络规则允许来自同一IP地址的多个对等点，那么这样做的成本很低。

eclipse攻击的成本在很大程度上取决于网络的体系结构，从少数机器(例如，一台机器上的数百个节点实例)到需要成熟的僵尸网络。

对策:

身份必须独立于一些随机的预言。

节点与当前网络布局之外的节点保持联系。

女巫攻击

女巫攻击是试图通过串通节点获得不成比例的网络控制，通常被用作其他攻击的工具。许多(如果不是全部的话)dht的设计假定节点的下部是恶意的。女巫攻击试图通过增加恶意节点的数量来打破这一假设。

对策:

将成本与向网络添加新标识符相关联。

将实际标识符(IP地址、MAC地址等)可靠地连接到节点标识符，并拒绝重复阈值。

有一个可信的中央机构或安全的去中心化的方案来发布身份。

利用社会信息和信任关系。

自适应join-leae攻击

假设我们有一个网络，它的节点id完全是由某个随机的预言机随机选择的。对手首先执行连接/离开，直到键空间中有节点为止。在此之后，它们依次进行处理，保留I处的节点并重新连接不属于I的节点，直到在该区间内获得控制。

重要的是要注意，如果重新加入网络的成本足够大，这种攻击将被抑制。在缺乏这种抑制因素的情况下，杜鹃规则被提出作为一种辩护。

结论

DHTs是一种有效的分布式存储和发现解决方案。尤其值得一提的是，Kademlia已经成功地实现并维护了一个拥有数百万参与者的文件共享和区块链网络。与所有网络一样，它也并非没有缺陷，需要精心的网络设计来减轻攻击。