基于离散时间G-限量排队的区块链系统的社会最优①

袁红莉 张大鹏 金顺福

(燕山大学信息科学与工程学院 秦皇岛 066004)

0 引 言

区块链是一个由系统中所有节点集体维护的分布式数据库，具有去中心化、不可篡改、数据透明及交易安全等特性。区块链概念在2008年被提出，并于2009年1月正式发布[1]。如今历经10余年的发展，区块链技术不断推广，其应用已延伸到金融、医疗、通信等领域。

区块链技术凭借自身的优势推动着众多领域的创新。Khaqqi等人[2]提出了一种基于信息化与自动化的新型排放交易政策(emission trading scheme，ETS)，利用区块链技术和防篡改智能仪表保证了数据的透明性和可信性。基于多准则分析法的结果表明，所提方案可以实现减少排放量并鼓励长期采用减排技术的双重目标。Zyskind等人[3]建立了一个去中心化的个人数据管理平台，将区块链与区块外存储相结合，使用户在接受第三方服务时，可以拥有和控制自己的数据，提高了数据的安全性。Fu和Fang[4]在文献[3]的基础上引入权益证明(proof-of-stake，POS)与可信任证明(proof-of-credibility score，POCS)的混合机制进行“挖矿”，基于节点之间的连接程度衡量节点的工作量。上述文献主要集中于区块链技术的应用研究。

自2016年起，部分学者基于排队论方法对区块链基础理论进行了研究。Kasahara等人[5,6]建立了一个批量服务的M/Gb/1模型，使用补充变量法得到了稳态下系统中的平均交易数及交易平均确认时间。然而，该模型没有体现区块的生成过程与区块链的建立过程。Li等人[7]提出了一种批量服务的GI/M/1型随机排队模型，用矩阵几何解方法得到了稳态下系统中的平均交易数、每个区块内的平均交易数及交易平均确认时间。与文献[5,6]相比，该模型的服务过程包含了区块的生成过程和区块链的建立过程2个阶段。要指出的是，上述文献均未考虑空块coinbase交易，并缺少对矿工收益的研究。

本文将区块的生成过程抽象为休假，区块链的建立过程抽象为服务，考虑区块容量，在离散时域下建立带有批量服务及空载服务期的G-限量休假模型。利用再生循环法，求得稳态下交易平均确认时间，研究区块容量、挖矿系数与交易到达率对区块链系统性能的影响。结合博弈理论，构建收益函数，在完全不可见情形下得到交易的纳什均衡到达率与社会最优到达率。改进布谷鸟寻优算法，以区块链系统社会收益最大化为目标，面向交易制定合理的收费方案。

1 区块链交易确认过程及系统模型

1.1 交易确认过程

区块链是一种把区块以链的方式组织在一起的数据结构，主要解决在没有第三方信任机构参与的情况下如何在所有节点之间达成共识的问题。专注于一个矿工，给出区块链中的交易确认过程如图1所示。

图1 区块链中的交易确认过程

区块链系统中的交易不断产生。用户产生某笔交易后，需要广播该交易至区块链系统中的所有矿工。每个矿工先进行交易验证，再把验证通过的交易放入各自的内存池中。争夺区块记账权的矿工从内存池中选出交易构建候选区块，并通过求解数学难题，即挖矿过程，进行工作量证明。获胜矿工的候选区块升级为新区块，同时将新区块广播给其余未获胜矿工。未获胜矿工首先将各自的候选区块作废并验证收到的新区块，然后将验证结果发送给获胜矿工。只有当成功验证新区块的矿工数目超过系统规定的阈值时，获胜矿工才可以将新区块接入区块链，并反馈新区块确认消息给其余矿工。获胜矿工之外的所有矿工收到新区块确认消息后，从各自的内存池中清除新区块中所含的交易。若新区块是空块，获胜矿工直接将新区块接入区块链。

由图1可知，区块链交易的一个生命周期由交易产生、交易传播、交易放入区块及区块接入区块链构成。

在区块链系统中，区块容量、挖矿系数及单位时间内到达的交易数目等都会影响交易用户的体验质量(quality of experience，QoE)。为了提高区块链系统的性能，需要建立合理的数学模型，定量刻画交易平均确认时间的变化趋势。

1.2 新型G-限量休假模型

由区块链系统中的交易确认过程可知，每个区块的容量均有上限，且一个区块内的所有交易同时得到验证。将挖矿过程视为休假，空块接入区块链的过程视为空载服务期，非空新区块的验证(假设每个区块均可以通过验证)及接入区块链的过程视为普通服务期，建立一种带有批量服务及空载服务期的新型G-限量休假模型。该模型的状态转移过程如图2所示。

图2 新型G-限量休假模型的状态转移

休假期内，矿工求解数学难题。数学题越难，即挖矿系数越小，休假期越长。难题求解成功后，休假结束。此时，若获胜矿工产生的新区块为空块，系统转入空载服务期，否则转入普通服务期。

若系统转入空载服务期，获胜矿工将空块接入区块链后，空载服务期结束。若系统转入普通服务期，获胜矿工之外的所有矿工验证非空新区块内的交易，获胜矿工将非空新区块接入区块链后，普通服务期结束。任何一个服务期结束，系统均返回休假期，进行下一次的挖矿过程。相邻2次挖矿过程起始点之间的时间长度称为一个挖矿循环。

区块链系统中的状态转移持续进行。与已有模型不同，新型G-限量休假模型中交易验证呈现出批量服务特点且具有空载服务期。

2 模型解析

在离散时间排队系统中，交易的到达和离去均只能发生在单位时隙处，假设交易的到达与离去分别发生在时隙末端与时隙首端，且在该时隙末端到达的交易不会在此时隙首端离去，将会在下一个时隙首端离去。

文献[5-7]对新型G-限量休假模型作出如下假设。

空载服务期与普通服务期形态相同，简称为服务期。服务期的时间长度S服从一般分布，其概率分布、均值和母函数分别为

bk=P{S=k}，k≥1

令AS表示一个服务期内到达的交易数量，其概率分布和母函数分别为

aj=P{AS=j}

休假期的时间长度V服从一般分布，其概率分布、均值和母函数分别为

vk=P{V=k}，k≥1

按照先到先服务的规则将交易放入区块，且每个区块最多可容纳M个交易。将一个服务期与其后的休假期之和称为忙循环。当一个忙循环内平均到达的交易数小于区块容量，即p(E[V]+E[S])

2.1 服务期开始时刻的交易数母函数

令Qb表示一个服务期开始时刻系统内的交易数，其概率分布和母函数分别为

qk=p{Qb=k}，k≥0

考虑相继2个服务期开始时刻系统内的交易数，有：

对上式取母函数，可得：

(1)

引入部分母函数，可得：

式(1)可改写为

(2)

引理1对任意小实数ε>0，当|z|=1+ε时，一个非负整数随机变量C的母函数满足如下不等式：

|C(z)|≤1+εE[C]+ο(ε)

其中，|C(z)|为母函数C(z)的模，E[C]为随机变量C的均值。

证明令一个非负整数随机变量C的概率分布和母函数分别为ck和C(z)。

ck=P{C=k}，k≥0

对任意小实数ε>0，当|z|=1+ε时，有：

(3)

根据泰勒公式[8]，可得：

=1+εE[C]+ο(ε)

(4)

综合式(3)和式(4)，可得：

|C(z)|≤1+εE[C]+ο(ε)

证毕。

由式(2)可知，为了确定服务期开始时刻的交易数母函数Qb(z)，必须给出部分母函数QM(z)的系数q0,q1, …,qM-1。

在式(2)的分母中，令g(z)=-S(Λ(z))V(Λ(z))，由引理1可得：

|g(z)|≤1+εp(E[V]+E[S])+ο(ε)

(5)

令f(z)=zM，根据泰勒公式[8]，f(z)表示为

|f(z)|=(1+ε)M=1+εM+ο(ε)

(6)

综合式(5)和式(6)，在系统稳态条件p(E[V]+E[S])

f(z)在|z|=1+ε内有M个零点。由Rouche定理[9]可知，g(z)+f(z)在|z|=1+ε内也有M个零点，即式(2)的分母有M个零点。略去零点z=1，其他M-1个零点记为zm，m=1,…,M-1。

式(2)的分子与分母有相同的零点，给出M-1个方程如下：

(7)

在式(2)中，令z=1，使用洛必达法则，给出方程如下：

(8)

结合式(7)和式(8)可唯一确定部分母函数QM(z)的系数q0,q1,…,qM-1，进而可以给出服务期开始时刻交易数母函数Qb(z)。

2.2 交易平均确认

交易确认时间定义为从一个交易进入区块链系统到包含这笔交易的区块接入到区块链为止的时间间隔，记为T。

处理非空竭休假模型的常用工具之一是再生循环法[10]。使用该方法需要给出一个服务期内平均服务的交易数和每个交易服务完成时刻系统内尚存交易数的母函数。

E[Φ]=p(E[V]+E[S])

(9)

一个区块内的交易是批量服务的，为了方便解析，人为设定区块内的交易顺序，但是不同交易服务完成时刻的间隔为0。

令Ln表示一个区块内的第n个交易服务完成时刻系统内尚存交易的数量，则Ln=Qb+As-n，n=1,…,Φ。Ln的母函数Ln(z)为

Ln(z)=E[zQb+As-n]

利用再生循环法和PASTA性质[11]，得到稳态下任意时刻系统内的交易数母函数L(z)为

将式(2)代入上式，整理后可得：

L(z)=

(10)

对式(10)求导，令z=1，可得任意时刻系统内的交易数均值E[L]为

(11)

由Little公式[12]可得，交易平均确认时间E[T]为

(12)

直观地，交易平均确认时间随交易到达率单调不减。为了在不同的区块容量与挖矿系数下定量刻画交易平均确认时间的变化趋势，需进行系统实验。

3 交易平均确认时间的系统实验

实验所用CPU型号为Intel(R) Core(TM) i7-4790，CPU运行频率为3.60 GHz，系统内存为8.00 GB。数值实验在Matlab 2016a环境中运行，仿真实验在Myeclipse 2014环境中采用Java语言实现。

文献[13,14]假设挖矿过程服从参数为θ的几何分布，服务期的时间长度服从参数为μ的几何分布，进行数值实验与仿真实验。在稳态条件的约束下，实验参数设定为服务强度μ=0.04，区块容量M=50、100，挖矿系数θ=0.06、 0.08、 0.10、 0.12。

针对不同的区块容量M，图3刻画了挖矿系数θ与交易到达率p对交易平均确认时间E[T]的影响。

图3表明，当区块容量M与挖矿系数θ固定时，交易平均确认时间E[T]随交易到达率p的增大呈上升趋势。交易到达率越大，区块链系统中的交易数越多。由于一个区块所能容纳的交易数是有限的，系统中的交易数越多，服务完成全部交易所需要的区块数越多，每个交易平均经历的挖矿循环次数也就越多。因而交易平均确认时间呈上升趋势。

(a) M=50

(b) M=100

纵向分析图3，在相同的区块容量M与交易到达率p下，挖矿系数θ越大，交易平均确认时间E[T]越小。挖矿系数大，意味着矿工求解数学难题的时间短，即挖矿过程短，交易可以更早地放入区块并得到确认。因而交易平均确认时间呈下降趋势。

对比图3(a)与图3(b)，在相同的挖矿系数θ与交易到达率p下，区块容量M越大，交易平均确认时间E[T]越小。一个区块所能容纳的交易数越多，服务完成全部交易所需的区块数越少，每个交易平均经历的挖矿循环越少，因而交易平均确认时间下降。随着交易到达率p的增大，区块容量M对交易平均确认时间E[T]的影响变大。当交易到达率较小时，系统中的交易几乎可以放入一个区块内，此时区块容量对交易平均确认时间的影响小。当交易到达率较大时，往往需要多个区块才能服务完成全部交易。区块容量越小，所需区块数越多，每个交易平均经历的挖矿循环越多，此时区块容量对交易平均确认时间的影响变大。

在区块链系统中，交易到达率越小，交易平均确认时间越短，用户体验的服务质量越好。而交易到达率越大，区块链系统的收益越高。综合考虑区块链用户的体验质量与区块链系统的收益，需要研究交易的纳什均衡行为与社会最优行为。

4 交易费方案

4.1 纳什均衡行为

每个交易都愿意进入区块链系统得到服务，但又不愿意承受过长的等待时间。假设交易到达区块链系统时，在完全不可见情形下，每个交易均从个体利益的角度出发，决定是否进入区块链系统接受服务[15]。

交易的个人收益定义为完成服务所获得的回报减去等待确认所花费的成本。交易的个人收益Gind(p)表示如下。

Gind(p)=R-CE[T]

其中，R为交易完成服务所获得的回报，C为交易在区块链系统滞留时单位时间所花费的成本。为了保证新到达的交易一定选择进入空的区块链系统，须满足R>CE[T]。

考虑系统的稳态条件，设置交易到达率的上界为pmax，分析交易的纳什均衡到达率。

当Gind(pmax)≥0时，区块链系统的全部交易都将获得非负的收益，即每个交易的收益为非负值。交易以概率qe=1进入系统为一个均衡策略，区块链系统的纳什均衡到达率pe=pmax。

当Gind(0)≤0时，即使进入区块链系统的交易可以直接接受服务，其所获收益也为非正值。交易以概率qe=0进入系统为一个均衡策略，区块链系统的纳什均衡到达率pe=0。

当Gind(0)≤Gind(p)≤Gind(pmax)时，只有部分进入区块链系统的交易可以获得非负的收益。交易以概率0

为了揭示交易个人收益的变化规律，进行数值实验。沿用第3节的实验参数，并设置R=350,C=6。在M=50下，交易个人收益Gind(p)随交易到达率p的变化情况如图4所示。

图4 交易个人收益的变化趋势

由图4观察到，对于所有的挖矿系数θ，交易个人收益Gind(p)均随交易到达率p的增大呈下降趋势。随着交易到达率的增加，交易平均确认时间延长，交易所花费的时间成本提高，因而交易个人收益下降。个人收益为0时所对应的交易到达率即为纳什均衡到达率。在相同的区块容量M下，挖矿系数θ越大，纳什均衡到达率pe越大。交易完成服务所获得的回报是固定的，挖矿系数越大，交易所花费的成本越小。增大交易到达率，直至成本与服务所获得的回报持平，即达到均衡状态。因此纳什均衡到达率变大。

4.2 社会最优行为

区块链系统的社会收益定义为单位时间内所有交易的个人收益与获胜矿工获得的区块奖励之和。社会收益Gsoc(p)表示如下：

Gsoc(p)=p(R-CE[T])+Q

(13)

其中，Q为单位时间内获胜矿工获得的区块奖励。

通过最大化社会收益Gsoc(p)，可以得到交易的社会最优到达率p*表示如下。

(14)

从式(12)无法得到交易到达率p的显示解，同时式(13)中社会收益Gsoc(p)关于p的单调性也无法确定。为了得到较准确的社会最优到达率，使用智能寻优算法。

布谷鸟寻优算法[16]的全局搜索能力强，但收敛速度较慢。为了提高收敛速度同时也能获得较高的寻优精度，引入自适应步长与动态步长缩放因子改进布谷鸟寻优算法，沿用第4.1节的实验参数，并设置Q=10，求解不同挖矿系数下的社会最优到达率。改进的布谷鸟寻优算法的主要步骤如下。

步骤 1初始化鸟窝数量n，宿主发现外来蛋的概率pa，鸟窝位置的上界Ub与下界Lb，当前迭代次数Gen=0，最大迭代次数MaxGen，步长s的最大值smax与最小值smin，步长缩放因子r的最大值rmax与最小值rmin。

步骤 2初始化鸟窝位置nesti。

fori=1:n

nesti=Lb+(Ub-Lb)×rand

endfor

步骤 3更新鸟窝位置对应的目标函数值fnewi。

fori=1:n

计算第i个鸟窝位置所对应的平均队长

%平均队长由式(11)得到

计算第i个鸟窝位置所对应的平均确认时间

%平均确认时间根据Little公式得到

fnewi=Gsoc(nesti)

%社会收益由式(13)得到

endfor

步骤 4寻找当前最优鸟窝位置bnest，计算当前最大目标函数值fmax。

fmax=Gsoc(best)

Gen=Gen+1 %更新当前迭代次数

ifGen>MaxGen

then跳转到步骤 7

endif

步骤5使用自适应步长s更新鸟窝位置。

fori=1:n

di=(nesti-best)/dmax

%dmax表示当前最优位置与其余鸟

窝位置距离的最大值

si=smin+(smax-smin)×di

nesti=best+si

endfor

步骤 6以概率pa更新鸟窝位置。

fori=1:n

ifrand>pa

r=rmax-(rmax-rmin)×Gen/MaxGen

%确定动态步长缩放因子

si=r×(nestm-nestw)

nesti=nesti+si

endif

endfor

返回步骤 3

步骤7输出鸟窝位置best为社会最优到达率p*，目标函数值fmax为最大社会收益Gsoc(p*)。

基于参数n=10，rmax=0.999999，MaxGen=40，pa=0.25，Ub=0.9，Lb=0.1，smax=0.01，smin=0.01，rmin=0.000001，利用改进的布谷鸟算法解出社会最优到达率与最大社会收益如表1所示。

表1 社会最优到达率

比较图4的纳什均衡到达率与表1的社会最优到达率，观察到在相同的挖矿系数下，交易的纳什均衡到达率大于社会最优到达率。为了降低交易的纳什均衡到达率使之与社会最优到达率一致，制定交易费收取方案, 实现区块链系统的社会最优。

4.3 交易费

(15)

=p(R-CE[T])+Q

(16)

比较式(15)与式(16)可以发现，区块链系统的社会收益并不受交易费的影响。区块链系统包括交易与矿工2部分。面向交易收取的费用全部转移给了矿工，因此区块链系统的社会收益不变。

f=Gind(p*)

使用与图4相同的实验参数，基于不同的挖矿系数计算出交易费如表2所示。

表2 交易费数值结果

从表2 可以看出，随着挖矿系数θ的增大，交易费f呈上升趋势。挖矿系数越大，即矿工求解数学难题越快，交易平均确认时间越短，可能有更多的交易到达系统。为控制交易到达率，使之与社会最优到达率一致，需设置较高的交易费。

5 结 论

基于区块链系统的交易确认过程，提出了一种带有批量服务及空载服务期的G-限量休假模型，研究交易纳什均衡到达率与社会最优到达率。采用再生循环法，给出了稳态下交易平均确认时间的表达式。进行数值实验与仿真实验，研究了区块容量、挖矿系数及交易到达率对交易平均确认时间的影响。构建交易的个人收益函数，给出了交易的纳什均衡到达率。构建区块链系统的社会收益函数，改进布谷鸟寻优算法，得到了交易的社会最优到达率。实验结果表明，在相同的挖矿系数下，交易的纳什均衡到达率高于社会最优到达率。基于该偏差，制定交易费方案，实现区块链系统社会收益的最大化。