星型區塊鏈架構的TKM分片算法

徐克圣 謝詔馳

摘 要：區塊鏈系統的通量嚴重不足，而解決此問題最有效的一類方案是并行化處理，并行化方案主要為星型架構，當前星型架構對系統中節點的分片方式多為賬戶隨機分片，這種分片方式的系統通量仍然不足。針對此問題，提出了一種基于星型結構的TKM分片算法，該算法將原始K-means聚類算法進行改進，并運用在節點分片上。TKM分片算法將聚類算法與區塊鏈的網絡分片技術相結合，使節點根據地理位置進行分片，極大提高鄰近節點發生的交易為片內交易的概率，從而提高系統通量，同時在原始算法的基礎上引入了時間戳，減少了惡意節點的攻擊。仿真實驗表明該算法與傳統的隨機分片算法相比，最大系統通量提高了20%。根據上述通量模型，通過實驗得出基于TKM算法的星型區塊鏈系統的最優分片數量。

關鍵詞：區塊鏈；星型架構；分片算法；聚類算法；通量

中圖分類號：TP393.04?? 文獻標志碼：A

文章編號：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］提出以來，區塊鏈技術受到廣泛的關注，區塊鏈技術已經從最初的數字貨幣領域發展到面對面實時支付、數字資產交易、物聯網等日常領域。區塊鏈雖然具有高安全性，但通量嚴重不足，無法滿足現實需求，也限制了其進一步擴展應用領域。通量是判斷區塊鏈系統性能的指標之一，通量也為吞吐量（transactions per second，TPS），同時也是區塊鏈技術當前的瓶頸之一。目前主流的公鏈系統如比特幣、以太坊［2］的通量處于101，聯盟鏈系統超級賬本［3，4］普遍處于102，與中心化支付系統微信錢包與支付寶最高可承載105的數量級相差甚遠。中心化系統處理交易的速度遠超區塊鏈系統，若想將區塊鏈技術運用在更廣泛的日常生活中，提高區塊鏈系統通量就成為了一個迫切需求。

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

本文的主要貢獻如下：

a）本文將聚類算法與分片規則結合，提出了基于星型架構的TKM分片算法。通過此分片規則可以極大提高鄰近節點之間的交易為片內交易的概率，更快地同步至主鏈，提高系統通量。

b）對星型架構中的區塊鏈通量與分片數量的關系進行推導，建立星型架構模型，得出分片數量與系統通量不成正比，系統存在一個通量峰值，該峰值對應著最優分片數。在最優分片數前，通量隨分片數增加會穩定增長，在最優分片數后，通量會隨分片數增加而緩慢下降，最后保持不變。

1 相關研究

1.1 區塊鏈技術

區塊鏈系統是多種技術融合在一起的成果，其中包括P2P通信、密碼學、智能合約、分布式存儲等。區塊鏈具有分布式、去中心化、強魯棒性、不可竄改等優點，每個節點共同組成一個大的P2P網絡，其中交易的合法性由共識機制和數字簽名保證，區塊間通過一條哈希鏈進行連接，賬本由網絡中所有節點共同維護。

區塊鏈的發展分為三個階段。第一階段是比特幣的產生，其應用范圍完全聚集在數字貨幣上，構建了一種全新的、去中心化的數字支付系統。第二階段的標志是將“智能合約”的概念引入到區塊鏈中，有了智能合約的加入，增強了區塊鏈系統的安全性，其應用范圍開始向金融領域蔓延。第三階段，人們企圖利用區塊鏈技術顛覆互聯網的底層協議，于是區塊鏈技術被逐漸應用到公證、審計、物流、醫療等領域［10］，最后應用領域擴大至整個社會。

1.2 性能瓶頸

區塊鏈性能的兩個主要指標分別是通量和時延，通量即固定時間處理的交易數，時延是交易處理的響應時間。通量和時延兩者對立相向，只考慮通量會造成交易響應時間過長，影響客戶體驗，只考慮時延會造成交易排隊。

a）通量。系統通量不足是目前區塊鏈有待攻克的技術瓶頸之一，當前主流的公有鏈系統（比特幣、以太坊）的系統通量與中心化系統相差甚遠。目前主流的提高系統通量的方案就是分片技術。

b）時延。區塊鏈交易存在延遲，在去中心化系統中以下原因會影響交易時延：（a）區塊鏈leader節點出塊時間；（b）主鏈的功能復雜度；（c）區塊存儲交易的上限數量。

本文主要針對區塊鏈系統通量不足的問題進行研究與改進。

1.3 分片技術

分片技術作為提高區塊鏈系統通量的主流方案［11］，近年來不斷更新迭代，各種分片規則層出不窮。區塊鏈分片技術主要分為無許可鏈和許可鏈兩種，前者是分片技術的主流方式。普遍的分片方案就是以太坊2.0應用的，以星型架構方式按照賬戶地址前6位將賬戶隨機地分到分片中的方案。表1是對近年來區塊鏈分片技術的歸納。表1中的符號含義如下：［a］表示每個分片100個節點，共16個分片；［b］表示每個分片鏈900個節點共60個分片，主鏈900個節點；［c］表示每個分片4個節點共5個分片；［d］表示共972個節點，分為36個分片；［e］表示每個分片36個節點，共2 048個分片。

2 基于星型架構的TKM算法

2.1 星型分片架構

基于星型架構的區塊鏈系統有著以下的共同特點：a）對交易進行分片存儲，每個分片負責一些特定的交易，減少節點的網絡負載；b）分片內節點間自由交易，這種類型的交易屬于片內交易；c）兩個節點進行交易但分別在不同的分片中，這種類型的交易屬于跨片交易，該類型的交易需要通過主鏈進行中轉。主鏈的功能是不固定的，在簡單的系統中主鏈只需要負責交易的轉發。但在一些復雜的系統中，主鏈還需要負責交易驗證、交易確認等復雜功能。針對簡單系統的主鏈功能，本文抽象地表示一種通用星型分片架構，如圖1所示。

在此星型架構中，區塊鏈由分片鏈和主鏈組成，分片鏈需處理本分片特定的交易，并同步與主鏈的數據，每筆交易產生后會送至對應分片鏈進行處理、打包。主鏈負責交易的確認、轉發即可。

區塊鏈的系統通量可以表示為總交易數除以所需時間，如式（1）所示。

TPS=Xtxttx（1）

當系統分為N個分片時，一筆交易屬于i分片的概率，如式（2）所示。

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

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

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

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

面對一些攻擊問題（例如雙花攻擊）時，星型結構防范雙花攻擊的關鍵在于共識機制，共識機制屬于共識層。本文提出的星型結構通過TKM分片算法引入的時間戳和工作量證明機制（PoW），增加惡意節點實施雙花攻擊的計算資源和時間，防止其在短時間內進行多次交易以實施雙花攻擊。

2.2 TKM分片算法

區塊鏈分片主要分為網絡分片、交易分片和狀態分片三種方式。本文提出的星型結構的分片規則基于TKM（timestamp K-means）分片算法，該分片算法屬于網絡分片算法，即通過一定的組織方式將整個網絡分成不同的分片，各個分片并行處理整個區塊鏈中的部分交易。節點在產生交易前就有對應的分片了。

TKM算法在K-means算法的基礎上主要的改進包括添加了時間戳這一參數，在TKM算法中時間戳的作用是與x和y坐標共同參與節點的分片，同時時間戳具有唯一性和隨機性，減少惡意節點通過控制距離（x和y坐標）的方式劃分到一個分片進行作惡的可能性。

在TKM分片算法中節點劃分分片的主要因素是通過節點間距離和節點生成時的時間戳，本文使用改進的K-means聚類算法，即TKM算法進行分片，其本質是兩節點間間距和時間戳的歐氏距離越接近，兩節點越可能被劃分到一個分片內。

兩節點距離和時間戳越接近，兩節點間的跳數（hop count）可能越小，通信時間也越小。TKM算法分片與隨機分片相比優勢在于前者可以極大提高鄰近節點發生的交易為片內交易的概率。假設一個交易為鄰近節點之間的片內交易，該交易會快速同步至主鏈，增加系統吞吐量，從而提高系統效率，以下為TKM算法運算步驟以及偽代碼。

算法1 TKM算法步驟

輸入：區塊鏈系統中節點的x坐標列表listx，y坐標列表listy，以及節點加入網絡時的時間戳列表listt。

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

a）隨機初始化k個簇中心mid存入列表listm中。

b）判斷result和listm是否發生變化，沒有變化結束算法。

c）循環計算節點到簇中心的距離列表listd，并按照最小距離原則進行聚類。

d）不斷更新listm以及聚類結果result。執行后轉步驟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算法的星型架構通量模型

2.3.1 主鏈性能與分片數量關系分析

主鏈的功能是轉發跨片交易，在本文提到的通量模型下，隨著分片數量的增加，跨片交易占總交易的比重也會增加，主鏈會出現過載的情況。分析極端的情況，若系統只有一個分片時也就是沒有分片，區塊鏈的通量沒有得到提高。若系統中每個節點自成一個分片，所有交易均為跨片交易，相當于沒有分片，與沒有分片時通量類似。

對上述兩種極端情況進行分析，系統通量隨分片數量增加的變化應該是先增加后減少，分片后的系統會呈現兩種情況。

a）分片較少時，主鏈轉發交易的時間遠小于各分片的交易處理時間。此時每個分片的交易處理時間tshard表示為

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

其中：tintra-tx是片內交易時間；tinter-txA是交易發送方在該分片的跨片交易；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）

將處理交易時間表達式（5）代入式（4）中，第i個分片的交易處理時間ti為

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

在單位時間處理的交易通量TPS為

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

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

ttotal=tmainchain（8）

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

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

由式（10）可知：分片數量越多，系統中片內交易占比越低、跨片交易比例越高，因此當主鏈處理交易的時間大于分片處理交易的時間時，分片數量N越大，系統通量反而越小。

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

{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）是等價的，均表示此時系統的最優分片數。

2.3.2 通量與分片數量函數關系

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

θ（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）以分片數量N為自變量帶入后，得到此時系統最優分片數：

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

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

式（16）與式（17）等價。

在該星型架構中，以TKM算法作為節點的分片規則，系統隨機產生交易，并等可能地落到每一個分片中，本文通過爬取以太坊中近30萬條數據進行模擬實驗，計算得出在不同分片數量N情況下每個分片的交易概率fi（N）近似1/N，如圖2所示。

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

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

式（18）中σi的取值為

-1≤σi≤1（19）

對交易數據進行模擬實驗，實驗分成2、4、8、16、32、64片，發現交易歸屬概率fi（N）在1/N附近波動，但不會超過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）應取分片鏈處理交易的最長時間對應式（16）中挑選fi（N）最大的分片：

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

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

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

變形為分片數量N的函數關系：

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

其中：

Γ=γ1+σmax（25）

式（24）的N值就是N的臨界值，即系統最佳分片數。以下用Nt表示該臨界值。結合式（7）（10）可以推導出以TKM算法作為分片規則的星型架構的通量表達式：

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

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

3 實驗仿真

3.1 實驗設計

本文選擇在PyCharm平臺對以太坊的30萬條交易數據進行三組模擬實驗。實驗1：模擬星型分片架構并將本文提出的TKM分片規則與傳統的賬戶隨機規則進行性能對比，實驗結果證明根據TKM分片規則進行分片，系統在處理相同數量交易數據時用時更少。實驗2：通過仿真模擬實驗得出不同分片數下系統中各分片的節點占比，實驗結果表明系統中各分片大小近似均勻，各分片中的節點個數近似系統中總節點數的1/N，避免了因個別分片過小而引發的安全問題。實驗3：將TKM、MACG、賬戶隨機算法等分別作為星型架構中的分片規則，對比幾種分片規則下的系統通量。實驗結果證明以TKM算法作為分片規則的區塊鏈系統通量高于其他幾種分片規則。

3.2 實驗結果分析

實驗1中，在α=1，β=1，Γ=10-1的主鏈復雜度下對比TKM算法作為分片規則和傳統的賬戶隨機分片規則在相同交易數據集下的完成時間對比如圖3所示。實驗數據以以太坊交易數據進行模擬實驗。

圖中x軸為系統的分片數量，y軸為TKM分片規則與賬戶隨機分片規則的處理交易完成時間。實驗結果為TKM算法作為分片規則的星型分片架構在不同測試分片數的情況下，系統完成時間均小于賬戶隨機分片。說明在α=1，β=1，Γ=10-1的主鏈復雜度時，TKM算法作為分片規則的星型分片架構在相同分片數下處理交易的速度都要高于賬戶隨機分片。

實驗2中，假設系統主鏈復雜度為α=1，β=1，Γ=10-1，即以太坊的復雜度等級。在不同的系統分片數下，TKM分片算法的系統中各個分片的節點個數占比如圖4、5所示。

其中，圖4、5分別是當分片數N=8和N=16時系統中各分片節點占比情況。x軸為系統中各個分片編號，y軸為各個分片中的節點占比。實驗結果得出在系統中分片數量N不同時，每個分片的節點占比近似1/N，可以看出TKM算法分片規則劃分的分片大小近似等于系統中節點總數的1/N，使系統中每個分片驗證交易的煩瑣度以及分片大小都在同一數量級，系統中不會出現因某個分片過大或過小所引發的安全問題。

實驗3中，在不同主鏈復雜度下對幾種近年的區塊鏈分片規則（賬戶隨機分片、MACG、基于PBFT的分片算法［16］、基于LBNC的分片算法［17］）的星型架構進行系統通量對比。由式（26）可知系統通量與分片數量呈分段函數，且不同的主鏈復雜度，即α、β、Γ不同時系統的最優分片數也不相同，因此列舉當Γ的數量級分別為10-1、10-2、10-3時，系統通量（不分片系統的通量倍數）與分片數的關系。

當Γ的數量級為10-1、10-2、10-3時，幾種算法的通量增長倍數依次如圖6～8所示，可以看出TKM算法分片規則的系統通量明顯高于其他幾種分片規則。

通過圖6～8可以看出在Γ=10-1，10-2，10-3時TKM算法作為分片規則的最大系統通量高于賬戶隨機規則20%，同時明顯高于其他的分片算法，并且TKM算法在三種情況下的最佳分片數N與賬戶隨機算法相同，分別為32、256、2 048。表2總結了不同主鏈復雜度下的TKM分片星型架構的最高通量倍數以及其對應的最優分片數。表中加粗數值代表在不同主鏈復雜度下的最優分片數以及最大系統通量。

4 結束語

本文提出了一種基于星型結構的TKM分片算法，該算法將原始K-mean聚類算法進行改進，并運用在節點分片規則上。該分片規則與傳統的賬戶隨機分片算法相比，極大提高了鄰居節點的交易為片內交易的概率，使最大系統通量提高20%，本文提出的分片算法仍有改進空間，使系統通量提升更大，這將是今后的工作與展望。

參考文獻：

［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］鄧加成.基于分片的混合共識協議算法研究［D］.海口：海南大學，2022.（Deng Jiacheng.Research on hybrid consensus protocol algorithm based on sharding［D］.Haikou：Hainan University，2022.）

［8］劉宏陽.面向物聯網的區塊鏈技術研究［D］.上海：上海交通大學，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］湯佳霖.區塊鏈綜述和創新應用場景探究［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］黃華威，孔偉，彭肖文，等.區塊鏈分片技術綜述［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和異步共識組的區塊鏈動態分片模型［J］.計算機科學，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］趙鵬，梁晉銘，劉佳寶.基于節點屬性分片的區塊鏈研究設計［J］.現代信息科技，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］王珺，馬建煒，羅金喜.一種應用于邊緣計算的區塊鏈分片方案［J］.物聯網學報，

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.）