Page 296 - 《软件学报》2020年第9期

张志威 等:区块链的数据管理技术综述 2917

Table 4 Comparision of the scalability of blockchains
表 4 区块链可扩展性比较
区块链 委员会节点加入条件 委员会节点替换策略 通讯复杂度 吞吐量与节点数关系
2
Elastico [49] PoW 全部替换 O(n ) 正比
Omniledger [105] Permissioned 部分替换 O(n) 正比
RapidChain [50] Permissioned 部分替换 O(n) 正比
2
ChainSpace [106] − − O(n ) 正比
Monoxide [107] PoW − − 正比
2
Hyperledger Fabric [60] Permissioned − O(n ) 反比
Elastico [49] 最早提出在公有链系统中采用分片模型.在 Elastico 中,整个网络被分为多个片.Elastico 首先会
要求所有节点计算基于工作量证明的验证字段(公式(1)).最先得到该函数哈希值的 C 个节点称为字典节点.字
典节点负责记录整个网络所有节点所对应的片.网络中的节点由其 PoW 提交的结果决定该节点将被分配到哪
个片,因而节点的分配具有随机性,并且恶意节点无法确定其是否分配到同一个片.同时,为防止女巫攻击,每个
新加入 Elastico 公有链的新节点都必须先执行 PoW,网络中的现有节点验证新节点的 PoW 并授权其加入网络.
当一笔交易提交到网络时,Elastico 会根据事务发送者的地址,随机分配到不同的片中执行.各个委员会内
对事务利用 PBFT 等机制达成共识,并最终将达成共识的事务提交到最终委员会.其中,最终委员会的节点也是
根据委员会节点 ID 进行随机选择.最终委员会在节点中运行 PBFT 共识协议,从而确保整个网络的一致性.由于
分片具有随机性,当每个分片的节点数量不低于 600 个时,其中三分之一的节点是恶意的概率为百万分之一,因
而系统的安全性可以得到保证.每执行一定数量的事务,Elastico 中所有的节点重新计算 PoW,以便重新分配节
点所属的片.为减少片间的通讯,Elastico 的消息通过 C 个字典节点进行传递,使得其最优的通讯复杂度为 O(Cn).
Elastico 在处理跨片事务的过程中,如果事务所需访问的数据在一个片被加锁,但在另一个片被拒绝,将会
导致被加锁的数据始终处于锁的状态.为了解决该问题,Omniledger [105] 在进行跨片事务验证时,采取两步验证
来避免出现由于部分非法输入而导致的事务中断.首先,在第 1 阶段,Omniledger 锁定所有输入分片以及输出分
片.所有输入分片检查自身所在的片内输入是否合法:如果合法,则生成一个包含本交易的区块签名的接收证
明;类似的,如果非法,则生成拒绝证明.当所有的输入都生成相应的证明,则可判定该事务可执行或取消.在第 2
阶段,如果所有的输入都返回接受证明,那么事务被执行.同时,终端创建并分发一个解锁请求.每个参与该事务
的节点验证并更新账本状态.如果存在一个输入所在的片返回拒绝证明,则事务取消.同时,终端生成并分发一
个解锁取消请求,输入所在的片接受该请求并将已加锁的数据解锁.
RapidChain [50] 同样在 Pow 共识协议下利用分片提高区块链可扩展性.与 Elastico 不同,RapidChain 不需要所
有节点都存储区块链的全部数据.在这种情况下,对于一个事务,例如输入输出分别为 In,Out 的事务 tx(In,Out),
有两种情况产生.第 1 种情况是事务的输入与输出均在同一片内.由于数据都存储于同一片中,这种情况下,直接
利用片中的节点间的共识机制即可处理该事务(RapidChain 利用近似的 PBFT 共识协议处理片中的事务).第 2
种情况为输入 In 与输出 Out 的数据处于不同片中.在这种情况下,不失一般性,假定输入包含 p 组数据 In={l 1 ,
l 2 ,…,l p },输出包含一组数据 Out.RapidChain 在处理该事务时,Out 所在的片将生成 p 个新的事务 tx i (l i ,O i ).每个事
务输入为 l i ,输出为 O i ,并且满足|l i |=|O i |.同时生成一个事务 tx p+1 (O,Out).其中,输入 O 包含 O 1 ,O 2 ,…,O p ,Out 为原
事务的输出.在进行事务验证时,输出所在的片首先要求 l i 所在的片验证事务 tx i (l i ,O i )是否可执行:如可执行,l i 所
在的片将事务 tx i 写入其账本,并发送 O i 至 Out 所在的片.最终,tx p+1 (O,O ut )可利用片内的共识机制进行验证.整个
过程通过将事务分割,实现了片间的共识.
Chainspace [106] 则旨在解决分片情况下数据的一致性问题.当数据在多个片均存在相同的备份,且不同片通
过不同的智能合约,均对该数据进行了修改,则可能导致不同片中数据不一致的情况出现.为了解决这个问题,
作者提出了事务痕迹的概念.事务痕迹包含这个事务所需要访问的所有数据,以及产生这些数据所调用的智能
合约.基于事务痕迹,作者提出了 S-BAC 共识算法.具体而言,当客户端提交事务时,Chainspace 根据事务痕迹,在
所有可能产生数据不一致的分片中分别执行共识算法,并且判断在一个分片内,该事务是否和其他事务产生冲