以太坊，幀同步遊戲和可重複性問題

08-22

以太坊，幀同步遊戲和可重複性問題

來自專欄幣與AI4 人贊了文章

今天終於要開始講以太坊（Ethereum）啦。從2016年底開始，幣圈屢創新高，也就是因為以太坊的 ERC20 合約的發明，大家只要會用電腦，跑軟體，就能發幣募資，發家致富。

Vitalik 當初做以太坊最主要的洞見，就是將區塊鏈上一系列的交易，想像成一系列的狀態改變。如果將比特幣（Bitcoin）的區塊鏈按這樣的方式去想的話，比特幣一開始的狀態是什麼都沒有的。原初區塊（Genesis block）的交易對這個狀態做了改變，將50個比特幣授予了地址 1A1zP1eP5QGefi2DMPTfTL5SLmv7DivfNa 。在比特幣中，交易（Transaction）是指令，挖礦（Bitcoin mining）是執行指令，而所有賬戶的比特幣餘額就是所操作的狀態空間。

在以太坊中，智能合約是在 EVM 上撰寫的指令，挖礦是執行智能合約的指令，而官方實現中的 LevelDB 就是所操作的鍵值表存儲（Key-value store）狀態空間。

比特幣的交易執行並不是圖靈完備的（Turing complete）。有很多方法可以證明這一點，一個簡單的方法是可以用輸入只讀圖靈機（Read-only Turing machine）來實現比特幣的交易執行系統，證明比特幣的交易執行屬於只讀圖靈機可以解決的範疇。又知只讀圖靈機與確定有限狀態自動機（Deterministic finite automaton）等價，因此可知比特幣的交易執行系統並非圖靈完備。

而以太坊的智能合約是近似圖靈完備的（quasi-Turing complete）。在取消掉 Gas 的限制之後，EVM 是嚴格等價於圖靈機的（EVM 的文檔特別指出了它可以操作的內存空間是沒有限制的，等同於在圖靈機中磁帶的長度是沒有限制的）。加入 Gas 的限制之後（在以太坊的定義中，每一個指令要消耗一定的 Gas，當 Gas 消耗到零之後，無論程序在什麼狀態都會停止執行，而程序所在的狀態就是 EVM 在執行了這個合約之後的最終狀態），EVM 的計算能力直接與 Gas 限制有關。

共識的形成

比特幣維護的共識是一系列認可的交易。以太坊維護的共識是一系列對用戶賬戶和合約賬戶的更新。與比特幣類似，以太坊參與挖礦的節點需要在 EVM 執行交易結束後解一個謎題，之後將答案廣播。謎題的答案包括了執行的交易和最後賬戶狀態的驗證碼。為了驗證被廣播的答案的正確性，所有參與挖礦的節點都需要分別執行交易，驗證賬戶的狀態，確認接收的廣播的答案然後再開始下一條交易的執行。

因此，以太坊的設計需要保證每條交易在 EVM 上執行之後的狀態都是一致的。如果同一條交易在不同實現上執行之後的狀態不一致，共識就無法達成。在紙面上，以太坊設計的 EVM 是一個抽象的機器。EVM 在 EVM yellow paper 中是明確定義的，因此不存在未定義的行為（Undefined behavior）。為了避免一些實現上的錯誤，EVM 不支持浮點數的運算，對於整數的運算潛在的溢出處理也都有定義。

類似以太坊這樣，需要每台參與的節點都執行相同的操作，並保證輸出狀態一致的系統，還有就是在線遊戲。

幀同步

大型在線遊戲的同步，在 P2P 幀同步和客戶端/伺服器架構兩端中間，有著不同的考量。在客戶端/伺服器架構中，客戶端將動作輸入提交給伺服器，伺服器運行完整的遊戲邏輯，將動作輸入執行之後把環境的更新通過增量壓縮之後，發回給所有的客戶端。客戶端接收到增量更新之後，更新環境和數據。在 P2P 幀同步架構中，參與的玩家將動作輸入（以及動作發生時的邏輯幀編號）廣播給所有人，接收到動作輸入後，遊戲將狀態退回到動作發生的邏輯幀，執行動作輸入，然後將遊戲邏輯繼續執行到當前邏輯幀。

在 P2P 幀同步架構中，不同的遊戲端需要在同樣的邏輯幀時間上執行同樣的動作輸入，並保證各個遊戲端在執行後遊戲的狀態一致。與 EVM 類似，幀同步遊戲的設計也需要避免未定義行為和硬體實現上的問題（浮點數運算）。與 EVM 不同，幀同步遊戲並沒有抽象的動作執行機器，而且有巨大的上下文（Context）環境。因此，在幀同步遊戲中，通常還需要處理：

隨機數發生器狀態的一致性（可以每個邏輯幀共享一個隨機數發生器，隨機數發生器使用預先約定的數字和當前邏輯幀編號初始化）；
遊戲版本的同步，拒絕不同遊戲版本的玩家參與同一局遊戲；
不同系統平台調用函數的一致性，避免在遊戲邏輯中與操作系統交互（渲染與遊戲邏輯隔離）；
選擇合適的編譯參數，避免一些容易出現不一致結果的參數（例如-ffast-math）。

在以太坊中，交易的執行順序並不重要，在挖礦結束後，節點會廣播當前系統狀態的增量更新，其他的節點在驗證（在驗證時會按順序執行區塊中的交易）後會接受最長的區塊鏈作為正確的區塊鏈，並在其上進行新的挖礦活動。

在幀同步遊戲架構中，因為並不會廣播當前遊戲的狀態，所以動作輸入的順序，和邏輯執行中的順序都很重要。動作輸入首先按邏輯幀編號排序，而在每個邏輯幀的執行中，每個實體（Entity-Component-System 架構中的 Entity）按照標識號的順序執行操作。如果在某幀中有創建新的實體，它的標識號需要通過一個一致的生成器來產生。

系統狀態的回滾對於以太坊和幀同步遊戲中都是需要解決的大問題。在以太坊中，節點在收到廣播的幾個新區塊之後，需要將當前的狀態回滾，然後驗證收到的所有新區塊，並更新當前的狀態。為了實現高效的狀態回滾，以太坊的每個區塊的所謂增量更新其實包含了系統所有的狀態。狀態的回滾只是從之前的區塊中讀取系統的所有狀態。在以太坊中，系統的所有狀態（鍵值表）是用一種叫 Patricia 樹的數據結構儲存的。這種數據結構可以引用之前區塊中 Patricia 樹的子樹，保證了每個區塊的大小是可控的。

在幀同步遊戲中，回滾的實現要簡單的多。幀同步遊戲中各個遊戲端會同意將一個邏輯幀（比如上個回合的最後一個邏輯幀，在幀同步遊戲中，回合的概念與遊戲的反作弊息息相關，但是具體講解 Lockstep protocol 中的反作弊不在我們的範圍之內）作為正確的邏輯幀，並保存其所有的狀態。如果需要回滾，遊戲不允許回滾到這個邏輯幀之前。所以狀態的回滾操作就變成了回到之前正確的邏輯幀，然後將遊戲用當前已知的動作輸入回放到當前的邏輯幀。

可重複性

直覺上，計算機的運行是確定的，給定一樣的輸入，就會有一樣的輸出。然而，因為軟體是在不同的計算機硬體上運行的，實現的差別，以及複雜軟體中引入的熵造成維持這樣的期待需要額外的努力。如上，在以太坊的設計中，通過完整定義一個抽象的計算機（EVM）來嘗試解決可重複性的問題。在幀同步遊戲中，通過消除偽隨機性，取消浮點數的應用，保證執行順序和同步程序版本號來避免在可重複性上出現問題。

解決可重複性，比如程序編譯的可重複性，是計算機信任鏈中的重要一環（Reflection on Trusting Trust）。如果同一份源代碼編譯出來的可執行文件與下載的可執行文件不一樣，那麼相信提供的源代碼安全也就無從談起（當然，和 Trusting Trust 講的一樣，還要信任編譯器）。