# Forerunner: ethereum transaction speedup
在共識階段推測多未來並預先執行，基於限制的實際執行加速技術。
整理自由多名微軟研究員刊登於操作系統原理研討會 SOSP 2021 的[《Forerunner: Constraint-based Speculative Transaction Execution for Ethereum》](https://dl.acm.org/doi/10.1145/3477132.3483564)論文。

Published on November XX, 2022 by Chen YanLong.

###### tags: `blockchain`
---
## Table of contents
* Intro.
* Background
* Architecture
* Design
* Implementation results
* Conclusion
* Ref.

---

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

不像一般的單未來預測執行，Forerunner採用的是多未來預測，並簡化 EVM 指令轉換成 S-EVM 指令。達成執行結果是原先執行速度的 6.06 倍。

---

# 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 accelarator
* 在執行階段運行 AP program


---

# Design

## Example used: Price oracle
預言機是將鏈下資產的價格更新在鏈上的一種方式，這裡不探究他的動機引誘機制，單純作為方便介紹 Forerunner 流程的範例。以下是使用 solidity 撰寫的智能合約。

contract PriceFeed {
    // persistent state variables of the contract
    uint256 public activeRoundID;
    mapping(uint256 => uint256) public prices;
    mapping(uint256 => uint256) public submissionCounts;
    // method to submit a price for each 5-minute round
    function submit(uint256 roundID, uint256 price) public {
         uint256 curTime = block.timestamp;
         uint256 curRoundID = curTime - curTime % (5 * 60);
         if (roundID != curRoundID) {revert();}

         if (activeRoundID < roundID) {
             activeRoundID = roundID;
             prices[roundID] = price;
             submissionCounts[roundID] = 1;
         } else {
             uint256 curPrice = prices[roundID];
             uint256 curCount = submissionCounts[roundID];
             uint256 newSum = curPrice * curCount + price;
             uint256 newCount = curCount + 1;
             submissionCounts[roundID] = newCount;
             prices[roundID] = newSum / newCount;
         }
     }
 // other methods and state variables...
}

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


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

## 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-based:**
運算元是以 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 指令會經過四個步驟：
1. Decomposition 分解：將 EVM 的指令分解成更低階的指令。文中舉例將`SHA256`指令分解成 `讀取資料` 及 `運算hash` 的指令。
2. stack to register translation
3. Register promotion：分配資料於暫存器之中。
4. 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"。

:::info
**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 判定的指令都會被移除。

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

### 5. Memoization

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

### 6. AP merging


經過以上五個步驟，單個 FC 可以產出如上圖這樣一個 AP，將每一個 AP 合成在一起，即成為最中實際運行的 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 圖，說明有超過 90% 交易的時間差超過四秒 => Forerunner 是有機會有效的。


下表表示的是 Forerunner 與普通節點之間的差異，可以看到有99.16% 的交易是有經過 AP 加速的，而平均加速是普通節點的 8.39 倍。


在這 8.39 倍的加速之中，有些是由極端值造成的加速，有 0.53% 的交易倍加速了 50 倍以上，甚至有些超過 1000 倍。而最多交易加速了 4 倍。


下圖表示了 gas fee 與 speedup 之間的關係。其中 gas fee 越高可以推測其程式碼的複雜度越高，可以看到程式碼複雜度越高加速程度越高的趨勢。


然而 Forerunner 的運行，相比普通的節點（Geth），CPU 使用度為 3.33 倍，記憶體使用量為 2.5 倍。需要花原先 12.19倍 交易執行的時間來建立 AP 及運行。

---

# Conclusion

Forerunner 在以太坊這種 DiCE 模型的分散式系統中是有效的。經過 AP 的建立，可以將程式碼大約縮減到原先的 10% ， 有效的加速可以來到原先的 8.39 倍，而考量未被加速的交易之下還是有 6.06 倍的加速。

---

# Ref.
* [Forerunner: Constraint-based Speculative Transaction Execution for Ethereum (paper)](https://www.microsoft.com/en-us/research/publication/forerunner-constraint-based-speculative-transaction-execution-for-ethereum/)
* [SOSP 2021: Forerunner: Constraint-based Speculative Transaction Execution for Ethereum (youtube)](https://www.youtube.com/watch?v=6mh5nZPSdhw&ab_channel=Veritasium)
* [Stack Based vs Register Based Virtual Machine Architecture, and the Dalvik VM ](https://www.codeproject.com/Articles/461052/Stack-Based-vs-Register-Based-Virtual-Machine-Arch)
* [Solidity Bytecode and Opcode Basics(paper)](https://medium.com/@blockchain101/solidity-bytecode-and-opcode-basics-672e9b1a88c2)
* [Virtual Machine Showdown: Stack Versus Registers](https://www.usenix.org/legacy/events%2Fvee05%2Ffull_papers/p153-yunhe.pdf)
* [Ethereum: a secure decentralised generalised transaction ledger berlin version ( Ethereum yellow paper )](https://ethereum.github.io/yellowpaper/paper.pdf)
* [Ethereum.org/transactions](https://ethereum.org/en/developers/docs/transactions/)

本文中出現的所有圖表（除第一張來自以太坊官網）皆出自 Forerunner 論文。本文的 Hackmd 原稿請參考[這裡](https://hackmd.io/@chenyanlong/ryJjrEA4s)，有任何錯誤請不吝指教。

p.s. 這是我【111-1 Operating System】的期中報告。