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

海 沫 朱建明

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

摘 要 由于区块链网络中的区块链分叉容易引起攻击者进行双重支付攻击,如何减少分叉概率成为一个非常有意义且有挑战性的研究问题.针对已有的通过优化区块链网络中交易和区块的传播机制以减少分叉概率的研究存在的3个问题:仅减少了相邻节点间的传播延迟或传播过程的路由跳数、传播过程产生大量的通信消息、基于传播路径上的节点都会继续传播交易和区块的假设,提出了区块链网络中最优传播路径和激励(optimal propagation path and incentive, OPPI)相结合的传播机制,以减少总传播延迟和通信消息数,从而在传播效率和传播开销之间达到较好的平衡.仿真实验结果表明:和已有的基于Gossip的区块链网络传播机制相比,当网络拓扑结构分别为随机图、无尺度图、小世界网络图时,在节点个数分别为10,100,1 000,10 000且节点度数k分别设置为2,4,8时,OPPI均大幅度减少了总传播延迟和传播过程产生的通信消息数,其将总传播延迟减少了99.4%~99.98%,并将通信消息数减少了99%~99.1%.

关键词 区块链网络;区块链分叉;传播机制;最优传播路径;激励;总传播延迟;通信消息数

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

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

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

(1)

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

因为-Pb>-1并且(1-f(t)) dt≥1,基于伯努力不等式可将式(1)放大近似为[10]

PF≥1Pb×(1-f(t)) dt.

(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 最优传播路径问题的形式化定义

当区块链网络中的某个节点产生一条交易或生成一个区块时,需要对交易和区块进行传播.为了使得交易和区块能够迅速地传播到其他节点,需要构造一条从源节点开始的最优传播路径,该条传播路径使得总传播延迟最小.该问题可形式化为:假定用图G=(V,E,W)表示区块链网络,其中,V表示区块链网络中所有节点构成的集合,E表示区块链网络中已建立的节点间的边集合,W表示边权重集合.节点总数n=|V|,每条边e=(vi,vj|viV,vjV,0≤in-1,0≤jn-1)都有一个权重wε,表示从节点vivj的传播延迟.最优传播路径问题就是找一棵图G的生成树T=(V,E′)|E′⊆E,并且使得总传播延迟最小,即生成图G的最小生成树.

2.2 最优传播路径的生成

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

采用改进的Boruvka算法[31]生成最优传播路径.算法执行完后,每个节点v需要知道其哪些边属于最小生成树.假定最小生成树是唯一的,唯一的最小生成树的连通子树称之为最小生成树片段,或者简称片段.如果对于每个1≤ihFi为最小生成树片段,这些片段之间是不连通的,并且则称集合{F1,F2,…,Fh}为最小生成树森林.对于参数αβ,如果最小生成树森林F最多包含α个片段,片段的最大直径为β,可称F为(α,β)森林.其中,片段Fi的直径为节点对(u,v)|u,vV(Fi)的最大距离,最小生成树森林F的直径为它所有片段直径的最大值.如果对于最小生成树森林F中的每个片段FiF,在最小生成树森林F′中都存在一个片段包含片段Fi,即V(Fi)⊆并且E(Fi)⊆则称最小生成树森林F′是对最小生成树森林F的粗糙化.对于一棵有根树T和树T中的非根节点v,用πT(v)表示树T中节点v的父节点.对于节点v,用id(v)表示节点v的标识符.对于每个片段Fi,有一个指定的根节点rt(Fi),Fi的标识符id(Fi)被设置为根节点rt的标识符id(rt).最优传播路径的生成过程为

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

2) 考虑的情况,其中,D为图G的直径,令假定已经执行了Boruvka算法的j个阶段,该算法从F0开始,得到粗糙森林Fj(j=0,1,2,…),接下来,执行Boruvka算法的下一个阶段,即构建Fj的粗糙森林Fj+1(也是F的粗糙森林).假定每个节点v知道其基片段Fv的标识符,并且知道v所属森林Fj的片段的标识符.对于v的每个邻居u,假定v知道Fu的标识符,同时假定根节点rt知道所有基片段的标识符,且在阶段j(j=0,1,…)开始时,rt知道Fj所有片段的标识符,并且对于每个基片段FiF,根节点知道粗糙化片段的标识符.为了确保归纳基数j=0成立,在构建了基最小生成树森林后,每个节点vFv的标识符更新其邻居节点,同时也在BFS树τ上执行基片段的|F0|≤nk个标识符的向上转型.在每个基片段FiF0上并行地计算连接节点uV(F)和的具有最小权值的边e(u,v).其中,是对基片段Fi进行粗糙化的片段.

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

4) 根节点rt在本地为每个片段计算其最小权重输出边同时在本地计算片段图,其图节点为Fj的片段,图的边为最小权重输出边,并且计算最小生成树森林Fj+1.对于每个基片段FiF,根节点rt知道粗糙化基片段的片段的标识符,并且知道对粗糙化的片段的标识符也对Fi进行了粗糙化).根节点rtτ上共发送了|F|条消息,每条消息的形式为其中,也对Fi进行了粗糙化.每条消息附加了目标区间I(rt(Fi)),并且沿着τ中唯一的从rtrt(Fi)的路径进行路由.

5) 每个基片段FiF的根节点rFi将新的第j+1层的片段的标识符广播给Fi中的所有节点.同时,每个节点v用它的新的第j+1层的片段的标识符对其在G中的邻居节点进行更新.

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验证条件可被形式化为

k≥1,∀

(3)

其中,表示长度为k的传播路径上第i(1≤i<k)个节点所分享的奖励费,表示区块所有者所分享的奖励费.Sybil节点分享的奖励费不超过区块所有者分享的奖励费.

交易传播决定可被理解为博弈游戏中的同时移动,其中一方在采取行动时不知道其他方采取的策略.假定所有节点都是理性的,并且在决定各自行动时,推断其他方也会理性行动.某些节点彼此间会合作.假定相互勾结的邻居彼此已经分享了所有信息,并且作为一个整体采取行动,即组合成可被看成Sybil节点的单个节点.通过理论分析可得出结论1~3.其中,表示已知道交易T的节点集合;表示还不知道交易T的节点集合;表示从节点n的视角所看到的包含了节点n自身的已知道交易T的节点集合;表示从节点n的视角所看到的还不知道交易T的节点集合;π(ni)表示节点ni成为区块所有者的概率,也称为节点ni的能力.

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

结论2. 存在节点∅,其中,n和交易T的客户端节点——cT之间的距离为k.如果

(4)

成立,即:长度为k+1的传播路径上的第k个节点所分享的奖励费和区块所有者所分享的奖励费的比值大于节点n的能力和已知道交易T的节点能力的比值,那么节点n的所有邻居将知道交易表示从节点n的视角所看到的包含了节点n自身的已知道交易T的节点集合.

结论3. 对于某些常量C∈(0,1),令将持续扩展直到没有更多的节点具有中的邻居并且满足固定条件以支持区块所有者,可得到:

(5)

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

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

(6)

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

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

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

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

(7)

进行分享,每个成为区块所有者的概率小于C的理性节点在无需引入Sybil节点的情况下,将被激励以传播交易和区块.式(7)定义的奖励费分享函数将任意交易和区块产生的总奖励费F分配给传播路径上的k个节点.其中,k为传播路径的长度,即:共k个节点参与了交易和区块的验证和传播;总奖励费F包含了验证交易和区块的奖励费以及传播交易和区块的奖励费;表示传播路径上第i(1≤i<k)个节点分享的奖励费,表示区块所有者分享的奖励费,并且满足是基于网络连通性选出的常量.

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

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

对传播路径进行签名的方式如图6所示.节点p为消息M的生成节点.当节点p将消息M转发给节点u之前,首先向节点u询问其公钥u.pk;接着,将消息M、节点u的公钥u.pk和传播费用x,即节点p要求分享的奖励费x,用节点p的私钥p.sk进行签名;最后,节点p将签名后的消息Mpu=(M,u.pk,x)p.sk发送给节点u.该消息通过对节点u的公钥u.pk进行签名以专门发送给节点u,其他节点不能接收.节点u只能继续传播所接收到的经过签名的消息Mpu,而不能传播原始消息M.假设节点u继续将签名后的消息Mpu传播给节点v,节点u将消息Mpu、节点v的公钥v.pk和节点u要求分享的奖励费x′,用节点u的私钥u.sk进行签名,经过签名后的消息为仅节点v才能接收该消息,节点v可以继续向其他节点传播消息Mpuv,其过程和消息Mpu描述的过程类似.如果从节点p传播到节点v后不再进行传播,并且传播消息M的总奖励费用为1,则:节点p分享的奖励费用为x、节点u分享的奖励费用为x′、节点v分享的奖励费用为1-x-x′.

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

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

4 算法的理论分析

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

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

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

(8)

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

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

当删除边和非叶子节点时,维护过程包含节点标记过程和重新生成最优传播路径的过程,每个连通分支并行执行标记过程.其中,每个连通分支标记过程的时间复杂度为O(log n),而最优路径生成算法的时间复杂度为因而,当删除边和非叶子节点时,维护算法的时间复杂度为节点标记过程的消息复杂度为O(n),而最优路径生成算法的消息复杂度为O(|E|log n+n log n×log*n),因而,当删除边和非叶子节点时,维护算法的消息复杂度为O(|E|log n+n log n×log*n+n).

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

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的通信消息数、传播延迟和传播覆盖率进行比较实验.

参考文献

[1]Melanie S. Blockchain: Blueprint for a New Economy[M]. Sebastopol, CA: O’Reilly Media Inc, 2015

[2]Nakamoto S. Bitcoin: A peer-to-peer electronic cash system[OL]. (2008-12-28) [2018-06-09]. https://bitcoin.org/bitcoin.pdf

[3]Shao Qifeng, Jin Cheqing, Zhang Zhao, et al. Blockchain: Architecture and research progress[J]. Chinese Journal of Computers, 2018, 41(5): 969-988 (in Chinese)(邵奇峰, 金澈清, 张召, 等. 区块链技术: 架构及进展[J]. 计算机学报, 2018, 41(5): 969-988)

[4]Qian Weining, Shao Qifeng, Zhu Yanchao, et al. Research problems and methods of blockchain and trusted data management[J]. Journal of Software, 2018, 29(1): 150-159 (in Chinese)(钱卫宁, 邵奇峰, 朱燕超, 等. 区块链与可信数据管理: 问题与方法[J]. 软件学报, 2018, 29(1): 150-159)

[5]Chen Weili, Zheng Zibin. Blockchain data analysis: A review of status, trends and challenges[J]. Journal of Computer Research and Development, 2018, 55(9): 1853-1870 (in Chinese)(陈伟利, 郑子彬. 区块链数据分析: 现状、趋势与挑战[J]. 计算机研究与发展, 2018, 55(9): 1853-1870)

[6]Antonopoulos A M. Mastering Bitcoin: Unlocking Digital Cryptocurrencies[M]. Sebastopol, CA: O’Reilly Media Inc, 2014

[7]Yonatan S, Aviv Z. Accelerating bitcoin’s transaction processing[OL]. (2013-10-30) [2018-06-09]. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.433.6590&rep=rep1&type=pdf

[8]Karame G O, Androulaki E, Capkun S. Two bitcoins at the price of one? Double-spending attacks on fast payments in bitcoin[C] //Proc of the 9th ACM Conf on Computer and Communication Security. New York: ACM, 2012: 1-17

[9]Decker C, Wattenhofer R. Information propagation in the bitcoin network [C] //Proc of the 13th IEEE Int Conf on Peer-to-Peer Computing. Piscataway, NJ: IEEE, 2013: 1-10

[10]Wang Jian, Chen Gongliang. Overview on blockchain fork in bitcoin[J]. Communications Technology, 2018, 51(1): 149-155 (in Chinese)(王健, 陈恭亮. 比特币区块链分叉研究[J]. 通信技术, 2018, 51(1): 149-155)

[11]Yonatan S, Aviv Z. Bitcoin’s underlying incentives[J]. Communications of the ACM, 2018, 61(3): 46-53

[12]Miller A, Laviola J. Anonymous Byzantine consensus from moderately-hard puzzles: A model for bitcoin[OL]. (2014-04-30) [2018-06-09]. https://nakamotoinstitute.org/static/docs/anonymous-byzantine-consensus.pdf

[13]George P, Ilya S. Mechanising blockchain consensus[C] //Proc of the 7th ACM SIGPLAN Int Conf on Certified Programs and Proofs. New York: ACM, 2018: 78-90

[14]Ittai A, Dahlia M. The blockchain consensus layer and BFT[OL]. (2014-04-30) [2018-06-01]. http://eatcs.org/beatcs/index.php/beatcs/article/view/506/495

[15]Baliga A. Understanding blockchain consensus models[OL]. (2017-04-30) [2018-06-01]. https://pdfs.semanticscholar.org/da8a/37b10bc1521a4d3de925d7ebc44bb-606d740.pdf

[16]Neil F. What the fork was that? A forking post mortem[OL]. (2013-03-14) [2018-06-01]. https://mineforeman.com/2013/03/14/what-the-fork-was-that-a-forking-post-mortem

[17]Pappalardo G, Di M T, Caldarelli G, et al. Blockchain inefficiency in the bitcoin peers network[OL]. (2017-04-10) [2018-06-09]. https://arxiv.org/pdf/1704.01414.pdf

[18]Garay J A, Kiayias A, Leonardos N. The bitcoin backbone protocol: Analysis and applications[C] //Proc of the 34th Annual Int Conf on the Theory and Applications of Cryptographic Techniques-Advances in Cryptology. Berlin: Springer, 2015: 281-310

[19]Karame G O, Androulaki E, Roeschlin M, et al. Misbehavior in bitcoin: A study of double-spending and accountability[J]. ACM Transactions on Information and System Security, 2015, 18(1): 1-32

[20]Tobias B, Christian D, Lennart E, et al. Have a snack, pay with bitcoin[C] //Proc of the 13th IEEE Int Conf on Peer-to-Peer Computing. Piscataway, NJ: IEEE, 2013: 20-25

[21]Christian D, Jochen S, Roger W. Bitcoin meets strong consistency[C] //Proc of the 17th Int Conf on Distributed Computing and Networking. New York: ACM, 2016: 1-10

[22]Ittay E, Adem E G, Emin G S, et al. Bitcoin-NG: A scalable blockchain protocol[C] //Proc of the 13th USENIX Symp on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2016: 45-59

[23]Eleftherios K K, Philipp J, Nicolas G, et al. Enhancing bitcoin security and performance with strong consistency via collective signing[C] //Proc of the 25th USENIX Security Symp. Berkeley, CA: USENIX Association, 2016: 279-296

[24]Emmanuelle A, Thibaut L M, Romaric L, et al. Safety analysis of bitcoin improvement proposals[C] //Proc of the 15th IEEE Int Symp on Network Computing and Applications. Piscataway, NJ: IEEE, 2016: 318-325

[25]Thibaut L M, Romaric L, Emmanuelle A. Handling bitcoin conflicts through a glimpse of structure[C] //Proc of the Symp on Applied Computing. New York: ACM, 2017: 444-449

[26]Boyd S, Ghosh A, Prabhakar B, et al. Randomized Gossip algorithms[J]. IEEE Transactions on Information Theory, 2006, 52(6): 2508-2530

[27]Shen Xin, Pei Qingqi, Liu Xuefeng. Survey of blockchain[J]. Chinese Journal of Network and Information Security, 2016, 2(11): 11-20 (in Chinese)(沈鑫, 裴庆祺, 刘雪峰. 区块链技术综述[J]. 网络与信息安全学报, 2016, 2(11): 11-20)

[28]Muntadher F, Gareth O, Mo A. A bitcoin model for evaluation of clustering to improve propagation delay in bitcoin network[C] //Proc of IEEE Int Conf on Computational Science and Engineering. Piscataway, NJ: IEEE, 2016: 468-475

[29]Muntadher F, Gareth O, Mo A. Locality based approach to improve propagation delay on the bitcoin peer-to-peer network[C] //Proc of IEEE Int Symp on Integrated Network Management. Piscataway, NJ: IEEE, 2017: 556-559

[30]Muntadher F, Gareth O, Mo A. Proximity awareness approach to enhance propagation delay on the bitcoin peer-to-peer network[C] //Proc of the 37th IEEE Int Conf on Distributed Computing Systems. Piscataway, NJ: IEEE, 2017: 2411-2416

[31]Michael E. A simple deterministic distributed MST algorithm, with near-optimal time and message complexities[C] //Proc of ACM Symp on Principles of Distributed Computing. New York: ACM, 2017: 157-163

[32]Gu Yu, Yang Jiaxue, Bao Yubin, et al. Vertex-driven parallel minimum spanning tree algorithms on large graphs

[J]. Journal of Computer Research and Development, 2014, 51(12): 2688-2701 (in Chinese)(谷峪, 杨佳学, 鲍玉斌, 等. 大图数据上顶点驱动的并行最小生成树算法[J]. 计算机研究与发展, 2014, 51(12): 2688-2701)

[33]Mark J, Alberto M. PeerSim: A peer-to-peer simulator[OL]. (2018-03-04) [2018-06-01]. http://peersim.sourceforge.net

A Propagation Mechanism Combining an Optimal Propagation Path and Incentive in Blockchain Networks

Hai Mo and Zhu Jianming

(School of Information, Central University of Finance and Economics, Beijing 100081)

Abstract For the blockchain fork in blockchain networks can cause the attacker to perform double-spending attack very easily, how to reduce the fork probability is a very important and challenging research issue. Aiming at three problems of current research on optimizing the propagation mechanism of transactions and blocks in blockchain networks to reduce the fork probability: only the propagation delay between adjacent nodes or the total number of routing hops of the propagation process is reduced; the propagation process generates a large number of communication messages; it is based on the assumption that nodes on the propagation path will continue to propagate transactions and blocks, and a propagation mechanism combining an optimal propagation path and incentive (OPPI) in blockchain networks, is proposed to decrease both the total propagation delay and the number of communication messages, which achieves a tradeoff between the propagation efficiency and the propagation cost. Simulation results show that: compared with the existing propagation mechanism of blockchain networks based on Gossip, when the network topology is random graph, scale-free graph, small-world network graph, the number of nodes is 10, 100, 1 000, 10 000 and the degree k is set to 2, 4, 8 respectively, OPPI reduces both the total propagation delay and the number of communication messages generated by the propagation process significantly, specifically, by 99.4% to 99.98% in the total propagation delay and by 99% to 99.1% in the number of communication messages.

Key words blockchain networks; blockchain fork; propagation mechanism; optimal propagation path; incentive; total propagation delay; number of communication messages

(haimo_hm@163.com)

DOI:10.7544/issn1000-1239.2019.20180419

收稿日期2018-06-07;修回日期:2018-11-13

基金项目国家重点研发计划项目(2017YFB1400700);国家自然科学基金重点项目(U201509214)

This work was supported by the National Key Research and Development Program of China (2017YFB1400700) and the Key Program of the National Natural Science Foundation of China (U201509214).

中图法分类号 TP311

Hai Mo, born in 1978. PhD. Associate professor, master supervisor. Senior member of CCF. Her main research interests include distributed algorithms, blockchain networks, big data analysis.

Zhu Jianming, born in 1965. PhD. Professor, PhD supervisor. Director of CCF. His main research interests include information security, block chain networks. (tyzjm65@163.com)