本节我们介绍S/Kademlia路由协议，解决上一节提到的各种安全问题。
首先是更加安全的节点编号生成规则。如果我们能够限制参与者随意选择节点ID的情况，那么我们就可以规避日食攻击，因为一旦ID的生成规则不被操控，那么就很难在被攻击节点周围形成有效的遮挡，无法到达屏蔽节点的目的。如果设计一个规则，使得攻击者很难廉价的生成大量的节点编号，那么就可以有效的规避女巫攻击。同时如果对节点的ID进行授权和检验，那么没有人可以仿冒或者偷走别人的节点ID。
可以通过将IP地址和端口进行hash运算或者对节点的公钥进行hash运算来达到对节点进行有效性检验的目的，但是对于NAT网络来说，很多共享网络的节点对外的IP地址是相同的，并且也无法通过IP地址的方式来限制节点的生成个数，因此我们采用后者，对一个公钥进行hash来生成节点的ID。通过这种方式生成节点之后，我们可以对节点与节点之间的消息进行签名。
签名分为两种，一种是弱签名，一种是强签名。弱签名只是对消息的部分内容进行签名，比如节点的IP地址，端口号和时间戳。时间戳指定了签名的有效时间，这个有效时间可以预防动态IP的接力攻击问题。这类签名可以用于查找节点和PING命令这些消息完整性要求不高的场景。
强签名是对节点之间的全消息进行签名，这保证了消息整体上的有效性，可以有效抵御中间人攻击，并且通过在消息中添加随机数，可以抵御接力攻击。
为了达到抵御女巫攻击和日食攻击的目的，还需要一些机制来限制设计节点ID的生成规则。有2种方式可以达到这个目的，一个是通过中心化的证书认证机构来实现，另一个是在生成节点编号时通过解答加密谜题的方式实现。
通过中心化的CA证书方式，可以有效解决项目早期，节点较少时的网络女巫攻击问题。通过评估早期公链早期节点数量来决定是否采用此方案。
在纯粹的去中心化网络中，没有中心认证机构的情况下，需要通过提高节点生成ID的成本和难度来预防女巫攻击和日食攻击。在我们的改进方案中，我们采用了2种解答谜语的方式，分别来解决女巫攻击和日食攻击的问题。
1，首先生成一个非对称密钥对；2，然后对公钥进行两次哈希操作；3，检查生成的hash值前C1个比特位是否为0，如果不是，从1开始重新操作，如果满足条件，则4，将节点的ID编号设置为公钥的一次hash值。以上4步骤可以预防节点ID的任意生成，因此可以防止日食攻击。
5，当节点ID生成之后；6，生成一个随机数；7，通过节点与随机数计算距离之后再计算一次hash；8，检查一下得到的hash值的前c2比特位是否为0，如果不满足条件则继续选择随机数，如果满足条件则9，标记NodeId和随机数X。如果有恶意攻击者要生成大量的满足NodeId和随机数x的信息，需要消耗巨大的计算机资源，因为这个函数是不可逆的，要找到这样的一些值有点类似挖矿的过程，是很消耗资源的。因此可以有效的解决随意生成节点ID信息来发动女巫攻击的问题。
第二，可靠的兄弟广播。
在前面的章节中我们知道，通过k个最接近key-value对中key的距离最近的节点来冗余存储value，我们可以实现数据的安全存储，并且这个k还是k-bucket的中的k的值，即每个距离等级下最多存储的节点的个数。也是用于冗余存储数据的距离key最近的节点的个数。我们现在考虑某个节点都保存w*s个距离最近的兄弟节点列表，这个列表可以确保每个节点知道至少S个距离某个ID的兄弟节点。下面我们来寻找一个w的值，并且证明一个节点可以有很高的概率来获取其兄弟节点的ID。
1表示计算2个节点之间的距离的方式为XOR即前面章节讲到的异或计算。
2表示任意两个节点x,y。y的id值比x小的概率
3，表示全网节点个数
4，表示网络节点ID的比特位长度
5，表示邻接的两个节点，即两个节点之间没有其他节点的情况下，平均的距离。分子为ID的取值空间，分母是当前网络中节点的个数
6，表示任意两个节点直接，需要u个节点才能联通的情况下在，这个两个节点之间的平均距离
7表示任意两个节点x,y之间经过的节点个数
8，表示在距离限制为dN(u)的情况下，x与y直接需要经过的节点个数的数学期望值是u，
9表示的是落入x,y之间的节点个数的数学期望。
公式10表示网络中1个节点落入x，y之间的概率，取决于他们的数学期望值与全网节点个数的比例。
公式11表示任意2点x,y之间少于s个节点的概率，或者说，少于s个节点落入x,y之间的概率。
公式15表示i个节点录入x,y之间的概率，公式16表示剩下的N-i个节点没有落入x,y之间的概率。
公式13表示的是排列组合中，组合的计算公式，即从N个节点中选出i个节点落入x,y之间的可能组合个数
公式14表示将落入x,y之间节点个数从0到s-1个这s个情况的所有概率累加起来，就能满足条件的概率
我们在公式12中，将u改为与S个节点相关一个线性公式，并通过实验来计算合适的c的值，以便在某个固定的S个兄弟节点的情况下，可以大概率的找到一个兄弟节点ID，实验情况下如下，在N为10的10次方的节点节点个数，n为160个比特位长度的情况下，其实验结果如下：
当w>=2*c>=5的情况下，可以较好的满足可靠兄弟节点的广播需求。并且维护兄弟节点的开销比较小。
第三，路由表的维护，在前面章节中我们提到过，在路由消息的过程中，我们会根据最新的消息来维护本地路由信息，如果是查找节点或者存储数据，那么我们都要执行相关的节点查询操作，根据查找消息的返回结果和响应情况来更新本地的路由信息。在我们的改进方案中，我们会根据消息是否签名来决定是否更新本地的路由信息，如果是弱签名或者是强签名，则可以根据一定的策略和情况来决定是否更新本地路由，如果消息未签名，则不用于更新本地路由。
第四，通过寻找d个不同相交的路径，来并发的查找节点，如果按照以前的方式，我们会在k个节点中人选a个节点来询问关于目标ID的信息，并逐渐的靠近目标节点ID，查找出k个距离目标ID最近的节点信息，这个过程中如果遇到恶意节点，则签名的递归查询就前功尽弃。为了解决这个问题，通过将k个靠近目标ID的节点信息查询出来并寻找D个不相交的到达目标ID的路径，然后同时发出寻找命令，那么就可以很好的规避恶意节点的攻击，只要D条路径中有一条路径上是安全的，没有恶意节点参与的，那么就可以成功完成查找动作。
综上所述，本节是路由层协议深入分析的完结篇，我们从路由的基本要求，路由的基本实现原理，以及如何安全的路由这些角度，分析了为了路由层协议应该具有的功能和实现原理。如果有兴趣的同学，可以参考IPFS的路由层代码，如下图;
