一種基于團(tuán)隊(duì)的P2P信譽(yù)機(jī)制設(shè)計(jì)

王 闖，管 剛，焦樹國(guó)

(軍事經(jīng)濟(jì)學(xué)院襄樊分院計(jì)算機(jī)教研室，襄樊441118)

1 引言

信譽(yù)機(jī)制的需求是伴隨著P2P的迅猛發(fā)展而產(chǎn)生的。在P2P應(yīng)用中，F(xiàn)reeRiding(搭便車)現(xiàn)象相當(dāng)突出，部分節(jié)點(diǎn)在節(jié)點(diǎn)間互享資源的時(shí)候，只享受服務(wù)而不提供服務(wù)。如在Gnutella中70%的節(jié)點(diǎn)不共享文件，而50%的文件請(qǐng)求由1%最好的節(jié)點(diǎn)提供服務(wù)［1］。這些最好的節(jié)點(diǎn)成了新形勢(shì)下的服務(wù)器，這顯然不符合研制P2P的初衷。因此，很早就有人提出需要建立一個(gè)可靠的信譽(yù)機(jī)制以限制或阻止FreeRiding，而這種機(jī)制必須要為正確服務(wù)的節(jié)點(diǎn)建立高的信譽(yù)，獲得一些特權(quán)，以鼓勵(lì)它繼續(xù)這種行為;與之對(duì)應(yīng)，對(duì)惡意服務(wù)的節(jié)點(diǎn)進(jìn)行懲罰，直到將它完全屏蔽在P2P應(yīng)用之外。

2 信譽(yù)機(jī)制的發(fā)展現(xiàn)狀

當(dāng)前存在的信譽(yù)模型可以分為典型的四類。即CAs、社會(huì)網(wǎng)絡(luò)、概率估計(jì)和博弈理論［2］。CAs(Certificate Agents)模型以CA做類似中央服務(wù)器式的服務(wù)，與P2P的分布式理念相左，可以基本排除;社會(huì)網(wǎng)絡(luò)的計(jì)算過程需要從所有節(jié)點(diǎn)獲取信息，雖然也通過某些近似方法作出改進(jìn)，但開銷仍然太大;概率估計(jì)模型開銷相對(duì)較小，但在初始階段可靠性不高;博弈應(yīng)用于信譽(yù)模型的理論比較少，單次博弈可以簡(jiǎn)單實(shí)現(xiàn)，但是連續(xù)博弈難度比較大，它需要仲裁機(jī)構(gòu)(中央服務(wù)器)的支持。后三類模型的優(yōu)劣比較見表 1［3］。

表1 三類信譽(yù)模型比較

通過以上的分析比較，筆者采用符合P2P特點(diǎn)的結(jié)構(gòu)化純分布式的概率估計(jì)模型——FTrust來構(gòu)建自己的信譽(yù)模型。

3 FTrust信譽(yù)機(jī)制設(shè)計(jì)

3.1 極大似然估計(jì)的信譽(yù)機(jī)制

FTrust以極大似然估計(jì)理論作為理論基礎(chǔ)，極大似然估計(jì)理論的工作原理如下:

節(jié)點(diǎn)Pi通過路由協(xié)議找到目標(biāo)節(jié)點(diǎn)Pj，想從Pj處獲得服務(wù)，而Pj正確服務(wù)的概率為全局值θj。Pi詢問第三方節(jié)點(diǎn)Pk關(guān)于Pj的信譽(yù)值，Pk說謊的可能為1k，如果每一個(gè)被詢問的第三方節(jié)點(diǎn)回饋信息{0，1}用隨機(jī)變量Yk表示，則Yk符合公式1所示的分布率(1表示Pk聲明Pj會(huì)正確服務(wù)，0表示不會(huì)):

一次對(duì)目標(biāo)節(jié)點(diǎn)Pj詢問的所有反饋事件為Y1、Y2…Yk這幾個(gè)隨機(jī)變量的取值，其聯(lián)合分布概率為 P(Y1=y1，Y2=y2，…Yk=yk)，此式是關(guān)于自變量 θj的方程，記作 L(θj)。Zoran Despotovic［4］直接給出L(θj)的計(jì)算式如下:

當(dāng) θj變化時(shí)，L(θj)跟著變化，當(dāng) L(θj)取得最大值時(shí)，θj就是對(duì)Pi來說Pj正確服務(wù)的概率。θj的大小，就是Pi用來決定是否從Pj獲取服務(wù)的依據(jù)。但很明顯，公式2成立的條件是Y1、Y2…Yk這幾個(gè)隨機(jī)變量相互獨(dú)立。但在文獻(xiàn)［4］中，這種條件不明顯成立。

3.2 FTrust信譽(yù)機(jī)制的原理

現(xiàn)實(shí)生活中，興趣愛好相同或相近的人很容易形成一個(gè)團(tuán)體，而這個(gè)團(tuán)體是自適應(yīng)的，既可以剔除舊成員，也可以增加新成員。當(dāng)某個(gè)成員變得對(duì)此團(tuán)體有所傷害的時(shí)候，會(huì)被其他成員探知，并通過一定的手段進(jìn)行懲罰，直到最后遭到團(tuán)隊(duì)的摒棄;當(dāng)外部節(jié)點(diǎn)通過它自身的努力，符合團(tuán)隊(duì)加入條件時(shí)，可以獲取團(tuán)隊(duì)資格，而一旦成功，則可以享受與其他團(tuán)隊(duì)成員相同的便利;團(tuán)體成員之間，更傾向于坦誠(chéng)相待，互通有無，以增加團(tuán)體的吸引力，吸收新的團(tuán)員;團(tuán)隊(duì)成員更加傾向于真實(shí)服務(wù)和推薦。

基于以上的思考，F(xiàn)Trust引入團(tuán)體概念，設(shè)置團(tuán)員之間坦誠(chéng)相待，使公式2中的隨機(jī)變量互相獨(dú)立變成可能，等號(hào)可以成立。通過設(shè)立Trans鏈表，設(shè)置Friends節(jié)點(diǎn)，保證各事件的獨(dú)立性。在此基礎(chǔ)之上，利用極大似然估計(jì)提供的計(jì)算方法，可以得到一個(gè)比較滿意的信譽(yù)機(jī)制效能。

FTrust重疊網(wǎng)絡(luò)從無到有的過程是這樣的。一開始網(wǎng)絡(luò)中只有若干獨(dú)立節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)都可以看作一個(gè)最小形式的團(tuán)隊(duì)。節(jié)點(diǎn)對(duì)其他節(jié)點(diǎn)來說都是新的，沒有任何信譽(yù)值可言，為了使他們之間能產(chǎn)生交互，使FTrust運(yùn)轉(zhuǎn)起來，設(shè)有一個(gè)默認(rèn)的信譽(yù)值(TRUST_DEFAULT_VALUE)。當(dāng)新節(jié)點(diǎn)以這個(gè)默認(rèn)值進(jìn)行了一定次數(shù)的傳輸之后，就可以依據(jù)過往傳輸記錄，計(jì)算并存儲(chǔ)相應(yīng)節(jié)點(diǎn)的信譽(yù)值。依據(jù)信譽(yù)值大小是否超過閾值TRUST_THRESHOLD_FRIEND，決定目標(biāo)節(jié)點(diǎn)是否能成為自己的伙伴節(jié)點(diǎn)。這樣，慢慢的伙伴之間就構(gòu)成了一個(gè)團(tuán)隊(duì)。

在將來的傳輸過程中，同一團(tuán)隊(duì)成員之間相互完全信賴，而不同的團(tuán)隊(duì)成員之間的傳輸需求，則依靠本團(tuán)隊(duì)成員的推薦或默認(rèn)信譽(yù)值，以決定是否進(jìn)行傳輸。記錄傳輸結(jié)果，更新信譽(yù)值。團(tuán)隊(duì)通過其成員與外界的交互作用，可以吸納新的團(tuán)員。另外，本團(tuán)隊(duì)內(nèi)成員之間的傳輸也要記錄，當(dāng)出現(xiàn)錯(cuò)誤的傳輸時(shí)，需要更新自己對(duì)目標(biāo)的信譽(yù)值，并廣播這種錯(cuò)誤，讓其它成員也對(duì)這種錯(cuò)誤傳輸有所感知，同時(shí)更新它們自己對(duì)目標(biāo)的信譽(yù)值。當(dāng)伙伴的傳輸錯(cuò)誤積累到一定程度時(shí)，請(qǐng)求服務(wù)節(jié)點(diǎn)將目標(biāo)節(jié)點(diǎn)從伙伴列表中刪除，然后廣播通知其他的伙伴，將目標(biāo)節(jié)點(diǎn)的錯(cuò)誤行為廣播。接收到廣播的節(jié)點(diǎn)進(jìn)行自己的處理:或者完全信任廣播將目標(biāo)清除出團(tuán)隊(duì)，或者降低目標(biāo)節(jié)點(diǎn)的信譽(yù)值。前者的作用比較直接，但容易被惡意節(jié)點(diǎn)利用;后者反應(yīng)雖然慢，但同樣能將錯(cuò)誤服務(wù)的節(jié)點(diǎn)驅(qū)除出團(tuán)隊(duì)。后者也伴生一個(gè)問題:如果惡意節(jié)點(diǎn)之間構(gòu)成共謀關(guān)系，互相協(xié)商對(duì)某個(gè)正常節(jié)點(diǎn)進(jìn)行詆毀。這種情況下，如果惡意節(jié)點(diǎn)占小部分，則它們會(huì)被驅(qū)除;否則，慢慢的會(huì)被其他正常節(jié)點(diǎn)與之發(fā)生傳輸時(shí)感知，從而主動(dòng)離開原團(tuán)隊(duì)。這樣，原團(tuán)隊(duì)就成了一個(gè)純的惡意節(jié)點(diǎn)，對(duì)團(tuán)隊(duì)外部的節(jié)點(diǎn)無影響。

4 FTrust的路由

4.1 路由協(xié)議的選擇

FTrust將作為信譽(yù)機(jī)制，實(shí)現(xiàn)P2P路由協(xié)議之上，構(gòu)成重疊網(wǎng)絡(luò)。Kademlia［5］是應(yīng)用于 eMule、Bit-Torrent、BitComet等軟件中成熟的一種結(jié)構(gòu)化純分布式P2P路由協(xié)議，經(jīng)受住了實(shí)際檢驗(yàn)。將FTrust構(gòu)建于Kademlia之上，控制文件下載的過程，幫助信譽(yù)值傳播。在安全性方面，Kademlia中節(jié)點(diǎn)經(jīng)過單向哈希生成ID標(biāo)記，在P2P應(yīng)用中自然就擁有了SHA－1單向哈希的保護(hù)，防止惡意節(jié)點(diǎn)冒充，減少tamper的可能。同時(shí)，因?yàn)镵ademlia中通過節(jié)點(diǎn)記錄相互存在的算法可以抵抗一些基本的DoS(拒絕服務(wù))攻擊。另外，F(xiàn)Trust通過團(tuán)隊(duì)的設(shè)立，降低collusion的發(fā)生。而 Free riding和 White washing(洗黑錢)節(jié)點(diǎn)跟新加入的節(jié)點(diǎn)一樣，沒有利用到團(tuán)隊(duì)提供給自己的便利，沒有利益可圖。

4.2 路由流程

FTrust每個(gè)節(jié)點(diǎn)擁有一個(gè)Trans表，里面保存一定數(shù)目與之發(fā)生過傳輸?shù)墓?jié)點(diǎn)信息，包括正確傳輸和錯(cuò)誤傳輸?shù)拇螖?shù)，以及一個(gè) Friends標(biāo)識(shí)位。Friends節(jié)點(diǎn)擁有很高的權(quán)限，本地節(jié)點(diǎn)無條件接受Friends節(jié)點(diǎn)的服務(wù)或推薦。一個(gè)包含 FTrust的P2P文件共享應(yīng)用流程如圖1所示。

圖1 FTrust流程

第①步，節(jié)點(diǎn)i發(fā)出一個(gè)文件搜索請(qǐng)求，請(qǐng)求關(guān)鍵字為fname的文件。第②步，Kademlia路由協(xié)議返回那些聲稱自己擁有fname文件的節(jié)點(diǎn)。節(jié)點(diǎn)i暫存這些節(jié)點(diǎn)信息，將這些節(jié)點(diǎn)記為集合［pa］。第③步，節(jié)點(diǎn)i向［pa］中的所有節(jié)點(diǎn)發(fā)送文件請(qǐng)求。第④步，［pa］中的節(jié)點(diǎn)返回文件名及該文件的SHA－1標(biāo)識(shí)碼。節(jié)點(diǎn)i比較這些標(biāo)識(shí)碼，剔除那些與大多數(shù)標(biāo)識(shí)碼不同的節(jié)點(diǎn)，縮減備選節(jié)點(diǎn)集合記［pb］。第⑤步，詢問集合［pb］中各節(jié)點(diǎn)的信譽(yù)值。第⑥步，通過信譽(yù)機(jī)制，得到各節(jié)點(diǎn)信譽(yù)值。節(jié)點(diǎn)i取信譽(yù)值最大的幾個(gè)記為集合［pc］。第⑦步，節(jié)點(diǎn)i向［pc］中節(jié)點(diǎn)發(fā)送文件下載請(qǐng)求。第⑧步，目標(biāo)節(jié)點(diǎn)返回對(duì)應(yīng)文件或文件塊。第⑨步，節(jié)點(diǎn)i對(duì)獲得的文件或文件塊進(jìn)行單項(xiàng)哈希，得到SHA－1標(biāo)識(shí)碼，與之前得到的標(biāo)識(shí)碼進(jìn)行比較，若相同則表明是正確傳輸，提升目標(biāo)節(jié)點(diǎn)的信譽(yù)值;否則是錯(cuò)誤傳輸，則降低目標(biāo)節(jié)點(diǎn)的信譽(yù)值，然后從［pc］中選擇另外的節(jié)點(diǎn)執(zhí)行步驟⑦→⑨，如果仍然不成功，則選擇集合［pb］－［pc］中的節(jié)點(diǎn)執(zhí)行步驟⑦→⑨，若仍不成功，則放棄。

⑤⑥⑨是FTrust在一般P2P應(yīng)用基礎(chǔ)上新加入的步驟，其中⑤⑥兩步利用了極大似然估計(jì)的方法，第⑨步Renew表的時(shí)候，明確錯(cuò)誤付出的代價(jià)比成功得到的利益要大，目的是懲罰惡意行為。

5 FTrust的性能分析

設(shè)置50個(gè)節(jié)點(diǎn)，其中10個(gè)惡意節(jié)點(diǎn)，40個(gè)善意節(jié)點(diǎn)。善意節(jié)點(diǎn)總是正確服務(wù)并正確推薦，而惡意節(jié)點(diǎn)則相反。測(cè)試程序隨機(jī)讓兩個(gè)節(jié)點(diǎn)之間發(fā)生傳輸(節(jié)點(diǎn)1和節(jié)點(diǎn)2)，統(tǒng)計(jì)數(shù)據(jù)total trans(總有效傳輸數(shù)目)加一。節(jié)點(diǎn)1用FTrust機(jī)制詢問它所知道的關(guān)于節(jié)點(diǎn)2的信譽(yù)值，然后根據(jù)FTrust的策略選擇是否從節(jié)點(diǎn)2獲取服務(wù)。如果決定獲取，又如果服務(wù)結(jié)果是成功，則統(tǒng)計(jì)數(shù)據(jù)succ增加一，若失敗，則統(tǒng)計(jì)數(shù)據(jù) fail增加一，節(jié)點(diǎn)1更新自己的TrustMap;如果決定不獲取，節(jié)點(diǎn)2如果是善意節(jié)點(diǎn)，統(tǒng)計(jì)數(shù)據(jù)wrong decision增加一。顯然，如果沒有信譽(yù)機(jī)制的作用，那么應(yīng)該有10/50=20%的傳輸是失敗的。

圖2顯示了FTrust網(wǎng)絡(luò)中(默認(rèn)信譽(yù)值為0.5)各項(xiàng)統(tǒng)計(jì)數(shù)據(jù)占總有效傳輸數(shù)目的比例。可以看出，排除錯(cuò)誤傳輸和錯(cuò)誤決定所占的一成之外，其余九成是正確傳輸和正確決定的比例。

圖2 TRUST_DEFAULT_VALUE=0.5傳輸比例統(tǒng)計(jì)圖

進(jìn)一步的實(shí)驗(yàn)表明，不同的TRUST_DEFAULT_VALUE值對(duì)成功傳輸和錯(cuò)誤決定的影響只在收斂速度上，另外，其值越小，失敗傳輸比例越小。當(dāng)值為0.1時(shí)，錯(cuò)誤傳輸比例降到0.02。所以TRUST_DEFAULT_VALUE越小，效果越好。因此，從長(zhǎng)遠(yuǎn)來看，選擇小值是比較好的。因?yàn)镕Trust擁有退出網(wǎng)絡(luò)時(shí)，將TrustMap保存起來的功能。在這一層意義上，較小值造成收斂速度較慢的影響可以在一定程度上消減下來。后續(xù)實(shí)驗(yàn)中，該值取折中值0.3。

6 FTrust與單純極大似然估計(jì)機(jī)制比較

Zoran Despotovic［4］在極大似然估計(jì)實(shí)驗(yàn)中設(shè)置惡意節(jié)點(diǎn)總是錯(cuò)誤服務(wù)，而一般的節(jié)點(diǎn)以一個(gè)隨機(jī)的固定概率值提供錯(cuò)誤服務(wù)。當(dāng)節(jié)點(diǎn)需要第三方的推薦時(shí)，只用搜集到10－20個(gè)證據(jù)就可以進(jìn)行計(jì)算。第三方節(jié)點(diǎn)撒謊的概率是全局同一的，但是這個(gè)值并沒有在文中提供，所以不得而知，其結(jié)果如圖3所示。而在FTrust實(shí)驗(yàn)中，第三方節(jié)點(diǎn)撒謊的概率是依節(jié)點(diǎn)而不同的，為1－trust，其中trust是第三方在發(fā)起源看來的信譽(yù)值，因此如果第三方是發(fā)起源的伙伴，那么撒謊概率為0，也就是完全相信自己的伙伴。這也就要求對(duì)成為伙伴的要求要高一點(diǎn)，TRUST_THRESHOLD_FRIEND(稱為伙伴的信譽(yù)值要求)設(shè)為0.8。實(shí)驗(yàn)中，一般節(jié)點(diǎn)不僅以一定的概率錯(cuò)誤服務(wù)，而且以一定的概率錯(cuò)誤推薦，然后根據(jù)不同惡意節(jié)點(diǎn)的比例，跟蹤錯(cuò)誤服務(wù)的數(shù)目(錯(cuò)誤決定的數(shù)目趨向于0，因此不再列出)，實(shí)驗(yàn)結(jié)果如圖4所示。

圖3 采用單純極大似然估計(jì)機(jī)制的實(shí)驗(yàn)結(jié)果圖

圖4 采用FTrust機(jī)制的實(shí)驗(yàn)結(jié)果圖

從上述兩圖可以看出，F(xiàn)Trust穩(wěn)定時(shí)錯(cuò)誤率在0.3到0.42之間，而極大似然估計(jì)最大則超過0.5。同時(shí)，極大似然估計(jì)的一個(gè)典型特點(diǎn)是，當(dāng)惡意節(jié)點(diǎn)占到0.5以上時(shí)，錯(cuò)誤率不會(huì)再增高，而相反會(huì)降低一些。當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)不可信時(shí)，它會(huì)采取相反的決定。而FTrust也繼承了這一優(yōu)點(diǎn)。

7 結(jié)束語

論文設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)切實(shí)可行的信譽(yù)機(jī)制FTrust，使其工作在P2P環(huán)境中。通過社會(huì)學(xué)和計(jì)算機(jī)科學(xué)的結(jié)合，引入團(tuán)體的概念，構(gòu)造出的FTrust，具有不俗的性能表現(xiàn)，同時(shí)通過Kademlia路由協(xié)議合理控制資源耗費(fèi)代價(jià)。通過構(gòu)造的實(shí)驗(yàn)場(chǎng)景對(duì)FTrust的性能分析可知，F(xiàn)Trust的作用明顯，特別是與單純極大似然估計(jì)機(jī)制相比。

［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.