-1-
基于 Kademlia协议的混合式可信 P2P网络研究1
摘 要：随着 P2P 技术的广泛应用，其在充分发挥优越性的同时，也暴露出一些应用的弊
端。由于 P2P 网络的匿名性、异构性以及自治性等特点，导致了 P2P 网络中存在许多安全
问题。目前对 P2P网络的研究重点主要集中在基于 DHT的资源定位和基于节点间信任机制
的交互安全上。本文通过对 P2P网络及网络中点间信任关系的研究，提出一种基于 Kademlia
协议的混合式可信 P2P网络模型，并对改进的 P2P网络抵抗恶意攻击的能力进行了验证。
关键词：P2P网络；Kademlia；混合式；信任计算
1 引言
随着 Internet发展的日益成熟，传统的 Client/Server模式暴露出一些负面问题，如大量
客户端资源的闲置、服务器带宽限制、网络扩展投资大、服务器维护成本高等，这些不利因
素促使网络从集中式的、以中央服务器为中心的服务模式逐渐转入一种分布式的、向边缘终
端设备扩散的模式，P2P技术应运而生。
P2P以分布式技术为基础，打破了传统的 Client/Server模式，每一个节点都处于对等的
关系，同时扮演服务器与客户机的角色，充分利用了电脑上的边缘性网络资源，节点之间通
过直接互联实现信息、处理器、存储甚至高速缓存等资源的全面共享，而无需依赖集中式服
务器的支持，以其资源利用率高、网络扩展能力强、网络性能好、信息流动速率高、搜索功
能强等优势，广泛应用于分布式计算、搜索功能、文件交换、协同工作等各个领域。
P2P技术的优越性是不言而喻的，目前，P2P技术研究工作主要集中在三方面，即安全
问题、搜索资源算法和拓扑结构。而安全问题是制约 P2P技术发展面临的主要问题。P2P网
络中普遍存在着合谋、欺骗、诋毁、冒名、潜伏、重入、搭便车等恶意行为，而由于 P2P
网络中节点的匿名性，对于这些安全问题的管理和控制成为困难，传统集中式网络模型中的
安全解决方案（如 PKI机制）已经不再适用于 P2P网络，需要在 P2P网络节点之间建立一
种有效的信任机制来解决这些安全问题。另外，基于 DHT技术的 P2P路由搜索算法将所有
的网络节点视为平等的对等体，但在实际网络中，由于节点异构性的普遍存在，这种绝对的
对等关系事实上不存在的。
本文基于以上几点考虑，提出一种基于 Kademlia协议的混合式可信 P2P网络，在节点
的交互过程中充分考虑了网络中节点的信誉度、网络节点之间性能的差异，选取优秀的节点
进行交互，排除恶意节点的干扰和破坏，从而保证了整个网络的可用性。
2 全分布式的 P2P网络路由算法
主流的全分布式路由算法
P2P 网络的路由机制分为两大类，即：非结构化的 P2P 网络资源搜索机制和结构化的
P2P网络资源搜索机制。
非结构化的 P2P 网络资源搜索机制采用了随机图的组织方式，具有较好的容错性和可
用性，支持复杂查询，但是随着联网节点的不断增加，其缺点是明显的：由于没有一个确定
1本课题得到北京市自然科学基金（No. 4092029）、教育部博士点基金(20060013007)的资助。
-2-
的拓扑结构的支持，其网络资源发现效率很低，由于采用 TTL（Time-to-Live）、泛洪
（Flooding）、随机游走或选择转发的算法来实施资源定位，其路由直径不可控，可扩展性
差，且大量的泛洪搜索势必会造成网络流量的急剧增加，严重影响网络的可用性，资源发现
的效率无法保证。
结构化的 P2P网络资源搜索机制采用 DHT（分布式哈希表）技术进行网络资源的定位。
其网络层次模型如图 1所示：
图 1 DHT技术的网络层次模型
DHT技术相当于在网络中的物理节点上覆盖一层逻辑网络，加入单独的 DHT层来进行
P2P网络资源定位和查找[1]，其核心思想是将网络资源表示为它将每个资源索引表示称为一
个（Key, Value）对，其中 Key为关键字，可以是文件名或文件其他描述信息的哈希值，Value
是实际存储文件的节点 IP地址或节点的其他描述信息。所有索引目录（即（Key, Value）对）
组成一个大的索引哈希表，只要输入资源的 Key 值，就可以从这张表中查出所有存储这项
资源的节点信息。
资源索引哈希表被分割成多个局部小块，按照不同 DHT协议的实现方式规定，将这些
局部哈希表分不到 P2P 网络中所有参与的节点上，每个节点负责维护其中一个小块，当请
求节点查询某项资源时，只要把查询报文路由到包含所要查找资源的（Key, Value）对的节
点上即可。
这种结构化的资源搜索策略的优点在于其具有良好的自治性和自我修复能力，基于此类
搜索机制所构建的 P2P网络拓扑的成本低，且鲁棒性强。目前，基于 DHT的 P2P网络路由
算法的典型实现协议主要有：Chord[2]、CAN[3]、Pastry[4]、Tapestry[5]和 Kademlia[6]等。
Kademlia路由技术
Kademlia 路由技术是一种基于 DHT 技术的 P2P 路由算法，是由美国纽约大学的 Petar
Maymounkov与 David Mazieres在 2002年发布的一项研究结果，使用分布式哈希表技术构
造了一种典型的结构化 P2P覆盖网络（Structured P2P Overlay Network）。作为一种最新的
技术标准，Kademlia技术具有比其他几种 DHT路由算法更低的配置信息量，更高的容错性，
可以说是目前最优的模型。Kademlia技术使得节点之间能相互通信的配置信息减小到最少，
通过使用一种并行的、异步的查找算法来避免那些非活动节点所带来的时间消耗，节点有着
较高的灵活性来选择路由路径，大大提高了路由查询的速度。
著名的 BitTorrent已于 2005年 5月在 版本中实现了基于 Kademlia协议的 DHT技
术，随后，国内的BitComet和BitSpirit也实现了和BitTorrent兼容的DHT技术，实现 trackerless
下载方法[7]。另外，Emule中也很早就实现了基于 Kademlia的类似技术（BT中称为 DHT，
-3-
Emule中成为 Kad），和 BT软件使用的 Kad技术的区别在于 key、value和 Node-ID的计算
方法不同[8]。
Kademlia节点信息及节点距离
基于 Kademlia的 P2P网络简称为 Kademlia网络，每一个加入到 Kademlia网络中的节
点都拥有一个专属的 ID，即 Node-ID，该 ID的取值是一个 160-bit的标识符，其有效期从节
点加入到 Kademlia网络中开始，直到该节点离开网络为止。这些 Node-ID值的具体生成应
用软件有不同的实现算法，一般是通过选择一个不重复的值进行 SHA-1 计算得到的，这个
值可以是由用户的 IP地址，或者只是简单的随机生成。
在 Kademlia 网络中，判断任意两个节点 X 与 Y 之间的距离是通过对这两个节点的
Node-ID进行异或（XOR）运算而得到的，这也是 Kademlia技术的独特之处。
假设节点 X与 Y的 Node-ID分别为 x和 y，则它们之间的距离 d(X, Y)为：
d(X, Y) = x y⊕ ，节点间距离的运算存在以下规则：
a) d(X, X) = 0；
b) d(X, Y) = d(Y, X)；
c) d(X, Y) d(Y, Z) = d(X, Z)⊕ 。
如：节点 X的 Node-ID为 010101，节点 Y的 Node-ID为 110011，则它们之间的距离为：
010101
X O R 110011
100110
因此，节点 X与节点 Y的距离为：DXY =32+4+2=38。
异或操作是单向的，对于任意一个给定的节点 X和距离 ∆>=0，总会存在一个精确的节
点 Y，使得 D(X,Y)= ∆。另外，单向性也确保对于同一个值的所有查询都会逐步收敛到同一
个路径上，而不管查询的起始节点的位置如何。
Kademlia路由表
图 2 Kademlia路由表结构
如图 2所示，为 Kademlia 网络中节点路由表结构，每个节点维护一张路由表，其中包
含于自己距离在[2i to 2i+1）之间的节点信息，整个路由表包含自多 160个列表（K-桶），其
中：
z k-bucket[0]中包含距离为[1,2）的节点，Node-ID前 159位相同，第 160位一定不同
的节点 1个；
z k-bucket[1]中包含距离为[2,4）的节点，Node-ID前 158位相同，第 159位一定不同
中国科技论文在线
-4-
的节点 2个；
z k-bucket[2]中包含距离为[4,8）的节点，Node-ID前 157位相同，第 158位一定不同
的节点 4个；
z ．．．
z k-bucket[159]中包含距离为[2159, 2160）的节点，Node-ID前 1位不同的节点 k个；
Kademlia路由机制
Kademlia技术的最大特点之一就是能够提供快速的节点查询（Node Lookup）机制，并
且可以通过参数进行查询速度的调节。假如节点 X（Node-ID值为 x）要查找 Node-ID值为
y的节点，Kademlia将按照如下步骤进行查找操作：
1） 计算节点 X到 y的距离：d (x, y) = x y;⊕
2） 请求节点 X从本地路由表的第 [log2d] 个 K-桶中取出 α个节点的信息（“[]”是取整
符号），同时进行 FIND_NODE查询操作。如果这个 K桶中的信息少于 α个，则从
附近多个桶中选择距离最接近 d的总共 α个节点；
3） 接收到查询操作的每个节点若发现自己的 Node-ID 值为 y，则回答自己是最接近 y
的；否则计算自己和 y的距离，并从自己对应的 K桶中选择 α个节点的信息发送给
请求节点 X；
4） 节点 X对新接收到的每个节点都再次执行 FIND_NODE查询操作，此过程不断重复
执行，直到每一个分支都有节点响应自己是最接近 y的节点；
5） 通过上述查找操作，请求节点 X就得到了 k个 Node-ID值最接近 y的节点信息。
之所以用“最接近”这个说法，是因为 Node-ID值为 y的节点不一定存在于网络中，也就
是说 y没有分配给任何一个节点。
如果查找成功，则<Key, Value>对数据会缓存在没有返回 Value值的最接近的节点上。
这样，下一次查询相同 Key 时就会更加快速的得到结果。通过这种方式，经常被请求资源
的<Key, Value>对数据的缓存范围就逐步扩大，使 Kademlia系统具有极佳的响应速度。这里
α也是为系统优化而设立的一个参数，用来调节每部查询的并发度，在 BitTorrent的实现中，
取值为 α=3。
3 基于 Kademlia的混合式可信 P2P网络
Kademlia 协议中的各个节点，无论性能如何，都被赋予了相同的责任，包括查询、下
载等。但在现实的 P2P网络中，物理节点的处理能力有强弱之分，有网络带宽充足的用户，
也有很多使用拨号上网或使用无线网络的用户，即节点存在异构性。随着网络的不断扩大，
节点自身性能的差会严重影响 Kademlia 网络的可用性，一些性能低的节点将成为网络的瓶
颈。
另一方面，P2P节点涉及交互安全，即通过路由算法定位到资源后，提供该资源的节点
是否可信，或者存在多个资源提供节点的时候，那个节点可信度更高时 P2P 网络中需要考
虑的严峻的安全问题。由于 P2P 网络节点的匿名性及节点进入/离开网络的随意性，导致网
络安全管理上的困难，网络中存在恶意交互、虚假反馈、合谋、误导等多种恶意行为，这就
要求在节点间建立一种信誉机制，提高网络节点的服务质量，从而规避由于使用 P2P 技术
而带来的风险。
混合式网络结构的提出
中国科技论文在线
-5-
基于 P2P 网络中节点的异构性，以及网络中存在恶意节点的问题，本文提出一种基于
Kademlia协议的混合式可信 P2P网络，整个网络建立在 Kademlia协议的基础上，根据节点
所在的地理位置的不同，将节点划分为不同的域，并在节点交互的过程中加入信任机制，通
过计算节点的信任度来选择所要交互的节点，排除恶意节点对网络的干扰与破坏，保证交互
过程的安全可靠，从而使得整个网络成为一个安全的可信 P2P 网络，网络拓扑结构如图 3
所示：
图 3 混合式可信 P2P网络
在本文所提出的混合式可信 P2P网络中，定义了以下三类节点：
1） 超级节点：超级节点为一个特定域的领袖节点，对域内节点进行管理，包括域内节
点资源管理、域内节点全局信誉度管理等。
2） 备份节点：用来备份一个域中超级节点的信息，当超级节点失效的时候，顶替失效
的超级节点。
3） 普通节点：除超级节点以外的节点，只能够在所在域内进行资源查找，信誉度计算
的能力，若需要寻找其他域的资源或获取其他域节点的信誉度必须通过本域超级节
点与其他域的沟通。备份节点在未启用时作为普通节点在域内与其他节点进行交
互。
构建节点信息
本文在构建网络节点信息时，作出以下规则的定义：
1. 构建网络资源信息规则：在基于 Kademlia 的混合式 P2P 网络中，为每个资源分
配一个对应的<Key, Value>对，其中 Key为一个 320-bit的哈希值，高 160-bit用
于在超级节点之间发布和定位资源，低 160-bit 用于在某个特定的域内发布和定
位资源，Value 为一个 160-bit 的哈希值，由资源所在节点的网络信息
（Node-ID+Port+IP）经过哈希计算得到。
2. 构建普通节点信息规则：普通节点拥有一个 160-bit的 Node-ID，该 Node-ID标识
了该节点在本域内的 ID，每个普通节点维护一张包含本域中和自己距离在一定
区间范围内的节点信息路由表，称之为 Local k-bucket；普通节点还需要维护一张
本地资源列表，其中包含该节点所拥有的网络资源所对应的<Key, Value>对。
3. 构建超级节点信息规则：超级节点拥有一个 160-bit的 Node-ID 以及一个 160-bit
的 Domain-ID（用来标识节点所在的域），每个超级节点维护两张路由表，其中
一张为 Local k-bucket，另一张为超级节点中和自己距离范围在一定区间内的节点
中国科技论文在线
-6-
信息路由表，称之为 Remote k-bucket。超级节点除了维护一张本地资源列表外，
还需要维护一张全局资源列表，存储它所知道的本地和域间资源的<Key, Value>
对。超级节点还维护一个缓存区列表，其中保存最近查询记录的<Key, Value>对，
加速资源定位。
信任评估
在本文所构建的基于可信 Kademlia协议的 P2P网络中，涉及信任的两个方面，即直接
信任关系以及节点的全局信誉两个方面，其中：
直接信任，是指请求节点 A 与服务节点 B进行直接交互而产生的信任关系；直接信任
关系所对应的信任评估是称之为直接信任度，是请求节点 A通过自己与服务节点 B的交互
记录多节点 B所作出的主观的评价。
网络中所有与节点 B交互过的其他节点根据其各自与节点 B的交互记录而对节点 B所
作出一个评价，而全局信誉正是这些评价的综合，全局信誉就是节点 B 在整个网络中的可
信程度的一个度量。
在本文构建的可信 P2P 网络中，采用事件记录的方式来对节点进行信任评估，节点 A
请求与节点 B进行交互，若交互成功，则记成功交互次数增 1，总交互次数增 1，若交互失
败，则记失败交互次数与总交互次数分别增 1，这样，节点 B 所提供给节点 A 的成功交互
的比例越大，节点 A对节点 B越信任，节点 B提供给网络中其他节点的成功的比例越大，
则节点 B 在整个网络中的全局信誉度越高，信任度计算方法引用窦文模型中信任度计算[9]
方法，并对反馈可信度的度量方法作出定义。
1. 直接信任度
根据上一节的定义，定义节点 A对节点 B的直接信任度 A BDT → 表示为：
A BDT AB
AB
S
N→
= （1）
其中， ABN 表示节点 A与节点 B进行交互的总次数， ABS 表示在节点 A看来，与节点
B的成功的交互次数。
2. 全局信誉度
目标节点 B 在网络中的全局信誉度为所有与其交互过的节点对其的信誉反馈与信任者
信誉度的乘积的综合，即：
B U B U
X
T RT C→= ×∑
（2）
其中，X为所有与目标节点 B交互过的节点。 BURT → 为节点 U对节点 B的信誉反馈（即
节点 U对节点 B进行信誉度的评估），即：
B B
B
U U
U
B
S FRT
S→
−=
（3）
式中， BUS 表示节点 U与 B成功交易的次数， BUF 表示节点 U与节点 B交易失败的次数，
BS 表示节点 B 所提供的所有成功交易的总次数。根据实际的信任特性可知，当 0BS = 或
B B 0U US F− ≤ 时， B 0URT → = ，即节点 B 没有过任何成功交易的记录，或者提供给节点 U 的
中国科技论文在线
-7-
成功交易次数少于失败交易次数时，节点 U对节点 B的信誉度评价为 0。
3. 反馈可信度
在（2）式中， UC 表示反馈者 U的可信度。
本文定义一种通过反馈信誉度与节点真实信誉度偏差来衡量反馈可信度的方法。
定义： U∆ 表示节点 U所提供的关于 B的信誉反馈与节点 A对 B所作反馈的偏差，那
么反馈者 U的可信度 UC 表示为：
1U UC = −∆ （4）
可以看出， U∆ 越小表示对于节点 A来说，节点 U的信誉反馈越可信。
下面对偏差 U∆ 进行详细讨论。
在所有与请求节点 A 和反馈节点 U 都有过交互过的节点集合 ( , )A UΝ 中，站在节点 A
的角度来看，节点 U所提供的反馈信息与自己所提交的反馈信息越接近，表示节点 U对于
节点 A所提供的信誉反馈偏差越小，则有：
( , )
( , )
Ai Ui
i N A U Ai Ui
U
N A U
S S
N N
N
∈
−
∆ =
∑
其中，i为与节点 A和节点 U都有过交互的节点， ( , )N A UN 为集合 ( , )A UΝ 中节点的个数。
当节点A与节点U没有共同交互的节点时，节点A对节点U的所提供的信誉反馈保持中立，
即取 ∆ = 。
4. 综合信誉度计算
请求节点 A在决定是否与响应节点 B进行交互时，考察响应节点 B的全局信誉度以及
自身对节点 B的直接信任度，对响应节点做出综合评价，即：
(1 )A B A B A BT DT RTα α→ → →= + −
其中，α 为权重因子，表示节点 A对节点 B的综合信任度中，节点 A对 B的直接信任
度和节点 B在整个网络中的全局信誉度所占的比重。
节点交互流程
为防止节点篡改信息，域内普通节点的全局信誉度由其所在域的超级节点负责计算和存
储，而请求节点保存其自身与交互节点的交互记录并计算对交互节点的直接信任度，最后根
据综合信任值选取可信度高的节点进行交互。
当请求节点 A请求网络中的某项资源<Key, Value>时，进行如下操作：
1. 请求节点 A根据<Key, Value>在本域内进行资源定位，这里出现两种情况：
1) 域内资源定位成功，请求节点 A收到域内 k个响应节点的连接信息向本域超级
节点发送请求，查询这 k个响应节点的全局信誉度，进行步骤 3；
2) 域内资源定位失败，向本域超级节点发起查询请求，超级节点首先查询本地资
源列表及缓存列表，若找到请求资源，则向请求节点 A返回资源节点的连接信
息以及全局信誉度，进行步骤 3；若超级节点未找到请求资源，则跳到步骤 5
进行域间节点交互；
中国科技论文在线
-8-
2. 请求节点在本域内和域内超级节点中都没有定位到资源，则由超级节点进行域间资
源定位，超级节点找到 k个响应节点，将这些响应节点的连接信息及全局信誉度返
回给请求节点 A（其他域中节点的全局信誉度由超级节点向响应节点所在域的超级
节点请求获取），进行步骤 3。
3. 请求节点 A 根据超级节点返回的全局信誉度以及本地列表中对响应节点交互记录
对节点进行综合信任评估，选取信任评分最高的节点进行交互；
4. 交互结束，请求节点 A根据交互情况更新本地信任列表，并向超级节点反馈交易情
况，若节点 A进行的是域间交互，则将资源在本地超级节点中进行一次备份；
超级节点根据请求节点交易情况的反馈更新服务节点的全局信誉度，并查看是否到达更
新时间，如果到达，则发送更新消息，要求更新备份节点中节点全局信誉度列表。
4模型性能分析
根据本文所提出的基于 Kademlia协议的混合式 P2P可信网络模型中的定义及节点交互
流程在 P2P 网络仿真环境下对系统进行仿真，初始化节点数为 200 个，定义节点初始的全
局信誉度为 ，其中按一定比例模拟数个恶意节点，以文件共享系统为例进行交互，恶意
节点提供与所请求资源不同的资源，即与恶意节点交互会失败，图 4为系统性能随恶意节点
比例变化而变化的情况，改进后的混合式可信 P2P 网络在恶意节点数较大的时候仍能保持
50%左右的交互成功率，另外，由于网络初始化是节点全局信誉度相同，而这些节点中存在
恶意节点和正常节点，在加入可信的 P2P 网络中，通过信任度计算选择信任度高的节点进
行交互，使得恶意节点的全局信誉度不断降低，最后排除在 P2P 网络之外，保证了系统的
可用性和安全性，图 5为恶意节点随交互次数变化，其全局信誉度的变化情况，可见，恶意
节点由于提供恶意服务而导致信誉度下降，随着交互次数的增加，恶意节点将最终被排除在
系统之外。
图 4 节点交易成功率对比
中国科技论文在线
-9-
图 5 恶意节点全局信誉度变化
5 总结
本文在分析了 P2P 网络结构及特点的基础上，基于 P2P 网络节点的异构性以及网络中
存在的安全问题，在 Kademlia协议的基础上提出混合式的安全 P2P网络，通过在网络中加
入信任计算构建一种更安全可靠的网络环境，降低恶意节点对网络可用性的影响与破坏。
本文在进行信任度计算的过程中没有考虑到对恶意节点所实施的恶意破坏采取惩罚措
施，是本文今后继续研究的一个深入点，另外，由于时间有限，本文并没有将信任值随时间
衰减这一因素纳入考虑范围，这也将作为本系统模型进一步完善的方向。
参考文献
[1] Ferreira , Grama A, Jagannathan S., “An IP address based caching scheme for peer-to-peer networks,”
Global Telecommunications Conference, 2003. GLOBECOM 03. IEEE, ,no.,-3850 ,1-5
Dec.
[2] Ion Staica, Robert Morris, David Karger, Kaashoek, Hari Balakrishnan. Chord: A Scalable
Peer-to-Peer Lookup Service for Internet Applications. SIGCOMM’ 01, August 27-31, 2001.
[3] Fu Xiaodong, Shi Weisong, Anatoly Akkerman. CANS: composable, adaptive network services
infrastructure[C]. Proceedings of 3rd U SEN IX Symposium Internet Technologies and Systems.
[4] Antony Rowstron, Peter Druschel. Pastry: Scalable, distributed object location and routing for large-scale
peer-to-peer systems[C]. Proceedings of the 18th IFIP/ACM International Conference on Distributed Systems
Platforms.(Middleware November 2001), 2001.
[5] Ben Y, Zhao John, Kubiatowicz D, et al. Tapestry: an infrastructure for fault-tolerant wide-area location and
routing[C].. Berkeley Technical Report UCB//CSD-01-1141, April 2000.
[6] Kademlia: A Peer-to-Peer information system based on the XOR metric[C]//Procedings of IPTPS, Canbridge,
USA. 2002: W, Wang H M, and Jia Y, et al.. A recommendation-based peer-to-peer trust model[J].
Journal of Software, 2004, 15(4): 571-583.
[7] Jonathan Ledlie, Margo Seltzer. Distributed, Secure Load Balancing with Skew, Heterogeneity, and
Churn[R].Harvard Technical Report TR-31-04,2004.
[8] Stutzbach D, Rejaie R. characterzing churn in peer-to-peer networks[R].Technical Report, CIS-TR-2005-03,
University of Oregon,2005.
[9] 窦文. 信任敏感的 P2P拓扑构造及其相关技术研究[D]. 长沙：国防科技大学, 2003: 53-70.
中国科技论文在线
-10-
Research On The Hybird Trusty Peer-to-Peer Network
Based On Kademlia Protocol
Wang Binyan
School of Computer Science, Beijing University of Posts and Telecommunications, Beijing,
PRC (100876)
Abstract
The extensive application of P2P technology brings the full superiorities, and exposed the shortcomings
of which at the same time. Various kinds of secure problems of the P2P Network has been caused due
to the features of P2P network, such as anonymity, heterogeneity and dynamicity. The current research
of P2P technical focus on the resources location based on the DHT(Distributed Hash Table) and the
trust mechanism between P2P nodes. This paper studied the P2P trust mechanism and proposed an
improved hybird trusty Peer-to-Peer network based on Kademlia protocol, and proved the ability of
resisting the malicious attacks has been advanced.
Keywords: Peer-to-Peer Networks; Kademlia; Hybird; Trust Evaluation
中国科技论文在线
