编辑推荐:
摘要在智能合约生态中,每个交易都包含待执行的代码,所有执行该交易块的节点必须达成相同的最终状态。因此,在以下场景中,需要在确保所有节点都能达到由一组交易的执行所产生的一致最终状态的同时,最大化节点内交易的并行执行:执行时间成为瓶颈时(例如在更重的工作负载、更大的区块或未来的扩
摘要
在智能合约生态中,每个交易都包含待执行的代码,所有执行该交易块的节点必须达成相同的最终状态。因此,在以下场景中,需要在确保所有节点都能达到由一组交易的执行所产生的一致最终状态的同时,最大化节点内交易的并行执行:执行时间成为瓶颈时(例如在更重的工作负载、更大的区块或未来的扩展设计中)。
传统的软件事务内存已被识别为区块内交易并行执行的一种可能抽象。然而,在智能合约场景中,执行顺序必须遵循区块中交易的预设顺序。本文对该模型(即内存事务或区块事务内存)进行了复杂度研究,并探讨了可能存在的根本界限。为此,我们形式化了区块事务内存模型并确定了所需的安全属性。随后,我们提出了满足预设可串行性的单版本和多版本区块事务实现的算法设计。最后,我们展示了区块事务内存模型的一些根本局限性,这确立了并行度的上限。
引言
区块链系统中的虚拟机(VM)是一个确定性的交易执行环境,用于运行智能合约,例如以太坊上的EVM [2]或Aptos上的MoveVM [3]。为了更高的执行吞吐量,智能合约生态系统依赖于一个由用户指定的交易块的并行执行,每个交易对VM状态执行一系列读取和写入操作 [4], [5], [6], [7], [8], [9]。一个区块提议者节点接收包含n个交易的区块以及一个预设的全序 T1?→?T2Tn作为输入。该节点尝试并行执行这些交易(n),使得并行执行产生的状态必须与按顺序执行这些交易 T1?·?T2???Tn 产生的状态相同。
与传统共享内存类似,我们可以考虑使用粗粒度锁或细粒度锁或原子事务来并行执行用户指定的交易。虽然传统共享内存的安全性允许并行执行与某个顺序执行等价(此处等价意味着两次执行包含相同的交易,执行相同的事务操作并接收来自这些操作的相同返回值 [10], [11]),即可串行性,但智能合约交易的安全性要求并行执行必须与遵循区块中预设顺序(交易顺序)的确切顺序执行等价。
本文研究了用于用户指定的智能合约交易安全并行执行的事务内存(TM)算法的复杂度 [7]。直观地说,如果执行必须遵循预设顺序,那么似乎会显著限制并发性。例如,如果我们认为交易 T1 必须在预设顺序中先于 T2(记作 T1?→?T2),那么在缺乏对访问的VM状态集上的读写冲突的先验知识的情况下,在 T1 提交之前提交 T2 可能会导致安全违规。为说明这一点,考虑以下执行:T1 读取VM状态 X1(读取值0),然后 T2 读取VM状态 X2(读取值0),接着将新值1写入 X1,如图1所示。请注意在图1a中,如果 T2 在此执行点提交,而 T1 在 T2 提交后试图将新值1写入 X2,则产生的执行在任何扩展中都不遵循预设顺序。显然,如果交易 T1 提交,产生的执行不与任何顺序执行等价。或者,如果 T1 中止并重新执行,后续对 X2 的任何读取都将返回由 T2 写入的值1,从而再次违反预设顺序,如图1b所示。因此,图1c表明,避免此违规的唯一方式是让 T2 等待直到 T1 提交。这一观察启发了我们对区块事务内存复杂度的研究。
贡献。在本文中,我们形式化了
区块事务内存(BTM)的模型 [7](类似于传统
事务内存(TM) [14])。虽然传统TM采用
可串行性及其变体作为正确性标准,但区块TM要求串行化顺序遵循预先确定的预设顺序。由于区块链中的智能合约执行发生在VM的确定性环境中,安全性属性如不透明性 [10] 和虚拟世界一致性 [12], [13](确保即使对中止的交易也能实现一致的读取)在此场景中并非关注重点 [7], [15]。因此,我们定义了预设可串行性的正确性标准,并研究了BTM中并行度的根本限制。具体而言,我们做出以下贡献。
- •
我们提出了一种满足预设可串行性的单版本BTM实现。然后我们表明,尽管满足正确性,但单版本实现无法始终利用所有可用的并行性,这促使了多版本执行的需求。
- •
我们提出了一种多版本BTM实现,该实现在保持预设串行化顺序的同时实现了最大并行度。
- •
我们证明最长冲突链的长度为执行跨度提供了下界,因此为任何BTM实现可达到的并行加速比提供了上界(命题1)。具体而言,对于一个包含n个交易的区块,如果最长冲突链的长度为L,则执行跨度至少为L,因此任何BTM实现都无法实现超过n/L的加速比。
- •
我们证明,在自然的活动性假设和不可见读取条件下,在最坏情况下,可能需要维护多达Ω(n)个共享VM状态的版本,以在预设可串行性下实现最大并行度(定理1)。
路线图。本文其余部分组织如下。第2节简要讨论了相关的并行化技术以及区块事务内存与传统事务内存的关系。第3节定义了安全属性并刻画了区块事务内存的复杂度。第3.2节形式化了区块事务内存模型并解释了其变体之间的关系。第4节介绍了我们的算法,第5节介绍了关于并行化成本和基本下界的研究结果。我们在第6节总结了要点。
各章节摘要
详细相关工作
本节详细介绍了不同的智能合约执行模型、现有的BTM算法,以及传统事务内存模型和结果与本文所呈现内容之间的关系。
区块事务内存:模型与定义
在本节中,我们形式化地定义了区块事务内存的模型和属性。我们将其作为与传统事务内存 [11] 模型相关的形式化的扩展来呈现。在全文中,我们考虑如下场景:一个包含n个智能合约交易的区块在异步共享内存机器上并发执行。
区块-TM算法
本节介绍了算法1,用于设计单版本读-写-无关的区块事务内存实现。
区块事务内存中的并行化成本
本节分析了区块链中并行度的限制(第5.1节),建立了基本的版本化成本,并推导了对区块事务内存的下界影响(第5.2节)。
讨论
简化硬件事务。Intel共享内存架构支持硬件事务,允许对一组事务性读取和写入进行原子执行。具体而言,当前的CPU包含指令,可将一组内存访问标记为事务性的,使其能在硬件中原子地执行。硬件事务通常提供缓存行粒度的自动冲突检测,确保当事务遇到内存...
CRediT作者贡献声明
Parwat Singh Anjana:撰写——初稿、方法论、概念化。Srivatsan Ravi:撰写——初稿、方法论、概念化。
利益冲突声明
作者声明他们没有已知的可能影响本文报告工作的竞争性经济利益或个人关系。
Parwat Singh Anjana|Srivatsan Ravi