物联网区块链中基于演化博弈的分片算法

徐小琼，孙 罡，罗 龙

(电子科技大学光纤传感与通信教育部重点实验室 成都 611731)

物联网在传统互联网的基础上，通过传感器网络赋予物体互联互通的能力，因此极大程度地降低了日常生产和运营的成本[1]。但随着物联网设备的急剧增长和服务的广泛部署，其网络性能受到边缘终端设备以及云服务器传输宽带的制约，使得物联网传输速率劣化，带来了一定的安全隐患[2]。同时，对数据进行中心化管理使得物联网设备隐私安全性得不到保障。因此，物联网系统不可避免地存在诸如用户隐私泄露、DDoS 攻击等安全性的问题[3]。

区块链的出现为物联网下实现安全、高效的数据交互和隐私保护提供了新的解决方案[4]。区块链是一个新型的分布式数据账本，其可以对不断增长的物联网数据进行记录和维护以防止伪造和非法篡改。区块链通过密码学技术对数据进行加密，并将数据以区块的形式进行存储且将相关联的数据区块进行链状串联。这种链状的结构能利用Merkle Tree 对数据进行校验，从而判断区块内的数据是否被篡改[5]。但由于现有的区块链架构存在可扩展性低、交易时延高的性能缺陷，仍不能很好地支撑物联网业务[6]。

为了满足区块链在物联网场景下的应用需求，近年来，已有一系列的区块链性能优化方案被提出。其中，网络分片被认为是解决区块链可扩展性问题及提升区块链性能最主要的技术之一[7-10]。分片通过将整个区块链网络拆分为多个子网络，每个子网络由一个不同的节点集合进行维护，交易在不同的子网络内并行处理。由于每个区块链节点不必处理系统中所有的交易，因此极大地提升了网络的交易处理性能。尽管如此，现有的区块链分片算法仍存在一些挑战[8]。首先，网络分片大小是需要考虑的问题，当网络分片数目较多，即每个分片内节点较少时，会导致共识的安全性问题。相反，当网络分片数目较少，则可并行的交易处理能力不够，网络性能无法满足应用需求。因此，在实际应用中，如何选择分片大小以平衡安全性和网络性能需求是需要解决的问题。其次，在基于实际拜占庭 容 错(practical byzantine fault tolerance, PBFT)共识算法的区块链网络中[11]，恶意节点的随机分布会导致某个分片内的恶意节点数目大于分片中所有节点的三分之一，这会出现个别分片无法对交易达成共识，进而产生分片失效的问题。因此，如何使恶意节点尽可能均匀地分布在不同的分片内以满足分片有效性是需要解决的又一问题。

针对这些问题，本文提出分片区块链安全性和可扩展性的理论分析模型。其次，基于提出的分析模型建立优化求解问题来解决可扩展性和安全性均衡问题。最后，基于演化博弈论得到较优的区块链分片算法使恶意节点尽可能地均匀分布于每个分片中。仿真结果表明，本文算法可以使不同类型节点的分布动态演化收敛到接近最优的均衡点，达到节点均匀分布的目的，进而在支持物联网应用的区块链中获得更好的性能。

1 相关工作

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

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

2 分片性能分析

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

2.1 分析模型

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

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

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

2.1.1 失效概率分析模型

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

2.1.2 网络交易吞吐量分析模型

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

2.1.3 交易平均时延分析模型

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

2.2 分片优化问题

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

f+1

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

3 基于演化博弈的节点分片选择

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

3.1 节点分片选择的演化博弈问题

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

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

3.2 收益函数

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

3.3 演化更新

4 实验结果

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

4.1 仿真参数配置

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

表1 仿真参数

4.2 分析模型验证

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

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

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

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

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

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

4.3 演化收敛性分析

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

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

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

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

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

4.4 性能对比分析

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

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

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

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

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

5 结 束 语

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