摘要

区块链技术迎来又一个爆发的一年，区块链的挑战仍有待解决。本文分析了基于区块链的比特币和Bitcoin-NG系统的特点，提出了一种改进的实现区块链系统的方法，将原链的结构替换为graph数据结构。它被命名为GraphChain。每个区块代表一个交易并包含交易者的余额状态。另外，众所周知，比特币系统中的所有交易都会被一个矿工打包，会浪费很多精力，所以提高资源利用率的另一种方法是将原来的竞争矿工的方式改为选举和并行挖矿。研究人员通过python模拟了具有graph结构和并行挖掘的区块链，并提出了可以同时提高容量和性能的概念性新graph模型。

索引词——区块链、性能、graph链、并行挖掘

I.引言 

区块链是去中心化数字货币的后端，其中一个著名的例子是比特币[1]。与传统系统相比，区块链具有去中心化、不可变等特点。根据调查论文Bitcoin and Beyond[5]，区块链创造性地结合了数十年研究的现有贡献，以解决通过互联网传递价值的基本问题。

现在区块链已经广为人知和广泛使用。该领域逐渐拓宽，原始设计的一些局限性和缺点正在显现，这是有关容量和性能可扩展性的问题之一。最早著名的区块链网络堵塞例子发生在 2017 年一款名为CryptoKitties的基于区块链的游戏中。太多人试图通过以太坊[7]网络购买CryptoKitties，很快以太坊就超过了其最大处理能力，以太坊上的所有交易都被延迟。

到目前为止，比特币[1]和以太坊[7]已经达到了每秒交易数 (TPS) 的最低性能瓶颈。他们俩都在寻找改进的解决方案。需要执行新协议，因为新解决方案应该解决以前区块链的缺点。商业应用依赖于高性能区块链。大多数公链都需要能够处理来自世界各地的用户请求。 所以性能很重要。

迄今为止报道的公开文献有限，该领域的研究很少，学术界也很少尝试提高性能。相比之下，许多工业区块链产品以性能为产品卖点，其中大多数通过调整区块链参数来接近更高的性能。只有少数系统化的方法已经被执行，例如Bitcoin-NG[2]（见下文）、Bitshares [3]/EOS、IoTA和更早的DagCoin [4]。

值得一提的是，在论文Bitcoin-NG [2]：A Scalable Blockchain Protocol中，通过领导人选举进行了改进。尽管如此，区块链上某一时刻只允许一个领导者操作，这使得操作是有序的，容量和性能仍然是一个重大挑战。

基于这个想法，我们提出了这种方法来提高区块链的性能。对于可以提高基础性能的高性能区块链协议，需要改变数据结构。链式数据结构和工作量证明算法被设计成一个单用户操作系统，只允许一个用户接触区块链数据。在我们的实验中，并行挖掘可以明显提高TPS。同时，多领导者可以增加网络稳定性，防止因没有矿工而导致网络堵塞的情况。

将数据结构从链更改为graph可以允许多个领导者并行挖掘。Graph数据结构在本实验中命名为GraphChain。GraphChain和并行挖矿将区块链变成了一个多用户操作系统，允许多个领导者贡献他们的计算资源。这也有利于交易确认时间。

本文详细介绍了区块链系统的新协议。这项工作的主要贡献是提供了一种构建具有实用性能的区块链的方法的解决方案。新的数据结构发挥了灵活的框架作用，新的挖掘机制提高了整体性能。结果可能是使用场景，例如微交易系统、大数据区块链或新一代银行系统。

II.模式与目标

众所周知，区块链系统由N个全节点组成。全节点带有完整的历史交易信息，节点与可靠的点对点网络相连。同时有M个矿工在等待交易请求，并准备将交易数据打包到区块链中。

在经典区块链中，所有矿工都在通过迭代一个称为nonce的数字来竞争解决数学难题。

谜题有一个具有一定难度的目标。解决难题后，将创建一个新块。最近的交易被打包到新区块中。如下文所述，在这个模型上发现了几个问题：

1. 大部分用于计算的电力能量都被浪费了，因为太多的竞争导致只有一个获胜者。只允许一个获胜者意味着这个矿工就像一个中央锁来限制区块链的性能。

2. 交易需要等待下一个新的区块生成被确认。这意味着交易无法实时完成。

可以通过简单地调整区块链参数来构建性能更好的区块链系统，例如增加区块大小。但是，从技术调查[5]的角度来看，暗示改变块大小或块的时间间隔并不能一路提高性能和容量。其他方面存在瓶颈，例如全节点大小限制或链节点分叉过多。因此，需要一种完全不同的设计/模型来克服这一限制。研究人员系统地提高了性能和容量，设计了包括数据结构、挖掘机制和存储分区的架构。

下面看本实验的具体过程：

1. 将当前链式数据结构改为graph数据结构。基本数据结构的改变使以下机制（见下面的第2点）改进成为可能。

2. 将单台矿机改为多台矿机进行并行挖矿。这提高了区块链的性能，交易将在更短的时间内处理。 这项工作的主要贡献是它提高了区块链的性能，交易将在更短的时间内处理。

3.数据分片。虽然通过并行挖掘提高了TPS，但数据分片让区块链能够跨不同节点存储更多交易。完整节点将不再存在，因为每个节点可能存储整个交易历史的不同部分。

本实验的这一过程表明，将数据结构更改为GraphChain的目标是打破传统区块链系统的中心锁，通过并行挖掘获得可扩展的区块链性能，提高TPS并减少交易确认时间。

图1. GraphChain的结构

III.链和graph

众所周知，链式数据结构已广泛应用于比特币[1]和其他产品中。IoTA和DagCoin[4]中使用了有向无环图（DAG）。

GraphChain数据结构思想的灵感来自于DAG。改变数据结构的主要原因是想办法用并行操作代替顺序操作。GraphChain 的数据结构如图1所示。GraphChain是一种定制的数据结构，它不是典型的DAG。区块通常有两个输入和两个输出，区块代表交易后账户的状态。另一个重要的一点是输入有方向。如果是发送账户，它应该连接到上面的输入点。因此，收款帐户应与下面的输入点连接。

与链不同，GraphChain不需要将交易打包到单个线程中。使用GraphChain，交易可以由不同的矿工并行添加。

IV. 并行采矿

新的机制被提出来，在世界范围内的M（尽可能多的）矿工中选择m（数量）个领导者。在论文Bitcoin-NG[2]中，引入了领导者。矿工们曾经通过解开谜题和生成新的区块来获得奖励。现在，在通过解开谜题进行的平行采矿中，矿工已经成为领导者。领导者在接下来的时间里负责任。

与传统的区块链例如比特币[1]不同，新机制要求赢得选举的矿工在其值班时间内保持在线。有时会发生意外，比如电源问题，或者互联网连接问题，都会意外发生。如果领导者不在线，其他人就不能代替他保持在线来处理交易。这使得整个区块链系统被封锁（交易需要太长的时间来确认）。在这种情况下，需要有冗余来保持系统的运行。这需要不止一个领导人待命，以增加系统的稳定性。领导人作为一个团队工作。为了让矿工们合作，制定了一套规则，即《2018年第一届IEEE热信息中心网络国际会议论文集》（HotICN 2018）。下面，有具体的细节和内容。

A. 矿工到Leader 

在并行挖矿的基础上，当矿工被选为Leader 时，Leader 在一定时间内履行职责。在一个滑动时间窗口中，m（数量）个矿工被选为领导者。根据比特币[1]系统，研究人员将选举间隔时间设置为10分钟，将服务时间设置为1小时。结果是有6个领导者在一个滑动时间窗口内在线。领导者在值班时监听点对点网络并等待新的交易请求。

一旦新交易被广播，领导者将其打包到GraphChain 中。由于领导者之间的通信延迟，同一交易有可能被不同的领导者多次打包到GraphChain 中。只有m（数量）个领导者并行工作，导致GraphChain最多有m（数量）个分叉。

B. 账户 

账户通常以零余额开始。账户余额因交易而发生变化。一笔交易中至少涉及两个账户。账户块是一个非交易块，通常只有一个输出（图1）。 交易块代表两个账户的余额状态。

C. 发行和撤销资产 

区块发行或撤销资产需要某个私钥或多个密钥的特殊签名。任何资产高于零的非交易区块都应在机制设计中仔细验证。

D. 交易 

任何交易都应该发生在至少两个账户之间。发件人余额必须高于零。如图1所示，每个交易块通常有两个输入和两个输出。一个交易块代表两个账户的当前余额，一个是发送方账户，另一个是接收方账户。

E. 可扩展性

比特币[1]和相关系统的可扩展性是有限的。原因包括区块大小、整体数据量、区块传播速度和矿工能力。 在比特币[1]的设计中，选择了一名矿工来打包过去10分钟的交易。 该规则就像中央锁一样，阻止其他矿工贡献。

并行挖掘使独立的交易可以同时发生。让我们来看看现实生活中的两种场景：1.父母给孩子一些零用钱 2.商店收货。零用钱的交易例子发生在每个家庭。他们是独立的，很多父母可以并行转账。第二种交易是按顺序进行的，接受每笔交易的商户都会改变自己的余额。这两种类型的交易都很常见，有时它们是混合的。 并行挖矿将通过允许更多领导者参与挖矿任务来加速交易处理。

F. 选举领导人 

在GraphChain和Bitcoin-NG的设计中，领导人扮演着比特币[1]的矿工的角色。 在比特币中，找到新区块的矿工有权将过去 10 分钟的交易打包到新区块中。 在 GraphChain 系统中，选举领导者在一定时间内打包交易。

它带来了一个问题：比特币的矿工在挖矿结束后完成他的任务，GraphChain和Bitcoin-NG的领导者需要在选举完成后继续工作。任何leader都可能因为异常随时下线，除非增加冗余，否则无法保证可用性。在GraphChain或Bitcoin-NG中，如果没有leader在线，整个系统就会被卡住，这就是为什么应该有多个leader在线作为副本的原因。领导者在竞争时一起工作。领导者的数量取决于系统性能要求。

领导者的选举方式与比特币矿工找到新区块的方式类似。该方法基于PoW。矿工想成为领导者，需要全球范围的竞争。不同之处在于，比特币将新区块奖励给获胜矿工，GraphChain将资格授予获胜矿工。成为领导者的矿工将与其他领导者合作一段时间，将用户交易打包到GraphChain中。

G. 追加交易 原始的 PoW 算法设定了一个困难的目标。 谁先计算出这个谜题，谁就会广播结果并创建下一个块。 在这种情况下，有无限的竞争者，只有其中一个可以获胜。

在并行挖掘场景中，有限数量的领导者试图解决更简单的难题。 如果一个leader重试了几次，仍然找不到满足目标的结果，这个leader就会放弃。因为这个谜题很简单，所以假设至少有一个领导者应该能够得到这个谜题的答案并创建下一个交易块。

结果是，一个交易可能由不同的领导者创建多个块。创建者重试次数较少的区块将是幸运的新区块。PoW算法的简单修改称为幸运证明（PoL）。

领导者将交易附加到GraphChain数据结构中。由于领导者数量有限，PoL算法发挥了一种高效的方式。任何领导者都可以从任何未打包的交易中选择追加到GraphChain中，不同的订单都可以。

为了提高效率，可以应用算法让不同的领导者按不同的顺序对交易进行排序，以确保所有交易至少应附加到数据结构中一次。 这是计算验证的一种冗余。

V.数据分片

链式数据结构很难“分片”，因为区块链不能按账户拆分。

现有的解决方案建议通过快照保持一定时间段的区块链。账户余额表也需要保持独立。丢弃部分区块链数据会导致数据验证困难。

此外，这里的“分片”一词不同于以太坊[7]的“分片”，它在Github项目页面https://github.com/ethereum/sharding/blob/develop/docs/doc.md中有描述。以太坊的分片是通过双层设计来增加容量。在GraphChain中，分片可以通过用户拆分数据来完成。

由于生产环境对TPS的要求很高，数据的整体规模会增长得非常快。假设有2000TPS，每天大约会产生24G的数据。较少的PC将满足充当完整克隆节点的条件。

GraphChain上的数据分片按账户划分数据。通常，用户帐户在内部表示为哈希。一个节点可以简单地设计为保留与哈希以“a”或“b”开头的帐户相关的所有交易信息。通过这种配置，海量数据可以由多个具有冗余的节点分开保存。

在GraphChain中，每个区块代表两个账户状态的历史。验证交易的正确性可以分为两个步骤：验证与一个用户帐户相关的所有交易历史记录，并对所有用户帐户重复相同的操作。当历史数据足够大时，多节点并行验证将是一个不错的选择。

VI.指标

为了证明所提出的性能改进，需要测量单领导和多领导的绩效。

第一个实验（图2）假设有4000个交易正在等待打包，性能是通过不同数量的领导者来衡量的。等待中的4000笔交易实际上是一个很大的阻塞案例。实际上，应尽快处理新交易。

在这个实验中，领导者可以自由选择任何交易写入GraphChain。如果网络延迟，领导者可能会尝试打包其他领导者已经完成的交易。根据最长链规则，在两条链长度相同的情况下，使用PoL算法来决定去哪一个分叉。

它还发现，当更多的交易被附加到GraphChain中时，整体性能会下降。原因是当链长增加时，数据库需要查找链来验证交易是否已经存在于区块中。这个问题是通过添加缓存来解决的。应用此技术后，我们可以在图2中观察到相当平均的性能。

第二个实验（图3）测量了区块链网络的稳定性。如果所有领导人都离线，则网络堵塞，因为无法处理任何交易。研究人员使用简单吉尔伯特模型[6]方法对网络状态进行建模。假设所有领导者都有机会p下线和1-p机会重新上线。 测量了单独领导者和多领导者的稳定性。

图2. 添加矿工的并行挖矿性能

VII.实验设置 

实验源代码列在Github https://github.com/ProofOfLuck/graph。

MySQL数据库用于存储graph、领导者和交易数据。它假设点对点网络传输是可靠的。实验没有实现那部分。在比特币中，数据存储在不同的全节点中，并被复制（相互复制）。这部分已经被证明是可行的。在GraphChain中，这部分是跟随比特币的。因此，数据存储在集中式MySQL数据库中不会影响性能测量。

交易直接插入到数据库表中。下面，每个脚本文件有两个主要步骤和细节： 

A. 模拟选举 

矿工首先通过选举成为领导者。在实际情况下，选举需要困难和竞争。在这个模拟代码中，矿工将通过解决简单的谜题（具有一些固定目标的迭代哈希）成为领导者。

B. 模拟挖矿 

领导者观察数据库的交易表，看是否有新交易出现。一旦出现新交易，空闲的领导者会在GraphChain中查询其他领导者是否已经完成将交易打包到块中。如果没有，当前的leader会立即开始打包。

检查下面的代码（Github存储库中的实验源代码https://github.com/ProofOfLuck/graph）：election.py通过解决简单的基于哈希的难题来选举矿工成为领导者。leader.py扮演领导者的角色，将交易打包成块。leader auto.py 结合了选举和leader 功能，继续扮演leader的角色，在leader期满时重新选举。

send.py是用户将余额发送给另一个用户的脚本。send auto.py模拟一组用户之间的自动交易。

钱包new.py生成一个私钥。私钥是身份，可用于矿工或普通用户。为简单起见，身份的公钥将用作钱包地址。

第一个实验（图2）寻找区块链可以实现多少性能的证据。在图2中，从相同数量的交易中模拟不同数量的矿工在挖掘任务中。据观察，随着在GraphChain上工作的矿工数量的增加，系统处理了更多的交易。该模拟在一台计算机上完成。模拟代码已被调整为故意放慢速度，以防止过度使用CPU。

第二个实验（图3）是模拟矿工每个人都有机会下线并重新上线。在这个模拟中使用了简单的吉尔伯特模型[6]。从结果中可以看出，5名矿工一起工作（p设置为0.1，q设置为0.5）几乎没有停机时间。

图3. 多矿工的可用性

在本文中，新协议是提高区块链性能的提议。主要做法是将链式数据结构改为GraphChain，使用新的挖掘机制来实现并行挖掘。

从实验中可以看出，矿工工作越多，可以处理的交易就越多。虽然增长不是线性增长，但在现有区块链中添加矿工可以提高性能。它类似于分布式数据库系统，当运行在超级计算机上的中央数据库无法满足数据存储和处理能力的需求时，人们就转向另一个方向，使用数千台小型PC来构建大数据系统。

还观察到，随着矿工数量的增加，所有节点下线的机会将接近于零。并行挖掘有利于构建高可用性区块链系统。

GraphChain和并行挖掘可以应用于以下几个方向：

1. 微交易。现在比特币和以太坊的价值很高，即使是很小的交易费用如果转换成法币也会很昂贵。允许多个矿工的GraphChain在支持微交易的去中心化货币系统中可能很有用，因为在GraphChain的设计中，每个区块只包含一个交易。如果有足够的矿工可用，则无需等待区块等待时间来确认交易。

2. 数据区块链。现在隐私问题是个大问题，个人数据已经成为大公司的私有资产。未来会有特定领域的区块链，例如健康数据。如果将大量数据插入到区块链中，存储它会很昂贵。GraphChain将数据单元拆分为最小的事务级别，数据跨节点链接。因此，可以通过这种数据结构进行分片数据。

3. 银行业的区块链。银行业正在寻找数字货币解决方案。由于性能和可扩展性问题，现有区块链无法满足需求。在这种情况下，新技术将彻底改变行业。传统银行系统接受企业存贷款。为了安全地获得存款，IT系统作为笔和纸的选举版本投入了巨额成本。监管政策已经制定，但仍然需要人来遵守。区块链是一项华丽的发明，因为人类不再需要监管部分。监管成本可能低得令人难以置信。 可扩展的高性能区块链将在银行业中发挥重要作用。

GraphChain和并行挖掘是对当前区块链系统的有益改进。如果正确实施，性能和容量问题将得到修复。

IX.相关工作 

Bitcoin-NG[2]：Bitcoin-NG被提议作为原始比特币 [1] 的性能改进。它引入了微块，它在链上的两个原始块之间充当更轻的块。与Bitcoin-NG相比，引入了并行挖矿以提高系统可用性。还引入了GraphChain结构，以使矿工能够协同工作，尤其是在交易不相关时。

BitShares[3]/EOS：BitShares和EOS从Proof of Stake开发了Delegated Proof-of-Stake (DPoS)。DPoS的委托方式试图减少决策者的数量以提高整个系统的效率。DPoS采用了与领导人选举类似的想法：让更少的矿工参与交易处理。它为下一代块节省了决策时间（更少的矿工竞争挖矿）。 GraphChain是纯基于PoW的，GraphChain没有使用PoS或DPoS共识。

IoTA/DagCoin[4]：IoTA和更早的DagCoin引入了DAG数据结构，这被认为是未来区块链的发展方向。有向无环图（DAG）的思想被许多以下系统借用。最著名和最成功的例子之一是IoTA。在2018年1st IEEE International Conference on Hot Information-Centric Networking (HotICN 2018) IoTA的设计中，没有矿工。任何需要后续交易确认的交易。与IoTA/DagCoin相比，Current更像是一个比特币系统，保持原有的PoW共识和挖矿作为必要的部分。虽然GraphChain借鉴了DAG的思想，但GraphChain并不是 DAG。

致谢 

作者感谢Brahma OS和团队顾问对性能相关区块链解决方案信息收集的帮助。

这项工作得到了国家自然科学基金第61701418号资助，部分由江苏省国家自然科学基金BK20150376资助，部分由苏州市科技发展计划资助SYG201516，部分由创新项目资助 NGII20170301 下的下一代互联网技术，部分由SIP&XJTLU技术转移项目KSF-T-03，部分由Grant RDF140243和Grant RDF150246下的西浦研究发展基金项目。

参考文献

[1] Nakamoto, S. (2008). Bitcoin: A peer-to-peer electronic cash system.

[2] Eyal, I., Gencer, A. E., Sirer, E. G., & Van Renesse, R. (2016, March). Bitcoin-NG: A Scalable Blockchain Protocol. In NSDI (pp. 45-59).

[3] Schuh, F., & Larimer, D. (2015). BitShares 2.0: Financial Smart Contract Platform.

[4] Lerner, S. D. (2015). DagCoin: a cryptocurrency without blocks.

[5] Tschorsch, F., & Scheuermann, B. (2016). Bitcoin and beyond: A technical survey on decentralized digital currencies. IEEE Communications Surveys & Tutorials, 18(3), 2084-2123.

[6] Yajnik, M., Moon, S., Kurose, J., & Towsley, D. (1999, March). Measurement and modelling of the temporal dependence in packet loss. In INFOCOM’99. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE (Vol. 1, pp. 345-352). IEEE.

[7] Buterin, V. (2013). Ethereum white paper. GitHub repository

原文链接：https://ieeexplore.ieee.org/document/8606020

---煤油灯科技victorlamp.com翻译整理---