第5章 【IPFS一问一答】IPFS技术的背景之分布式哈希表DHTs

5 分布式哈希表DHTs

5.1 Kademlia DHT

Kademlia DHT的简称就是KAD,它对DHT进行了良好的改进。简单分析如下: 新加入的节点,首先根据节点的IP地址随机产生一个节点ID,通过种子节点,获取与自己ID异或距离相近的节点,生成160个K桶。K桶里的节点信息有IP地址、udp端口和NodeID。另外还有一个<key,value>类型的文件存储信息DHT表,key是存储文件的哈希值,value是存储文件的节点ID。网络中每个节点都会优先存储与自己ID距离较小的文件,也就是key和NodeID异或距离更近的节点存储文件。

5.2 Coral DSHT

Coral提供了一个名叫DSHT的概念。DSHT提供了一种基于key/value的存储机制,不同的value可以具有相同的key。CoralCDN通过这种结构,将各种key映射到不同CoralCDN节点。尤其,通过这种机制,CoralCDN可以查找距离客户端较近的DNS服务器,距离客户端较近的存有web数据的HTTP代理,可以定位到具有较小时延的Coral节点。

不同于一般的覆盖网络,所有的Coral节点属于几个独立的DSHT(称为集群)。每个集群依据最大RTT作为衡量标准进行划分。系统依据不同的RTT标准分为几个层。所有的节点均为某个层上的节点。在Coral中,将DSHT分为三层:

Level-2对应两两延时小于20毫秒;快响应覆盖的集群。(regional coverage)
Level-1对应两两延时小于60毫秒;低延迟覆盖的集群。(continental coverage)
Level-0对应其他的全部节点;延迟时间∞;不限制延迟覆盖的集群。(planet-wide)

Coral首先请求较高层的比较快的节点,然后请求较低层比较慢的节点。这样可以有效的降低响应时间,以及找到距离比较近的节点。

Coral为应用提供了一下接口:

5.3 S/Kademlia DHT

Kademlia协议运用于完全开放的P2P网络,并没有提供安全措施,容易遭到恶意节点的攻击。S/Kademlia协议在Kademlia基础上,扩展了抵御攻击的策略,包括限制节点任意产生节点ID、兄弟广播和不相交的路径查询算法。

5.3.1 Kademlia面临的攻击

主要分为两类,一类是针对路由表控制网络中部分节点;另外一类是恶意消耗占用节点的资源。 

女巫攻击是在P2P网络中,因为节点随时加入退出等原因,为了维持网络稳定,同一份数据通常需要备份到多个分布式节点上,这就是数据冗余机制。女巫攻击是攻击数据冗余机制的一种有效手段。如果网络中存在一个恶意节点,那么同一个恶意节点可以具有多重身份,就如电影了的女主角都可以分裂出16个身份,那么恶意节点比它还能分。这一分可好,原来需要备份到多个节点的数据被欺骗地备份到了同一个恶意节点(该恶意节点伪装成多重身份),这就是女巫攻击。

日蚀攻击主要是对单个节点进行攻击,攻击的主要对象是节点的K桶。攻击者可以自由的选择自己的ID,当被攻击者的K桶不满或内部有节点ping不通时,恶意节点就会有机会进入K桶。恶意节点控制了K桶,信息的传递都要通过恶意节点,那么被攻击者将会与整个网络脱离。

攻击者控制一堆节点,一下子把节点从网络中流失,从而导致网络稳定性降低。

恶意节点收到查询指令后,不按照KAD的要求返回距离Key最接近的网络节点,而是转移给同伙节点,最终导致查询实效。为了避免这种无聊的敌对路由攻击,设计算法在查询时进行并行查询,每一条查询路径不相交,一旦并行查询的路径中有一条抵达,就代表成功查询了。

5.3.3 S/Kademlia安全策略

1.控制节点ID的生成,使其不能任意的选择节点ID,不能大量的生成节点ID。同时要保证节点的ID不能被窃取或被伪装。以此来解决女巫攻击和日蚀攻击。

S/Kademlia要求每个节点在接入网络前必须解决两个密码学问题。

静态问题是:产生一对公钥和私钥,公钥两次哈希运算后,具有 C1 个前导零。公钥的一次哈希值就是节点的NodeID。 动态问题是:不断生成一个随机数X,将X与NodeID求XOR,再求哈希,哈希值要求C2个前导零。

下图描述了解决这两个数学问题的过程。

这样设计,第一个静态问题,保证节点不能再自由选择节点 ID,后一个动态问题,提高了大量生成ID的成本。女巫攻击和日蚀攻击将难以进行。

为确保节点身份不被窃取,节点对发出的消息进行签名。其他节点收到消息,验证签名的合法性,然后检查ID是否满足两个难题的要求。验证节点信息的合法性的时间复杂度是很低的,而生成这样一个合法的攻击信息的时间复杂度是很高的,这种不对称就能避免上面的前三种攻击了。

2.不相交的路径查询算法

Kademlia 协议中,访问α个 K-Bucket 中的节点,然后排序后,选择前 α 个继续迭代请求,缺点很明显,如果有恶意节点,查询很可能就会失败。

S/Kademlia 提出每次查询选择 k 个节点,放入 d 个不同的桶中。这 d 个桶进行查找,d 条查询路径做到不相交,单个桶有失效的可能,但是只要 d 个桶中有一条查询到了需要的信息,工作就完成了。通过不相交路径查询,解决了敌对路由攻击。