歡迎光臨
每天分享高質量文章

以太坊又一次大擁堵何去何從?深度對話美圖以太坊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 上面看看程式碼。


Q&A;

Q1: DPoS 是否背離了去中心化?

個人認為是背離的,出塊的 21 個節點就是一個小中心,DPoS 演演算法本身就是犧牲去中心化來換取效能(現在很多人也認為 PoW 的礦池算力集中也是另外一種中心化)。另外從 BM 解釋 DPoS 的另一個最佳化就是假設出塊節點都是一些知名節點(如交易所, 大的礦池等等),他們在物理上能夠做到互通,所以在出塊之後不是隨機廣播而是直接先傳送給下一個節點,這樣理論上在出塊後傳播的時間只有物理鏈路的 RTT, 比如美西到中國可能只需要幾百 ms。BM 早期跟在 BitcoinTalk 提出 Bitcoin 效能太差需要修改共識演演算法就被中本聰懟了(If you don’t believe me or don’t get it, I don’t have time to try to convince you, sorry),之前 V 神也忒過 DPoS。個人在效能提升方面也更加傾向於分片或者 offchain 這種減少主鏈交易次數的方式,DPoS 在沒有強大的技術或者信譽背書的情況下還是比較難進行的, 另外就是如何產生動力驅動社群使用者不斷去投票從而不斷更新和迭代驗證人。


相關索引: 

  1. BM 解釋 BFT DPoS 影片 https://www.youtube.com/watch?v=Xs1dyZFhIr4

  2. Governance, Part 2: Plutocracy Is Still Bad https://vitalik.ca/general/2018/03/28/plutocracy.html

  3. BitcoinTalk 關於中本聰懟 BM 的貼著找不到了, 網上還有一些截圖

  4. DPOS vs. POW by Dan Larimer http://bytemaster.github.io/bitshares/2015/01/04/Delegated-Proof-of-Stake-vs-Proof-of-Work/


Q2:既然認為 DPoS 背離了去中心化,那為啥還要擼一個美圖 DPoS ?

正如之前文章的引言,我們更多是探索,另外 DPoS 雖然一定程度背離去中心但也有自己的優點。


Q3: 不知這個專案你們開發了多久 ?比如大約用了多少人月?

我們從真正開始接觸以太坊原始碼到改造完成差不多是 2 個月左右,主要是閱讀程式碼週期比較長。人力加起來差不多是 3-4個人邊看邊做。


Q4:以後會有原始碼分析的直播麼?

不會,太細節的程式碼解析分享意義不大, 比較歡迎上去直接看程式碼,有問題隨時討論。


Q5:目前做過真實網路環境的測試嗎?執行資料怎麼樣?瓶頸在哪裡?DPoS原理上可以更快吧?

現在就是在內網驗證,沒有在多個地區部署驗證。現在把預設的出塊時間調的比較久(5s), 所以效能也就是以太坊的2-3倍。5s 是我們的除錯的預設時間,如果假設出塊節點都是直連的場景下出塊時間可以跟 Steemit 一樣調整到 1s, 另外EOS 出塊時間另外一個最佳化就是新塊優先給下一個出塊節點,這樣時間可以調整到幾百毫秒。


Q6: 投票和成為候選人是任何時候都可以投以及任何節點都可成為候選人?

投票和成為候選人跟普通交易一樣隨時可以進行,只是投票和候選⼈結果只能在下一個選舉週期生效。另外任何節點都可以成為候選人,所以線上上真正執行還是需要控製成為候選人的門檻(或者最佳化演演算法),否則候選人數過多在選舉的時候節點在排序和計算時可能會耗時比較久甚至節點不可用。


Q7:投票或者成為候選人在美圖修改 Ethereum 版本⾥⾯是如何體現的?

我們把投票和候選人相關的操作都當做是普通的交易,在交易⾥面增加一個 type 欄位來區分是普通交易、投票還是候選⼈相關操作,這個在之前的⽂文章⾥⾯也有體現。


寫在後面

未來美圖技術團隊將會結合自身的業務做更多的拓展,我們也期待和更多的技術人員交流。


程式碼開源地址:https://github.com/meitu/go-ethereum,後續有什麼問題可以隨時討論。

相關閱讀:


只用200行Go程式碼寫一個自己的區塊鏈!

200行Go程式碼實現自己的區塊鏈——區塊生成與網路通訊

200行Go程式碼實現區塊鏈 —— 挖礦演演算法

超越比特幣以太坊的區塊鏈技術:石墨烯專案簡介

以太坊完全指南

重磅!美圖技術團隊釋出開源 Ethereum DPoS 實現


特別推薦:


比特幣、以太坊、ERC20、PoW、PoS、智慧合約、閃電網路……

想深入瞭解及討論這些話題?高可用架構在知識星球(小密圈)建立了區塊鏈學習小組,共同學習區塊鏈包括數字貨幣前沿技術,歡迎點選連結加入。


區塊鏈學習小組

高可用架構

改變網際網路的構建方式

長按二維碼 關註「高可用架構」公眾號

贊(0)

分享創造快樂