P2P網絡中有效消解多Sybil節點滲透衝突的方法
2023-05-12 18:03:21
P2P網絡中有效消解多Sybil節點滲透衝突的方法
【專利摘要】本發明公開了一種P2P網絡中有效消解多Sybil節點滲透衝突的方法，目的是解決Sybil節點向Kademlia進行滲透的過程中因出現節點間滲透衝突而導致整體滲透效能下降的問題。技術方案是通過劃分滲透區域和對Sybil節點進行編組，實現分區域滲透，避免各組Sybil節點間發生滲透衝突；通過為Sybil節點合理分配節點的標識，避免組內Sybil節點間發生效能衝突。採用本發明可以提高多個Sybil節點的總體滲透效能，避免多個Sybil節點在向Kademlia網絡進行無序滲透時造成的資源浪費和效能流失，且可使Sybil節點在Kademlia網絡動態變化過程中保證其滲透效能。
【專利說明】P2P網絡中有效消解多Sybi I節點滲透衝突的方法
【技術領域】
[0001]本發明涉及提高多Sybil節點對Kademlia網絡滲透效能的方法,尤指Kademlia網絡中有效消解多Sybil節點滲透衝突的方法。
【背景技術】
[0002]Kademlia是美國紐約大學的Petar Maymounkov等人於2002年提出的一種結構化P2P協議；基於Kademlia協議構建的P2P網絡稱為Kademlia網絡。Kademlia協議是一種典型的DHT (Distributed Hash Table,分布哈希表)協議,廣泛用於構建大規模、純分布式P2P (Peer to Peer)網絡,如電驢、BitTorrent等。Kademlia給每個節點分配一個唯一、隨機的節點標識，即nodeID ;為每個對象分配一個類似的對象標識，即objectID(又稱為key)。這些標識通常使用SHA-1這種單向散列函數來生成，ID之間的距離採用異或運算來度量。
[0003]在Kademlia網絡中，每個對象都存儲在節點標識最接近其對象標識的K個節點上。K是一個常數，一般取值為20。
[0004]每個Kademlia節點的路由表由L(L等於節點標識的比特位數,通常取值為128)個鍊表組成，每個鍊表稱為一個「K-bucket」，用於記錄網絡中到自己的異或距離在區間[21, 2i+1) (i為K-bucket的序號，O≤i < L)內的鄰居節點的信息，每條信息以三元組形式表示和存儲。Kademlia協議規定，K-bucket長度以K為上限。每當Kademlia節點收到來自其他節點的消息,它就根據該消息發送節點到自己的異或距離以及消息中的信息來更新K-bucket中的記錄,這稱為捎帶確認(piggybacking)。L個K-bucket組成一個Kademlia節點的路由表，因此路由表也稱「K-buckets」。一個路由表中的L個K-bucket通過連續的序號i區分。
[0005]Kademlia協議由四個RPC(Remote Process Call,遠程過程調用，是一種命令)組成，其名稱分別是PING，STORE, FIND_N0DE, FIND_VALUE，它們的工作如下所示:
[0006]PING:探測一個節點是否在線；
[0007]STORE:指示一個節點存儲一個對，以便於將來的數據獲取。key為對象散列值，即obiectID, value為真正的數據對象(或其索引)；
[0008]FIND_N0DE:以 ID 為參數，FIND_N0DE RPC 的接收者以 的形式返回他所知的離目標ID最近的K個節點；
[0009]FIND_VALUE:以 key 為參數，尋找 key 對應的 value。
[0010]Sybil節點原指具有多重身份的單個實體節點，目前通常將網絡中的虛假節點都稱為Sybil節點。對於Kademlia網絡中的Sybil節點，其重要性主要體現為能夠成為多少節點的鄰居節點，即該Sybil節點的入度大小。快速提高Sybil節點的重要性，有助於利用Sybil節點更多、更高效地獲知網絡中大量節點的活動情況，從而為快速發現和遏制網絡中的惡意活動提供技術支撐。
[0011]Sybil節點重要性的提升，主要依賴於儘可能多的將自身加入到Kademlia網絡節點的路由表中，即滲透。但是，在滲透的過程中，多個Sybil節點可能會進入同一個Kademlia節點的同一個K-bucket中；當該節點在該K-bucket進行某些網絡活動時,報文會同時發送到多個Sybil節點。這樣，一個節點的活動被多個Sybil節點所感知，實質上造成了感知能力的冗餘。這種情況稱為Sybil節點之間的滲透衝突，滲透衝突引起滲透效能的下降。由於Kademlia網絡規模一般都較大，Sybil節點的數量和性能有限，因此應當儘量避免滲透效能發生衝突的情況，以提高多個Sybil節點的整體滲透效能。
[0012]P2P網絡爬蟲是指用於獲取P2P網絡中各個節點信息及其拓撲結構的軟體系統。這種軟體系統通過迭代地向P2P網絡中的已知節點發送特定消息，獲得新的節點；再重複向新的節點發送特定消息，就可以獲得整個網絡的拓撲結構和各個節點信息。P2P網絡爬蟲能夠用於獲取Kademlia網絡的節點信息和拓撲結構。
[0013]目前尚沒有針對Kademlia網絡消除Sybil節點滲透衝突的方法的公開報導。
【發明內容】
[0014]本發明要解決的技術問題在於:針對多個Sybil節點在向Kademlia進行滲透的過程中，可能因出現節點間滲透衝突而導致整體滲透效能下降的問題，提出Kademlia網絡中有效消解多Sybil節點滲透衝突的一種方法,使多個Sybil節點通過避免相互之間的滲透衝突而優化整體滲透效能。
[0015]為解決上述技術問題，本發明的技術方案為:通過劃分滲透區域和對Sybil節點進行編組，實現分區域滲透，避免各組Sybil節點間發生滲透衝突；通過為Sybil節點合理分配節點的標識nodeID,避免組內Sybil節點間發生效能衝突,nodeID為L比特,L為正整數，通常取值為128。
[0016]對於nodeID為L 比特的Kademlia網絡來說，節點標識空間為2L，Sybil節點的數量可設置為q.2H 「.」表示乘法運算，q為整數，一般取值為5)。本發明具體步驟如下:
[0017]第一步，劃分滲透區域。將整個Kademlia網絡節點標識空間平均劃分為2q個滲透區域，此時這些滲透區域可表示為{?.2ιΛ (」+1)20)|0≤_]_≤2<1-1，」為整數}，其中每個元素是一個區間，每個元素中的整數對應滲透區域中的節點標識，記[j.2L-\ (j+l)2L-q)為第j號滲透區域。
[0018]第二步，Sybil節點編組。將所有Sybil節點編為2q個組,每組q個Sybil節點，並依次用O到(2[1)這2^個整數作為組號。
[0019]第三步，設置Sybil節點的標識nodeID。對於組號為P (O2q-l)的Sybil節點編組，將集合{ (P ? 2「) I O < a < q-1，a為整數} ( φ表示異或運算，通過2a與組號p的異或運算來區分距離，確保組內不同的Sybi I節點出現在Kademl ia節點的不同K-bucket中)中的這q個值作為nodeID分配給組內的q個Sybil節點。
[0020]第四步,通過P2P網絡爬蟲(如開源的Emule客戶端程序、Nutch、Crawler4j等)獲得整個Kademlia網絡中所有節點的路由表，即每個節點的鄰居節點的，並通過路由表獲得每個節點的節點度d(即節點的路由表中鄰居節點的個數)。
[0021]第五步，對2^個滲透區域中的節點，分別按照節點度d的大小進行降序排列，形成2q個列表，其中每個列表稱為對應滲透區域的節點降序列表；依次將第j號滲透區域的節點降序列表發送給組號為j的Sybil編組中的每個Sybil節點，具體步驟如下:[0022]5.1令」=0。
[0023]5.2將j號滲透區域的節點降序列表發送給組號為j的Sybil編組中的q個Sybil節點。
[0024]5.3j = j+1 ο
[0025]5.4判斷j是否等於2%如果等於，則轉第六步，否則，轉5.2)。第六步，設置全局計數器Ne，並為每個Sybil節點設置一個局部計數器隊(O≤r≤q.2M)，Ng,Nr都初始化為0，所有Sybil節點並行執行如下步驟:
[0026]6.1向第五步中收到的節點降序列表中的首節點發送PING探測命令，然後將該首節點從節點降序列表中刪除。
[0027]6.2判斷節點降序列表是否為空。如果為空，Nr = Nr+1,NG = NG+1並轉第6.3步；否則，轉第6.1步。
[0028]6.3查詢是否所有Sybil節點都完成了步驟6.1-6.2，即判斷Ne是否等於q.2q。是，則轉第七步；否則執行一個空操作後轉6.3。
[0029]第七步,設置計時器為T小時，T可取值為6。
[0030]第八步，間歇t秒，t可取值為5。
[0031]第九步，判斷是否從系統進程接收到結束指令:是，轉第十一步；否則轉第十步；
[0032]第十步，判斷是否計時器時間用完:是，轉第四步；否，轉第八步。
[0033]第^^一步，結束。
[0034]採用本發明可以達到以下技術效果:
[0035]通過在第一步和第二步中對Kademlia網絡節點和Sybil節點進行科學分組,並在第三步中合理設置各個Sybil節點的nodeID值，有效地消解了多個Sybil節點之間的滲透衝突，提高了多個Sybil節點的總體滲透效能,避免了多個Sybil節點在向Kademlia網絡進行無序滲透時造成的資源浪費和效能流失。通過在第四步獲得網絡中各節點最新的路由表，可以使得Sybil節點在Kademlia網絡動態變化的過程中，仍然能夠保證其滲透效能。
【專利附圖】
【附圖說明】
[0036]圖1為本發明的總流程圖。
【具體實施方式】
[0037]1、劃分滲透區域。將整個Kademlia網絡節點標識空間平均劃分為2q個滲透區域，此時這些滲透區域可表示為{[j.2ιΛ (j+l)2L-<1) |0≤j < 2q，j為整數}，其中每個元素是一個區間，每個元素中的整數對應滲透區域中的節點標識，記[j.2L-\ (j+ld為第j號滲透區域。
[0038]2、Sybil節點編組。將所有Sybil節點編為2q個組，每組q個Sybil節點，並依次用O到(211)這2^個整數作為組號。
[0039]3、設置Sybil節點的標識nodeID。對於組號為p (O≤p≤2q-l)的Sybil節點編組，將集合{ (P ? 2「).2^ I O≤a < q，a為整數} ( ?表示異或運算，通過2a與組號p的異或運算來區分距離，確保組內不同的Sybil節點出現在Kademlia節點的不同K-bucket中)中的這q個值作為nodeID分配給組內的q個Sybil節點。[0040]4、通過P2P網絡爬蟲(如開源的Emule客戶端程序、Nutch、Crawler4j等)獲得整個Kademlia網絡中節點的路由表，即鄰居節點的。
[0041]5、對2^個滲透區域中的節點，分別按照節點度d的大小進行降序排列，形成2^個列表，其中每個列表稱為對應滲透區域的節點降序列表；依次將第j號滲透區域的節點降序列表發送給組號為j的Sybil編組中的每個Sybil節點。
[0042]6、設置全局計數器Ne，並為每個Sybil節點設置一個局部計數器Nr (O 2M)，Ng, Nr都初始化為0，所有Sybil節點並行執行如下步驟:
[0043]6.1向步驟5中收到的節點降序列表中的首節點發送PING命令，然後將該首節點從節點降序列表中刪除。
[0044]6.2判斷節點降序列表是否為空。如果為空，Nr = Nr+1, Ng = Ng+I並轉步驟6.3 ；否則，轉步驟6.1。
[0045]6.3查詢是否所有Sybil節點都完成了步驟6.1-6.2，即判斷Ne是否等於q.2q。是，則轉步驟7 ;否則執行一個空操作後轉6.3。
[0046]7、設置計時器為T小時，T可取值為6。
[0047]8、間歇t秒，t可取值為5。
[0048]9、判斷是否從系統進程接收到結束指令:是，轉步驟11 ;否則轉步驟10 ； [0049]10、判斷是否計時器時間用完:是，轉步驟4 ;否，轉步驟8。
[0050]11、結束。
【權利要求】
1.一種P2P網絡中有效消解多Sybil節點滲透衝突的方法，其特徵在於包括以下步驟: 第一步，劃分滲透區域Jf-AKademlia網絡節點標識空間平均劃分為2q個滲透區域，這些滲透區域表示為{[j.2^, (j+ld |0≤j < 2' j為整數}，其中每個元素是一個區間，每個元素中的整數對應滲透區域中的節點標識，記[j.2L-\ (j+ld為第j號滲透區域；Kademlia網絡節點標識稱為nodeID, nodeID為L比特的Kademlia網絡的節點標識空間為2S L為正整數，Sybil節點的數量為q.2%「.」表示乘法運算，q為整數； 第二步，Sybil節點編組:將所有Sybil節點編為2q個組,每組q個Sybil節點，並依次用O到2^-1這2^個整數作為組號； 第三步，設置Sybil節點的標識nodeID:對於組號為p的Sybil節點編組，O≤P≤2^-1，將集合！(P十2a).2?0≤a < q，a為整數}中的這q個值作為nodeID分配給組內的q個Sybil節點；Θ表示異或運算，通過2a與組號P的異或運算來區分距離，確保組內不同的Sybil節點出現在Kademlia節點的不同K_bucket中；每個Kademlia節點的路由表由L個鍊表組成，每個鍊表稱為一個「K-bucket」，用於記錄網絡中到自己的異或距離在區間[21，2i+1)內的鄰居節點的信息，i為K-bucket的序號，O≤i < M ;每條信息以三元組形式表示和存儲，K-bucket長度以K為上限，K是一個常數；每當Kademlia節點收到來自其他節點的消息,它就根據該消息發送節點到自己的異或距離以及消息中的信息來更新K-bucket中的記錄，這稱為捎帶確認piggybacking山個K-bucket組成一個Kademlia節點的路由表,路由表也稱「K-buckets」, 一個路由表中的L個K-bucket通過連續的序號i區分； 第四步，通過P2P網絡爬蟲獲得整個Kademlia網絡中所有節點的路由表，即鄰居節點的，並通過路由表獲得每個節點的節點度d，節點度指節點的路由表中鄰居節點的個數，即節點的路由表中的表項數； 第五步，對個滲透區域中的節點，分別按照節點度d的大小進行降序排列，形成2^個列表，其中每個列表稱為對應滲透區域的節點降序列表；將第j號滲透區域的節點降序列表發送給組號為j的Sybil編組中的每個Sybil節點,具體步驟如下:
.5.1 令 j = O ; .5.2將j號滲透區域的節點降序列表發送給組號為j的Sybil編組中的q個Sybil節佔.5.3j = j+1 ； .5.4判斷j是否等於2%如果等於，則轉第六步，否則，轉5.2)； 第六步，設置全局計數器Ne，並為每個Sybil節點設置一個局部計數器隊，O≤r≤q.2q-l, Ng, Nr都初始化為0，所有Sybil節點並行執行如下步驟: .6.1向收到的節點降序列表中的首節點發送PING探測命令，然後將該首節點從節點降序列表中刪除；PING探測命令是Kademlia協議中的一種遠程過程調用； .6.2判斷節點降序列表是否為空，如果為空，N, = Nr+1，NG = Ng+1並轉第6.3步；否則，轉第6.1步； .6.3判斷Ne是否等於q.2%是，轉第七步；否則執行一個空操作後轉6.3 ； 第七步，設置計時器為T小時，T取值為6 ；第八步，間歇t秒，t取值為5; 第九步，判斷是否從系統進程接收到結束指令:是，轉第十一步；否則轉第十步； 第十步，判斷是否計時器時間用完:是，轉第四步；否，轉第八步。 第H^一步，結束。
2.如權利要求1所述的P2P網絡中有效消解多Sybil節點滲透衝突的方法，其特徵在於所述L取值為128，q 取值為5，K取值為20。
【文檔編號】H04L29/08GK104038547SQ201410269637
【公開日】2014年9月10日 申請日期:2014年6月17日 優先權日:2014年6月17日
【發明者】劉波, 王懷民, 王天佐, 魯強, 肖哲鋒, 張天, 馬曉龍, 于洋 申請人:中國人民解放軍國防科學技術大學