物聯(lián)網(wǎng)區(qū)塊鏈中基于演化博弈的分片算法

徐小瓊，孫 罡，羅 龍

(電子科技大學光纖傳感與通信教育部重點實驗室 成都 611731)

物聯(lián)網(wǎng)在傳統(tǒng)互聯(lián)網(wǎng)的基礎上，通過傳感器網(wǎng)絡賦予物體互聯(lián)互通的能力，因此極大程度地降低了日常生產(chǎn)和運營的成本[1]。但隨著物聯(lián)網(wǎng)設備的急劇增長和服務的廣泛部署，其網(wǎng)絡性能受到邊緣終端設備以及云服務器傳輸寬帶的制約，使得物聯(lián)網(wǎng)傳輸速率劣化，帶來了一定的安全隱患[2]。同時，對數(shù)據(jù)進行中心化管理使得物聯(lián)網(wǎng)設備隱私安全性得不到保障。因此，物聯(lián)網(wǎng)系統(tǒng)不可避免地存在諸如用戶隱私泄露、DDoS 攻擊等安全性的問題[3]。

區(qū)塊鏈的出現(xiàn)為物聯(lián)網(wǎng)下實現(xiàn)安全、高效的數(shù)據(jù)交互和隱私保護提供了新的解決方案[4]。區(qū)塊鏈是一個新型的分布式數(shù)據(jù)賬本，其可以對不斷增長的物聯(lián)網(wǎng)數(shù)據(jù)進行記錄和維護以防止偽造和非法篡改。區(qū)塊鏈通過密碼學技術(shù)對數(shù)據(jù)進行加密，并將數(shù)據(jù)以區(qū)塊的形式進行存儲且將相關(guān)聯(lián)的數(shù)據(jù)區(qū)塊進行鏈狀串聯(lián)。這種鏈狀的結(jié)構(gòu)能利用Merkle Tree 對數(shù)據(jù)進行校驗，從而判斷區(qū)塊內(nèi)的數(shù)據(jù)是否被篡改[5]。但由于現(xiàn)有的區(qū)塊鏈架構(gòu)存在可擴展性低、交易時延高的性能缺陷，仍不能很好地支撐物聯(lián)網(wǎng)業(yè)務[6]。

為了滿足區(qū)塊鏈在物聯(lián)網(wǎng)場景下的應用需求，近年來，已有一系列的區(qū)塊鏈性能優(yōu)化方案被提出。其中，網(wǎng)絡分片被認為是解決區(qū)塊鏈可擴展性問題及提升區(qū)塊鏈性能最主要的技術(shù)之一[7-10]。分片通過將整個區(qū)塊鏈網(wǎng)絡拆分為多個子網(wǎng)絡，每個子網(wǎng)絡由一個不同的節(jié)點集合進行維護，交易在不同的子網(wǎng)絡內(nèi)并行處理。由于每個區(qū)塊鏈節(jié)點不必處理系統(tǒng)中所有的交易，因此極大地提升了網(wǎng)絡的交易處理性能。盡管如此，現(xiàn)有的區(qū)塊鏈分片算法仍存在一些挑戰(zhàn)[8]。首先，網(wǎng)絡分片大小是需要考慮的問題，當網(wǎng)絡分片數(shù)目較多，即每個分片內(nèi)節(jié)點較少時，會導致共識的安全性問題。相反，當網(wǎng)絡分片數(shù)目較少，則可并行的交易處理能力不夠，網(wǎng)絡性能無法滿足應用需求。因此，在實際應用中，如何選擇分片大小以平衡安全性和網(wǎng)絡性能需求是需要解決的問題。其次，在基于實際拜占庭 容 錯(practical byzantine fault tolerance, PBFT)共識算法的區(qū)塊鏈網(wǎng)絡中[11]，惡意節(jié)點的隨機分布會導致某個分片內(nèi)的惡意節(jié)點數(shù)目大于分片中所有節(jié)點的三分之一，這會出現(xiàn)個別分片無法對交易達成共識，進而產(chǎn)生分片失效的問題。因此，如何使惡意節(jié)點盡可能均勻地分布在不同的分片內(nèi)以滿足分片有效性是需要解決的又一問題。

針對這些問題，本文提出分片區(qū)塊鏈安全性和可擴展性的理論分析模型。其次，基于提出的分析模型建立優(yōu)化求解問題來解決可擴展性和安全性均衡問題。最后，基于演化博弈論得到較優(yōu)的區(qū)塊鏈分片算法使惡意節(jié)點盡可能地均勻分布于每個分片中。仿真結(jié)果表明，本文算法可以使不同類型節(jié)點的分布動態(tài)演化收斂到接近最優(yōu)的均衡點，達到節(jié)點均勻分布的目的，進而在支持物聯(lián)網(wǎng)應用的區(qū)塊鏈中獲得更好的性能。

1 相關(guān)工作

近年來，研究者們將分片技術(shù)應用到區(qū)塊鏈中，使其成為解決區(qū)塊鏈可擴展性問題的重要方案。區(qū)塊鏈網(wǎng)絡分片的關(guān)鍵思想是將網(wǎng)絡劃分成多個子集，稱為分片，每個分片包含一部分區(qū)塊鏈網(wǎng)絡節(jié)點。所有的分片并行處理網(wǎng)絡中不同的交易集，而不是整個網(wǎng)絡節(jié)點處理相同的交易。由于每個分片內(nèi)節(jié)點單獨進行交易共識，節(jié)點只需要和同分片內(nèi)的其他節(jié)點進行通信，因此大大降低了計算和通信的開銷。迄今為止，已有大量的區(qū)塊鏈分片協(xié)議被提出[12-15]。

文獻[12]提出了一種可用于公有區(qū)塊鏈的分布式分片算法Elastico，其使用工作量證明(power of work, PoW)將網(wǎng)絡礦工節(jié)點隨機分配到較小的分片中，每個分片處理一組不相交的交易。然后，分片內(nèi)部節(jié)點采用經(jīng)典的PBFT 共識算法并行處理交易。雖然Elastico 能實現(xiàn)在拜占庭環(huán)境下的高可擴展性，但Elastico 算法的分片選擇不具有很強的偏差抗性。文獻[13]在Elastico 算法的基礎上提出了一種新的分片算法OmniLedger，該算法利用抗偏置隨機協(xié)議RandHound 和可驗證隨機函數(shù)來自主執(zhí)行節(jié)點分片以確保分片的安全性。但在OmniLedger算法中，由于每個分片在進行幾輪共識后就會被拆散重構(gòu)，分片重構(gòu)太過頻繁帶來較高的分片切換時延。

文獻[14]采用可信執(zhí)行環(huán)境(trusted execution environment, TEE)設計了一個高效安全的分片生成協(xié)議，其在分布式設置中實現(xiàn)了一個可信的隨機信標來生成無偏隨機值，同時利用TEE 來增加拜占庭共識算法的容錯能力以減少分片大小。文獻[15]提出了公有區(qū)塊鏈的分片算法RapidChain，其可以使整個網(wǎng)絡容忍高達33%的惡意節(jié)點或故障節(jié)點，每個分片內(nèi)可以容忍近50%的惡意節(jié)點。同時，在沒有任何可信假設的情況下，RapidChain 算法能實現(xiàn)通信、計算和存儲的完全分片，具有更高的吞吐量。

盡管上述的分片算法在一定程度上實現(xiàn)了區(qū)塊鏈的高可擴展性，但隨著網(wǎng)絡惡意節(jié)點數(shù)量的增加，如何獲得一個較優(yōu)的分片算法，使得惡意節(jié)點均勻分布在每個分片以降低分片失效概率，是一個亟待解決的問題。

2 分片性能分析

本節(jié)首先對分片區(qū)塊鏈的安全性和可擴展性進行理論分析?；诜治瞿Ｐ?，本節(jié)建立分片優(yōu)化求解問題來實現(xiàn)分片區(qū)塊鏈安全性和可擴展性的均衡。

2.1 分析模型

在基于PBFT 共識算法的區(qū)塊鏈網(wǎng)絡中，安全性和可擴展性指標的相關(guān)定義為：

1)安全性：分片區(qū)塊鏈的安全性可以由分片內(nèi)交易失效概率來衡量，被定義為分片中惡意節(jié)點數(shù)目超過能容忍最大惡意節(jié)點的界限。分片交易的失效概率越低，則代表網(wǎng)絡安全性越高。

2) 可擴展性：分片區(qū)塊鏈的可擴展性一般由分片后交易吞吐量和交易平均時延來衡量。交易吞吐量被定義為網(wǎng)絡中平均每秒執(zhí)行的交易數(shù)目，交易平均時延被定義為交易從提交到上鏈整個過程花費的平均時間。交易吞吐量越高，交易平均時延越低，網(wǎng)絡可擴展性越高。本文僅考慮交易共識階段的可擴展性，即交易共識吞吐量和交易共識時延。

2.1.1 失效概率分析模型

在分片區(qū)塊鏈中，如果某個分片內(nèi)惡意節(jié)點數(shù)目過多，分片內(nèi)節(jié)點無法對交易達成共識。為了避免分片交易失效對整個性能的影響，本文定義了一個安全參數(shù) λ來限制分片失效概率，如果滿足以下不等式，則分片是足夠安全的：

2.1.2 網(wǎng)絡交易吞吐量分析模型

區(qū)塊鏈中，網(wǎng)絡交易吞吐量直接取決于兩個參數(shù)：每個區(qū)塊包含的交易數(shù)目，即區(qū)塊大小SB字節(jié)以及區(qū)塊成塊間隔TI。假設分片后每個分片內(nèi)包含的惡意節(jié)點數(shù)目未超過分片內(nèi)總節(jié)點數(shù)目的三分之一，即滿足PBFT 共識算法的要求，則區(qū)塊鏈總交易吞吐量為各個分片的交易吞吐量之和。總交易吞吐量 TH為：

2.1.3 交易平均時延分析模型

PBFT 的共識算法包含3 個階段：pre-prepare階段、prepare 階段以及commit 階段。主節(jié)點接收到來自客戶端的交易請求后，發(fā)送一個共識消息到其他節(jié)點。節(jié)點執(zhí)行PBFT 的3 階段共識流程，返回消息到客戶端，客戶端收到來自 個節(jié)點的相同消息之后完成共識[18]。根據(jù)文獻[19]可知，分片交易平均時延為：

2.2 分片優(yōu)化問題

在本文中，分片區(qū)塊鏈性能優(yōu)化的目的是在滿足安全性約束和交易共識時延約束的條件下，盡可能最大化交易吞吐量。因此，結(jié)合約束式(8)、式(12)，建立分片區(qū)塊鏈優(yōu)化求解問題P1：

f+1

由于區(qū)塊鏈配置參數(shù)復雜以及存在非線性約束，解決上述優(yōu)化問題非常困難。

3 基于演化博弈的節(jié)點分片選擇

采用PBFT 共識算法的分片區(qū)塊鏈網(wǎng)絡可以保證數(shù)據(jù)的最終一致性，但分片內(nèi)惡意節(jié)點的隨機分布導致某些分片內(nèi)交易共識有效性遭到破壞，從而影響這些分片的性能。本節(jié)在不犧牲系統(tǒng)可擴展性和安全性的前提下，設計節(jié)點分片選擇算法，以使惡意節(jié)點盡可能均勻地分布在每個分片中。

3.1 節(jié)點分片選擇的演化博弈問題

區(qū)塊鏈網(wǎng)絡對每個節(jié)點的行為是完全不可知的，且每個節(jié)點不能掌握全局所有節(jié)點的信息，只能獲取自己及鄰居節(jié)點的部分信息。所以，在進行分片選擇時，節(jié)點只能依靠這些不完全信息來給出決策。其次，考慮到節(jié)點是有限理性的，因此，節(jié)點無法一次性給出全局最優(yōu)的分片選擇策略。最后，由于區(qū)塊鏈網(wǎng)絡是一個分布式系統(tǒng)，不存在中央控制節(jié)點，因此，無法對分片的選擇進行全局控制。

目前，演化博弈理論被認為是研究分布式網(wǎng)絡中的有限理性節(jié)點決策行為的有效工具[20]。與傳統(tǒng)博弈模型不同，在演化博弈過程中，節(jié)點不斷與周圍鄰居節(jié)點進行博弈，通過多次試錯達到博弈均衡。同時，演化博弈不要求節(jié)點是完全理性的且不需要掌握全局信息，本節(jié)將共識節(jié)點的分片選擇過程建為演化博弈模型G ={N,S,x,y}，其中：

3.2 收益函數(shù)

在演化博弈中，收益函數(shù)對節(jié)點做出決策起著至關(guān)重要的作用，每個共識節(jié)點在做決策時都傾向于選擇使自身收益最大化的策略。因此，本節(jié)在設計節(jié)點收益函數(shù)，使具有有限理性的共識節(jié)點在進行分片選擇時，選擇使自己收益最大化的分片，能最終逐步達到均衡點。

3.3 演化更新

4 實驗結(jié)果

為了驗證本文提出的算法能夠有效解決分片區(qū)塊鏈的可擴展性和安全性均衡問題，同時能解決惡意節(jié)點分布不均的問題，本節(jié)進行數(shù)值仿真分析。

4.1 仿真參數(shù)配置

在性能理論分析中，本文均假設系統(tǒng)中每個節(jié)點都具有相同的交易處理能力，且每個節(jié)點上的交易處理時延一致。區(qū)塊鏈網(wǎng)絡的交易速率為平均每秒50 筆，除非另有說明，否則仿真參數(shù)如表1 所示。

表1 仿真參數(shù)

4.2 分析模型驗證

通過分析在不同網(wǎng)絡參數(shù)下的網(wǎng)絡性能隨分片數(shù)目的變化情況，來驗證本文提出的分析模型的有效性。

仿真實驗中設置分片數(shù)目為10～100 個，步長為10 個，惡意節(jié)點數(shù)目分別設置為M=[100,150,200,250]。惡意節(jié)點隨機加入到任意分片中，然后根據(jù)式(4)計算分片內(nèi)交易失效的概率。圖1 展示了網(wǎng)絡包含不同惡意節(jié)點數(shù)目下的分片交易失效概率。圖1 表明，當網(wǎng)絡惡意節(jié)點數(shù)為100 個、分片數(shù)目小于50 個時，分片內(nèi)交易失效概率低于2%。同時，當網(wǎng)絡中包含的惡意節(jié)點數(shù)目一定時，分片數(shù)目越多則交易失效概率緩慢上升。此外，還可看到，交易的失效概率隨著網(wǎng)絡包含的惡意節(jié)點數(shù)目的增加而增長。這是由于隨著越來越多新的惡意節(jié)點加入網(wǎng)絡，單個分片內(nèi)可能的惡意節(jié)點數(shù)目隨之變多，導致交易共識失敗，這符合理論模型的分析。

圖1 不同分片數(shù)目下的交易失效概率

其次，實驗分析了不同分片數(shù)目對交易吞吐量和交易共識時延的影響。實驗設置網(wǎng)絡的節(jié)點數(shù)目為N=1 000 個 ，惡意節(jié)點數(shù)占比10%，即M=100個。區(qū)塊大小分別設置為SB=[50,100,150,200] MB。圖2 為區(qū)塊大小逐漸增加時的交易平均共識時延。從中可以看出，交易平均共識時延與區(qū)塊大小和分片數(shù)目有關(guān)，區(qū)塊越大則平均時延越高，因為其增加了交易打包到區(qū)塊的排隊時延。

圖2 不同分片數(shù)目下的共識時延

圖3 不同分片數(shù)目下的交易吞吐量

4.3 演化收斂性分析

圖4 和圖5 分別給出了4 個分片內(nèi)，惡意節(jié)點占比和誠實節(jié)點占比的動態(tài)演化過程。從圖4 和圖5可以觀察到，不同類型的節(jié)點在全網(wǎng)的占比隨著時間的推移逐漸達到平衡點并穩(wěn)定下來，最后每個分片內(nèi)的不同類型節(jié)點的占比都接近一致。因此，其證明了本文提出的演化博弈分片選擇算法具有收斂性，且能使有限理性的節(jié)點最后大概均勻分布于每個分片。

圖4 分片內(nèi)惡意節(jié)點占比的動態(tài)演化

圖5 分片內(nèi)誠實節(jié)點占比的動態(tài)演化

圖6 展示了每個分片內(nèi)節(jié)點的平均收益，在演化初期，由于第四個分片全為誠實節(jié)點，共識的成功率較高，使得該分片內(nèi)的節(jié)點平均收益高于其他3 個分片。隨著博弈演化，越來越多的惡意節(jié)點轉(zhuǎn)移到第四個分片，第四個分片的平均收益逐漸減少，而其他分片的平均收益增加。最后，每個分片內(nèi)的平均收益都達到均衡，具有相同的平均收益。

圖6 分片節(jié)點的平均收益的動態(tài)演化

4.4 性能對比分析

將提出的基于演化博弈的分片算法(用EGT-Based 表示)與Elastico 算法[12]、OmniLedger[13]算法進行性能比較，對比的指標包括交易吞吐量和分片切換時延。實驗設置網(wǎng)絡中惡意節(jié)點的占比為10%，分片數(shù)目為Ns=[1,2,4,8,16]。OmniLedger算法中無偏差隨機數(shù)生成方案RandHound 的參數(shù)c=16。網(wǎng)絡連接帶寬設置為20 Mbps，節(jié)點間通信鏈路時延為100 ms。

圖7 給出了在不同分片算法下的分片切換時延對比結(jié)果。圖7 表明，隨著分片數(shù)目增多，分片切換時延呈現(xiàn)近似線性的增長。其中，Elastico 算法的分片切換時延最長，1 個分片的時延為109 s，16 個分片的時延為743 s。這是因為在Elastico 算法中，節(jié)點需要花費較多的時間求解PoW 難題來加入分片，導致很高的時延。本文提出的EGTBased 算法的分片切換時延要略高于OmniLedger算法，主要由于演化博弈需要進行多輪才能達到均衡，節(jié)點需要和鄰居節(jié)點多次通信，從而導致時延的上升。

圖7 不同分片數(shù)目下的分片切換

圖8 給出了在不同分片算法下的網(wǎng)絡交易吞吐量對比，可以看出，隨著分片數(shù)目增加，本文提出的EGT-Based 分片算法的交易吞吐量要明顯優(yōu)于其他兩種算法。這是因為惡意節(jié)點均勻分布于每個分片，使得單個分片的失效概率接近于0。而在OmniLedger 算法中，RandHound 方案可能選擇惡意節(jié)點擔任主節(jié)點，造成分片的失敗。同時，Elastico算法太過頻繁進行分片重構(gòu)，引入較高的分片切換時延，會造成整體的交易吞吐量下降。

圖8 不同分片數(shù)目下的交易吞吐量

5 結(jié) 束 語

分片技術(shù)有望解決物聯(lián)網(wǎng)區(qū)塊鏈中可擴展性不足的問題。本文首先理論分析了分片區(qū)塊鏈的分片安全性和可擴展性。其次，為了均衡分片區(qū)塊鏈的可擴展和分片安全性，提出了一種基于演化博弈的分片算法來優(yōu)化節(jié)點分片選擇。實驗結(jié)果表明，本文算法可以有效解決分片區(qū)塊鏈中惡意節(jié)點分布不均導致的安全性問題，同時能提高網(wǎng)絡的可擴展性。在未來的工作中，可以在分片區(qū)塊鏈中考慮更多與動態(tài)環(huán)境相關(guān)的因素，如節(jié)點的動態(tài)加入和退出，將本文提出的基于演化博弈的區(qū)塊鏈分片算法應用于真實的物聯(lián)網(wǎng)中。