EigenTrust信任模型

TheEigenTrustAlgorithmforReputationManagementinP2PNetworksSepandarD.KamvarMarioT.SchlosserHectorGarcia-MolinaStanfordUniversity2Problem:ReduceinauthenticfilesdistributedbymaliciouspeersonaP2Pnetwork.Motivation:Problem“Majorrecordlabelshavelaunchedanaggressivenewguerrillaassaultontheundergroundmusicnetworks,floodingonlineswappingserviceswithboguscopiesofpopularsongs.”-SiliconValleyWeekly3ProblemGoal:Toidentifysourcesofinauthenticfilesandbiaspeersagainstdownloadingfromthem.Method:Giveeachpeeratrustvaluebasedonitspreviousbehavior.0.90.14SomeapproachesPastHistoryFriendsofFriendsEigenTrust5TerminologyLocaltrustvalue:cij.Theopinionthatpeerihasofpeerj,basedonpastexperience.Globaltrustvalue:ti.Thetrustthattheentiresystemplacesinpeeri.Peer1Peer3Peer2Peer4t4=0t1=.3t3=.5t2=.2C21=0.6C23=0.7C14=0.01C12=0.36LocalTrustValuesEachtimepeeridownloadsanauthenticfilefrompeerj,cijincreases.Eachtimepeeridownloadsaninauthenticfilefrompeerj,cijdecreases.PeeriPeerjCij=7NormalizingLocalTrustValuesAllcijnon-negativeci1+ci2+...+cin=1Peer2Peer1Peer4C14=0.1C12=0.9Peer2Peer4Peer18LocalTrustVectorLocaltrustvectorci:containsalllocaltrustvaluescijthatpeerihasofotherpeersj.1.009.0000Peer2Peer4Peer1c1Peer2Peer1Peer4C14=0.1C12=0.99SomeapproachesPastHistoryFriendsofFriendsEigenTrust10PasthistoryEachpeerbiasesitschoiceofdownloadsusingitsownopinionvectorci.Ifithashadgoodpastexperiencewithpeerj,itwillbemorelikelytodownloadfromthatpeer.Problem:Eachpeerhaslimitedpastexperience.Knowsfewotherpeers.000000Peer4Peer6Peer1??????11FriendsofFriendsAskfortheopinionsofthepeoplewhoyoutrust.000000Peer4Peer6Peer1000000Peer2Peer812FriendsofFriendsWeighttheiropinionsbyyourtrustinthem.000000Peer4Peer1000000Peer2Peer8Peer413TheMathjjkijcccik'AskyourfriendsjWhattheythinkofpeerk.Andweighteachfriend’sopinionbyhowmuchyoutrusthim.TC'icic.1.5000.20.20.30.5.1000.1.3.2.3.1.1.214ProblemwithFriendsEitheryouknowalotoffriends,inwhichcase,youhavetocomputeandstoremanyvalues.Or,youhavefewfriends,inwhichcaseyouwon’tknowmanypeers,evenafteraskingyourfriends.000000000000000000000000000000000015DualGoalWewanteachpeerto:Knowallpeers.Performminimalcomputation(andstorage).16KnowingAllPeersAskyourfriends:t=CTci.Asktheirfriends:t=(CT)2ci.Keepaskinguntilthecowscomehome:t=(CT)nci.00000000000000000000000017MinimalComputationLuckily,thetrustvectort,ifcomputedinthismanner,convergestothesamethingforeverypeer!Therefore,eachpeerdoesn’thavetostoreandcomputeitsowntrustvector.Thewholenetworkcancooperatetostoreandcomputet.18Non-distributedAlgorithmInitialize:Repeatuntilconvergence:(k)T1)(ktCtT(0)tnn1...119DistributedAlgorithmNocentralauthoritytostoreandcomputet.Eachpeeriholdsitsownopinionsci.Fornow,let’signorequestionsoflying,andleteachpeerstoreandcomputeitsowntrustvalue.)()(11)1(...knnikikitctct.1.5000.20.20.30.5.1000.1.3.2.3.1.1.220DistributedAlgorithmForeachpeeri{-First,askpeerswhoknowyoufortheiropinionsofyou.-Repeatuntilconvergence{-Computecurrenttrustvalue:ti(k+1)=c1jt1(k)+…+cnjtn(k)-Sendyouropinioncijandtrustvalueti(k)toyouracquaintances.-Waitforthepeerswhoknowyoutosendyoutheirtrustvaluesandopinions.}}21ProbabilisticInterpretation22MaliciousCollectives23Pre-trustedPeersBattlingMaliciousCollectivesInactivePeersIncorporatingheuristicnotionsoftrustConvergenceRate24Pre-trustedPeersBattlingMaliciousCollectivesInactivePeersIncorporatingheuristicnotionsoftrustConvergenceRate25SecureScoreManagementTwobasicideas:Insteadofhavingapeercomputeandstoreitsownscore,haveanotherpeercomputeandstoreitsscore.Havemultiplescoremanagerswhovoteonapeer’sscore.MMMMScoreManagerScoreManagers????DistributedHashTable26HowtousethetrustvaluestiWhenyougetresponsesfrommultiplepeers:Deterministic:Choosetheonewithhighesttrustvalue.Probabilistic:Chooseapeerwithprobabilityproportionaltoitstrustvalue.27LoadDistributionDeterministicDownloadChoiceProbabilisticDownloadChoice28ThreatScenariosMaliciousIndividualsAlwaysprovideinauthenticfiles.MaliciousCollectiveAlwaysprovideinauthenticfiles.Knoweachother.Giveeachothergoodopinions,andgiveotherpeersbadopinions.29MoreThreatScenariosCamouflagedCollectiveProvideauthenticfilessomeofthetimetotrickgoodpeersintogivingthemgoodopinions.MaliciousSpiesSomemembersofthecollectivegivegoodfilesallthetime,butgivegoodopinionstomaliciouspeers.30MaliciousIndividuals31MaliciousCollective32CamouflagedCollective33MaliciousSpies34Simulations35ConclusionEigentrustDramaticallyreducesnumberofinauthenticfilesonthenetwork.Robusttomaliciouspeers.Lowoverhead.36TheEndPaperavailableat