Forerunner: Ethereum transaction speedup

Published in

SWF Lab

13 min readNov 14, 2022

在共識階段推測多未來並預先執行，基於限制的實際執行加速技術。
整理自由多名微軟研究員刊登於操作系統原理研討會 SOSP 2021 的《Forerunner: Constraint-based Speculative Transaction Execution for Ethereum》論文。

Published on November 15, 2022 by Chen YanLong.

*Special thanks to ChiHaoLu for reviewing.

Intro.
Background
Architecture
Design
Implementation results
Conclusion
Ref.

Intro

Forerunner 可以做為一個節點的擴充功能運行，在接收各個地方傳出的交易請求後，在共識階段與執行階段中的空檔預測各種可能的未來（簡稱多未來，multi-future），並預先執行、記憶各種未來的結果，形成一個如迴路般的路徑，用以加速在狀態確定後的執行速度。

不像傳統的預測執行預測單一個未來，Forerunner 預測多種可能的未來，並將 EVM 指令在本地轉換成團隊自行研發的簡化版指令-「S-EVM 指令」方便執行。有 Forerunner 運行的節點的執行結果可以達到原先執行速度的 6.06 倍。

名詞解釋：

預測執行（speculative execution）：是一種最佳化技術，電腦系統會根據現有資訊，提前執行一些將來可能用得上也可能用不上的指令。
S-EVM：由團隊自行研發的 register- based 類 EVM 虛擬機。

Background

以太坊裝有準圖靈完備（quasi-Turing complete）的虛擬機 EVM（Ethereum virtual machine），使用者可以藉由編寫智能合約（smart contract, 其實就是 code）進行交易，經由 EVM 執行後更改整個以太坊的狀態（state）。

以太坊的共識機制在每一區塊的打包中分為兩個階段。一是共識階段，驗證節點接收從各個地方傳出的交易請求並各自打包。在舊的 PoW 共識下由最快達成雜湊後條件的節點得到打包權，新的 PoS 則由系統決定。二是執行階段，獲得打包權的節點會將交易執行，並將新的世界狀態廣播給所有其他節點。

在這樣的機制（文中稱為 Dissemination-Consensus-Execution (DiCE)）底下，交易訊息「被知道的時間」與「被執行的時間」之間的落差，可以被用來預測執行（speculative execution）交易內容，加速以太坊的交易速度。

因為每個節點所打包的區塊可能因為延遲、或是 gas fee 的不同而有所不同，各個交易在不同節點可能有不同的順序，而又沒有任何人可以知道哪一個節點會被「選」中，造就以太坊在共識階段有著多未來的狀態，沒有人可以預先知道下一個世界狀態為何。

在每個循環（共識階段 + 執行階段）當中，有就是每個區塊被打包的時候，交易只能在有限時間的執行階段中被執行，因此執行階段能夠處理的交易量，就是整個系統的吞吐量。Forerunner 想做的事就是加快這段期間的執行速度，達成整個以太坊系統的加速。

Architecture

這裡主要先介紹整個技術的架構，下一個段落會細講每一個部分。

Forerunner 由三個主要的元件組成：
1. multi-future predictor

預測較可能被打包的交易內容
將這些交易內容整理成各種可能的 future context（FC）

2. speculator

預先執行 predictor 傳來的各種 FC
紀錄執行中寫入或讀取的資訊
使用 specialization 和 memoization 建構 constrained fast-path 確保 CD-equivilant

（1, 2 會建構出一個 Accelarated Program（AP））

3. transaction execution accelerator

在執行階段運行 AP program

Design

Example used: Price oracle

預言機是將鏈下資產的價格更新在鏈上的一種方式，這裡不探究他的動機引誘機制，單純作為方便介紹 Forerunner 流程的範例。以下是使用 solidity 撰寫的智能合約（gist 用 .js 純粹為了美觀）。

呼叫此合約的人使用第 7 行的 submit()，提交當下的 price和 roundID 。而執行此交易（稱 Tx_e）需要讀取在打包當下的 block.timestamp（line 8），合約才能判定當下是不是在同一個 round當中，進而有不同的執行（if-else）。因此，不同的打包就會有不同的執行結果。

如上圖所示，除了各個交易的順序不同之外，每個 FC 中的交易內還有可能因為該 FC 的 timestamp 不同而有所不同。

A. Synthesis of APs（Accelerated Programs）

下圖是整個 AP 產生的流程，每一個可能的 FC 都會產生單一 AP，而最後將這些 AP 合成在一起，成為最終由 Transaction execution accelarator 的 AP。

1. Program specialization with S-EVM

上述智能合約中的submit() 可以轉換成 88 個 EVM 的指令（opcode 對應到的指令），Forerunner 紀錄這些指令及其順序，並將這些指令轉換成 S-EVM （團隊自行推出的版本）指令。

EVM 與 S-EVM 的差別在於， EVM 是一個 stack-based 的虛擬機，而 S-EVM 是 register-based。每個 S-EVM 的指令只滿足 EVM 指令中「讀、寫、計算」的其中一項功能，而轉換後的指令有助於 AP 的生成。

Stack-based v.s. Register-based VMs
stack-base
運算元是以 stack 的方式儲存，運算方式會先將 stack 最上面的運算元 pop出來進行運算，再 push 回去。因此操作的指令會較為複雜，因為指令中並沒有包含儲存地址，需要將資料一個一個 pop 出來
register-based:
運算元以 CPU 暫存器的方式儲存，因此指令須包含運算元位置，在運算上較為快速。
example
在此舉一個簡單的例子: c = 20 + 7
stack-based :
pop 20
pop 7
add 20, 7, c
push c
register-based :
add R1, R2, R3 （其中 7 存在 R1, 20 存在 R2, 將結果存在 R3）
可以看到 stack-based 不紀錄位置，而是以堆疊的方式依順序拿取；而 register-based 的指令是直接指定運算元存取的位置，因此指令會較長但指令數少。

將 stack-based 的 EVM 指令轉換成 register-based 的 S-EVM 指令會經過四個步驟：

Decomposition 分解：將 EVM 的指令分解成更低階的指令。文中舉例將SHA256指令分解成 讀取資料 及 運算hash 的指令。
stack to register translation
Register promotion：分配資料於暫存器之中。
Control flow elimination: 刪除有關流程控制的指令，因為這個由第二步的 constaint generation 控制。

經過以上的流程，以 FC1 來說，會將原先的 88 個 EVM 指令結果轉換成 S-EVM 指令，最終執行結果存於 12 個暫存器位置當中。（如下圖中的左半邊長方框內所示，v 為 register, n 為 instructions）

而圖中的菱形框內（n5 及 n8）則為接下來要介紹的第二步生成的 constraint。

2. Constraint generation

為了保障 CD-equiv.，需要在 AP 的流程當中置入 “guard”。

CD-equivalent
C 和 D 分別代表 control flow 和 data flow，論文指出只要兩個不同的 FC 是 CD-equiv. 的，那麼他們所遵循的指令順序就會是相同的。也就是說不同節點打包的區塊可能可以適用於同一個指令序列。
舉例來說：
所有滿足300 < block.timetamp <= 599 && activeRoundID == roundID 的 FC 都可以分類為同一種，也都遵循同樣的指令及順序。CD equiv. 可以將所有可能的未來分類，只要在該分類中有任一個 FC 被拿來做跟蹤，那跟蹤後產生的 AP 就可以預測到所有在該分類中的 FC。

上圖中的 n5 及 n8 即為 control flow 的 guard。舉 n5 來說，就是控制下面這段程式碼的流程，檢查存在 v4 （也就是 EQ ( v3, roundID )）暫存器中的資料是否為 true ，若是，則准許流程繼續往下走。若否則會停止整個 program ，如同程式碼所指示的 revert。

if (roundID != curRoundID) {revert();}

3. Dead code elimination

所有不影響 guard 判定的指令（也就是不會被 IF-ELSE 使用的 variable 賦值）都會被移除。

4. Rollback-free execution

在第三點被移除的指令會被丟到所有 guard 都被執行完之後，也就是 fast path 的部分，因其不會影響 guard 的判定，將他們移到後面再執行可以減少不會通過 guard 之 FC 操做多餘的指令。

5. Memoization

藉由預先執行並記憶化結果，當程式判定一個 FC 在某一個指令的結果和預測時跑過的結果一樣，則可以直接跳過許多已算過的指令，直接讀取已經計算好的結果，這部分稱為 shortcuts ( AP 圖中 m 的部分).

6. AP merging

經過以上五個步驟，單個 FC 可以產出如上圖這樣一個 AP，將每一個 AP 合成在一起，即成為最中實際運行的 merged-AP。

Forerunner 的技術可以做到讓執行 N 個 AP 合成起來的時間複雜度跟 N 無關，也就是可以以處理單個未來的效率處理 N 個未來。

從上圖可以看到經過 AP 的製作過程，程式碼大約減到了原本的 8.95% 。

B. Predictor

Predictor 會從以太坊所有待打包的交易池中挑出較可能被打包的交易，並建構可能的未來（FC）。這些建構好的 FC 才會被丟到由以上所組成的 Speculator 製造 AP。

Predictor 會優先納入以下兩種交易：

gas fee 較高者
礦工自行提出的交易

C. Prefetcher

先到以太坊鏈上存取可能使用到的 read-set 方便 AP 運行時更快速的找到需要使用的值。

Implementation results

團隊使用 Geth 將 Forerunner 架設為一個運行節點，進行為期十天的測試，同時將整個過程（live traffic）記錄下來方便以相同的環境測試不同版本的 Forerunner，在這段期間之中發生了 1300 萬筆交易。而因為在真實的 Ethereum 上運行， Forerunner 必需在實際交易的有限時間之內完成。

Forerunner 可以有效運作的條件是交易訊息廣播與交易被執行之間的時間差，下圖表為時間差的反向 CDF （Cumulative distribution function, 累積分配函數）圖，說明有超過 90% 交易的時間差超過四秒 => Forerunner 是有機會有效的。