徐克圣 謝詔馳

摘 要：區(qū)塊鏈系統(tǒng)的通量嚴(yán)重不足，而解決此問(wèn)題最有效的一類方案是并行化處理，并行化方案主要為星型架構(gòu)，當(dāng)前星型架構(gòu)對(duì)系統(tǒng)中節(jié)點(diǎn)的分片方式多為賬戶隨機(jī)分片，這種分片方式的系統(tǒng)通量仍然不足。針對(duì)此問(wèn)題，提出了一種基于星型結(jié)構(gòu)的TKM分片算法，該算法將原始K-means聚類算法進(jìn)行改進(jìn)，并運(yùn)用在節(jié)點(diǎn)分片上。TKM分片算法將聚類算法與區(qū)塊鏈的網(wǎng)絡(luò)分片技術(shù)相結(jié)合，使節(jié)點(diǎn)根據(jù)地理位置進(jìn)行分片，極大提高鄰近節(jié)點(diǎn)發(fā)生的交易為片內(nèi)交易的概率，從而提高系統(tǒng)通量，同時(shí)在原始算法的基礎(chǔ)上引入了時(shí)間戳，減少了惡意節(jié)點(diǎn)的攻擊。仿真實(shí)驗(yàn)表明該算法與傳統(tǒng)的隨機(jī)分片算法相比，最大系統(tǒng)通量提高了20%。根據(jù)上述通量模型，通過(guò)實(shí)驗(yàn)得出基于TKM算法的星型區(qū)塊鏈系統(tǒng)的最優(yōu)分片數(shù)量。

關(guān)鍵詞：區(qū)塊鏈；星型架構(gòu)；分片算法；聚類算法；通量

中圖分類號(hào)：TP393.04?? 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695（2024）03-006-0683-05

doi：10.19734/j.issn.1001-3695.2023.06.0289

TKM sharding algorithm for star blockchain architecture

Xu Keshenga，Xie Zhaochib

（a.School of Software，b.School of Computer & Communication Engineering，Dalian Jiaotong University，Dalian Liaoning 116021，China）

Abstract：

The throughput of blockchain systems is severely insufficient，and the most effective solution to this problem is parallelization processing.The parallelization scheme is mainly a star architecture.Currently，the star architecture mostly uses account random sharding for node sharding in the system，and the system throughput of this sharding method is still insufficient.In response to this issue，this paper proposed a TKM sharding algorithm based on star structure，which improved the original K-means clustering algorithm and applied it to node sharding.The TKM sharding algorithm combined clustering algorithm with blockchain network sharding technology，allowing nodes to be sharded based on geographical location，greatly increasing the probability of transactions between neighboring nodes being intra chip transactions，thereby improving system throughput.At the same time，it introduced time stamps on the basis of the original algorithm to reduce attacks from malicious nodes.Simulation experiments show that this algorithm improves the maximum system throughput by 20% compared to traditional random sharding algorithms.Based on the above flux model，the optimal number of shards for the star blockchain system based on the TKM algorithm is obtained through experiments.

Key words：blockchain；star architecture；sharding algorithm；clustering algorithm；throughput

自2008年比特幣［1］提出以來(lái)，區(qū)塊鏈技術(shù)受到廣泛的關(guān)注，區(qū)塊鏈技術(shù)已經(jīng)從最初的數(shù)字貨幣領(lǐng)域發(fā)展到面對(duì)面實(shí)時(shí)支付、數(shù)字資產(chǎn)交易、物聯(lián)網(wǎng)等日常領(lǐng)域。區(qū)塊鏈雖然具有高安全性，但通量嚴(yán)重不足，無(wú)法滿足現(xiàn)實(shí)需求，也限制了其進(jìn)一步擴(kuò)展應(yīng)用領(lǐng)域。通量是判斷區(qū)塊鏈系統(tǒng)性能的指標(biāo)之一，通量也為吞吐量（transactions per second，TPS），同時(shí)也是區(qū)塊鏈技術(shù)當(dāng)前的瓶頸之一。目前主流的公鏈系統(tǒng)如比特幣、以太坊［2］的通量處于101，聯(lián)盟鏈系統(tǒng)超級(jí)賬本［3，4］普遍處于102，與中心化支付系統(tǒng)微信錢包與支付寶最高可承載105的數(shù)量級(jí)相差甚遠(yuǎn)。中心化系統(tǒng)處理交易的速度遠(yuǎn)超區(qū)塊鏈系統(tǒng)，若想將區(qū)塊鏈技術(shù)運(yùn)用在更廣泛的日常生活中，提高區(qū)塊鏈系統(tǒng)通量就成為了一個(gè)迫切需求。

分片技術(shù)是當(dāng)前解決通量問(wèn)題的常用方法之一，其原理是將系統(tǒng)中節(jié)點(diǎn)按照一定規(guī)則進(jìn)行分片，每個(gè)分片獨(dú)立且并發(fā)地處理交易，從而提高系統(tǒng)通量。近年來(lái)，區(qū)塊鏈系統(tǒng)的分片方案層出不窮，這些方案主要分為將主鏈作為中轉(zhuǎn)的星型架構(gòu)（Polkadot［5］、以太坊2.0［6］等）和分片之間直接交互的平行架構(gòu)（Omniledger［7］、Chainspace［8］、Monoxide［9］等）兩類。本文主要是針對(duì)星型架構(gòu)進(jìn)行研究及實(shí)驗(yàn)。星型架構(gòu)與平行架構(gòu)相比，著重于主鏈節(jié)點(diǎn)的功能復(fù)雜度，主鏈的功能復(fù)雜度的不同會(huì)影響系統(tǒng)通量峰值以及系統(tǒng)最優(yōu)分片數(shù)。分片數(shù)為最優(yōu)分片數(shù)時(shí)，系統(tǒng)中的跨片交易與片內(nèi)交易達(dá)到最優(yōu)平衡，在這種狀態(tài)下跨片交易產(chǎn)生的額外通信開銷不會(huì)破壞分片技術(shù)帶來(lái)的擴(kuò)容效果。

本文的主要貢獻(xiàn)如下：

a）本文將聚類算法與分片規(guī)則結(jié)合，提出了基于星型架構(gòu)的TKM分片算法。通過(guò)此分片規(guī)則可以極大提高鄰近節(jié)點(diǎn)之間的交易為片內(nèi)交易的概率，更快地同步至主鏈，提高系統(tǒng)通量。

b）對(duì)星型架構(gòu)中的區(qū)塊鏈通量與分片數(shù)量的關(guān)系進(jìn)行推導(dǎo)，建立星型架構(gòu)模型，得出分片數(shù)量與系統(tǒng)通量不成正比，系統(tǒng)存在一個(gè)通量峰值，該峰值對(duì)應(yīng)著最優(yōu)分片數(shù)。在最優(yōu)分片數(shù)前，通量隨分片數(shù)增加會(huì)穩(wěn)定增長(zhǎng)，在最優(yōu)分片數(shù)后，通量會(huì)隨分片數(shù)增加而緩慢下降，最后保持不變。

1 相關(guān)研究

1.1 區(qū)塊鏈技術(shù)

區(qū)塊鏈系統(tǒng)是多種技術(shù)融合在一起的成果，其中包括P2P通信、密碼學(xué)、智能合約、分布式存儲(chǔ)等。區(qū)塊鏈具有分布式、去中心化、強(qiáng)魯棒性、不可竄改等優(yōu)點(diǎn)，每個(gè)節(jié)點(diǎn)共同組成一個(gè)大的P2P網(wǎng)絡(luò)，其中交易的合法性由共識(shí)機(jī)制和數(shù)字簽名保證，區(qū)塊間通過(guò)一條哈希鏈進(jìn)行連接，賬本由網(wǎng)絡(luò)中所有節(jié)點(diǎn)共同維護(hù)。

區(qū)塊鏈的發(fā)展分為三個(gè)階段。第一階段是比特幣的產(chǎn)生，其應(yīng)用范圍完全聚集在數(shù)字貨幣上，構(gòu)建了一種全新的、去中心化的數(shù)字支付系統(tǒng)。第二階段的標(biāo)志是將“智能合約”的概念引入到區(qū)塊鏈中，有了智能合約的加入，增強(qiáng)了區(qū)塊鏈系統(tǒng)的安全性，其應(yīng)用范圍開始向金融領(lǐng)域蔓延。第三階段，人們企圖利用區(qū)塊鏈技術(shù)顛覆互聯(lián)網(wǎng)的底層協(xié)議，于是區(qū)塊鏈技術(shù)被逐漸應(yīng)用到公證、審計(jì)、物流、醫(yī)療等領(lǐng)域［10］，最后應(yīng)用領(lǐng)域擴(kuò)大至整個(gè)社會(huì)。

1.2 性能瓶頸

區(qū)塊鏈性能的兩個(gè)主要指標(biāo)分別是通量和時(shí)延，通量即固定時(shí)間處理的交易數(shù)，時(shí)延是交易處理的響應(yīng)時(shí)間。通量和時(shí)延兩者對(duì)立相向，只考慮通量會(huì)造成交易響應(yīng)時(shí)間過(guò)長(zhǎng)，影響客戶體驗(yàn)，只考慮時(shí)延會(huì)造成交易排隊(duì)。

a）通量。系統(tǒng)通量不足是目前區(qū)塊鏈有待攻克的技術(shù)瓶頸之一，當(dāng)前主流的公有鏈系統(tǒng)（比特幣、以太坊）的系統(tǒng)通量與中心化系統(tǒng)相差甚遠(yuǎn)。目前主流的提高系統(tǒng)通量的方案就是分片技術(shù)。

b）時(shí)延。區(qū)塊鏈交易存在延遲，在去中心化系統(tǒng)中以下原因會(huì)影響交易時(shí)延：（a）區(qū)塊鏈leader節(jié)點(diǎn)出塊時(shí)間；（b）主鏈的功能復(fù)雜度；（c）區(qū)塊存儲(chǔ)交易的上限數(shù)量。

本文主要針對(duì)區(qū)塊鏈系統(tǒng)通量不足的問(wèn)題進(jìn)行研究與改進(jìn)。

1.3 分片技術(shù)

分片技術(shù)作為提高區(qū)塊鏈系統(tǒng)通量的主流方案［11］，近年來(lái)不斷更新迭代，各種分片規(guī)則層出不窮。區(qū)塊鏈分片技術(shù)主要分為無(wú)許可鏈和許可鏈兩種，前者是分片技術(shù)的主流方式。普遍的分片方案就是以太坊2.0應(yīng)用的，以星型架構(gòu)方式按照賬戶地址前6位將賬戶隨機(jī)地分到分片中的方案。表1是對(duì)近年來(lái)區(qū)塊鏈分片技術(shù)的歸納。表1中的符號(hào)含義如下：［a］表示每個(gè)分片100個(gè)節(jié)點(diǎn)，共16個(gè)分片；［b］表示每個(gè)分片鏈900個(gè)節(jié)點(diǎn)共60個(gè)分片，主鏈900個(gè)節(jié)點(diǎn)；［c］表示每個(gè)分片4個(gè)節(jié)點(diǎn)共5個(gè)分片；［d］表示共972個(gè)節(jié)點(diǎn)，分為36個(gè)分片；［e］表示每個(gè)分片36個(gè)節(jié)點(diǎn)，共2 048個(gè)分片。

2 基于星型架構(gòu)的TKM算法

2.1 星型分片架構(gòu)

基于星型架構(gòu)的區(qū)塊鏈系統(tǒng)有著以下的共同特點(diǎn)：a）對(duì)交易進(jìn)行分片存儲(chǔ)，每個(gè)分片負(fù)責(zé)一些特定的交易，減少節(jié)點(diǎn)的網(wǎng)絡(luò)負(fù)載；b）分片內(nèi)節(jié)點(diǎn)間自由交易，這種類型的交易屬于片內(nèi)交易；c）兩個(gè)節(jié)點(diǎn)進(jìn)行交易但分別在不同的分片中，這種類型的交易屬于跨片交易，該類型的交易需要通過(guò)主鏈進(jìn)行中轉(zhuǎn)。主鏈的功能是不固定的，在簡(jiǎn)單的系統(tǒng)中主鏈只需要負(fù)責(zé)交易的轉(zhuǎn)發(fā)。但在一些復(fù)雜的系統(tǒng)中，主鏈還需要負(fù)責(zé)交易驗(yàn)證、交易確認(rèn)等復(fù)雜功能。針對(duì)簡(jiǎn)單系統(tǒng)的主鏈功能，本文抽象地表示一種通用星型分片架構(gòu)，如圖1所示。

在此星型架構(gòu)中，區(qū)塊鏈由分片鏈和主鏈組成，分片鏈需處理本分片特定的交易，并同步與主鏈的數(shù)據(jù)，每筆交易產(chǎn)生后會(huì)送至對(duì)應(yīng)分片鏈進(jìn)行處理、打包。主鏈負(fù)責(zé)交易的確認(rèn)、轉(zhuǎn)發(fā)即可。

區(qū)塊鏈的系統(tǒng)通量可以表示為總交易數(shù)除以所需時(shí)間，如式（1）所示。

TPS=Xtxttx（1）

當(dāng)系統(tǒng)分為N個(gè)分片時(shí)，一筆交易屬于i分片的概率，如式（2）所示。

θ（i）=P（sID=i） i=1，2，…，N，∑Ni=1θ（i）=1（2）

一筆交易屬于i分片，但交易的目的地址屬于j分片的概率表達(dá)式為

ε（j，i）=P（rID=j|sID=i） i，j=1，2，…，N，∑Nj=1ε（j，i）=1（3）

其中：sID是交易的發(fā)送方所在分片；rID是交易的接收方所在分片。

面對(duì)一些攻擊問(wèn)題（例如雙花攻擊）時(shí)，星型結(jié)構(gòu)防范雙花攻擊的關(guān)鍵在于共識(shí)機(jī)制，共識(shí)機(jī)制屬于共識(shí)層。本文提出的星型結(jié)構(gòu)通過(guò)TKM分片算法引入的時(shí)間戳和工作量證明機(jī)制（PoW），增加惡意節(jié)點(diǎn)實(shí)施雙花攻擊的計(jì)算資源和時(shí)間，防止其在短時(shí)間內(nèi)進(jìn)行多次交易以實(shí)施雙花攻擊。

2.2 TKM分片算法

區(qū)塊鏈分片主要分為網(wǎng)絡(luò)分片、交易分片和狀態(tài)分片三種方式。本文提出的星型結(jié)構(gòu)的分片規(guī)則基于TKM（timestamp K-means）分片算法，該分片算法屬于網(wǎng)絡(luò)分片算法，即通過(guò)一定的組織方式將整個(gè)網(wǎng)絡(luò)分成不同的分片，各個(gè)分片并行處理整個(gè)區(qū)塊鏈中的部分交易。節(jié)點(diǎn)在產(chǎn)生交易前就有對(duì)應(yīng)的分片了。

TKM算法在K-means算法的基礎(chǔ)上主要的改進(jìn)包括添加了時(shí)間戳這一參數(shù)，在TKM算法中時(shí)間戳的作用是與x和y坐標(biāo)共同參與節(jié)點(diǎn)的分片，同時(shí)時(shí)間戳具有唯一性和隨機(jī)性，減少惡意節(jié)點(diǎn)通過(guò)控制距離（x和y坐標(biāo)）的方式劃分到一個(gè)分片進(jìn)行作惡的可能性。

在TKM分片算法中節(jié)點(diǎn)劃分分片的主要因素是通過(guò)節(jié)點(diǎn)間距離和節(jié)點(diǎn)生成時(shí)的時(shí)間戳，本文使用改進(jìn)的K-means聚類算法，即TKM算法進(jìn)行分片，其本質(zhì)是兩節(jié)點(diǎn)間間距和時(shí)間戳的歐氏距離越接近，兩節(jié)點(diǎn)越可能被劃分到一個(gè)分片內(nèi)。

兩節(jié)點(diǎn)距離和時(shí)間戳越接近，兩節(jié)點(diǎn)間的跳數(shù)（hop count）可能越小，通信時(shí)間也越小。TKM算法分片與隨機(jī)分片相比優(yōu)勢(shì)在于前者可以極大提高鄰近節(jié)點(diǎn)發(fā)生的交易為片內(nèi)交易的概率。假設(shè)一個(gè)交易為鄰近節(jié)點(diǎn)之間的片內(nèi)交易，該交易會(huì)快速同步至主鏈，增加系統(tǒng)吞吐量，從而提高系統(tǒng)效率，以下為TKM算法運(yùn)算步驟以及偽代碼。

算法1 TKM算法步驟

輸入：區(qū)塊鏈系統(tǒng)中節(jié)點(diǎn)的x坐標(biāo)列表listx，y坐標(biāo)列表listy，以及節(jié)點(diǎn)加入網(wǎng)絡(luò)時(shí)的時(shí)間戳列表listt。

輸出：分片結(jié)果result和分片簇中心列表listm。

a）隨機(jī)初始化k個(gè)簇中心mid存入列表listm中。

b）判斷result和listm是否發(fā)生變化，沒(méi)有變化結(jié)束算法。

c）循環(huán)計(jì)算節(jié)點(diǎn)到簇中心的距離列表listd，并按照最小距離原則進(jìn)行聚類。

d）不斷更新listm以及聚類結(jié)果result。執(zhí)行后轉(zhuǎn)步驟b）。

算法2 TKM算法偽代碼

input：listx，listy，listt

output：result，listm

find out k mid，put into listm

while result！=resultnew or listm！=listnew

listd=sqrt（listx+listy+listt）

get result，by listd

update new listnew

update new resultnew

return result，listm

2.3 基于TKM算法的星型架構(gòu)通量模型

2.3.1 主鏈性能與分片數(shù)量關(guān)系分析

主鏈的功能是轉(zhuǎn)發(fā)跨片交易，在本文提到的通量模型下，隨著分片數(shù)量的增加，跨片交易占總交易的比重也會(huì)增加，主鏈會(huì)出現(xiàn)過(guò)載的情況。分析極端的情況，若系統(tǒng)只有一個(gè)分片時(shí)也就是沒(méi)有分片，區(qū)塊鏈的通量沒(méi)有得到提高。若系統(tǒng)中每個(gè)節(jié)點(diǎn)自成一個(gè)分片，所有交易均為跨片交易，相當(dāng)于沒(méi)有分片，與沒(méi)有分片時(shí)通量類似。

對(duì)上述兩種極端情況進(jìn)行分析，系統(tǒng)通量隨分片數(shù)量增加的變化應(yīng)該是先增加后減少，分片后的系統(tǒng)會(huì)呈現(xiàn)兩種情況。

a）分片較少時(shí)，主鏈轉(zhuǎn)發(fā)交易的時(shí)間遠(yuǎn)小于各分片的交易處理時(shí)間。此時(shí)每個(gè)分片的交易處理時(shí)間tshard表示為

tshard=tintra-tx+tinter-txA+tinter-txB（4）

其中：tintra-tx是片內(nèi)交易時(shí)間；tinter-txA是交易發(fā)送方在該分片的跨片交易；tinter-txB是交易接收方在該分片的跨片交易。

tintra-tx=Mθ（i）ε（i，i）t

tinter-txA=Mθ（i）［1-ε（i，i）］αt

tinter-txB=∑j≠iMθ（j）ε（i，j）βt（5）

將處理交易時(shí)間表達(dá)式（5）代入式（4）中，第i個(gè)分片的交易處理時(shí)間ti為

ti=Mθ（i）ε（i，i）t+Mθ（i）［1-ε（i，i）］αt+∑j≠iMθ（j）ε（i，j）βt（6）

在單位時(shí)間處理的交易通量TPS為

1max{θ（i）ε（i，i）t+θ（i）［1-ε（i，i）］αt+∑j≠iθ（j）ε（i，j）βt}（7）

b）分片數(shù)開始增加，超出一定值時(shí)，交易在主鏈的處理時(shí)間超出了各個(gè)分片處理交易的時(shí)間，因此要等待主鏈上所有跨片交易處理完畢后，其他分片才能進(jìn)行對(duì)跨片交易的處理。此時(shí)交易數(shù)量M較大，系統(tǒng)處理交易的總時(shí)間ttotal恒等于主鏈處理交易的時(shí)間tmainchain。

ttotal=tmainchain（8）

tmainchain=M［1-∑Ni=1θ（i）ε（i，i）］（9）

TPS=MM［1-∑Ni=1θ（i）ε（i，i）］γt（10）

由式（10）可知：分片數(shù)量越多，系統(tǒng)中片內(nèi)交易占比越低、跨片交易比例越高，因此當(dāng)主鏈處理交易的時(shí)間大于分片處理交易的時(shí)間時(shí)，分片數(shù)量N越大，系統(tǒng)通量反而越小。

綜上：當(dāng)ti>tmainchain時(shí)，系統(tǒng)的通量受到最慢的分片鏈速度限制；當(dāng)ti≤tmainchain時(shí)，系統(tǒng)通量主要由主鏈的處理交易速度決定；當(dāng)分片數(shù)N處于一個(gè)特定值時(shí)，即ti=tmainchain（代入到式（6）（9）（11）），可得到系統(tǒng)通量最大值的分片數(shù)，也就是系統(tǒng)最優(yōu)分片數(shù)。

{Mθ（i）ε（i，i）t+Mθ（i）［1-ε（i，i）］αt+∑j≠iMθ（j）ε（i，i）βt}（11）

M［1-∑Ni=1θ（i）ε（i，i）］γt（12）

式（11）和（12）是等價(jià)的，均表示此時(shí)系統(tǒng)的最優(yōu)分片數(shù)。

2.3.2 通量與分片數(shù)量函數(shù)關(guān)系

交易所屬分片的概率θ（i）、片內(nèi)交易概率ε（i，i）、跨片交易概率ε（j，i）都受到分片數(shù)量N的影響，因此表達(dá)式如下：

θ（i）=f（N）（13）

ε（i，i）=g（N）（14）

ε（j，i）=1-g（N）N-1 j≠i（15）

將式（12）中的θ（i）、ε（i，i）和ε（j，i）以分片數(shù)量N為自變量帶入后，得到此時(shí)系統(tǒng)最優(yōu)分片數(shù)：

fi（N）g（N）+fi（N）［1-g（N）］α+∑j≠ifi（N）1-g（N）N-1β（16）

［1-g（N）］γ（17）

式（16）與式（17）等價(jià)。

在該星型架構(gòu)中，以TKM算法作為節(jié)點(diǎn)的分片規(guī)則，系統(tǒng)隨機(jī)產(chǎn)生交易，并等可能地落到每一個(gè)分片中，本文通過(guò)爬取以太坊中近30萬(wàn)條數(shù)據(jù)進(jìn)行模擬實(shí)驗(yàn)，計(jì)算得出在不同分片數(shù)量N情況下每個(gè)分片的交易概率fi（N）近似1/N，如圖2所示。

圖2中依次是N=2、N=8、N=16時(shí)的各分片交易概率分布，式（13）中分片獲交易的概率fi（N）可視作：

θ（i）=fi（N）=1N（1+σi） i=1，2，…，N（18）

式（18）中σi的取值為

-1≤σi≤1（19）

對(duì)交易數(shù)據(jù)進(jìn)行模擬實(shí)驗(yàn)，實(shí)驗(yàn)分成2、4、8、16、32、64片，發(fā)現(xiàn)交易歸屬概率fi（N）在1/N附近波動(dòng)，但不會(huì)超過(guò)3/2N?？梢暒业纳洗_界為1/2。式（14）中交易概率分布g（N）為各分片的平均交易概率，可視作1/N：

ε（i，i）=g（N）=1N i=1，2，…，N（20）

式（15）中跨片交易概率可視作：

ε（j，i）=1-g（N）N-1=1N j≠i（21）

若使式（11）與（12）相等，式（11）應(yīng)取分片鏈處理交易的最長(zhǎng)時(shí)間對(duì)應(yīng)式（16）中挑選fi（N）最大的分片：

fmax（N）=1N（1+σmax） 0≤σmax≤12（22）

將fmax（N）=1N（1+σmax），g（N）=1N代入式（16）（17）中并化簡(jiǎn)得：

（1+σmax）（1N2+N-1N2α+N-1N2β）=N-1Nγ（23）

變形為分片數(shù)量N的函數(shù)關(guān)系：

N=（α+β+Γ）+（α+β+Γ）2-4Γ（α+β-1）2Γ（24）

其中：

Γ=γ1+σmax（25）

式（24）的N值就是N的臨界值，即系統(tǒng)最佳分片數(shù)。以下用Nt表示該臨界值。結(jié)合式（7）（10）可以推導(dǎo)出以TKM算法作為分片規(guī)則的星型架構(gòu)的通量表達(dá)式：

TPS=1t×N2（1+σmax）［1+（α+β）（N-1）］

1t×Nγ（N-1） （26）

3 實(shí)驗(yàn)仿真

3.1 實(shí)驗(yàn)設(shè)計(jì)

本文選擇在PyCharm平臺(tái)對(duì)以太坊的30萬(wàn)條交易數(shù)據(jù)進(jìn)行三組模擬實(shí)驗(yàn)。實(shí)驗(yàn)1：模擬星型分片架構(gòu)并將本文提出的TKM分片規(guī)則與傳統(tǒng)的賬戶隨機(jī)規(guī)則進(jìn)行性能對(duì)比，實(shí)驗(yàn)結(jié)果證明根據(jù)TKM分片規(guī)則進(jìn)行分片，系統(tǒng)在處理相同數(shù)量交易數(shù)據(jù)時(shí)用時(shí)更少。實(shí)驗(yàn)2：通過(guò)仿真模擬實(shí)驗(yàn)得出不同分片數(shù)下系統(tǒng)中各分片的節(jié)點(diǎn)占比，實(shí)驗(yàn)結(jié)果表明系統(tǒng)中各分片大小近似均勻，各分片中的節(jié)點(diǎn)個(gè)數(shù)近似系統(tǒng)中總節(jié)點(diǎn)數(shù)的1/N，避免了因個(gè)別分片過(guò)小而引發(fā)的安全問(wèn)題。實(shí)驗(yàn)3：將TKM、MACG、賬戶隨機(jī)算法等分別作為星型架構(gòu)中的分片規(guī)則，對(duì)比幾種分片規(guī)則下的系統(tǒng)通量。實(shí)驗(yàn)結(jié)果證明以TKM算法作為分片規(guī)則的區(qū)塊鏈系統(tǒng)通量高于其他幾種分片規(guī)則。

3.2 實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)1中，在α=1，β=1，Γ=10-1的主鏈復(fù)雜度下對(duì)比TKM算法作為分片規(guī)則和傳統(tǒng)的賬戶隨機(jī)分片規(guī)則在相同交易數(shù)據(jù)集下的完成時(shí)間對(duì)比如圖3所示。實(shí)驗(yàn)數(shù)據(jù)以以太坊交易數(shù)據(jù)進(jìn)行模擬實(shí)驗(yàn)。

圖中x軸為系統(tǒng)的分片數(shù)量，y軸為TKM分片規(guī)則與賬戶隨機(jī)分片規(guī)則的處理交易完成時(shí)間。實(shí)驗(yàn)結(jié)果為TKM算法作為分片規(guī)則的星型分片架構(gòu)在不同測(cè)試分片數(shù)的情況下，系統(tǒng)完成時(shí)間均小于賬戶隨機(jī)分片。說(shuō)明在α=1，β=1，Γ=10-1的主鏈復(fù)雜度時(shí)，TKM算法作為分片規(guī)則的星型分片架構(gòu)在相同分片數(shù)下處理交易的速度都要高于賬戶隨機(jī)分片。

實(shí)驗(yàn)2中，假設(shè)系統(tǒng)主鏈復(fù)雜度為α=1，β=1，Γ=10-1，即以太坊的復(fù)雜度等級(jí)。在不同的系統(tǒng)分片數(shù)下，TKM分片算法的系統(tǒng)中各個(gè)分片的節(jié)點(diǎn)個(gè)數(shù)占比如圖4、5所示。

其中，圖4、5分別是當(dāng)分片數(shù)N=8和N=16時(shí)系統(tǒng)中各分片節(jié)點(diǎn)占比情況。x軸為系統(tǒng)中各個(gè)分片編號(hào)，y軸為各個(gè)分片中的節(jié)點(diǎn)占比。實(shí)驗(yàn)結(jié)果得出在系統(tǒng)中分片數(shù)量N不同時(shí)，每個(gè)分片的節(jié)點(diǎn)占比近似1/N，可以看出TKM算法分片規(guī)則劃分的分片大小近似等于系統(tǒng)中節(jié)點(diǎn)總數(shù)的1/N，使系統(tǒng)中每個(gè)分片驗(yàn)證交易的煩瑣度以及分片大小都在同一數(shù)量級(jí)，系統(tǒng)中不會(huì)出現(xiàn)因某個(gè)分片過(guò)大或過(guò)小所引發(fā)的安全問(wèn)題。

實(shí)驗(yàn)3中，在不同主鏈復(fù)雜度下對(duì)幾種近年的區(qū)塊鏈分片規(guī)則（賬戶隨機(jī)分片、MACG、基于PBFT的分片算法［16］、基于LBNC的分片算法［17］）的星型架構(gòu)進(jìn)行系統(tǒng)通量對(duì)比。由式（26）可知系統(tǒng)通量與分片數(shù)量呈分段函數(shù)，且不同的主鏈復(fù)雜度，即α、β、Γ不同時(shí)系統(tǒng)的最優(yōu)分片數(shù)也不相同，因此列舉當(dāng)Γ的數(shù)量級(jí)分別為10-1、10-2、10-3時(shí)，系統(tǒng)通量（不分片系統(tǒng)的通量倍數(shù)）與分片數(shù)的關(guān)系。

當(dāng)Γ的數(shù)量級(jí)為10-1、10-2、10-3時(shí)，幾種算法的通量增長(zhǎng)倍數(shù)依次如圖6～8所示，可以看出TKM算法分片規(guī)則的系統(tǒng)通量明顯高于其他幾種分片規(guī)則。

通過(guò)圖6～8可以看出在Γ=10-1，10-2，10-3時(shí)TKM算法作為分片規(guī)則的最大系統(tǒng)通量高于賬戶隨機(jī)規(guī)則20%，同時(shí)明顯高于其他的分片算法，并且TKM算法在三種情況下的最佳分片數(shù)N與賬戶隨機(jī)算法相同，分別為32、256、2 048。表2總結(jié)了不同主鏈復(fù)雜度下的TKM分片星型架構(gòu)的最高通量倍數(shù)以及其對(duì)應(yīng)的最優(yōu)分片數(shù)。表中加粗?jǐn)?shù)值代表在不同主鏈復(fù)雜度下的最優(yōu)分片數(shù)以及最大系統(tǒng)通量。

4 結(jié)束語(yǔ)

本文提出了一種基于星型結(jié)構(gòu)的TKM分片算法，該算法將原始K-mean聚類算法進(jìn)行改進(jìn)，并運(yùn)用在節(jié)點(diǎn)分片規(guī)則上。該分片規(guī)則與傳統(tǒng)的賬戶隨機(jī)分片算法相比，極大提高了鄰居節(jié)點(diǎn)的交易為片內(nèi)交易的概率，使最大系統(tǒng)通量提高20%，本文提出的分片算法仍有改進(jìn)空間，使系統(tǒng)通量提升更大，這將是今后的工作與展望。

參考文獻(xiàn)：

［1］Howell A，Saber T，Bendechache M.Measuring node decentralisation in blockchain peer to peer networks［J］.Blockchain：Research and Applications，2023，4（1）：100109.

［2］Sharma R，Villányi B.A sustainable Ethereum merge-based big-data gathering and dissemination in IIoT system［J］.Alexandria Engineering Journal，2023，69：109-119.

［3］Zhang Shiyao，Cheng Cheng，Chen Zhimin，et al.Research on digital smart contract based on blockchain［J］.Academic Journal of Engineering and Technology Science，2020，3（3）：030309.

［4］Shaikh Z A，Khan A A，Baitenova L，et al.Blockchain hyperledger with non-linear machine learning：a novel and secure educational accreditation registration and distributed ledger preservation architecture［J］.Applied Sciences，2022，12（5）：2534-2534.

［5］Xie Renqiang，Zhang Wende.Research on copyright protection of digital works based on multi-blockchain［J］.Recent Advances in Computer Science and Communications，2022，15（9）：1223-1230.

［6］Ahad S A，Sangra S，Saini J，et al.Decentralized E-voting system using Ethereum blockchain technology［J］.Advances in Science and Technology，2023，6630（1）：619-627.

［7］鄧加成.基于分片的混合共識(shí)協(xié)議算法研究［D］.?？冢汉Ｄ洗髮W(xué)，2022.（Deng Jiacheng.Research on hybrid consensus protocol algorithm based on sharding［D］.Haikou：Hainan University，2022.）

［8］劉宏陽(yáng).面向物聯(lián)網(wǎng)的區(qū)塊鏈技術(shù)研究［D］.上海：上海交通大學(xué)，2020.（Liu Hongyang.Blockchain technology for Internet of Things［D］.Shanghai：Shanghai Jiao Tong University，2020.）

［9］Wang Jiaping，Wang Hao.Monoxide：scale out blockchain with asynchronous consensus zones［J］.IACR CryptologyePrint Archive，2019，2019（1）：263-263.

［10］湯佳霖.區(qū)塊鏈綜述和創(chuàng)新應(yīng)用場(chǎng)景探究［J］.全國(guó)流通經(jīng)濟(jì)，2019，2019（22）：144-145.（Tang Jialin.Overview of blockchain and exploration of innovative application scenarios［J］.China Circulation Economy，2019，2019（22）：144-145.）

［11］黃華威，孔偉，彭肖文，等.區(qū)塊鏈分片技術(shù)綜述［J］.計(jì)算機(jī)工程，2022，48（6）：1-10.（Huang Huawei，Kong Wei，Peng Xiaowen，et al.Survey on blockchain sharding technology［J］.Computer En-gineering，2022，48（6）：1-10.）

［12］潘吉飛，黃德才.基于跳躍Hash和異步共識(shí)組的區(qū)塊鏈動(dòng)態(tài)分片模型［J］.計(jì)算機(jī)科學(xué)，2020，47（3）：273-280.（Pan Jifei，Huang Decai.Blockchain dynamic sharding model based on jump Hash and asynchronous consensus group［J］.Computer Science，2020，47（3）：273-280.）

［13］Chen Huan，Wang Yijie.SSChain：a full sharding protocol for public blockchain without data migration overhead［J］.Pervasive and Mobile Computing，2019，59（C）：101055.

［14］Mohammad J A，Divyakant A，Amr E A.SharPer：sharding permissioned blockchains over network clusters［EB/OL］.（2019）.https：//arxiv.org/abs/1910.00765.

［15］Dang H，Dinh A T T，Loghin D，et al.Towards scaling blockchain systems via sharding［C］//Proc of International Conference on Management of Data.Piscataway，NJ：IEEE Press，2019：123-140.

［16］趙鵬，梁晉銘，劉佳寶.基于節(jié)點(diǎn)屬性分片的區(qū)塊鏈研究設(shè)計(jì)［J］.現(xiàn)代信息科技，2023，7（4）：29-31，35.（Zhao Peng，Liang Jinming，Liu Jiabao.Research and design of blockchain based on node attribute fragmentation［J］.Modern Information Technology，2023，7（4）：29-31，35.）

［17］王珺，馬建煒，羅金喜.一種應(yīng)用于邊緣計(jì)算的區(qū)塊鏈分片方案［J］.物聯(lián)網(wǎng)學(xué)報(bào)，

2023，7（4）：88-100.（Wang Jun，Ma Jianwei，Luo Jinxi.A blockchain sharding scheme inedge computing［J］.Chinese Journal on Internet of Things，2023，7（4）：88-100.）