基于IOTA区块链的一种新型Tips选择算法的研究

张秀贤,马莫凡,杨佳源,王君羽,江军熠

(南京晓庄学院 电子工程学院,江苏 南京 211171)

随着物联网的发展,越来越多的设备连接到互联网,例如智能汽车、智能家居设备、安防监控设备、智慧医疗设备、智能电网监控设备、智能交通设备等[1]。这些设备会产生大量的数据,如果能够有效地利用这些数据,将会产生巨大的利用价值。而区块链技术开放、透明、可追溯、防篡改,无论是人还是机器,都可以通过区块链系统实现可信的价值交换和数据共享[2]。目前,区块链已经被大量应用在金融、健康医疗、供应链、资产管理等诸多领域。

然而,传统的区块链共识时间长,吞吐量低,无法满足大规模物联网的需求,而专为物联网开发的IOTA区块链,打破了传统区块链的链式结构,采用有向无环图(DAG)的存储方式,允许所有的节点随时,随地,并发地向分布式账本Tangle中写入数据,且写入账本中的数据不再由区块链中的节点验证,而是由后续的交易验证,使得IOTA打破了区块链的“不可能三角”,同时达到了安全、去中心化和可扩展三方最优,它具有0交易费用、资源占用低、共识时间短,网络吞吐量大,抗量子级加密等优点。然而,由于IOTA的交易是由后续交易验证前面的交易,因此,交易的选择至关重要,传统的IOTA交易选择只与交易的权重即PoW的难度值有关会产生较多的孤儿,且容易受到寄生链攻击。另外,不同的用户时间敏感度不同,所能容忍的共识时间也不同。

因此,为了解决这个问题,我们综合考虑了用户时间敏感度,以及孤儿的数量,提出了一个新的Tips选择共识算法。1)按用户的时间敏感度将用户划分优先级,优先处理时间敏感度要求高的用户;2)为了降低孤儿的数量,优先选择先上传到区块链上的交易;3)为了解决寄生链攻击问题,将区块链上的交易按入度值排序,优先选择入度值大的交易。

1 Related Work

区块链技术作为一种去中心化,公开透明的分布式账本技术,将为6G提供强有力的安全保障。但是,由于传统区块链吞吐量低,共识时间长,可扩展性差等原因,目前,对于小额交易比较频繁的大规模物联网领域,共识时间短,零交易费,即插即用,吞吐量高以及抗量子级的加密技术使得IOTA作为区块链的一种替代方案受到越来越多研究人员的关注。论文[2]分析Tangle的共识算法比PoW和PoS更适合于物联网系统。论文[3]研究了IOTA的核心Tips选择方法针对寄生链攻击的漏洞,并提出了新的算法。论文[4]提出了一个基于IOTA区块链的物联网频谱共享框架。论文[5]提出了一种基于IOTA Tangle网络的物联网架构,解决了物联网存储在云中的集中化问题。论文[6]提出并分析了一种维持IOTA-tangle稳定性的策略。论文[7-9]对IOTA-tangle的性能进行了仿真。论文[10]为了提高系统的稳定性和安全性,提出了一种新的选择父节点的算法。论文[11]对Tangle的Tips选择机制进行了修改。保证了所有的事务在有限的时间内被验证,并且保留了蒙特卡罗选择算法的基本特征。论文[12]对加权随机漫步和随机漫步两种Tips选择算法的差别进行了分析。论文[13]以离散时间形式分析了平均未确认交易数量和平均确认交易时间。论文[14]分析了给定Tips将被遗留下来的概率和将成为永久Tips的概率。论文[15]研究了随机漫步Tips选择算法中,寄生链在Tangle中被吸收的概率。然而这些研究都没有考虑用户的时间敏感度,以及孤儿的数量,因此,本文提出了一种新的共识算法,满足不同时间敏感度的用户需求。

3 IOTA简介

图1 Tangle中交易共识过程示意图

IOTA的交易结构采用Tangle的形式,Tangle是一种特殊的有向无环图(DAG),如图1所示。DAG中的顶点即为存储的交易,有向边为验证关系,后面的交易验证前面的交易,其中,被验证过的DAG的顶点称为Sites,没有被验证过的交易称为Tips。即交易为DAG的顶点,其中包括Sites和Tips。当节点有交易需要写到Tangle时,由节点按照随机漫步或加权随机漫步的算法选择Tangle中的两个Tips,并对Tips进行检测,然后再做一定难度的PoW,最后将交易及所选的Tips在区块链中广播同步到其他节点,并更新本地Tangle。新存储到Tangle的交易作为新的Tips被后面的交易验证,当某个交易被所有的Tips可见时,称此交易完成共识,此时交易不可更改。如图1所示,图中的交易0—4都是共识完成的交易,因为,这几个交易都可以被Tip 9、Tip 10看到,但是交易5—8是没有完成共识的交易。

4 系统模型

图2 系统模型

如图2所示,系统主要分为两层,通信网络和由通信网络映射的区块链网络,通信网络即为大规分布式物联网,由智能终端、边缘网关、基站以及边缘服务器等组成;而区块链网主要用来保证数据的安全可信共享,采用IOTA共识算法实现。IOTA共识算法分为四部分:1)将交易写入本地Tangle;2)选择Tips并验证所选的Tips;3)做PoW计算;4)将交易、交易所选的Tips以及PoW的计算结果广播到网络的各个节点;5)等待被验证。而不同的Tips选择算法,对共识时间,系统吞吐量,孤儿的数量等的影响较大,而目前的随机选择或加权随机选择算法,很难满足不同的应用,因此,本文对Tips的选择算法进行了改进。

5 Tips选择算法

网络中的用户有些是时间敏感的,比如控制信息,报警信息等,有些则对时间要求不是很高的,比如视频流量,交易信息等,因此,本文将不同的时间敏感用户分为不同的优先级,时间敏感的用户优先处理。另外,为了降低孤儿的数量,优先选择先上传到区块链上的数据。为了解决寄生链攻击问题,将区块链上的交易按入度值排序,优先选择入度值大的交易。具体算法如下:

输入:Tipsall={Tip1,Tip2,,Tip3,…,Tipn};

输出:Tipssel;

1)检测Tips中是否含有寄生链,并将寄生链对应的Tips删除, 得到不包含寄生链的Tips集合:Tipsnopara;

2) 检查Tips中是否含有懒惰节点,将懒惰节点去除,得到Tips集合:Tipsnopl;

3) 根据共识时间敏感度将Tips分为两个优先级Htips,Ltips;

4) 分别统计Htips和Ltips中每个Tips直接或间接验证的所有未达成共识的Site的时间戳,计算数据写到Tangle的平均时间t,按t由大到小的顺序排序;

5) if length(Htips)>2

for i=1∶2

Tips_sel (i)=Htips(i);

end

else if 0

for i =1∶length(Htips)

Tips_sel (i)=Htips(i);

endfor

for j = length(Htips):2

Tips_sel (j)=Ltips(j)-length(Htips);

endfor

else

for i = 1∶2

Stips(i)=Ltips(i);

endfor

endif

6) return Tips_sel

首先,将寄生链对应的Tips以及懒惰节点删除,按时间敏感度将Tips分为高优先级Htips和低优先级Ltips;分别统计Htips和Ltips中每个Tips直接或间接验证的所有未达成共识的Site的时间戳,计算数据写到Tangle的平均时间t,按t由大到小的顺序排序;若判断高优先级Htips中元素个数是否大于Tips的选择个数(tips的选择个数一般为2),若大于2,则选取Htips中前两个Tips来验证,若小于2,则选取Htips中元素,剩下的从Ltips中选取。

图3 懒惰节点示意图

5.1 懒惰节点检测算法

如图3所示,以Tip 9为例,Tip 9验证了Site 2和Site 6。1)验证Site 2的还有Site 5和Site 6,倘若Site 5 和Site 6 的时间戳与Tip 9 的时间戳的差值超过2h,则认为Tip 9 为懒惰节点。2)验证Site 6的Tips有Tip 10和Tip 9,倘若Tip 10和Tip 9的时间戳差值小于2h,则认为两个节点都不是懒惰节点。只要被判断一次为懒惰节点的Tips则从待选Tips中删除。 具体算法如下:其中Tipshash为所有Tips 哈希值的集合,hashself的Tips本身的哈希值,hashfa1,hashfa2为Tips对应的两个父节点的哈希值,T为交易的时间戳, Tipsnopl为没有懒惰节点的Tips集合。

输入:Tipshash={hash1,hash2,,hash3,…,hashnum} ,

hash1={hashself,hashfa1,hashfa2,T},...,hashnum={hashself,hashfa1,hashfa2,T};

输出:Tipsnopl;

1) 计算num=Tipshash;

2) for i=1∶num

查找Tipshashi中每个Tips的父节点hashfa1,hashfa2;

for j=1∶2

hashchildj=checkchild(hashfaj);

childnumj=lenth(hashchildj);

将hashchildj按时间从大到小的顺序排列hashchildjT=sort(hashchildj);

for k=2∶childnumj

tdi=hashchildjTk-hashchildjT1;

if tdi<2h

Tipsnopl= Tipsnopl∪ Tipi;

endif

endfor

endfor

endfor

3) return Tipsnopl;

输入:Tipshash={hash1,hash2,,hash3,…,hashnum} ,

hash1={hashself,hashfa1,hashfa2,T},...,hashnum={hashself,hashfa1,hashfa2,T},hashfa

输出:hashchild

1) for i=1∶num

for j=1∶2

if hashfa==hashi.hashfaj

hashchild= hashchild∪ hash1;

endif

endfor

endfor

2) return hashchild;

5.2 寄生链检测算法

在t-h时刻,Tangle中的Tips总个数为L0=2λh[4],其中,λ为网络中总的事件到达率,在t时刻Tangle中Tips的个数也为L0,而在h时间间隔内,事件的到达个数为λh,因此,所有被选中的Tips个数为λh才可以使得在t时刻Tips的总个数仍为L0;另外对于λh个新到事件,每个事件会选择2个Tips作为父节点,相当于在λh个Tips中选2λh次,则每个Tips被选中的平均次数为2。因此,每个Site的出度和入度都为2。当前Tips的前N个Site的出度值为:深度为N的满2叉树的节点个数2N-1, 出度总和为2*(2N-1),当出度值大于2α*(2N-1)时,判定Tips不是寄生链的Tips,其中α为系数。

假设每个交易最少选2个Tips进行验证,则前N层Site的出度计算算法如下:

输入:Tipshash={hash1,hash2,hash3,…,hashnum} ,

hash1={hashself,hashfa1,hashfa2,T},...,hashnum={hashself,hashfa1,hashfa2,T};

输出:Tipsnopara

1)for i=1∶num

for j=1∶N

for k=1∶2j

if hashik.hashfa1!=0

outdegreei = outdegreei+1;

if hashik.hashfa2!=0

outdegreei = outdegreei+1;

endif

endif

hashik=hashik.hashfa1∪ hashik.hashfa2

endfor

if outdegree<2α*(2N-1),

Tipsall=Tipsall/Tipsi;

endif

endfor

endfor

2)Tipsnopara=Tipsall;

3)return Tipsnopara;

6 仿真评估与分析

本文使用Matlab对传统IOTA Tips选择算法和文章提出的Tips选择算法进行了仿真分析,如图4所示,本文对网络中不同Tips数量时,孤儿的数量进行了仿真,由图可以看出,传统的随机选择算法,当网络中Tips数量增加时,被遗留下的孤儿数量增加,而对于本文提出的算法,由于在Tips选择时,增加了写入网络中的时间因素,写入网络时间越早,被选中的概率越大,因此,本文提出的Tips选择算法,被遗留下的孤儿数量显著降低,有效的解决了孤儿的遗留问题。

同时,假设网络中时间敏感数据占10%的情况下,对时间敏感问题是否及时解决进行了仿真,如图5所示,时间敏感的Tips在本文提出的Tips共识算法中,被选中所用的周期数明显降低,主要是因为,在我们提出的算法中,时间敏感的数据有优先选择权,保证了时间敏感数据可以快速达成共识。

图4 孤儿数量仿真

图5 时间敏感Tips被选中所需的周期数

7 结 论

本文对在现有的IOTA区块链中,Tips选择选择算法进行了改进,本文综合考虑孤儿的数量,用户的时间敏感度,设计了新的Tips选择算法。并针对新的Tips选择算法设计了懒惰节点识别和防止寄生链攻击算法。仿真和分析结果表明,本文提出的算法明显降低了孤儿的数量,更好的满足不同时间敏感度的用户需求。