本文假设读者有一定的区块链背景知识。

1. 引言

        区块链起源于中本聪在2008年发表的比特币白皮书，它介绍了世界上第一个分布式加密货币。由于其核心技术——区块链具有数据持久化、防篡改、防抵赖、可靠性高以及去中心化等特点，在金融、征信、审计等众多重要领域具有广泛的应用前景，引起了国内外业界广泛的重视。区块链系统由数据层、网络层、共识层、激励层、合约层、应用层组成。其中，数据层包含交易数据和加密技术等；在网络层，区块链采用P2P网络模型，消息转发和传播机制也属于网络层的范畴；共识层包含不同区块链系统采用的各种共识机制，大多数区块链系统都采用了基于工作量证明PoW共识机制；激励层则决定了系统中货币的发行机制与分配机制；合约层和应用层，可以运行智能合约，支持去中心化应用的开发。

然而目前基于比特币风格的区块链有以下几个显著的缺点：

1）可伸缩性差：随着系统中节点数量不断增加，无法提高系统的吞吐率和交易处理速度。

  2）吞吐率低：比特币系统平均每秒处理的交易数量是7笔。

  3）确认延迟高：由于比特币区块产生速度为10分钟，确认延迟至少10分钟，而且由于分叉现象，习惯上认为60分钟后才可以认为交易已经被确认。

  4）高能耗：由于PoW机制，节点需要通过挖矿来争取记账权，因此会消耗大量的电力资源。据估计，比特币挖矿每年消耗数十T瓦时电量，足够一个中型国家的耗电量。

因此，为了使得区块链能满足实际应用需求，必须解决以上问题，尤其需要提高区块链系统的可伸缩性和吞吐率。针对这些问题，近年来涌现出了多种解决方案，其中主要有两种，一种是基于有向无环图（DAG）的方法，将单链结构变成图结构；另外一种是基于分区（Sharding）的方法，将单链分布存储变成多链并行分布存储。

2. DAG图型区块链

DAG图型区块链主要改进了比特币区块链的数据层和共识层，如下图所示。

图1 DAG图型区块链与比特币的不同

2.1系统概述

2013年9月，NXT社区中有用户提出以DAG图作为区块链的底层数据结构以提高系统整体性能，将比特币区块链系统中的链式存储结构改成DAG图存储，即区块DAG，DAG图中连接粗粒度的区块。2014年12月出现第一个细粒度区块的图型区块链系统RaiBlocks。每笔交易作为单独的存储单元，或者说，一个图区块中，只包含一笔交易。Byteball是另一个细粒度区块的分布式账本系统，它通过最短路径最优父节点算法，选出一条全网共识的主链。DAGCoin虽然提出较早，但是后并没有代码实现，直到来Byteball出现。它在Byteball的基础上进行修改，让每一笔交易都直接参与维护全网的交易顺序。这样，图型区块链进一步演变成了完全抛弃比特币区块链的一种解决方案，当交易发起后，直接广播全网，无需打包区块，提高了处理速度。

2016年7月推出了IOTA系统，IOTA里既没有区块，也没有挖矿和矿工，这就代表没有交易费，提高了整个网络的吞吐量。另一个备受关注的图型区块链系统是Nano（由Raiblocks更名而来），采用了一个用户一条链的方式，只记录自己的交易，也只有自己可以修改记录，不与其它帐户共享数据，从而使所有的交易都可以并行执行，能提供秒级的交易确认速度和无限可伸缩性。

2.2 系统模型

DAG图型区块链沿用比特币区块链的P2P网络结构来组织全网节点，P2P网络的特点是网络中的每个节点都是对等的地位且互相连接，不存在类似于C/S架构中的中心化服务器，不存在特殊层级的节点，这保证了区块链系统的自治性、开放性和公平性，每个节点都承担着验证数据区块、保存数据区块、转发消息等功能。

比特币区块链上，新发布的区块会加入到原先的最长链之上，并且以所有节点都认为最长的链为准，依次无限延伸。而DAG中，一个网络节点要发起一笔新的交易时，需要在网络中找2笔（或更多）其他交易去验证，并且将自己新发起的交易指向这两笔交易，整个网络就是这样一点一点扩大出去的。正因为这样的设计，整个网络中验证交易的责任从传统的矿工转移到了网络的每个节点上，这样的设计促使网络中每一个节点都积极的参与验证其它交易。

2.3 数据结构

比特币区块链将粒度较大的区块连接在一起，形成不可篡改的链条，而DAG图区块链采用了以每笔交易为基本存储单位和处理单位，相当于细粒度的区块。在执行过程中，由每笔交易对它之前的两笔或以上交易进行验证。如图2所示，DAG区块链中每个节点只保存一笔交易和该节点验证过的节点哈希值，节点U1被U2a和U2b两个节点所验证，节点U2a被节点U3a、U3b和U5a所验证。

图2 DAG区块链的数据结构

当用户向区块链中添加数据时，它创建一个新的存储单元并将其广播给其他节点，每个单元中必须包含一个或多个先前单元的哈希值，与本单元直接相连的单元称之为父单元，这样做的目的是使得各单元之间有序，如果尝试修改其中一个单元，必须改变它所有的子孙单元，如此就保证了数据的防篡改性。如果沿着父子链的历史单元前进，当同一个单元被多个后来的单元引用时，会观察到很多分叉，当同一个单元引用多个较早单元时，就会出现融合。最终形成一个有向无环图DAG结构。

2.4 共识机制

DAG图型区块链采用的共识机制分为PoS、Witness、DPoS、Tangle几种，下面分别介绍。

2.4.1 基于权益证明(PoS)

最初由PeerCoin区块链系统所采用，该方法与要求证明人执行一定量的计算工作不同，权益证明要求证明人提供一定数量加密货币所有权即可，权益证明机制根据每个节点拥有代币的比例和时间，等比例地降低节点的挖矿难度，从而加快了寻找随机数的速度。这种共识机制可以缩短达成共识所需的时间，但本质上仍然需要网络中的节点进行挖矿运算。值得一提的是，以太坊目前虽然采用PoW共识机制，但是其创始人Buterin提出，以太坊会经过一个过渡期PoW+PoS（Casper协议），然后转变共识机制为PoS，目的是为了提高网络效率。由此可见，PoS相比于PoW更适合实际应用。

2.4.2 见证人机制(Witness)

Byteball区块链中提出的共识机制，它根据规则选取主链从而决定交易的全局顺序，见证人（Witeness）是系统中长期实名并且声誉比较高的组织或者个人，他们参与系统维护，并自愿频繁发起交易单元的节点，对于消极工作甚至作弊的见证人，可以经过用户投票更换。在Byteball中，从任何一个顶端单元出发到达创世单元的最优路径称为候选主链（Candidate Mainchain）。最优路径通过选择最优父单元产生，全部节点运行一致的选取最优父单元算法，递归的选取出主链。如图3描述了稳定主链和稳定点的形成。

图3 稳定主链和稳定点的形成

最优父单元选取策略需满足的3个条件：

条件1. 在选择最优父单元时，见证级别最高的父单元为最优父单元；

条件2. 如果见证级别相同，则单元级别最低的作为最优父单元；

条件3. 如果见证级别和单元级别都相同，则选择单元哈希值（base64编码）更小的作为最优父单元。

其中，单元级别是由当前单元出发至创世单元的最长路径长度定义为单元级别，见证级别是从当前单元的最优父单元开始沿主链回溯，并对路径中不同见证人进行计数（相同见证人只计数1次），当遇到的见证人数足够多时（超过大多数的已知见证人，以当前单元的见证人列表为准）停止回溯；然后计算停止位置的单元级别，将其称作当前单元的见证级别。

不同的候选主链会在某个单元位置交叉（最差的情况是在创世单元交叉），该交叉点称为稳定点（Stable Point）。对于所有候选主链，从稳定点到创世单元的路径完全相同，该路径称为稳定主链（Stable Mainchain），如图3所示。稳定主链是一条确定的路径，根据这条路径，与之相关的所有单元均可以在此基础上进行排序，其序号称为主链序号（MCI, Main Chain Index）。创世单元的MCI为0，依次加1直到链尾。对于不在主链上的单元，其MCI等于主链上最先包含（直接或者间接）该单元的那个单元的MCI。MCI代表了从主链视角来看单元在DAG中的总序，总序使得全网达成共识。DagCoin是建立在Byteball上层的全新区块链，因此它的共识机制和Byteball相同。

2.4.3 基于代理权益证明(DPoS)

该方法是基于权益证明的改进，Nano项目采用了DPoS共识机制，DPoS的方法由EOS系统创始人提出，即每位持币人都有权投票选出代理节点，持币量少的人也能参与投票。在Nano中每个节点基于持有的XRB（Nano中的流通货币）数量来选取代表，拥有的XRB越高，所选的代表权重就越高，最终全网会产生若干个权重较高的代表来验证交易，维护网络运行。为了使一笔交易生效，节点必须发送交易到验证器节点，即，所选取的高权重代表，该节点验证交易，然后将其广播到与其连接的其他验证器节点。每个后续验证器节点都会执行相同的验证和传递过程，直到交易传遍整个网络。

2.4.4 缠结（Tangle）

Tangle是IOTA系统采用的共识机制，是一个有向无环图（DAG）数据结构。随着越来越多的交易被添加到缠结中，一个“权重”被添加到附属的祖先交易中。当交易有足够的权重时，交易将显示“确认”状态。理论上，如果整个网络中有足够的交易流，这个确认过程可以在快到几秒钟内完成。该共识机制的创新之处在于不再采用网络中的一个子集（如矿工）去专门负责维护共识，而是全网所有的参与者都进行网络交易的验证工作。IOTA中共识机制与交易过程是一体的，它是其内生的组成部分，可以使IOTA系统在没有任何交易费用的情况下进行扩展。

2.5 小结

表1总结了几个比特币区块链和DAG图型区块链出现的年份（Year）、数据结构（Data Structure）、体系结构（Architecture）、共识机制（Consensus）、项目状态（Project Status）、开源情况（Open Source）几个方面的情况。在数据结构上比特币区块链将多笔交易打包进区块，区块之间形成稳定的链条，而Byteball、Dagcoin、Nano和IOTA区块链中，每笔交易以及父母单元的哈希值构成一个基本单元，各单元之间通过哈希值紧密连接，从而形成一个有向无环图，其中NXT较为特殊，它将仍然以粗粒度的区块作为基本单位，只是不再是一个区块连接一个区块，而是一个区块连接若干个区块。在体系结构上，列举的区块链均采用P2P网络结构。在共识机制上，比特币采用PoW共识机制，而以太坊采用PoW+PoS混合的Casper共识机制，DAG图型区块链中，NXT采用了PoS共识机制，Dagcoin系统是基于Byteball的源码修改而来，所以也暂时采用和Byteball相同的Witness共识机制。目前，表1中的各个项目都已经通过各种方式发行货币，开始流通，属于在生产环境下的系统，大多数已经开源，但Dagcoin仍然没有开放源码，而IOTA只是开放了部分源码，对系统中的协调器部分代码闭源，因此导致其公平性备受争议。

表1 DAG与传统区块链的对比

3. 分区(Sharding)型区块链

分区型区块链主要在系统模型和共识层对区块链进行了改进，每个区块中的数据结构几乎和比特币相同，因此，可以参考比特币的数据结构。

3.1 系统概述

数据库中拓展存储容量的一个有效方法是采用分片技术，其目的是将庞大的数据集划分成多个子数据集，分别存储在不同的节点上，使得不同节点上的交易可以被并行处理。对于区块链系统，分区机制通过将全网节点划分成不同的集合，划分系统的通信资源、计算资源、存储资源，使每个集合独立并行地运行，从而提高区块链系统的吞吐率和可伸缩性。

目前，已经提出许多基于分区的区块链的解决方案，最初提出将分区技术应用于公有链的是Elastico系统，Elastico系统将区块链网络划分成了多个组，每个组处理互不相交的交易数据，在每个组中，独立运行PBFT共识机制,然而PBFT协议需要极高的网络带宽，且对于可任意加入的公有链系统来说，容易遭受女巫攻击（Sybil attack）。因此，Elastico系统设计了基于PoW的准入机制，防止女巫攻击。分区的方法虽然提高了吞吐率和可伸缩性，但是它没有解决跨区域的交易产生的事务原子性问题。

在此基础上，又提出了Zilliqa系统和OmniLedger系统。它们在事务的原子性问题上，对Elastico系统进行了改进，其中，OmniLedger系统在跨区交易过程中，加入了两段封锁提交协议，保证了事务的跨区事务的原子性，并使用了称为ByzCoinX的共识机制，它是由ByzCoin改进而来。随后RapidChain系统被提出，它将PBFT与纠错偏码（erasure-code）相结合，减少了PBFT带来的巨大通信量，但是它对网络带宽仍有较高的要求。Monoxide是一种在继续沿用PoW共识机制的分区方案，它提出了诸葛连弩挖矿（Chu-ko-nu mining）算法解决了PoW共识机制在分区后算力被稀释，从而导致对单区域恶意攻击难度降低的问题，也通过最终一致性原则解决了跨区域交易的事务原子性问题。

分区型区块链在数据层几乎和比特币相同，但是它改变了网络结构，采用了多层的P2P网络，并且消息转发的方法也进行了优化。部分分区型区块链在共识层采用PBFT类型的共识机制，而Monoxide在解决了算力稀释问题的情况下，仍然采用了PoW共识机制。

图4 由8个节点构成的分区型区块链

3.2 系统模型

区块链是一种线性的单链结构，单链结构并发度低。分区的方法将全网的节点分成了若干个组，每个分组相当于一个相对独立的区块链系统，每个组中有若干个节点。所有的区块数据也被划分到多个组中，每一组只保存和本分组相关联的区块数据，但是这些数据组合起来仍然是一个完整的账本数据，尽管物理上是分区存储多个小组中的多条链在逻辑上组成了全局链。如果全网包含n个分组，区块数据被分成n份，分别保存在各组中，全网所有节点的存储开销缩小为原来的1/n。同时，在需要处理的交易数量一定的情况下，由于每组可以分别处理交易，使得系统吞吐量变为原来的n，在不考虑跨区域交易的情况下，通信量也会随着分组而减少为原来的1/n，系统的伸缩性也得到了提升，因为随着分组的增多，系统整体处理能也会呈线性增长。

如图4，在一个由8节点组成的网络中，每4个节点组成一个分组，各组内组成了P2P网络，各组之间也可以互相通信，这样组成了一个两层的P2P网络。一个完整的区块链数据被分割到2份，每个分组中保存其中的一部分。而各个分组内的P2P网络节点保存着相同的数据，因此构成了一个可以并行处理交易数据并产生区块的系统。

3.3 数据结构

分区型区块链的各个分组中包含了多个并行延长的区块链，它们的区块结构和比特币区块链类似，如图5，分区区块链和比特币区块链都是由一系列包含了交易信息的区块组成，它的基本组成单元我们称之为区块。每个区块分为区块头和区块体两部分，区块头包含了版本号、父区块哈希值、时间戳、难度值、随机数和默克尔树根等信息，区块体包含了所有具体交易信息，这些信息经过默克尔树生成过程，最终生成树根保存在区块头中。如上所述，区块头中包含了前一个区块的哈希值，子区块又会包含它的哈希值，这样就形成了一条联系紧密的链条，其中某个部分修改，就要修改之后的所有区块。特例是区块链中的首个区块叫做创世区块（genesis block），它没有父区块。

图5 分区区块链的数据结构

3.4 共识机制

分区区块链的共识过程发生在每个小组内部，在每组中并行地运行着共识协议，处理并存储交易信息。部分分区型区块链系统之所以不使用PoW共识机制，是因为分区带来算力稀释问题导致单区域对攻击难度降低，所以采用了PBFT协议，它可以避免基于算力的恶意攻击，但是PBFT会伴随着巨大的通信开销，同时也面临着女巫攻击的风险，通常这些系统提高了准入系统的要求，使得其成为系统内节点的难度大大提高，从而避免女巫攻击。Elastico采用了PBFT共识机制，OmniLedger采用的是ByzCoinX共识机制，而RapidChain采用了改进的PBFT协议，Monoxide则采用了PoW共识机制，因为它通过诸葛连弩挖矿（Chu-ko-nu mining）算法解决了PoW共识机制在分区后算力被稀释问题，使得攻击单个分区和攻击整个系统一样困难。

3.4.1 实用拜占庭协议PBFT及其改进协议

        实用拜占庭协议PBFT共识协议每一轮共包括3个阶段：预准备阶段、准备阶段和确认阶段。在准备阶段，由主节点发布包含待验证记录的预准备消息。接受到预准备消息后，每一个节点进入准备阶段，主节点向所有节点发送包含待验证记录的准备消息，每一个节点验证其正确性，将正确记录保存下来并发送给其他节点。直到某一个节点接收到2f个不同节点发送的与准备阶段接收的记录一致的正确记录，则该节点向其他节点广播确认消息，系统进入确认阶段。在确认阶段，直到每个诚实节点接收到2f+1个确认消息，协议终止，各节点对该记录达成共识。

        Elastico系统采用了PBFT共识机制。OmniLedger系统中的ByzCoinX共识机制实际上是对PBFT的修改，但是相对减少了协议的通信开销。OmniLedger区块链由一条身份链和多条子链构成，它使用了一个随机分配协议将所有的验证器（全节点）分配到不同的子链中。在每个子链中仍使用PBFT共识算法达成一致性。而在RapidChain中延续了PBFT共识协议，但是它通过被称之为Gossip-IDA的消息传递协议减少了通信带来的巨大开销。它将每一个即将传播出的消息分割成若干个块，在网络中传播消息的碎片而不是整个消息从而减少了通信量，各个节点通过接收到的消息通过纠错偏码的方法组合成原消息。

3.4.2 诸葛连弩挖矿算法（Chu-ko-nu）

比特币等大多数区块链系统都采用PoW共识机制，PoW最初用来应对服务与资源滥用、或是拒绝服务攻击等。在比特币中，必须选择一个节点来记录一段时间内的交易信息。最简单的办法是随机选择，但是这种方法极易受到攻击而失效。另外的办法是提高成为记账人的条件，即工作量证明。

诸葛连弩挖矿算法是对基于工作量证明机制算法的改进，PoW算法矿工节点经过算力竞争，由胜出者产生全系统中唯一的下一个区块，它的安全风险在于当恶意节点掌握全网算力一半以上时，可以逆转已经发生的交易造成双(double spending)问题，由于这样的算力很难达成，这种攻击难以实现。在分区后，总体的挖矿算力被划分到不同的分组中，会导致攻击单个区域只需要达到该区域的算力的一半即可，所以在分区后仍然使用PoW会带来安全隐患。

诸葛连弩挖矿算法允许任何一个分区内矿工在成功解决哈希难题时，同时在多个分区产生多个区块，但是每个分区最多产生一个区块，通过这种方式，使得每个分区内的矿工算力放大，从而达到攻击单个区域和攻击整个系统有着相同量级的算力要求。

表2 分区区块链与传统区块链的对比

表2总结了几个比特币区块链和分区型区块链出现的年份年份（Year）、数据结构（Data Structure）、体系结构（Architecture）、共识机制（Consensus）、项目状态（Project Status）、开源情况（Open Source）几个方面的情况。在数据结构方面，分区区块链保留了比特币区块链中大部分的数据结构，均以区块为单位组织数据。相比于数据结构，分区区块链变化较大的是体系结构，分区区块链不再是所有的节点组成一个P2P网络，而是将多个节点分成若干组，每组中有局部的P2P网络，组和组之间又形成一个高层次的P2P网络，形成分区-P2P的模型。在共识机制方面，Elastico采用PBFT协议，但是该协议面临着巨大通信开销，因此Zilliqa共识将PBFT与EC-Schnorr多重签名结合，Rapidchain共识将PBFT与ErasureCode相结合减少了通信量，而OmniLedger中的ByzCoinX是指每个分组包含了若干验证器节点，分区内通过PBFT达成共识后，各验证器节点之间通信，分区之间不再需要运行PBFT协议，从而也减少了通信量。特别的，Monoxide系统采用了PoW共识机制，它解决了分区后总算力被稀释导致的PoW共识机制的安全性问题。上述的分区系统中，只有Zilliqa开始投入运营，并且公开源码，其它的分区区块链均处于实验阶段，且没有公开源码。

4. 总结与展望

表3列举了各区块链系统的性能指标，包含区块链类型（Type）、容错性（Fault Tolerance）、是否需要挖矿（Mining）、交易手续费（Transaction Fee）、去中心化（Decentralization）、交易确认延迟（TX Confirm）、吞吐率（Throughput）以及可拓展性（Scalability）。

表3 各区块链系统的性能对比

在容错性方面，两种传统区块链和Monoxide容错率都达到1/2，而采用PBFT类共识的分区区块链Elastico、Zilliqa、OmniLedger以及RapidChain的容错率和PBFT本身的容错率一致，为1/3。在挖矿方面，采用了PoW类共识的传统区块链以及Monoxide需要挖矿，而DAG图型区块链NXT、DagCoin、Byteball、Nano以及IOTA和采用PBFT类共识的Elastico、Zilliqa、OmniLedger以及RapidChain分区区块链不需要挖矿。在交易手续费方面，两种传统区块链一般需要支付较多的手续费才可以在系统中发起交易，DAG图型区块链中NXT、Dagcoin、Byteball只需要支付较少的手续费，Nano、IOTA和分区型区块链不需要手续费。在交易确认速度上比特币至少10分钟，以太坊约18s，NXT约1分钟，Dagcoin约30s，Byteball在1分钟以上，Nano在10s之内，IOTA在60s之内，Elastico约800s，OmniLedger、RapidChain、Monoxide分别是20s、8s和15秒。在吞吐率方面，以每秒处理的交易次数为单位（TPS），比特币达到约7TPS,以太坊平均30TPS，NXT约100TPS，Nano和Zilliqa在理论上分别可达7kTPS和1.4kTPS,而OmniLedger、RapidChain和Monoxide在实验条件下最高可达6kTPS、7kTPS和6kTPS。在去中心化程度上，两种传统区块链、列举的分区区块链、NXT以及Nano是完全去中心化的，而DAG图型区块链Byteball和IOTA的共识机制中分别存在存在着 “见证人”、“协调器”等中心化的组件，因此并不是完全去中心化。在可拓展性上，两种传统区块链几乎无法实现拓展，而DAG图型区块链有较好的可拓展性，分区区块链在理论上可以随着网络节点和分组数的增加实现线性的无限拓展。安全性方面，传统区块链既有理论上基于算力的容错模型，又经过实际运行，充分证实了其安全可靠，分区区块链经过分区，面临着单分区遭受攻击的风险，DAG图型区块链中的中心化组件遭受攻击也给系统的安全性带来隐患。

图6 区块链不可能三角

        就目前来看，无论采取哪种区块链的变种结构，都很难同时在去中心化性、扩展性、安全性三个方面都取得令人满意的效果，如图6的去中心化需求-扩展性-安全性的不可能三角，每种技术都很难同时在这三方面获得良好的效果。因此，考虑不同的业务应用对三个性质的要求各不相同，未来可能需要一种能够在不可能三角之间灵活调节的区块链系统，甚至是一种能够自适应调节的区块链系统，以满足各种业务不同的去中心化性、扩展性、和安全性需求。

本文来自东北大学大数据研究组

作者：张长贵，李晓华，张岩峰，聂铁铮，于戈

http://faculty.neu.edu.cn/cc/zhangyf/