一种基于团队的P2P信誉机制设计

王 闯，管 刚，焦树国

(军事经济学院襄樊分院计算机教研室，襄樊441118)

1 引言

信誉机制的需求是伴随着P2P的迅猛发展而产生的。在P2P应用中，FreeRiding(搭便车)现象相当突出，部分节点在节点间互享资源的时候，只享受服务而不提供服务。如在Gnutella中70%的节点不共享文件，而50%的文件请求由1%最好的节点提供服务［1］。这些最好的节点成了新形势下的服务器，这显然不符合研制P2P的初衷。因此，很早就有人提出需要建立一个可靠的信誉机制以限制或阻止FreeRiding，而这种机制必须要为正确服务的节点建立高的信誉，获得一些特权，以鼓励它继续这种行为;与之对应，对恶意服务的节点进行惩罚，直到将它完全屏蔽在P2P应用之外。

2 信誉机制的发展现状

当前存在的信誉模型可以分为典型的四类。即CAs、社会网络、概率估计和博弈理论［2］。CAs(Certificate Agents)模型以CA做类似中央服务器式的服务，与P2P的分布式理念相左，可以基本排除;社会网络的计算过程需要从所有节点获取信息，虽然也通过某些近似方法作出改进，但开销仍然太大;概率估计模型开销相对较小，但在初始阶段可靠性不高;博弈应用于信誉模型的理论比较少，单次博弈可以简单实现，但是连续博弈难度比较大，它需要仲裁机构(中央服务器)的支持。后三类模型的优劣比较见表 1［3］。

表1 三类信誉模型比较

通过以上的分析比较，笔者采用符合P2P特点的结构化纯分布式的概率估计模型——FTrust来构建自己的信誉模型。

3 FTrust信誉机制设计

3.1 极大似然估计的信誉机制

FTrust以极大似然估计理论作为理论基础，极大似然估计理论的工作原理如下:

节点Pi通过路由协议找到目标节点Pj，想从Pj处获得服务，而Pj正确服务的概率为全局值θj。Pi询问第三方节点Pk关于Pj的信誉值，Pk说谎的可能为1k，如果每一个被询问的第三方节点回馈信息{0，1}用随机变量Yk表示，则Yk符合公式1所示的分布率(1表示Pk声明Pj会正确服务，0表示不会):

一次对目标节点Pj询问的所有反馈事件为Y1、Y2…Yk这几个随机变量的取值，其联合分布概率为 P(Y1=y1，Y2=y2，…Yk=yk)，此式是关于自变量 θj的方程，记作 L(θj)。Zoran Despotovic［4］直接给出L(θj)的计算式如下:

当 θj变化时，L(θj)跟着变化，当 L(θj)取得最大值时，θj就是对Pi来说Pj正确服务的概率。θj的大小，就是Pi用来决定是否从Pj获取服务的依据。但很明显，公式2成立的条件是Y1、Y2…Yk这几个随机变量相互独立。但在文献［4］中，这种条件不明显成立。

3.2 FTrust信誉机制的原理

现实生活中，兴趣爱好相同或相近的人很容易形成一个团体，而这个团体是自适应的，既可以剔除旧成员，也可以增加新成员。当某个成员变得对此团体有所伤害的时候，会被其他成员探知，并通过一定的手段进行惩罚，直到最后遭到团队的摒弃;当外部节点通过它自身的努力，符合团队加入条件时，可以获取团队资格，而一旦成功，则可以享受与其他团队成员相同的便利;团体成员之间，更倾向于坦诚相待，互通有无，以增加团体的吸引力，吸收新的团员;团队成员更加倾向于真实服务和推荐。

基于以上的思考，FTrust引入团体概念，设置团员之间坦诚相待，使公式2中的随机变量互相独立变成可能，等号可以成立。通过设立Trans链表，设置Friends节点，保证各事件的独立性。在此基础之上，利用极大似然估计提供的计算方法，可以得到一个比较满意的信誉机制效能。

FTrust重叠网络从无到有的过程是这样的。一开始网络中只有若干独立节点，每个节点都可以看作一个最小形式的团队。节点对其他节点来说都是新的，没有任何信誉值可言，为了使他们之间能产生交互，使FTrust运转起来，设有一个默认的信誉值(TRUST_DEFAULT_VALUE)。当新节点以这个默认值进行了一定次数的传输之后，就可以依据过往传输记录，计算并存储相应节点的信誉值。依据信誉值大小是否超过阈值TRUST_THRESHOLD_FRIEND，决定目标节点是否能成为自己的伙伴节点。这样，慢慢的伙伴之间就构成了一个团队。

在将来的传输过程中，同一团队成员之间相互完全信赖，而不同的团队成员之间的传输需求，则依靠本团队成员的推荐或默认信誉值，以决定是否进行传输。记录传输结果，更新信誉值。团队通过其成员与外界的交互作用，可以吸纳新的团员。另外，本团队内成员之间的传输也要记录，当出现错误的传输时，需要更新自己对目标的信誉值，并广播这种错误，让其它成员也对这种错误传输有所感知，同时更新它们自己对目标的信誉值。当伙伴的传输错误积累到一定程度时，请求服务节点将目标节点从伙伴列表中删除，然后广播通知其他的伙伴，将目标节点的错误行为广播。接收到广播的节点进行自己的处理:或者完全信任广播将目标清除出团队，或者降低目标节点的信誉值。前者的作用比较直接，但容易被恶意节点利用;后者反应虽然慢，但同样能将错误服务的节点驱除出团队。后者也伴生一个问题:如果恶意节点之间构成共谋关系，互相协商对某个正常节点进行诋毁。这种情况下，如果恶意节点占小部分，则它们会被驱除;否则，慢慢的会被其他正常节点与之发生传输时感知，从而主动离开原团队。这样，原团队就成了一个纯的恶意节点，对团队外部的节点无影响。

4 FTrust的路由

4.1 路由协议的选择

FTrust将作为信誉机制，实现P2P路由协议之上，构成重叠网络。Kademlia［5］是应用于 eMule、Bit-Torrent、BitComet等软件中成熟的一种结构化纯分布式P2P路由协议，经受住了实际检验。将FTrust构建于Kademlia之上，控制文件下载的过程，帮助信誉值传播。在安全性方面，Kademlia中节点经过单向哈希生成ID标记，在P2P应用中自然就拥有了SHA－1单向哈希的保护，防止恶意节点冒充，减少tamper的可能。同时，因为Kademlia中通过节点记录相互存在的算法可以抵抗一些基本的DoS(拒绝服务)攻击。另外，FTrust通过团队的设立，降低collusion的发生。而 Free riding和 White washing(洗黑钱)节点跟新加入的节点一样，没有利用到团队提供给自己的便利，没有利益可图。

4.2 路由流程

FTrust每个节点拥有一个Trans表，里面保存一定数目与之发生过传输的节点信息，包括正确传输和错误传输的次数，以及一个 Friends标识位。Friends节点拥有很高的权限，本地节点无条件接受Friends节点的服务或推荐。一个包含 FTrust的P2P文件共享应用流程如图1所示。

图1 FTrust流程

第①步，节点i发出一个文件搜索请求，请求关键字为fname的文件。第②步，Kademlia路由协议返回那些声称自己拥有fname文件的节点。节点i暂存这些节点信息，将这些节点记为集合［pa］。第③步，节点i向［pa］中的所有节点发送文件请求。第④步，［pa］中的节点返回文件名及该文件的SHA－1标识码。节点i比较这些标识码，剔除那些与大多数标识码不同的节点，缩减备选节点集合记［pb］。第⑤步，询问集合［pb］中各节点的信誉值。第⑥步，通过信誉机制，得到各节点信誉值。节点i取信誉值最大的几个记为集合［pc］。第⑦步，节点i向［pc］中节点发送文件下载请求。第⑧步，目标节点返回对应文件或文件块。第⑨步，节点i对获得的文件或文件块进行单项哈希，得到SHA－1标识码，与之前得到的标识码进行比较，若相同则表明是正确传输，提升目标节点的信誉值;否则是错误传输，则降低目标节点的信誉值，然后从［pc］中选择另外的节点执行步骤⑦→⑨，如果仍然不成功，则选择集合［pb］－［pc］中的节点执行步骤⑦→⑨，若仍不成功，则放弃。

⑤⑥⑨是FTrust在一般P2P应用基础上新加入的步骤，其中⑤⑥两步利用了极大似然估计的方法，第⑨步Renew表的时候，明确错误付出的代价比成功得到的利益要大，目的是惩罚恶意行为。

5 FTrust的性能分析

设置50个节点，其中10个恶意节点，40个善意节点。善意节点总是正确服务并正确推荐，而恶意节点则相反。测试程序随机让两个节点之间发生传输(节点1和节点2)，统计数据total trans(总有效传输数目)加一。节点1用FTrust机制询问它所知道的关于节点2的信誉值，然后根据FTrust的策略选择是否从节点2获取服务。如果决定获取，又如果服务结果是成功，则统计数据succ增加一，若失败，则统计数据 fail增加一，节点1更新自己的TrustMap;如果决定不获取，节点2如果是善意节点，统计数据wrong decision增加一。显然，如果没有信誉机制的作用，那么应该有10/50=20%的传输是失败的。

图2显示了FTrust网络中(默认信誉值为0.5)各项统计数据占总有效传输数目的比例。可以看出，排除错误传输和错误决定所占的一成之外，其余九成是正确传输和正确决定的比例。

图2 TRUST_DEFAULT_VALUE=0.5传输比例统计图

进一步的实验表明，不同的TRUST_DEFAULT_VALUE值对成功传输和错误决定的影响只在收敛速度上，另外，其值越小，失败传输比例越小。当值为0.1时，错误传输比例降到0.02。所以TRUST_DEFAULT_VALUE越小，效果越好。因此，从长远来看，选择小值是比较好的。因为FTrust拥有退出网络时，将TrustMap保存起来的功能。在这一层意义上，较小值造成收敛速度较慢的影响可以在一定程度上消减下来。后续实验中，该值取折中值0.3。

6 FTrust与单纯极大似然估计机制比较

Zoran Despotovic［4］在极大似然估计实验中设置恶意节点总是错误服务，而一般的节点以一个随机的固定概率值提供错误服务。当节点需要第三方的推荐时，只用搜集到10－20个证据就可以进行计算。第三方节点撒谎的概率是全局同一的，但是这个值并没有在文中提供，所以不得而知，其结果如图3所示。而在FTrust实验中，第三方节点撒谎的概率是依节点而不同的，为1－trust，其中trust是第三方在发起源看来的信誉值，因此如果第三方是发起源的伙伴，那么撒谎概率为0，也就是完全相信自己的伙伴。这也就要求对成为伙伴的要求要高一点，TRUST_THRESHOLD_FRIEND(称为伙伴的信誉值要求)设为0.8。实验中，一般节点不仅以一定的概率错误服务，而且以一定的概率错误推荐，然后根据不同恶意节点的比例，跟踪错误服务的数目(错误决定的数目趋向于0，因此不再列出)，实验结果如图4所示。

图3 采用单纯极大似然估计机制的实验结果图

图4 采用FTrust机制的实验结果图

从上述两图可以看出，FTrust稳定时错误率在0.3到0.42之间，而极大似然估计最大则超过0.5。同时，极大似然估计的一个典型特点是，当恶意节点占到0.5以上时，错误率不会再增高，而相反会降低一些。当网络中节点不可信时，它会采取相反的决定。而FTrust也继承了这一优点。

7 结束语

论文设计并实现了一个切实可行的信誉机制FTrust，使其工作在P2P环境中。通过社会学和计算机科学的结合，引入团体的概念，构造出的FTrust，具有不俗的性能表现，同时通过Kademlia路由协议合理控制资源耗费代价。通过构造的实验场景对FTrust的性能分析可知，FTrust的作用明显，特别是与单纯极大似然估计机制相比。

［1］Eytan Adar and Bernardo A Huberman.Free Riding on Gnutella［R］.Internet Ecologies Area and Xerox Palo Alto Research Center，2000.

［2］Zoran Despotovic，Karl Aberer.Trust and Reputation Management in P2P Networks［R］.Swiss Federal Institute of Technology Lausanne，2004.

［3］Zoran Despotovic.Karl Aberer，Possibilities for Managing Trust in P2P Networks［R］.Swiss Federal Institute of Technology Lausanne，2004.

［4］Zoran Despotovic， Karl Aberer.Maximum Likelihood Estimation of Peers＇Performance in P2P Networks［J］.The Second Workshop on the Economics of Peer－to－Peer Systems，2004:1 －6.

［5］Petar Maymounkov，David Mazi`eres.Kademlia:A Peerto－peer Information System Based on the XOR Metric［J］.Proc.of the 1st Int＇l Workshop on Peer － to － Peer Systems，2002:153 －161.