近年来，研究者们将分片技术应用到区块链中，使其成为解决区块链可扩展性问题的重要方案。区块链网络分片的关键思想是将网络划分成多个子集，称为分片，每个分片包含一部分区块链网络节点。所有的分片并行处理网络中不同的交易集，而不是整个网络节点处理相同的交易。由于每个分片内节点单独进行交易共识，节点只需要和同分片内的其他节点进行通信，因此大大降低了计算和通信的开销。迄今为止，已有大量的区块链分片协议被提出^[12-15]。

文献[12]提出了一种可用于公有区块链的分布式分片算法Elastico，其使用工作量证明(power of work, PoW)将网络矿工节点随机分配到较小的分片中，每个分片处理一组不相交的交易。然后，分片内部节点采用经典的PBFT共识算法并行处理交易。虽然Elastico能实现在拜占庭环境下的高可扩展性，但Elastico算法的分片选择不具有很强的偏差抗性。文献[13]在Elastico算法的基础上提出了一种新的分片算法OmniLedger，该算法利用抗偏置随机协议RandHound和可验证随机函数来自主执行节点分片以确保分片的安全性。但在OmniLedger算法中，由于每个分片在进行几轮共识后就会被拆散重构，分片重构太过频繁带来较高的分片切换时延。

文献[14]采用可信执行环境(trusted execution environment, TEE)设计了一个高效安全的分片生成协议，其在分布式设置中实现了一个可信的随机信标来生成无偏随机值，同时利用TEE来增加拜占庭共识算法的容错能力以减少分片大小。文献[15]提出了公有区块链的分片算法RapidChain，其可以使整个网络容忍高达33%的恶意节点或故障节点，每个分片内可以容忍近50%的恶意节点。同时，在没有任何可信假设的情况下，RapidChain算法能实现通信、计算和存储的完全分片，具有更高的吞吐量。

尽管上述的分片算法在一定程度上实现了区块链的高可扩展性，但随着网络恶意节点数量的增加，如何获得一个较优的分片算法，使得恶意节点均匀分布在每个分片以降低分片失效概率，是一个亟待解决的问题。

本节首先对分片区块链的安全性和可扩展性进 行理论分析。基于分析模型，本节建立分片优化求解问题来实现分片区块链安全性和可扩展性的均衡。

在基于PBFT共识算法的区块链网络中，安全性和可扩展性指标的相关定义为：

1)安全性：分片区块链的安全性可以由分片内交易失效概率来衡量，被定义为分片中恶意节点数目超过能容忍最大恶意节点的界限。分片交易的失效概率越低，则代表网络安全性越高。

2) 可扩展性：分片区块链的可扩展性一般由分片后交易吞吐量和交易平均时延来衡量。交易吞吐量被定义为网络中平均每秒执行的交易数目，交易平均时延被定义为交易从提交到上链整个过程花费的平均时间。交易吞吐量越高，交易平均时延越低，网络可扩展性越高。本文仅考虑交易共识阶段的可扩展性，即交易共识吞吐量和交易共识时延。

在分片区块链中，如何指派网络节点到不同的分片问题可以转化为不放回抽样问题。因此，本文采用超几何分布来计算分片后交易的失效概率^[16]。

假设网络中总的节点数目为$ N $，恶意节点数目为$ M $，网络中分片的数目为$ {N}_{{\rm{s}}} $，每个分片具有相等的分片大小，因此分片内的节点数目为$ n=N/{N}_{{\rm{s}}} $。令随机变量$ X $表示分片中恶意节点的数量，$ P(X=k) $表示包含$ n $个节点的分片中存在$ k $个恶意节点的概率：

其均值为：

方差为：

在基于PBFT共识的区块链中，分片内能容忍的最大恶意节点数为$ {N}_{\mathrm{m}}=⌊(n-1)/3⌋ $。因此，分片后交易失效概率$ {P}_{f} $可以表示为：

在分片区块链中，如果某个分片内恶意节点数目过多，分片内节点无法对交易达成共识。为了避免分片交易失效对整个性能的影响，本文定义了一个安全参数$\mathrm{{\text{λ}} }$来限制分片失效概率，如果满足以下不等式，则分片是足够安全的：

利用切比雪夫界^[17]可知，对于任意的$ {a}\geqslant 0 $有：

因此，分片交易失效概率$ {P}_{f} $的上界可以表示为：

联合式(5)和(7)有：

区块链中，网络交易吞吐量直接取决于两个参数：每个区块包含的交易数目，即区块大小$ {S}^{{\rm{B}}} $字节以及区块成块间隔$ {T}_{{\rm{I}}} $。假设分片后每个分片内包含的恶意节点数目未超过分片内总节点数目的三分之一，即满足PBFT共识算法的要求，则区块链总交易吞吐量为各个分片的交易吞吐量之和。总交易吞吐量$ \mathrm{T}\mathrm{H} $为：

假设区块的头部大小为$ {S}_{{\rm{H}}}^{{\rm{B}}} $字节，区块内每笔交易的平均大小为β(字节)，则每个分片的交易处理速率为$ ⌊{(S}^{{\rm{B}}}-{S}_{{\rm{H}}}^{{\rm{B}}})/\beta ⌋/{T}_{{\rm{I}}} $，于是有：

PBFT的共识算法包含3个阶段：pre-prepare阶段、prepare阶段以及commit阶段。主节点接收到来自客户端的交易请求后，发送一个共识消息到其他节点。节点执行PBFT的3阶段共识流程，返回消息到客户端，客户端收到来自$ f+1 $个节点的相同消息之后完成共识^[18]。根据文献[19]可知，分片交易平均时延为：

式中，$ {T}_{v} $为区块验证时延；$ {T}_{a} $为区块排队等待时延；$ {R}_{t} $为数据传输速率。由于网络存在时延，单个分片内的交易需要等待一段时间才能获得最终确认以实现全网的一致性。为了尽可能保持区块链账本的一致性并防止区块在进入最终共识之前被丢弃，共识阶段的交易处理时延应限制在一定的区块成块间隔内，那么交易的共识时延应该受到以下约束：

在本文中，分片区块链性能优化的目的是在满足安全性约束和交易共识时延约束的条件下，尽可能最大化交易吞吐量。因此，结合约束式(8)、式(12)，建立分片区块链优化求解问题P1：

由于区块链配置参数复杂以及存在非线性约束，解决上述优化问题非常困难。

本文假设每个节点具有相同的交易处理能力，每个节点处的交易处理时延相等。同时，假设恶意节点均匀分布在每个分片中，则每个分片内的交易吞吐量一致。由式(10)可知，当区块大小$ {S}^{{\rm{B}}} $和区块成块间隔$ {T}_{{\rm{I}}} $确定的情况下，分片的数目$ {N}_{{\rm{s}}} $越大，则网络交易吞吐量$ \mathrm{T}\mathrm{H} $越高。

当网络中总的恶意节点数满足PBFT共识算法的条件，即$ N\geqslant 3M+1 $时，在给定网络节点数目$ N $、恶意节点数目$ M $的情况下，约束条件式(8)可以转化为：

因此，P1的优化问题可以转化成：

对于优化问题P2，在给定的假设条件下，很容易找到满足安全性约束的最优分片数目$ {N}_{{\rm{s}}}^{*} $，使得系统的交易吞吐量最大。但由于每个节点的行为(恶意或诚实)是完全不可知的，要使恶意节点能均匀分布于各个分片比较困难。因此，本文提出了一种基于演化博弈的分片选择算法来处理此问题。

采用PBFT共识算法的分片区块链网络可以保证数据的最终一致性，但分片内恶意节点的随机分布导致某些分片内交易共识有效性遭到破坏，从而影响这些分片的性能。本节在不牺牲系统可扩展性和安全性的前提下，设计节点分片选择算法，以使恶意节点尽可能均匀地分布在每个分片中。

区块链网络对每个节点的行为是完全不可知的，且每个节点不能掌握全局所有节点的信息，只能获取自己及邻居节点的部分信息。所以，在进行分片选择时，节点只能依靠这些不完全信息来给出决策。其次，考虑到节点是有限理性的，因此，节点无法一次性给出全局最优的分片选择策略。最后，由于区块链网络是一个分布式系统，不存在中央控制节点，因此，无法对分片的选择进行全局控制。

目前，演化博弈理论被认为是研究分布式网络中的有限理性节点决策行为的有效工具^[20]。与传统博弈模型不同，在演化博弈过程中，节点不断与周围邻居节点进行博弈，通过多次试错达到博弈均衡。同时，演化博弈不要求节点是完全理性的且不需要掌握全局信息，本节将共识节点的分片选择过程建为演化博弈模型$ \mathcal{G}=\left\{\mathcal{N},\mathcal{S},\boldsymbol{x},\boldsymbol{y}\right\} $，其中：

1) $ \mathcal{N} $为参与分片选择的所有共识节点集合，$ \left|\mathcal{N}\right|=N $。

2) $\mathcal{S}=\left\{{S}_{1},{S}_{2},\cdots ,{S}_{{N}_{{\rm{s}}}^{*}}\right\}$是分片的集合，每个共识节点将选择加入到一个分片$ {S}_{i} $中，$ {S}_{i}\in \mathcal{S} $。

3) $\boldsymbol{x}={[\{{x}_{1}^{{\rm{h}}},{x}_{1}^{{\rm{m}}}\},\{{x}_{2}^{{\rm{h}}},{x}_{2}^{{\rm{m}}}\},\cdots ,\{{x}_{{N}_{{\rm{s}}}^{*}}^{{\rm{h}}},{x}_{{N}_{{\rm{s}}}^{*}}^{{\rm{m}}}\}]}^{{\rm{T}}}$为分片内节点数目的状态矢量。式中，$ {x}_{i}^{{\rm{h}}} $代表分片$ {S}_{i} $内诚实节点在全网的占比；$ {x}_{i}^{{\rm{m}}} $代表分片$ {S}_{i} $内恶意节点在全网的占比；且$\displaystyle \sum\limits _{{S}_{i}\in \mathcal{S}}{x}_{i}^{{\rm{h}}}=N-M$及$\displaystyle \sum\limits _{{S}_{i}\in \mathcal{S}}{x}_{i}^{{\rm{m}}}=M$。

4) $\boldsymbol{y}={[\{{y}_{1}^{{\rm{h}}},{y}_{1}^{{\rm{m}}}\},\{{y}_{2}^{{\rm{h}}},{y}_{2}^{{\rm{m}}}\},\cdots ,\{{y}_{{N}_{s}^{*}}^{{\rm{h}}},{y}_{{N}_{s}^{*}}^{{\rm{m}}}\}]}^{{\rm{T}}}$为分片内节点的收益矢量，式中，$ {y}_{i}^{{\rm{h}}} $代表分片$ {S}_{i} $内诚实节点的收益；$ {y}_{i}^{{\rm{m}}} $代表代表分片$ {S}_{i} $内恶意节点的收益。

在演化博弈中，收益函数对节点做出决策起着至关重要的作用，每个共识节点在做决策时都倾向于选择使自身收益最大化的策略。因此，本节在设计节点收益函数，使具有有限理性的共识节点在进行分片选择时，选择使自己收益最大化的分片，能最终逐步达到均衡点。

共识节点的收益不仅取决于其策略，同时还取决于同分片内其他共识节点的行为，即分片内当前节点的状态。此外，PBFT共识算法要求分片内诚实节点至少占分片内总节点的三分之二，才能对交易成功达成共识，并产生区块。假设在一个时间周期$ {T} $内，分片内成功产生的预期区块数目被定义为变量$ k $的连续可微单调递增函数$ f\left(\theta \right) $，$ \theta $为分片内诚实节点的比例，$ f\left(0\right)=0 $。分片$ {S}_{i} $在时间周期$ {T} $内产生的预期区块数目为$ f\left({\theta }_{i}\right) $，其中分片$ {S}_{i} $内诚实节点的比例为$ {\theta }_{i} $：

当成功产生一个区块后，区块链网络为参与成块的所有共识节点提供奖励$ {R} $，$ {R} $为该新区块内交易的总费用及产生区块的奖励之和。每个参与共识的节点单独获得的奖励$ r $为：

如果分片内共识节点未成功对交易达成共识，系统会在超时后提出一个空的区块，参与该轮共识的所有节点都没有奖励。

其次，假设诚实节点参与共识的成本为$ {e} $，恶意节点表现出不合作行为，即不参与共识，其共识成本为$ 0 $。因此，在时间周期$ {T} $内，对于分片$ {S}_{i} $内诚实节点的收益为：

分片$ {S}_{i} $内恶意节点的收益为：

在每一轮博弈后，节点随机选择邻居分片内的某一节点进行收益比较，并在收益较低时以概率$ W $在下一轮博弈转入到其他分片中。策略转变的概率$ W $采用统计物理中的费米函数来计算。也就是说，分片$ {S}_{i} $的节点$ {N}_{i} $随机选择分片$ {S}_{j} $内的节点$ {N}_{j} $进行收益比较，在下一轮该节点$ {N}_{i} $选择分片$ {S}_{j} $的概率为：

如果分片切换概率$ W({S}_{i}\to {S}_{j}) $大于门限$ \mathrm{\omega } $，则在下一轮，节点$ {N}_{i} $切换到分片$ {S}_{j} $，否则不变。算法1描述了包含$ N $个共识节点的区块链网络遵循费米规则进行分片选择的演化博弈过程。

算法1：基于演化博弈的节点分片选择

初始化：对于所有的节点$ {N}_{i}\in \mathcal{N} $，随机选择一　　个分片$ {S}_{i}\in \mathcal{S} $开始；

输入：$ t\leftarrow 1 $

while 分片内的节点未收敛或$ t < {\mathrm{T}}_{\mathrm{m}\mathrm{a}\mathrm{x}} $ do

　for $ {N}_{i}\in \mathcal{N} $ do

　　随机选择一个分片$ {S}_{j}\in \mathcal{S} $；

　　计算节点$ {N}_{i} $和分片$ {S}_{j} $内的随机节点$ {N}_{j} $在本　　　　轮博弈的收益$ {y}_{i} $和$ {y}_{j} $；

　　根据式(20)计算概率$ {W}({S}_{i}\to {S}_{j}) $；

　　if $ W({S}_{i}\to {S}_{j}) > \mathrm{\omega } $ do

　　　节点$ {N}_{i} $在下一轮切换到分片$ {S}_{j} $；

　　else

　　　节点$ {N}_{i} $保持继续在分片$ {S}_{i} $内；

　　end if

　$t\leftarrow t$+1

　end for

end while

为了验证本文提出的算法能够有效解决分片区块链的可扩展性和安全性均衡问题，同时能解决恶意节点分布不均的问题，本节进行数值仿真分析。

在性能理论分析中，本文均假设系统中每个节点都具有相同的交易处理能力，且每个节点上的交易处理时延一致。区块链网络的交易速率为平均每秒50笔，除非另有说明，否则仿真参数如表1所示。

通过分析在不同网络参数下的网络性能随分片数目的变化情况，来验证本文提出的分析模型的有效性。

仿真实验中设置分片数目为10～100个，步长为10个，恶意节点数目分别设置为$ M=[100,150,200, $$ 250] $。恶意节点随机加入到任意分片中，然后根据式(4)计算分片内交易失效的概率。图1展示了网络包含不同恶意节点数目下的分片交易失效概率。图1表明，当网络恶意节点数为100个、分片数目小于50个时，分片内交易失效概率低于2%。同时，当网络中包含的恶意节点数目一定时，分片数目越多则交易失效概率缓慢上升。此外，还可看到，交易的失效概率随着网络包含的恶意节点数目的增加而增长。这是由于随着越来越多新的恶意节点加入网络，单个分片内可能的恶意节点数目随之变多，导致交易共识失败，这符合理论模型的分析。

图  1  不同分片数目下的交易失效概率

其次，实验分析了不同分片数目对交易吞吐量和交易共识时延的影响。实验设置网络的节点数目为$ N=1\;000 $个，恶意节点数占比10%，即$ M=100 $个。区块大小分别设置为$ {S}^{{\rm{B}}}=\left[\mathrm{50,100,150,200}\right] $ MB。图2为区块大小逐渐增加时的交易平均共识时延。从中可以看出，交易平均共识时延与区块大小和分片数目有关，区块越大则平均时延越高，因为其增加了交易打包到区块的排队时延。

图  2  不同分片数目下的共识时延

图3给出了分片数目对网络交易吞吐量的影响，区块大小分别设置为$ {S}^{{\rm{B}}}=50 $ MB，恶意节点数目$ M=[100,150,\mathrm{200,250}] $。其表明网络交易吞吐量随着分片数目的增加而有效地增长。但当网络恶意节点数目大于200个、分片数目超过90个时，网络交易吞吐量反而下降。这是由于过多的分片数目导致某些分片内包含的恶意节点超过PBFT共识算法的安全性要求，导致分片共识失败。

图  3  不同分片数目下的交易吞吐量

分析基于演化博弈的节点分片选择算法的收敛性，实验设置分片数目为$ {N}_{{\rm{s}}}=4 $个，共识代价为$ {e}=0.01 $，每成功产生一个新区块的成块奖励$ {R}=0.5 $。演化更新的博弈间隔为$ {T}=60 $ s，$ f\left(\theta \right)=\mathrm{l}\mathrm{n}(1+\theta ) $。初始时刻，恶意节点在每个分片内的占比为$ {[x}_{1}^{m},{x}_{2}^{m},{x}_{3}^{m}, $$ {x}_{4}^{m}]=[\mathrm{0.5,0.3,0.2,0}] $。

图4和图5分别给出了4个分片内，恶意节点占比和诚实节点占比的动态演化过程。从图4和图5可以观察到，不同类型的节点在全网的占比随着时间的推移逐渐达到平衡点并稳定下来，最后每个分片内的不同类型节点的占比都接近一致。因此，其证明了本文提出的演化博弈分片选择算法具有收敛性，且能使有限理性的节点最后大概均匀分布于每个分片。

图6展示了每个分片内节点的平均收益，在演化初期，由于第四个分片全为诚实节点，共识的成功率较高，使得该分片内的节点平均收益高于其他3个分片。随着博弈演化，越来越多的恶意节点转移到第四个分片，第四个分片的平均收益逐渐减少，而其他分片的平均收益增加。最后，每个分片内的平均收益都达到均衡，具有相同的平均收益。

图  4  分片内恶意节点占比的动态演化

图  5  分片内诚实节点占比的动态演化

图  6  分片节点的平均收益的动态演化

将提出的基于演化博弈的分片算法(用EGT-Based表示)与Elastico算法^[12]、OmniLedger^[13]算法进行性能比较，对比的指标包括交易吞吐量和分片切换时延。实验设置网络中恶意节点的占比为10%，分片数目为$ {N}_{s}=[1,\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }2,\mathrm{ }4,\mathrm{ }8,\mathrm{ }16] $。OmniLedger算法中无偏差随机数生成方案RandHound的参数$ {c}=16 $。网络连接带宽设置为20 Mbps，节点间通信链路时延为100 ms。

图7给出了在不同分片算法下的分片切换时延对比结果。图7表明，随着分片数目增多，分片切换时延呈现近似线性的增长。其中，Elastico算法的分片切换时延最长，1个分片的时延为109 s，16个分片的时延为743 s。这是因为在Elastico算法中，节点需要花费较多的时间求解PoW难题来加入分片，导致很高的时延。本文提出的EGT-Based算法的分片切换时延要略高于OmniLedger算法，主要由于演化博弈需要进行多轮才能达到均衡，节点需要和邻居节点多次通信，从而导致时延的上升。

图  7  不同分片数目下的分片切换

图8给出了在不同分片算法下的网络交易吞吐量对比，可以看出，随着分片数目增加，本文提出的EGT-Based分片算法的交易吞吐量要明显优于其他两种算法。这是因为恶意节点均匀分布于每个分片，使得单个分片的失效概率接近于0。而在OmniLedger算法中，RandHound方案可能选择恶意节点担任主节点，造成分片的失败。同时，Elastico算法太过频繁进行分片重构，引入较高的分片切换时延，会造成整体的交易吞吐量下降。

图  8  不同分片数目下的交易吞吐量

分片技术有望解决物联网区块链中可扩展性不足的问题。本文首先理论分析了分片区块链的分片安全性和可扩展性。其次，为了均衡分片区块链的可扩展和分片安全性，提出了一种基于演化博弈的分片算法来优化节点分片选择。实验结果表明，本文算法可以有效解决分片区块链中恶意节点分布不均导致的安全性问题，同时能提高网络的可扩展性。在未来的工作中，可以在分片区块链中考虑更多与动态环境相关的因素，如节点的动态加入和退出，将本文提出的基于演化博弈的区块链分片算法应用于真实的物联网中。