本文是一篇计算机论文，本文系统分析了当前区块链事务处理存在的问题，创新性地提出了结合链上链下的“执行-排序-重执行与验证”区块链事务处理框架EOR。针对系统可扩展性低问题，EOR将事务执行和数据存储转移至链下，链上节点作为轻量级节点参与排序与验证，较好降低了链上节点“参与成本”。
1 绪论
1.1 研究背景及意义
近年来，由于比特币[1]、以太坊[2]等加密货币以及去中心化概念的兴起，区块链(Blockchain)技术在工业界与学术界得到了广泛关注，并产生了巨大影响。区块链是一种新型分布式数据存储和处理技术，它支持在无信任环境下安全处理去信任中心交易，同时具有数据防伪造、不可篡改、历史数据可追溯以及能方便实现智能合约等特点，被称为一种将引发社会变革的新型技术。目前，区块链技术已经被应用到多个领域，例如资产管理[3]、专利保护[4]、医疗健康[5]、政府监管[6]、物联网[7]等。
作为一种新型分布式数据处理系统，区块链具有如下独特特征[8]。
多方参与、去中心化。传统数据库无论物理集中或物理分散，在逻辑上始终是一个整体，由一个中心化单方控制[9]。而区块链系统由多方参与并管理，是一个完全去中心化系统。最初比特币区块链设计的初衷是让任意参与方能随时通过互联网加入区块链网络，系统由所有身份地位相同的参与方共同维护，其存储的数据始终保持透明性。
智能合约。比特币区块链与数字货币耦合，它主要用来处理公钥地址间货币的相互转移(类似传统银行数据库的转账业务)[1]。随着以太坊兴起，之后的区块链系统开始支持处理智能合约(Smart Contracts)[10]，这为区块链应用提供了无限多的可能。智能合约是一种特殊账户，内部存储着代码和数据，用户通过调用账户地址来执行代码并更新对应数据。支持智能合约的区块链系统必须能够同时处理普通转账事务和智能合约事务。
不可篡改和可追溯性。区块链将事务和数据存储在不同的区块，区块间使用哈希指针连接。该结构不仅支持快速溯源被永久保存的历史数据，还使得节点在分布式网络上能以尽量小的通信代价和共识成本来保持数据的一致性。不同于传统的以事务为最小单位的处理机制，这种设计让每个区块内包含了多个事务，事务以块为单位在网络上执行、广播及验证，每个参与节点以块为单位对事务进行批处理。
1.2 研究现状
1.2.1 区块链基础知识
(1) 区块链概念
区块链是一种去中心化的分布式数据管理系统，由网络中的多个节点通过共识算法共同维护一组相同的数据，而无需中心化的服务器参与。这组数据被设计为一条通过哈希指针相连，无法修改而只能在尾部增加数据的链表式结构，该链表中最小的逻辑单元是区块，每个区块包含一批事务。客户端通过发起事务来修改区块链上存储的数据，在支持智能合约的区块链上，事务一般分为转账事务和智能合约事务，前者类似传统数据库中的转账交易，后者则是通过调用并执行部署在区块链上的智能合约来更新相应的数据。
目前流行的区块链被分为公有链(Permissionless Chain)[1-2]和联盟链(Permissioned Chain)[25]，公有链是完全公开的系统，对参与系统节点身份不做任何限制，任意节点均可随时加入或退出系统。而联盟链由一组身份已知，数量确定的节点组成，但节点并不相互信任，其节点的加入有一定限制条件。两类链的最主要区别在于其系统安全性的假设不同，由于后者存在准入限制，后者假设比前者具有更高安全性[26]，这导致两类系统所采用的事务处理机制也迥异。
(2) 区块链共识算法
在分布式环境中会存在多个节点，每个节点在本地维护自己的数据，多个节点可能会保存一部分相同的数据，如果节点之间没有对这些相同数据达成一致，那么不同的节点对外提供的数据就不同，这样的分布式系统不能正常工作。故分布式系统需要共识算法来确保节点数据的一致性。
区块链是一个典型的完全去中心化的分布式系统，各节点上需要通过共识算法来保证区块数据一致性。由于区块链处于拜占庭环境(不可信环境)，即节点除了崩溃故障外，还可能具有潜在的恶意行为，如篡改事务数据或故意发送错误消息等，区块链必须采用拜占庭容错共识[27]，这类共识包括传统的BFT(Byzantine Fault Tolerance)类共识协议[13]，基于工作量的PoW共识以及基于权益的PoS(Proof of Stake)，DPoS(Delegated Proof of Stake)[14]等共识策略。
2 EOR事务处理框架
2.1 EOR框架设计目标
EOR框架旨在实现如下目标。
减少链上节点存储和执行压力，提高系统的可扩展性。如上所述，EOR将数据的存储与部分事务的执行转移至链下第三方服务商，通过降低节点的存储和执行成本以实现系统的高扩展性。
设计并发控制协议加强节点执行事务的效率。在链下将事务和服务商分组以便多组同时并行执行事务，服务商节点通过支持嵌套合约的NCEP-2PL协议并发执行事务。
提高系统事务处理效率的同时，保障系统安全性。本文假设链下执行环境是不可信任的，在不额外使用其他硬件设备或密码学算法的情况下，通过NCVP-LC协议链上快速验证保证事务的执行正确性，进而维持区块链系统的安全性。
提升高冲突率下事务的处理效率。在链上排序阶段即可提前发现因为冲突而无法提交的事务，并在验证阶段对中止事务进行重执行，这样的策略避免了高冲突率下事务无法提交的问题。
2.2 EOR框架概述
2.2.1 EOR框架节点分类
为了提高系统可扩展性，EOR将系统节点分为链上和链下两部分。链下节点执行事务和存储所有数据，链上节点则为“低成本”轻量级节点，存储少量数据以执行排序算法和验证事务。事务的执行和数据的存储转移至链下第三方，使得系统的算力和存储能力较为稳定，而链上节点参与共识，则保证了区块链系统的去中心化。另外，为进一步提高事务处理效率，链下节点被划分为多组并行执行事务。
为了达到设计目标，EOR中将节点分为四类，如图2.1所示。
客户端节点(Clients)。客户端节点通过区块链网络发送事务请求来调用并执行智能合约以更新区块链数据。
第三方服务提供商(Service Providers, SP)。本文假设SP是区块链外第三方提供的一组数量和行为相对稳定，具有高存储、高计算力的服务器节点。相比链上一般节点，我们给予SP更高的信任，但并不认为它们完全诚实。为保证去中心化，它们也不参与链上共识。SP分组用于执行事务和存储区块链数据。
排序节点(Order Nodes)。排序节点对链下完成执行的事务按MLC算法排序，提前中止因为存在并发冲突而无法提交的事务。
重执行与验证节点(Re-execute&Validate Nodes, RV)。RV节点对链下执行的事务进行并发验证，重执行被排序节点中止的事务并生成区块。
3 链下事务并发执行 ........................ 15
3.1 事务分组并行策略 .................................. 15
3.2 区块链嵌套合约概述 .................................. 16
4 链上事务排序策略 ................................... 28
4.1 事务可串行化分析 ............................. 28
4.2 Lockchain合并规则 ............................... 30
5 链上事务重执行与验证 ............................ 37
5.1 RV节点事务处理流程 .................................. 37
5.2 NCVP-LC协议 ................................ 37
5 链上事务重执行与验证
5.1 RV节点事务处理流程
RV节点的工作包含两部分，一是验证SP执行事务的结果是否正确，二是重执行被排序节点中止的事务。由于本文假设SP不可信，链上RV节点必须通过Lockchain再次确定性并发执行被排序后的事务，并检查数据的执行结果与SP所提供的是否一致，如果不一致，则要中止所有事务。另外，RV重新使用NCEP-2PL协议执行那些排序失败的事务，将所有事务打包生成新区块。
RV节点在收到排序节点广播的排序结果后，具体通过如下几步完成最后的验证和重执行过程
由于SP可能表现出恶意行为，故RV节点需要再次执行所有分组中的所有事务。在提出的EOR框架中，假设了链下SP计算能力远超链上普通节点，我们希望链上验证的效率能高于链下执行的效率，这对于系统整体的事务执行效率有着极大的帮助，故本节提出了NCVP-LC协议，通过Lockchain中记录的事务及嵌套合约的并发冲突信息，在事务并发执行时定位事务读写数据的正确版本，进而确定性并发执行嵌套合约和事务。
在链下执行阶段，SP在实际执行事务之前无法通过任何方式提前获得事务可能的并发冲突，因此只能进行推测性执行。如果发生冲突，事务必须中止并回滚，这会浪费一定的资源和时间。第二阶段在锁链表的帮助下，RV节点可以完全避免任何并发冲突，使用基于锁链表的并发控制协议进行确定性执行，该协议确保RV节点和SP节点之间的事务并发调度是冲突等价的。
6 总结与展望
6.1 全文总结
自2008年中本聪提出比特币和区块链概念以来，区块链技术得到了广泛关注和发展，并已成为研究热点。以太坊智能合约出现以后，区块链的研究和应用由最初为数字货币提供底层技术支持转向了更为泛化的数据处理和存储，由此数据库领域和区块链有所交集。随着区块链在其他领域的发展，作为区块链系统底层技术之一的事务处理得到越来越多的关注。
区块链系统事务吞吐量低的缺陷阻碍了区块链技术广泛应用，而事务处理效率低下的原因在于节点对事务的执行缺少并发控制，节点间存在事务的大量冗余执行，框架上缺乏事务并行执行设计等。另一方面，区块链上数据量逐日增加，致使区块链系统的扩展成本也迅速提高。为解决这些问题，本文展开了较为深入研究，取得如下主要成果。
系统分析了当前区块链事务处理存在的问题，创新性地提出了结合链上链下的“执行-排序-重执行与验证”区块链事务处理框架EOR。针对系统可扩展性低问题，EOR将事务执行和数据存储转移至链下，链上节点作为轻量级节点参与排序与验证，较好降低了链上节点“参与成本”。为解决事务冗余执行问题并加快事务执行效率，提出了链下分组并行执行，链上合并排序策略。EOR框架让链上节点验证、重执行和提交事务并生成新区块的机制，确保了在不依靠任何密码学算法或可信任执行硬件的情况下，链下事务执行的安全性并维持了区块链去中心化特性。
为解决单个节点事务执行效率低下问题，本文创新性提出了区块链嵌套合约并发执行的概念，系统分析了嵌套合约执行的正确性准则，基于两段锁设计了支持嵌套合约的NCEP-2PL并发控制协议。该协议支持事务内部嵌套合约并发执行，在事务存在嵌套合约调用情况下，实验证明本文提出的协议可以多线程同时并发执行嵌套合约和事务，相比于其他并发控制协议，事务执行速度明显加快。
参考文献（略）