区块链网络最优传播路径和激励相结合的传播机制

海 沫 朱建明

(中央财经大学信息学院 北京 100081)

区块链是分布式数据存储、点对点传输、共识机制、加密算法等计算机技术在互联网时代的创新应用模式.目前，区块链的应用已延伸到物联网、智能制造、供应链管理、数字资产交易等多个领域[1].区块链源自于比特币的底层技术.2008年，化名为“中本聪”的学者提出了一种被称为比特币的数字货币.传统的货币系统通常由一个统一机构或者权威第三方作为中心节点来处理所有事务，而比特币颠覆了这种设计，使得在没有任何权威中介机构统筹的情况下，互不信任的人可以直接用比特币进行支付，并采用共识和激励机制在点对点网络中维护了一个分布式公共账簿，账簿中的数据通过密码学算法来保证安全性与合法性[2-5].

区块是比特币中用来记录和确认交易的数据结构，它是由区块链网络中一些称为矿工的节点产生的，而矿工构造区块的过程被称为挖矿.一笔交易被创建后会向全网广播，而矿工们则会收集并验证这些交易，并将其中合法的交易数据存储在本地交易池中.在交易达到一定数量后，矿工开始用这些交易数据构造区块.矿工挖矿成功后，会向全网广播其构建的区块，收到区块的节点会验证和确认这个区块，并将合法的区块数据添加到区块链头部，并将它继续向外传播.区块链由许多区块首尾相连而成，每一个区块都记录着系统一段时间内的交易数据.当一个区块b还在传播时另一个冲突的区块b′发现并且被传播时，会产生区块链分叉[6].其中，区块b′是由网络中不知道区块b的节点生成的.文献[7-8]发现：当发生区块链分叉时，在不同分支的区块上可能会存在花费相同比特币的交易，这容易引起攻击者进行双重支付攻击.

文献[9]给出了计算区块链分叉概率P的公式：

(1)

其中，f(t)为区块传播时间t后接收到区块的节点所占百分比；F为离散随机变量，用来统计当某个区块正在传播时其他没有接收到该区块的节点产生的和其冲突的区块个数；Pb为每秒挖出区块的概率，其在所有节点上一致随机分布，生成区块的速度越快，Pb越大.

(2)

式(2)表明：分叉产生概率P和区块产生概率Pb大约成正比.而生成区块的速度越快，Pb越大，分叉产生概率P越大，分叉越容易出现；同时，分叉产生概率P和区块传播速度大约成反比，区块传播速度越快，f(t)越大，分叉产生概率P越小，分叉越不容易出现.由此可见，可通过降低区块产生速度或提高区块传播速度以减少区块链分叉发生的概率，但比特币通过对难度目标值的调整保持了区块产生速度的稳定，因而，找到加速区块传播的方法，对于区块链分叉概率的减少变得尤其重要.

本文的主要贡献有6个方面：

1) 对区块链网络中最优传播路径问题进行了形式化定义，以此为基础提出了具有低时间复杂度和消息复杂度的最优传播路径的生成算法，该算法使得交易和区块从源节点沿着该路径进行传播时具有最低的传播延迟；

2) 提出了当区块链网络拓扑结构的改变导致需要在生成的最优传播路径上删除边和节点、插入边和节点时最优传播路径的增量更新算法，该算法使得所需的时间复杂度和消息复杂度较小；

3) 分析了能够激励生成的最优传播路径上的所有节点对交易和区块进行传播的激励函数需满足的必要条件，并定义了满足该条件的激励函数，即奖励费分享函数，在位于传播路径上的所有节点之间合理分配奖励费，从而激励节点传播交易和区块，以确保交易和区块最终能够到达整个网络；

4) 提出了对传播路径进行签名的方式以保障传播路径的安全性；

5) 对最优传播路径的生成和维护算法的时间复杂度和消息复杂度进行了理论分析；

6) 对提出的区块链传播机制和已有的区块链传播机制在不同网络拓扑结构、节点规模和节点度数下的传播延迟和传播所产生的通信消息数进行了比较.

1 相关工作

目前对区块链分叉问题的解决方法主要有3类：1)通过共识算法[11-19]使得在发生分叉后系统最终收敛成只有一个区块链分支的稳定状态，但该方法并没有减少分叉发生的概率；2)通过指定特殊节点来负责交易及区块验证和确认的全过程[20-24],或加上同步限制以增加交易及区块的验证和确认操作的全局有序性[25]，从而避免分叉的发生，但降低了区块链网络的去中心化特征，并且额外增加的同步限制将导致较大的同步开销；3)通过优化区块链网络中交易和区块的传播方法，以减少分叉发生的概率.其中，通过优化区块链网络中区块和交易的传播方法以减少分叉概率的研究主要可分为3类：优化区块链网络拓扑结构、优化单个节点的传播行为、流水线化传播过程.

1.1 区块链网络拓扑结构的优化

区块链网络采用对等网络组网方式将所有节点连接在一起，网络中每个节点地位对等且以扁平式拓扑结构相互连通和交互，不存在任何中心特殊节点和层级结构，每个节点均会承担网络路由、验证交易和区块、基于Gossip协议[26]传播交易和区块、发现新节点等工作[27].区块链网络中每个节点随机选择邻居节点以建立连接，因而，相邻节点之间的传播延迟可能较长，由此导致交易和区块的传播延迟变长.目前有一些研究工作通过对区块链网络拓扑结构进行优化，以加快交易和区块的传播.

为了最小化任意2个节点之间的路由跳数，文献[9]通过构建一个用作中心通信枢纽的星形子图以连接网络中的每个节点，以减少发送交易及区块的节点和其他节点之间的路由跳数，从而加速交易和区块的传播.文献[4]实现了一个保持有4 000个开放连接的连接池，该连接池能够和每个被宣告地址的节点进行连接，且每次可到达的节点少于4 000个.因而，任何2个连接到中心通信枢纽的节点间的路由跳数为2.文献[28]提出了一种基于超级节点的区块链网络聚类协议——BCBSN(bitcoin clustering based on super node).该协议的目标是在区块链网络中基于节点的局部性进行聚类.在每个聚类中，指定一个节点为聚类头节点以维护整个聚类.每个普通节点仅和一个聚类头节点连接，每个聚类头节点和其他聚类头节点相连，这样减少了传播交易和区块所经过的路由跳数.实验结果表明：BCBSN协议中交易和区块传播延迟的变化幅度随着相连节点个数的增加而增加；随着传播交易和区块所经过的跳数的减少，BCBSN协议中交易和区块传播延迟的变化幅度也随之减少；同一聚类中节点的局部性减少了交易和区块在同一聚类中的传播延迟.文献[29]提出了一种基于地理位置的聚类协议——LBC(location based clustering).LBC协议的目标是通过将区块链网络中的节点按照其地理位置进行聚类以减少区块链网络相邻节点间的距离，从而减少相邻节点的传播延迟.实验结果表明：基于节点地理位置的距离更好地定义了聚类结构，从而优化了交易传播的性能.和BCBSN协议相比，LBC协议能够更有效地减少交易和区块的传播延迟，并且交易和区块的传播延迟的变化幅度比BCBSN协议更小.文献[30]提出了一种基于Ping延迟的区块链网络聚类协议——BCBPT(bitcoin clustering based on ping time).BCBPT协议基于节点间的Ping延迟将节点进行聚类，以减少区块链网络中相邻节点的传播延迟.实验结果表明：相比于基于地理位置的聚类协议——LBC，BCBPT协议中基于Ping延迟的节点间物理距离的度量方式更好地定义了聚类结构，使其能优化交易和区块传播的性能.其性能改进的根本原因在于：地理位置邻近的节点在物理Internet网络上的距离可能相距很远，而采用Ping延迟能更准确地度量节点间的物理距离，从而减少相邻节点间的传播延迟.实验结果表明：物理距离阈值设置得越小，BCBPT协议的交易和区块的传播延迟越小.和LBC协议相比，BCBPT协议能更有效地减少交易和区块的传播延迟，并且其交易和区块的传播延迟的变化幅度比LBC协议更小.

1.2 单个节点传播行为的优化

为了避免将交易和区块发送给已经从其他节点接收到该交易和区块的节点，在传播过程中，节点不直接转发其接收到的交易和区块给邻居节点，而是当完成对交易和区块的验证后，先向邻居节点发送目录消息——inv(inventory),以通知该交易和区块的可用性.交易和区块在单个节点上的转发过程如图1所示[9].其中，inv消息包含了被发送节点A接收到并且可获取的交易和区块的散列值的集合，getdata消息为请求交易和区块的消息.图1表明：一旦节点A完成难度检查以及对交易和区块的验证，该节点通过向邻居节点B发送inv消息以通知该交易和区块的可用性；如果接收到inv消息的邻居节点B发现本地没有该交易和区块，则向节点A发送getdata消息以请求交易和区块；接着，节点A才向节点B发送交易和区块.其中，难度检查包括：节点对接收到的区块进行散列以验证工作量证明，并将计算得到的散列值和当前的难度目标值进行比较.区块链网络中产生的每个交易和区块都按照这样的方式从源节点开始广播到整个网络.交易和区块在传播过程中每经过一个节点都会产生传播延迟，传播延迟由传输时间、难度检查时间、交易和区块的本地验证时间构成.传输时间包括：inv消息、getdata消息、交易和区块消息的传输时间.对区块进行验证时需要对区块中的每个交易进行验证.

Fig. 1 Spreading transaction or block from node A to node B图1 从节点A传播交易和区块到节点B

Fig. 2 Optimization of propagation behavior of a single node图2 单个节点传播行为的优化

由此可见，导致区块链网络中区块传播延迟的主要因素为：节点在将区块广播到网络之前验证区块所花费的时间.区块验证时间和区块大小有密切关系.由于传播过程中每一跳上的节点在将其转发给邻居节点之前都需要验证该区块，因而，传播延迟和传播路径的长度成正比.区块验证过程可分为2个阶段：难度检查和区块中交易的验证.难度检查包括：节点对接收到的区块进行散列以验证工作量，并将计算得到的散列值和当前的难度目标值进行比较.此外，节点还将检查接收到的新区块是否为最近接收到的旧区块的副本，并且将最近接收到的旧区块作为它的前继节点以证明新区块不是旧区块的重新提交.区块中的每个交易都需要验证.只要难度检查已经完成，在对区块或交易进行验证前，可将区块或交易转发到邻居节点.因而，文献[9]提出：可将每个节点的传播行为改变为：一旦难度检查完成，节点就会发送一条inv消息，而不是等待更长时间的交易和区块验证完成后才发送inv消息，并且在对区块或交易进行验证前，可将交易和区块转发到邻居节点，如图2所示.然而，任何对网络中节点传播行为的改变都必须被审查以降低被攻击者滥用从而损害网络的可能性.特别是，转发未经验证的交易和区块可能允许攻击者发送任意数量的数据，这些数据被立即转发至网络中的某些节点，从而导致分布式拒绝服务攻击.然而，由于生成一个能通过难度检查的非法区块和生成一个合法区块具有同等难度，对节点传播行为的这种改变并没有增加拒绝服务攻击的风险.虽然该方法加速了传播路径上每跳的传播，但如果仅在连接度不高的单个节点上实施，则对总传播延迟减少的影响较小.

1.3 传播过程的流水线化

文献[9]提出将区块和交易传播过程流水线化的方法，即：一旦节点接收到inv消息，将立即将该消息转发给邻居节点，而无需先进行难度检查以及区块或交易的验证.如图3所示，节点A接收到inv消息后，立即转发给邻居节点B.该方法通过提早宣告区块或交易的可用性，以减少邻居节点之间的往返时间.所接收到的getdata消息将排队一直到该区块或交易被接收，并且已经完成难度检查后，区块或交易将发送给请求它的邻居节点.攻击者可能会宣告任意数量的区块或交易但不能提供所请求的区块或交易.接收这些垃圾宣告信息的节点会将它们转发给邻居节点.一旦节点检测到某个邻居节点正在宣告一个它不能提供的区块或交易，该节点会转变成原来的行为：在宣告区块或交易之前首先验证区块或交易.即使该方法会导致节点转发不能提供区块或交易的inv消息，但是由于inv消息很小，所以其对传播延迟的影响很小.虽然该方法加速了传播路径上每跳的传播，但如果仅在连接度不高的单个节点上实施，则对总传播延迟减少的影响较小.

Fig.3 Immediate forwarding of inv message图3 inv消息的立即转发

综上所述，已有的通过优化区块链网络中交易和区块的传播方法以减少分叉概率的研究采取优化区块链网络拓扑结构、优化单个节点传播行为、流水线化传播过程3种方法，在一定程度上加快了区块链网络中交易和区块的传播，然而仍然存在3点不足：

1) 减少了相邻节点间的传播延迟或减少了传播所需的路由跳数，但不一定会减少总传播延迟；

2) 采用的基于Gossip协议的传播方式会导致环路，从而在网络中产生大量的通信消息；

3) 基于传播路径上的节点都会继续传播所接收到的交易和区块的假设，但实际上某些节点会选择不继续传播交易和区块.

本文针对这3个问题，首先以较低的时间复杂度和消息复杂度生成和维护总传播延迟最小的最优传播路径，并定义激励传播路径上的每个节点进行传播的激励函数，使得在产生的通信消息较少的情况下，交易和区块能够迅速地传播到整个网络.

2 最优传播路径和激励(optimal propagation path and incentive, OPPI)相结合的传播机制

首先对区块链网络中的最优传播路径问题进行形式化定义，以此为基础研究如何在较短的时间内、在产生的通信消息数较少的情况下，生成最优的传播路径，使得交易和区块沿着该路径传播时具有最低的总传播延迟；并研究当区块链网络拓扑改变时，如何以增量方式更新最优传播路径，使得所需的时间复杂度和消息复杂度较小；进一步定义能够激励生成的最优传播路径上的所有节点对交易和区块进行传播的激励函数.

2.1 最优传播路径问题的形式化定义

2.2 最优传播路径的生成

假定区块链网络中节点之间的通信模型为分布式通信的同步拥塞模型.图G=(V,E,W)中的每个节点v在单个处理器上运行，这些处理器基于同步循环中的O(logn)条消息相互通信.假定所有边的权重最多为n的多项式，或者将消息大小限制为边权重的O(1)倍或节点标识符大小.开始通信时，每个节点v知道它唯一的节点标识符，用id(v)表示.

1) 为根节点为rt的图G构造1棵辅助的宽度优先搜索(breadth first search, BFS)树τ.每个基片段Fi∈F都有其指定的根节点rFi.树τ中的每个节点v都能够将消息从树τ的根节点rt路由到每个基片段Fi的根节点rFi.其中，每个基片段属于根节点为v的树τ的子树τv.需为每个节点v∈V(τ)计算其区间，例如对于V中的每个节点对(u,v)，如果它们分别属于树τ的不同分支，则它们的区间不相交；如果具有更长区间的节点在树τ中是具有更短区间的节点的祖先节点，则它们的区间嵌套.给定这些区间，当节点v需要将消息路由到基片段Fi(其中的每个节点∈V(τV))的根节点rFi，它将找到节点v的孩子节点u，它的区间I(u)包含了I(rFi)，并将消息发送给节点u.

3) 在附属BFS树τ上发送所有共O(nk)=条消息到树τ的根节点rt上，这通过流水线化的收敛广播过程完成.其中，树τ的每个中间节点u向其父点πτ(u)转发每个片段上权值最小的边，这些边初始时存储在树τ的根节点为u的子树τu的节点集合z的某个节点上.

2.3 最优传播路径的更新

当区块链网络拓扑结构的改变导致需要在生成的最优传播路径上删除边和节点时，可采用基于节点标记的更新策略更新最优传播路径[32].如图4所示，当删除边e(1,4)时，生成的最优传播路径变成2个不同的连通分量.分别为节点1和节点4赋予标记1和标记2，然后，节点1将自己所属的连通分量上的节点2，3，5都标记为1，节点4将自己所属的连通分量上的节点4和节点6都标记为2.在产生的2个新的连通分量上运行最优传播路径生成算法，即可生成新的最优传播路径.删除多条边时，为每条被删除边创建一个线程，分别运行基于标记的更新算法.当被删除节点v为叶子节点时，不需要更新；如果被删除节点v为非叶子节点时，为其不同的邻居节点赋予不同的标识符，这些邻居节点将各自发起标记过程，用其标识符标记其所属的连通分量中的所有节点.如果删除度为d的非叶子节点v，则会产生d个不同的连通分量，在这d个连通分量上运行最优传播路径生成算法，即可生成新的最优传播路径.

Fig. 4 Marking process of nodes when deleting a single edge图4 删除边时的节点标记过程

Fig. 5 Updating process of optimal propagation path when inserting a single edge图5 插入边时的最优传播路径更新过程

当插入边时，可通过新插入边的2个节点找到它们的标识符最小的共同祖先，进而找到插入边后所产生的环路，然后删除环路中的最大权重边即可得到新的最优传播路径.如图5所示，当插入边(2,3)时，首先找到节点2和节点3的具有最小标识符的共同祖先——节点1，进而发现了环路(1,2,3)，由于边(1,2)的权重最大，删除该边后，将得到新的最优传播路径.当插入新节点时，新的节点将和区块链网络中已有的某些节点相连，因而会产生一些新的边.按照这些边的权重从小到大的顺序，依次执行插入边时的最优传播路径更新算法即可完成插入新节点时最优传播路径的更新.

2.4 激励函数的定义

考虑1连通网络和其他类型网络下的Sybil验证问题.其中，k连通网络意味着移除k-1个节点不会使得网络不连通.Sybil节点是和原始节点具有相同邻居节点的伪造节点，它不会增加网络连通性，也没有增加其成为区块所有者的概率.为了使得在1连通网络中不引入Sybil节点，需要在第1个传播节点和区块所有者之间共享奖励费，即:使得1连通网络不可能存在Sybil验证激励机制.在2连通网络中，任意2个节点间存在包含客户端节点和区块所有者节点的多条路径，节点通过遵循Sybil验证条件而对引入Sybil节点失去动力.Sybil验证条件可被形式化为

(3)

结论1.节点的传播决定和其邻居节点成为区块拥有者的概率无关，而和自己相对其他节点知道交易的相对概率相关，并且，理性节点会将交易传播给所有节点或者不传播给任何节点.

(4)

(5)

式(5)表明：长度为k+1的传播路径上的第k个节点所分享的奖励费为区块所有者所分享奖励费的常数倍.

从结论1可知，邻居节点成为区块拥有者的概率对节点的传播决定没有任何影响.除非获得的奖励费减少，这由以后诸如增加路径长度之类的行动所导致，否则将满足结论1.如果传播节点所分享的奖励费没有随着路径长度的增加而增加，那么传播节点将不受任何以后行动的影响，这可被形式化为

(6)

基于以上分析，可得出一个理想的奖励费分享函数应满足的必要条件为

1) 将Sybil节点引入网络不会对传播路径上的节点产生任何有利影响；

2) 对于理性节点应该有足够的激励机制使其愿意传播交易和区块，并使得交易和区块最终能够到达整个网络.

基于这2个必要条件和式(3)(5)(6)，可推出：在n连通(n≥2)网络中，如果总奖励费F基于

(7)

3 传播路径的安全性保障方法

可采用对最优传播路径进行签名的方式以保障传播路径的安全性.用M表示被传播的交易或区块消息.当节点u将消息M传播给节点v后，节点u会得到相应的奖励费.首先必须确保节点v不能否认它是从节点u接收到消息M的事实.如果节点u仅对消息M进行签名，节点v一旦接收到消息，可以创建一个虚假节点w对消息M进行签名，并宣称消息M是从节点w发送给节点v的.如果节点u对消息M加密，接收到消息M的节点v将不能验证其真实性.因而，在传播路径的每跳上，基于发送节点的私钥对消息M、接收节点的公钥和要求分享的奖励费x进行签名.用u.pk和u.sk分别表示节点u的公钥和私钥，对节点v和节点p的公钥和私钥的表示方式类似.

Fig. 6 The signature method of propagation path图6 传播路径的签名方式

当且仅当被传播的消息M从生成它的源节点p开始传播，并且传播过程中每跳的发送节点均为上一跳的接收节点时，才称传播路径是安全的.而以上对传播路径进行签名的方式确保了传播过程中每跳的发送节点均为上一跳的接收节点，因而保障了传播路径的安全性.

4 算法的理论分析

4.1 最优传播路径生成算法的复杂度分析

最优路径生成算法中，每个节点v用Fv的标识符更新其邻居节点过程的时间复杂度为O(1)，在BFS树τ上执行基片段的|F0|≤nk个标识符的向上转型过程的时间复杂度为O(D+nk)，在每个基片段Fi∈F0上并行地计算连接节点u∈V(F)和的具有最小权值的边e(u,v)的过程的时间复杂度为O(k)，在附属BFS树τ上发送所有共O(nk)条消息到树τ的根节点rt上的流水线化广播过程的时间复杂度为O(D+|Fj|)，在本地计算片段图过程的时间复杂度为O(D+|F|)，每个基片段Fi∈F的根节点r(Fi)将新的第j+1层的片段的标识符广播给Fi中所有节点的过程的时间复杂度为O(k)，每个节点v用它的新的第j+1层的片段的标识符对其在G中的邻居节点进行更新的过程的时间复杂度为O(1).并且对于每个j=0,1,2,…，都有其中，Fj+1和Fj为粗糙森林，阶段数l=O(logn).因而，其时间复杂度为

O(D+nk)+O(k×log*n)+
O((D+k+|F|)×logn)=
O((D+k+nk)

(8)

构建最小生成树森林F的消息复杂度为O(|E|logn+nlogn×log*n)，计算区间的消息复杂度为O(D×nk+n)，每个后续阶段的消息复杂度为O(D×nk+|E|+n).当D≤k时，总消息复杂度为O(|E|logn+nlogn×log*n).对于当参数k=D时，计算(nk,O(k))最小生成树森林F=F0共需要的时间为O(D×log*n)，共产生的消息数为O(|E|logn+nlogn×log*n).对于每个j=0,1,2,…，算法第j个阶段所需时间为O(D+k+|F|)=O(D+k+nk)=O(D)，即所有阶段共需时间为O(Dlogn).因而，最优路径生成算法的时间复杂度为每个阶段产生的消息数为O(|E|+n+D×|F|)，即所有l个阶段共产生消息O((|E|+n)×logn)，因而，最优路径生成算法的消息复杂度为O(|E|logn+nlogn×log*n).

4.2 最优传播路径维护算法的复杂度分析

插入边时，插入边的时间复杂度和消息复杂度均为O(1)，找到插入边后所产生的环路上权重最大边的时间复杂度和消息复杂度均为O(logn)，而删除环路上权重最大边的时间复杂度和消息复杂度均为O(1)，因而，插入边时最优传播路径维护算法的时间复杂度和消息复杂度均为O(logn).插入节点的过程等价于插入多条边的过程，因而，插入节点时维护算法的时间复杂度和消息复杂度均为O(logn).

5 实验与结果

5.1 实验环境和设置

采用Peersim-1.0.5[33]分别生成3种不同的区块链网络拓扑结构：随机图、基于Barabasi-Albert模型的无尺度网络图、基于Watts-Strogatz的小世界网络图.基于事件驱动的方式对区块链网络中基于Gossip协议的传播机制、本文提出的最优传播路径和激励(OPPI)相结合的传播机制进行模拟.节点个数n分别设置为10，100，1 000，10 000；节点间的传播延迟设置为区间[1,100]的符合一致随机分布的整数；节点度数k分别设置为2，4，8；小世界模型图中节点重连线的概率β设置为0.8.用从源节点传播交易和区块到其他节点过程中产生的通信消息数测量传播开销，用所花费的传播延迟测量传播效率.

5.2 实验结果

为了使得实验结果看起来更直观，分别对通信消息数和传播延迟取10的对数.每种实验分别执行10次，实验结果取10次的平均值.

1) 通信消息数

为了观察节点个数对消息数的影响，图7～9分别对网络拓扑结构为随机图、无尺度BA图和小世界网络图时在不同节点个数下Gossip和OPPI的通信消息数进行了比较.

Fig. 7 Comparison of number of messages of Gossip and OPPI (random graph)图7 Gossip和OPPI的消息数比较(随机图)

Fig. 8 Comparison of number of messages of Gossip and OPPI (scale-free BA graph)图8 Gossip和OPPI的消息数比较(无尺度BA图)

Fig. 9 Comparison of number of messages of Gossip and OPPI (small-world graph)图9 Gossip和OPPI的消息数比较(小世界网络图)

为了观察节点度数k对消息数的影响，图10对节点个数为1 000的情况下，在不同节点度数k下，Gossip和OPPI的消息数进行了比较.为了观察网络拓扑结构对消息数的影响，图11对节点个数为1 000的情况下，在不同网络拓扑结构下，Gossip和OPPI的消息数进行了比较.

Fig. 10 Comparison of number of messages of Gossip and OPPI when the number of nodes is 1 000 and k is set to a different value图10 节点数为1 000且k取不同值时Gossip和OPPI的消息数对比

Fig. 11 Comparison of number of messages of Gossip and OPPI when the number of nodes is 1 000 and the topology is different图11 节点数为1 000且在不同拓扑结构下Gossip和OPPI的消息数对比

实验结果表明：基于Gossip的传播机制和基于OPPI的传播机制所产生的消息数都随着节点个数的增加而近似线性增长；节点度数k和网络拓扑结构改变对这2种传播机制所产生的消息数几乎没有影响；在节点个数、节点度数k和网络拓扑结构都相同的情况下，相比于基于Gossip的传播机制，OPPI传播过程所产生的消息数减少了99%～99.1%.这是因为：Gossip协议中，节点会定期随机选取邻居节点转发消息，而收到消息的节点也会重复该步骤，因此就不可避免地存在消息重复发送给同一节点的情况，造成了消息的冗余，而且，由于是定期发送，因此，即使收到了消息的节点还会反复收到重复消息，加重了消息的冗余.OPPI产生的消息数为O(n)，而Gossip产生的消息数为O(n2)，因而，相比于OPPI，基于Gossip的传播机制在网络中会产生大量的通信消息.

2) 传播延迟

为了观察节点个数对传播延迟的影响，图12～14对网络拓扑结构分别为随机图、无尺度BA图和小世界网络图时，在不同节点个数下，Gossip和OPPI的传播延迟进行了比较.

Fig. 12 Comparison of propagation delay of Gossip and OPPI (random graph)图12 Gossip和OPPI的传播延迟比较(随机图)

Fig. 13 Comparison of propagation delay of Gossip and OPPI (scale-free BA graph)图13 Gossip和OPPI的传播延迟比较(无尺度BA图)

Fig. 14 Comparison of propagation delay of Gossip and OPPI (small-world graph)图14 Gossip和OPPI的传播延迟比较(小世界网络图)

为了观察节点度数k对传播延迟的影响，图15对节点个数为1 000的情况下，在不同节点度数k下，Gossip和OPPI的消息数进行了比较.为了观察网络拓扑结构对传播延迟的影响，图16对节点个数为1 000的情况下，在不同网络拓扑结构下，Gossip和OPPI的传播延迟进行了比较.

Fig. 15 Comparison of propagation delay of Gossip and OPPI when the number of nodes is 1 000 and k is set to a different value图15 节点数为1 000且k取不同值时Gossip和OPPI的传播延迟对比

Fig. 16 Comparison of propagation delay of Gossip and OPPI when the number of nodes is 1 000 and the topology is different图16 节点数为1 000且在不同拓扑结构下Gossip和OPPI的传播延迟对比

实验结果表明：随着节点个数的增加，Gossip和OPPI的传播延迟近似线性增长；节点度数k和网络拓扑结构的改变对Gossip和OPPI的传播延迟几乎没有影响；在节点个数、节点度数k和网络拓扑结构相同的情况下，相比于基于Gossip的传播机制，OPPI的传播延迟减少了99.4%～99.98%.这是因为：Gossip和OPPI的传播延迟只和节点个数相关，并且OPPI中交易和区块是沿着具有最小传播延迟的传播路径传播，而Gossip在传播过程中随机选取邻居节点进行转发并产生环路，从而增加了传播延迟.

以上实验结果表明：Gossip和OPPI的消息数及传播延迟都和节点个数密切相关；相比于Gossip，OPPI对通信消息数和传播延迟减少的效果显著，较好地解决了基于Gossip的传播方式产生的通信消息数过多并且传播延迟过长的问题，在传播效率和传播开销之间达到了较好的平衡.

6 总 结

本文首先分析了区块链中区块的传播速度和区块链分叉概率的定量关系，并对已有的通过优化区块链网络中交易和区块的传播方法以减少分叉概率的研究进行了分析，总结了已有研究存在的3个问题：1)只减少相邻节点间的传播延迟或传播的路由跳数，并未减少总传播延迟;2)传播过程产生大量的通信消息;3)基于传播路径上的节点都会继续传播交易和区块的假设.针对这些问题，提出了区块链网络中最优传播路径和激励(OPPI)相结合的传播机制.实验结果表明：和已有的基于Gossip的区块链网络传播机制相比，OPPI大幅度减少了消息数和传播延迟.其中，相比于Gossip，OPPI的消息数减少了99%～99.1%，OPPI的传播延迟减少了99.4%～99.98%.下一步将对传播路径上的某些节点不愿意继续传播所接收到的交易和区块的情况进行模拟，比较该情况下Gossip和OPPI的传播覆盖率，并在真实区块链网络上对Gossip和OPPI的通信消息数、传播延迟和传播覆盖率进行比较实验.