基于博弈论的P2P网络信任进化机制研究

󰀁

2007年11月

文章编号:1001-9081(2007)11-2710-02

计算机应用

ComputerApplications

󰀁

Vo.l27No.11Nov.2007

基于博弈论的P2P网络信任进化机制研究

满红芳,杨蓉蓉,刘凤鸣

(1.聊城大学图书馆,山东聊城252059;󰀁2.济南技术学院旅游管理系,济南250002;

3.东华大学信息科学与技术学院,上海201620)(manh@f126.com;manhongfang@lcu.edu.cn)

摘󰀁要:基于博弈理论,着眼于信任机制的进化演变,应用复制动态机制对节点之间的信任关系的长期演化趋势进行了分析。分析结果显示网络节点之间的信任关系通过博弈收益机制的调节而成为网络安全与稳定的长期演化趋势。仿真结果也证明,应用收益机制调节,信任会成为网络节点的稳定策略,从而提高了网络的安全性与稳定性。

关键词:P2P网络;进化博弈;复制动态机制;进化稳定策略中图分类号:TP393.08󰀁󰀁文献标识码:A

1

2

3

ResearchoftrustevolutionarymechanismbasedongametheoryinP2Pnetworks

MANHong󰀁fang,YANGRong󰀁rong,LIUFeng󰀁ming

1

2

3

(1.Liabrary,LiaochengUniversity,LiaochengShandong252059,China;

2.DepartmentofTravelManagement,JinanTechnologyCollege,JinanShandong250002,China;

3.CollegeofInformationScienceandTechnology,DonghuaUniversity,Shanghai201620,China)

Abstract:Theevolutionarytendencyoftrustrelationshipamongpeerswasanalyzedwiththereplicationdynamicmechanismbasedonthegametheory.Thetrustrelationshipbetweenpeerswillbethelong󰀁termtendencyofevolutionary

adjustedbythereceiptsmechanisminthereplicationdynamicproceedingofevolutionarygame.Thesimulationresultsshowthatthetrustwillbethestablestrategyofpeerswithappropriatemechanism,andthenthesecurityandstabilityofnetworkwillbeenhanced.

Keywords:P2Pnetworks;evolutionarygame;replicationdynamicmechanism;evolutionarystablestrategy

任度,以此保证节点的可信性与可靠性,从而维护网络的安全性与稳定性。由于需要全局节点的配合,这本身又是信任问题。加之计算量与网络通信开销大等原因,这种理想的模式实施起来很困难。对于节点的自由进入、退出,基于局部信息计算的信任模型,如Chord[5]、P󰀁Grid[6]等,又显得󰀂证据不足 。因此,信任的定量研究有待进一步探索。

信任,目前作为解决分布式网络安全性的重要手段,主要解决网络节点的可信性问题,也就是说一个节点对另一个节点所采取的策略是不是信任的问题。信任是社会生活的基本事实,是一种预期,是相信他人未来的可能行动的[7]。所谓,也就是博弈。博弈论是20世纪80年代以来由一般的应用数学理论,一跃成为主流经济学的核心内容,成了几乎所有领域经济学家的基本分析工具和共同语言。经典博弈论是基于一种󰀂完全理性 的假设,要求行为主体应具有完善的判断和预测能力,并且始终追求其自身利益的最大化。但完全理性的假设并不普遍,Alchian基于生物学进化论󰀂自然选择 思想,允许人通过模仿、试错以适应不断变化的环境,提出了进化博弈理论。

本文基于进化博弈理论的思想,着眼于全局信任机制的进化演变,应用复制动态机制对节点之间的信任关系的长期演化趋势进行了分析。仿真结果表明,应用适当的机制,信任会成为网络节点的稳定策略,从而提高了网络的安全性与稳定性。

0󰀁引言

近几年来,随着Napster、Gnutella等的成功,P2P网络应用的研究变得炙手可热。从文件共享、分布存储到资源发现,P2P成为未来网络发展的理想模式,这主要是因为:P2P网络天生具有的开放性、匿名性、自治性等特性;网络中的节点没有中心控制服务器的控制,可以自由地直接互联,为信息的传播提供了充分的自由;每一个节点具有客户机与服务器的双重身份,提高了网络的可扩展性与容错能力。

但是,随着P2P系统应用的不断深入发展,网络的安全性与稳定性越发变得严重。在Napster、Gnutella中,有66%的节点对整个系统没有任何贡献,10%的节点提供了87%的文件资源,20%的节点提供了98%的共享文件[1]。大量自私节点的存在严重影响了整体网络的性能,破坏了网络系统的稳定性。此外,恶意节点随便改变身份,提供虚假服务,传播病毒、木马等具有破坏性的软件,给网络的安全带来极大的隐患。因此,建立适当的机制,在不破坏网络先天特性的情况下,保证网络的安全性与稳定性是很有必要的。

信任,作为目前解决P2P网络中安全问题的重要手段,越来越受到研究者的关注。P2P网络中信任机制的研究,如EigneTrust[2]、EigenRep[3]、PeerTrust[4]等信任模型,试图通过收集节点的全部声誉信息(即历史行为)计算节点的全局信

󰀁󰀁收稿日期:2007-06-04。

󰀁󰀁作者简介:满红芳(1973-),女,山东聊城人,讲师,硕士,主要研究方向:网络安全;󰀁杨蓉蓉(1980-),女,山东济南人,讲师,主要研究方向:网络技术;󰀁刘凤鸣(1969-),男,山东胶州人,博士研究生,主要研究方向:网络智能、信息安全。第11期满红芳等:基于博弈论的P2P网络信任进化机制研究

x1=0x2=1x3=

󰀁󰀁2711󰀁󰀁

(6)

(7)

1󰀁信任博弈模型

P2P网络在复杂多样、层次交叠、动态多变环境中,进行信息、数据、服务之间的交互、转移、生灭,形成了网络系统的动态、连续、不确定的系统状态。然而长期的不同形式与过程的演化发展的结果,使整个系统趋向更高级的有序化发展,自组织形成一个动态、有机的整体,整个系统通过各节点的交互和协作解决问题[8]。

节点之间的交互与协作基础就是信任。信任策略的选取也保证了网络节点之间的协作,从而也保证了网络的安全性与稳定性。节点信任策略的选取也是基于复制动态机制的基础上,通过与其他节点反复交互即博弈,不断地模仿与试错,动态调整自身策略,从而保证了信任策略的进化稳定,也保证了网络的安全性与稳定性。为清楚地讨论网络进化的可能趋向和稳定性,下面给出理论模型,进一步深入讨论。

b-d(8)c-a+b-d

上述三个不同的解都有可能是进化稳定策略,但根据微分方程的󰀂稳定性原理 可知:稳定状态处的函数的导数必须小于0,即F!(x*)<0。x*表示稳定状态,也就是进化稳定策略。用复制动态方程的相位图表示,就是与水平轴相交且交点处切线斜率为负的点,即为相应博弈复制动态的进化稳定策略。根据进化稳定策略的性质还可知,这个稳定状态必须对微小扰动具有稳健性。也就是说,如果某些博弈方由于偶然的错误出现偏离,复制动态仍然会使其回到稳定状态。

由以上分析可知,要使信任成为一个进化稳定策略,应该满足以下三个条件:

1)F!(x1=0)<02)F!(x2=1)<0

b-d

3)0c-a+b-d

由以上三个条件得:d>b、a>c且a-c>d-b,由此得如图2所示的复制动态方程局部相位图。因此,为提高网络整体的安全性与稳定性,必须引入一定的机制使得信任成为网络中唯一的进化稳定策略。为实现上述目的,可以采取以下措施:

1)使b变小或d变大,d-b增大,即建立相应的惩罚机制,加大惩罚力度,使选择不信任策略成为一种风险很大、收益很小的行为。

2)使a变大或c变小,a-c增大,即提高信任策略的收益,鼓励和促进博弈方选择信任策略,降低失信的机会收益,从而使信任成为一种自动约束机制。

3)使a-c远大于d-b,这样x3趋向0,初始状态选择信任策略的概率远大于选择不信任策略的概率。

这样,虽说x1=0在最初状态也是一个稳定解,但随着博弈次数的增加,节点在博弈过程中不断模仿、学习,博弈双方的比例因策略动态调整不断发生变化,最终x3逐步退化为x1,此时F!(x1=0)>0,x2=1就成为唯一的一个进化稳定策略。

图1󰀁节点博弈的收益矩阵

图1显示了一次博弈中博弈双方的收益矩阵。其中,a为

一次博弈中双方都选择信任策略时的收益;当一方策略为信任,而另一方的策略为不信任时,b为信任方的收益,c为不信任方的收益,d为双方都选择不信任策略时的收益。

在经典的󰀂囚徒困境 中,存在唯一的纳什均衡为博弈双方都选择不信任策略。但如果博弈无限地进行下去,博弈双方都会采用相互信任的策略进行博弈,信任策略成为了唯一的纳什均衡,这在经济学中的非合作重复博弈理论中被称为子博弈精练纳什均衡,是得到证明存在的。这样,将非合作博弈理论引入到P2P网络,分析解决节点间的信任进化机制,从理论上保证了策略均衡的存在性和网络进化的稳定性。现在考虑在网络全部节点参与的情况下,在节点间随机配对进行博弈。假设有比例为x的节点采取信任策略,比例为1-x的节点采取不信任策略。由于网络带宽等资源的,博弈节点的学习速度是比较慢的,也就是说,当某一节点改变策略时,其他节点模仿学习的速度是比较慢的。那么,假设采用信任策略博弈节点的期望收益为u1,采用不信任策略博弈节点的期望收益为u2,全部节点的平均期望收益为u,那么有:

u1=xa+(1-x)b

u2=xc+(1-x)d

(1)(2)

图2󰀁复制动态微分方程局部相位图

u=xu1+(1-x)u2(3)则采取信任策略的节点在t阶段策略的动态变化速度,可由下列动态微分方程表示:

dx/dt=x(u1-u)(4)将式(1)~(3)代入式(4)可得复制动态方程为:

dx/dt=x(1-x)(x(a-c)+(1-x)(b-d))(5)在式(5)的基础上进一步讨论博弈的进化稳定策略(EvolutionStableStrategy,ESS)。也就是说信任策略,如何才能成为网络进化的稳定策略。

3󰀁仿真结果分析

在学校校园网上,对上述模型及调节机制进行了试验仿真。在校园局域网上,设置了1000个Agent,每一Agent都能在与其他Agent博弈交互中进行学习,慢慢模仿收益高的Agent节点动态调整自己的交互策略。设x=0.8,初始收益矩阵是a=10,b=-4,c=6,d=-1,然后将收益调整为a=11,b=-5,c=2,d=0,博弈交互重复100次。图3反映了收益调节前选择两种策略的Agent博弈过程中的数量变化,图4显示了收益调节后的Agent博弈过程中的数量变化。从图中可以看出,策略的调整随着收益机制的调节有着明显的变化,虽然在过程中有一些小的波动,这是有些Agent暂时退出博弈的原因,但总体上可以比较出机制的调节对于策略的选择有着明显的影响。因此,适当建立相应的收益激励机制,可以提高选择信任策略的Agent的数量,从而可以使网络趋向稳定,提高网络的安全性。(下转第2717页)󰀁2󰀁信任进化机制

要讨论该信任博弈的进化稳定策略,应先找出动态复制

方程的稳定解。也就是在复制动态的过程中,采用两种策略博弈方比例不同的水平。

令F(x)=dx/dt=0可解得三个解:

第11期杜焕强等:基于身份的代理盲签名

表1󰀁本方案与其他方案的性能比较

󰀁󰀁2717󰀁󰀁

方案文献[2]方案文献[5]方案本文的方案

生成代理密钥

2Pa+4Pm+4Ad+MuG3+ExG3+Hs3Pa+Pm+2Ad+MuG3+ExG3+Hs2Pa+2Pm+2Ad+2MuG3+2ExG3+2Hs

签名

2Pa+6Pm+5Ad+2Hs

2Pa+2Pm+2Ad+MuG3+ExG3+Hs2Pa+2Pm+2Ad+MuG3+ExG3+Hs

验证

3Pa+Pm+Ad+MuG3+ExG3+2Hs

3Pa+3MuG3+3ExG3Pa+2MuG3+2ExG3

󰀁󰀁从各种操作的计算复杂度来看,本方案效率有了明显的

提高。

[4]󰀁CHAUMD.Blindsignaturesystems[C]//AdvancesinCryptology

-Crypto󰀁83.NewYork:PlenumPress,1983:153.

[5]󰀁李素娟,张福泰.基于ID的代理盲签名[J].计算机工程,2006,

32(17):203-204.[6]󰀁SHAMIRA.

Identity󰀁basedcryptosystemsandsignatureschemes

CHAUMD.AdvancesinCryptology:

[C]//BLAKLEYGR,

5󰀁结语

本文结合代理签名和盲签名,利用双线性对,构造了一个高效的基于身份的代理盲签名方案。分析表明,该方案兼具了代理签名和盲签名的优点。同时,与以往相关文献相比,在效率、安全性等方面都有了明显的提高。因此方案的计算开销较少,适用于电子现金、电子投票、电子商务等领域。参考文献:

[1]󰀁MAMBOM,USUDAK,OKAMOTOE.Proxysignature:delegation

ofthepowertosignmessage[J].IEICETransactionsonFundamen󰀁tals,1996,E79󰀁A(9):1338-1353.[2]󰀁ZHENGD,HUANGZ,CHENKF,etal.

ID󰀁basedproxyblind

signature[C]//Proceedingsofthe18thInternationalConferenceonAdvancedInformationNetworkingandApplications(AINA2004).LosAlamipos:IEEEComputerSociety,2004:380-383.

[3]󰀁GUCX,ZHUYF.AnefficientID󰀁basedproxysignaturescheme

frompairing[EB/OL].[2007-05-01].http://eprint.iacr.org/2006/158.

CRYPTO1984.Berlin:Springer,1984:47-53.

[7]󰀁BARRETOPSLM,LIBERTB,McCULLAGHETN,etal.Effi󰀁

cientandprovably󰀁secureidentity󰀁basedsignaturesandsigncryptionfrombilinearmaps[C]//ASIACRYPT2005.Berlin:Springer,2005:515-532.

[8]󰀁BONEHD,FRANKLINM.Identity󰀁basedencryptionfromtheWeil

pairing[C]//KILIANJ.AdvancesinCryptology:CRYPTO2001.Berlin:Springer,2001:213-229.

[9]󰀁SILVERMANJH.Thearithmeticofellipticcurves[M].NewYork:

Springer󰀁Verlag,1986.

[10]󰀁MILLERV.Shortprogramsforfunctionsoncurves[R/OL].(1986)

[2007-05-01]http://crypto.stanford.edu/miller/miller.pd.f

[11]󰀁BLAKEI,SEROUSSIG,SMARTN.Advancesinellipticcurvecryp󰀁

tography[M].Cambridge,UK:CambridgeUniversityPress,2005.

(上接第2711页)

间达到有效合作进化,最终使信任策略成为网络稳定进化、安全服务的有力保障。参考文献:

[1]󰀁SAROIUS,GUMMADIPK,GRIBBLES.Ameasurementstudyof

peer󰀁to󰀁peerfilesharingsystems[C]//MutlmiediaComputingandNet󰀁working(MMCN02).NewYork:Springer󰀁Verlag,2002:156-170.[2]󰀁KAMVARSD,SCHLOSSERMT,MOLINAHG.Theeigentrust

algorithmforreputationmanagementinP2Pnetworks[C]//WWW󰀁03:ProceedingsoftheTwelfthInternationalConferenceonWorldWideWeb.Budapest:ACMPress,2003:0-651.[3]󰀁KAMVARSD,SHLOSSERMT,MOLINAHG.EigenRep:Repu󰀁

tationmanagementinP2Pnetworks[C]//ProceedingsoftheTwelfthInternationalWorldWideWebConference.Budapest:ACMPress,2003:123-134.

[4]󰀁XIONGL,LIUL.Areputation󰀁basedtrustmodelforpeer󰀁to󰀁peerE󰀁

commercecommunities[C]//IEEEConferenceonE󰀁Commerce(CEC󰀁03).NewYork:IEEEComputerSociety,2003:275-284.[5]󰀁STOICAI,MORRISR,KARGERD,etal.Chord:Ascalable

peer󰀁to󰀁peerlookupserviceforinternetapplications[J].ComputerCommunicationReview,2001,31(4):149-160.

[6]󰀁ABERERK.P󰀁Grid:Aself󰀁organizingaccessstructureforP2Pin󰀁

formationsystems[C]//Proceedingsofthe6thInternationalConfer󰀁enceonCooperativeInformationSystems,Springer,2001:179-194.

[7]󰀁SZTOMPKAP.Trust:Asociologicaltheory[M].Cambridge:Cam󰀁

bridgeUniversityPress,1999.

[8]󰀁皋磊.基于生态网络的下一代Internet资源动态服务的研究

[D].上海:东华大学,2005.

LNCS2172.

Berlin:

4󰀁结语

本文基于进化博弈理论,从网络的整体安全性与稳定性入手,对网络中节点的策略行为选择采用复制动态机制进行了分析,从动力学的角度提出了相应的解决机制。也就是说,为了保持网络的安全与稳定,必须在网络中建立相应的激励机制与惩罚机制,使节点背叛失信变得不可取,从而使节点之