一種基于團隊的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.