星型区块链架构的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.）