前言
本次调研对比了类似以太坊的实现系统，分析了交易并行执行的难点和可能性。链本身基于Account模型设计，而不是采用UTXO模型。调研对象
1.国内的众多联盟链，如FISCO-BCOS，支持并行执行block内部的交易验证。2.Khipu，公链项目，以太坊协议的scala实现。3.Aptos，公链项目，Move虚拟机。交易并行执行的难点
我们先来回顾一下传统的交易执行过程：执行模块从区块中取出一个个交易，然后依次去执行。执行的过程中会修改最新的世界状态，一笔交易执行完成后进行状态累加，到达区块完成后的最新的世界状态。下一区块的的执行时又严格依赖上一个区块执行后的世界状态，所以传统的交易线性执行过程无法很好的进行并行执行优化。
目前在以太坊的并行方案中，主要存在以下几点冲突：1.账户冲突。如果两个线程同时对一个地址账号的余额或者其他属性进行处理，能否跟顺序处理的结果保持一致，也就是世界状态是否是一个确定的有限状态机。2.同一个地址Storage存储冲突。两个合约变量都对同一个全局变量进行了存储修改。3.跨合约调用冲突。本来合约Ar先部署，合约B需要等到合约A部署完成之后，去调用合约A，但是当交易并行之后，并没有这种先后顺序，这就存在着冲突。交易并行方案对比
FISCO-BCOS
概述
FISCO-BCOS2.0在处理交易的过程中运用了图结构，设计了一种基于DAG模型的并行交易执行器。PTE能充分发挥多核处理器优势，使区块中的交易能够尽可能并行执行。同时对用户提供简单友好的编程接口，使用户不必关心繁琐的并行实现细节。基准测试程序的实验结果表明，相较于传统的串行交易执行方案，理想状况下4核处理器上运行的PTE能够实现约200%~300%的性能提升，且计算方面的提升跟核数成正比，核数越多性能越高。方案细节
一个无环的有向图被称为有向无环图。在一批交易中，可以通过一定的方式识别出各个交易占用的互斥资源，再根据交易在Block中的顺序以及互斥资源的占用关系构造出一个交易依赖的DAG图。如下图所示，凡是入度为0的交易均可以并行执行。基于左图的原始交易列表的顺序进行拓扑排序后，可以得到右图的交易DAG。
Beosin：SheepFarm项目遭受攻击事件简析:金色财经报道，根据区块链安全审计公司Beosin旗下Beosin EagleEye 安全风险监控、预警与阻断平台监测显示，BNB链上的SheepFarm项目遭受漏洞攻击，Beosin分析发现由于SheepFarm合约的register函数可以多次调用，导致攻击者0x2131c67ed7b6aa01b7aa308c71991ef5baedd049多次利用register函数增大自身的gems，再利用upgradeVillage函数在消耗gems的同时累加yield属性，最后调用sellVillage方法把yield转换为money后再提款。本次攻击导致项目损失了约262个BNB，约7.2万美元。Beosin Trace追踪发现被盗金额仍在攻击者账户，将持续关注资金走向。[2022/11/16 13:10:39]
模块架构
?用户直接或间接通过SDK发起交易。?随后交易在节点间同步，拥有打包权的节点调用打包器从中取出一定量交易并将其打包成一个区块。此后，区块被发送至共识单元准备进行节点间共识。?达成共识前需要执行交易验证，此处便是PTE工作的开始。从架构图中可以看到，PTE首先按序读取区块中的交易，并输入到DAG构造器中。DAG构造器会根据每笔交易的依赖项，构造出一个包含所有交易的交易DAG，PTE随后唤醒工作线程池，使用多个线程并行执行交易DAG。汇合器负责挂起主线程，直到工作线程池中所有线程将DAG执行完毕。此时Joiner负责根据各个交易对状态的修改记录计算stateroot及receiptroot，并将执行结果返回至上层调用者。?区块验证通过后，区块上链。在交易执行完成后，若各个节点状态一致，则达成共识。区块随即写入底层存储，被永久记录于区块链上。交易DAG构造流程
1.从打包好的区块中取出区块的所有交易。2.将交易数量作为最大顶点数量初始化一个DAG实例。3.按序读出所有交易。如果一笔交易是可并行交易，则解析其冲突域，并检查是否有之前的交易与该交易冲突。若存在冲突，则在相应交易间构造依赖边。若该交易不可并行，则认为其必须在前序的所有交易都执行完后才能执行，因此在该交易与其所有前序交易间建立一条依赖边。备注：都建立依赖边之后则无法并行，只能顺序执行。
Sin City Metaverse创世土地以350万美元售罄:金色财经报道，Sin City《罪恶之城》虚拟土地销售在2小时内以350万美元售罄。刚刚售罄的四个区分别是RED LIGHT DISTRICT、CARTEL DISTRICT、CHINATOWN DISTRICT和THE STRIP DISTRICT。据悉，Sin City是由Rated R' Metaverse利用虚拟现实和区块链技术形成的虚拟房地产，共有15,000 块面积为10x10平方米的土地被仔细地划分为17个地区。下一次土地出售活动定于二月份举行。（prnewswire）[2022/1/5 8:25:33]
DAG执行流程1.主线程会首先根据硬件核数初始化一个相应大小的线程组，若获取硬件核数失败，则不创建其他线程.2.当DAG尚未执行完毕时，线程循环等待从DAG的waitPop方法以取出入度为0的就绪交易。若成功取出待执行的交易，则执行该交易，执行后将后续的依赖任务的入度减1。若有交易入度被减至0，则将该交易加入topLevel中。若失败，则表示DAG已经执行完毕，线程退出。问题与解决方法
1.对于同一个区块，如何确保所有的节点执行完成，状态一致？FISCOBCOS采用验证stateroot、transactionroot和receiptroot三元组是否相等的方式来判断状态是否达成一致。transactionroot是根据区块内的所有交易计算出的一个哈希值，只要所有共识节点处理的区块数据相同，transactionroot必定相同。由于这一点比较容易保证，因此重点在于如何保证交易执行后生成的state和receiptroot相同。众所周知，对于在不同CPU核心上并行执行的指令，指令间的执行顺序无法提前预测。并行执行的交易也存在同样的情况。在传统的交易执行方案中，每执行一笔交易，stateroot便发生一次变迁，同时将变迁后的stateroot写入交易回执中。所有交易执行完后，最终的stateroot就代表了当前区块链的状态，同时再根据所有交易回执计算出一个receiptroot。可以看出，在传统的执行方案中，stateroot扮演着一个类似全局共享变量的角色。当交易被并行且乱序执行后，传统计算stateroot的方式显然不再适用。这是因为在不同的机器上，交易的执行顺序一般不同，此时无法保证最后的stateroot的一致性。同理，receiptroot的一致性也无法得到保证。在FISCOBCOS中，先并行执行交易，将每笔交易对状态的改变历史记录下来，待所有交易执行完后，再根据这些历史记录综合计算出一个stateroot。由此就可以保证即使并行执行交易，最后共识节点仍然能够达成一致。2.如何判定两笔交易是否有依赖？若两笔交易本来无依赖关系但被判定为有，则会导致不必要的性能损失；反之，如果这两笔交易会改写同一个账户的状态却被并行执行了，则该账户最后的状态可能是不确定的。因此，依赖关系的判定是影响性能甚至能决定区块链能否正常工作的重要问题。在简单的转账交易中，我们可以根据转账的发送者和接受者的地址来判断两笔交易是否有依赖关系。以如下3笔转账交易为例：A→B，C→D，D→E。可以很容易看出，交易D→E依赖于交易C→D的结果，但是交易A→B和其他两笔交易没有联系，因此可以并行执行。这种分析在只支持简单转账的区块链中是正确的。但因为我们无法准确知道用户编写的转账合约中到底有什么操作，这种分析一旦放到图灵完备、运行智能合约的区块链中，则不够准确。可能出现的情况是：A→B的交易看似与C、D的账户状态无关，但是在用户的底层实现中，A是特殊账户，通过A账户每转出每一笔钱必须要先从C账户中扣除一定手续费。在这种场景下，3笔交易均有关联，则它们之间无法使用并行的方式执行。若还按照先前的依赖分析方法对交易进行划分，则必定会出现问题。那么我们能否做到根据用户的合约内容自动推导出交易中实际存在哪些依赖项？答案是否定的。正如静态分析中提到的，我们很难分析出合约依赖项以及执行过程。FISCOBCOS将交易依赖关系的指定工作交给更熟悉合约内容的开发者。具体来讲，交易依赖的互斥资源可以由一组字符串表示。FISCOBCOS暴露接口给到开发者，开发者以字符串形式定义交易依赖的资源，告知链上执行器，执行器则根据开发者指定的交易依赖项自动将区块中的所有交易排列为交易DAG。比如在简单转账合约中，开发者仅需指定每笔转账交易的依赖项是｛发送者地址+接收者地址｝。进一步讲，假如开发者在转账逻辑中引入了另一个第三方地址，那么依赖项就需要定义为｛发送者地址+接受者地址+第三方地址｝。这种方式实现起来较为直观简单，也比较通用，适用于所有智能合约，但也相应增加了开发者肩上的责任。开发者在指定交易依赖项时必须十分小心，如果依赖项没有写正确，后果将无法预料。并行框架合约
法国经济新闻电视台BFM Business在节目中提到DeFi应用Aave:据推特消息，法国 BFM 经济新闻电视台（BFM Business）在一期节目中邀请加密市场策略分析师 Nicolas Cheron 谈到加密金融和去中心化金融，该节目还特别提到了 DeFi 应用 Aave。BFM Business在法国是一家全国性的经济类电视台，曾开设了法国第一个经济新闻频道，旗下的广播也是全法收听人数最多的广播。[2021/1/25 13:25:15]
FISCOBCOS为了开发者能够使用并行合约这一套框架设定了一些合约编写的规范，细节如下：并行互斥两笔交易是否能被并行执行，依赖于这两笔交易是否存在互斥。互斥是指两笔交易各自操作合约存储变量的集合存在交集。例如，在转账场景中，交易是用户间的转账操作。用transfer(X,Y)表示从X用户转到Y用户的转账接口，则互斥情况如下：
?互斥参数：合约接口中，与合约存储变量的“读/写”操作相关的参数。例如转账接口为transfer(X,Y)，X和Y都是互斥参数。?互斥对象：一笔交易中，根据互斥参数提取出来的、具体的互斥内容。例如转账接口为transfer(X,Y)，一笔调用此接口的交易中，具体的参数是transfer(A,B)，则这笔操作的互斥对象是；另外一笔交易调用的参数是transfer(A,C)，则这笔操作的互斥对象是。判断同一时刻两笔交易是否能并行执行，就是判断两笔交易的互斥对象是否有交集。相互之间交集为空的交易可并行执行。FISCO-BCOS提供了两种编写并行合约的方式，一种是solidity合约，另一种是预编译合约。这里只介绍solidity合约，预编译合约同理。solidity合约并行框架编写并行的solidity合约时，在基础上只需要将ParallelContract.sol作为需要并行的合约的基类，并调用registerParallelFunction()方法，注册可以并行的接口即可。parallelContract代码如下：
以下是基于并行框架合约进行编写的转账合约：
动态 | 外媒：Singapore Dollar Coin项目虚假列出多位加密知名人物:据newslogical报道，有迹象显示Singapore Dollar Coin是项目。该项目在其官网中列出WazirX首席执行官Nischal Shetty、加密货币顾问ToneVays和Bob Ras的照片，以及一些其他加密知名人物等。但Nischal Shetty接受采访时表示，并没有参与该项目。Tone Vays也发推特称并未参与，警告加密投资者不要参与投资。[2019/12/1]
确定接口是否可并行可并行的合约接口，必须满足：?无调用外部合约。?无调用其它函数接口。确定互斥参数在编写接口前，需要先确定接口的互斥参数，接口的互斥即是对全局变量的互斥。互斥参数的确定规则为：?接口访问了全局mapping，mapping的key是互斥参数。?接口访问了全局数组，数组的下标是互斥参数。?接口访问了简单类型的全局变量，所有简单类型的全局变量共用一个互斥参数，用不同的变量名作为互斥对象。例如：合约里有多个简单类型的全局变量，不同接口访问了不同的全局变量。如需将不同接口并行，则需要在修改了全局变量的接口参数中定义一个互斥参数，调用时指明使用了哪个全局变量。在调用时，主动给互斥参数传递相应修改的全局变量的“变量名”，用以标明此笔交易的互斥对象。如：setA(intx)函数中修改了全局参数globalA，则需要将setA函数定义为set(stringaflag,intx)，在调用时，传入setA("globalA",10)，用变量名“globalA”来指明此交易的互斥对象是globalA。确定互斥参数后，根据规则确定参数类型和顺序，规则为：确定参数类型和顺序-接口参数仅限：string、address、uint256、int256。-互斥参数必须全部出现在接口参数中。-所有互斥参数排列在接口参数的最前。可以看出，FISCO-BCOS交易并行其实很大程度依赖用户编写合约的规范。如果用户编写合约不规范，系统贸然的进行了并行执行，则有可能会造成账本root不一致的问题。Khipu
概述
与FISCO-BCOS的观点不同，Khipu认为让用户在编写合约的时候识别和标明会发生静态冲突的地址范围并且不出错是不现实的。竞态是否会出现、在何处出现、在什么条件下会出现，只有当确定性获取涉及到当前状态后才可以做判断。以目前的合约编程语言而言，几乎不可能通过对代码进行静态分析来获取完全无误并且没有遗漏的结果。Khipu针对这方面做了比较全面的尝试，并且完成了工程实现。方案细节
在Khipu的实现方案中，同一个区块里面的每条交易都从前一个区块的世界状态开始，然后并行执行，在执行过程中记录下所有的理想经历路径上遇到的以上三种竞态。在并行执行阶段结束后，转入合并阶段。合并阶段开始逐条合并并行的世界状态，每合并一条交易时，先从记录下来的静态条件中判断是否已经与前面已经合并的竞态条件有冲突。如果没有，直接合并。如果有，则将这条交易以之前已经合并的世界状态为起点再执行一次。最后合并的世界状态将用区块的哈希做最后的校验。这是最后的一道防线，如果校验有误，则放弃前面的并行方案，将区块内的交易重新串行执行。并行度指标
动态 | 币安正式在新加坡推出Binance Singapore交易所:7月10日，Binance宣布与Vertex Ventures合作正式推出Binance Singapore。经过两个月的运营，Binance Singapore的用户基数每周增长约20％，并且每日交易量也在大幅增加。赵长鹏表示，新加坡政府对加密货币有深入的了解，对金融创新持开放态度，坚信新加坡将引领下一个金融业即将发生的革命。（forbes）[2019/7/10]
Khipu在这里引入了一个并行度指标，即一个区块内能够不需要再次执行就可以直接合并结果的交易比例。Khipu通过对以太坊从创世区块到最新的区块进行几天的重放观测发现，这个比例平均可以达到80%。总体而言，如果计算任务可以被完全并行化，单链的可扩展性就会是无限的，因为总是可以往一个节点里添加更多的CPU核心数量。若事实并非如此，则最大的理论速率就受限于安达尔定理：你能给系统进行提速的极限取决于那些不能进行并行化的部分的倒数。也就是说，如果你可以进行99%的并行化，那么你就可以提速到100倍。但如果你只能实现95%的并行化，那么你就只能提速到20倍。冲突标记在以太坊所有的交易重放下来看，大概有80%的交易是可以并行化的，有20%不能并行化，所以Khipu对以太坊提速的平均效率是5倍左右。通过对evm代码指令的解读可以发现，冲突的地方是一些有限的指令对于stroage产生了读写过程，因此可以通过记录这些读写的地方形成一个读写集合。仅仅利用静态的代码分析无法确保这些过程都被记录，所以需要在处理每个区块里面的交易时对每一笔交易并行的预执行一次。通过预执行过程，可以得知这些交易是否是对同一个account或者storage进行读写，然后对每笔交易产生一个readSet和writeSet。简言之，预执行的过程就是首先将世界状态拷贝多份作为所有交易的初始状态。假设区块链里面存在100个交易，那么这100多交易就可以通过线程池并行执行。每个合约都有同样的初始世界状态，执行过程中会也会产生100个readSet和writeSet，同时也会各自产生100个新的状态。预执行结束后，开始下一个阶段的处理。理想状态下，如果这100个readSet和writeSet没有冲突，那么就可以直接进行合并，产生这个区块里面所有交易执行完毕的最终世界状态。但是交易往往不会如此理想化，所以正确的处理方式为：先取第一个交易执行后的状态里面的readSet、writeSet，和第二个合约执行后的readSet、writeSet进行对比，看他们是否有对同一个账户或者storage进行读写。如果有，那就意味这两笔交易存在冲突，则以第一个交易执行完成的状态作为第二个交易的起始状态，将交易二重新执行一遍。以此类推，随着不断进行合并状态机，冲突集也会不断地累加。只要后面的交易与前面的交易存在冲突就顺序执行，直到执行完所有的交易。通过对以太坊主网的交易重放可以发现，凡是冲突多的地方，大部分是交易所在同一个区块进行的有互相关联的交易，这也是与该过程相符合的。
处理流程图
具体并行执行过程
Aptos
概述
Aptos在Diem的Move语言和MoveVM的基础上创建了一个高吞吐量的链，实现了并行执行。Aptos的方法是检测关联关系，同时对用户/开发者透明。也就是说，不要求交易明确声明它们使用哪一部分状态。方案细节
Aptos使用名为Block-STM的软件交易内存(SoftwaretransactionMemory)的修改版本，基于Block-STM论文实现了并行执行引擎。Block-STM使用MVCC来避免写-写冲突。所有到相同位置的写入都与它们的版本一起存储，这些版本包含它们的tx-id和写入tx被重新执行的次数。当交易tx读取某一个内存位置的值时，它从MVCC中获得在tx之前出现的写入该位置的值，以及关联的版本,从而判断是否有读写冲突。在Block-STM中，交易在区块内是预先排序的，并在执行期间在处理器线程之间划分以并行执行。在并行执行中，假设没有依赖关系执行交易，被交易修改的内存位置被记录下来。执行后，验证所有交易结果。在验证期间，如果发现一个交易访问了由先前交易修改的内存位置，则该交易无效。刷新交易的结果，重新执行交易。重复该过程，直到区块中的所有交易都被执行。当使用多个处理器内核时，Block-STM会加快执行速度。加速取决于交易之间的相互依赖程度。可以看到，Aptos采用的方案和前文提到的Khipu大致类似，但是实现细节略有不同。主要区别如下：?Khipu对区块内交易采用并行执行，顺序验证的方式，而Aptos对区块内的交易采用并行执行，并行验证的方式。这两种方案各有优缺点。Khipu的方案易实现，效率略低。Aptos的Block-STM实现采用了诸多线程中的同步与信号操作，难以进行代码实现，但效率较高。?由于Move原生支持全局资源寻址，所以在利于并行执行的情况下，Aptos会对交易进行重新排序，甚至是跨区块进行排序。官方宣称这个方案既可以提高并行的效率，也可以解决MEV问题，但是这样是否会影响用户体验则有待考虑。?Aptos在执行过程中会将执行得到的写集存储在内存中以获得最大的执行速度，并将其用作要执行的下一个块的缓存，任何重复的写入操作都只需要写入稳定的存储器一次。基准测试
Aptos针对Block-STM进行集成后做了相应的benchmark，将10k交易一个区块在顺序执行情况下与并行执行情况下的表现进行了对比，结果如下：
从上图可以看到，BlockSTM在32个线程并行执行的情况下比使用程的顺序执行实现了16倍的加速，而在高争用情况下，Block-STM实现了超过8倍的加速。总结
综上所述，一些方案需要用户在编写合约时按照既定的规则写存储，这样才能够被静态和动态分析发现依赖关系。Solana和Sui采用了类似的方案，只是用户感知度不同。这类方案本质上都是对于存储模型的更改以获得更好地分析结果。Khipu和Aptos的方案属于用户无感知的。即用户无需谨慎编写合约，虚拟机会在执行前进行动态分析依赖关系，从而将没有依赖关系的并行执行。这类方案实现难度较大，而且并行度在一定程度上取决于交易的账户分部情况。当交易冲突较多的时候，不断地重新执行反而会导致性能严重下降。Aptos在论文中提到后续可能也会对用户编写合约进行一些优化，从而更好地分析依赖关系，达到更快的执行速度。单纯的修改交易串行到并行模式在公链环境下可以带来3~16倍的吞吐量提升。如果能够结合大区块和大的gasLimit等优化，L2吞吐量可以提升百倍左右。考虑到工程实现和效率问题，OlaVM大概率会采用Khipu+定制化存储模型方案。在获得性能提升的同时，避免引入Block-STM带来的复杂性，也便于后期更好的进行工程优化。参考：
1.Block-STM论文：Block-STM:ScalingBlockchainExecutionbyTurningOrderingCursetoaPerformanceBlessing(arxiv.org)2.FISCO-BCOSGithub,FISCO-BCOS3.KhipuGithub,GitHub-khipu-io/khipu:AnenterpriseblockchainplatformbasedonEthereum4.AptosGithub,GitHub-aptos-labs/aptos-core:Aptosisalayer1blockchainbuilttosupportthewidespreaduseofofblockchainthroughbettertechnologyanduserexperience.关于我们
Sin7y成立于2021年，由顶尖的区块链开发者组成。我们既是项目孵化器也是区块链技术研究团队，探索EVM、Layer2、跨链、隐私计算、自主支付解决方案等最重要和最前沿的技术。团队于2022年7月推出OlaVM白皮书，致力于打造首个快速、可扩展且兼容EVM的ZKVM。微信公众号：Sin7y官网：https://sin7y.org/白皮书：https://olavm.org/社群：http://t.me/sin7y_labs官推：@Sin7y_Labs邮箱：contact@sin7y.orgGithub：Sin7y研究文章：https://hackmd.io/@sin7y
郑重声明： 本文版权归原作者所有， 转载文章仅为传播更多信息之目的， 如作者信息标记有误， 请第一时间联系我们修改或删除， 多谢。