2020:07:14   今天是星期二   11:16:33
APP下载 万链之家APP

Android

隐私加密系列|详解分布式哈希表DHT

05-29 11:55

标签    区块链   区块链论坛   区块链媒体   比特币   以太坊

文章来源: 万链之家

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

⟨key,value⟩对通常存储在网络的一个子集中,通常以某种“接近”的方式存储。

DHT网络设计允许网络容忍出现故障的节点而不会出现故障,并允许网络规模无限增加。

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


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

· Gnutella搜索效率低下,因为查询将导致信息泛滥到网络中。
· Napster使用了中央索引服务器,这是一个单点故障,很容易受到攻击。
· FreeNet使用了基于密钥的路由。但是它的结构比DHT少并且不能保证可以找到数据。

2001年,引入了四个DHT项目:CAN,Chord,Pastry和Tapestry。他们的目标是具有类似于集中索引的查找效率(O(log(n))),同时具有分散网络的优势。

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

· 每个参与者都有一些唯一的网络标识符。
· 他们执行对端查找,数据存储和检索服务。
· 有一些隐式或显式的连接过程。
· 通信仅需要通过某种算法确定的邻居之间发生。

在本文中,我们将讨论所有DHT共有的一些方面,并深入研究一个流行的DHT实现,称为Kademlia。

DHT网络的特征

对等发现(Peer Discovery)

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

随着对等方不断相互交流,这些列表会不断更新以确保网络完整性。

可扩展性和容错性

DHT网络有效地分配了对路由信息和数据的复制存储和检索的责任。这种分布允许节点以最小或没有中断的方式加入和离开。网络可以具有大量的节点(在BitTorrent的情况下为数百万个节点),而每个节点不必知道网络中的每个其他参与者。这样,与典型的集中式系统相比,DHT本质上具有更强的抵御恶意攻击者的能力。

BitTorrent是现存最大的分散式网络之一,其包含的并发用户数千万,活动用户数亿。据估计BitTorrent网络每月有25亿用户。截至2019年,Tor拥有约9000台中继服务器和200多万用户。

分布式数据存储

节点的子集可以存储和复制任意数据,以供以后检索。使用一致的哈希函数(例如SHA256)对数据进行哈希处理以生成数据的密钥。该数据被传播并最终存储在一个节点ID与某个距离函数的该数据的密钥“更近”的一个或多个节点上。

分区数据存储对典型的区块链的作用有限,因为需要每个完整节点保留所有交易和块的副本以进行验证。

Kademlia

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

1. 节点相互了解所需的消息数量最小化。
2. 节点有足够的信息通过低延迟路径路由流量。
3. 并行和异步查询是为了避免失败节点的超时延迟。
4. 节点存在算法抵抗某些基本的分布式拒绝服务(DDoS)攻击。

节点ID

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

区块链


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

引导节点(Bootstrapping a Node)

希望加入网络的节点没有已知的联系人。为了使节点在网络上建立自己节点,它必须联系一个或多个引导节点。这些节点在任何方面都不是特殊的,只是列在一些预定义的列表中。它们只是作为请求节点的第一个联系点,以便让更多的网络知道并找到其最接近的对等点。

有很多方法可以获得引导节点,包括向配置添加地址和使用DNS种子。连接过程描述如下:

1. 连接节点生成一个随机ID。
2. 它会联系一些它知道的节点。
3. 它发送新生成的节点ID的FIND_NODE查找请求。
4. 联系的节点返回他们所知道的最近的节点。新发现的节点将添加到加入节点的路由表中。
5. 然后连接节点联系它所知道的一些新节点。然后该过程迭代地继续,直到连接节点无法找到任何更靠近的节点。

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

XOR Metric

2002年发表的Kademlia论文提供了使用XOR(⊕)运算符确定距离以及网络中对等节点的位置的新颖思想。定义为:


之所以可行,是因为XOR具有与任何距离函数相同的数学属性。

具体来说,

Identity: a⊕a=0
Non-negativity: a⊕b>0 for a≠b
Symmetry: a⊕b=b⊕a
Triangle inequality: a⊕b+b⊕c≥a⊕c

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

协议

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

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

对等发现(Peer discovery)

· PING/PONG-用于确定同伴的活动状态。
· FIND_NODE-返回更接近给定查询值的多个节点。

数据存储/检索

· STORE-请求存储 ⟨key,value⟩对。
· FIND_VALUE-通过返回更近的节点,其行为与FIND_NODE相同。如果节点具有请求的⟨key,value⟩对,则它将返回存储的值。

值得注意的是,没有JOIN消息。这是因为在Kademlia中没有明确的加入。每当在它们之间发送/接收RPC消息时,每个对等体都有机会被添加到另一个节点的路由表中。以这种方式,该节点成为网络已知的。

查询程序(Lookup Procedure)

给定节点ID,查找过程允许节点定位其他节点。该过程从启动器同时查询与其知道的目标节点ID最接近的α(并发参数)节点开始。查询的节点返回它知道的k个最近的节点,然后查询节点轮流进行,查询越来越近的节点,直到找到该节点为止。在此过程中,查询节点和中间节点都相互了解。

数据存储和检索程序

存储和检索过程确保 ⟨key,value⟩对被可靠地存储并且能够被网络中的参与者检索:

· 存储过程使用查找过程来定位最接近键的节点,这时它将向这些节点发出STORE RPC消息。每个节点都会重新发布⟨key,value⟩对,以提高数据的可用性。取决于实现方式,数据最终可能会过期(例如24小时)。因此在该期限到期之前,可能要求原始发布者重新发布数据。

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

路由表

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

应当注意,这是由XOR度量捕获的。例如给定节点A(1100)具有对等端B(1110),C(1101),D(0111)和E(0101),到节点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在同一个bucket中,D和E在它们自己的bucket中。

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


这保证了对于bucket j,其中0<=j

k-bucket排序

k-bucket中的对等点按最少到最近看到的排序。一旦节点接收到来自对等方的请求或回复,它就会检查对等方是否包含在适当的k-bucket中。根据对等点是否已存在,该条目将被移动或附加到列表的尾部(最近看到的)。如果一个特定的bucket已经是大小k,那么节点将尝试PING列表中的第一个对等方(最近看到的最少)。如果对等方不响应,则将其逐出并将新对等方附加到存储bucket中,否则将丢弃新对等方。通过这种方式,算法偏向于使用寿命长且高度可用的对等点。

Kademlia攻击

Kademlia一些值得注意的攻击:

节点插入攻击

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

日蚀攻击

Kademlia容易受到日蚀攻击。这将在下一节中讨论。

DHT漏洞和攻击

日蚀攻击

日蚀攻击(Eclipse Attack)是针对对等式(或译为点对点)网络的一种攻击类型:攻击者通过使节点从整个网络上消失,从而完全控制特定节点对信息的访问。

攻击者利用了这样一个事实:实际上在160位密钥空间的大多数部分中,节点相对较少。攻击者将自己注入比其他同伴更靠近目标的位置,最终可以取得统治地位。如果网络规则允许许多对等方来自同一IP地址,则可以廉价地完成此操作。

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

应对措施:

· 身份必须独立于某些随机预言。
· 节点与当前网络布局之外的节点保持联系。

女巫攻击

女巫攻击是通过合谋节点来获得对网络的不成比例的控制的尝试,通常被用作其他攻击的媒介。许多(如果不是全部的话)dht是在假设低部分节点是恶意的情况下设计的。女巫攻击试图通过增加恶意节点的数量来打破这一假设。

应对措施:

· 将成本与向网络添加新标识符相关联。
· 将真实的标识符(IP地址、MAC地址等)可靠地连接到节点标识符,并拒绝重复的阈值。
· 有可信的中心权威或安全的分散的方案来发布身份。
· 利用社交信息和信任关系。

自适应联动离开攻击(Adaptive Join-Leave Attack)

假设我们有一个网络,它的节点id是通过一些随机的oracle完全随机选择的。对手首先执行join/leaves,直到在该keyspace中有节点为止。之后,它们将进行轮次处理,保留位于I的节点并重新加入不属于I的节点,直到在该时间间隔内获得控制权为止。

需要注意的是,如果重新加入网络的成本足够大,则会抑制此攻击。在没有这种抑制因素的情况下,布谷鸟规则被提出作为防御手段。

结  论

DHTs是一种行之有效的分布式存储和发现解决方案。特别是Kademlia,已经成功地实现并维持了与数百万参与者的文件共享和区块链网络。与每一个网络一样,它也不是没有缺陷的,需要仔细的网络设计来减轻攻击。


声明:万链之家登载此文出于传递更多信息之目的,并不意味着赞同其观点或证实其描述。文章内容仅供参考,不构成投资建议。投资者据此操作,风险自担。

丶薄情少年′

0打赏金币 11所得总金币

    最新发表    最高金币  最高点击量

特约作者

7x24h快讯更多 >>
  • 07.13 13:11

    红苹果交易所平台币Apple燃烧挖矿模式于7月10日创新上... [快讯详情]

  • 07.12 17:28

    MJT(莫吉托) 7.12号盛世挖矿开启,全网十五个知名社... [快讯详情]

  • 07.12 14:30

    ABLEX数字资产平台获得美国MSB金融交易牌照据官方消息... [快讯详情]

  • 07.12 14:19

    MFA将开启宝莱坞电影投融资根据MFA“鲲鹏计划”发展规划... [快讯详情]

  • 07.11 18:13

    HKEx.one全球技术交流会·长沙站暨HKEx Club... [快讯详情]