干货 | Flashbots：关于加速EVM的几种方法

2024.06.09 Skypiea

    原文作者：Flashbots团队Xinyuan Sun
    感谢 Alejo Salles、Hongbo Zhang、Alex Obadia 和 Kushal Babel 对本文的反馈和审阅。
    原标题：《关于加速EVM的几种方法，实现更好的可扩展性和更高效的MEV提取》
    借助性能更高的以太坊虚拟机 (EVM)，我们可以实现更好的网络可扩展性和更高效的最大可提取价值 (MEV) 提取。本系列文章分析了几种加速 EVM 的方法，重点是并行化和共享数据冲突分析。
    出于多种原因，以太坊虚拟机 (EVM) 的性能至关重要。首先，如果我们有更快的虚拟机，那么以太坊客户端将能够更快地处理和验证交易，从而让每个人都更容易运行一个完整的节点，并加强网络的去中心化和安全性。第二，作为以太坊上的 MEV 提取变得更加突出，我们需要使 MEV 提取更容易，以便从中获得的利润可以更均匀地分配，以防止网络经济集中化。性能更高的 EVM 通过帮助搜索者（以及当以太坊引入提议者-构建者分离时的区块构建者）产生更有利可图的完整区块和中继以具有更好的延迟来实现这一点。这意味着建设者市场将变得更有效率，从而吸引更多的搜索者并使市场更具竞争力，这反过来又使人们更难以进行危及网络稳定性的重组。
    为了通过向后兼容性和对共识规则或存储实现方式的最小更改来提高 EVM 性能，我们需要并行性。在本系列的第 1 部分中，我们认为需要并行 EVM，并介绍实现它的一般方法，例如 EIP 648、EIP 2930 和推测执行。在第 2 部分中，我们研究了静态分析和形式化方法如何使 EVM 可并行化，具体来说，我们提出了两种实现并行化的简单算法。

    背景
    去中心化对区块链安全至关重要：去中心化网络的参与者很难串通。理想情况下，这是通过尽可能多的单独方运行节点来验证正在进行的交易来实现的。然而，拥有个人电脑的普通用户通常需要 3 天以上的时间才能在以太坊上启动一个完整的节点（重新计算和验证那里的 1300 万个区块需要几天的时间）。这种低效率的背后是以太坊的大存储容量，更具体地说是 EVM 的存储设计：

对于节点性能，EVM 存储维护（对以太坊状态 Merkle trie 的操作）是一大瓶颈，目前占用了超过 70% 的事务处理时间。而对于另外 20%+ 的实际 EVM 指令解释时间，最耗时的操作码是 SLOAD，因为在涉及 IO 访问的大型数据库中，Merkle trie 节点的随机访问（因此无法有效缓存）。

    那么，要在不影响去中心化的情况下扩展以太坊（即不需要节点像强大的机器那样拥有大量的前期成本），我们能做些什么呢？
    提出了几个方向：

无状态，它在以太坊节点中引入了角色分离，一些节点是“存储节点”，而另一些是“验证节点”。验证者节点将仅在验证块时接收部分存储。通过传输其合法性证明来确保存储的正确性。但这会产生额外的网络 IO 开销。解决方案是为以太坊存储使用新的数据结构，例如 Verkle 树来压缩存储验证证明。
RainBlock，也是一个分离节点功能的提议。除了存储节点和验证节点之外，它还引入了一个特殊的 IO-helper 节点。这个提议遇到了同样的问题，即产生额外的网络 IO 开销，它使用他们称为 DSM-tree 的自定义数据结构解决了这个问题。
分片类似于节点功能的垂直分离，将计算卸载到不同的网段。

    这些提议虽然很有希望，但都涉及对基础客户端或共识规则的重大改变。
    作为正交方向，我们现在可以做的是使 EVM 并行（即同时执行没有存储访问冲突的事务，甚至可能使用可选访问列表预加载一些存储访问）。这有助于直接增加 EVM 的吞吐量，因此我们可以提高 gas 限制并在一个块中包含更多交易，从而提高每秒交易量 (tps)。此外，这还可以横向帮助现有的可扩展性提议，如分片。
    高效的 MEV 提取
    下图（取自 Babel 等人的 Clockwork Finance 论文）显示了可用于 MEV 提取的具有多个相关 AMM 交易的区块数量。作者仅在 2021 年 5 月之前从三个 DeFi 协议（MakerDAO、Uniswap、SushiSwap）中对确定性单块 MEV 机会进行抽样，但结果令人震惊。

    今天，MEV 机会要复杂得多，典型的验证者（矿工）在每个区块中看到超过 10 个 MEV 发射交易。
    由于区块构建和捆绑利润优化是一个 NP 完全问题，而且我们有太多的 MEV 捆绑要考虑，因此蛮力是不现实的，区块构建者很难有效地生产最优的完整区块（或者，在引入之前）提议者建造者分离，巨型捆绑）。
    对 EVM 并行化的研究可以帮助解决这个日益具有挑战性的捆绑合并问题。本质上，并行化算法设计的双重问题是理解冲突是如何在搜索包中发生的：它们都需要知道事务的共享数据访问信息。此外，并行 EVM 可以帮助完整的区块构建者（和 MEV 搜索者）进行更多的模拟，从而产生更有利可图的捆绑包（正如我们之前提到的，生产最有利可图的区块是 NPC 问题，因此是提高竞争力和推动提取的重要途径限制是做更多的状态空间搜索，即模拟）。
    并行化问题的细分
    并行化 EVM 可能并不像看起来那么简单。像投机并发这样的幼稚解决方案（乐观地并行执行事务，然后检查是否存在冲突，如果存在，则诉诸顺序执行）已经表明，随着以太坊变得越来越拥挤（内存池中的事务越来越多），乐观执行的冲突率也会增加。仅就 2017 年的交易而言，冲突率已经高达 35%。
    高冲突率表明我们需要设计更精细的并行化算法，这将需要更精确的存储访问信息。接下来，我们正式确定这些任务的范围。
    设当前区块号为 k，以太坊区块链的状态为 s/k，顺序 EVM 的状态转换函数为δ(tˉ,s)，它返回一个新的 EVM 状态给定的交易ˉt和状态 s的列表。假设在列表ˉt中有 n 个事务，从 txn_1到txn_n，顺序为

    意味着我们只有在完成txni执行后才开始执行txnj?。
    我们的目标是设计一个并行的 EVM 执行状态转换函数δp，例如δ(tˉ,sk?1?)=δp?(tˉ,sk?1?)。请注意，δ总是按照它们传入的顺序执行tˉ。而在δp?中，tˉ的执行没有按顺序。例如，在两个不同 CPU 内核上运行的两个事务可以同时完成执行，或者txnj?的执行将在我们开始执行txni?之前完成。
    为了让我们获得一个好处，我们有两个作业要做：

1. 为每个事务获取有关可能的共享数据冲突的信息（这是捆绑冲突分析可能提供信息的地方）。

    这意味着如果我们只在事务级别进行并行化，共享数据冲突将只是 EVM 存储，因为来自一个事务的信息可以溢出到另一个事务的唯一方式是通过存储。如果我们在更深层次上并行化，比如 EVM 操作码，那么我们得到的信息也将包括 EVM 堆栈和内存。
    形式上，这意味着对于每个txni，我们都有一些关于其共享数据访问κ(txni?)的信息。此信息可以是任何东西，例如，κ(txni?)可以在交易调用的合约代码中返回一组存储位置文字。假设完美信息函数是k_perfect，那么我们推导出的 κ 是对Kperfect的估计。

2. 基于信息的准确性，我们设计了我们的算法δp?(tˉ,sk?1?,κ)，它现在将 k 作为附加参数。

    我们并行化的确切策略和抽象级别取决于k的精炼程度以及我们容忍冲突的程度（类似于分片的工作方式）。例如，有了关于每个事务的调用数据、堆栈、内存和存储的完美信息Kperfect?，我们可以设计一个在操作码级别并行化而没有冲突的δp?。
    为简单起见，我们在这篇文章中只考虑事务级并行性。也就是说，我们假设 κ 仅包含有关存储访问的信息。我们将更精细的并行化模型留给以后的帖子。
    我们意识到这种形式化不同于通常用于实现并行 EVM（在同一个存储数据库上实例化具有读/写锁定多个 VM 实例）所采用的形式。我们选择这种形式化的原因是，通过分离 κ，我们可以轻松地将算法重新用于优化操作批处理和缓存等优化。
    存储访问信息（第一个作业）
    要检索有关存储访问的信息，可以直接从手动输入中获取。例如，更改交易的传递方式并要求开发人员/用户列出他们将使用的地址的高估，或者像 Solana 或其他基于 UTXO 的链一样，让每笔交易都包含与之交互的帐户签名列表 . 这似乎是一个简单的解决方案，因为我们不会为 κ 的生成产生运行时开销（因为它像 oracle 一样提供）并且始终可以确保其稳健性（如果不是，则通过还原事务）。但是这些方法至少需要更改客户端或在客户端之前实现一个附加层。此外，它们极大地改变了用户/开发人员的习惯，因此可能难以实施。
    或者，来自 Optimism 的 Ben Jones 在一次演讲中提议，我们将工作外包给 flashbots 搜索者，因为他们需要在想出一个有利可图的捆绑包时以任何方式模拟交易。这种方法通过提供 k =K_perfect 来实现最佳精度，但它依赖于搜索者诚实地传递附加信息及其捆绑包，并且仅涵盖使用 mev-geth 的客户端。更重要的是，如果不设计一些额外的激励系统，就很难在像 flashbots 这样的无权限系统中执行。
    另一个想法是在运行时之前使用推测生成的存储信息并将其缓存（有点像大多数 web3 库中估计气体的工作方式）。因为这种方法是推测性的，所以收集到的存储信息是不健全的，在这种情况下，我们会退回到正常的存储访问。如果我们在 Rainblock 中进行节点功能分离（因为它将工作卸载到其他 VM 实例），则此建议效果最佳。但如前所述，假定不存在。
    另一个有趣的想法是形式化方法辅助字节码分析以实现高性能并行化，我们将在下一篇文章中介绍。其中一个例子是 Forerunner，它与 raw geth 相比实现了 8 倍的性能提升，也是基于推测执行的思想，并且与我们在第二篇文章中的方法最相似，因为它们也使用形式方法技术来帮助生成的 κ。
    并行化算法（第二个工作）
    在这个阶段，我们应该已经使用我们选择的任何方法获得了必要的共享数据访问信息 κ。现在，出于演示目的，我们使用 κ 的特定示例。假设我们有两个事务txn_i <txn_j?都访问存储位置 σ，我们将它们的访问信息记录为元组 {(r, w), (r, w)} 的元组。第一个元组 (r, w) 表示 txn_i的读/写操作，第二个元组表示txn_j的元组。例如，写入 {(r), (r, w)} 表示txn_i?读取但未写入 σ，而 txn_j 既读取又写入 σ。
    使用这种形式化，我们可以想到四种简单的情况：
    {(r), (r)}:txn_i 和 txn_j 是可并行的，假设 \sigmaσ 只是这两个事务的“读取”集中的一个。
    {(r), (w)}：txn_i 和 txn_j 必须按照 tˉ 的顺序依次执行。
    {(w), (r)}：txn_i 和 txn_j 必须按照 tˉ 的顺序依次执行。
    {(w), (w)}：如果对 s' 的写操作是可交换的（例如，无符号整数的加法是可交换的），那么 txn_i 和 txn_j 是可并行的，否则它们必须按照 tˉ 的顺序执行。
    但是，txn_i 和 txn_j 不仅访问σ，还访问更多位置，因此我们扩展了我们的四个简单规则，包括每个事务的读取集和写入集，并且在搜索要执行的可并行事务时，我们循环遍历每个事务的存储访问信息 \kappaκ 并应用上述规则。
    或者，我们可以使用 Vitalik 在 EIP 648 中描述的简单算法：每个事务都包含它访问的地址的集合β，如果两个事务 txn_i 和 txn_j 满足 β_i ∩β_j =?，则并行执行它们，否则不。
    最终，这一切都取决于我们的 κ 有多精细，以及我们希望并行执行有多精细。例如，它可能不仅仅是二次的，这意味着我们的 κ 不仅包含存储访问信息，还包含内存/调用数据上的信息，因为我们也在单个事务中进行并行化。
    当然，在这四种情况下，有很多复杂性。例如：{(w), (w)}。在这种情况下，我们可能让 txn_i 先读取 s' 然后更改它，但分配给 s' 的值始终等于 txn_j 的分配值，因为智能合约是如何编写的。所以这有效地减少到 {(r), (r)} 的情况。或者这很容易反其道而行之，简化为 {(w), (r)}, {(w), (w)} 或 {(r), (w)}。即便如此，也可能是编写器以某种方式不会更改存储的值，或者读取器不会影响 EVM 中的状态更改（例如，在最初为 1 时将某个值读取为 2，但它的唯一用途是存储读数只是需要检查变量是否为正）。
    这些例子的重点只是说有很多特定类别的情况我们的并行化算法不能以最佳方式工作。所以这意味着根据 κ 的确切结构，我们有很多长尾优化设计截然不同的并行化算法以获得最佳性能。我们将在下一篇文章中回到精确的优化。
    结论
    EVM 并行化促进了以太坊的吞吐量增加，而不会影响去中心化或需要对协议进行重大更改。并行 EVM 研究的采用和开放共享还有助于通过允许更多个人使用更好的捆绑合并和生产来最大限度地减少 MEV 的经济中心化。
    在这篇文章中，我们探索了以太坊可扩展性解决方案的前景，并讨论了为什么当前的并行化技巧不能顺利运行。我们还通过将并行化问题分为两部分来展示我们对并行化问题的形式化：生成共享数据访问信息和设计利用该信息的并行化算法。