摘 要：分片機制是解決區(qū)塊鏈吞吐量低和通信復雜度高等性能瓶頸問題的一種途徑。然而在現(xiàn)有的分片系統(tǒng)中，分片之間的交易可以并行處理，這樣會不可避免地出現(xiàn)頻繁的跨分片交易，相比于片內(nèi)交易，跨分片交易會增加確認時間。當系統(tǒng)中跨分片交易增多時會導致分片系統(tǒng)效率降低。提出了一種動態(tài)分片自適應模型，用于提高區(qū)塊鏈平臺的吞吐率和效率。將通過交易數(shù)據(jù)相關(guān)性動態(tài)地將數(shù)據(jù)拆分到同一個分片，同時將多個高度相關(guān)的分片自適應地合并到同一個分片當中。為了驗證區(qū)塊鏈動態(tài)分片自適應模型，使用超級賬本對區(qū)塊鏈動態(tài)分片自適應模型進行實驗。實驗結(jié)果表明所提出的模型可以提升區(qū)塊鏈分片系統(tǒng)的可擴展性，同時保證安全性以及一致性問題。

關(guān)鍵詞：區(qū)塊鏈；動態(tài)分片；節(jié)點聚類；智能合約；可擴展性；超級賬本

中圖分類號：TP311.1 文獻標志碼：A 文章編號：1001-3695（2024）11-004-3231-08

doi：10.19734/j.issn.1001-3695.2024.03.0069

Dynamic sharding adaptive model for blockchain

Zhai Sheping^{a， b}， Liu Jiayiteng^a?， Yang Rui^a， Zhu Pengju^a

（a.School of Computer Science， b.Shaanxi Key Laboratory of Network Data Analysis amp; Intelligent Processing， Xi’an University of Posts amp; Telecommunications， Xi’an 710121， China）

Abstract：Sharding mechanism is a way to address performance bottlenecks in blockchain such as low throughput and high communication complexity. However， in existing sharding systems， transactions across shards can be processed in parallel， inevitably leading to frequent cross-shard transactions which increase confirmation times compared to intra-shard transactions. As the number of cross-shard transactions increases， the efficiency of the sharding system decreases. This paper proposed a dynamic sharding adaptive model to enhance the throughput and efficiency of blockchain platforms. By dynamically splitting data into the same shard based on transaction data correlation， multiple highly correlated shards were adaptively merged into the same shard. To validate the dynamic sharding adaptive model for blockchain， it conducted experiments using Hyperledger. Experimental results demonstrate that the proposed model can enhance the scalability of blockchain sharding systems while ensuring security and consistency.

Key words：blockchain; dynamic sharding; node clustering; smart contracts; scalability; Hyperledger Fabric

0 引言

區(qū)塊鏈利用對等（peer-to-peer，P2P）分布式網(wǎng)絡(luò)、基于鏈的數(shù)據(jù)結(jié)構(gòu)、密碼學、共識算法等一系列技術(shù)機制來達到創(chuàng)建信任的目的^［1］。隨著新一輪產(chǎn)業(yè)革命的興起，區(qū)塊鏈技術(shù)在物流、法律、新基建等領(lǐng)域廣泛應用，在醫(yī)療健康等產(chǎn)業(yè)也扮演日益重要的角色^［2］。區(qū)塊鏈的去中心化特性和分布式共識機制導致了交易處理速度和效率的限制。傳統(tǒng)的中心化交易系統(tǒng)可以通過集中式的處理和控制，更快地完成大量交易，而區(qū)塊鏈網(wǎng)絡(luò)需要在保證去中心化和安全性的前提下，通過復雜的共識算法和分布式網(wǎng)絡(luò)來驗證和記錄每一筆交易，這導致了處理速度的明顯下降。因此區(qū)塊鏈的吞吐量遠低于傳統(tǒng)的中心化交易系統(tǒng)。怎樣提高區(qū)塊鏈性能成為一個重要的研究方向。分片方案通常被視為一種“安全地適應開放網(wǎng)絡(luò)中節(jié)點狀態(tài)變化的可持續(xù)擴展性能”的方案，分片是通過改變網(wǎng)絡(luò)內(nèi)部各步驟之間的驗證方式來提高區(qū)塊鏈可擴展性的一種方法，其核心思想是“化整為零”，將區(qū)塊鏈網(wǎng)絡(luò)劃分成若干個能夠處理交易的較小組件式網(wǎng)絡(luò)，以達到較高的交易處理速度。在區(qū)塊鏈分片系統(tǒng)中，賬本數(shù)據(jù)拆分并分布到各分片。各分片只處理相關(guān)數(shù)據(jù)的交易，借助基于分片的并行處理，提升網(wǎng)絡(luò)容量。在應用分片策略時，必須滿足以下屬性：a）安全性；b）可擴展性；c）一致性；d）互操作性^［3］。

然而，現(xiàn)有的分片方案大多數(shù)都采用預先定義的靜態(tài)分片規(guī)模。區(qū)塊鏈被認為是一個去中心化、無須許可的系統(tǒng)^［4］，這意味著網(wǎng)絡(luò)中的節(jié)點狀態(tài)和網(wǎng)絡(luò)規(guī)模隨時都在發(fā)生著變化。當網(wǎng)絡(luò)在短時間內(nèi)發(fā)生較大規(guī)模的變動時，利用靜態(tài)分片規(guī)模的區(qū)塊鏈網(wǎng)絡(luò)會因為系統(tǒng)不能及時調(diào)整分片狀態(tài)而導致區(qū)塊鏈系統(tǒng)利用率降低^［5］。無法達到提升區(qū)塊鏈系統(tǒng)性能的設(shè)計目的。另一方面，在區(qū)塊鏈網(wǎng)絡(luò)中的節(jié)點數(shù)短時間內(nèi)大幅減少的情況下，預先設(shè)定分片規(guī)模也會增加分片內(nèi)的安全隱患。最后，預先設(shè)定分片規(guī)模的靜態(tài)分片方案，未來需要擴展分片網(wǎng)絡(luò)規(guī)模時，只能采用時延較長、成本較高的硬分叉方式，這使得系統(tǒng)更新更為困難、代價更大。因此將分片動態(tài)拆分和合并的動態(tài)分片網(wǎng)絡(luò)成為分片技術(shù)研究的重點。對比于預先定義的靜態(tài)分片方法，Zhou等人^［6］提出了一種在聯(lián)盟鏈中的基于隨機值的動態(tài)分片協(xié)議，它改進了聯(lián)盟鏈中靜態(tài)分片的安全性風險，但并未對跨分片事務(wù)作出具體的處理。Skychain^［7］提出了一種自適應賬本協(xié)議，以保證基于動態(tài)分片策略的賬本能夠有效地合并或拆分。然后為了在高維系統(tǒng)狀態(tài)的動態(tài)環(huán)境下優(yōu)化分片策略，提出了一種基于深度強化學習的動態(tài)分片區(qū)塊鏈框架，以解決節(jié)點加入、退出和惡意攻擊等動態(tài)環(huán)境下的問題，但由于通信復雜度過高導致系統(tǒng)利用效率低的問題并沒有解決。Xi等人^［8］為了解決大規(guī)模協(xié)作物聯(lián)網(wǎng)中信任問題，以及高比例的跨碎片交易會嚴重限制去中心化區(qū)塊鏈的性能，提出了HMMDShard，這是一種基于隱馬爾可夫模型（hidden Markov model，HMM）的動態(tài)區(qū)塊鏈分片方案，通過集成HMM，實現(xiàn)了區(qū)塊鏈碎片的自適應動態(tài)增量更新，有效減少了所有高比例的跨碎片交易。但文章內(nèi)容并未解決當網(wǎng)絡(luò)狀態(tài)發(fā)生變化時應如何動態(tài)地調(diào)整分片狀態(tài)。Sun等人^［9］提出了一種新的適用于區(qū)塊鏈的分片協(xié)議，減少了跨分片事務(wù)的影響，提高了系統(tǒng)性能。分片協(xié)議采用了有向無環(huán)圖賬本，實現(xiàn)了并行交易處理，并采用了動態(tài)交易確認共識以簡化操作。該協(xié)議的分片過程和節(jié)點評分機制可以阻止惡意行為。盡管有向無環(huán)圖賬本可以提供更快的交易確認速度和更好的可擴展性，但隨著網(wǎng)絡(luò)規(guī)模的增長，節(jié)點間的交互和數(shù)據(jù)傳輸可能會成為瓶頸，影響系統(tǒng)的整體性能和擴展性。Zhang等人^［10］提出了一種基于信譽的分片動態(tài)重組網(wǎng)絡(luò)分片方案，該方案將節(jié)點性能和行為特征集成到信譽計算中，同時添加替代領(lǐng)導者以保持分片系統(tǒng)的穩(wěn)定性。然而該方法并未對具有交易數(shù)據(jù)相關(guān)性的跨分片交易進行分析處理。Cai等人^［11］提出了SmartChain，一個動態(tài)自適應的分片框架，用于在具有動態(tài)性和異構(gòu)性的物聯(lián)網(wǎng)區(qū)塊鏈上進行分片決策。SmartChain可以根據(jù)當前狀態(tài)自適應地動態(tài)選擇碎片數(shù)量、分區(qū)結(jié)構(gòu)和主選擇模式。但SmartChain未對碎片分片進行合并，這樣會導致跨分片交易數(shù)量增多，導致系統(tǒng)利用率降低。

因此，針對現(xiàn)有方案中存在的問題，本文設(shè)計一種自適應的網(wǎng)絡(luò)動態(tài)分片方案，支持區(qū)塊鏈應用于更多領(lǐng)域和中心化服務(wù)器進行競爭，解決區(qū)塊鏈平臺必須性能瓶頸問題，提高區(qū)塊鏈系統(tǒng)的性能，增加系統(tǒng)的吞吐量（transactions per second，TPS），支持大規(guī)模用戶場景和高效的數(shù)據(jù)交互。

本文的主要貢獻如下：

a）設(shè)計了一種動態(tài)分片委員會方案。考慮分片利用率的分片合并與拆分，為了充分發(fā)揮分片的并行性，基于分片之間的關(guān)聯(lián)，通過動態(tài)分片委員會對分片進行動態(tài)的合并與拆分。設(shè)計一種具有追溯功能的智能合約實現(xiàn)動態(tài)分片組織中歷史數(shù)據(jù)的跟蹤。

b）為了實現(xiàn)跨分片事務(wù)的并行處理，采取了數(shù)據(jù)重定位的策略，將多個高度相關(guān)的數(shù)據(jù)分配至同一分片。這種方法有效地減少了跨分片交易的頻率，實現(xiàn)了負載均衡機制，保證分片內(nèi)交易在整個分片網(wǎng)絡(luò)中均勻分布。在提高系統(tǒng)性能的同時，有效降低了跨分片事務(wù)的復雜性和開銷。

c）設(shè)計了一種節(jié)點聚類方法，該方法可快速達成交易提案的共識，通過考慮節(jié)點間的網(wǎng)絡(luò)延遲對分片節(jié)點進行適當分片組聚類，減少每個分片中的共識延遲。因此，分片之間的交易速率處理得到了提升，從而提高了動態(tài)分片系統(tǒng)的吞吐量，提升系統(tǒng)的可擴展性。

1 相關(guān)知識

1.1 區(qū)塊鏈分片項目

1）Elastico

Elastico^［12］是2016年SIGSAC會議上提出的第一個為公有鏈設(shè)計的分片協(xié)議，網(wǎng)絡(luò)中的節(jié)點需要運行PoW（proof of work，工作量證明）機制來進行身份確認，節(jié)點分配到分片中是隨機的，每個分片內(nèi)部運行的是基于PBFT（practical Byzantine fault tolerance，實用拜占庭容錯）的共識算法，區(qū)塊鏈網(wǎng)絡(luò)中的通信復雜度隨著節(jié)點數(shù)的增加而增加。Elastico并沒有固定地預設(shè)分片規(guī)模大小，而是根據(jù)網(wǎng)絡(luò)的需求來調(diào)整分片的大小。這種調(diào)整可以根據(jù)當前網(wǎng)絡(luò)流量、參與者數(shù)量以及其他因素來自適應地進行。然而當一個Elastico系統(tǒng)被確定之后，系統(tǒng)就會成為固定的分片大小，并沒有考慮到發(fā)生網(wǎng)絡(luò)狀態(tài)變化時系統(tǒng)應如何對系統(tǒng)分片進行調(diào)整。

2）Rapidchain

Rapidchain^［13］在初始階段基于隨機數(shù)值選舉出分片委員會，由該委員會的節(jié)點負責網(wǎng)絡(luò)分片，構(gòu)成一個個子網(wǎng)絡(luò)。在處理跨分片交易時，基于UTXO（unspent transaction output，未花費的交易輸出）模型，交易的哈希輸出值對應驗證交易的分片。該分片方案能有效提升區(qū)塊鏈系統(tǒng)的吞吐量，且顯著降低交易延遲，但是委員會內(nèi)部共識還是傳統(tǒng)的PBFT，通信復雜度依然很高。

3）Harmony

Harmony^［14］是一個區(qū)塊鏈平臺。Harmony利用分片方法實現(xiàn)可擴展性，允許多個分片鏈同時處理交易。其共識機制稱為有效權(quán)益證明（effective proof-of-stake，EPoS），旨在保持安全性同時提高能源效率。Harmony旨在為各種應用程序提供高吞吐量、低延遲和低成本的區(qū)塊鏈基礎(chǔ)設(shè)施。Harmony系統(tǒng)還采用跨分片協(xié)議的技術(shù)來促進不同分片之間的通信和交互，確保整個網(wǎng)絡(luò)的一致性和安全性。

1.2 共識算法

1）fastBFT

fastBFT^［15］是一種共識算法，旨在解決分布式系統(tǒng)中的拜占庭容錯問題。與傳統(tǒng)的拜占庭容錯算法相比，fastBFT（fast Byzantine fault tolerance，快速拜占庭容錯）通過精簡消息傳遞的數(shù)量和優(yōu)化節(jié)點之間的通信，實現(xiàn)了更高的性能。該算法采用了兩個關(guān)鍵的優(yōu)化策略，以提高共識的速度。首先，fastBFT引入了批處理機制，允許節(jié)點在一輪中處理多個提案，從而減少了通信的開銷。其次，通過合并準備和提交階段的消息，避免了不必要的通信往返，進一步提高了性能。通過這些創(chuàng)新性的優(yōu)化，fastBFT在實際應用中表現(xiàn)出更高的吞吐量和更低的延遲，使其成為分布式系統(tǒng)中高效而可靠的共識算法之一。

2）Paxos

Paxos^［16］是一種用于解決分布式系統(tǒng)中一致性問題的經(jīng)典共識算法，Paxos算法流程如圖1所示。其核心思想通過提議、承諾、接受和學習等階段，確保在節(jié)點故障、消息延遲等不可靠環(huán)境中，系統(tǒng)的節(jié)點能夠就提案達成一致。提議者向其他節(jié)點發(fā)送提案，其他節(jié)點回復承諾，表示接受高于當前提案編號的提案，最終節(jié)點學習到被接受的提案。Paxos的算法流程包括提議、承諾、接受和學習等步驟，通過這些步驟的交互，系統(tǒng)能夠保持一致性。在算法的設(shè)計中，每個節(jié)點兼具提議者、承諾者和學習者的角色，通過相互協(xié)作達成一致。

1.3 交易數(shù)據(jù)相關(guān)性

在一個具有分片的區(qū)塊鏈網(wǎng)絡(luò)中，會發(fā)生兩種類型的交易：分片內(nèi)交易和跨分片交易。分片內(nèi)事務(wù)可以通過一個分片獨立處理。然而跨分片交易事務(wù)必須使用兩個或多個分片進行處理，因為它們必須從多個分片中訪問數(shù)據(jù)。如果只發(fā)生分片內(nèi)交易，隨著區(qū)塊鏈網(wǎng)絡(luò)被拆分為額外的分片，整體網(wǎng)絡(luò)的容量逐漸增大。然而當存在分片網(wǎng)絡(luò)時，不可避免地會發(fā)生跨分片交易。當一個跨分片事務(wù)在多個分片間異步處理時，事務(wù)的原子性和隔離性受到威脅。交易數(shù)據(jù)相關(guān)性指的是區(qū)塊鏈上不同交易之間的關(guān)聯(lián)程度或依賴關(guān)系。具體來說，交易數(shù)據(jù)相關(guān)性可以分為兩個方面：

a）交易之間的邏輯關(guān)系。某些交易在執(zhí)行或處理時可能依賴于其他交易的狀態(tài)或結(jié)果。例如，在區(qū)塊鏈上進行資金轉(zhuǎn)賬，一筆轉(zhuǎn)賬交易可能需要檢查發(fā)送方賬戶的余額是否足夠支付，并在確認后才能執(zhí)行。這種依賴關(guān)系意味著一些交易必須在另一些交易之前或之后執(zhí)行，形成了交易之間的邏輯關(guān)系。

b）交易涉及相同資產(chǎn)或賬戶。一些交易可能涉及相同的資產(chǎn)或賬戶。例如，多筆交易都涉及同一個賬戶的資金轉(zhuǎn)移或狀態(tài)修改。這些交易之間存在關(guān)聯(lián)，因為它們都涉及同一組數(shù)據(jù)或資源的操作。

區(qū)塊鏈系統(tǒng)數(shù)據(jù)之間的相關(guān)性非常重要，因為它影響到交易處理的順序、并發(fā)性和數(shù)據(jù)分片的優(yōu)化策略。有效地處理交易數(shù)據(jù)相關(guān)性可以提高系統(tǒng)的效率和性能，減少不必要的數(shù)據(jù)傳輸和通信開銷。

2 動態(tài)分片系統(tǒng)

動態(tài)分片系統(tǒng)主要功能在于動態(tài)分片網(wǎng)絡(luò)，總體架構(gòu)如圖2所示，系統(tǒng)包括發(fā)起請求的用戶節(jié)點、動態(tài)分片委員會、動態(tài)分片監(jiān)測模塊、動態(tài)分片控制器以及多個分片節(jié)點組成。首先定義了區(qū)塊鏈網(wǎng)絡(luò)的故障模型以及拜占庭作惡模型。

在考慮參考節(jié)點的崩潰故障模型時，基于一個假設(shè)，即參考節(jié)點僅可能經(jīng)歷崩潰故障而不涉及合謀行為。這意味著參考節(jié)點不會共同進行任何破壞性操作。通常通過設(shè)定參考節(jié)點只包括那些具有最高聲譽或?qū)ο到y(tǒng)有高度利害關(guān)系的成員來證明這種假設(shè)的合理性。這樣的配置旨在確保在系統(tǒng)中擔任關(guān)鍵角色的參考節(jié)點是可信的，從而最大程度地減小崩潰故障的可能性，提高系統(tǒng)的可靠性和安全性。

對于分片節(jié)點的拜占庭故障模型，假設(shè)除了參考節(jié)點之外，所有的節(jié)點都可能受到拜占庭故障的影響。因此每個分片中的同伴節(jié)點可能表現(xiàn)出不可預測的行為，而這些行為有時可能無法被正確檢測。在拜占庭失效的情況下，拜占庭容錯（Byzantine fault tolerance，BFT）相似的共識模型變得至關(guān)重要，以確保在各個對等體之間維持一致的狀態(tài)。為了應對這一挑戰(zhàn)，引入了fastBFT共識協(xié)議，將其應用于每個分片，以提供對抗拜占庭故障的能力，確保系統(tǒng)整體的穩(wěn)健性和可信度。這種方法旨在有效應對分片網(wǎng)絡(luò)中的潛在不穩(wěn)定性，確保在面對不可靠節(jié)點時依然能夠達成共識，從而保障系統(tǒng)的正常運行。

在系統(tǒng)中，最重要的兩個模塊分別是動態(tài)分片監(jiān)測模塊和動態(tài)分片控制器模塊，這兩個模塊決定了分片的大小以及分片的屬性。動態(tài)分片監(jiān)測模塊通過用戶提交數(shù)據(jù)次數(shù)檢測網(wǎng)絡(luò)節(jié)點狀態(tài)，并測量每個分片的共識時延。之后動態(tài)分片委員會根據(jù)動態(tài)分片測量模塊的數(shù)據(jù)調(diào)整當前網(wǎng)絡(luò)分片屬性，再由分片控制器對分片進行合并以及拆分，并根據(jù)拆分后的狀態(tài)分配給不同的分片組織。在傳統(tǒng)區(qū)塊鏈當中賬本信息是固定的，通過哈希值可追溯到原始的區(qū)塊信息，但是在提出的動態(tài)分片系統(tǒng)中，區(qū)塊會被分割成很小的塊，區(qū)塊鏈的可追溯性和不可竄改性會被打破。為了解決這個問題，運用智能合約對分割區(qū)塊進行追溯，因此編寫并部署專門用于分片的智能合約，以持續(xù)向分片委員會保持數(shù)據(jù)的可追溯性。在所提出的區(qū)塊鏈系統(tǒng)中，采用Paxos共識模型，在假設(shè)參考節(jié)點成員不存在拜占庭故障的情況下，滿足安全性和活性要求。

動態(tài)分片中的分片處理流程如圖3所示，在分片分配過程中根據(jù)監(jiān)測模塊提交給分片委員的監(jiān)測數(shù)據(jù)信息，可以知道分片應當發(fā)往哪個分片組織。當分片委員會收到來自用戶的信息時，首先會檢查用戶請求信息，根據(jù)委員會判斷后轉(zhuǎn)發(fā)給負責的分片組織。當分片在組織內(nèi)達成共識后，將消息以及成員簽名信息返回給分片委員會。之后委員會根據(jù)返回的信息進行檢查，并根據(jù)分片組內(nèi)共識結(jié)果提交給提案用戶。

分片共識不是只存在于一個組內(nèi)，當發(fā)生跨分片提案時，分片委員會將分片共識分為準備階段和執(zhí)行階段，用來保證賬本一致性?？绶制灰琢鞒倘鐖D4所示，首先分片委員會檢查用戶請求信息，在準備階段，委員會向參與跨分片的所有分片組織發(fā)送準備消息，之后接收分片組返回的分片執(zhí)行準備結(jié)果。在執(zhí)行階段，分片委員會發(fā)送提交請求消息，并利用準備階段的結(jié)果完成對分片組內(nèi)的提交，之后委員會接收各個分片組返回的共識結(jié)果。當所有分片組織完成共識后，將共識結(jié)果提交給提案用戶。在處理跨分片操作時，區(qū)塊內(nèi)數(shù)據(jù)信息會被鎖定，此時無法進行其他的共識行為，雖然這樣的處理方式降低了可用性，但有效地保證了區(qū)塊的一致性問題。

2.1 動態(tài)分片算法

在這里定義一些符號來描述動態(tài)分片的算法流程。在提出動態(tài)分片算法之前首先定義委員會的數(shù)據(jù)塊，將提案用戶提交給委員會的數(shù)據(jù)分成塊，記為P_block，將用戶提案的數(shù)據(jù)總量表示為P_total，這樣每一個數(shù)據(jù)塊的大小為「P_total/P_block?。

用Q_k表示第k個分塊所屬的分片的索引，n表示當前網(wǎng)絡(luò)當中分片數(shù)量，由此可得出Q_k的范圍在［1，n］。用α表示交易量，s（t_i）表示分片交易的吞吐量，其中t_i表示在第i個分片中所需要的共識時延。

分片組之間的分配向量為

Q=（Q₁，Q₂，…，Q_k－1，Q_k，Q_Pblock）（1）

分片交易吞吐量為

s（t_i）=α/t_i（2）

要實現(xiàn)分片模型，首先應該測量出每個分片當中的數(shù)據(jù)處理量。g_i（Q）表示分片內(nèi)數(shù)據(jù)處理量。ΔT表示一個時隙，f（Q_k）表示第k個分組中數(shù)據(jù)的總量，也被表示為一個時隙內(nèi)產(chǎn)生數(shù)據(jù)訪問的次數(shù)。要實現(xiàn)k個分組被分配給第i個分片的時候，分片必須是固定的一個，這時可以用單位階躍函數(shù)（3）來實現(xiàn)分配策略。

h_i（Q_k）=1

if Q_k=i0

others （3）

以上定義可得分片內(nèi)數(shù)據(jù)處理量為

g_i（Q）=h₁（Q_k）×f（Q_k）+…+h_Pblock（Q_k）×f（Q_k）（4）

在一個時隙期間分片可處理的數(shù)據(jù)總量為

s（t_i）×ΔT（5）

其中：u_i（t_i，Q）表示第i個分片的利用率，由數(shù)據(jù)請求量和數(shù)據(jù)分片節(jié)點數(shù)據(jù)處理能力決定。φ表示系統(tǒng)固定參數(shù)，g^cro_i（Q）表示第i個分片中跨分片數(shù)據(jù)請求數(shù)量。F表示為第i個分片中數(shù)據(jù)處理效率，且效率處于（0，1）之間。

F=g_i（Q）－g^cro_i（Q）s（t_i）×ΔT（6）

第i個分片的利用率為

u_i（t_i，Q）=1－（1－min（1，F(xiàn)））^δ（7）

式（7）可以看出，由于分片的量的增加，導致分片的利用率會變低。因此提出動態(tài)分片的算法，其目標為在一個動態(tài)分片系統(tǒng)中確定每個動態(tài)分片的數(shù)量n、分片分配向量Q以及每個分片中的共識延遲t_i，用算法來提高系統(tǒng)的吞吐率，提高系統(tǒng)的可擴展性。

因此，在確定分片數(shù)量、分片分配向量以及每個分片中的共識時延的前提下，致力于提高分片系統(tǒng)的可擴展性?？紤]到系統(tǒng)安全性，可以根據(jù)分片系統(tǒng)和區(qū)塊節(jié)點數(shù)來設(shè)置安全閾值，N^max表示為最大安全閾值，n∈（1，N^max）。對于采用PBFT共識的網(wǎng)絡(luò)，PBFT算法是一種狀態(tài)機復制，每一個“節(jié)點”是一個副本，有一個主副本，其他全為從副本。f表示為惡意副本，n^node_i表示節(jié)點數(shù)量，f惡意副本可能會不發(fā)送消息，那么除去這f個惡意副本的消息也要達到2f+1的確認。因此必須有2f+1個正常副本才可以在f個惡意副本拒絕發(fā)送消息的情況下順利進行確認和整個流程。所以得出n^node_i節(jié)點數(shù)量應大于3f+1。

定義Fra表示整個系統(tǒng)中所有分片利用率之和：

Fra=∑ni=1u_i（t_i，Q）（8）

由此可得出分片最大數(shù)量為

arg max{Fra}（9）

這個定義依賴于三個變量即網(wǎng)絡(luò)當前分片數(shù)量n、分片組之間的分配向量Q以及每個分片當中的共識時延t_i。通過網(wǎng)絡(luò)當前分片數(shù)量n確定分片組之間的分配向量Q，由Q與共識時延t_i確定當前第i個分片的利用率，通過式（8）來計算出當前系統(tǒng)利用率之和，由式（9）arg max函數(shù)可得出當分片利用率最大時系統(tǒng)的分片數(shù)量，進而得出新的n值，由新的n值再一次執(zhí)行動態(tài)分片算法。當動態(tài)分片委員會進行分片時，分片中的對等節(jié)點數(shù)量會發(fā)生改變，節(jié)點內(nèi)的共識時延也會發(fā)生改變，故動態(tài)分片委員會能執(zhí)行動態(tài)分片和共識延遲確定過程。

2.2 具有追溯功能的智能合約

區(qū)塊鏈智能合約是一種基于區(qū)塊鏈技術(shù)的自動執(zhí)行合同的機制，其本質(zhì)是一段以編程方式定義的、具有自動執(zhí)行能力的計算機代碼^［17］。當一個區(qū)塊被拆分成多個分片，或者多個分片合并成一個區(qū)塊時，不僅系統(tǒng)網(wǎng)絡(luò)結(jié)構(gòu)會發(fā)生改變，原始數(shù)據(jù)內(nèi)的歷史也無法被追蹤，這樣違背了區(qū)塊鏈系統(tǒng)可溯源的特性。因此需要設(shè)計一個動態(tài)分片網(wǎng)絡(luò)的智能合約，用來追蹤分片系統(tǒng)變化情況。當發(fā)生分片操作時，需要將分片后的結(jié)構(gòu)添加到分片委員會當中，用智能合約來使這些變化的分片被系統(tǒng)追蹤。如圖5所示為分片的智能合約設(shè)計圖。

圖6顯示智能合約在分片系統(tǒng)當中的應用流程，分片2中的分片通過數(shù)據(jù)塊賦值操作移動到分片1時，動態(tài)委員會通過調(diào)用智能合約創(chuàng)建包含兩個分片數(shù)據(jù)配置的操作。它是一種跨分片交易，應該在分片1和2中同時處理。跨分片交易處理完畢后，從分片2中刪除該分片中的所有數(shù)據(jù)，并將其添加到分片1中。當分片1中的分片與分片2中的分片合并時，動態(tài)委員會通過調(diào)用智能合約創(chuàng)建包含兩個分片組數(shù)據(jù)配置的操作，從而產(chǎn)生跨分片組操作。

2.3 分片控制器

分片委員會主要由動態(tài)分片監(jiān)測以及動態(tài)分片控制器組成。提出的系統(tǒng)需要確定分片數(shù)量n、分片分配向量Q及每個分片中的共識時延t_i。故這三個變量可以決策整個動態(tài)分片系統(tǒng)的效率。當動態(tài)分片過程發(fā)生后，分片中所需要的共識時延也是不斷變化。當k個分片需要合并成一個區(qū)塊時，系統(tǒng)會鎖定這k個分片。同時當發(fā)生一個區(qū)塊分成多個數(shù)據(jù)不相交的分片時，在各個分片組織內(nèi)部是不能共識其他分片組內(nèi)信息，這會導致系統(tǒng)效率變低。在分片當中如何界定分片類型對于系統(tǒng)是很重要的，因此問題可以總結(jié)為三點：

a）一個ΔT時隙后判斷系統(tǒng)共識時延，推選新的領(lǐng)導人；

b）經(jīng)過一個ΔT時隙系統(tǒng)中拜占庭節(jié)點過多時，分片委員會確定新的分片數(shù)量；

c）經(jīng)過一個ΔT時隙分片利用率降低時，分片委員會確定新分片的索引。

這三個問題分別對應著當分片進行共識過程時（問題2），當分片存在跨分片共識時（問題3），當共識時延高時或一個時隙過后重新選舉新的領(lǐng)導人（問題1），以下為分片控制流程偽代碼。

//初始化前一個時隙的分片利用率、節(jié)點數(shù)量和共識時延

a） utilization_previous=initial_utilization_value

b） node_count_threshold=3*f+1 /* 節(jié)點數(shù)量閾值，其中f是最大容忍的拜占庭節(jié)點數(shù) */

c） latency_previous=initial_latency_value

//定義動態(tài)分片控制器檢測流程函數(shù)

a） function dynamicShardingController（）：

//獲取當前時隙的分片利用率、節(jié)點數(shù)量和共識時延

a） current_utilization=getCurrentShardUtilization（）

b） current_node_count=getCurrentNodeCount（）

c） current_latency=getCurrentConsensusLatency（）

//檢查分片利用率是否小于前一個時隙的利用率

a） if current_utilization lt; utilization_previous：

b）

submitReportToCommittee（） //提交信息給分片委員會

//檢查節(jié)點數(shù)量是否小于節(jié)點數(shù)量閾值

j） if current_node_count lt; node_count_threshold：

k）

submitReportToCommittee（） //提交信息給分片委員會

//檢查共識時延是否小于前一個時隙的共識時延

l） if current_latency lt; latency_previous：

m）

submitReportToCommittee（） //提交信息給分片委員會

//更新前一個時隙的分片利用率、節(jié)點數(shù)量和共識時延

l） utilization_previous=current_utilization

m） byzantine_threshold=current_byzantine_nodes

n） latency_previous=current_latency

//主程序入口

l） while true：

m） dynamicShardingController（） //執(zhí)行動態(tài)分片控制器的檢測流程

n） sleep（T seconds） // 每隔T秒執(zhí)行一次檢測流程

2.4 分片組內(nèi)領(lǐng)導人選舉機制

在分布式系統(tǒng)中，PBFT多用于區(qū)塊鏈系統(tǒng)的領(lǐng)導者選舉過程，它需要在節(jié)點共識時交換節(jié)點全部信息以達成節(jié)點之間的共識，故PBFT節(jié)點為全節(jié)點共識。考慮到分片系統(tǒng)中拜占庭節(jié)點進行共識，所以必須考慮到參與共識節(jié)點之間的數(shù)量問題。

對于使用PBFT算法作為共識機制的區(qū)塊鏈系統(tǒng)，系統(tǒng)中最多可容納33%的拜占庭節(jié)點，一旦拜占庭節(jié)點超過了33%，那么就可以發(fā)起合謀攻擊，在區(qū)塊鏈系統(tǒng)上發(fā)布錯誤信息。因此每一個分片組織內(nèi)都需要更多非拜占庭節(jié)點來保持系統(tǒng)的安全性。但是當大量節(jié)點參與共識時，因為PBFT節(jié)點共識為全節(jié)點共識，需要交換大量的節(jié)點信息，這會導致系統(tǒng)的效率變低。故使用FastBFT算法來保證系統(tǒng)的效率和安全性質(zhì)，F(xiàn)astBFT算法是基于可信執(zhí)行環(huán)境TEE的拜占庭容錯算法，算法核心是提高分布式系統(tǒng)的性能和效率。該算法通過優(yōu)化消息復雜度和驗證過程，采用了聚合簽名技術(shù)^［18］，使得多個消息可以合并成一個相對較小的簽名。fastBFT的階段流程主要包括預準備階段（pre-processing）、預準備聚合階段（prepare）、提交階段（commit）和提交聚合階段（reply）。

在預準備階段（pre-processing），節(jié)點首先廣播預準備消息，表明其意圖參與下一輪的共識。接著，在預準備聚合階段（prepare），節(jié)點收到其他節(jié)點的預準備消息后，將這些消息聚合成一個單一的消息，并將其廣播給其他節(jié)點。這個聚合的過程有效地減少了通信開銷。一旦預準備階段完成，系統(tǒng)進入提交階段（commit）。節(jié)點廣播提交消息，表明其已經(jīng)收到足夠數(shù)量的相容的預準備消息。最后，在提交聚合階段（reply），節(jié)點收到其他節(jié)點的提交消息后，進行聚合，并將聚合后的提交消息廣播給其他節(jié)點。fastBFT通過這樣的流程有效地減少了消息傳遞和驗證的復雜性，從而提高了系統(tǒng)的整體性能。通過聚合簽名技術(shù)，節(jié)點之間的通信開銷減小，使得算法更適用于高吞吐量的分布式系統(tǒng)，同時仍能確保系統(tǒng)的安全性和拜占庭容錯特性。算法流程如圖7所示。

由圖7可以看出在fastBFT共識時延為領(lǐng)導者和對等節(jié)點之間的往返時間和節(jié)點簽名時間的總和。定義RTTs表示一個對等節(jié)點之間的信息往返時間，t_sig表示節(jié)點的簽名時間，RTT（L_rtts，p_rtts）表示領(lǐng)導者和對等網(wǎng)絡(luò)之間的往返時間。對等節(jié)點之間的往返時間可以通過它們之間交換一個小的控制消息來測量。

在動態(tài)分片系統(tǒng)當中，分片委員會通過網(wǎng)絡(luò)監(jiān)測模塊收集節(jié)點之間的信息往返時間，通過fastBFT的視圖轉(zhuǎn)換選出領(lǐng)導者。領(lǐng)導者節(jié)點應當滿足：

arg max{3×max［RTT（L_rtts，p_rtts）］+5×t_sig}（10）

若實際的共識延遲比預期的要長，則選舉一個新的領(lǐng)導者。其次，拜占庭節(jié)點可能會報告不同的網(wǎng)絡(luò)延時，而不是它們的實際延遲。因此，它應該與一些機制結(jié)合使用，例如，選舉、激勵機制和投票等行為防止節(jié)點作惡。

2.5 分片組聚類算法和區(qū)塊分片算法

上一節(jié)解決的領(lǐng)導人選舉機制，這一節(jié)解決分片委員會確定新的分片數(shù)量n以及分片委員會確定跨分片的索引Q_k問題，由此提出分片組聚類算法和區(qū)塊分片算法來解決。

當改變分片數(shù)量n時，假定在各個節(jié)點內(nèi)的共識延遲相差很小的情況下，可以排除分片中所需要的共識時延對系統(tǒng)的影響，因為現(xiàn)在趨于一個系統(tǒng)的固定值，所以可以定義新的分片最大數(shù)量求得公式?，F(xiàn)在影響分片最大數(shù)量的變量有分片數(shù)量n和分片分配向量Q。故需要解決n和Q的測量問題。

分片委員會通過用戶提交的提案在每個時隙內(nèi)周期性地測量每個分片組節(jié)點的相關(guān)性，f（Q_k）表示分片組節(jié)點的相關(guān)性?？梢酝ㄟ^分片控制器，用一個連通圖結(jié)構(gòu)的形式表達分片組節(jié)點以及不同分片組之間的相關(guān)性問題。如圖8所示。

f（Q_k）可以用G=（V，E）的形式來表達，其中V表示頂點，E表示邊。根據(jù)系統(tǒng)結(jié)構(gòu)定義了兩種邊的形式，分別是分片內(nèi)交易邊和跨分片交易邊。

在分片內(nèi)交易邊中，邊的兩個端點連接在同一個頂點V上，邊E的權(quán)重設(shè)置為在一個時隙內(nèi)用戶提交的提案中只需要訪問對應分片中數(shù)據(jù)的交易數(shù)。跨分片交易邊的兩個端點分別與兩個不同的頂點相連。它的權(quán)重設(shè)置為用戶在一個時隙期間提交的提案時，在邊緣兩端的兩個塊中需要訪問數(shù)據(jù)的交易數(shù)量。圖（a）表示為分片節(jié)點內(nèi)部交易以及跨分片交易的連通圖，圖（b）通過圖（a）跨分片的情況進行分片組的聚類以提高系統(tǒng)的效率。

K-means^［19］聚類可以解決分片組的聚類問題，通過迭代把數(shù)據(jù)對象劃分到不同的簇中，以求目標函數(shù)最小化，從而使生成的簇盡可能地緊湊和獨立。但是K-means聚類選擇初始質(zhì)心的時間復雜度為O（kⁿ），其中k是簇的數(shù)量，n是數(shù)據(jù)點（分片節(jié)點）的數(shù)量。但是提出的動態(tài)分配的算法需要較小的時間復雜度用來應對動態(tài)變化的網(wǎng)絡(luò)狀態(tài)，因此提出分片組聚類算法來應對快速變化的網(wǎng)絡(luò)環(huán)境，算法過程如算法1所示。

算法1 分片組聚類算法

輸入：節(jié)點樣本G，分片數(shù)量n。

輸出：分片組分配向量Q。

// 步驟1 確定分片數(shù)

a） if n未作為輸入?yún)?shù)給出

b） n為當前分片數(shù)量

c） end if

// 步驟2 生成分片組簇，并確定領(lǐng)導節(jié)點

d） 創(chuàng)建n集合{h₁，h₂，…，h_n}

e） 將頂點V中的所有分片移動到優(yōu)先級隊列V_P中，其中分片的優(yōu)先級由跨分片交易的權(quán)重之和決定

f） for each i屬于{h₁，h₂，…，h_n}

g） 從優(yōu)先級隊列V_P中選擇權(quán)重最小的分片

h） 將選中的分片添加到h_i當中

i） end for

// 步驟3 剩余的分片分配給分片組簇

g） for each Q_k屬于V_P

k） for each i屬于{h₁，h₂，…，h_n}

l）

計算h_i中第i個分片的利用率U_i（Q）

m）

計算h_i∪Q_k中第i個分片的利用率U_i（Q）_p

n） end for

o） 選擇最大的U_i（Q）和U_i（Q）_p

p） 將Q_k添加到所選分片組簇對應的集合中

q） end for

// 步驟4 確定分片組分配向量

r） for each i屬于{h₁，h₂，…，h_n}

s） for each Q_k屬于h_i

t）

把分片i賦給Q_k

u） end for

V） end for

通過改進K-means聚類，結(jié)合貪心法^［20］的改進節(jié)點集群的聚類，貪心法在每一步都作出局部最優(yōu)選擇而不考慮未來后果，貪心算法通常比較簡單，其時間復雜度可以做到線性級別，而且空間復雜度一般也比較低，滿足系統(tǒng)的要求。同時考慮到拜占庭節(jié)點作惡問題需要設(shè)計區(qū)塊分片算法用來確定分片數(shù)量，保證在一個安全閾值分片數(shù)，其思想是初始化一個拜占庭容錯的分片數(shù)量，根據(jù)分片組算法來確定分片的數(shù)量n以及分片分配向量Q，保證了系統(tǒng)的安全性。算法流程如算法2所示。分別對算法1和2進行特性分析與復雜性分析。

算法2 區(qū)塊分片算法

輸入：節(jié)點樣本G。

輸出：分片組分配向量Q以及分片數(shù)量n。

// 步驟1 初始化一個拜占庭容錯的分片數(shù)量

a） n=|∑n^presenti=1n^node_i3f+1| //n^present表示當前分片數(shù)量

// 步驟2 確定分片的數(shù)量n以及分片的分片向量Q

b） for each i∈{1，2，…，n_sh}

c） u_i=arg max{∑ni=1u_i（Q_one）}" //Q_one為算法一得出的分片向量

d） if igt;1 and u_ilt;u_i－1

e）

n=i－1

f）

Q=Q_one

g）

break

h） end if

i） if i=n_sh

g）

Q=Q^temp_i

k） end if

l） end for

1）算法1特性分析

a）分片組聚類。該算法在將節(jié)點樣本分配到不同的分片組中，以實現(xiàn)分布式數(shù)據(jù)處理和管理，使得系統(tǒng)能夠有效地處理大規(guī)模數(shù)據(jù)。

b）優(yōu)先級隊列。通過使用優(yōu)先級隊列，算法可以快速選擇權(quán)重最小的分片進行分配，以提高分配效率和系統(tǒng)的整體性能。

c）領(lǐng)導節(jié)點確定。通過分配過程確定每個分片組的領(lǐng)導節(jié)點，這些領(lǐng)導節(jié)點負責協(xié)調(diào)和管理分片組，保證系統(tǒng)的穩(wěn)定運行和高效管理。

d）利用率計算。通過計算分片的利用率，算法可以評估分片的分配效果，并根據(jù)實際情況優(yōu)化分片組的分配方案，以進一步提高系統(tǒng)的整體性能和資源利用率。

2）算法2特性分析

a）動態(tài)分片數(shù)量。該算法采用拜占庭容錯算法動態(tài)確定分片數(shù)量，以適應系統(tǒng)負載變化和故障情況，提高系統(tǒng)的容錯性能和穩(wěn)定性。

b）分片向量優(yōu)化。通過迭代過程確定最優(yōu)的分片向量，使得各個分片組之間的負載更加均衡，進而提高系統(tǒng)的整體性能和資源利用率。

3）復雜度分析

a）時間復雜度。算法1的時間復雜度取決于節(jié)點樣本數(shù)量n和分片數(shù)量k，以及優(yōu)先級隊列操作和利用率計算的復雜度，在算法中，需要對優(yōu)先級隊列進行操作，包括插入、刪除和查找操作。因此，算法1的時間復雜度可以表示為O（k×log（n）+k），其中l(wèi)og（n）是基于優(yōu)先級隊列的操作復雜度。雖然時間復雜度可能較高，但由于算法的簡單性，可以在系統(tǒng)中獲得較高的執(zhí)行效率。算法2時間復雜度主要由兩個部分組成：拜占庭容錯算法和分片向量優(yōu)化的迭代過程。拜占庭容錯算法的時間復雜度為O（n²），其中n是節(jié)點樣本的數(shù)量。分片向量優(yōu)化的迭代過程的時間復雜度取決于迭代次數(shù)和每次迭代的計算量，時間復雜度為O（m×k），其中m是迭代次數(shù)，k是分片數(shù)量。采用了拜占庭容錯算法動態(tài)確定分片數(shù)量，適應系統(tǒng)負載變化和故障情況，提高了系統(tǒng)的穩(wěn)定性和容錯性。

b）空間復雜度。算法1的空間復雜度主要取決于分片數(shù)量k，節(jié)點樣本數(shù)量n，分片組簇和優(yōu)先級隊列的存儲，以及輔助變量和數(shù)據(jù)結(jié)構(gòu)的存儲。算法1的空間復雜度可以表示為O（k+n）。算法1可以根據(jù)具體情況靈活調(diào)整分片數(shù)量和分配策略，適用于不同規(guī)模和需求的系統(tǒng)。算法2的空間復雜度主要取決于分片數(shù)量k，節(jié)點樣本數(shù)量n，分片向量的存儲，以及輔助變量和數(shù)據(jù)結(jié)構(gòu)的存儲。因此算法2的空間復雜度可以表示為O（k+n）。通過迭代過程確定最優(yōu)的分片向量，使得分片組之間的負載更加均衡，進一步提高了系統(tǒng)的整體性能和資源利用率。

3 模擬驗證

3.1 模型可行性分析

為了測試動態(tài)分片系統(tǒng)的可行性，在三個維度對模型進行實驗模擬分析：a）動態(tài)分片節(jié)點聚類共識；b）領(lǐng)導節(jié)點選舉實驗；c）分片分配策略實驗。用超級賬本區(qū)塊鏈性能基準框架超級賬本Caliper^［21］對吞吐量進行了測量。

3.1.1 分片節(jié)點聚類共識

通過NIST Net^［22］模擬框架，評估了動態(tài)分片節(jié)點共識時延的性能。在這項研究中，強調(diào)了節(jié)點間聚類對系統(tǒng)共識效率的影響。實驗測試了當5個分片時共識時延對吞吐率的影響，由圖9可以看出即使在分片交易未獲得確認的情況下，分片組內(nèi)的共識已經(jīng)完成。這突顯了動態(tài)分片系統(tǒng)在提高效率方面的能力，并為未來的系統(tǒng)優(yōu)化提供了保證。這項可行性分析強調(diào)了在區(qū)塊鏈網(wǎng)絡(luò)中聚焦于節(jié)點協(xié)同和聚類對性能優(yōu)化的關(guān)鍵作用。

3.1.2 領(lǐng)導者節(jié)點選舉

對領(lǐng)導者選舉進行了測試分析，結(jié)合fastBFT和貪心算法結(jié)合，實驗使用了5個對等節(jié)點進行區(qū)塊鏈網(wǎng)絡(luò)環(huán)境模擬，然后在一個ΔT時隙過后執(zhí)行更換領(lǐng)導者節(jié)點的行為。由圖10可以看出，有效利用領(lǐng)導者節(jié)點網(wǎng)絡(luò)狀態(tài)可以緩解系統(tǒng)共識延遲，對于提升整體交易吞吐量具有至關(guān)重要的作用。

3.1.3 分片分配策略

首先，對區(qū)塊大小在有分片的區(qū)塊鏈系統(tǒng)性能上的影響進行了深入分析。在提出的系統(tǒng)中，當區(qū)塊值減小時，每個數(shù)據(jù)塊的容量增加。圖11展示了在分片數(shù)量固定為24的情況下，區(qū)塊大小對分片總利用率的影響。當區(qū)塊較小時，即便采用區(qū)塊分片算法，精確控制分片利用率也變得困難。這可能導致部分分片利用不足或過度利用，進而對區(qū)塊鏈系統(tǒng)的交易處理速率產(chǎn)生影響。因此，合理選擇區(qū)塊值大小至關(guān)重要，以在系統(tǒng)性能和分片利用率之間找到平衡。這一研究強調(diào)了在設(shè)計具有分片的區(qū)塊鏈系統(tǒng)時需考慮的關(guān)鍵因素。

其次，分析分片組織算法對區(qū)塊鏈系統(tǒng)的影響。為評估區(qū)塊分片算法性能，停用了動態(tài)分片控制器中的分配策略模塊，將時隙固定為50 s。拜占庭節(jié)點的數(shù)量設(shè)置分別為1個、4個、8個和12個。在所提出的系統(tǒng)中，可創(chuàng)建的分片數(shù)量受拜占庭節(jié)點數(shù)量極大影響。增加一個分片中的拜占庭節(jié)點數(shù)量可能導致在該分片的節(jié)點間達不成共識。系統(tǒng)動態(tài)調(diào)整分片數(shù)量，考慮到拜占庭節(jié)點的預期數(shù)量。從圖12中清晰看出，隨著拜占庭節(jié)點數(shù)量的增加，吞吐量下降，這是由于分片數(shù)量無法增加。當拜占庭節(jié)點為1時，配置12個分片；相反，當拜占庭節(jié)點為12時，配置1個分片。這揭示了拜占庭節(jié)點對于分片動態(tài)調(diào)整和整體性能的重要影響。

3.2 實驗結(jié)果分析

在這一部分中，將提出的有分片的區(qū)塊鏈與現(xiàn)有的運行有分片組織的有分片的區(qū)塊鏈進行了比較。本實驗改進的算法將采用基于Golang進行開發(fā)，區(qū)塊鏈框架采用Hyperledger Fabric^［23］框架。在搭建基于Fabric的區(qū)塊鏈，首先要確保在至少多臺服務(wù)器上安裝了必要的基礎(chǔ)設(shè)施，包括Docker及其Compose工具、Go編程語言、Node.js、npm和Python 2.7。通過下載Hyperledger Fabric的示例文件夾并執(zhí)行相關(guān)命令，生成證書和創(chuàng)世塊，以確保網(wǎng)絡(luò)的安全性和節(jié)點身份驗證。為了驗證所提出的區(qū)塊鏈的性能，最初共創(chuàng)建了120 Byte來動態(tài)組織區(qū)塊鏈網(wǎng)絡(luò)，并在所有120 Byte上部署了可追溯智能合約。用戶節(jié)點可以通過動態(tài)分片委員會調(diào)用可追溯智能合約。

首先，實驗定義兩個分片網(wǎng)絡(luò)，分別是傳統(tǒng)分片網(wǎng)絡(luò)和分片分配網(wǎng)絡(luò)。傳統(tǒng)分片網(wǎng)絡(luò)考慮拜占庭節(jié)點，將區(qū)塊分割成多個分片，每個片段可以處理特定范圍內(nèi)的交易。根據(jù)分片順序分配給不同節(jié)點進行共識。分片分配網(wǎng)絡(luò)與傳統(tǒng)分片網(wǎng)絡(luò)一樣，都能將區(qū)塊劃分為多個分片。區(qū)別在于分片分配網(wǎng)絡(luò)可以根據(jù)跨分片次數(shù)權(quán)重進行排序分片操作，但在跨分片交易時候并沒有將有聯(lián)系的數(shù)據(jù)移動到同一個分片當中，會導致過多的跨分片交易事務(wù)的產(chǎn)生。

在所提出的動態(tài)分片區(qū)塊鏈網(wǎng)絡(luò)中使用了改進的共識機制進行領(lǐng)導人選舉，但傳統(tǒng)區(qū)塊鏈網(wǎng)絡(luò)以及傳統(tǒng)分片網(wǎng)絡(luò)并未對共識做優(yōu)化。為了比較區(qū)塊鏈系統(tǒng)的吞吐量以及分片利用率，將改進的共識機制同時應用于三個區(qū)塊鏈系統(tǒng)。為了能夠模擬動態(tài)分片系統(tǒng)中分片分裂過程的各種情況。本文進行了如下設(shè)置：設(shè)置系統(tǒng)內(nèi)有120 Byte，其中包括9個拜占庭節(jié)點，設(shè)置一個ΔT時隙為100 s，即每個ΔT時隙觸發(fā)動態(tài)分片委員會策略進行網(wǎng)絡(luò)分片合并操作。結(jié)果如圖13、14所示。

最初，所有區(qū)塊鏈系統(tǒng)在單一網(wǎng)絡(luò)中運行，未對其進行分區(qū)。因此，初始階段并未發(fā)生跨分片交易。系統(tǒng)吞吐量反映了區(qū)塊鏈網(wǎng)絡(luò)處理交易的能力。在傳統(tǒng)的分片網(wǎng)絡(luò)中，每100 s觸發(fā)一次分片組織模塊，將區(qū)塊鏈網(wǎng)絡(luò)分為12個分片。這一變化引發(fā)了跨分片交易的出現(xiàn)。雖然跨分片交易頻繁發(fā)生，但由于12個分片同時處理內(nèi)部交易，整體分片利用率提高。然而，隨著數(shù)據(jù)訪問頻率的波動，跨分片交易顯著增加，導致總體系統(tǒng)吞吐量和分片利用率下降。這種下降源于在區(qū)塊分配中未考慮區(qū)塊之間的相關(guān)性。在分片分配網(wǎng)絡(luò)中，系統(tǒng)每100 s將區(qū)塊分為12個分片，將每個區(qū)塊放入與之最相關(guān)的片段。盡管考慮了數(shù)據(jù)相關(guān)性，相較于傳統(tǒng)分片網(wǎng)絡(luò)，區(qū)塊鏈系統(tǒng)的吞吐量有所提升。然而不考慮分片利用率的區(qū)塊分配可能導致分片之間的利用率不平衡。由于區(qū)塊數(shù)量與數(shù)據(jù)量相等，動態(tài)將所有區(qū)塊分配到適當?shù)姆制兊美щy，可能限制動態(tài)分片系統(tǒng)的性能。

在所提出的動態(tài)分片區(qū)塊鏈系統(tǒng)中，分片組織和區(qū)塊分配算法每在100 s內(nèi)執(zhí)行一次?？紤]拜占庭節(jié)點數(shù)量，系統(tǒng)總共創(chuàng)建了12個分片，并在分片之間綜合考慮它們的關(guān)系，將區(qū)塊適當?shù)胤峙浣o這12個分片。通過圖15可以看出，相較于現(xiàn)有系統(tǒng)，整體利用率和吞吐量在所提出的區(qū)塊鏈系統(tǒng)中得到了提高。這是因為優(yōu)化的區(qū)塊分配最大程度地提高了系統(tǒng)利用率，同時減少了跨分片交易的發(fā)生。此外，由于系統(tǒng)能夠動態(tài)響應數(shù)據(jù)訪問頻率的變化，不會導致性能下降。與結(jié)合動態(tài)分片系統(tǒng)的分片網(wǎng)絡(luò)相比，可以清晰地看到利用率和吞吐率提高了64%以上。

之后，實驗比較當分片數(shù)量為2、8、12時的共識模型的共識延遲。根據(jù)共識模型比較吞吐量。在Paxos、PBFT和fastBFT中，共識領(lǐng)導者以隨機的方式選舉產(chǎn)生。相反，在所提出的共識協(xié)議中，領(lǐng)導者是考慮網(wǎng)絡(luò)狀態(tài)而當選的，因此在所提出的共識協(xié)議則有較小的共識時延。根據(jù)共識模型測量了每秒的交易吞吐量。為了響應跨分片交易發(fā)生的變化，實驗將計時器設(shè)置為100 s，觸發(fā)所提出的區(qū)塊分片算法。領(lǐng)導者選舉的計時器設(shè)置為20 s。這意味著領(lǐng)導人幾乎每一輪都是新當選的。其結(jié)果如圖16～18所示。

在實驗初始階段，頻繁的跨分片交易導致各種共識協(xié)議的低吞吐量。隨著時間推移，經(jīng)過一個時隙后，通過考慮交易關(guān)系并適當安排區(qū)塊，吞吐量在100 s后有所提高。共識延遲對吞吐量產(chǎn)生明顯影響。低共識延遲的共識模型在給定時間內(nèi)經(jīng)歷更多的共識輪次，在提出的共識協(xié)議中實現(xiàn)了最高吞吐量。增加分片數(shù)量的同時，比較了系統(tǒng)吞吐量?？梢钥闯觯诳绶制灰装l(fā)生率較低時，增加分片數(shù)量有助于提高系統(tǒng)吞吐量，因為多個分片可以同時處理更多獨立交易。因此，保持低跨分片交易發(fā)生率對于提高系統(tǒng)性能至關(guān)重要。

最后，本文使用共識協(xié)議ByzCoinX、PBFT和EPoS進行對比實驗。這分別是OmniLedger、Elastico和Harmony區(qū)塊鏈所采用的共識協(xié)議。

實驗比較了共識模型的共識延遲。在PBFT、ByzCoinX和EPoS中，共識領(lǐng)導者以隨機的方式或競爭方式選舉產(chǎn)生。相反，在所提出的共識協(xié)議中，領(lǐng)導者是考慮網(wǎng)絡(luò)狀態(tài)而當選的。如圖19所示，無論采用何種共識模型，隨著參與共識節(jié)點數(shù)量的增加，完成共識所花費的時間逐漸增加。結(jié)果表明，與ByzCoinX和EPoS相比，PBFT通常具有更長的共識延遲，因為PBFT中的每個節(jié)點與所有其他節(jié)點交換共識消息，即全對全消息交換。例外的是，當節(jié)點數(shù)小于5時，共識模型的共識延遲相差不大。這是因為當節(jié)點數(shù)目較少時，EPoS的消息復雜度O（n）與PBFT的消息復雜度O（n²）相差不大。圖20顯示，無論何時選出具有低網(wǎng)絡(luò)延遲的領(lǐng)導者，ByzCoinX和EPoS都具有低一致延遲的輪次。在ByzCoinX中，當具有低網(wǎng)絡(luò)延遲的對等體被放置在樹的第一個深度時，共識延遲會減少。因此，領(lǐng)導者的網(wǎng)絡(luò)狀態(tài)可以使共識延遲相差數(shù)百毫秒。具有低共識延遲的共識模型可以在給定的時間內(nèi)經(jīng)歷更多的共識輪數(shù)。因此，在提出的共識協(xié)議中實現(xiàn)了更低的共識時延，提高系統(tǒng)效率。

4 結(jié)束語

針對現(xiàn)有的分片方案不能及時調(diào)整分片的規(guī)模以適應鏈上環(huán)境中跨分片數(shù)量短時間內(nèi)的大幅變化，以及由此導致可擴展性和性能提升困難的問題，本文提出了一種動態(tài)分片自適應模型，該模型考慮到跨分片交易并發(fā)控制操作，分片數(shù)據(jù)之間的相關(guān)性，分片合并分割的利用率以及分片組之間的共識時延問題，提出了動態(tài)分片算法以及領(lǐng)導人選舉機制來解決以上問題。實驗結(jié)果表明，本文提出的動態(tài)分片自適應模型提高了系統(tǒng)的吞吐率以及可擴展性。本文模型還有很多地方需要進一步完善。例如模型中的參數(shù)，在面對不同的環(huán)境時是不一樣的，這與系統(tǒng)的安全性要求有關(guān)。另外本文考慮的是在節(jié)點數(shù)量一定的情況下進行動態(tài)分片，并未對整個系統(tǒng)的擴張和收縮進行討論，這些都是下一步的研究方向。

參考文獻：

［1］Nakamoto S. Bitcoin： a peer-to-peer electronic cash system ［EB/OL］. （2008）. https：//bitcoin.org/en/bitcoin-paper.

［2］袁勇， 王飛躍. 區(qū)塊鏈技術(shù)發(fā)展現(xiàn)狀與展望 ［J］. 自動化學報， 2016， 42（4）：481-49.（Yuan Yong， Wang Feiyue. The current status and prospects of blockchain technology development ［J］. Acta Automatica Sinica， 2016， 42（4）： 481-49.）

［3］Ren Yongjun， Liu Xinyu， Sharma P K， et al. Data storage mechanism of industrial IoT based on LRC sharding blockchain ［J］. Scientific Reports， 2023， 13（1）： 2746.

［4］王鋒， 張強， 劉揚， 等. 從擴展性角度看區(qū)塊鏈 ［J］. 計算機應用研究， 2023， 40（10）： 2896-2907.（Wang Feng， Zhang Qiang， Liu Yang， et al. Research progress of blockchain from perspective of scalability ［J］. Application Research of Computers， 2023， 40（10）： 2896-2907.）

［5］Liu Chuyi， Wan Jianxiong， Li Leixiao， et al. Throughput optimization for blockchain system with dynamic sharding ［J］. Electronics， 2023， 12（24）： 4915.

［6］Zhou Zhixuan， Qiu Zhijie， Yu Qiang， et al. A dynamic sharding protocol design for consortium blockchains ［C］// Proc of IEEE International Conference on Big Data. Piscataway，NJ：IEEE Press， 2020： 2590-2595.

［7］Zhang Jianting， Hong Zicong， Qiu Xiaoyu， et al. Skychain： a deep reinforcement learning-empowered dynamic blockchain sharding system ［C］// Proc of the 49th International Conference on Parallel Processing. 2020： 1-11.

［8］Xi Jinwen， Xu Guosheng， Zou Shihong， et al. A blockchain dynamic sharding scheme based on hidden Markov model in collaborative IoT ［J］. IEEE Internet of Things Journal， 2023，10（16）： 14896-14907.

［9］Sun Nigang， Li Junlong， Liu Yining， et al. A scalable sharding protocol based on cross-shard dynamic transaction confirmation for alliance chain in intelligent systems ［J］. International Journal on Semantic Web and Information Systems， 2023， 19（1）： 1-30.

［10］Zhang Shuhui，Tian Hanwen， Wang Lianhai， et al. A reputation-based dynamic reorganization scheme for blockchain network sharding ［J］. Connection Science， 2024， 36（1）： 2327438.

［11］Cai Ting， Chen Wuhui， Zhang Jianting， et al. SmartChain： a dynamic and self-adaptive sharding framework for IoT blockchain ［J］. IEEE Trans on Services Computing， 2024，17（2）： 674-688.

［12］Liu Xiaolong， Muhammad K， Lloret J， et al. Elastic and cost-effective data carrier architecture for smart contract in blockchain ［J］. Future Generation Computer Systems， 2019， 100： 590-599.

［13］Zamani M， Movahedi M， Raykova M. Rapidchain： scaling blockchain via full sharding ［C］// Proc of ACM SIGSAC Conference on Computer and Communications Security. New York：ACM Press， 2018： 931-948.

［14］Lai Ziliang， Liu C， Lo E. When private blockchain meets deterministic database ［C］// Proc of ACM on Management of Data. New York：ACM Press， 2023： 1-28.

［15］Liu Jian， Li Wenting， Karame G O， et al. Scalable Byzantine consensus via hardware-assisted secret sharing ［J］. IEEE Trans on Computers， 2018， 68（1）： 139-151.

［16］Lamport L. Paxos made simple ［J］. ACM SIGACT News （Distri-buted Computing Column）， 2001，32（4）： 51-58.

［17］歐陽麗煒， 王帥， 袁勇，等. 智能合約：架構(gòu)及進展 ［J］. 自動化學報， 2019， 45（3）： 445-457.（Ouyang Liwei， Wang Shuai， Yuan Yong， et al. Smart contracts： architecture and progress ［J］. Acta Automatica Sinica， 2019， 45（3）： 445-457.）

［18］Jalalzai M M， Niu Jianyu， Feng Chen， et al. Fast-hotstuff： a fast and robust BFT protocol for blockchains ［J］. IEEE Trans on Dependable and Secure Computing， 2023，21（4）： 2478-2493.

［19］Ahmed M， Seraj R， Islam S M S. The K-means algorithm： a comprehensive survey and performance evaluation ［J］. Electronics， 2020， 9（8）： 1295.

［20］Lu Chao， Zheng Jun， Yin Lyujiang， et al. An improved iterated greedy algorithm for the distributed hybrid flowshop scheduling problem ［J］. Engineering Optimization， 2023，152： 1-19.

［21］Choi W， Hong J W K. Performance evaluation of Ethereum private and testnet networks using Hyperledger caliper ［C］// Proc of the 22nd Asia-Pacific Network Operations and Management Symposium. Piscataway，NJ：IEEE Press， 2021： 325-329.

［22］Carson M， Santay D. NIST Net： a Linux-based network emulation tool ［J］. ACM SIGCOMM Computer Communication Review， 2003， 33（3）： 111-126.

［23］Androulaki E， Barger A， Bortnikov V， et al. Hyperledger Fabric： a distributed operating system for permissioned blockchains ［C］// Proc of the 13th EuroSys Conference. 2018： 1-15.