在之前的章节中我们说过，当k-bucket满之后，如果有新的节点落入，则需要检查队列中最久未更新的链接是否依然有效，如果有效，则新节点丢弃，老的节点保留，如果老的节点已经网络不可达，那么则把老的节点删除，新的节点加入到队列的队尾。但是这个实现在具体的产品应用中会产生很多消息，使得网络的消息负载加重，为了缓解这个现象。新加入的节点其实是被加入到了替补队列，等以后该节点收到查询消息之后，也就是说在收到其他必须响应的有实际使用价值且不得不做的查找指令的时候，再将这些老的节点中，没有响应的节点删除，然后从替补队列中选择一个节点加入到k-bucket队列。替补的策略是，替补节点按照时间排序，时间最近的节点拥有最高的替补权限，有点像足球比赛的替补队员。

另外由于kademlia使用udp作为实现协议，因此存在报文丢失或者网络拥堵导致的报文延迟，当节点没有及时响应，则不再持续发送rpc状态检查，如果连续5次没有做出正确的响应，也不是直接将节点从k-bucket中删除，而是将该节点标注为待观察，这样做的目的是防止因为自己的网络出现闪断，而将本节点内的所有路由信息全部删除，当网络恢复的时候，将不得不重新从零开始更新路由信息。

为了加快查找速度，具体的kademlia实现过程中往往不用二叉树，而是使用2^b次方分叉树来降低树的高度和加快查找速度，但是这样需要增加k-bucket路由表的大小，通过这种牺牲存储来加快路由的查找速度。

Kademlia路由协议面临的安全攻击

1,底层攻击，由于该路由协议没有提供任何安全策略，因此任何恶意节点可以任意篡改本层的数据，基于本路由协议的上层协议需要知晓这个设计原则。同时我们默认假设节点可以假冒任意IP地址并且并不提供报文的授权使用机制，因此对该协议的底层攻击可能会形成对上层协议的DOS攻击。

2,上层协议攻击，分类归纳为以下几种：

a,日食攻击

通过在某一个或者几个恶意节点周围放置恶意节点，使得正常节点的所有路由消息都至少经过一个恶意节点，这样使得攻击者可以操控部分上层协议的网络，从而达到将部分正常节点从网络中屏蔽的目的。不过这个问题是可以容易防范的，如果节点的ID是不能随意生成，并且新节点影响其它节点路由表的方式是受控的，那么这个问题可以得到解决，从前面的章节我们已经知道，kademlia的k-bucket里面节点的替换原则是，更青睐长期在线的老节点信息，因此较为安全的避免了此类攻击。

b,女巫攻击

在一个完全去中心化的网络中，没有方案可以控制节点ID的生成，这样攻击者可以生成一定数量的恶意节点ID来达到控制网络的目的，经过证明，这种攻击是无法完全杜绝的，只能通过增加生成ID的成本来控制这种攻击带来的危害。中心化的系统可以通过支付一定费用并绑定现实世界的个人来解决这种攻击问题，但是区块链世界就必须绑定一定的代币并且付出一定的计算机资源，以此来提高攻击网络的成本。

c,流失攻击

如果攻击者拥有一定数量的节点并且使得网络的使用达到一定的失败率，那么会有非恶意节点的退出，劣币驱逐良币，这样整个网络就会失去价值，不过这种攻击对kademlia的攻击影响有限，因为本协议更倾向于长久在线的老的节点，因此除非初始的多数节点都是恶意攻击者，否则流失攻击对系统影响有限。

d,恶意路由攻击

如果一个节点不响应查询或者不路由任何数据，那么其他节点就会将其从路由表中删除，因此一个恶意节点攻击网络的方式就只能是广播恶意的路由信息，比如一个恶意节点会返回某一个被查找节点ID附近的节点，而不是被查找节点本身，这样查询者就无法正确的找到目标节点，通过改善查找算法，通过查找多条没有交点的，能够到达目标节点的路径，来规避此类攻击，只要其中一个路径上没有恶意节点，那么就可以成功找到目标节点。查找成功的概率如下:

我们将该概率公式拆解分析如下：

公式1中，m表示恶意节点个数占总节点数的比例，那么公式1表示非恶意节点，即正常节点的比例。

公式2中i表示从本节点到目标节点需要经过的节点的个数，即点与点之间的路径长度，那么公式2表示成功通过正常节点传递路由信息的概率，即在路径长度为i的情况下，不被攻击的概率

公式3显然表示在恶意节点比例是m，且路径长度是i的情况下被攻击的概率

公式4中，d表示不相交的路径的个数，那么公式4表示在有d个不相交路径的情况下仍然被攻击的概率

公式5表示在有d条不相交的情况下成功躲避攻击的概率

至此躲避攻击成功的概率解释完毕，但是在一个网络中，从某点到另外一点的路径长度是i的情况是需要一定分布概率的，下图以实例的方式解释hi的概念。

上图中，i表示路径的长度，中间表示路径为i的各种可能的路径，因此hi就表示长度为i的概率分布，即本长度出现的次数除以总所有长度之和，hmx表示最大的个数不为0的长度，公式9和10给出了具体的解释。

由此可以证明，上述公式表示了在恶意节点比例为m，路径长度为i，不相交路径为d的情况下成功躲避恶意节点攻击的概率。从上面的公式可以看出，即使出现一定规模的恶意节点，即m值非常可观时，通过不相交路径查找算法可以有效规避这类攻击。

3,其他攻击。

a,DOS攻击

攻击者可以通过快速消耗掉某些节点的计算机资源来达到dos攻击的目的，因此在设计路由协议的时候，要对资源的申请和使用做一定的限制。

b,存储攻击

因为他们的路由协议层是为IPFS这样的存储协议提供基础服务的，因此我们的上层业务需要对数据进行冗余存储，以避免丢失数据的攻击得逞。

本节的内容简单介绍到这里，对于攻击的解决方案在下一节继续讲解。