基于小世界理論的區(qū)塊鏈Kademlia 網(wǎng)絡(luò)改進(jìn)方法

趙越，趙赫，譚海波，余斌，俞望年，馬志宇

(1.中國科學(xué)院合肥物質(zhì)科學(xué)研究院，安徽 合肥 230031；2.中國科學(xué)技術(shù)大學(xué)，安徽 合肥 230026；3.安徽中科晶格技術(shù)有限公司，安徽 合肥 230088)

區(qū)塊鏈技術(shù)具有防篡改、可追溯、安全可信的特點，被廣泛應(yīng)用在加密數(shù)字貨幣、供應(yīng)鏈物流、信息共享等領(lǐng)域[1].它的可擴(kuò)展性具有明顯的不足，主要原因之一是它采用的P2P 網(wǎng)絡(luò)結(jié)構(gòu)存在缺陷.當(dāng)網(wǎng)絡(luò)規(guī)模增大后，傳輸性能會逐漸下降.為了改善區(qū)塊鏈網(wǎng)絡(luò)的性能，需要優(yōu)化網(wǎng)絡(luò)結(jié)構(gòu).本研究主要關(guān)注區(qū)塊鏈Kademlia 網(wǎng)絡(luò)，它的典型項目有以太坊、Filecoin、Storj 等.本研究受到Kleignberg 的小世界理論[2]的啟發(fā)，通過引入置換擴(kuò)容節(jié)點的概率公式，以提升網(wǎng)絡(luò)傳輸性能.

1 相關(guān)工作

當(dāng)前，區(qū)塊鏈Kad 網(wǎng)絡(luò)性能方面的研究主要集中在通過改變網(wǎng)絡(luò)結(jié)構(gòu)以提高數(shù)據(jù)傳輸效率.Yu 等[3]將K 桶均勻劃分成多個區(qū)域，每個分區(qū)存儲不同的節(jié)點信息.Liang[4]為網(wǎng)絡(luò)中所有節(jié)點都添加了本地緩存以擴(kuò)大存儲空間.此外，部分研究探討了加快節(jié)點定位速率的方法.Zhang 等[5]提出Kadabra 協(xié)議，該協(xié)議創(chuàng)造了可以根據(jù)網(wǎng)絡(luò)的異質(zhì)性進(jìn)行動態(tài)調(diào)整的路由表，減少了網(wǎng)絡(luò)查找的延遲.網(wǎng)絡(luò)結(jié)構(gòu)的改變?nèi)菀讚p害網(wǎng)絡(luò)的安全性，為了增強(qiáng)網(wǎng)絡(luò)抵御攻擊的能力，Eisenbarth 等[6]分析以太坊的網(wǎng)絡(luò)特性，提出檢測和廢除可疑節(jié)點的架構(gòu)，以抵御Sybil 攻擊.類似地，Xu 等[7]設(shè)計基于隨機(jī)森林分類算法的日蝕攻擊檢測模型，能以較高的準(zhǔn)確率檢測出以太坊網(wǎng)絡(luò)中的惡意節(jié)點.

小世界現(xiàn)象源于Milgram[8]設(shè)計的小世界實驗，他通過實驗證明只需不到6 個人就可以將一封信從奧馬哈市的志愿者寄送給波士頓的一位居民.Watts 等[9]通過對規(guī)則網(wǎng)絡(luò)的每條邊進(jìn)行隨機(jī)化重連，構(gòu)建WS 小世界模型.通過實驗發(fā)現(xiàn)，該模型的網(wǎng)絡(luò)性能優(yōu)于結(jié)構(gòu)化網(wǎng)絡(luò)，但是可能出現(xiàn)孤立節(jié)點.Watts 等[10]對其加以改進(jìn)，提出NW 小世界模型，將隨機(jī)化重連改為隨機(jī)化加邊，保證了網(wǎng)絡(luò)的連通性.Kleignberg 系統(tǒng)地研究小世界理論，給出建立小世界網(wǎng)絡(luò)的具體方法.通過該方法，Zou 等[11-12]將小世界理論應(yīng)用于Can 和Chord這2 種P2P 網(wǎng)絡(luò)，提升了網(wǎng)絡(luò)性能.近年來，一些學(xué)者嘗試將小世界理論引入?yún)^(qū)塊鏈網(wǎng)絡(luò)中.Serena等[13]使用分布式賬本網(wǎng)絡(luò)分析器，研究比特幣和以太坊網(wǎng)絡(luò)的交易圖，檢測到這些交易圖都有小世界特征.Wang等[14]利用以太坊網(wǎng)絡(luò)分析儀探測以太坊的P2P 網(wǎng)絡(luò)，發(fā)現(xiàn)該網(wǎng)絡(luò)具有無標(biāo)度網(wǎng)絡(luò)的特征且存在一定的小世界效應(yīng).

2 基于小世界理論的Kademila 網(wǎng)絡(luò)模型

2.1 方案介紹

Kad 網(wǎng)絡(luò)是基于二叉樹結(jié)構(gòu)的P2P 網(wǎng)絡(luò)，其中每個節(jié)點被映射為二叉樹的葉子節(jié)點.這些節(jié)點維護(hù)一組被稱為K 桶的信息存儲結(jié)構(gòu)，K 桶數(shù)量等于節(jié)點ID 的位數(shù).每個K 桶存儲的節(jié)點信息與節(jié)點間的邏輯距離相對應(yīng)，此處的邏輯距離指2 個節(jié)點ID 的異或值.每個節(jié)點都可以計算自身與目的節(jié)點的邏輯距離，通過不斷地迭代查詢，獲取目的節(jié)點的地址信息.通常情況下，每個K 桶中能存儲的節(jié)點數(shù)量不超過k個.當(dāng)Kad 網(wǎng)絡(luò)的節(jié)點ID 是3 bits 時，設(shè)k=1，整個網(wǎng)絡(luò)空間的結(jié)構(gòu)如圖1 所示.

圖1 8 節(jié)點二叉前綴樹Fig.1 Binary prefix tree with 8 nodes

在該網(wǎng)絡(luò)中，假設(shè)每個K 桶都存儲與本節(jié)點邏輯距離最近的k個節(jié)點.以節(jié)點000 作為廣播消息的起點，節(jié)點000 的K 桶1、2、3 分別存儲節(jié)點001、節(jié)點010、節(jié)點100.這3 個節(jié)點連接的節(jié)點依次是（節(jié)點000、節(jié)點011、節(jié)點101）、（節(jié)點011、節(jié)點000、節(jié)點110）、（節(jié)點101、節(jié)點110、節(jié)點000）.當(dāng)該網(wǎng)絡(luò)經(jīng)歷2 個傳輸層級即傳播兩跳時（將同一層級內(nèi)多次消息傳輸只看作一跳），全網(wǎng)仍有節(jié)點111 未收到消息.這是因為存在冗余，如節(jié)點001 和節(jié)點100 都保存了節(jié)點101 的地址信息.冗余保證了網(wǎng)絡(luò)的連通性，也增強(qiáng)了網(wǎng)絡(luò)的健壯性和安全性.在區(qū)塊鏈網(wǎng)絡(luò)中，適量的冗余是必需的.

在保證網(wǎng)絡(luò)存在冗余的前提下，為了減少網(wǎng)絡(luò)傳輸?shù)膶蛹墸梢宰尮?jié)點000 額外存儲節(jié)點111 的信息.此時消息只要傳播兩跳就可以發(fā)送到全網(wǎng).一個節(jié)點的地址信息包含節(jié)點ID、IP 地址、端口號等內(nèi)容，大小只有幾十字節(jié).擴(kuò)容一個節(jié)點需要花費的代價很小，但是網(wǎng)絡(luò)性能提升很多.該方法的效果良好，主要是因為擴(kuò)容了適當(dāng)?shù)墓?jié)點.考慮到實際網(wǎng)絡(luò)結(jié)構(gòu)的復(fù)雜性，需要探索準(zhǔn)確且便捷的節(jié)點選擇方式，因此在Kad 網(wǎng)絡(luò)中引入小世界理論.

本文的主要思想源于Kleignberg 建立的K 模型.該模型的實現(xiàn)方式是使所有節(jié)點以D-m的概率緩存節(jié)點信息，D為該節(jié)點與其他節(jié)點的距離，m為正整數(shù)，被稱作維度.基于該理論，提出置換擴(kuò)容節(jié)點的概率公式：

式中：a、b、c為網(wǎng)絡(luò)中的任意3 個節(jié)點，|a-b| 和|a-c|分別為節(jié)點a和節(jié)點b、c的距離.假如節(jié)點a只額外保存了節(jié)點b的地址信息，在節(jié)點a接收到節(jié)點c的消息后，它將根據(jù)計算出的概率決定是否將存儲空間的節(jié)點b替換為節(jié)點c.概率越大，節(jié)點a進(jìn)行置換的可能性越大；反之，概率越小，置換的可能性越小.通過引入隨機(jī)數(shù)，可以實現(xiàn)概率對結(jié)果的影響.基于小世界理論的區(qū)塊鏈Kad 網(wǎng)絡(luò)改進(jìn)方法可以被簡稱為小世界Kad，工作流程如圖2 所示.

圖2 小世界Kad 的工作流程圖Fig.2 Work flow chart of small world Kad

首先將區(qū)塊鏈Kad 網(wǎng)絡(luò)初始化，并為每個節(jié)點擴(kuò)容，使它們額外存儲相同數(shù)量的節(jié)點信息.之后訓(xùn)練網(wǎng)絡(luò).具體來說，讓全網(wǎng)每個節(jié)點都能廣泛地通信，便于它們收集到其他節(jié)點的地址信息，按照概率公式進(jìn)行計算，通過計算結(jié)果判斷是否置換擴(kuò)容節(jié)點，每一次改變都會影響網(wǎng)絡(luò)性能，這個過程會反復(fù)進(jìn)行多輪.在網(wǎng)絡(luò)狀態(tài)穩(wěn)定后停止訓(xùn)練，從而構(gòu)建出小世界網(wǎng)絡(luò).

由于網(wǎng)絡(luò)中節(jié)點數(shù)量的動態(tài)變化，網(wǎng)絡(luò)性能可能會受到影響.當(dāng)網(wǎng)絡(luò)性能下降到一定程度時，必須重新訓(xùn)練網(wǎng)絡(luò)，以使性能恢復(fù)到最佳狀態(tài).為了確定重新訓(xùn)練的時機(jī)，可以在最后一次訓(xùn)練結(jié)束后測量并記錄網(wǎng)絡(luò)的平均廣播跳數(shù)，將其設(shè)定為閾值.在網(wǎng)絡(luò)正常運行期間，需要定期測量網(wǎng)絡(luò)的平均廣播跳數(shù).若一天內(nèi)多次測量值均超過閾值的10%，則判斷網(wǎng)絡(luò)性能嚴(yán)重下降，需要重新訓(xùn)練.選擇10% 作為閾值的原因如下：相比于普通Kad 網(wǎng)絡(luò)，該模型的性能提升最多只有30%.若平均廣播跳數(shù)下降超過10%，意味著算法的改進(jìn)效果十分有限，需要重新投入訓(xùn)練.時間窗口設(shè)定為1 天，以確保性能下降不是由短期的網(wǎng)絡(luò)波動所引起的.在重新訓(xùn)練時，可以選擇網(wǎng)絡(luò)交易數(shù)量較少的時刻，例如全網(wǎng)負(fù)荷不到50%時，這樣可以減少對網(wǎng)絡(luò)正常操作的干擾.小世界Kad 方法的一大優(yōu)勢是無論網(wǎng)絡(luò)的初始狀態(tài)如何，利用該模型均能改善網(wǎng)絡(luò)的通信性能.在重新訓(xùn)練后，網(wǎng)絡(luò)性能必然得到提升.通過以上方法，該模型能夠及時識別網(wǎng)絡(luò)性能下降的情況并采取相應(yīng)的措施，以保持網(wǎng)絡(luò)的高性能狀態(tài).

本方案的核心理念是讓網(wǎng)絡(luò)中大部分節(jié)點與距離自身較近的節(jié)點保持連接，只有少數(shù)節(jié)點與遠(yuǎn)距離節(jié)點建立連接.這種方式使得整個網(wǎng)絡(luò)空間呈現(xiàn)出短鏈多、長鏈少的特點，符合K 模型的核心特征.

2.2 推導(dǎo)證明

假設(shè)Kad 網(wǎng)絡(luò)中存在N個節(jié)點，若所有節(jié)點按照概率公式置換擴(kuò)容節(jié)點，則這個過程的狀態(tài)轉(zhuǎn)移僅依賴于當(dāng)前狀態(tài)，是馬爾科夫過程.因為它的時間和狀態(tài)都離散，可以被視為馬爾科夫鏈.為了便于理解和研究，將任意2 個節(jié)點間的距離視作一種狀態(tài)，因而節(jié)點a的狀態(tài)空間可以被表示成（其中da,k表示節(jié)點a與任意節(jié)點如節(jié)點k之間的距離）.當(dāng)節(jié)點a連接節(jié)點b時，它們之間的距離是s=|a-b|，此時這條馬爾科夫鏈處于狀態(tài)s.當(dāng)節(jié)點a接收到其他節(jié)點比如節(jié)點c的消息時，它會根據(jù)概率公式置換節(jié)點.設(shè)t=|a-c| 表示節(jié)點a、c之間的距離，若置換成功，則鏈的狀態(tài)從s轉(zhuǎn)移到t.若置換失敗，則鏈的狀態(tài)保持不變.該過程是馬爾科夫鏈中的一步狀態(tài)轉(zhuǎn)移.

為了簡潔地說明情況，如圖3 所示，展現(xiàn)了節(jié)點a僅有4 個狀態(tài)時的狀態(tài)轉(zhuǎn)換示例.

圖3 節(jié)點a 的四狀態(tài)轉(zhuǎn)換圖Fig.3 Four state transition diagrams for node a

根據(jù)馬爾科夫定理可知，若馬爾科夫鏈的狀態(tài)數(shù)量有限，狀態(tài)轉(zhuǎn)移過程不存在周期且轉(zhuǎn)移矩陣元素全部為正數(shù)，則該鏈具有遍歷性和不可約性，它的平穩(wěn)分布存在且唯一，等于它的極限分布.假設(shè)這條馬爾科夫鏈的平穩(wěn)分布是 πj，有以下公式.

式中：πi為馬爾科夫鏈的初始概率分布，Pij為馬爾科夫鏈的轉(zhuǎn)移概率.

網(wǎng)絡(luò)中任意一節(jié)點經(jīng)過有限步數(shù)的節(jié)點置換，會趨于穩(wěn)定的狀態(tài)，這與節(jié)點的起始狀態(tài)無關(guān)，所以網(wǎng)絡(luò)初始化階段可以隨機(jī)分配存儲節(jié)點.在馬爾科夫鏈達(dá)到穩(wěn)態(tài)后，狀態(tài)的轉(zhuǎn)出和轉(zhuǎn)入會達(dá)到平衡，此時從穩(wěn)定狀態(tài)j到狀態(tài)s的轉(zhuǎn)出概率等于從狀態(tài)s到狀態(tài)j的轉(zhuǎn)入概率（s∈A,s≠j）.可得如下方程：

從式（2）可知，平穩(wěn)分布 πj的和為1，且狀態(tài)轉(zhuǎn)移過程離散，因此對于狀態(tài)s，有

C為任意大于0 的常數(shù)，方程的一個解為

節(jié)點狀態(tài)表示節(jié)點之間的距離，任意2 個狀態(tài)的運算結(jié)果必為一確定常數(shù)，所以式（4）是常系數(shù)方程.設(shè)狀態(tài)空間A中存在n個狀態(tài)，可將這些狀態(tài)依次代入式（4），得到n元方程組.該方程組只存在一個解，即式（6）.這個結(jié)果與該馬爾科夫鏈中平穩(wěn)分布等于極限分布相符.式（6）說明網(wǎng)絡(luò)中每個節(jié)點連接其他節(jié)點的概率分布與它們之間的距離呈反比，與本方案的思想一致.

在普通的Kad 網(wǎng)絡(luò)中，節(jié)點間的距離一般指2 個節(jié)點ID 的異或值即邏輯距離，但是這種距離沒有考慮路由跳數(shù)的影響.路由跳數(shù)反映了節(jié)點傳輸信息需要經(jīng)過的中間節(jié)點數(shù)量.在小世界網(wǎng)絡(luò)的相關(guān)研究中，通常將路由跳數(shù)認(rèn)定為節(jié)點間的距離[15].為了平衡邏輯距離和路由跳數(shù)的影響，增強(qiáng)算法的優(yōu)化效果，提出實際距離rd，將其應(yīng)用于式（1）.rd的計算方法如下所示：

式中：ld和hd分別為邏輯距離和路由跳數(shù)；x、y均為自然數(shù)，分別是邏輯距離和路由跳數(shù)的系數(shù).邏輯距離和路由跳數(shù)的系數(shù)比例表明了它們在網(wǎng)絡(luò)中的權(quán)重差距，系數(shù)占比高的因素在算法中的作用更突出.邏輯距離僅由節(jié)點ID 決定，不受方向的影響，而路由跳數(shù)會隨著節(jié)點之間的路由方向改變而變化.

當(dāng)計算置換概率時，節(jié)點間的邏輯距離可以通過對節(jié)點ID 進(jìn)行異或運算取得，路由跳數(shù)通過發(fā)送消息測量.為了獲取準(zhǔn)確的跳數(shù)，減少重復(fù)傳輸，可以在每條消息中增加傳輸路徑信息.該信息包含發(fā)送節(jié)點的節(jié)點ID、地址信息以及中間節(jié)點和目的節(jié)點與發(fā)送節(jié)點的邏輯距離集合.存儲邏輯距離是因為在大多數(shù)區(qū)塊鏈網(wǎng)絡(luò)中節(jié)點ID 長度遠(yuǎn)大于邏輯距離，例如在以太坊中邏輯距離的字節(jié)大小是4，節(jié)點ID 的字節(jié)大小是32.在目的節(jié)點收到消息后，可以將傳輸路徑中中間節(jié)點數(shù)量最少的消息轉(zhuǎn)發(fā)回發(fā)送節(jié)點，以便發(fā)送節(jié)點獲取自身與目的節(jié)點之間的廣播路由跳數(shù).

2.3 時間分析

雖然在經(jīng)過一定輪數(shù)的訓(xùn)練后，小世界Kad網(wǎng)絡(luò)能夠趨于穩(wěn)定狀態(tài)，但是本模型要求所有節(jié)點在每一輪訓(xùn)練過程中廣播自身的地址信息，以便其他節(jié)點能夠計算概率并進(jìn)行置換.這導(dǎo)致狀態(tài)變化過程非常復(fù)雜，無法使用馬爾科夫鏈的相關(guān)理論推導(dǎo)得到本文算法準(zhǔn)確的時間復(fù)雜度.目前，Wright[16]證明了大小為n的馬爾科夫鏈最多需要O（n2）步就可以達(dá)到平衡.Peter 等[17]通過實驗發(fā)現(xiàn)，在Chord 網(wǎng)絡(luò)上構(gòu)建小世界網(wǎng)絡(luò)的算法運行時間是O（n2）.參照該思路開展一系列實驗，擬合實驗數(shù)據(jù)，得到算法的時間復(fù)雜度為O（n2+m2+y/x）（x，y≠0），其中邏輯距離和路由跳數(shù)的系數(shù)比例對算法運行時間的影響較小，因此時間復(fù)雜度可以近似為O（n2+m2）.

根據(jù)時間復(fù)雜度的分析可知，隨著節(jié)點數(shù)量和維度的增長，算法達(dá)到穩(wěn)定狀態(tài)需要的時間會顯著增加.節(jié)點數(shù)量無法改變，而維度可以調(diào)整，然而維度改變會影響網(wǎng)絡(luò)性能，本研究最主要的目的是提升Kad 網(wǎng)絡(luò)的傳輸性能，而不是使模型達(dá)到完全穩(wěn)定的狀態(tài).由后續(xù)實驗可知，當(dāng)其他條件相同時，增加維度能夠一定程度上改善算法的優(yōu)化效果.通過實驗發(fā)現(xiàn)，該模型在訓(xùn)練前期性能提升很快，但是十幾輪后性能改變幅度很小，因此可以在每一輪訓(xùn)練后測量網(wǎng)絡(luò)的平均廣播跳數(shù).若連續(xù)3 輪跳數(shù)的下降比例不到1%，則判定該模型訓(xùn)練成功.利用該策略，可以在合理的時間內(nèi)獲得性能相對良好的模型，減少模型的訓(xùn)練成本.

該模型的訓(xùn)練時間為

式中：N為節(jié)點總數(shù)，Li為節(jié)點i每次發(fā)送消息的數(shù)據(jù)量，hdi為節(jié)點i將消息廣播至全網(wǎng)的路由跳數(shù)，V為網(wǎng)絡(luò)的傳輸速率，W為訓(xùn)練輪數(shù).

區(qū)塊鏈作為動態(tài)的開放環(huán)境，式（8）的各項參數(shù)均會動態(tài)變化.以以太坊作為示例，提供所有參數(shù)的估計值，評估該方案的時間效率.以太坊的數(shù)據(jù)傳輸速率為20 Mb/s，節(jié)點數(shù)量約為104，大多數(shù)節(jié)點能夠在6 跳內(nèi)將消息廣播至全網(wǎng).在訓(xùn)練過程中，每次傳輸消息的數(shù)據(jù)量不到100 字節(jié)，其中發(fā)送節(jié)點ID、IP 地址和端口號等信息大小約為54 字節(jié)，發(fā)送節(jié)點與其他節(jié)點的邏輯距離集合大小約為24 字節(jié).考慮到性能提升幅度在訓(xùn)練十幾輪后變得較小，可以將訓(xùn)練輪數(shù)設(shè)定為30.根據(jù)所設(shè)定的參數(shù)，預(yù)計在以太坊上，該模型的理論訓(xùn)練時間約為9 s，耗時很少.該模型具有極高的時間效率.對于其他應(yīng)用Kad 網(wǎng)絡(luò)的區(qū)塊鏈項目，它們的訓(xùn)練時間與以太坊接近.

2.4 算法描述

該算法的具體步驟如算法1 所示.

3 性能分析

3.1 實驗環(huán)境

該方法的實驗環(huán)境如下：操作系統(tǒng)為Windows 11 教育版64 位，CPU 為13th Gen Intel(R)Core(TM) i5-13600K 3.50 GHz，內(nèi)存大小為64 GB，利用Java 語言來編寫代碼，開發(fā)工具是VScode.

在實驗過程中，對模型的效果進(jìn)行初步驗證，通過對照實驗確定主要的參數(shù)值.將該方案的優(yōu)化算法與其他算法進(jìn)行比較，綜合評估該模型在消息廣播、節(jié)點定位和網(wǎng)絡(luò)安全性方面的表現(xiàn).

3.2 方法驗證

創(chuàng)建包含128 個虛擬節(jié)點的Kad 網(wǎng)絡(luò)，其中節(jié)點的ID 使用7 位二進(jìn)制數(shù)表示，因此K 桶數(shù)為7，k設(shè)置為4，每個節(jié)點保存了23 個節(jié)點的地址信息.對每個節(jié)點擴(kuò)容，使它們額外存儲4 個節(jié)點的信息.根據(jù)概率公式訓(xùn)練網(wǎng)絡(luò)，記錄實驗結(jié)果.共進(jìn)行10 組實驗，分別以0～9 設(shè)置Java 隨機(jī)數(shù)生成器的初始值，即通過不同的隨機(jī)數(shù)種子Aseed對網(wǎng)絡(luò)進(jìn)行初始化，以確保網(wǎng)絡(luò)的初始狀態(tài)不同.通過這些操作，展現(xiàn)了該算法在不同初始狀態(tài)的網(wǎng)絡(luò)下的應(yīng)用效果，實驗結(jié)果如圖4 所示.

圖4 不同初始狀態(tài)時算法的平均廣播跳數(shù)Fig.4 Average broadcast hop count of algorithm in different initial states

圖4 中，E為訓(xùn)練輪數(shù)；Bhop為平均廣播跳數(shù)，即所有節(jié)點進(jìn)行全網(wǎng)廣播時需要經(jīng)歷的平均傳輸層級.平均廣播跳數(shù)越小，表示網(wǎng)絡(luò)的通信速率越快，網(wǎng)絡(luò)性能越好，這意味著區(qū)塊鏈上處理交易的速度會更快.由于各節(jié)點全網(wǎng)廣播所經(jīng)歷的傳輸層級不完全相同，平均廣播跳數(shù)可能為小數(shù).實驗結(jié)果顯示，改造后的網(wǎng)絡(luò)在經(jīng)過一定輪數(shù)的訓(xùn)練后，性能得到提升并且狀態(tài)逐漸趨于穩(wěn)定.無論網(wǎng)絡(luò)的初始情況如何，該方案均能夠?qū)W(wǎng)絡(luò)進(jìn)行有效的優(yōu)化，證明該算法具有收斂性和魯棒性.

3.3 參數(shù)確定

該算法需要確定的2 個重要參數(shù)分別是維度以及邏輯距離與路由跳數(shù)的比例，它們會影響算法的優(yōu)化效果.實驗采用之前創(chuàng)建的網(wǎng)絡(luò)，Aseed設(shè)為0.維度對算法性能的影響如圖5 所示.

圖5 不同維度時算法的平均廣播跳數(shù)Fig.5 Average broadcast hop count of algorithm in differen dimensions

從圖5 可以看出，當(dāng)維度增加時，節(jié)點向全網(wǎng)廣播消息所需的平均跳數(shù)有所減少，網(wǎng)絡(luò)性能得到提升.相較于維度從1 變?yōu)? 時顯著的性能差異，當(dāng)維度從2 增加到3 時，網(wǎng)絡(luò)性能只有微小的改變.當(dāng)維度為1 時，算法只須訓(xùn)練10 輪左右就能達(dá)到穩(wěn)定狀態(tài)，比其他維度快很多，但是訓(xùn)練速度快的代價是網(wǎng)絡(luò)性能較差.即使在所有維度的訓(xùn)練輪數(shù)均設(shè)定為10 的情況下，維度為2 和3 時的性能也優(yōu)于維度為1 時的性能.

如圖6 所示為邏輯距離與路由跳數(shù)比例的變化對算法性能的影響.

圖6 不同比例時算法的平均廣播跳數(shù)Fig.6 Average broadcast hop count of algorithm in differen proportions

實驗結(jié)果表明，當(dāng)邏輯距離與路由跳數(shù)任意一個系數(shù)比例為0 時，平均廣播跳數(shù)較多，優(yōu)化效果較差.這說明邏輯距離與路由跳數(shù)都在算法中發(fā)揮著重要作用，不能忽視其中任何一個.隨著路由跳數(shù)占比的增加，算法性能略有提升，當(dāng)比例為1∶3 時，性能相對最佳.

3.4 方案對比

將該模型與普通的原始Kad 網(wǎng)絡(luò)、分區(qū)Kad網(wǎng)絡(luò)[3]、擴(kuò)容Kad 網(wǎng)絡(luò)[4]進(jìn)行對比，評估本方案的優(yōu)缺點.為了獲得最佳效果，圖7 展示了本模型在不同維度和比例組合下的平均廣播跳數(shù).此處排除了一些在圖6 中表現(xiàn)不佳的參數(shù)設(shè)置，例如維度為1、比例中存在0、邏輯距離系數(shù)比例大于路由跳數(shù)系數(shù)比例的情況.

如圖7 所示，經(jīng)過訓(xùn)練后，該模型在不同維度和比例組合下均取得顯著的性能提升，優(yōu)于其他模型.當(dāng)維度為3，比例為1∶3 時，模型性能達(dá)到最佳水平，因此在后續(xù)實驗中采用該參數(shù)組合.

之前實驗中的節(jié)點總數(shù)都是128，后續(xù)實驗將網(wǎng)絡(luò)的節(jié)點數(shù)量細(xì)分為5 部分，分別為128、256、512、1 024、2 048.魏戰(zhàn)爭等[18]通常認(rèn)為0～200 個節(jié)點的網(wǎng)絡(luò)是小型網(wǎng)絡(luò)，200～1 000 個節(jié)點的網(wǎng)絡(luò)是中型網(wǎng)絡(luò)，1 000 個節(jié)點以上的網(wǎng)絡(luò)是大型網(wǎng)絡(luò).后續(xù)實驗涵蓋了小、中、大3 種類型的網(wǎng)絡(luò)，以全方位地探究小世界Kad 網(wǎng)絡(luò)的性能表現(xiàn).

在Kad 協(xié)議中，k的選取需要考慮系統(tǒng)性能和網(wǎng)絡(luò)負(fù)載的平衡.例如BitTorrent 中k被設(shè)定為8，以太坊的k為16.為了更好地呈現(xiàn)實驗結(jié)果，針對小型、中型和大型3 種規(guī)模的網(wǎng)絡(luò)設(shè)置不同的k，分別是4、8 和16.當(dāng)進(jìn)行4 類Kad 協(xié)議的對比實驗時，原始Kad 和分區(qū)Kad 中每個節(jié)點保存相同數(shù)量的節(jié)點信息，擴(kuò)容Kad 和小世界Kad 中的節(jié)點需要額外存儲k個節(jié)點.在不同節(jié)點總數(shù)的網(wǎng)絡(luò)中，原始Kad 和分區(qū)Kad 中每個節(jié)點存儲的節(jié)點數(shù)量分別為23、47、55、111 和127.擴(kuò)容Kad和小世界Kad 將其分別擴(kuò)大到27、55、63、127 和143.雖然小世界Kad 的存儲成本增加了12.6%～17.4%，但是額外消耗的存儲空間不到1 kB，對比實驗的結(jié)果如圖8 所示.

圖8 中，N為節(jié)點總數(shù)；Bratio為各優(yōu)化模型與原始Kad 的平均廣播跳數(shù)的比值，即廣播跳數(shù)優(yōu)化比例.Bratio越小，表示網(wǎng)絡(luò)廣播速率越快，因此原始Kad 的優(yōu)化比例保持不變，全部是100%.這能直觀地展示各方案的優(yōu)化效果.與原始Kad 相比，本模型的平均廣播跳數(shù)減少了15.7%～30.8%，均高于它增加的存儲消耗.小世界Kad 的性能提升水平在節(jié)點總數(shù)為128、512、2 048 時明顯優(yōu)于其他方案，在另外2 種情況下與其他優(yōu)化方案相同.

當(dāng)網(wǎng)絡(luò)節(jié)點總數(shù)為256 和1 024 時，擴(kuò)容Kad和小世界Kad 實現(xiàn)了相同的優(yōu)化效果.在增加了k個節(jié)點的存儲容量后，這2 種網(wǎng)絡(luò)的性能均達(dá)到最佳狀態(tài)；因此，可以適當(dāng)減少額外補充的節(jié)點數(shù)量以降低存儲開銷，且盡可能保證優(yōu)化效果不受影響.經(jīng)過多次測試發(fā)現(xiàn)，在256 和1 024 個節(jié)點的小世界Kad 網(wǎng)絡(luò)中，只需要每個節(jié)點額外多連接k/4 個節(jié)點，即分別多存儲2 個和4 個節(jié)點的地址信息，就能夠?qū)⑷W(wǎng)廣播的平均跳數(shù)降低到接近最佳值，如圖9 所示.

圖9 調(diào)整后的平均廣播跳數(shù)優(yōu)化比例Fig.9 Optimization ratio of average broadcast hop count after adjusting

圖9 中，網(wǎng)絡(luò)節(jié)點總數(shù)為128、512、2 048 時的存儲成本與性能提升水平均與圖8 相同.當(dāng)節(jié)點總數(shù)為256 和1 024 時，小世界Kad 較原始Kad 額外花費的存儲代價僅為4%左右，平均廣播跳數(shù)分別下降了15.0%和21.8%.小世界Kad 的優(yōu)化作用強(qiáng)于擴(kuò)容Kad，與分區(qū)Kad 幾乎等同.這表明小世界Kad 具有很好的靈活性，可以根據(jù)需要調(diào)整網(wǎng)絡(luò)中額外存儲的節(jié)點數(shù)量，從而以更小的存儲開銷換取較多的性能提升.分區(qū)Kad 的優(yōu)化效果會受到節(jié)點總數(shù)與k的影響，當(dāng)節(jié)點總數(shù)為128、512、2 048 時沒有發(fā)揮作用，性能甚至比原始Kad 更差.相比之下，采用小世界Kad 的所有網(wǎng)絡(luò)都實現(xiàn)了性能優(yōu)化，這說明小世界Kad 具備更加廣泛的適用性，能夠應(yīng)對不同場景下的網(wǎng)絡(luò)優(yōu)化需求.由于調(diào)整效果良好，在后續(xù)的實驗中，本方案將保持這個配置，即在節(jié)點總數(shù)為256 和1 024時，每個節(jié)點只額外存儲k/4 個節(jié)點的地址信息，其余情況下存儲k個.

圖10 中，F(xiàn)ratio為各模型相對于原始Kad 的平均查找跳數(shù)優(yōu)化比例.小世界Kad 的查找跳數(shù)較原始Kad 下降了1.4%～6.6%.優(yōu)化效果只在節(jié)點總數(shù)為256 和 1 024 時差于分區(qū)Kad，在其他情況下，都是表現(xiàn)最好的.

圖10 平均查找跳數(shù)的優(yōu)化比例Fig.10 Optimization ratio of average find hop count

3.5 安全性評估

常見的區(qū)塊鏈網(wǎng)絡(luò)攻擊方式有雙花攻擊[19]、DDoS 攻擊[20]、Sybil 攻擊[21]、日蝕攻擊[22]等，小世界Kad 能夠增強(qiáng)網(wǎng)絡(luò)的安全性，提高抵御這些攻擊的能力.

雙花攻擊是指用戶惡意利用區(qū)塊鏈的交易確認(rèn)機(jī)制，通過在網(wǎng)絡(luò)中重復(fù)花費同一筆資產(chǎn)來獲得不當(dāng)利益的攻擊行為.雙花攻擊的本質(zhì)是利用交易未被確認(rèn)的時間窗口進(jìn)行多次消費，而小世界Kad 可以提升全網(wǎng)廣播交易消息的速度，從而縮短時間窗口，降低發(fā)生雙花攻擊的風(fēng)險.

DDoS 攻擊通過控制大量傀儡機(jī)，對一個或多個目標(biāo)節(jié)點發(fā)送大量請求，使目標(biāo)節(jié)點無法正常工作.在小世界Kad 網(wǎng)絡(luò)中，向目標(biāo)節(jié)點發(fā)送消息，需要事先保存該節(jié)點的地址信息，然而這些信息如果被存儲在小世界桶（按照概率公式存儲節(jié)點地址信息的空間結(jié)構(gòu)）中，那么有可能會被置換，導(dǎo)致攻擊不能順利實施.

Sybil 攻擊是指攻擊者通過將單個節(jié)點偽造成多個虛假節(jié)點以操縱網(wǎng)絡(luò)的攻擊方式.為了實現(xiàn)這種攻擊，虛假節(jié)點的地址信息必須被網(wǎng)絡(luò)中的其他節(jié)點所保存，而在小世界Kad 網(wǎng)絡(luò)中，每個節(jié)點會定期更換擴(kuò)容的節(jié)點信息，這增大了發(fā)動Sybil 攻擊的難度.

日蝕攻擊的基本原理類似于Sybil 攻擊，但是前者更加著重于攻擊單個節(jié)點.日蝕攻擊的主要目的是覆蓋目標(biāo)節(jié)點與網(wǎng)絡(luò)的全部連接，使目標(biāo)節(jié)點被隔離在網(wǎng)絡(luò)之外.以太坊曾經(jīng)飽受日蝕攻擊的困擾.為了抵御日蝕攻擊，以太坊在Geth v1.8.1 版本上作了改進(jìn)，將網(wǎng)絡(luò)中每個節(jié)點存儲的K 桶數(shù)從256 削減為17，只保留距離最遠(yuǎn)的17 個K 桶[23].這雖然增強(qiáng)了網(wǎng)絡(luò)的安全性，但是導(dǎo)致了傳輸性能的下降.

舊版本的以太坊難以抵御日蝕攻擊，是因為網(wǎng)絡(luò)中的節(jié)點ID 由公鑰生成，不受IP 限制，用戶可以通過密鑰生成算法大量制造.Kad 網(wǎng)絡(luò)的高度結(jié)構(gòu)化導(dǎo)致其缺乏彈性，每個節(jié)點的i號K桶都只存儲與自身邏輯距離為的節(jié)點信息.只要攻擊者知道目標(biāo)節(jié)點的節(jié)點ID，就可以生成許多容易被目標(biāo)節(jié)點連接的虛假節(jié)點.當(dāng)虛假節(jié)點占據(jù)了目標(biāo)節(jié)點的大部分K 桶時，該節(jié)點的通信能力會被嚴(yán)重削弱.結(jié)構(gòu)化程度更高的分區(qū)Kad 更易受到日蝕攻擊的威脅，安全性更弱.擴(kuò)容Kad 中，每個節(jié)點都存儲了更多的節(jié)點信息，攻擊者為了封鎖目標(biāo)節(jié)點的對外通信，就必須生成更多的虛假節(jié)點，增加了攻擊者的成本，間接提高了網(wǎng)絡(luò)的安全性，但是提升幅度較小.

與這2 個方案相比，小世界Kad 按照概率存儲擴(kuò)容節(jié)點，引入了一定的隨機(jī)性，安全性更強(qiáng).概率置換公式中的實際距離由邏輯距離和路由跳數(shù)共同決定，而虛假節(jié)點無法改變自身與目標(biāo)節(jié)點的路由跳數(shù)，這由網(wǎng)絡(luò)的整體情況決定，因此小世界桶中的節(jié)點可信度很高.小世界桶中保存的節(jié)點信息會根據(jù)概率公式被多次置換，即使在某一時刻小世界桶中存儲了虛假節(jié)點，它們也很可能會在下一時刻被換掉，不會長期存在.攻擊者幾乎不可能使虛假節(jié)點完全占據(jù)小世界桶，導(dǎo)致目標(biāo)節(jié)點被網(wǎng)絡(luò)隔離.當(dāng)攻擊者發(fā)動50%的日蝕攻擊，即覆蓋目標(biāo)節(jié)點50%的對外連接時，需要花費的成本即創(chuàng)造的虛假節(jié)點數(shù)量如圖11 所示.

圖11 發(fā)動50%的日蝕攻擊的虛假節(jié)點數(shù)量優(yōu)化比例Fig.11 Optimization ratio of number of false nodes of launching 50% eclipse attack

圖11 中，Aratio為各模型與原始Kad 中虛假節(jié)點數(shù)量的比例，比例越大表明該模型抵御日蝕攻擊的能力越強(qiáng)，比例越小表明該模型越容易受到日蝕攻擊的侵害.當(dāng)攻擊者對小世界Kad 發(fā)動50%的日蝕攻擊時，承擔(dān)的成本最大，相較于原始Kad 增加了1.7%～7.1%.對于分區(qū)Kad，攻擊者花費的代價最小，需要生成的節(jié)點數(shù)僅為原始Kad的26.7%～46.7%.

4 結(jié)語

為了提升區(qū)塊鏈網(wǎng)絡(luò)的可擴(kuò)展性和安全性，本文提出在區(qū)塊鏈Kademlia 網(wǎng)絡(luò)上構(gòu)建小世界網(wǎng)絡(luò)的方法.該方法以節(jié)點間距離與連接概率成反比的方式置換擴(kuò)容節(jié)點，提高了網(wǎng)絡(luò)的傳輸性能.具體而言，平均廣播跳數(shù)減少了15.0%～30.8%，平均查找跳數(shù)減少了1.4%～6.6%.該方法引入一定的隨機(jī)性，增強(qiáng)了網(wǎng)絡(luò)抵御各種攻擊的能力，如攻擊者發(fā)動 50% 的日蝕攻擊的成本增加了1.7%～7.1%，幾乎不可能實現(xiàn)100%的日蝕攻擊.盡管該方法增加了3.6%～17.4%的存儲成本，但是額外消耗的空間不到1 kB，代價很小.在后續(xù)的研究中，會考慮現(xiàn)實環(huán)境對網(wǎng)絡(luò)的影響，將物理層面上節(jié)點的距離、網(wǎng)絡(luò)帶寬和CPU 運行速度等因素納入概率公式，使得該方法能夠更好地應(yīng)用于實際的網(wǎng)絡(luò)拓?fù)?