先提了现在最先进的分片解决方案:Monoxide。说他能根据账户分配机制减少imbalanced transaction (TX)。然后这个TX会导致hot shards,从而跨分片TX可能会经历等待无限期时间来接受确认。
0.2 本文解决的问题是hot shards:将被大量TX阻塞的碎片称为热碎片。
1.标记hot shards;
2.减少跨分片TX
0.3 本文做的工作为BrokerChain下定义:
为基于账户/余额的状态切分而设计的交叉切分区块链协议。
做了什么工作:
从本质上讲,BrokerChain利用细粒度的状态分区和帐户分段。通过经纪人帐户处理跨切分TX。
通过哪些属性来和之前的方法进行比较:
系统吞吐量、事务确认延迟、事务池的队列大小和工作负载平衡。
1.介绍关于分片的介绍:
分片(Sharding):以太坊区块链扩容加速解决方案_链圈子
第一段介绍了一下分片的意思,第二段介绍了三种分片方法。
1.1 三种分片方法在每一轮常规分片协议中,在委员会成立后,根据切片协议,将若干不相交的TX集分配给这些委员会。然后,委员会在本地运行特定的共识协议,如实用拜占庭容错协议(PBFT),以实现对指定TX集的本地共识。
分片策略还停留在理论阶段,现有的分片方法依赖于UTXO(未使用的交易输出)或账户\余额交易模型 。
1.1.1 network sharding网络分片。 这种方法把整个区块链划分为更小的委员会,因此被认定为其他两种分片方法的基础
1.1.2 transaction sharding交易分片。
1.1.3 state sharding状态分片。由于需要由所有分片来分摊区块链的所有状态,因此是最困难的一种分片方法
1.2 动机在Monoxide中,用户账户根据其地址的前几位分布到不同的区块链碎片,旨在协同存储所有帐户状态。虽然这种方式可以提高系统吞吐量,但不可避免地会产生跨分片TX。同时,通过引入接力交易(relay TXs)来确保分片交易的原子性。但是接力交易会导致分片的拥塞,我们称这种被大量TX堵塞的碎片为热分片。在每个热碎片中,TXs无法及时处理,可能会经历较长的确认延迟。
通过实验证明,拥挤的热碎片是由活动帐户引起的,这些帐户经常在其关联的碎片中启动大量交易。因此,各分片的交易数量是不均衡的。这些观察结果背后的见解是,Monoxide采用的账户部署方法没有考虑账户发动交易的频率。
当分片数量很大时,几乎所有的交易都是跨分片交易。当一个收款账户在热分片中时,Monoxide可能会导致无限的发送确认延迟。
1.3 挑战在基于帐户/余额的状态的分片中分配大量交易时,一个大问题是如何在所有分片之间达到负载平衡,从而避免热分片的产生,保证跨分片交易的原子性。 而BrokerChain旨在生成更少的跨分片交易,并确保所有分片的负载平衡。
BrokerChain在协议层将帐户的状态进行划分,并对帐户进行归类。帐户状态可以由多个分片分摊,以实现所有分片之间的工作负载平衡。
为了缓解热分片问题,BrokerChain还包括跨分片交易处理机制,该机制可以保证跨分片TX的持续时间有限的最终原子性。
2. 准备工作和相关工作 2.1 两种交易模型:UTXO和交易/余额在UTXO模型下,一个交易可能包含多个输入和输出。在帐户/余额模型下,用户可以使用其帐户中的存款生成一个交易。以太坊采用帐户/余额模型,因为它很简单,每个TX只有一个发送方帐户和一个接收方帐户。
2.2 代表性的分片解决方案介绍了分片方案的发展历史与一些典型方案
2.3 分片交易处理介绍了一些现有的分片方案。
与现有的研究相比,BrokerChain利用了经纪人账户的优势来处理跨分片的交易。此外,BrokerChain可以通过细粒度的状态分区( fine-grained state-partition )和账户分割机制在分配交易的同时实现工作负载的平衡。
3 协议设计和BrokerChain 3.1 BrokerCain概述与Rapidchain类似,首先定义一个固定长度的epoch周期。为避免女巫攻击,区块节点需要在加入分片前通过解决哈希难题来确认身份。此周期的哈希难题由上一个周期给出。一旦一个结点成功解决了哈希难题,解决方案的最后几位比特会指出该节点应加入到哪个分片里面。
3.1.1 两种分片BrokerChain中有两种分片。BrokerChain的分片区块链需要S个矿工分片和一个分区分片。每个分片都通过PBFT协议来达成各自的块内共识并避免分叉。
1.矿工分片(M-shard):矿工分片打包交易来产生交易块并在每个周期的开头实现分片内的共识
2.分区分片(P-shard):该分片在每个周期中以自适应的方式划分账户状态
3.1.2 BrokerCain的四个连续阶段1.交易区块共识阶段:在一个周期开始时,每个矿工分片都会从交易池里打包交易,并通过运行PBFt协议发布多个交易块。矿工区块在一个周期内产生的交易块数量取决于分片内的网络参数,如带宽等。而矿工分片产生的第一个新交易区块遵循状态区块(也就是图2中的),记录着前一周期的状态划分结果。
2.状态图分区阶段。分区分片从产生的区块中读取交易并持续更新所有账户的账户图。一旦挖矿分片生产出了当前周期中的所有交易块,状态图就固定了。然后,协议开始对状态图进行划分,以实现所有碎片之间的工作负载平衡。
3.状态区块共识阶段。在前一阶段对所有账户的状态图进行分区后,BrokerChain将执行账户分割,这在第III-C节中有详细描述。为了对状态图分区和账户分割的结果达成共识,再次利用PBFT协议生成一个状态块(由表示),然后将其添加到分区分片链中。
4.状态重配置阶段。对划分结果达成共识后,分区分块广播包含S分区的状态图的状态区块到所有相关联的矿工分片。当接收到状态块时,矿工分片从状态块读取状态分区结果,并相应地重新配置其状态,以便可以根据新的帐户状态将下一个周期(第t+1个)中的交易分配到指定的分片。
3.2 状态图分区
分区分片监视着矿工分片产生的交易块,并根据导入的交易实时建立/更新状态图。当接受到指定的最小发送块数时,状态图就被固定了。正如图2中状态图分区阶段一样,状态图的每个顶点表示一个帐户。边权重(由表示)定义为涉及相应帐户的交易数,而顶点权重(由表示)则代表该账户相关的所有交易之和。对于固定状态图,分区分片使用Metis对图中的所有帐户进行分区,Metis是一种著名的启发式图分区工具。Metis可以将状态图划分为不重叠的S个部分,同时减少跨切分交易的数量,并考虑所有切分之间的工作负载平衡。
3.2.1 划分账户的动机强制用户设立多个账户是不合理的,因此设计了一种账户分割机制( account segmentation mechanism)。这个机制在区块链架构的协议层工作。
提出的账户分割机制具有以下优点。i) 不强制用户开立多个帐户。ii)用户帐户的状态可以轻松划分并存储在多个碎片中。iii)通过这种用户透明的方式,可以方便地实现所有碎片的工作负载平衡,从而消除热碎片。
3.2.2 划分账户的例子假设现在有三个账户以及三笔要处理的交易,如下所示:
假设现在有两个分片,而账户A,B分别存储在两个分片中。那么不妨假设C设立在分片2中。如果用Monoxide的分片方法,这三笔交易会产生四个跨分片交易。而如果采用BrokerChain的方法,那跨分片交易会减少到两个。
表面上看,BrokerChain好像就是把一个账户分割了成了两个账户,分配存款后放入不同的分片。但值得注意的是,这两个账户的地址是相同的。也就是说,BrokerCain协议在某个分片上存储着另一个分片上的帐户存款,并且他们具有相同的账户地址。研究者采用以太坊的计数器机制(帐户状态的nonce)来识别位于另一个分片上的帐户的多个状态。
3.2.3 改良的状态树要启用状态图分区和帐户分割 *** 作,BrokerChain必须强制每个碎片以了解所有帐户的存储映射。因此,研究者基于以太坊的状态树设计了一种改进的分片状态树(mSST),以存储帐户状态。
与状态树不同,BrokerChain的mSST构建在所有帐户的存储映射上。研究者用向量 来表示这个存储映射,其中每个e都是一个布尔值,然后S是矿工分片的数量。BrokerCain需要为每个帐户配置存储映射。为1代表这个账户的状态被分片 i 给存储了,如果在中有多个元素被置为1,代表该账户被多个对应的分片存储了状态。
3.2.4. mSST的账户结构改进的分片状态树有一个向量,里面存储着与分区数量相同的布尔值,布尔值等于1代表这个分片存储了该账户
某个用户的账户状态 被表示为:
其中表示用户µ的帐户地址,以及 表示nonce字段,该字段表示从地址发送的交易数或用户µ生成的合同创建 *** 作。然后 表示值字段,该字段显示用户的存款。最后 是表示帐户类型的字段。帐户类型包括用户帐户和智能合约帐户。
对于某个特定的账户而言,不同的分片为这个账户维护的不同的mSST。这些状态树的区别在于值,nonce以及代码。而当某个分片不再存储这个账户时,其对应的mSST及字段将被删除。这个分片只需要更新目标帐户的状态,而目标帐户状态的任何更改都将导致mSST块头里state root的更改。因此,很容易保持多个关联分片中帐户状态的一致性。
3.2.5 查询复杂度通过在mSST中查询存储映射,我们可以很容易地确定一个交易是片内交易还是片间交易。查询时间复杂度为O(1)。因此,该协议可以通过查询所有分片的帐户状态的值字段得出账户的存款。存款查询时间复杂度为O(), 其中是存储了该账户状态的分片数量。
4 处理跨分片交易尽管账户分割机制能够将一个账户细分为多个较小的账户,但问题是区块链系统需要招募一些愿意充当中介的账户,以帮助处理跨分片交易。我们称这些中介机构为经纪人账户,简称为经纪人账户。在本节中,研究者将介绍BrokerCain如何通过经纪人处理跨分片交易。
成为经纪人的一个基本要求是其账户拥有足够数量的货币。对于打算成为经纪人的系统用户,他们可以请求将其资产抵押给受信任的第三方或特殊的智能合同。然后,BrokerCain协议为那些感兴趣的系统用户提供了代理资格。为了激励系统用户扮演经纪人的角色,需要一种激励机制。这种激励机制的设计是我们今后的工作。
仍以图三为例。假设C是一个经纪人,其帐户被分割并存储在分片1和分片2中。现在,我们有了一个原始交易,即发送方A通过代理C向接收方B传输v个货币。这里,我们将分片#1称为源分片,将分片#2称为此发送的目标分片。利用图5,我们介绍了跨分片发送处理的成功和失败案例。
4.1 跨分片交易成功案例中的原子性保证成功的跨分片交易的五个 *** 作描述如下。
4.1.1 *** 作1:生成原始交易账户A首先选择一个适当的锁定货币时间(由表示),这个时间其实就是从产生到解锁货币的区块产生间隔的时间。的定义如下:
代表经纪人C的nonce
代表发送方账户A的nonce。
是发送方A的签名,由ECDSA算法计算得出。
随后,A将原始交易发送给经纪人C。
4.1.2 *** 作2:生成前半部分跨分片交易收到后,经纪人C生成跨分片交易的前半部分 。此时分片#1的块高度表示为。的定义如下:
Type1 是的标志
是经纪人C的签名
之后,被广播到区块链网络上。当其他分片中的所有结点收到了,他们依次执行以下 *** 作:
1.用、确认。
2.获取发件人的公钥并使用签名计算发件人的帐户地址。
3.通过查询mSST,分片结点知道这笔交易的来源分片和目标分片。
4.利用Kademlia路径选择协议,转发到分片#1和分片#2。在确认是正确的以及转账方A的账户余额是充足的情况下,会被添加到分片#1的交易池中,然后等待被打包进区块链中。
4.1.3 *** 作3:确认广播结束后,分片#1中的区块链结点应该把包括进自己的区块,此时区块高为(通常大于)。然后转账方A把v个货币转账给经纪人C,这些货币在区块高为至+时被锁定。发送方A的nonce将增加1以防止重播攻击
4.1.4 *** 作4:生成后半部分跨分片交易当经纪人C认为已经被确认之后,C会生成 后半部分跨分片交易其定义如下:
Type2是的标签。会被广播到区块链网络上,最终到达目标分片,即分片#2。 在确认是正确的以及经纪人C的账户余额是充足的情况下,会被添加到分片#2的交易池中,然后等待被打包进区块链中。
4.1.5 *** 作5:确认如果分片#1的区块高小于+/2的话,那么分片#2中的结点收到后会将其打包放入一个新的区块。首先经纪人C转账V个货币给收款人B,然后分片#2的的账户状态才会变化。同时经纪人C的nonce增长1以抵御重放攻击。
在跨分片交易的成功案例中,一旦被成功写入目标分片的区块链(分片#2),收款方B就能收到这笔v个货币的转账。从另外一个方面讲,只有当分片#1的块高度大于 +时,A向C支付的v个货币才能解锁,从而发给经纪人C。
4.2 跨分片交易失败案例中的原子性保证根据我们在图4中所示的设计,所有碎片都相互共享其块头,其中包括基本的块高度信息。因此,当分片#1中的区块高大于 +/2时,如果分片#2还未将写入区块中,我们就认为没有被分片#2承认。此失败结果很可能是由恶意经纪人引起的,该经纪人打算盗用打款人帐户的锁定货币。
为了处理此类失败案例,BrokerChain执行以下步骤以保证跨分片交易的原子性。首先,会被包含在分片#2中,而这个分片的nonce会更新。然后分片#2中的区块链结点会发送以下关于的确认信息到分片#1作为失败的证据(用表示):
dest代表目标分片的标志
代表所在的目标分片的块的高度
代表默克尔树路径。包含了从默克尔树根节点到所在结点之间相关联的所有哈希值。被用来证明被分片#2中的一个区块给写入了。
一旦分片#1中的结点收到了失败证据并且证明了的正确性,分片#1就清楚已经被包括在分片#2中而并没有被包括进去。然后会被写进来源分片也就是分片#1的区块中,它的高度小于 + 。最后,在 *** 作3中锁定的货币会被返还给转账方A。
无论一笔跨分片交易成功与否,在目的分片中只有或者中的一个会被写入。一旦在广播过程中丢失了,目标分片就可以重新产生发送一遍。
5 BrokerChain的性质分析 5.1 处理双花攻击 5.1.1 如果转账方A是恶意结点恶意发件人帐户可能会发起双花攻击。在这种攻击中,转账方A可能会在来源分片中创建一个双花交易和原始交易 表示为:
其中A'是转账方A的另一个帐户,而 是的nonce。
为了实现双花攻击,的 必须与在前半部分交易 中写入的 一模一样。所以和中只有一个能被来源分片(分片#1)确认。而只有当被来源分片确认了,经纪人分片才会生成。通过这种方式,经纪人 C可以抵御恶意转账人发起的双花攻击。
5.1.2 如果经纪人C是恶意结点当被来源分片确认时,一个恶意的经纪人C可能会对目标分片实行双花攻击:
和5.1.1相同,由于的 和 的 完全相同,双花攻击不能成功。且为了防止经纪人C盗用转账方A的冻结货币,此时BrokerChain会强制执行此类跨分片交易的处理例程,以使其进入转账失败的流程。
总之,通过拟议的资产抵押和令牌锁机制,BrokerCain可以确保跨分片交易在双花攻击威胁下的原子性。
5.2 货币锁定时间的建议设置回想一下,在前面描述的跨分片交易处理的 *** 作1中,发送方需要首先选择适当的货币锁定持续时间来创建原始交易。问题是如何为原始交易设置这样的货币锁定时间。一种可行的方法是根据当前观察到的系统吞吐量设置令牌锁持续时间。经验推荐的设置是设置为处理跨分片交易的平均延迟的20倍。
5.3 跨分片共识的分析如图5所示,在处理跨分片交易期间发生的跨分片共识包括以下两种情况:i)在交易成功的情况下,代理C必须验证 包含在来源分片的区块链中,ii)在交易失败情况下,来源分片的节点需要验证故障证明 由目标分片发送。
因此,在成功的情况下,跨分片交易验证的计算复杂性为O(1)。在失败情况下,跨碎片验证的计算复杂性为O(n),其中n是来源分片中区块链节点的数量。因此,BrokerChain可以利用代理人的角色将链上验证转换为链外验证,从而降低这种跨分片验证的开销。
关于跨分片交易的确认延迟,理论上比分片内部的确认延迟长两倍。这是因为必须按顺序在来源分片和目标分片上确认跨碎片发送。相反,BrokerChain可以根据代理人的信誉降低确认延迟。如果经纪人完全受分片区块链信任,则和可以同时执行。因此,从技术上讲,它们的确认延迟可以接近于片内交易的确认延迟。
5.4 有限持续时间的最终原子性Monoxide保证了跨分片交易的最终原子性。然而,Monoxide没有规定中继交易的确认时间。因此,在Monoxide中处理跨分片交易可能需要很长时间。相反,BrokerCain可以确保每个跨分片交易都在预定义的货币锁定时间内完成。成功处理跨分片交易后,接收方将收到发送方帐户的抵押货币。否则,转账人的抵押货币将由经纪人退还。因此,我们声称BrokerChain确保了跨分片交易的持续时间的最终原子性。
6 性能评估 6.1 设置 6.1.1 实验原型和交易驱动的模拟器为了对BrokerChain进行评估,我们设计了一个实验原型和一个TX驱动的模拟器。实验原型以java语言进行开发并部署在阿里云上。然后我们同时运行了基于阿里云的原型系统以及运行历史交易的分片模拟器。
6.1.2 数据集及其使用我们使用真实的以太坊交易作为数据集,其中包含从2015年8月7日至2016年2月13日记录的167万个历史交易。在每个周期开始时,个交易按时间顺序以一定的到达率重播到区块链分片系统。所以这些交易会根据他们账户的状态被分配给不同的矿工分片。
6.1.3 对比我们考虑了以下三种技术。Monoxide根据账户的前几位地址对其进行分配;LBF定期更新账户分配来实现交易的负载均衡;Metis纯粹强调帐户状态图上的均衡分区。
6.1.4 度量我们首先研究了几个关键的系统参数对各种系统指标的影响,包括交易吞吐量、交易的确认延迟和交易池的队列大小。关于工作负载性能,我们测量了分片工作负载的总和以及差异。
6.2 系统吞吐量和交易确认延迟首先,我们使用基于云端的实验原型来评估吞吐量和事务确认延迟。我们从阿里云租用了112台虚拟机来部署我们的原型系统,总共包括16个分片。每个虚拟机配置1个CPU核心(Intel Xeon, 2.5/3.2GHz)和2GB内存。所有节点之间的网络连接带宽设置为5mbps。对于每个矿工分片,其出块间隔为8秒,每个区块能容纳500笔交易。交易到达率固定为500 交易 /秒。由于Metis与交易的吞吐量和延迟无关,我们只比较了BrokerChain与Monoxide、LBF的性能。实验结果如表一所示。
接下来,我们通过调优更复杂的系统参数来进行全面的交易驱动模拟。出块时间保持八秒不变,但是区块内交易数量上升到2000个。通过分别改变发送到达率和分片数,我们研究了不同分片方法下的平均吞吐量和发送确认延迟。模拟结果如图6所示。图6(a)显示了当交易到达率固定为3200个交易每秒时,当S(矿工分片的数量)从8增加到32时,平均交易确认延迟减小。
这是因为当矿工分片的数量(S)小于32时,每个分片中到达的交易超过了分片的处理能力。然而,当S超过32时,BrokerChain的延迟在到达率3200以下收敛。当S=64时,BrokerCain的平均发送延迟低至14.87秒。下面这张图片说明了当分片数量固定为32时,不同的分片方法在变化的交易到达率下的变化。
BrokerChain与其他两种分片方式相比展示出了压倒性的低延迟,即使是在高交易到达率的情况下。
图6(c)和图6(d)分别展示了分片数量和变化的交易到达率对吞吐量的影响。尽管在大多数方法中,大量分片有助于提高吞吐量,但图6(c)显示,当分片数量超过52时,增多分片的好处变得饱和。这是因为分片过多反而增加了跨分片交易的数量。这些结果还表明,当发送到达率超过4000时,BrokerCain的吞吐量将达到饱和,因为当前设置会影响事务处理能力
6.3 交易池的队列大小我们通过监测交易池的队列大小来研究交易池的变化。我们总共使用了167万笔交易,以稳定速率持续输入区块链系统的交易池,直到所有的交易都被使用过了。根据VISA的吞吐量,即大约4000 ,我们把K固定为40,分片数固定为32,并将交易到达率在{2500, 3200, 4000, 5000} 笔交易每秒区域内波动。
从图7可以看出,在开始的几百秒内,当不断注入交易时,队列的大小会不断增长。当167万个交易全部被消耗后,队列大小会缩小。在所有的方法中,Monoxide保持线性增长的队列,队列尺寸最大。当交易到达率较低时,例如2500交易 /秒,LBF与BrokerChain的队列大小相近。然而,一旦交易到达率较大,BrokerChain比LBF和Monoxide维持的交易池更小。我们将这一结果归功于以下几点:
首先,Monoxide倾向于将交易放入少量的热碎片中。该策略会生成大量跨分片交易,导致处理延迟较大。因此,在Monoxide的交易池总是比较大的。其次,LBF尝试将交易均匀地分布到所有分片上,在较小的交易到达率下,交易池的队列大小保持在较低的水平。但是LBF在较高的到达率情况下,无法及时处理跨分片交易。相比之下,BrokerChain能够及时处理交易池中的所有交易。
6.4 分段账户数量的影响回想一下,代理的帐户可以被分割并部署到不同的碎片。现在我们通过改变K和修正S=64, =16e4来评估分段账户数量的影响。回想一下,经纪人帐户可以被分割并部署到不同的分片。现在我们通过改变K并将S固定为64, 固定为16e4来评估分片账户数量的影响。在10个周期中工作负载的情况如下所示(总的系统工作负载是所有分片的TX工作负载的总和):
我们可以看到,随着K的增加,系统的总工作负载、最大工作负载和分片工作负载的方差都在减少。原因是有了更多的分段帐户,经纪人可以帮助减少跨分片交易的数量,并使交易的工作负载比其他分片方法更均衡。
6.5 分片工作负载的表现通过图9,我们研究了所有分片方法下的分片工作量总量、最大工作量和方差。通过设定等于8e4,每个周期的分片数量等于16,K=40,图9(a)显示BrokerChain的系统总工作负载与其他方法相比最低。
这是因为BrokerChain能减少跨分片交易的数量。为了更清楚地展示这一点,我们在图9(d)中比较了跨分片TXs的比例。
此外,我们还想知道系统工作负载的总体细分情况。从图9(b)和图9(c)可以看出,与其他3种分片方法相比,BrokerChain的工作量方差更小,工作量峰值更小。
在下一组模拟中,为了找出分片数量对工作负载性能的影响,我们改变S,同时固定NTX=8e4, K=40。如图10(a)所示,我们可以看到,S的增加会导致系统总负载的增加。
这是因为跨分片交易的数量会随着分片数量的增加而增加。图10(b)和图10(c)显示,BrokerChain优于其他分片方法。
此外,BrokerChain在数据上也有最少的异常值。这意味着,与其他两种方法相比,BrokerChain可以使分片工作负载更加平衡和稳定。同样,从图10(d)可以看出,BrokerChain的跨分片交易比率仍然是最低的。
最后,为了评估每个时期输入交易的数量对工作负载性能的影响,我们在{8e4, 12e4, 16e4}内改变NTX,并修正S=64和K=40。图11(a)显示,与其他方法相比,BrokerChain保持了大约10%-20%的系统工作负载下降。虽然NTX的增加会导致系统工作负载的增加,但从图11(b)、图11(c)和图11(d)可以看出,与基线相比,BrokerChain产生的方差更低,最大分片工作负载更低,跨分片比率更低。
7 总结BrokerChain作为一个跨分片协议用于基于账户的区块链状态分片。BrokerChain通过细粒度状态图划分和帐户分割机制实现各分片之间的负载平衡。BrokerChain通过利用经纪人帐户来处理跨分片交易。基于云端的原型和交易驱动的模拟器的评估结果表明,BrokerChain在交易吞吐量、确认延迟、交易池队列大小和工作负载平衡方面都优于最先进的分片方法。在未来的工作中,我们计划研究激励账户充当经纪人的激励机制。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)