白首圳，陳美娟

（南京郵電大學(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ā)安全和隱私方面的問題，并且可能存在單點(diǎn)故障，無法提供穩(wěn)定的服務(wù)［3］。隨著連接到工業(yè)互聯(lián)網(wǎng)中的設(shè)備數(shù)量不斷增多，這些問題日益突出。

區(qū)塊鏈?zhǔn)且粋€(gè)分布式的共享賬本，一個(gè)不可逆轉(zhuǎn)的公共數(shù)據(jù)庫，它使不相關(guān)的參與者能夠根據(jù)特定交易或事件的發(fā)生達(dá)成共識，而無需集中授權(quán)［4］。區(qū)塊鏈的不可篡改、去中心化、可溯源等特點(diǎn)能夠有效解決工業(yè)互聯(lián)網(wǎng)中的安全和隱私問題［5］，但兩者的結(jié)合仍面臨諸多挑戰(zhàn)，總結(jié)為以下兩方面：一方面，工業(yè)互聯(lián)網(wǎng)設(shè)備采集和生成的大量數(shù)據(jù)需要被安全、高效、實(shí)時(shí)存儲，然而當(dāng)前主流區(qū)塊鏈平臺的吞吐量（Transactions Per Second，TPS）遠(yuǎn)不能滿足工業(yè)互聯(lián)網(wǎng)中海量數(shù)據(jù)快速上鏈存儲的需求［6］；另一方面，區(qū)塊鏈在不同場景下的應(yīng)用都因高冗余存儲機(jī)制（每個(gè)節(jié)點(diǎn)存儲一份完整的賬本副本）增強(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ò)，每個(gè)網(wǎng)絡(luò)都由原始網(wǎng)絡(luò)中的一部分節(jié)點(diǎn)構(gòu)成，稱為分片。在整個(gè)網(wǎng)絡(luò)中的交易會被分配到不同分片進(jìn)行并行處理，因此能夠近似線性地提升區(qū)塊鏈的吞吐量［9］。文獻(xiàn)［10］提出一種基于公有鏈的分片方案ELASTICO。在ELASTICO 的每個(gè)共識周期中，參與者都需要計(jì)算出工作量證明（Proof of Work，PoW）答案，該答案用于配置分片。各分片采用實(shí)用拜占庭容錯(cuò)（Practical Byzantine Fault Tolerance，PBFT）共識算法驗(yàn)證交易，共識結(jié)果將被提交到最終分片，最終分片負(fù)責(zé)對其他分片的共識結(jié)果產(chǎn)生最終決策，決策結(jié)果將被返回以更新其他分片。但是，ELASTICO 需要在每輪共識后重新配置分片，且任一分片均須存儲網(wǎng)絡(luò)中其他所有分片的區(qū)塊數(shù)據(jù)，這會造成計(jì)算和存儲資源的浪費(fèi)。為解決ELASTICO 存在的問題，文獻(xiàn)［11］提出一種分片協(xié)議OmniLedger，使用分布式隨機(jī)數(shù)生成方案和可驗(yàn)證隨機(jī)函數(shù)來配置分片，減少了分片過程的計(jì)算開銷，但OmniLedger 在處理跨分片交易時(shí)需要向全網(wǎng)廣播，并且容錯(cuò)率與ELASTICO 相同，僅為1/4。文獻(xiàn)［12］提出一種將容錯(cuò)率提升至1/3 的分片方案RapidChain。同時(shí)，為解決OmniLedger 在處理跨分片交易時(shí)需要向全網(wǎng)廣播的問題，RapidChain 設(shè)計(jì)了分片間路由協(xié)議以快速驗(yàn)證跨分片交易，減少了通信開銷。但是，RapidChain 是基于網(wǎng)絡(luò)同步的假設(shè)設(shè)計(jì)的，在異步網(wǎng)絡(luò)中的性能還未經(jīng)過驗(yàn)證。文獻(xiàn)［13］提出一種橫向擴(kuò)展的分片協(xié)議Monoxide，通過設(shè)計(jì)一種特定的異步共識區(qū)域，使吞吐量能夠隨著共識區(qū)域數(shù)量的增多而線性增加，并且不會影響系統(tǒng)的去中心性。此外，Monoxide 還設(shè)計(jì)了一種用于放大算力的PoW 方案，使每個(gè)區(qū)域的有效算力與整個(gè)網(wǎng)絡(luò)保持相同，從而保證每個(gè)分片的安全性。

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

上述研究雖然在一定程度上解決了區(qū)塊鏈的性能瓶頸，但是仍存在未考慮區(qū)塊鏈容量不足等問題。因此，亟須設(shè)計(jì)一種新的區(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é)點(diǎn)之間的拓?fù)浣Y(jié)構(gòu)將區(qū)塊鏈網(wǎng)絡(luò)劃分為多個(gè)分片，并為各分片選取能夠最小化區(qū)塊廣播時(shí)間的主節(jié)點(diǎn)。每個(gè)分片都對一組不相交的交易運(yùn)行PBFT 共識算法進(jìn)行驗(yàn)證。在一個(gè)共識周期（epoch）內(nèi)，成功經(jīng)過驗(yàn)證的交易區(qū)塊會被主節(jié)點(diǎn)打包為一個(gè)壓縮區(qū)塊，壓縮區(qū)塊內(nèi)包含指向這些交易區(qū)塊的指針。邊緣層各分片會周期性地將交易區(qū)塊卸載到云區(qū)塊鏈層進(jìn)行存儲，本地只存儲體積更小的壓縮區(qū)塊。

1 LSchain 系統(tǒng)模型

針對區(qū)塊鏈應(yīng)用于工業(yè)互聯(lián)網(wǎng)時(shí)所面臨的問題，本文構(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)平臺層由多個(gè)業(yè)務(wù)相互隔離的工業(yè)部門構(gòu)成，這些工業(yè)部門可以是來自垂直行業(yè)或水平行業(yè)的不同企業(yè)和工廠。各工業(yè)部門內(nèi)包含大量的異構(gòu)設(shè)備，這些設(shè)備由于算力和存儲空間有限，無法充當(dāng)區(qū)塊鏈節(jié)點(diǎn)。工業(yè)互聯(lián)網(wǎng)平臺層產(chǎn)生的大量數(shù)據(jù)會被發(fā)送到邊緣區(qū)塊鏈層中進(jìn)行共識驗(yà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ù)器會被劃分為若干個(gè)分片，各分片并行地運(yùn)行PBFT 共識算法驗(yàn)證來自工業(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)過共識驗(yàn)證的交易區(qū)塊卸載到云區(qū)塊鏈層存儲，邊緣區(qū)塊鏈層只存儲包含交易區(qū)塊索引的壓縮區(qū)塊。

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

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

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

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

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

其中：rij是第j個(gè)分片中第i個(gè)節(jié)點(diǎn)的聲譽(yù)值；rreward是獎(jiǎng)勵(lì)的聲譽(yù)值。

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

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

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

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

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

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

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

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

其中：A為邊緣層區(qū)塊鏈網(wǎng)絡(luò)的鄰接矩陣；aij用來刻畫節(jié)點(diǎn)之間的連通情況，aij=1 表示節(jié)點(diǎn)ni和nj之間有邊相連，aij=0 表示節(jié)點(diǎn)ni和nj之間無邊相連，只有借助其他節(jié)點(diǎn)轉(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 個(gè)方面：1）如何定義一個(gè)社團(tuán)；2）如何判定劃分結(jié)果的優(yōu)劣；3）如何在一個(gè)合理的劃分標(biāo)準(zhǔn)下，設(shè)計(jì)一種高效的劃分算法。

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

基于上述原因，NEWMAN 等［18］在GN 算法的基礎(chǔ)上提出一種快速算法——FN（Fast-Newman）。FN算法繼承了貪心算法的思想，從所有節(jié)點(diǎn)各自作為一個(gè)社團(tuán)開始，沿著使模塊度Q增大最多或減小最少的方向不斷合并社團(tuán)，直至整個(gè)網(wǎng)絡(luò)都合并為一個(gè)社團(tuán)。由于FN 算法需要在每輪合并過程中遍歷有邊相連的社團(tuán)并計(jì)算模塊度增量，這一過程的復(fù)雜度為O（m）（m為網(wǎng)絡(luò)中邊的數(shù)量），并且在合并完成后還需要更新社團(tuán)結(jié)構(gòu)，這一過程的復(fù)雜度為O（n），因此每輪合并的復(fù)雜度為O（m+n）。又因?yàn)镕N 算法最多需要合并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的計(jì)算公式［19］如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

將T分解為通信時(shí)間Tc和驗(yàn)證時(shí)間Tv，則式（13）可以表示如下：

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

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

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

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

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

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

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

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

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

3.1 性能分析

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

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

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

圖7 分片時(shí)間對比Fig.7 Comparison of the sharding times

從圖8 可以看出：當(dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)不超過100時(shí)，2 種算法的分片結(jié)果Q值相同，再次印證了對于節(jié)點(diǎn)數(shù)不超過100 的小規(guī)模網(wǎng)絡(luò)，改進(jìn)的FN 算法等同于原始FN 算法；當(dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)超過100 時(shí)，改進(jìn)FN 算法的分片結(jié)果Q值圍繞原始FN 算法的分片結(jié)果Q值在不超過0.1 的范圍內(nèi)波動(dòng)。這是因?yàn)楦倪M(jìn)的FN 算法在繼承原始FN 算法最大化Q值思想的同時(shí)，也不可避免地繼承了原始FN 算法只能選取局部最優(yōu)解的特性（根據(jù)2.1 節(jié)的描述，算法在合并過程中的某幾輪可能會使Q值減?。W(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 算法相比時(shí)高時(shí)低，但2 種算法的Q值差距很小，且2 種算法的Q值均在正常范圍內(nèi)。

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

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

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

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

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

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

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

從圖10 可以看出，當(dāng)同一個(gè)網(wǎng)絡(luò)被分為不同分片時(shí)，各分片由最小深度生成樹算法選取的主節(jié)點(diǎn)的生成樹深度與分片數(shù)成反比。這是因?yàn)閷?shí)驗(yàn)為控制變量，假設(shè)每個(gè)分片的規(guī)模相同（包含的節(jié)點(diǎn)數(shù)相同）。分片數(shù)越多，每個(gè)分片的規(guī)模越小，由最小深度生成樹算法選取的主節(jié)點(diǎn)的生成樹深度就越淺?；诖?，LSchain 可以根據(jù)工業(yè)互聯(lián)網(wǎng)平臺層的業(yè)務(wù)需求動(dòng)態(tài)地劃分邊緣層區(qū)塊鏈網(wǎng)絡(luò)：當(dāng)網(wǎng)絡(luò)負(fù)載大時(shí)，將網(wǎng)絡(luò)分為更多的片，以優(yōu)先滿足吞吐量需求；當(dāng)網(wǎng)絡(luò)負(fù)載小時(shí)，將網(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é)點(diǎn)的生成樹深度就越淺。這是因?yàn)檫B通圖（任意兩個(gè)節(jié)點(diǎn)都有邊相連的網(wǎng)絡(luò)）的生成樹深度具有理論上下限。節(jié)點(diǎn)數(shù)量為n的全局耦合網(wǎng)絡(luò)僅需1 跳即可到達(dá)網(wǎng)絡(luò)中的任意位置，這種網(wǎng)絡(luò)的生成樹深度恒為1，連通性最好；任一節(jié)點(diǎn)數(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é)點(diǎn)角色的各邊緣服務(wù)器可能會遭到惡意攻擊，從而影響系統(tǒng)的正常運(yùn)行。本節(jié)主要從LSchain 協(xié)議能夠抵御單分片接管攻擊和主節(jié)點(diǎn)自私攻擊兩方面進(jìn)行說明。

3.2.1 單分片接管攻擊抵御

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

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

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

4 結(jié)束語

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