带有优先级、空块及批量验证的区块链系统的社会最优

张大鹏,袁红莉

(1.江苏信息职业技术学院 物联网工程学院,江苏 无锡 214153;2.燕山大学 信息科学与工程学院,河北 秦皇岛 066004)

0 引言

作为加密货币比特币的核心技术,区块链因防篡改、防抵赖、可靠性高以及去中心化等特点引起众多领域的广泛关注。近年来,区块链的基础理论研究也不容忽视。

目前,排队论中已有的批量排队系统都分析了区块链系统交易的基本运行流程。Kasahara等[1]建立了一个批量服务的M/Gb/1模型,使用补充变量法得到了稳态下系统中的平均交易数及交易平均确认时间。通过数值实验,研究了交易到达率和区块大小对交易平均确认时间的影响。Kasahara等[2]建立了一个带有优先权和批量服务的单服务台排队模型,得到了每类优先级交易的平均确认时间,研究了优先级对小额交易平均确认时间的影响。数值实验表明当区块容量不变时,小额交易的到达率增大为原来的四倍,小额交易平均确认时间将猛增。Geissler等[3]提出了一个批量服务的GI/GIN/1模型,通过嵌入马尔科夫链得到了平均交易数及交易平均确认时间。Li等[4]提出了一个批量服务的GI/M/1型随机排队模型,使用矩阵几何解方法得到了稳态下系统内的平均交易数、每个区块内的平均交易数及交易平均确认时间。

如果候选区块所包含的交易数小于区块可容纳交易数的最大上限时,根据区块链系统的默认机制,在挖矿过程中到达的交易将放入候选区块中。Kawase等[5]提出了一个具有优先级机制的M/Gb/1模型,得到了每类优先级交易的平均确认时间。通过比较测量数据和分析结果,发现挖矿过程并没有遵循默认机制,其挖矿过程中到达的交易并不放入候选区块中,而是放入下一轮挖矿过程。

上述文献均忽略了挖矿过程不遵循默认机制。除此之外,上述文献均未考虑空块的coinbase交易。

另一方面,Mose等[6]分析了在区块链系统中,用户支付交易费的数据,结论表明了交易费对区块链系统的安全性和可持续性起着至关重要的作用。对于矿工来说,出块奖励每四年减半,随着出块奖励的减少,交易费将作为主要的利润来源[7]。对于用户来说,交易费极大地影响了交易的优先级,进而影响了交易确认时间,且过高的交易费不利于小额交易的确认时间。

Li等[8]在非抢占优先级排队模型下,假设每个用户不支付交易费,该用户发出的交易最终记录到区块链后仍然会获得收益,但是会随着长时间的等待而减少。如果用户支付了足够高的交易费将获得第一名,该交易到达后将立刻处理,那么该用户的收益不会因为时间等待而减少,而是因交易费而减少。研究了没有用户、所有用户和部分用户支付交易费三种情况下用户的纳什均衡行为。实验结果表明,在平衡状态下,具有足够高的时间成本的用户将增加交易费,而具有足够低的时间成本的用户可能拒绝提供交易费。Li等[9]又引入了多优先级规则,分析了用户在不同优先级上的等待时间,建立博弈模型研究了用户的纳什均衡费用决策,为区块链系统交易的优化排队规则提供了有用的管理见解。

以上文献均体现了研究区块链系统交易费及博弈的重要性。然而迄今为止,有关方面的研究仍然很薄弱。因此基于排队论方法分析区块链基础理论十分有益。

在之前的工作中,本课题组提出了一种带有批量服务及空载服务期的G-限量休假排队模型[10],在此基础上,对带有优先级的G-限量休假排队模型继续展开研究。本文第1章对带有优先级、空块及批量验证的区块链系统的交易确认过程进行了介绍;第2章给出了带有优先级、批量服务及空载服务期的G-限量休假排队模型,并进行了数值实验及仿真实验;第3章构造了Ⅰ类交易与Ⅱ类交易的个人收益函数及区块链系统的社会收益函数,给出了社会最优下系统能容纳两类交易的最大进入率的数值结果,同时分别对Ⅰ类交易和Ⅱ类交易制定交易费方案,实现区块链系统的社会最优;最后总结全文。

1 带有优先级、空块及批量验证的区块链系统的交易确认过程

假设区块链系统中有两类不同等级的交易,分别为Ⅰ类交易和Ⅱ类交易,Ⅰ类交易比Ⅱ类交易具有更高级别的优先权。

区块链系统中的Ⅰ类交易与Ⅱ类交易不断产生。用户产生任一类交易后,需要广播该类交易至区块链系统中的所有矿工。每个矿工先进行交易验证,再把验证通过的交易放入各自的内存池中。争夺区块记账权的矿工从内存池中选出交易构建候选区块,并通过求解数学难题,进行工作量证明,这就是挖矿过程。

争夺区块记账权的矿工从内存池选择交易时,会出现下面三种情况。

1)如果内存池中既有Ⅰ类交易,又有Ⅱ类交易,首先按照先到先入的规则选择I类交易放入区块,直到内存池中没有剩余的I类交易或区块无剩余容量为止。然后如果内存池中没有剩余的Ⅰ类交易且区块中仍有剩余容量,按照先到先入的规则选择Ⅱ类交易放入区块,直到内存池中没有剩余的Ⅱ类交易或区块无剩余容量为止。

2)如果内存池中只有Ⅰ类交易,按照先到先入的规则选择Ⅰ类交易放入区块,直到内存池中没有剩余的Ⅰ类交易或区块无剩余容量为止。

3)如果内存池中只有Ⅱ类交易,按照先到先入的规则选择Ⅱ类交易放入区块,直到内存池中没有剩余的Ⅱ类交易或区块无剩余容量为止。

一旦挖矿过程成功,最快解答出数学难题的矿工为获胜矿工,其余所有矿工称为未获胜矿工。获胜矿工的候选区块升级为新区块,同时将新区块广播给其余未获胜矿工。未获胜矿工首先将各自的候选区块作废并验证收到的新区块,然后将验证结果发送给获胜矿工。只有当成功验证新区块的矿工数目超过系统规定的阈值时,获胜矿工可以将新的区块接入到区块链中,并反馈新区块确认消息给其余矿工。获胜矿工之外的所有矿工收到新区块确认消息后,从各自的内存池中清除新区块中所含的交易。若获胜矿工的新区块为空块,不需广播给其余未获胜矿工进行验证,获胜矿工直接将空块接入到区块链。这就是区块验证过程。

挖矿过程加上区块验证过程称为区块链的交易确认过程。在区块链的交易确认过程中,很明显发现Ⅰ类交易的数量会影响Ⅱ类交易的确认时间,为了进一步研究优先级对交易确认时间的影响,需要建立合理的数学模型,定量刻画Ⅰ类交易与Ⅱ类交易平均确认时间的变化趋势。

2 带有优先级、批量服务及空载服务期的G-限量休假模型

2.1 模型描述

从区块链的交易确认过程可以观察到,获胜矿工所构造的非空新区块会受到交易优先级的影响,而构造的空块则不受交易优先级的影响。将挖矿过程视为休假,空块接入区块链的过程视为空载服务期,非空新区块的验证以及接入区块链的过程视为普通服务期。考虑区块链中的多点同步需求,结合现代通信的数字化本质,在离散时间领域建立一种带有优先级、批量服务及空载服务期的G-限量休假模型。

对带有优先级、批量服务及空载服务期的G-限量休假模型做出如下假设:

2.2 模型分析

Ⅰ类交易的平均确认时间和Ⅱ类交易的平均确认时间是衡量区块链系统响应性能的重要指标。

定义T1为Ⅰ类交易的确认时间,也就是说Ⅰ类交易从进入内存池直到链入区块链的时间间隔。

2.2.1 服务期开始时刻的Ⅰ类交易的交易数母函数

2.2.2 Ⅰ类交易的平均确认时间

对比文献[10]中式(12)与本文的式(31),观察到在带有优先级、批量服务及空载服务期的G-限量休假模型中,Ⅰ类交易的平均确认时间与在带有批量服务及空载服务期的G-限量休假模型中交易平均确认时间一样,故在带有优先级、批量服务及空载服务期的G-限量休假模型中,Ⅰ类交易不受Ⅱ类交易的影响。

2.2.3 服务期开始时刻的Ⅱ类交易的交易数母函数

定义T2为Ⅱ类交易的确认时间,可以理解为从Ⅱ类交易到达区块链系统的时刻到包含Ⅱ类交易的区块接入区块链所持续的时间。

2.2.4 Ⅱ类交易的平均确认时间

处理非空竭休假模型常用工具之一除了再生循环法,还有逝去时间法[11]。使用逝去时间法给出Ⅱ类交易的平均确认时间的表达式。使用逝去时间法需要给出一个忙循环开始时系统内Ⅱ类交易的交易数和一个忙循环逝去时间内到达Ⅱ类交易的交易数。

3 系统实验

带有优先级、空块及批量验证的区块链系统中,只要系统中存在Ⅰ类交易,区块链系统就必须优先服务优先权高的Ⅰ类交易。故得出结论:Ⅰ类交易不受Ⅱ类交易的影响。进行系统实验,研究Ⅰ类交易的到达率、服务强度、挖矿系数及区块容量对Ⅱ类交易的平均确认时间的影响。

实验环境如下:CPU型号为Intel Core i7-4790,CPU运行频率为3.60 GHz,系统内存为8.00 GB。

假设挖矿过程服从参数为θ的几何分布,服务期的时间长度服从参数为μ的几何分布,进行数值实验与仿真实验。数值实验在MATLAB 2016a环境中运行,仿真实验在MyEclipse 2014环境中采用Java语言实现。在稳态条件的约束下,实验一的参数设定为:在服务强度μ=0.4,挖矿系数θ=0.5下,区块容量M=5,7,Ⅰ类交易到达率pH=0.3,0.4,结果如图1所示。实验二的参数设定为:区块容量M=5,Ⅰ类交易到达率pH=0.4下,服务强度μ=0.35,0.40,挖矿系数θ=0.50,0.60,结果如图2所示。图1刻画了在不同的区块容量M下,Ⅰ类交易到达率pH与Ⅱ类交易到达率pL对Ⅱ类交易的平均确认时间E[T2]的影响。图2刻画了在固定的区块容量M和Ⅰ类交易到达率pH下,服务强度μ和挖矿系数θ对Ⅱ类交易的平均确认时间E[T2]的影响。

图1 不同区块容量下的Ⅱ类交易平均确认时间Fig.1 Average confirmation time for Transaction Ⅱ under different block size

图2 固定区块容量和Ⅰ类交易到达率下Ⅱ类交易的平均确认时间Fig.2 Average confirmation time for Transaction Ⅱ with fixed block size and arrival rate of Transaction Ⅰ

横向对比分析图1。当区块容量M和Ⅰ类交易到达率pH固定时,随着Ⅱ类交易到达率pL的增加,Ⅱ类交易的平均确认时间E[T2]呈上升趋势。Ⅱ类交易到达率越大,区块链系统内存池中等待被确认的Ⅱ类交易就越多,Ⅱ类交易的等待时间也就越长,因此Ⅱ类交易的平均确认时间呈上升趋势。

纵向对比分析图1。在相同的区块容量M和Ⅱ类交易到达率pL下,随着Ⅰ类交易到达率pH的增加,Ⅱ类交易的平均确认时间E[T2]逐渐增加。Ⅰ类交易到达率越大,到达区块链系统内存池的Ⅰ类交易也就越多,区块链系统因优先服务Ⅰ类交易,造成Ⅱ类交易在内存池的等待时间变长,因此Ⅱ类交易的平均确认时间增加。当固定Ⅰ类交易到达率pH和Ⅱ类交易到达率pL时,Ⅱ类交易的平均确认时间E[T2]随区块容量M的增加呈下降趋势。区块容量越大,一个区块能容纳的交易数越多,Ⅱ类交易能尽早从内存池放入区块被确认,故Ⅱ类交易的平均确认时间越短。

从图2可以观察到,随着服务强度μ的增加,Ⅱ类交易的平均确认时间E[T2]逐渐变短。服务强度越大,Ⅱ类交易的服务时间也就越短,因此Ⅱ类交易的平均确认时间也就越短。还可以观察到,随着挖矿系数θ的增加,Ⅱ类交易的平均确认时间E[T2]逐渐变短。挖矿系数越大,单位时间产生的区块数量也就越多,Ⅱ类交易从内存池放入区块被确认的等待时间也就越短,因此Ⅱ类交易的平均确认时间也就越短。

图1和图2中,无论哪种参数组合,数值实验结果均与仿真实验结果相吻合。

综上,Ⅰ类交易的平均确认时间不受Ⅱ类交易到达率的影响,但是Ⅱ类交易的平均确认时间与Ⅰ类交易到达率有很大关联,如果Ⅰ类交易较多,则Ⅱ类交易一直等待被确认及记录到区块链,则Ⅱ类交易的平均确认时间也大大增加,不利于发起Ⅱ类交易的用户。因此需要对带有优先权、批量服务及空载服务期的G-限量休假模型进行优化,综合考虑交易进入区块链系统所获得的收益与等待被确认所消耗的时间成本,研究交易的纳什均衡行为与社会最优行为,给出交易到达区块链系统时,以多大概率进入区块链系统和收取多少的交易费来吸引更多的交易选择进入区块链系统。

4 带有优先权、空块及批量验证的区块链系统的优化

4.1 纳什均衡行为和社会最优行为

首先对带有优先权、批量服务及空载服务期的G-限量休假模型做出以下假设。

1)一批交易的潜在到达率为Λ,以概率α为Ⅰ类交易,以概率q进入到区块链系统的内存池中。Ⅰ类比Ⅱ类交易的优先权高。

2)R1和R2分别代表Ⅰ类交易和Ⅱ类交易完成服务后获得回报。

3)C1和C2分别代表Ⅰ类交易和Ⅱ类交易在单位确认时间内所耗费的成本。

4)同一类交易的收益相同且可以叠加。

5)当一个新的Ⅰ类交易或Ⅱ类交易进入空的区块链系统时,直接接受服务后获得的收益比等待确认所花费的成本高,即R1＞C1E[T1],并且R2＞C2E[T2]。

将每类交易的个人收益定义为一个交易进入区块链系统接受服务后所获得的回报与等待被确认所耗费的时间成本之差。Ⅰ类交易的个人收益B1(q)与Ⅱ类交易的个人收益B2(q)分别表示

式中,E[T1]和E[T2]分别表示Ⅰ类交易和Ⅱ类交易的平均确认时间。

为了揭示Ⅰ类交易与Ⅱ类交易的个人收益的变化规律,进行数值实验。实验参数设置为:M=5,R1=12,R2=10,C1=2,C2=1.8,Λ=1.5,α=0.3,μ=0.4和θ=0.5,0.6。图3和图4分别表示在不同的挖矿系数θ下,Ⅰ类交易的个人收益B1(q)和Ⅱ类交易的个人收益B2(q)随着进入率q的变化趋势。

图3 不同挖矿系数θ下Ⅰ类交易的个人收益Fig.3 Individual profit of Transaction Ⅰ with different mining coefficients

图4 不同挖矿系数下Ⅱ类交易的个人收益Fig.4 Individual profit of Transaction Ⅱ with different mining coefficients

由图3和图4可以观察到,针对不同的挖矿系数θ,Ⅰ类交易的个人收益B1(q)和Ⅱ类交易的个人收益B2(q)随着进入率q的增大逐渐减少。Ⅰ类交易进入率或Ⅱ类交易进入率越大,Ⅰ类交易到达率或Ⅱ类交易到达率就越大,Ⅰ类交易与Ⅱ类交易在区块链中的平均确认时间也就越长,因此,Ⅰ类交易和Ⅱ类交易的个人收益不断减少。

同时可观察到,对于每一条Ⅱ类交易的个人收益,有且仅有一个进入率的取值使得B2(q)=0,记为Ⅱ类交易的纳什均衡进入率。当B2(q)＞0,Ⅱ类交易选择进入区块链系统,相对应的,当B2(q)＜0,Ⅱ类交易选择放弃进入区块链系统。而对于每一条Ⅰ类交易的个人收益,当进入率处于0～0.1范围内,Ⅰ类交易的个人收益均为正值,即B1(q)＞0,Ⅰ类交易均选择进入区块链系统接受服务。

将区块链系统的社会收益定义为单位挖矿时间内Ⅰ类交易和Ⅱ类交易的个人收益与获胜矿工的区块奖励之和,社会收益D(q)表示为

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

通过最大化式(48),给出社会最优概率

设置区块奖励Q=10,图5表示在不同的挖矿系数θ下,社会收益D(q)随着进入率q的变化趋势。

图5 不同的挖矿系数下的社会收益Fig.5 Social benefits with different mining coefficients

由图5可以观察到,对于不同的挖矿系数θ,随着进入率q的增加,社会收益D(q)均呈现出先上升再下降的趋势。当两类交易的总进入率较小时,两类交易的交易数量是影响社会收益的主要因素,因此,两类交易的总到达率越大,社会收益也就越大。当进入率较大时,Ⅰ类交易与Ⅱ类交易的平均确认时间均增加,单位确认时间所耗费的时间成本变高,因此,随着两类交易总进入率的增加,社会收益呈下降趋势。对于图1中的每一条曲线,都存在唯一的进入率使得社会收益D(q)取得最大值,该进入率即为社会最优进入率q*。

因为在求解Ⅱ类交易的平均确认时间E[T2]的过程中,需给出Ⅰ类交易的到达率的确定值,并调用仿真实验中服务期开始时联合概率的数值结果。所以,式(49)无法得到关于q*的显示解。利用改进的布谷鸟算法[10],得到社会最优进入率如表1所示。

表1 社会最优进入率Tab.1 Social optimal entry rate

4.2 交易费

引用图4和图1中的实验参数,对于不同的挖矿系数θ,在表2中呈现了Ⅰ类交易与Ⅱ类交易的交易费f1和f2的数值结果。

表2 不同挖矿系数下Ⅰ类交易和Ⅱ类交易的交易费Tab.2 Transaction fees of Transaction I and II with different mining coefficients

由表2观察到,随着挖矿系数的增加,Ⅰ类交易的交易费f1与Ⅱ类交易的交易费f2均呈现出上升的趋势。并且在每一个挖矿系数θ下,Ⅰ类交易的交易费f1均高于Ⅱ类交易的交易费f2。挖矿系数越大,Ⅰ类交易与Ⅱ类交易到达区块链系统的越多,为了维护系统稳态,需逐渐提高交易费。同时为了维护发起Ⅱ类交易用户的热情,需对优先权较高的Ⅰ类交易设置较高的费用,抑制一部分Ⅰ类交易的热情。

5 结论

本文基于带有优先权、空块及批量验证的区块链系统的交易确认过程,建立了带有优先权、批量服务及空载服务期的G-限量休假排队模型,同时使用再生循环法和逝去时间法分别给出了Ⅰ类交易与Ⅱ类交易的平均确认时间的表达式。然后进行了数值实验及仿真实验,主要刻画了Ⅰ类交易到达率、区块容量、挖矿系数及服务强度对Ⅱ类交易的平均确认时间的影响。构造了Ⅰ类交易与Ⅱ类交易的个人收益函数及区块链系统的社会收益函数,给出了社会最优下系统能容纳两类交易的最大进入率的数值结果,分别对Ⅰ类交易和Ⅱ类交易制定交易费方案,实现了区块链系统社会收益的最大化。