针对区块链状态分片合谋攻击的改进方案

于 谦 李志淮 田 娜

1(大连海事大学 辽宁 大连 116026)

2(泰康人寿 北京 102200)

0 引 言

区块链技术[1]本质上是一个分布式总账系统,拥有去中心化、去信任、不可更改等特点,解决了传统互联网模式中第三方中介不可信、不可靠的问题[2]。习近平在中央政治局第十八次集体学习时强调:把区块链作为核心技术自主创新重要突破口,加快推动区块链技术和产业创新发展。区块链技术的价值有目共睹。但是,目前区块链的基础设施无法满足大规模应用的要求,限制了区块链行业的发展,扩容需求强烈[3-5]。为此,开发者们提出了分片[6]、DAG[7]、状态通道[8-9]、侧链[10]等多种扩容方案。

对比各种扩容方案,分片是最有希望能够实现高性能而不降低去中心化程度的扩容方案。分片包括网络分片、交易分片和状态分片[11]。其中网络分片在网络层将所有节点划分到了不同的分片中[12]。交易分片将全网交易划分到不同的分片中验证和打包,全网多个分片可以同时打包和验证不同的交易,并行处理,从而提升全网的整体性能。状态分片将完整的账本信息分别存储到各个分片当中,各个节点不再存储完整的区块链状态信息,每个分片内各自维护部分的账本信息。网络分片是交易分片和状态分片的基础[12]。交易分片虽然能在一定程度上提升公链性能,但并不能从根本上解决资源瓶颈等问题。因此,只有实现状态分片才能从本质上解决公链可扩展性问题。

状态分片是迄今为止所有分片提案中实现难度最高的,面临着跨分片通信和状态交换频繁、分片遭受攻击导致脱机,以及节点保持静态遭受攻击等挑战。对于跨分片通信和状态交换问题,目前业界大致有四种方案。Omniledger[13]让发出交易的客户端主动维护一致性,分片协议不用考虑维护一致性的问题,技术简单,且避免了分片之间一致性协议的开销;Chainspace[14]基于trace对交易进行标注,交易注入到网络中之前,先模拟trace,并以此标注出可能与其他交易冲突的地方,然后根据这些冲突发到相关的分片中处理,相关的分片之间再用S-BAC去共识;Ethereum[15]将币的转移过程切开,分成币的发送和币的接收,并且在不同的共识周期中完成;Rchain将跨分片的交易在它们的父级分片中处理。对于分片受到攻击导致脱机这一问题,目前解决方案是维护存档或备份节点,以帮助网络进行故障排除并从数据不可用中恢复。最后,为了防止节点是静态的,不能很好地抵御攻击和故障,在Rapidchain[16]分片协议中介绍了一个委员会重组方案,叫作有界的布谷鸟原则(Bounded Cuckoo Rule),更加高效地进行分片委员会重构,同时可以防止恶意节点控制某个分片的行为发生。

另外,针对状态分片间的女巫攻击[17]以及双花攻击[18]问题,在以太坊[19]2.0状态分片中,引入信标链来负责主链以及管理各个分片。验证节点需要向信标链抵押一定数量的ETH来获得许可,若节点作恶,信标链会对作恶节点进行相应的惩罚,以此来防止女巫攻击。由信标链对跨分片交易进行验证,以防止分片间双花攻击问题。

在状态分片种种挑战的解决方案中,都回避了受状态分片限制导致的合谋攻击问题。

多轮的概念在文献[12]里被首次提出。为防止分片失效无法达成共识,故提出多轮的解决方案。主要思想是:如果第一轮共识失败,则节点重新随机分配进行第二轮共识,直到共识成功为止。此方案同样回避了合谋攻击问题,因为即使共识成功,也有可能是作恶节点合谋导致。

本文针对目前区块链状态分片存在的合谋攻击问题,提出一种状态分片中抗合谋攻击的多轮验证方案。

1 问题描述与分析

1.1 合谋攻击问题描述

在分片内的验证节点中,拜占庭[20]节点所占比例较高但是不超过总节点1/3的情况下,存在某个分片中拜占庭节点占据大多数,且相互串通,进行合谋攻击,最终达成错误共识的可能。分片内合谋攻击发生需满足以下两个条件。

(1) 分片内拜占庭节点数大于该分片内节点总数的2/3。

(2) 拜占庭节点串通在一起进行合谋。

因状态分片的约束,区块链网络中节点的随机分配受到限制,即节点只能分配到存储其数据的分片中去。BFT(拜占庭)节点数量比交易分片有更高概率出现b≥2n/3(n为网络中节点总数),且这些BFT节点可能形成合谋,将错误的事务验证确认,从而破坏整个链的数据一致性。

1.2 交易分片与状态分片发生合谋攻击的概率对比

1.2.1交易分片发生合谋攻击的概率分析

(1)

分母表示全网一共有N个节点,其中分到第Ki个分片的节点是L个;分子分别表示全网(N×f)个拜占庭节点中,第Ki个分片有x个,全网(N-N×f)个非拜占庭节点中,第Ki个分片有(L-x)个。

根据式(1),假设网络中验证节点总数N=8 000,设置f=[0.1,0.25,0.33]。使用Python语言进行模拟计算,当网络中拜占庭比例f以及单个分片中节点数目L均发生变化时,分片中拜占庭节点发生合谋攻击的概率。单个分片中拜占庭节点合谋的概率P见表1。

表1 单个分片中拜占庭节点合谋的概率

如表1所示,当区块链网络中拜占庭节点占比比较低(f<0.15)时,无论单个分片中节点数目怎样变化,合谋攻击发生的概率都不会太高;当区块链网络中拜占庭节点占比比较高(f=0.25～0.33)时,只要单个分片内节点数目不低于60,合谋攻击发生的概率也不会太高,最高概率是5.09e-10左右,甚至可以忽略。

1.2.2状态分片发生合谋攻击的概率分析

状态分片中,节点只能被分配到存储其数据的分片中去。假设有Mi个节点存储第Ki个分片的数据,用F表示Mi个节点中拜占庭节点比例。同理,状态分片发生合谋攻击的概率也按照超几何分布的分布列进行处理。第Ki个分片发生合谋攻击的概率如式(2)所示。

(2)

式中:分母表示有Mi个节点存储第Ki个分片的数据,其中分到第Ki个分片的节点是L个;分子分别表示(Mi×F)个拜占庭节点中,第Ki个分片有x个,(Mi-Mi×F)个非拜占庭节点中,第Ki个分片有(L-x)个。

由式(2)可知,第Ki个分片发生合谋攻击的概率跟Mi、F、L的取值有关。为了方便比较,先假设F=0.33,L=120,用Python模拟计算出在存储第Ki个分片数据的节点数Mi发生变化时,第Ki个分片拜占庭节点发生合谋攻击的概率,见表2。

表2 不同节点数Mi对合谋攻击概率P的影响

如表2所示,当其他条件固定时,合谋攻击概率P与Mi取值关系不大,甚至可以忽略。

另一方面,式(2)中,Mi个节点中拜占庭节点数(Mi×F)一定是小于等于网络中拜占庭节点总数(N×f)的,且因拜占庭节点分配不均,Mi个节点中拜占庭节点比例F有可能大于整个网络中拜占庭节点比例f。又因Mi取值对合谋攻击概率P的影响微乎其微,故为方便比较,设置Mi=600,根据式(2)用Python模拟计算当Mi个节点中拜占庭比例F以及单个分片中节点数目L均发生变化时,分片中拜占庭节点发生合谋攻击的概率,见表3。

表3 分片内不同节点数L以及Mi个节点中不同拜占庭

如表3所示,合谋攻击发生的概率随着F的增大显著增大。F取值从0.40开始,在其他变量(整个网络的拜占比f,分片内节点数量L)一致的前提下,状态分片合谋攻击发生的概率已经远远超过了交易分片合谋攻击发生的概率。

此外,根据表3还可以看出,相同拜占比下,合谋攻击发生的概率随着分片内节点数量的减少而升高。当单个分片内验证节点数量减少到低于60,只要F大于等于0.38,此时合谋攻击发生的概率最小也是5.1e-7,这已经是一个不能忽视的值了;F取值从0.45开始,即使分片内节点数L达到128个,合谋攻击发生的概率依然高达1.1e-8。系统的安全性受到了极大的威胁。

综合上述分析,状态分片的合谋攻击问题不容忽视且亟待解决。针对此问题,本文将提出一种解决方案,在降低分片内合谋攻击发生的概率、保证系统安全性的同时,在一定程度上提高系统的性能。

2 抗合谋攻击的多轮验证方案设计

2.1 多轮验证方案总体设计

多轮验证方案主要包括以下3个步骤。

(1) 按照映射规则将交易分配到相应分片中。

(2) 使用节点随机分配算法生成随机数,然后将验证节点根据映射规则分配到相应的分片中,对交易进行共识验证。

(3) 如果交易验证结果达到一致,则重复步骤(2),直到相同的交易验证结果达到两次,将交易打包;若交易验证共识超时,同样重复步骤(2),当多轮轮次达到T次仍共识超时,则放弃该笔交易。具体流程见图1。

图1 多轮验证总体流程

2.2 多轮轮数的选择

2.2.1轮数上限Tmax

轮数上限Tmax,即多轮验证方案最多要进行的共识验证轮数。当对同一笔交易通过Tmax轮共识验证都无法达到统一验证结果时,便舍弃此交易。Tmax受共识超时概率的影响,当分片内拜占庭节点所占比例大于等于三分之一时,会导致共识超时,分片失效,从而破坏系统一致性。将Tmax的取值设定为共识超时概率低于10-6时的值。

(3)

式中:分母表示全网一共有N个节点,其中存储第Ki个分片的节点是Mi个;分子分别表示全网(N×f)个拜占庭节点中,这Mi个节点中有(Mi×F)个,全网(N-N×f)个非拜占庭节点中,这Mi个节点中有(Mi-Mi×F)个。

设置系统网络中节点数N=8 000,易知,系统拜占比越高,分片失效概率越大,需要的轮数越多。因此,轮数上限的确定选择在系统拜占比f=0.33的情况下,根据式(3),使用Python语言进行模拟计算。当存储第Ki个分片数据的节点数Mi以及Mi个节点中拜占比F各自发生变化时事件A发生的概率见表4。

如表4所示,无论Mi取值多少,这Mi个节点中,根据表中所提供的数据,最有可能出现的拜占比F为0.35。用同样的方式模拟计算出F在区间[0.30,0.35]和[0.35,0.40]上时,事件A发生的概率。无论Mi取值多少,当F为0.33时,事件A发生的概率最大。也就是说,当有Mi个节点存储第Ki个分片的数据时,在系统拜占比f=0.33的情况下,无论Mi取值多少,这Mi个节点中最有可能出现的F是0.33。

当单个分片内拜占庭节点数X>L/3时,共识超时,分片失效。分片失效概率如式(4)所示。

(4)

根据式(4),令F=0.33,使用Python语言模拟计算分片内节点数L以及存储第Ki个分片数据的节点数Mi取值各不同时,分片失效的概率见表5。

表5 不同Mi和L对分片失效概率的影响

2.2.2轮数下限Tmin

轮数下限Tmin,即多轮验证方案最少要进行的共识验证轮数。Tmin受合谋攻击概率影响。在状态分片后续发展中,为了提高性能,会通过减少分片内节点数目,扩大分片规模来实现。设定Tmin的取值为分片内节点数大于40,合谋攻击发生的概率小于10-8的值。多轮过程中合谋攻击发生概率与轮数T之间的关系如式(5)所示。

(5)

PA-m-r表示多轮验证过程中合谋攻击发生的概率,T表示多轮轮数,P(X>2L/3)表示一轮中合谋攻击发生的概率。将式(5)展开如式(6)所示。

(6)

在2.2.1节的分析中得到,Mi对合谋攻击发生概率的影响微乎其微,甚至可忽略,为了方便比较,根据式(6),设定Mi=600,在F=0.33的情况下,取L=[30,45,60],通过改变多轮轮数T的取值,得到多轮下的合谋攻击发生的概率。使用Python语言进行模拟计算,在分片内节点数L固定的前提下,计算出在多轮轮数T不同的情况下,分片中拜占庭节点发生合谋攻击的概率P,结果见表6。

表6 轮数T对合谋攻击概率P的影响

可以看出,多轮轮数T=2时,合谋攻击发生的概率与未使用多轮方案时发生合谋攻击的概率相比降低十分明显,几乎降到了未使用多轮方案时合谋攻击发生概率的平方级别,可见,多轮共识验证的方案对抗合谋攻击起到了很好的作用。

此外,分片内节点越少,合谋攻击发生的概率越大。但是从第二轮开始,合谋攻击发生的概率已经远远小于10-8,因此取Tmin的值为2。也就是说,为了很好地改善合谋攻击问题,本方案设置在多轮共识验证过程中,当对同一笔交易进行共识验证的结果达成一致且一致次数达到两次时,此笔交易验证通过,而这需要的最少轮数是两轮。

2.3 节点随机分配算法

为保证节点分配时较高的随机性和不可预测性,本方案选择VRF(Verifiable Random Function,可验证随机函数)[21]作为节点随机分配算法的随机函数。

2.3.1可验证随机函数

所谓VRF就是指给定一个消息和一个私钥,可以计算出一个唯一确定的值,这个值唯一确定且不可预测,且可以验证。

LISP协议即位置标识和身份标识分离协议，它是一种针对互联网未来提出的一种全新的路由架构。LISP架构的提出可以给边缘网络更大的灵活性，同时对解决BGP路由表的膨胀和终端移动性增多等问题效果显著。因为它将隧道协议应用在不同LISP本地网络间，这在很大程度上有利于在虚拟网络下实现LISP架构。

VRF包含4个函数:VRFGEN、VRFVAL、VRFPROVE、VRFVER。

(1) VRFGEN:随机生成密钥,用来生成一对非对称加密的密钥,即一对非对称加密的公私钥(Vk,Sk)。

(2) VRFVAL:生成随机数输出value。

(3) VRFPROVE:证明函数,根据私钥和输入x计算,生成零知识证明proofx。

(4) VRFVER:验证函数,其他节点收到广播出来的输入x和零知识证明后,结合生成随机数的公钥,对随机数进行验证。

VRF生成随机数的流程是节点用VRFGEN生成的私钥和一个全网都知道的x作为输入,使用VRFVAL生成随机数value,VRFPROVE生成零知识证明proofx。

随机数生成后,该节点将零知识证明proofx和随机数value广播到全网,所有收到该零知识证明和随机数的人,均可通过公钥Vk和输入x验证随机数是否正确。VRF随机数生成和验证流程见图2。

VRF流程见图3。

图3 VRF流程

2.3.2参数设置与结果处理

2.3.1节提到的x是VRF生成随机数的种子参数。因VRF具有对于相同的输入,输出一定相同的特点,x需具有公开、随机且不断更新的特点。据此,本方案对VRF输入x进行设置,如式(7)所示。

x=H(Bh-1,{Ik})

(7)

式中:h表示当前区块高度,即第h个区块;Bh-1表示当前区块的上一区块的哈希值;{Ik}表示第k个验证节点与网络中相邻的两个验证节点互换一个数字得到的数字集合。

生成的随机数value均匀分布在值域范围内,定义输入x的最大位数是256位,则value的取值在0到2256之间,即value=2bits(value),value∈[0,2256),bits(value)是value的位数。对value进行处理,让验证节点根据结果进入相应的分片中,如式(8)所示。

(8)

2.3.3安全性分析

在区块链网络中,因状态分片的约束,BFT(拜占庭)节点数量有更高概率出现b≥2n/3,b表示拜占庭节点数,n表示网络中节点总数。且这些BFT节点可能形成合谋,将错误的事务验证确认,从而破坏整个链的数据一致性。而多轮验证有效解决了这个问题。由式(6)可知,多轮过程中合谋攻击发生概率与轮数T之间的关系为:

(9)

使用Python语言进行模拟计算,在分片内节点数L=30的前提下,计算出在多轮轮数T不同的情况下,分片中拜占庭节点发生合谋攻击的概率P,结果见表7。

表7 轮数T对合谋攻击概率P的影响

如表7所示,虽然选取的拜占庭比例F较高,但是采用多轮后,即使拜占庭比例F达到0.38,合谋攻击的概率也降到了10-8以下,跟未使用多轮时发生合谋攻击的概率(见表3)差异明显。使用多轮后合谋恶意验证的概率显著降低。

同时,在不同轮验证中,尽量避免两个以上的节点重复进入同一分片。根据VRF算法的随机性和不可预测性,本方案采用VRF随机数生成算法,在每一轮次对验证节点重新分配时,作恶节点无法通过控制随机数的生成进入到特定的分片中。每一轮次重新分配验证节点时,某个节点进入哪个分片无法预测,保证了随机性。

3 实 验

为验证本文方法确实可以降低合谋攻击的概率,且多轮验证牺牲的延迟不会降低系统总体的交易吞吐量TPS,进行模拟对比实验。目前比较流行的分片方案中都回避了合谋攻击问题,但OmniLedger分片方案在目前存在的分片方案中优势极为突出。尤其是在节点随机分配方面,启用验证器来加入系统,用一种安全的方法进行分片,这样恶意者就不能轻易地对一个分片进行攻击。OmniLedger还是第一个可提供“水平扩展”事务处理能力的分布式账本体系结构,与Visa等中心化支付处理系统相媲美,同时又不会影响安全性,兼具去中心化的特点。再看其发展前景,OmniLedger和Chainspace的结合极有可能创建一个开放式可扩展的智能合约平台,与其他分片协议对比,提供了更强大的可扩展性和安全性。综上,OmniLedger分片方案不仅在目前存在的分片方案中优势极为突出且发展前景良好,最重要的是,OmniLedger方案跟本方案都使用VRF协议将节点随机地分配到不同的分片上,且每个分片的共识都采用PBFT算法,有较好的对比性。故选择Omniledger分片方案为基础,与本方案做对比,对比两种方案的交易验证率、出块时间、吞吐量和在使用多轮验证后的差异。

3.1 实验基本设置

实验在实验室的8台服务器上运行,使用实验室局域网搭建的P2P测试网络作为实验所需的网络环境。使用相同配置的虚拟机模拟区块链网络中的验证节点,一个虚拟机代表一个验证节点,实验共设置1 800个节点,设置分片规模为30,每个分片中平均有60个验证节点。为了更直观地进行分析对比,在实验过程中除了交易产生的gas(单笔交易的消耗)费,其余gas费予以忽略。

3.2 实验设计及结果分析

3.2.1交易验证率对比实验

总节点数为1 800,设置拜占庭节点所占比例为0.3,运行Omniledger模拟系统和本方案系统,分别向每个分片内投放3 000条交易,其中包含20%不合法交易,以投放交易时刻作为0时刻,分别在0、5、15、20、25、30时刻记录Omniledger模拟系统和本方案模拟系统中每个分片交易处理情况,重复进行实验,计算平均交易验证率,并对结果加以对比分析。交易验证率对比见图4。

图4 交易验证率

如图4所示,两实验开始交易验证率均接近80%,随着时间推移,不合法交易所占的比例逐渐增加,故两系统的交易验证率均逐渐降低。可以看出,Omniledger模拟系统中的交易验证率变化不明显,说明有一部分不合法交易被验证通过了,即发生了合谋攻击。而在本方案的实验中,随着时间推移,验证率有较明显的降低,说明部分发生合谋的交易验证未被通过。由此实验可以证明,多轮验证方案可以有效降低合谋攻击发生的概率。

3.2.2出块时间对比实验

TPS=(gasLimit/gas)/time,其中:gasLimit是单个区块允许的最多gas总量;gas指的是单笔交易的消耗;time是区块出块时间。在进行交易处理能力对比实验之前,先进行平均出块时间对比实验。将Omniledger模拟系统以及本方案模拟系统分别运行10天,记录每天的区块高度,计算平均出块时间,再根据区块链浏览器统计相同时间下真实网络的平均出块时间,进行对比分析。平均出块时间见图5。

可以看出,实验室网络下,Omniledger模拟系统和本方案模拟系统平均出块时间相近,略低于真实网络中Omniledger系统的平均出块时间,三种情况下的平均出块时间均相对稳定,无剧烈变化。说明三种情况下,系统均稳定运行,且本方案系统在降低合谋攻击概率的同时,并没有牺牲出块时间。实验室搭建的P2P网络运行比较稳定,所以两种方案的平均出块时间均无剧烈变化。实验环境下未考虑除交易产生的gas费的其他费用,且真实网络下,验证节点遍布世界各地,数据的传输需要花费一定的时间,网络延迟比较大,所以真实网络下的Omniledger系统平均出块时间比实验环境下的高。

3.2.3吞吐量对比实验

在交易处理能力实验设计中,改变Omniledger模拟系统的设置,总节点数保持1 800不变,将分片数设为14,使得每个分片中验证节点数达到128,本方案系统保持不变。设置区块gasLimit大小为8 000 000。分别运行Omniledger模拟系统和本方案模拟系统,每隔一个区块向Omniledger模拟系统中投放84 000条交易,向本方案的模拟系统中投放180 000条交易,平均每个分片内500条交易。随着时间的增加,单个分片内的交易分别达到1 000、2 000、3 000、4 000、5 000、6 000等,单个分片内每产生一个区块,统计消耗的交易数量,重复实验,计算出每秒平均交易处理数量,并进行对比分析。平均交易处理能力见图6。

图6 平均交易处理能力

可以看出,随着时间的推移,交易不断累积,造成交易拥堵,因此两个模拟系统的交易处理能力都在慢慢降低。当系统中总验证节点数不变时,本方案的平均交易处理能力总体稍高于Omniledger系统的平均交易处理能力。虽然加入多轮验证方案使得交易验证的时间变长,但是在验证节点总数不变的情况下,增加了分片的数量,使得总体交易处理能力得到提升。可以证明,本方案在不影响系统性能甚至在系统性能稍有提升的情况下,很好地达到了抗合谋攻击的效果。

4 结 语

因状态分片的约束,验证节点的随机分配受到限制,即节点只能分配到存储其数据的分片中去。BFT节点数量有更高概率出现b≥2n/3,且这些BFT节点可能形成合谋,将错误的事务验证确认,从而破坏整个链的数据一致性。

针对上述问题,在区块链状态分片的基础上,加入抗合谋攻击的多轮验证方案。对同一笔交易进行多轮共识验证,直到验证结果达成一致的次数达到两次,有效降低了合谋攻击发生的概率,同时为避免资源浪费,设定本文方案的轮数上限。在每一轮次对验证节点重新分配时,选择VRF作为节点随机分配算法,并对产生的随机数进行调整,保证了验证节点在分配时的随机性和不可预测性。

实验表明,本文提出的抗合谋攻击的多轮验证方案合理可行,可以在不影响系统性能的情况下,有效降低合谋攻击发生的概率。但是,此方案尚存在一些不足,还需在后续工作中继续展开细致的研究,不断健全此方案。

(1) 倘若网络中存在只存储一个分片数据的节点、存储k个分片数据的节点,以及存在全节点时,还需具体分析合谋攻击发生的概率会有怎样的变化,然后提出相应的激励机制,鼓励网络中的节点向好的方向发展。

(2) 因区块链公开透明的特点,如何生成不可预测的随机数,是区块链面临的一个重要问题。在下一步工作中,需对如何获取更加公开、随机且无法预测的“种子”作为输入x展开研究。