分布式哈希表DHT及其变种
分布式哈希表DHT及其变种
P2P网络，如果用一个中心化数据库来协调，问题是很明显的，最主要是单节点很不安全，节点被攻击或者性能达到瓶颈宕机了，整个网络就瘫痪了。人们一开始肯定想到了消息洪泛方法（message flooding）来定位查找数据，但网络承载不了这么多数据查找请求，或者每个请求的生存时间设置短一点来控制整个网络内请求的数量。到了第三代，就是DHT（Distributed Hash Table），其实核心思想也很简单：全网维护一个巨大的文件索引哈希表，这个哈希表的条目形如（key，value）。这里key通常是文件的哈希值，而value则是存储文件的IP地址。根据key就能找到存储到节点地址并返回给查询节点。当然，这个表是按照一定规则分割存储到全网各个节点上。我们接下来介绍三种IPFS会用到的分区表类型：
- Kademlia DHT
- Coral DHT
- S/Kademlia
Kademlia DHT
KAD网络对DHT有较大改进，一个新来的网络节点在初次连接到网络时会分配到一个ID，每个节点自身维护一个路由表和一个DHT，路由表保存网络中一部分节点的连接信息，DHT则用于存放文件信息。从上可以看出，KAD由两部分组成：
- 路由表
- DHT
KAD网络中每个节点优先保存距离自己更近的节点信息，但一定确保距离在[2n,2(n+1)-1]的全部节点，至少保存k个（k是常数）,我们称做K-Buket，网络中每个节点都会优先存储与自己ID距离较小的文件。每次检索时，查询文件的哈希值与自己的ID求距离，然后找到这个距离对应的K-Buket，这样递归查询下去，有某个节点发现自己存了检索数据，就返回给查询的节点。
1.Kademlia二叉状态树
image
Kademlia网络的节点ID是由一颗二叉树维护，每个DHT条目包含<key,value>对，Key是文件的哈希值，Value是节点ID。Key和Value有相同的值域，都是160位。数据就存放在Key值和ID值最接近的节点上。如何定义它们的距离远近，XOR运算可以解决这个问题。在160位Hash上，判断两个节点x，y的距离远近是异或的二进制运算，d(x,y) = x XOR y。使用异或距离，只要沿着XOR距离降低的方向查找，从任意一个网络节点开始查询，总能找到存放文件的地址。每次更新总能筛选掉一半的节点，最多只需Log(n)步即可到达。
2.节点路由表K-Buket
节点路由表保存每个节点与自己一定距离范围内其他节点的连接信息。每一条路由信息由如下三部分组成：IP Address、UDP Port、Node ID。KAD路由表将距离分为160个K桶（存放K个数据的桶），比如编号为i的路由表，存放着距离为[2i,2(i+1)-1]的K条路由信息。且K桶内部存放位置是根据上次看到的时间顺序排列，最早看到的放在头部，最后看到的放在尾部。
当节点x收到一个消息时，发送者y的IP地址被用来更新对应的K桶，具体步骤如下：
- （1）计算自己和发送者的ID距离：d(x,y) = x XOR y
- （2）通过距离d选择对应的K桶进行更新操作。
- （3）如果y的IP在K桶中，把对应项移到K桶的尾部，如果y不再K桶中：
- 1 如果K桶的记录项小于k个，直接把y的信息插入队列尾部。
- 2 如果K桶的记录项大于k个，选择头部的记录项进行RPC_PING操作：
- （a）如果没有PING通，则从K桶中移除其信息，把y信息插入队列尾部。
- （b）如果PING通，把其信息放入队列尾部，忽略y的信息。
1）路由查询机制
KAD能运用递归查找，快速查找节点，还可以通过参数进行查找速度的调节。
- d(x,t)
- 从x的log(d)的K桶中取出α个节点的信息，FIND_NODE操作。
- 收到查询请求的节点发现自己是t，则回答自己最接近t的；否则测量自己和t的距离，并从自己对应的K桶中选择α个节点的信息给x。
- x对收到的新的节点再次执行FIND_NODE操作，不断重复执行，直到每一个分支都有节点响应自己是最接近t的。
- 通过上述操作，x得到k个最接近t的节点信息。
这里说是最接近t的节点信息，而不是等于，可能是ID为t的节点根本就不存在。α也是为了权衡性能设定的参数。整个查询过程的收敛速度为O(logN)，N为全网节点数量。
查找节点ID的方法，对于文件查找也是一样，FIND_Value操作，查找自己是否保存ID为t的文件。文件查找的收敛速度同样是O(logN)。
2) 节点加入和离开
节点u要加入KAD网络，总是需要一个介绍人w，u首先要把w插入自己适当的K桶中，然后对自己的ID执行FIND_NODE操作，然后得到的信息更新自己的K桶内容。通过对自己临近节点由近及远的逐步查询，u完成了K桶信息的构建，同时也把自己的信息发布到其他节点的K桶中。
节点要离开KAD网络，不需要发布任何消息，等待节点离线的时间足够长，其他网络节点访问它失败后，便会纷纷自动将其移出各自的路由表，这一节点也就离开了。
Coral DSHT
在Kademlia协议，使用的是XOR距离，信息永远是存储在XOR距离最近的节点中。而这样并没有考虑实际网络的情况，例如节点之间的延时，数据的位置。这样会浪费大量网络带宽和存储空间。不同于经典的DHT方式，Coral首先对所有的节点评估连接情况，然后根据循环时间（Round-Trip Time）划分为几个等级。
Coral DSHT(Distributed Sloppy hash table)适用于软状态的键值对检索，同一个Key可能会保存多个Value。这种机制能把给定的Key映射到网络中Coral服务器地址。比如，使用DSHT来查询距离用户较近的域名服务器，查询拥有特定网站缓存信息的服务器，定位周围的节点来最小化请求延时。
1.索引机制和分层
Coral对路由表的处理也比较特殊，每一个Coral节点根据他们的延时特性放在不同的DSHT中。同一个DSHT的节点被称为同一个集群（Cluster），每个集群有一个最大延时时间，称为集群直径（Diameter）。整个系统会预先设定几个直径，称为等级（Level）。在每个等级划分下，每个节点都会是某一个DSHT的成员。一组节点只有满足两两直径小于第i个等级的极限时，他们就能成为一个集群。在Coral中，将DSHT分为三层：
- Level-2对应两两延时小于20毫秒；
- Level-1对应两两延时小于60毫秒；
- Level-0对应其他的全部节点；
Coral在询问时，也会优先请求等级更高，响应时间更短的节点。
2.基于键值对的路由层
Coral的键值对与Kademlia一样，每个节点的ID是由它的IP地址通过SHA-1运算得到。可通过Put指令保存一个Key/Value对，用来表明Key和Value是接近的，也可通过Get指令，查询对于同一个Key，节点的远近顺序如何。
3.Sloppy存储
Kademlia斜体中，数据通过XOR保存到更近的节点，数据如果非常流行，就会有大量查询造成拥堵，称为Hot-Spot；同时对一个缓存键值对存储了过多的值，称为Tree-saturation。Sloppy存储希望避免这两种情况。
每一个Coral节点定义有两种异常状态：
- Full，在当前节点R，已经有L个（Key/Value）对使得Key=k，并且这L个键值对的生存周期都大于新值的1/2。
- Loaded，对于给定的Key=k，在过去的一分钟里已经收到超过beta次请求。
Coral执行存储分为两步进行：
第一步是前向查询，Coral会持续迭代查找距离Key更近的节点ID，每一个节点返回两个信息，1.该节点是否loaded，2.对于该Key，这一节点存储有几个Value，每一个Value的实效时间是多长。客户端根据信息决定这些节点是否可以存储新的值。
第二步为反向查询，客户端从第一步得到了可存放的节点列表，按照距离Key从近到远的顺序，依次尝试添加Key/Value到这些节点。
S/Kademlia DHT
Kademlia用于完全开放的P2P网络，不提供安全措施，容易受到恶意节点的攻击。基于Kademlia，S/K协议在节点ID中加入隐式身份认证和兄弟广播（sibling Broadcast）。S/K就有能力抵御常见的日蚀攻击（Eclipse attack）和女巫攻击（Sybil attack）。
1.Kademlia面临的攻击
主要分为两类，一类是针对路由表控制网络中部分节点；另外一类是恶意消耗占用节点的资源。前者包括日蚀攻击、女巫攻击、流失攻击（Churn attack）和对抗路由攻击。
- 1.日蚀攻击：如果一个节点在网络能够自由选择它的ID，攻击者在网络中放一些恶意节点，使得信息都必须经由恶意节点传递。恶意节点就能够在网络将一个或几个节点从网络中隐藏掉。要解决日蚀攻击，只要恶意节点不能自由选择ID或者很难通过策略修改其他节点的K-Bucket，这一节点就避免了。但KAD会优先请求K-Bucket中的长时间在线的节点，一旦被攻击节点的K-Bucket是非满的，恶意节点就有机会加入攻击节点的K-Bucket，那么攻击者只要足够长时间在线就能实现攻击了。
- 2.女巫攻击：在开放的对等网络里，攻击者可假冒多个ID，用少数网络节点控制多个虚假身份。KAD网络难以控制节点数量，攻击者可伪造大量虚假节点身份，控制一片网络。通常情况下通过消耗一定的系统和计算资源提高女巫攻击者的成本，当然，这只能改善并不能彻底杜绝。
- 3.流失攻击：攻击者控制一堆节点，一下子把节点从网络中流失，从而导致网络稳定性降低。
- 4.敌对路由：恶意节点收到查询指令后，不按照KAD的要求返回距离Key最接近的网络节点，而是转移给同伙节点，最终导致查询实效。为了避免这种无聊的敌对路由攻击，设计算法在查询时进行并行查询，每一条查询路径不想交，一旦并行查询的路径中有一条不碰到而已节点，就能成功查询了。
2.S/K防护方式
S/K协议针对KAD容易被攻击做出了几个改进：
- （1）为了避免日蚀攻击和女巫攻击，S/K需要节点不能自由选择节点ID，不能大批量生成ID，同时不能窃取和伪装其他节点的ID。肯定就需要通过非对称加密确保节点身份不被窃取，设置一定的计算量障碍，强迫节点进行一定的哈希运算确保不能自由选择和批量生产。
- （2）为避免敌对路由攻击，设计并发不想交的查询路径。
安全的节点分配策略
S/K节点ID的分配策略有三个：不能自由选择，不能大量生成，不能窃取和伪装。
S/K要求每个节点在接入网络前必须解决两个密码学问题。静态问题是：产生一对公钥和私钥，公钥两次哈希运算后，具有C1个前导零。公钥的一次哈希值就是节点的NodeID。动态问题是：不断生成一个随机数X，将X与NodeID求XOR再求哈希，哈希值要求C2个前导零。这样设计，第一个静态问题，保证节点不能再自由选择节点ID，后一个动态问题，提高了大量生成ID的成本。女巫攻击和日蚀攻击将难以进行。
为确保节点身份不被窃取，节点对发出的消息进行签名。其他节点收到消息，验证签名的合法性，然后检查ID是否满足两个难题的要求。验证节点信息的合法性的时间复杂度是很低的，而生成这样一个合法的攻击信息的时间复杂度是很高的，这种不对称就能避免上面三种攻击了。
不想交的路径查询算法
Kademlia协议中，访问α个K-Bucket中的节点，然后排序后，选择前α个继续迭代请求，缺点很明显，如果有恶意节点，查询很可能就会失败。
S/K提出每次查询选择k个节点，放入d个不同的Bucket中。这个d个Bucket进行查找，d条查询路径做到不想交，单个bucket有实效的可能，但是只要d个bucket中有一条查询到了需要的信息，工作就完成了。通过不想交路径查询，解决了敌对路由攻击。
