两种新区块链的分析：基于 DAG 和基于分片

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

1 简介

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

然而，当前基于比特币的区块链具有以下显着缺点：

1）可扩展性差：随着系统中节点数量的不断增加，系统的吞吐率和交易处理速度得不到提升。

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

3）确认延迟高：由于比特币区块生成速度为10分钟，确认延迟至少为10分钟，并且由于分叉现象，习惯上认为60分钟后交易才能确认。

4）高能耗：由于采用PoW机制，节点需要通过挖矿的方式来争夺记账权，消耗了大量的电能资源。 据估计，比特币挖矿每年消耗数十兆字节的电力，足够一个中等国家使用。

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

2. DAG图区块链

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

图1 DAG图区块链与比特币的区别

2.1 系统概述

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

IOTA系统于2016年7月上线，IOTA没有区块，没有挖矿和矿工，也就是说没有交易手续费，提高了整个网络的吞吐量。 另一个备受关注的图形化区块链系统是Nano（改名自Raiblocks），它采用一用户一链的方式，只记录自己的交易，并且只有自己可以修改记录，不与其他人共享数据accounts ，让所有的交易可以并行执行，可以提供秒级的交易确认速度和无限的可扩展性。

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 中，从任何顶部单元到创世单元的最佳路径称为候选主链。 通过选择最优父单元生成最优路径，所有节点运行相同的算法选择最优父单元，递归选择主链。 图 3 描绘了稳定主干和稳定点的形成。

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

最优父单元选择策略需要满足三个条件：

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

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

条件3.如果witness level和unit level相同，则选择hash值（base64编码）较小的unit作为最优parent unit。

其中，单元层级定义为当前单元到创世单元的最长路径长度，见证层级从当前单元的最优父单元沿主链回溯，统计链中的不同见证人。路径（同一个witness只算一次），当遇到的witness足够多时（超过大部分已知witness，基于当前单元的witness list），停止回溯； 然后计算止损位的单位层级，将其划分为当前单元格的见证层级。

不同的候选主链会在某个单元位置相交（最坏情况是在创世单元），这个相交点称为稳定点（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是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中的各个项目已经通过各种方式发行货币并开始流通。 它属于生产环境中的系统。 协调器的部分代码是闭源的，因此其公平性存在争议。

表1 DAG与传统区块链对比

3.分片区块链

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

3.1 系统概述

扩展数据库存储容量的一种有效方法是使用分片技术。 目的是将一个庞大的数据集划分成多个子数据集，分别存储在不同的节点上，从而可以并行处理不同节点上的交易。 对于区块链系统，分区机制将整个网络节点划分为不同的集合，将系统的通信资源、计算资源、存储资源进行划分，并使各个集合独立并行运行，从而提高网络的吞吐量和吞吐量。区块链系统。 可扩展性。

目前，已经提出了很多基于分区的区块链解决方案。 Elastico 系统最初是为了将分区技术应用到公链上而提出的。 Elastico系统将区块链网络划分为多个组，每个组处理不相交 在每个组中，PBFT共识机制独立运行。 但是PBFT协议对网络带宽要求极高，对于可以随意加入的公链系统来说，容易受到Sybil攻击。 因此，Elastico 系统设计了基于 PoW 的接入机制来防止 Sybil 攻击。 分区方式虽然提高了吞吐量和扩展性，但并没有解决跨地域交易产生的交易原子性问题。

在此基础上，提出了 Zilliqa 系统和 OmniLedger 系统。 他们在事务的原子性方面改进了 Elastico 系统。 其中，OmniLedger系统在跨区域交易时增加了两个区块提交协议，以保证跨区域交易的原子性。 是ByzCoinX的共识机制，是在ByzCoin的基础上改进而来的。 随后提出了RapidChain系统，将PBFT与纠删码相结合，减少了PBFT带来的巨大流量，但对网络带宽的要求仍然很高。 Monoxide 是一种继续使用 PoW 共识机制的分区方案。 提出Chu-ko-nu挖矿算法，解决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所示。分区区块链和比特币区块链均由一系列包含交易信息的区块组成，它的基本单位称为块。 每个区块分为两部分：区块头和区块体。 区块头包含版本号、父区块哈希值、时间戳、难度值、随机数、默克尔树根等信息。 区块体包含所有具体的交易信息，存储在 Merkle 树的生成过程中，生成的树的根最终存储在区块头中。 如前所述，区块头包含前一个区块的哈希值，子区块将包含其哈希值，从而形成一个紧密相连的链。 如果修改了其中的一部分，则必须修改所有块。 特殊情况是区块链中的第一个块称为创世块，它没有父块。

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

3.4 共识机制

分区区块链的共识过程发生在每个组内，共识协议在每个组内并行运行以处理和存储交易信息。 部分分区区块链系统之所以不使用PoW共识机制，是因为分区带来了算力的稀释，降低了攻击单个区域的难度，所以采用PBFT协议，可以避免基于区块链的恶意攻击算力，但 PBFT 会伴随着巨大的通信开销，也面临女巫攻击的风险。 通常这些系统会增加对系统的访问权限，使其更难成为系统中的节点，从而避免女巫攻击。 Elastico采用PBFT共识机制，OmniLedger采用ByzCoinX共识机制，RapidChain采用改进的PBFT协议，Monoxide采用PoW共识机制，因为是通过Chu-ko-nu挖矿算法解决的。 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算法矿工节点争夺算力后，获胜者将产生整个系统唯一的下一个区块。 其安全风险在于，当恶意节点掌握整个区块的网络算力过半时，有可能逆转已经发生的交易，造成双花问题。 由于这样的计算能力很难达到，所以这种攻击很难实现。 分区后整体挖矿算力被分成不同的组，这会导致对单个区域的攻击只能达到该区域算力的一半，所以分区后仍然使用PoW会带来安全隐患。

诸葛连奴挖矿算法允许任何分区的矿工在成功解决哈希问题后同时在多个分区中生成多个块，但每个分区最多生成一个块。 这样，每个分区网络中矿工的算力都被放大了，使得攻击单个区域和攻击整个系统的算力需求具有相同的量级。

3.5 总结

表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 已经上线运行并发布了源代码。 其他分区区块链都处于实验阶段，还没有发布源代码。

四、总结与展望

表3列出了各个区块链系统的性能指标，包括区块链类型（Type）、容错性（Fault Tolerance）、是否需要挖矿（Mining）、交易费用（Transaction Fee）、去中心化（Decentralization）、交易确认延迟（ TX Confirm）、吞吐量（Throughput）和可扩展性（Scalability）。

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

在容错性方面，传统区块链和Monoxide的容错率都达到了1/2，而使用PBFT共识的分区区块链Elastico、Zilliqa、OmniLedger、RapidChain的容错率与容错率一致PBFT 本身的速率。 1/3。 在挖矿方面，传统区块链和Monoxide采用PoW型共识需要挖矿，而基于DAG图的区块链NXT、DagCoin、Byteball、Nano、IOTA和采用PBFT型的Elastico、Zilliqa、OmniLedger、RapidChain共识分区区块链不需要挖矿。 在交易费用方面，两大传统区块链普遍需要支付更多的费用才能在系统中发起交易。 在DAG图区块链中，NXT、Dagcoin、Byteball只需要支付较少的费用。 、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。 In terms of decentralization, the two traditional blockchains, the enumerated partitioned blockchains, NXT and Nano are completely decentralized, while the consensus mechanisms of the DAG graph blockchain Byteball and IOTA exist “ Centralized components such as "witness" and "coordinator", so they are not completely decentralized. In terms of scalability, the two traditional blockchains are almost impossible to expand, while the DAG graph blockchain has better scalability, and the partitioned blockchain can theoretically be realized with the increase in the number of network nodes and groups. Linear infinite expansion. In terms of security, the traditional blockchain not only has a fault-tolerant model based on computing power in theory, but also has been proved to be safe and reliable through actual operation. After partitioning, the partitioned blockchain faces the risk of a single partition being attacked. The DAG graph Attacks on centralized components in the blockchain also bring hidden dangers to the security of the system.

Figure 6 Blockchain Impossible Triangle

From the current point of view, no matter which variant structure of the blockchain is adopted, it is difficult to achieve satisfactory results in the three aspects of decentralization, scalability, and security at the same time, as shown in Figure 6. Decentralization requirements - Impossible triangle of scalability-security, it is difficult for each technology to achieve good results in these three aspects at the same time. Therefore, considering that different business applications have different requirements for the three properties, a blockchain system that can be flexibly adjusted between impossible triangles may be needed in the future, or even a blockchain system that can be adaptively adjusted , to meet the different decentralization, scalability, and security requirements of various businesses.

This article is from the Big Data Research Group of Northeastern University