DHT（分布式哈希表）：一种分布式存储方法的相关研究调研

本文是一篇类似于文献综述的东西，做点前期调研。

随着区块链项目的火热，很多传统技术结合区块链技术都取得了一定程度上的成功。2014 年 Juan Benet 成立了 Protocol Labs 并在开源社区的帮助下发展出了 IPFS[1]：一个去中心化的分布式文件系统。IPFS 的下层构建于对等网络交换协议，其核心是用于索引数据的分布式哈希表（DHT）。

分布式哈希表的研究伊始就是为了开发点对点网络系统，以便将分散在网络中各处的存储资源利用起来。但是在上个世纪末，局限于当时的技术条件，所设计出的半分布式系统没能够很好的达到要求，中央索引服务器容易受到攻击，其次每次搜索都会将查询消息广播给网络中的每个节点，效率非常低；之后诞生的第一个完全分布式系统，设计了一套基于关键值的转送方法，在这个方法中，每个文件与一个关键值相结合，而拥有相似关键值的文件会被相似的节点构成的集合所保管。于是查询消息就可以根据它所提供的关键值被转送到该集合，而不需要经过所有的节点。虽然解决了效率低下的问题，却不能够保证数据在网络中一定被找到。

直到 21 世纪初，最初的四项分布式哈希表技术同时于 2001 年被发表。

相关研究
Kademlia DHT：基于异或度量的分布式哈希表
- 异或度量的距离
- kad 节点维护
- Kad 协议
- 键值对的存储：STORE
- 节点查找：FIND_NODE
- 查找值：FIND_VALUE
- 新节点加入 kad 网络
S/Kademlia：基于密钥的安全路由方法
- 针对 Kademlia 的攻击
- 安全的节点 ID 分配
- 通过不相交的路径进行查找
参考文献

Kademlia DHT：基于异或度量的分布式哈希表

A Peer-to-Peer Information System Based on the XOR Metric.

Kademlia DHT，以下简称 kad，采用了 160 位（SHA-1）长度的 key，网络中的每个节点都有唯一的 key，称为节点 ID，这里可以简单的随机生成长度与 SHA-1 哈希值等长的 160 位作为节点的 ID。每个数据块都有对应的 key（计算 SHA-1），以 <key, value> 的形式存储在距离该数据 key 最近的节点上，这里涉及到两个哈希值距离的概念。

异或度量的距离

kad 通过直接计算两个哈希值的异或，得到的结果称为异或距离，例如：

$$a = 00101101$$
$$b = 11010010$$
$$c = 11011110$$
$$d(a,b) = a \oplus b = 11111111$$
$$d(a,c) = a \oplus c = 11110011$$
$$d(b,c) = b \oplus c = 00001100$$
$$d(a,c) = d(a,b) \oplus d(b,c) = 11110011$$

异或运算有如下的规律：

$$d(x,x) = 0$$
$$d(x,y) > 0,$$ if $$x \ne y$$
$$\forall x,y : d(x,y) = d(y,x)$$
$$d(x,y) + d(y,z) \geq d(x,z)$$
$$d(x,y) \oplus d(y,z) = d(x,z)$$
$$\forall a \geq 0, b \geq 0 : a + b \geq a \oplus b$$

根据异或的运算规律，对于任意一个 x，给定一个距离 $$\delta > 0$$，都能找到唯一的 y，满足 $$d(x,y) = \delta$$。如果将距离的每一个二进制位视为树的左、右子树，1 表示左子树，0 表示右子树，就能够将异或距离度量转变为二叉树的结构，每个 key 都可作为二叉树的叶子节点。如下图取自论文：

kad异或距离度量的二叉树图.png

kad 通过将 160bit 的 key 用二叉树存储，例如图中黑色的点对应 0011，表示该节点距离当前节点的异或距离为 0011，假设当前节点的 key 是 1010，则可以计算出黑色节点对应的 key 为 $$0011 \oplus 1010 = 1001$$。通过二叉树建立的路由表就可以快速地执行存储和查询。

kad 节点维护

每个 kad 节点都要保存一部分路由信息，节点查询时通过节点中继的方式将 kad 联成一张网络。前面提到对于 160bit 长的 key，将位的值映射到二叉树的左右节点上，从而加快查询速度。每个节点在维护路由表时，也是通过类似的方式实现的。每个节点有 160 个桶，称为 $$k$$-buckets，编号分别从 0-159。对每个 $$0 \leq i < 160$$，第 $$i$$ 个 bucket 中保存的是距离当前节点 $$2^i \sim 2^{i+1}$$ 之间的节点信息。如下图 4bit 长度构成的地址空间：

最右边的节点 0000 表示距离自己为 0000 的节点，即保存节点自身信息，向左的每个桶保存距自己 $$2^i \sim 2^{i+1}$$ 之间的节点信息，因此在 4bit 的地址空间中，只需要用 4 个桶就可以保存所有节点，节点信息以 <IP addr, UDP port, Node ID> 的格式保存。

k-buckets 有大小限制，每个 bucket 中存储的节点数不能超过 k（文章中设定 $$k=20$$），如果 bucket 装满，就需要按照一定的规则取舍，当有新节点要被添加到 k-buckets 中时，首先计算新节点到当前节点的距离，根据距离关系从 k-buckets 中取出对应的 bucket，更新规则如下：

若 bucket 中已存在该节点，则将该节点移动到队尾
若 bucket 中不存在该节点：
- 若 bucket 中节点未装满（数量未达到阈值 k），则直接将该节点添加到队尾
- 若 bucket 装满，则检查队首节点是否仍有响应：
  - 若有响应，则将队首节点移动到队尾，新节点丢弃
  - 若队首节点无响应，则丢弃队首节点，将新节点加入队尾

kad 的更新规则基于这样的前提：在线时间更长的节点，之后一小时在线的概率也越高。下图取自论文，横坐标表示在线的时间，单位为分钟，纵坐标表示已在线 $$x$$ 分钟的节点在接下来的 $$x+60$$ 分钟内仍然在线的概率。可以认为，在线时间越长的节点越可靠，越值得信任。

当节点与任意其他节点建立连接（不论是主动请求或被动响应），该节点都将使用上面的方法更新自己的 k-buckets。为了减少无效节点对查询过程的延迟影响，kad 要求定期对未更新过的节点进行存活检测，例如每隔一小时，就将桶中上一小时内未更新过的节点取出，发起 PING 请求，若节点不存在，则将节点信息从桶中删除。

Kad 协议

Kad 协议包含四个 RPCs，分别为：

PING：检测一个节点是否在线
STORE：请求一个节点保存 <key, value> 数据
FIND_NODE：从一个节点请求距离目标 key 最接近的 k 个节点数据，返回的节点数据为 <IP addr, UDP port, Node ID> 的三元组
FIND_VALUE：与 FIND_NODE 的操作类似，如果被请求的节点无 <key, value> 数据，则返回 k 个 <IP addr, UDP port, Node ID> 的三元组；如果被请求的节点保存有对应 key 的 <key, value>，则返回对应的 value

键值对的存储：STORE

当需要存储一个键值对时，首先通过节点查找算法找到距离数据 key 最接近的 $$\alpha$$ 个节点，然后向每个节点发起 STORE 请求对方保存数据即可。$$\alpha$$ 的取值要求满足条件：在当前规模的 kad 网络中，任意选择 k 个节点，这 k 个节点在任意时间内同时不在线的概率几乎为 0。

为了避免过度缓存，键值对有一个有效时间，文章中举例的是 24 小时，即键值对在存储到一个节点后，过 24 小时后就会将该键值对删除。数据提交者需要定期向存储有这些数据的节点发起“续存”的请求，即更新该键值对的有效时间，以保证该数据不会被到期删除。另外 kad 还建议对距离 key 越近的节点，该节点保存的对应数据有效时间越长。采用这种定期更新的方式还有另一个好处，kad 网络中随着时间的推移，会有新的节点加入，同时会有节点离开，因此定期更新可以保证数据尽可能在距离 key 最接近的节点集合上。

节点查找：FIND_NODE

对于已知的 key，从当前的 kad 网络中找到距离该 key 最接近的 $$\alpha$$ 个节点所对应的网络信息（三元组 <IP addr, UDP port, Node ID>）的过程称为 kad 节点查找。kad 采用递归的方式进行节点查找，过程如下：

查找发起者从自己的桶中筛选出距离目标 key 最近的 $$\alpha$$ 个节点信息
发起者向筛选出的 $$\alpha$$ 个节点同时发起异步查询请求
每个被查询者收到请求后，从自己的桶中筛选出距离距离目标 key 最接近的 $$\alpha$$ 个节点集合返回给查找发起者
发起者再从所有收到的节点集合以及自己已知的节点集合中，筛选出距离目标 key 最接近的且未请求过的 $$\alpha$$ 个节点，重复步骤 2，期间没有响应的节点将被直接排除掉
重复步骤 2,3,4，直到无法获得比查找发起者已知的 $$\alpha$$ 个节点更接近目标节点为止

查找值：FIND_VALUE

查找值时，通过 FIND_VALUE 不断逼近距离目标 key 最接近的节点，一旦查询过程中有任意一个节点返回了所查找的 value，FIND_VALUE 的查询过程就结束。考虑到加快查找的效率，查找结束后，发起者可以将 <key, value> 缓存到距离 key 最接近的但是没有存储该键值对的数个节点上。

新节点加入 kad 网络

通过任意途径，获得一个已经在 kad 网络中的节点信息，将该节点加入桶中
向该节点发起 FIND_NODE 的请求，查找距离当前节点自身 ID 最近的 $$\alpha$$ 个节点
递归过程中不断刷新自己的 k-buckets

Kademlia 原文中还讨论了实现上的一些细节，例如通过一些方式减少查询所需时间，以加快查找速度等，这里不深入讨论。

S/Kademlia：基于密钥的安全路由方法

Kademlia 方法很容易被攻击，Ingmar Baumgart 和 Sebastian Mies 在 Kademlia 的基础上，构建了一套基于密钥的安全路由协议，即 S/Kademlia，以下简称 S/kad，它通过在多个不相交的路径上使用并行查找来抵御常见的攻击，通过一系列约定限制自由生成节点 ID 并引入可靠的对等体广播，来达到安全路由的目的。

针对 Kademlia 的攻击

攻击底层网络：攻击者可能能够侦听或修改任意数据包，对底层的攻击可能导致拒绝服务攻击
攻击覆盖路由
- 日蚀攻击：攻击者在网络中部署数个对抗节点，使得部分消息在至少一个对抗节点上路由，从而使攻击者能够控制覆盖网络的一部分
- 女巫攻击：攻击者在网络中部署大量节点，直到能够完全控制整个 kad 网络的一部分
- 流失攻击：攻击者通过在网络中所控制的某些节点，引发高流失，直到网络稳定性失效
- 对抗路由攻击：被攻击者控制的节点在响应查询请求时，返回对抗路由的信息（生成最接近查询 key 的节点 ID），使得请求发起者无法正确找到目标
其他攻击
- 拒绝服务攻击：攻击者消耗节点的资源，使其无法向 kad 网络提供服务
- 对数据存储的攻击

安全的节点 ID 分配

由于 kad 随机任意生成 Node ID 的方式可以引发多种攻击，S/kad 使用散列公钥的方式生成 Node ID，并使用公钥对节点交换的消息进行签名。

弱签名：弱签名不会签署整个消息，它仅限于 IP 地址、端口和时间戳
强签名：签署消息的全部内容，确保消息的完整性

密钥对（节点 ID）的生成：

监督签名：签名的公钥由可信赖的证书颁发机构签名
加密拼图签名：在没有值得信赖的证书颁发机构的情况下，需要通过加密拼图来阻止日蚀和女巫攻击

S/kad 的加密拼图方法分两个步骤，下图取自 S/kad 原文，左图是静态的加密拼图方法，右图是动态加密拼图方法，如果节点收到签名消息，它可以首先验证其签名，然后检查加密拼图是否已解决。

静态加密拼图
1. 生成密钥对 $$S_{publ}, S_{priv}$$
2. 计算 $$P:=H(H(S_{publ}))$$
3. 判断 $$P$$ 的前 $$c_1$$ 个 bit 是否都为 0
4. 若步骤 3 满足条件，则 $$NodeID:=H(S_{publ})$$，否则转到步骤 1
动态加密拼图
1. 由静态加密拼图生成了 $$NodeID:=H(S_{publ})$$
2. 选择一个随机数 $$X$$
3. 计算 $$P:=H(NodeID \oplus X)$$
4. 判断 $$P$$ 的前 $$c_2$$ 个 bit 是否都为 0
5. 若步骤 4 满足条件，则动态拼图（$$NodeID, X$$）完成，否则转到步骤 2

通过不相交的路径进行查找

kad 直接通过迭代的方式查找距离目标最近的 k 个节点，S/kad 使用 $$d$$ 不相交路径，以提高其在具有对抗节点的网络中的查找成功率。

发起者从路由表中筛选出 k 个最接近目标的节点，并将其加入查找桶内
对于查找桶内的每个节点，查找是并行独立进行的，且每个节点只被查找一次，以确保查找路径不相交
查找不会在单个节点上收敛，key 的所有邻居节点都知道目标 key 的完整的 s 个邻居节点

参考文献

[1] Benet J . IPFS - Content Addressed, Versioned, P2P File System (DRAFT 3)[J]. Eprint Arxiv, 2014.
[2] Ratnasamy S P . A Scalable Content-Addressable Network[C]// Conference on Applications. ACM, 2001.
[3] Stoica I, Morris R T, Karger D R, et al. Chord: A scalable peer-to-peer lookup service for internet applications[J]. acm special interest group on data communication, 2001, 31(4): 149-160.
[4] Rowstron A I, Druschel P. Pastry : Scalable, decentralized object location, and routing for large-scale peer-to-peer systems[J]. Lecture Notes in Computer Science, 2001: 329-350.
[5] Zhao B Y, Huang L, Stribling J, et al. Tapestry: a resilient global-scale overlay for service deployment[J]. IEEE Journal on Selected Areas in Communications, 2004, 22(1): 41-53.
[6] Maymounkov P, Mazières D. Kademlia: A Peer-to-Peer Information System Based on the XOR Metric[C]// Revised Papers from the First International Workshop on Peer-to-peer Systems. 2002.
[7] Baumgart I , Mies S . S/Kademlia: A practicable approach towards secure key-based routing[C]// Parallel and Distributed Systems, 2007 International Conference on. IEEE, 2008.
[8] Pouwelse J, Epema D, Sips H. The bittorrent p2p file-sharing system: measurements and analysis[C]// International Conference on Peer-to-peer Systems. 2005.

神楽坂雪紀的电子后花园