白首圳，陳美娟

（南京郵電大學(xué) 通信與信息工程學(xué)院，南京 210003）

0 概述

工業(yè)互聯(lián)網(wǎng)作為重要的5G 應(yīng)用場景，將工業(yè)生產(chǎn)效率和生產(chǎn)力達(dá)到前所未有的水平［1］。目前，工業(yè)互聯(lián)網(wǎng)已廣泛應(yīng)用于智能電網(wǎng)、電子商務(wù)、能源控制、高效物流等不同商業(yè)和工業(yè)領(lǐng)域［2］。然而，工業(yè)互聯(lián)網(wǎng)系統(tǒng)采用的集中式架構(gòu)會引發(fā)安全和隱私方面的問題，并且可能存在單點故障，無法提供穩(wěn)定的服務(wù)［3］。隨著連接到工業(yè)互聯(lián)網(wǎng)中的設(shè)備數(shù)量不斷增多，這些問題日益突出。

區(qū)塊鏈?zhǔn)且粋€分布式的共享賬本，一個不可逆轉(zhuǎn)的公共數(shù)據(jù)庫，它使不相關(guān)的參與者能夠根據(jù)特定交易或事件的發(fā)生達(dá)成共識，而無需集中授權(quán)［4］。區(qū)塊鏈的不可篡改、去中心化、可溯源等特點能夠有效解決工業(yè)互聯(lián)網(wǎng)中的安全和隱私問題［5］，但兩者的結(jié)合仍面臨諸多挑戰(zhàn)，總結(jié)為以下兩方面：一方面，工業(yè)互聯(lián)網(wǎng)設(shè)備采集和生成的大量數(shù)據(jù)需要被安全、高效、實時存儲，然而當(dāng)前主流區(qū)塊鏈平臺的吞吐量（Transactions Per Second，TPS）遠(yuǎn)不能滿足工業(yè)互聯(lián)網(wǎng)中海量數(shù)據(jù)快速上鏈存儲的需求［6］；另一方面，區(qū)塊鏈在不同場景下的應(yīng)用都因高冗余存儲機(jī)制（每個節(jié)點存儲一份完整的賬本副本）增強(qiáng)了數(shù)據(jù)的公開性、透明性，確保了數(shù)據(jù)不被篡改，但卻給區(qū)塊鏈帶來了巨大的存儲壓力，傳統(tǒng)區(qū)塊鏈采用的高冗余存儲機(jī)制無法適用于工業(yè)互聯(lián)網(wǎng)場景［7］。

分片技術(shù)是提升區(qū)塊鏈吞吐量最直接有效的手段［8］。將分片技術(shù)應(yīng)用于區(qū)塊鏈就是將原始的區(qū)塊鏈網(wǎng)絡(luò)拆分為若干小規(guī)模的區(qū)塊鏈網(wǎng)絡(luò)，每個網(wǎng)絡(luò)都由原始網(wǎng)絡(luò)中的一部分節(jié)點構(gòu)成，稱為分片。在整個網(wǎng)絡(luò)中的交易會被分配到不同分片進(jìn)行并行處理，因此能夠近似線性地提升區(qū)塊鏈的吞吐量［9］。文獻(xiàn)［10］提出一種基于公有鏈的分片方案ELASTICO。在ELASTICO 的每個共識周期中，參與者都需要計算出工作量證明（Proof of Work，PoW）答案，該答案用于配置分片。各分片采用實用拜占庭容錯（Practical Byzantine Fault Tolerance，PBFT）共識算法驗證交易，共識結(jié)果將被提交到最終分片，最終分片負(fù)責(zé)對其他分片的共識結(jié)果產(chǎn)生最終決策，決策結(jié)果將被返回以更新其他分片。但是，ELASTICO 需要在每輪共識后重新配置分片，且任一分片均須存儲網(wǎng)絡(luò)中其他所有分片的區(qū)塊數(shù)據(jù)，這會造成計算和存儲資源的浪費(fèi)。為解決ELASTICO 存在的問題，文獻(xiàn)［11］提出一種分片協(xié)議OmniLedger，使用分布式隨機(jī)數(shù)生成方案和可驗證隨機(jī)函數(shù)來配置分片，減少了分片過程的計算開銷，但OmniLedger 在處理跨分片交易時需要向全網(wǎng)廣播，并且容錯率與ELASTICO 相同，僅為1/4。文獻(xiàn)［12］提出一種將容錯率提升至1/3 的分片方案RapidChain。同時，為解決OmniLedger 在處理跨分片交易時需要向全網(wǎng)廣播的問題，RapidChain 設(shè)計了分片間路由協(xié)議以快速驗證跨分片交易，減少了通信開銷。但是，RapidChain 是基于網(wǎng)絡(luò)同步的假設(shè)設(shè)計的，在異步網(wǎng)絡(luò)中的性能還未經(jīng)過驗證。文獻(xiàn)［13］提出一種橫向擴(kuò)展的分片協(xié)議Monoxide，通過設(shè)計一種特定的異步共識區(qū)域，使吞吐量能夠隨著共識區(qū)域數(shù)量的增多而線性增加，并且不會影響系統(tǒng)的去中心性。此外，Monoxide 還設(shè)計了一種用于放大算力的PoW 方案，使每個區(qū)域的有效算力與整個網(wǎng)絡(luò)保持相同，從而保證每個分片的安全性。

目前，分片協(xié)議多數(shù)建立在公有鏈的基礎(chǔ)上，有關(guān)聯(lián)盟鏈的分片協(xié)議研究較少。由于公有鏈允許任何節(jié)點加入且區(qū)塊數(shù)據(jù)完全公開，因此對公有鏈分片時，需要借助大量復(fù)雜的計算來增加節(jié)點作惡的成本，以提升網(wǎng)絡(luò)的安全性。然而，聯(lián)盟鏈中的節(jié)點均是通過證書頒發(fā)機(jī)構(gòu)（Certificate Authority，CA）鑒權(quán)后加入到網(wǎng)絡(luò)中的，它們通常只會因為宕機(jī)、網(wǎng)絡(luò)延遲等原因而未能按預(yù)期參與共識過程［14］。得益于聯(lián)盟鏈網(wǎng)絡(luò)的封閉性，文獻(xiàn)［15］提出一種無需通過復(fù)雜計算來確保網(wǎng)絡(luò)安全性的聯(lián)盟鏈分片協(xié)議MDIoTSP。該協(xié)議能夠在保持與ELASTICO 相同吞吐量的前提下縮短區(qū)塊的生成周期，但其分片配置過程僅考慮了節(jié)點的地理位置因素，并且缺少分片重配置過程，使得網(wǎng)絡(luò)在長期運(yùn)行后可能會因為某些節(jié)點發(fā)生故障而無法繼續(xù)正常工作，降低了系統(tǒng)的魯棒性。

上述研究雖然在一定程度上解決了區(qū)塊鏈的性能瓶頸，但是仍存在未考慮區(qū)塊鏈容量不足等問題。因此，亟須設(shè)計一種新的區(qū)塊鏈架構(gòu)，以應(yīng)對來自工業(yè)互聯(lián)網(wǎng)的海量數(shù)據(jù)。為此，本文構(gòu)建一種分層分片區(qū)塊鏈架構(gòu)LSchain（Layering and Sharding blockchain），關(guān)鍵思想是根據(jù)節(jié)點之間的拓?fù)浣Y(jié)構(gòu)將區(qū)塊鏈網(wǎng)絡(luò)劃分為多個分片，并為各分片選取能夠最小化區(qū)塊廣播時間的主節(jié)點。每個分片都對一組不相交的交易運(yùn)行PBFT 共識算法進(jìn)行驗證。在一個共識周期（epoch）內(nèi)，成功經(jīng)過驗證的交易區(qū)塊會被主節(jié)點打包為一個壓縮區(qū)塊，壓縮區(qū)塊內(nèi)包含指向這些交易區(qū)塊的指針。邊緣層各分片會周期性地將交易區(qū)塊卸載到云區(qū)塊鏈層進(jìn)行存儲，本地只存儲體積更小的壓縮區(qū)塊。

1 LSchain 系統(tǒng)模型

針對區(qū)塊鏈應(yīng)用于工業(yè)互聯(lián)網(wǎng)時所面臨的問題，本文構(gòu)建一種適用于工業(yè)互聯(lián)網(wǎng)場景的分層分片區(qū)塊鏈架構(gòu)LSchain，如圖1 所示，LSchain 包括工業(yè)互聯(lián)網(wǎng)平臺層、邊緣區(qū)塊鏈層、云區(qū)塊鏈層等3 層。

圖1 LSchain 系統(tǒng)模型Fig.1 LSchain system model

工業(yè)互聯(lián)網(wǎng)平臺層由多個業(yè)務(wù)相互隔離的工業(yè)部門構(gòu)成，這些工業(yè)部門可以是來自垂直行業(yè)或水平行業(yè)的不同企業(yè)和工廠。各工業(yè)部門內(nèi)包含大量的異構(gòu)設(shè)備，這些設(shè)備由于算力和存儲空間有限，無法充當(dāng)區(qū)塊鏈節(jié)點。工業(yè)互聯(lián)網(wǎng)平臺層產(chǎn)生的大量數(shù)據(jù)會被發(fā)送到邊緣區(qū)塊鏈層中進(jìn)行共識驗證。

邊緣區(qū)塊鏈層由大量邊緣服務(wù)器構(gòu)成，是LSchain 的核心層。這些邊緣服務(wù)器擁有更強(qiáng)的算力和更大的存儲空間，經(jīng)由CA 鑒權(quán)后加入網(wǎng)絡(luò)。依據(jù)邊緣服務(wù)器之間的拓?fù)浣Y(jié)構(gòu)，所有邊緣服務(wù)器會被劃分為若干個分片，各分片并行地運(yùn)行PBFT 共識算法驗證來自工業(yè)互聯(lián)網(wǎng)平臺層的海量數(shù)據(jù)。不同分片之間的交易數(shù)據(jù)來自業(yè)務(wù)相互隔離的不同工業(yè)部門，各分片之間的數(shù)據(jù)互不共享，不存在跨分片交易。由于邊緣服務(wù)器的存儲容量有限，無法滿足大規(guī)模工業(yè)互聯(lián)網(wǎng)中海量數(shù)據(jù)長期存儲的需求，因此邊緣區(qū)塊鏈層會周期性地將經(jīng)過共識驗證的交易區(qū)塊卸載到云區(qū)塊鏈層存儲，邊緣區(qū)塊鏈層只存儲包含交易區(qū)塊索引的壓縮區(qū)塊。

云區(qū)塊鏈層由多個分布式云（例如，阿里云、騰訊云等云服務(wù)租賃平臺）構(gòu)成，它們組成云區(qū)塊鏈網(wǎng)絡(luò)，共同維護(hù)從邊緣區(qū)塊鏈層卸載過來的區(qū)塊數(shù)據(jù)。由于云區(qū)塊鏈層不是本文研究的重點，因此不展開詳細(xì)討論。

2 LSchain 協(xié)議設(shè)計

本節(jié)重點介紹LSchain 邊緣區(qū)塊鏈層中涉及的兩個重要部分，即區(qū)塊鏈網(wǎng)絡(luò)分片和分片內(nèi)主節(jié)點選取。下面詳細(xì)介紹每一部分的實現(xiàn)。

2.1 基于社團(tuán)劃分的區(qū)塊鏈網(wǎng)絡(luò)分片算法

邊緣層區(qū)塊鏈網(wǎng)絡(luò)的節(jié)點由經(jīng)過CA 鑒權(quán)的邊緣服務(wù)器擔(dān)任，這些節(jié)點通常只會因為宕機(jī)、網(wǎng)絡(luò)延遲等原因而未能按預(yù)期參與共識過程，但不排除節(jié)點被惡意劫持的可能。因此，引入聲譽(yù)機(jī)制，用聲譽(yù)值r來描述節(jié)點的可信程度［16］。根據(jù)r的不同，節(jié)點的信譽(yù)狀態(tài)可以分為ST0、ST1、ST2、ST3 等4 類。節(jié)點的信譽(yù)狀態(tài)會隨著它們在共識過程中的行為發(fā)生變化，在共識過程中表現(xiàn)良好的節(jié)點會受到聲譽(yù)值獎勵，獎勵公式如下：

其中：rij是第j個分片中第i個節(jié)點的聲譽(yù)值；rreward是獎勵的聲譽(yù)值。

在共識過程中做出錯誤決策的節(jié)點會受到聲譽(yù)值懲罰，懲罰公式如下：

其中：rpunishment是懲罰的聲譽(yù)值。rreward和rpunishment的取值可以根據(jù)實際應(yīng)用場景進(jìn)行調(diào)整。

節(jié)點信譽(yù)狀態(tài)的轉(zhuǎn)換過程如圖2 所示。

圖2 節(jié)點信譽(yù)狀態(tài)的轉(zhuǎn)換過程Fig.2 Conversion process of the node reputation state

在網(wǎng)絡(luò)初始化時，LSchain 會將所有節(jié)點的初始r都置為rnormal。rcredible、rnormal和rinvalid為3 個聲譽(yù)門限值，它們的關(guān)系為rinvalid

表1 節(jié)點權(quán)限分類Table 1 Node permission classification

信譽(yù)狀態(tài)為ST1 和ST2 的節(jié)點都只能作為普通共識節(jié)點參與共識過程；信譽(yù)狀態(tài)為ST3 的節(jié)點才有資格競選成為主節(jié)點；信譽(yù)狀態(tài)為ST0 的非法節(jié)點將被禁止參與接下來的共識過程。該權(quán)限分類可以有效防止惡意節(jié)點阻礙共識過程。

基于聯(lián)盟鏈的準(zhǔn)入機(jī)制和上述聲譽(yù)機(jī)制對節(jié)點可信狀態(tài)的描述，惡意節(jié)點將被隔離在網(wǎng)絡(luò)之外。因此，對邊緣層區(qū)塊鏈網(wǎng)絡(luò)分片時，無需再通過復(fù)雜的計算來確保分片后區(qū)塊鏈網(wǎng)絡(luò)的安全性。根據(jù)邊緣服務(wù)器之間的拓?fù)浣Y(jié)構(gòu)，可以將邊緣層區(qū)塊鏈網(wǎng)絡(luò)表示成如下矩陣形式：

其中：A為邊緣層區(qū)塊鏈網(wǎng)絡(luò)的鄰接矩陣；aij用來刻畫節(jié)點之間的連通情況，aij=1 表示節(jié)點ni和nj之間有邊相連，aij=0 表示節(jié)點ni和nj之間無邊相連，只有借助其他節(jié)點轉(zhuǎn)發(fā)才能通信，并且規(guī)定aii≡0，i=1，2，…，n。

上述工作從復(fù)雜網(wǎng)絡(luò)角度分析了邊緣層區(qū)塊鏈網(wǎng)絡(luò)?；诖?，LSchain 探索將區(qū)塊鏈網(wǎng)絡(luò)的分片問題轉(zhuǎn)化為復(fù)雜網(wǎng)絡(luò)的社團(tuán)劃分問題。復(fù)雜網(wǎng)絡(luò)的社團(tuán)劃分研究主要包含以下3 個方面：1）如何定義一個社團(tuán)；2）如何判定劃分結(jié)果的優(yōu)劣；3）如何在一個合理的劃分標(biāo)準(zhǔn)下，設(shè)計一種高效的劃分算法。

經(jīng)典的社團(tuán)劃分算法GN（Girvan-Newman）通過不斷從網(wǎng)絡(luò)中移除介數(shù)最大的邊，將整個網(wǎng)絡(luò)劃分為不同的社團(tuán)［17］，但GN 算法的復(fù)雜度達(dá)到了O（n3）（n為網(wǎng)絡(luò)中節(jié)點的數(shù)量），目前僅局限于對中等規(guī)模的網(wǎng)絡(luò)進(jìn)行社團(tuán)劃分。

基于上述原因，NEWMAN 等［18］在GN 算法的基礎(chǔ)上提出一種快速算法——FN（Fast-Newman）。FN算法繼承了貪心算法的思想，從所有節(jié)點各自作為一個社團(tuán)開始，沿著使模塊度Q增大最多或減小最少的方向不斷合并社團(tuán)，直至整個網(wǎng)絡(luò)都合并為一個社團(tuán)。由于FN 算法需要在每輪合并過程中遍歷有邊相連的社團(tuán)并計算模塊度增量，這一過程的復(fù)雜度為O（m）（m為網(wǎng)絡(luò)中邊的數(shù)量），并且在合并完成后還需要更新社團(tuán)結(jié)構(gòu)，這一過程的復(fù)雜度為O（n），因此每輪合并的復(fù)雜度為O（m+n）。又因為FN 算法最多需要合并n-1 輪，所以其總復(fù)雜度為O（（m+n）n）。在FN 算法中，用模塊度Q來衡量社團(tuán)劃分結(jié)果的質(zhì)量，Q的取值范圍為［0，1］，值越大說明社團(tuán)結(jié)構(gòu)越明顯，劃分結(jié)果越好。一般的網(wǎng)絡(luò)社團(tuán)劃分結(jié)果的Q值介于0.3～0.7，Q的計算公式［19］如下：

其中：k為社團(tuán)數(shù)；eij表示網(wǎng)絡(luò)中連接兩個不同社團(tuán)si和sj的節(jié)點的邊相對于所有邊的比例；ai表示與社團(tuán)si中的節(jié)點相連的邊相對于所有邊的比例。

FN 算法需要不斷合并社團(tuán)，只有整個網(wǎng)絡(luò)都合并為一個社團(tuán)時才收斂。邊緣層各分片區(qū)塊鏈網(wǎng)絡(luò)采用的PBFT 共識算法對參與共識的節(jié)點數(shù)量有嚴(yán)格限制，即節(jié)點數(shù)應(yīng)不小于4 且不大于100［20］。為使FN 算法能夠應(yīng)用于邊緣層區(qū)塊鏈網(wǎng)絡(luò)的分片過程，LSchain 在FN 算法的合并過程中改進(jìn)了合并約束與收斂條件，以控制合并后的分片規(guī)模，并減少合并過程的算力消耗與合并輪數(shù)。

對于具有n個節(jié)點的邊緣層區(qū)塊鏈網(wǎng)絡(luò)，改進(jìn)的FN 算法包括以下3 個執(zhí)行步驟：

步驟1將網(wǎng)絡(luò)初始化為n個分片，即每個節(jié)點各自作 為1 個分片。此 時Q=0，eij和αi滿足式（5）和式（6）：

其中：ni～nj表示節(jié)點ni和nj之間有邊相連；ki為節(jié)點ni的度。

步驟2遍歷有邊相連的分片對，判斷將分片對合并后是否滿足約束：

其中：si∪sj表示將分片si和sj合并；card（）函數(shù)用于計算有限集合的元素個數(shù)。式（7）用于控制合并后的分片規(guī)模，確保每個分片包含的節(jié)點數(shù)不超過100，并減少ΔQ的計算次數(shù)。若分片對滿足式（7），則計算合并后的ΔQij：

根據(jù)貪心算法的原理，從滿足式（7）的分片對中選取能使Q增大最多或減小最少的分片對合并。在每輪合并后，更新對應(yīng)的eij，并將E=（eij）n×n矩陣中對應(yīng)si、sj分片的行和列相加，然后計算Q=Q+max｛ΔQ｝。

步驟3重復(fù)執(zhí)行步驟2 以不斷合并分片，直至滿足以下收斂條件：

式（9）的物理含義為：繼續(xù)合并網(wǎng)絡(luò)中任意兩個分片后均會使合并后的分片規(guī)模大于100。借助式（9），本文改進(jìn)的FN 算法可以減少合并輪數(shù)，從而提升算法的時間性能。

改進(jìn)合并約束與收斂條件的FN 算法流程如圖3所示。

圖3 改進(jìn)合并約束與收斂條件的FN 算法流程Fig.3 FN algorithm procedure for improving merger constraints and convergence conditions

根據(jù)邊緣區(qū)塊鏈層節(jié)點數(shù)量的不同，算法的運(yùn)行結(jié)果分為2 種情況：1）如果n≤100，則改進(jìn)FN 算法與原始FN 算法的運(yùn)行結(jié)果相同，均會得到一個分片結(jié)構(gòu)分解的樹狀圖，通過選擇在不同位置斷開可以得到不同的分片配置方案；2）如果n＞100，則改進(jìn)FN算法的運(yùn)行結(jié)果為包含多個分片結(jié)構(gòu)分解樹狀圖的森林，其中的每一顆樹代表一個分片，可以根據(jù)實際應(yīng)用場景的需求進(jìn)一步拆分其中的某些分片，以獲得更多的分片數(shù)量。改進(jìn)的FN 算法通過減少合并過程中ΔQ的計算次數(shù)與合并輪數(shù)將算法的復(fù)雜度降為O（（m′+n）n′）（m′≤m且n′≤n，等號僅在n≤100 時成立），從而提高了算法的時間性能，減少了邊緣層區(qū)塊鏈網(wǎng)絡(luò)分片花費(fèi)的時間。

2.2 基于生成樹的分片內(nèi)主節(jié)點選取算法

在工業(yè)互聯(lián)網(wǎng)中的許多應(yīng)用場景都對時延提出了很高的要求，而區(qū)塊鏈中的共識機(jī)制往往非常耗時［21］。無論是公有鏈廣泛采用的PoW、權(quán)益證明（Proof of Stake，PoS）共識算法，還是受聯(lián)盟鏈和私有鏈青睞的拜占庭容錯（Byzantine Fault Tolerance，BFT）類共識算法，都需要耗費(fèi)大量的時間用于向全網(wǎng)廣播區(qū)塊，包括邊緣層各分片區(qū)塊鏈采用的PBFT共識算法。在PBFT 中，一個主節(jié)點將交易打包成區(qū)塊，并將其廣播至全網(wǎng)供其他節(jié)點驗證的過程可以轉(zhuǎn)化為一顆生成樹。以一個隨機(jī)生成的小規(guī)模網(wǎng)絡(luò)拓?fù)錇槔?，如圖4 所示，在這個拓?fù)渲杏? 個節(jié)點和16 條邊。假設(shè)節(jié)點6 是網(wǎng)絡(luò)中的主節(jié)點，由主節(jié)點打包生成的區(qū)塊需要廣播至整個網(wǎng)絡(luò)，在圖5 中的生成樹可以表示區(qū)塊的廣播過程。

圖4 隨機(jī)生成的網(wǎng)絡(luò)拓?fù)銯ig.4 Randomly generated network topology

圖5 基于生成樹的區(qū)塊廣播過程Fig.5 Block broadcast process based on spanning tree

首先，以節(jié)點6 為根節(jié)點求圖4 的生成樹，可以確保區(qū)塊以最少的通信次數(shù)廣播至整個網(wǎng)絡(luò)。在類似圖5 的生成樹中，假設(shè)vi是節(jié)點ni驗證區(qū)塊所需的時間，則所有節(jié)點的驗證延遲集合V表示如下：

其中：I是生成樹中的節(jié)點數(shù)。

然后，用dij表示任意兩個有邊相連的節(jié)點（如節(jié)點ni和它的鄰居節(jié)點nj）之間的傳輸延遲；用cm表示節(jié)點nm接收到區(qū)塊并完成區(qū)塊驗證所花費(fèi)的時間；用Nm表示從主節(jié)點到節(jié)點nm的路徑上所有節(jié)點的標(biāo)識集（其元素按接收區(qū)塊的順序排列）。基于此，區(qū)塊從主節(jié)點傳播至節(jié)點nm的時間cm可以表示如下：

將式（11）代入式（12）后發(fā)現(xiàn)，路徑上的節(jié)點數(shù)與路徑上的最后一個節(jié)點接收區(qū)塊并完成驗證所花費(fèi)的時間之間存在很強(qiáng)的相關(guān)性。每條傳播路徑對應(yīng)于樹的一個分支，路徑上的節(jié)點數(shù)量決定了分支的長度。由此可以推斷出：網(wǎng)絡(luò)中參與區(qū)塊驗證的最后一個節(jié)點位于最長分支的末端，該分支的長度等于生成樹的深度。綜上所述，減少生成樹的深度意味著減少區(qū)塊廣播至全網(wǎng)的時間，因此可以將區(qū)塊的廣播時間問題轉(zhuǎn)化為生成樹的深度問題。

基于上述結(jié)論，本文提出一種通過尋找分片內(nèi)的最小深度生成樹來選取分片內(nèi)主節(jié)點的算法，以取代PBFT 隨機(jī)選取主節(jié)點的方案，詳見算法1。

算法1最小深度生成樹算法

算法1 通過尋找分片內(nèi)區(qū)塊傳播深度最小的生成樹，為每個分片選取可以最小化區(qū)塊廣播時間的主節(jié)點。因為網(wǎng)絡(luò)初始化時會將所有節(jié)點的聲譽(yù)值都置為rnormal，所以在每次網(wǎng)絡(luò)初始化后第一次運(yùn)行最小深度生成樹算法時，聲譽(yù)門限值應(yīng)設(shè)為rnormal。經(jīng)過幾輪epoch 共識后，為選取更加可靠的節(jié)點擔(dān)任分片內(nèi)的主節(jié)點，聲譽(yù)門限值應(yīng)設(shè)為rcredible。

下面以圖6 中4 個節(jié)點運(yùn)行PBFT 算法的共識流程為例，分析由最小深度生成樹算法選取的主節(jié)點對PBFT 共識算法吞吐量的影響。

圖6 4 個節(jié)點的PBFT 共識流程Fig.6 PBFT consensus flow of four nodes

共識流程的3 個核心階段分別為pre-prepare 階段、prepare 階段和commit 階段［22］，其中，pre-prepare階段是最小深度生成樹算法關(guān)注的由主節(jié)點向全網(wǎng)廣播區(qū)塊的階段。PBFT 共識算法的吞吐量可以表示如下：

其中：N表示時間T內(nèi)包含的交易數(shù)量。

將T分解為通信時間Tc和驗證時間Tv，則式（13）可以表示如下：

然后采用文獻(xiàn)[14]給出的無可靠度約束等維修周期預(yù)防性維護(hù)模型，代入相同動態(tài)可變參數(shù)后，分別得到與本維護(hù)模型最佳維修策略(0.75,13)和(0.95,15)有相同預(yù)防維修次數(shù)時的維修優(yōu)化結(jié)果，如表3所示,其中：總維修費(fèi)用C0=[E(C0)]×L0。

將通信時間進(jìn)一步拆分為算法5 個階段的通信時 間Tc_request、Tc_pre-prepare、Tc_prepare、Tc_commit和Tc_reply后，式（14）可以表示如下：

重點關(guān)注區(qū)塊廣播pre-prepare 階段，將其余4 個階段的通信時間合并為Tc_others，式（15）可以進(jìn)一步表示如下：

假設(shè)將pre-prepare 階段的區(qū)塊廣播過程轉(zhuǎn)化為生成樹后，樹的深度為d，則式（16）可以表示如下：

其中：Tc_depthi表示生成樹中第i層的通信時間。

假設(shè)任意兩個邊緣服務(wù)器之間的通信時延趨向于一個相近值Tc_average，則式（17）可以表示如下：

由上述分析可知，將算法1 中求出的生成樹深度最小的節(jié)點作為分片內(nèi)的主節(jié)點，可以縮短PBFT共識過程花費(fèi)的時間，進(jìn)而提升邊緣層各分片區(qū)塊鏈網(wǎng)絡(luò)的吞吐量。

3 實驗設(shè)置與結(jié)果分析

本節(jié)首先通過仿真實驗對所提的改進(jìn)FN 算法和最小深度生成樹算法進(jìn)行性能分析，然后對LSchain 的安全性進(jìn)行理論分析。

3.1 性能分析

采用MATLAB 進(jìn)行仿真測試，實驗環(huán)境如下：處理器Intel?CoreTMi5-10210U，主頻1.60 GHz，內(nèi)存16 GB，操作系統(tǒng)Microsoft Windows 10 64 位。

3.1.1 改進(jìn)FN 算法的性能分析

2 個性能指標(biāo)為分片時間和分片結(jié)果Q值，對比算法為文獻(xiàn)［18］所提的原始FN 算法，實驗結(jié)果均為多次運(yùn)行結(jié)果取平均值。首先，對比2 種算法對同一網(wǎng)絡(luò)分片時所花費(fèi)的時間，以驗證改進(jìn)的FN 算法在縮短分片時間方面的性能。然后，對比2 種算法對同一網(wǎng)絡(luò)分片后的模塊度Q值，以衡量改進(jìn)FN 算法的分片質(zhì)量。實驗所用數(shù)據(jù)集為來自斯坦福大學(xué)的大型網(wǎng)絡(luò)數(shù)據(jù)集網(wǎng)站和Mark Newman 的個人數(shù)據(jù)集網(wǎng)站的5 個關(guān)系網(wǎng)絡(luò)，5 個網(wǎng)絡(luò)的規(guī)模信息如表2 所示。

表2 數(shù)據(jù)集基本信息Table 2 Dataset basic information

從圖7 可以看出，改進(jìn)的FN 算法在對小型網(wǎng)絡(luò)分片時花費(fèi)的時間與原始FN 算法幾乎相同，但隨著網(wǎng)絡(luò)規(guī)模的增大，改進(jìn)的FN 算法對網(wǎng)絡(luò)分片時花費(fèi)的時間明顯少于原始FN 算法，并且時間差越來越大，對于5 號這一大型網(wǎng)絡(luò)，改進(jìn)的FN 算法能夠在不犧牲分片質(zhì)量的前提下將分片時間縮短約36%。這是因為：當(dāng)網(wǎng)絡(luò)中的節(jié)點數(shù)不超過100 時，改進(jìn)的FN 算法等同于原始FN 算法；當(dāng)節(jié)點數(shù)超過100 時，改進(jìn)的FN 算法通過改進(jìn)合并約束與收斂條件，減少了合并過程中ΔQ的計算次數(shù)與合并輪數(shù)，從而提高了算法的時間性能，縮短了分片時間。

圖7 分片時間對比Fig.7 Comparison of the sharding times

從圖8 可以看出：當(dāng)網(wǎng)絡(luò)中的節(jié)點數(shù)不超過100時，2 種算法的分片結(jié)果Q值相同，再次印證了對于節(jié)點數(shù)不超過100 的小規(guī)模網(wǎng)絡(luò)，改進(jìn)的FN 算法等同于原始FN 算法；當(dāng)網(wǎng)絡(luò)中的節(jié)點數(shù)超過100 時，改進(jìn)FN 算法的分片結(jié)果Q值圍繞原始FN 算法的分片結(jié)果Q值在不超過0.1 的范圍內(nèi)波動。這是因為改進(jìn)的FN 算法在繼承原始FN 算法最大化Q值思想的同時，也不可避免地繼承了原始FN 算法只能選取局部最優(yōu)解的特性（根據(jù)2.1 節(jié)的描述，算法在合并過程中的某幾輪可能會使Q值減?。?。對網(wǎng)絡(luò)編號為2～5 的網(wǎng)絡(luò)進(jìn)行分片后，改進(jìn)的FN 算法與原始FN 算法相比減少了合并輪數(shù)，而減少的這幾輪合并過程既有可能使Q值繼續(xù)增大，也有可能使Q值減小，導(dǎo)致了改進(jìn)的FN 算法的分片結(jié)果Q值與原始FN 算法相比時高時低，但2 種算法的Q值差距很小，且2 種算法的Q值均在正常范圍內(nèi)。

圖8 分片結(jié)果Q 值對比Fig.8 Comparison of the Q value of sharding results

從圖7、圖8 的實驗結(jié)果可以看出，本文改進(jìn)的FN算法在不犧牲分片質(zhì)量的前提下提升了分片效率，從而減少了區(qū)塊鏈網(wǎng)絡(luò)分片以及分片重配置的時間。

3.1.2 最小深度生成樹算法的性能分析

為了驗證最小深度生成樹算法在減少區(qū)塊廣播時間方面的性能，選取主節(jié)點的生成樹深度作為性能指標(biāo)。對比方案為文獻(xiàn)［22］所提共識算法采用的主節(jié)點選取策略，實驗結(jié)果均為多次運(yùn)行結(jié)果取平均值。首先對比由最小深度生成樹算法選取的主節(jié)點和由PBFT算法選取的主節(jié)點的生成樹深度，為保證實驗的公平性，規(guī)定PBFT 算法只能從最小深度生成樹算法的備選節(jié)點集中選取主節(jié)點；然后對比分片數(shù)量對最小深度生成樹算法性能的影響；最后測試網(wǎng)絡(luò)的連通性對最小深度生成樹算法性能的影響。

實驗數(shù)據(jù)由隨機(jī)網(wǎng)絡(luò)生成模型Salama［23］生成。Salama 模型中有2 個重要的網(wǎng)絡(luò)特征參數(shù)α和β，其中，α代表網(wǎng)絡(luò)中短邊相對于長邊的比例，β代表網(wǎng)絡(luò)中邊的密度。α和β共同決定了網(wǎng)絡(luò)的連通性，α/β越大，網(wǎng)絡(luò)的連通性越好。實驗通過控制Salama模型的網(wǎng)絡(luò)特征參數(shù)α和β，生成規(guī)模不同但連通性相同的網(wǎng)絡(luò)以模擬各分片區(qū)塊鏈網(wǎng)絡(luò)。下面如無特殊說明，均由相同比例的α/β生成實驗網(wǎng)絡(luò)，以確保不同規(guī)模的網(wǎng)絡(luò)連通性相同。

從圖9 可以看出，在不同分片規(guī)模（包含的節(jié)點數(shù)不同）下，最小深度生成樹算法選取的主節(jié)點的生成樹深度均要小于PBFT算法選取的主節(jié)點的生成樹深度。這是因為PBFT 共識算法的主節(jié)點是在每輪共識開始之前隨機(jī)選取的。最小深度生成樹算法通過遍歷備選節(jié)點的生成樹，選取生成樹深度最小的節(jié)點來擔(dān)任主節(jié)點。因此，在減少區(qū)塊廣播時間方面，最小深度生成樹算法的主節(jié)點選取策略優(yōu)于PBFT 算法的主節(jié)點選取策略。

圖9 主節(jié)點的生成樹深度對比Fig.9 Comparison of the spanning tree depth of leader node

從圖10 可以看出，當(dāng)同一個網(wǎng)絡(luò)被分為不同分片時，各分片由最小深度生成樹算法選取的主節(jié)點的生成樹深度與分片數(shù)成反比。這是因為實驗為控制變量，假設(shè)每個分片的規(guī)模相同（包含的節(jié)點數(shù)相同）。分片數(shù)越多，每個分片的規(guī)模越小，由最小深度生成樹算法選取的主節(jié)點的生成樹深度就越淺?；诖?，LSchain 可以根據(jù)工業(yè)互聯(lián)網(wǎng)平臺層的業(yè)務(wù)需求動態(tài)地劃分邊緣層區(qū)塊鏈網(wǎng)絡(luò)：當(dāng)網(wǎng)絡(luò)負(fù)載大時，將網(wǎng)絡(luò)分為更多的片，以優(yōu)先滿足吞吐量需求；當(dāng)網(wǎng)絡(luò)負(fù)載小時，將網(wǎng)絡(luò)分為更少的片，以更好地保障網(wǎng)絡(luò)的安全。

圖10 同等網(wǎng)絡(luò)規(guī)模下不同分片數(shù)的生成樹深度對比Fig.10 Depth comparison of the spanning tree with different shards number in the same network scale

從圖11 可以看出，α/β越大（即網(wǎng)絡(luò)的連通性越好）的分片，由最小深度生成樹算法選取的主節(jié)點的生成樹深度就越淺。這是因為連通圖（任意兩個節(jié)點都有邊相連的網(wǎng)絡(luò)）的生成樹深度具有理論上下限。節(jié)點數(shù)量為n的全局耦合網(wǎng)絡(luò)僅需1 跳即可到達(dá)網(wǎng)絡(luò)中的任意位置，這種網(wǎng)絡(luò)的生成樹深度恒為1，連通性最好；任一節(jié)點數(shù)為n，邊數(shù)為n-1 的網(wǎng)絡(luò)，其生成樹的最小可能深度為（n-1）/2，最大可能深度為n-1，這種網(wǎng)絡(luò)的連通性最差。所以，連通性越好的網(wǎng)絡(luò)，其生成樹的最小可能深度越接近1。

圖11 同等網(wǎng)絡(luò)規(guī)模下不同連通度分片的生成樹深度對比Fig.11 Comparison of the spanning tree depth of the shards with different connectivity in the same network scale

3.2 安全性分析

在邊緣層區(qū)塊鏈網(wǎng)絡(luò)中，承擔(dān)區(qū)塊鏈節(jié)點角色的各邊緣服務(wù)器可能會遭到惡意攻擊，從而影響系統(tǒng)的正常運(yùn)行。本節(jié)主要從LSchain 協(xié)議能夠抵御單分片接管攻擊和主節(jié)點自私攻擊兩方面進(jìn)行說明。

3.2.1 單分片接管攻擊抵御

為確保邊緣層區(qū)塊鏈網(wǎng)絡(luò)的安全，所有分片均需滿足PBFT 算法的容錯限制，即惡意節(jié)點數(shù)f不超過節(jié)點總數(shù)的1/3。任何分片突破這個限制，都會導(dǎo)致分片被惡意節(jié)點劫持，從而影響整個邊緣層區(qū)塊鏈網(wǎng)絡(luò)的正常運(yùn)行，這被稱為單分片接管攻擊［24］。為了能及時偵測到被惡意劫持的分片，LSchain 規(guī)定各分片內(nèi)的節(jié)點應(yīng)定時向CA 發(fā)送心跳消息，心跳消息中包含各節(jié)點用自己的私鑰對所處分片安全狀態(tài)的決策簽名。當(dāng)誠實節(jié)點在共識過程中檢測到分片內(nèi)的惡意節(jié)點數(shù)超過PBFT 容錯限制時，會向CA 發(fā)送否認(rèn)分片狀態(tài)安全的決策簽名。在各分片的心跳消息集中需要包含至少f+1（確保至少有1 個誠實節(jié)點可以向CA 反饋真實的網(wǎng)絡(luò)狀態(tài)）條為安全狀態(tài)背書的簽名，該分片才能繼續(xù)運(yùn)行。若某分片的心跳消息集中少于f+1 的節(jié)點認(rèn)為該分片安全，則停用該分片，并計算該分片中各節(jié)點在本輪epoch 中累積的r。根據(jù)節(jié)點的r判斷節(jié)點的信譽(yù)狀態(tài)，狀態(tài)為ST0的節(jié)點將被禁止參與接下來的共識過程，直至其經(jīng)過安全漏洞修復(fù)并向CA 申請才能重新加入網(wǎng)絡(luò)。因此，LSchain 協(xié)議在一定程度上抵御了單分片接管攻擊。

3.2.2 主節(jié)點自私攻擊抵御

PBFT 共識算法需要在每輪共識開始前隨機(jī)選取主節(jié)點，而LSchain 通過最小深度生成樹算法為各分片選取的主節(jié)點可以最小化區(qū)塊廣播時間，并且具有較高的聲譽(yù)值。因此，各分片內(nèi)的主節(jié)點在沒有不良行為的情況下無需頻繁更換，但當(dāng)分片內(nèi)的其余節(jié)點檢測到主節(jié)點作惡或長時間未響應(yīng)時均會觸發(fā)視圖切換（view-change）過程［25］。view-change會重新運(yùn)行最小深度生成樹算法以選取新的主節(jié)點，同時作惡主節(jié)點的聲譽(yù)值將會被直接清零。該方式與普通節(jié)點作惡的處置方式相同，直至經(jīng)過安全漏洞修復(fù)并向CA 申請才能重新加入網(wǎng)絡(luò)。因此，本文方案在一定程度上抵御了主節(jié)點自私攻擊。

4 結(jié)束語

本文針對區(qū)塊鏈應(yīng)用于工業(yè)互聯(lián)網(wǎng)時所面臨的吞吐量不足和存儲壓力較大的問題：首先構(gòu)建分層存儲架構(gòu)，將工業(yè)互聯(lián)網(wǎng)產(chǎn)生的海量數(shù)據(jù)在邊緣區(qū)塊鏈層和云區(qū)塊鏈層中進(jìn)行分層維護(hù)，解決了區(qū)塊鏈存儲容量不足的問題；然后基于經(jīng)典社團(tuán)劃分算法設(shè)計并改進(jìn)區(qū)塊鏈網(wǎng)絡(luò)分片算法，在提升區(qū)塊鏈吞吐量的同時縮短了分片時間；最后論證了區(qū)塊廣播時間對吞吐量的影響，提出一種能夠最小化各分片內(nèi)區(qū)塊廣播時間的主節(jié)點選取算法，進(jìn)一步提升了邊緣層區(qū)塊鏈的吞吐量。實驗結(jié)果表明，與經(jīng)典社團(tuán)劃分算法以及隨機(jī)選取主節(jié)點的策略相比，所提方案能夠同時減少分片時間和各分片內(nèi)區(qū)塊的廣播時間。下一步將完善邊緣層交易區(qū)塊的卸載機(jī)制，并針對工業(yè)互聯(lián)網(wǎng)場景設(shè)計合理有效的區(qū)塊存儲卸載算法，以降低邊緣層區(qū)塊鏈節(jié)點的存儲壓力。