以太坊又一次大擁堵何去何從？深度對話美圖以太坊DPoS演演算法實現團隊

最近，以太坊又一次出現大擁堵，美圖基於以太坊框架實現了 DPoS 演演算法並且對程式碼進行了開源(連結見文末)，希望藉助此方案能讓以太坊發展有更多的選擇的可能。

圖：最近一週以太坊交易又出現大範圍擁堵

有些人對於以太坊不是特別熟悉，所以開始之前先簡單介紹一下以太坊一些基礎。

以太坊整體包含幾個模組：

1. 協議管理，一個是外部訪問和互動的 JSON-RPC 協議(HTTP)，一個用來節點發現和塊/交易資料(TCP/UDP) 同步；

2. 交易池，儲存當前未打包的交易；

3. 共識演演算法，目前官方版本裡麵包含了 PoW 和 PoA(Clique), 共識演演算法主要的作用就是決定產生新塊，合法性驗證以及衝突解決；

4.  EVM， 用來執行智慧合約程式碼的虛擬機器

5. StateDB, 由 MPT（merkle patric trie） 和 KV 儲存兩部分組成，以太坊所有資料最終都會落到 KV 儲存。

錢包透過 JSON-RPC 將簽名過的交易傳送到交易池，然後由共識演演算法來決定能否出塊以及時機(非挖礦節點不會主動出塊，只有被動接收塊)，然後將塊寫到 DB。

由於以太坊是根據 Gas Price 決定優先打包哪些交易，所以我們可以看到以太坊的交易池裡面會有一個最大堆用來放當前價格較高的交易 ID。

另外，為了避免交易重放問題，以太坊還在賬號裡面引入了 nonce，用來表示這個是當前使用者發出的交易編號(從 0 開始嚴格 +1 遞增)。比如 A 給 B, C 兩個人轉賬的兩筆交易分別是 tx1（nonce=1） 和 tx2 (nonce=2)， 這兩筆交易實際上是有依賴關係的，節點在未收到 nonce = 1 這筆交易的情況，nonce = 2 是不能被打包的(假設當前節點裡面 A 賬號 nonce = 0)。

所以就有了我們下麵圖中的 Queued Pool 和 Peding Pool, 如果一筆交易過來會先到 Queued Pool, 如果 nonce 值符合要求那麼會遷移到 Pending Pool, Pending Pool 裡面所有交易都是認為可打包的。Pending Pool 也可能因為塊回滾會導致交易重新回到 Queued Pool。

接著就由共識演演算法部分來決定當前節點能否出塊以及出塊的時機，這個不同共識演演算法不太一樣，這裡不進行詳細描述，最終被打包的塊就會寫入到 DB 裡面來，至於 DB 裡面如何儲存這些賬號以及對應的資產，不同賬號模型儲存實現不一樣。

比特幣的賬號模型是 UTXOs(unspent transaction ouputs), 下麵的圖來自 Ethereum Design Rationale。

關於優缺點下麵取用的以太坊設計檔案裡面也有詳細的的描述，我這裡先不羅列。主要先說明兩種的區別： 

1. Account 賬號模型跟我們傳統業務類似很好理解，就是直接 DB 裡面儲存餘額但也引入其他問題，比如本身無法判斷交易是否重放問題，需要其他手段比如 account nonce 來輔助解決。

2. UTXOs 模型由上圖可以看到儲存不再是餘額，而是 unspent transaction outputs， 這個機制可以簡單理解就是一次性的支票，收款的類似別給你簽完名一張一次性的支票(只能被使用一次)，轉賬也是類似，看看自己有哪些面額的支票，找出足額的支票簽名後放到一起給對方。

相關索引: Ethereum Design Rationale 

https://github.com/ethereum/wiki/wiki/Design-Rationale。

接著引申一個問題就是如何儲存賬號的餘額？ 

以太坊的賬號餘額資料是儲存在由 Patricia Trie 和 Merkle Trie 組成的(MPT)樹上，主要利用 Patricia Trie 的特性實現賬號餘額的快速查詢和 Merkle Trie 來證明交易是否被篡改過。Patricia Trie 和 Merkle Trie 之前在很多非區塊鏈場景都使用到了(比如 kernel 的新 ip 路由查詢演演算法使用的就是 patricia trie )。 

儲存餘額的樹是所有區塊共享的, 如下圖:

這個可以很直觀的看到，每次塊內交易產生交易的時候實際上只複製了被修改到的賬號和對應的父節點相關資料並產生新的 trie root, 這樣在不同塊往下查詢到的餘額就是對應塊的最終餘額，比如我們最近的餘額就是沿著最新塊查詢的餘額。

每個塊頭除了包含餘額這個樹之外還有交易和收據樹，這兩個樹都是每個塊獨有的，塊和塊之間是沒有任何關聯。如果要弄懂以太坊的就一定先理解清楚 merkle patricia trie。

如果要弄懂以太坊的就一定先理解清楚 Merkle Patricia trie，另外的儲存就是將樹的節點內容儲存到 KV(當前以太坊用的 leveldb), 這個替換 KV 儲存也特別簡單，只要實現 GET/PUT/DELETE 幾個介面。

上面就是以太坊整體模組的一些簡單介紹, 接下來會細化 DPoS 演演算法的一些內容，作為之前文章的補充。 

之前文章裡面提到以太坊三種機制對於開發影響很大，如果是想基於以太坊做改造的要特別註意一下:

1. full sync 同步全量區塊並回放所有交易資料來構造全域性狀態樹；

2. fast sync（預設） 同步全量區塊資料以及第 N 塊的全域性狀態樹，同時只回放從第 N 塊之後的交易資料。這個機制很像 Redis 的 RDB + AOF 機制，這種方式避免回放所帶來的效能問題(回放交易主要的效能瓶頸是在於隨機 IO 讀寫)；

3. light sync 只同步區塊頭部資訊不同步具體交易內容，主要是用於錢包實現 SPV 功能。

之前我們開發過程中踩到一個坑就是 Fast Sync 導致的，這個在之前的文章已經描述過，這裡不再贅述。Fast Sync 在 Geth 作者開發這個特性的時候也有比較詳細的描述， 具體見 PR: https://github.com/ethereum/go-ethereum/pull/1889。

這裡面沒有提到另外一個比較重要的點是由於 Fast Sync 點之前的塊實際上是沒有回放的，直接把最終的餘額數同步過來，所以這個點之前是沒有辦法根據塊來獲取到餘額的，這個大家需要註意一下。

DPoS 本身其實是足夠簡單，相對於其他的幾個演演算法就是多儲存幾個全域性狀態樹: 

• EpochTrie 記錄每個週期的驗證人串列

• VoteTrie 記錄投票人對應驗證人

• CandidateTrie 記錄候選人串列

• DelegateTrie 記錄驗證人以及對應投票人的串列

• MintCntTrie 記錄驗證人在週期內的出塊數目

這幾個樹的作用主要是為了避免獲取相關資料需要從創世塊開始回放資料而增加，所以這幾個樹的角色和我們賬號的餘額樹是一樣的，都是全域性狀態樹(所有塊共享)並把樹的 root 儲存在塊頭。這裡我們之前踩到的坑其實還是跟 Fast Sync 有關，原始程式碼裡由於只有賬號這個全域性狀態樹，所有同步的時候也只同步這個賬號狀態樹，其他沒有傳送就會導致我們選舉有問題。

其他開發過程主要是一些細節和邏輯的開發，也比較簡單，我們這裡就不在展開去說，歡迎大家去 Github 上面看看程式碼。