乾貨 | Flashbots：關於加速EVM的幾種方法

原文作者：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，但它的唯一用途是存儲讀數只是需要檢查變量是否為正）。

這些例子的重點只是說有很多特定類別的情況我們的并行化算法不能以最佳方式工作。所以這意味着根據 κ 的確切結構，我們有很多長尾優化設計截然不同的并行化算法以獲得最佳性能。我們將在下一篇文章中回到精確的優化。