王子亭的博客

Kademlia协议(模型)是被电驴，BitTorrent所采用了的，基于异或距离算法的分布式散列表(DHT), 它实现了一个去中心化的信息储存与查询系统。

Kademlia将网络设计为一个具有160层的二叉树，树最末端的每个叶子便是一个节点，节点在树中的位置由同样是160bit的节点ID决定。

每个bit的两种可能值(0或1), 决定了节点在树中属于左面还是右面的子树，160层下来，每个节点ID便都有了一个确定的位置。

Kademlia使用独特的异或距离算法来计算节点间的距离，异或是一种简单的数学计算，它有很多独特的性质，这些性质在之后会为我们带来方便：

自己与自己的距离为0:
x ^ x = 0
不同的节点间必有距离:
x ^ y > 0
交换律，x到y的距离等于y到x的距离:
x ^ y = y ^ x
从a经b绕到c, 要比直接从a到c距离长:
a ^b + b ^ c >= a ^ c
下面两个是资料上提到的，似乎很重要，但我不大理解他们的含义:
a + b >= a ^ b
(a ^ b) ^ (b ^ c) = a ^ c

在Kademlia中，异或(距离)算法具有单向性(或者说一一对应关系)，即给定一个节点和一个距离，必定存在唯一一个相对应节点。包括距离算法在内的，Kademlia中大部分的概念，都既有算术上的意义，又可以在节点树上表现实际意义。

事实上，节点间距离反映的就是节点ID中比特的差异情况，而且越靠前的比特权值越大。或者说是反映节点在树中相隔了多少个分支，需要向上多少个树节点才能找到共同的祖先节点。

Kademlia中使用了名为K-桶的概念来储存其他(临近)节点的状态信息，这里的状态信息主要指的就是节点ID, IP, 和端口。

对于160bit的节点ID, 就有160个K-桶，对于每一个K-桶i, 它会储存与自己距离在区间 [2^i, 2^(i+1)) 范围内的节点的信息，每个K-桶中储存有k个其他节点的信息，在BitTorrent的实现中，k的取值为8.

下表反映了每个K-桶所储存的信息

放在节点树上，即每个节点都更倾向于储存与自己距离近的节点的信息，形成 储存的离自己近的节点多, 储存离自己远的节点少 的局面。

从上表可以看出，在1-15这个范围内的节点，只要发现，就会被100%地储存下来，而离自己距离在1000左右的节点，只会储存13%.

对于一个节点而言，K-桶就代表着节点树上那些未知的节点(其实除了自己都是未知的)构成的子树，160个K桶分别是具有1到160层的子树，由小至大。对于节点ID, 160个K-桶分别储存着节点ID前0到159个bit和自己一致的节点。

K-桶中的条目(其他临近节点的状态信息)排序的，每当收到一个消息(如查询)时，就要更新一次K桶。

首先计算自己与对方的距离，然后储存到对应的K-桶中，但如果K-桶已满(前面提到每个K-桶储存有k=8个条目), 则会倾向放弃储存，继续保持旧的节点信息(如果还有效的话). 除了距离外，Kademlia更倾向于与在线时间长，稳定的节点建立联系。

这是因为实践证明，累积在线时间越长的节点越稳定，越倾向于继续保持在线，即节点的失效概率和在线时长成反比。

这样还可以在一定程度上抵御攻击行为。因为当大量恶意的新节点涌入时，大家都会选择继续保持旧的节点信息，而不是接受新的。

除此之外，还需要定时检查K-桶中的节点是否任然在线，及时删去已失效节点。

Kademlia协议仅定义了四种操作：

• PING: 探测一个节点是否在线
• STORE: 令对方储存一份数据
• FIND NODE: 根据节点ID查找一个节点
• FIND VALUE: 根据键查找一个值(数据)

当查找一个节点时，首先计算自己与目标节点的距离d, 然后将 log₂d 向下取整，找到对应的K-桶，从这个K-桶中选取a个节点(在BitTorrent的实现中取值为3), 向它们发送查询。

收到查询的节点同样计算距离后从自己的对应K-桶中选取a个节点返回给查询者。查询者不断重复这个过程，知道找到目标节点，或无法再找到更近的结果。

很多资料将这个过程描述成是递归的，但我觉得这里认为它是迭代的更为恰当。

因为每个节点都更倾向于储存距自己近的节点的信息，而整个网络又是一个二叉树，因此每次查询都会至少取得距离减半的结果，对于有N个节点的网络，至多只需要 log₂N 次查询。

当进行 FIND VALUE 操作时，查询操作是类型的，每份数据都有一个同样是160bit的键，每份数据都倾向于储存在与键值距离较近的节点上。

当上传者上传一份数据时，上传者首先定位几个较为接近键值的节点，用STORE操作要求他们储存这份数据。

储存有数据的节点，每当发现比自己与键值距离更为接近的节点时，便将数据复制一份到这个节点上。

当一个新节点欲加入网络时，只需找到一个已在网络中的节点，借助它对自己的节点ID进行一次常规查询即可，这样便完成了对自己信息的广播，让距自己较近的节点获知自己的存在。而离开网络不必执行任何操作，一段时间后，你的信息会自动地从其他节点被删除。

毫无疑问，Kademlia要比我之前为零毫秒设想的网络模型优秀得多，更为彻底地实现了去中心化，弱化了关键节点失效对整个网络的影响。而电驴和BitTorrent的实践也证明了kademlia是具有相当的可行性的。

Kademlia的精妙之处在于它选择了异或运算作为计算距离的依据，异或运算不仅具有算术的意义，在二叉树式的网络模型中，同样具有实际意义，同时任何情况下都在强调距离的概念，让节点间通过距离来聚合起来。

在上一篇日志的末尾，我便在思考如何来聚合节点，现在通过Kademlia, 我算是找到了。下一步我想思考的是，既然以上是Kademlia的优势，那么它的弱势在哪？哪些地方存在不足？

在一年多以前，我曾计划写一个系列，关于密码学基础的科普文章。但当我写完第一篇，散列算法的时候，便觉得自己功力尚浅，仍需修炼。今天重新捡起来，写下去。

公钥密码学，也称非对称加密，可以说是现代密码学的基础设施之一。公钥密码学也可以说标志着现代密码学的诞生，让密码学从政府，军方之间的斗智斗勇，成为了具有严谨数学基础的学科。

目前使用最为广泛的公钥加密算法：RSA, 其发明者因此获得图灵奖(计算机领域的最高奖项).

应该说密码学一直以来和军队，战争都是密不可分的。

我们设想这样一个场景，同属一个阵营的两个部队，被相隔一段距离，其间都被地方部队占领，这意味着他们之间通过信使传递的所有信息，都是可能被敌人监控(阅读)的。

那么如何在事先没有沟通的情况下安全地交换信息呢？

对于经典的对称加密算法(对等加密, 共享密钥加密), 这是很难做到的。因为对称加密需要一个密钥(密码), 而两个部队事先是没有沟通过的，没有对密钥达成共识。

而且他们现在也不可能再协商密钥，因为现在他们所有的通信都是被监控的了，一旦他们在这种环境下协商密钥，那么敌人也会知道密钥，便也能解密他们之后传送的加密信息。

对称加密对加密和解密都使用同一个密钥，我们可能需要的是一种针对加密和解密，使用不同密钥的加密算法，这便是非对称加密的含义。

试想，部队A可以生成一对密钥，分别用于加密(公钥)和解密(私钥), 然后将公钥发送给部队B. B便可以使用这份密钥对信息进行加密，再将加密信息发送回A了。

这里的公钥，即使被敌人获取也没有关系，因为这里的公钥，仅仅能够用于加密数据，而唯一可以解密数据的私钥，自始自终都在A手中，从未公布出去。

这样一来，A和B便可以在受监控的情况下，没有实现沟通，便能安全地交换信息了。

让我们进一步设想，如果敌人可以篡改A和B之间发送的信息呢？

例如当A发送公钥给B的时候，敌人将公钥拦截下来，自己生成一堆公私钥，将自己的公私钥发送给B. 相当于敌人冒充了B与A建立联系，建立了两个加密通道，分别是从A到敌人，和从敌人到B.

这样以来，敌人便可以在两个通道之间，监控到A和B通信的明文了，同时敌人还可以任意篡改A和B之间发送的信息，即使它们已经被加密。

这便是经典的“中间人攻击”. 应该说如果A和B没有事先沟通过，而且没有一个可信的第三方，那么这个问题几乎是无解的。

但如果允许A和B事先进行沟通，该如何在敌人可以篡改信息的前提下，安全地交换信息呢？

其实这个问题很好解决，只需在实现沟通时互相交换密钥即可，其后敌人(中间人)便无法再进行冒充了，因为密钥根本没有在这时被交换。

然而更为通用的做法是使用“数字签名”，数字签名恰好是公钥加密的逆运算。即将加密密钥保密，而将解密密钥公布出去，使得只有自己可以加密信息，而任何人都可以解密信息。

要实现数字签名，只需自己将要签名的信息(通常是一个散列摘要值)加密并公布即可，其他人可以认为，凡是用你公布出去的解密密钥能解密的信息，都是你自己加密(签名)过的。

这样便可以识别一段信息，是否真正地由其宣传的发信人所发送，识别出被中间人所篡改的信息。

在前面的情况下，我们还需要考虑的是“重放”攻击，即中间人虽然不知道A和B传输的实际内容，但却可以将其中的一份信息复制两遍甚至更多，已达到干扰的目的。通常应对重放攻击只需在加密信息中约定一个递增的编号，或者时间戳即可。

下面我们来讨论公钥加密算法(RSA)背后的数学原理，本人数学很渣，只能大概谈谈应用RSA时需要了解的一些原理，更详细的数学原理请围观各种大牛的文章，如： http://www.matrix67.com/blog/archives/5100

RSA基于这样一个原理：计算两个数的乘积是十分容易，但对一个数进行因式分解，得到这两个数却十分不易。

可能这个原理并不直观，甚至有点反常识，但RSA选择的两个数的乘积，都是2^2048这样数量级的数字，换算为十进制，那么将会是1后面跟6000多个0.

直到目前，对大数进行因式分解仍是一个难题，数学家还没有找到比试除法更高效一点的方法，因此在目前，对一个足够大的数进行因式分解可以认为是一项不可能完成的任务。但也不排除今后有数学家发明进行因式分解的简单方法，届时，RSA算法，甚至整个密码学，整个世界都会坍塌。

有点虎头蛇尾啊，本来打算最后举一个RSA计算的例子的，结果还是写不下去 …

TCP和UDP是传输层最常用的两种协议，几乎每个应用层协议都要在它们中间选择一个。同样，本文不详述其协议本身，而是着重对比。

显然如果我要是说，TCP是面向连接的可靠传输协议，而UDP无连接且不可靠，那么我这半个月的书算是白读了。

UDP仅仅是在IP的基础上提供了多路分解和多路复用，以及差错校验，十分简单——从UDP报头就能看出。

而TCP提供的功能则要复杂得多，首先为了保证数据能够正确、有序地到达，TCP使用了“流水线”“积累确认”的模型。

TCP会对每个数据报进行编号，同时在每个数据报中，都包含一个“确认序列号”的字段，用来指明上一个从对方正确接收的数据报。一旦接收方在一定时间内没有发送相应的确认序列号，那么发送方就会重传这些数据报。

数据报的发送行为是“流水线”(与之对应的是“逐一确认”)的，即发送方不逐一等待确认，而是一次发送若干个数据报，换句话说，发送和确认的行为是异步的。

而在这里，确认行为是“积累”(与之对应的是“选择重传”)的，也就是说，一旦一个数据报丢失了，那么在这之后的所有数据报都会重传。

TCP还提供有流量控制和拥塞控制的功能。

流量控制即在每个数据报中，都会指明自己的缓冲区还能容纳多少数据，发送方将根据这个值来协调同时存在于“流水线”上的数据量。流量控制保证了，应用层程序不会因为缓冲区不足而无法接收到新数据。当缓冲区满了以后，发送方会暂停发送。

拥塞控制即TCP会根据网络情况，自动调整发送速率。典型策略是每发送成功一个包，即提高一些发送速率，每出现一次重传，即降低一些发送速率。

同时TCP还使用了“慢启动”模型，即建立连接后默认速率是最低的(1MSS/RTT, MSS即最小TCP分段, MTU减去TCP报头), 然后逐渐提升发送速率。

这样可以保证重传行为始终是受控的，不会因为网络不稳定而出现大量重传的数据报而堵塞线路。

TCP往往用于要求数据分毫不差的应用中，比如网页(HTTP), 文件传输(FTP), 电子邮件(SMTP/POP3), 终端(Telnet)等等。

而UDP往往用于可以容忍数据丢失的协议，如流媒体应用, 语音和视频通话等，这些应用即使出现数据丢失，影响也是瞬间的，可以容忍的。

那么为什么这些流媒体应用要选择UDP呢？换言之，TCP在保证可靠传输的同时又牺牲了什么呢？

对于流媒体应用，临时的数据丢失是可以容忍的，但绝不能容忍的是延迟。

为了建立一个TCP连接，TCP需要进行“三次握手”，只有当三次握手完成后，才会正式传输数据。这样一来，建立连接并传输一份数据，至少需要2个RTT(往返延迟), 如果考虑发送端确认的话，那么需要2.5个RTT.

在断开连接时，TCP还需要“四次挥手”，又会消耗掉至少1.5个RTT.

UDP则没有这个顾虑，直接发送数据，只需0.5个RTT.

UDP协议本身保证了，当应用层通过Socket将数据传递给传输层时，UDP会立刻将数据报发送出去。而TCP不提供这个担保，TCP因为提供有流量控制和拥塞控制服务，TCP会自行选择在“合适”的时候再发送数据报。

流媒体应用在需要低延迟的情况下，还需要尽可能的带宽保证。

尤其是因为TCP的拥塞控制服务，注定了TCP不能够尽可能利用带宽，当网络出现堵塞时，TCP的拥塞控制会降低发送速率，让出带宽，直到网络恢复。

而UDP只会简单粗暴地继续发送数据报，很多情况下，TCP都在为UDP让出带宽，这也算是劣币驱逐良币的一种表现，据说有大牛在研究给UDP加上拥塞控制。

总结：那些宁可在UDP上自行实现TCP的部分功能的应用，主要原因在于希望避开TCP的拥塞控制，以便于尽可能地利用带宽。