最近,以太坊又一次出現大擁堵,美圖基於以太坊框架實現了 DPoS 算法而且對代碼進行了開源(連接見文末),但願藉助此方案能讓以太坊發展有更多的選擇的可能。html
圖:最近一週以太坊交易又出現大範圍擁堵git
有些人對於以太坊不是特別熟悉,因此開始以前先簡單介紹一下以太坊一些基礎。github
以太坊總體包含幾個模塊:
算法
協議管理,一個是外部訪問和交互的 JSON-RPC 協議(HTTP),一個用來節點發現和塊/交易數據(TCP/UDP) 同步;網絡
交易池,存儲當前未打包的交易;架構
共識算法,目前官方版本里麪包含了 PoW 和 PoA(Clique), 共識算法主要的做用就是決定產生新塊,合法性驗證以及衝突解決;app
EVM, 用來執行智能合約代碼的虛擬機框架
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。
關於優缺點下面引用的以太坊設計文檔裏面也有詳細的的描述,我這裏先不羅列。主要先說明兩種的區別:
Account 帳號模型跟咱們傳統業務相似很好理解,就是直接 DB 裏面存儲餘額但也引入其餘問題,好比自己沒法判斷交易是否重放問題,須要其餘手段好比 account nonce 來輔助解決。
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 算法的一些內容,做爲以前文章的補充。
以前文章裏面提到以太坊三種機制對於開發影響很大,若是是想基於以太坊作改造的要特別注意一下:
full sync 同步全量區塊並回放全部交易數據來構造全局狀態樹;
fast sync(默認) 同步全量區塊數據以及第 N 塊的全局狀態樹,同時只回放從第 N 塊以後的交易數據。這個機制很像 Redis 的 RDB + AOF 機制,這種方式避免回放所帶來的性能問題(回放交易主要的性能瓶頸是在於隨機 IO 讀寫);
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 在沒有強大的技術或者信譽背書的狀況下仍是比較難進行的, 另外就是如何產生動力驅動社區用戶不斷去投票從而不斷更新和迭代驗證人。
相關索引:
BM 解釋 BFT DPoS 視頻 https://www.youtube.com/watch?v=Xs1dyZFhIr4
Governance, Part 2: Plutocracy Is Still Bad https://vitalik.ca/general/2018/03/28/plutocracy.html
BitcoinTalk 關於中本聰懟 BM 的貼着找不到了, 網上還有一些截圖
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,後續有什麼問題能夠隨時討論。
相關閱讀:
重磅!美圖技術團隊發佈開源 Ethereum DPoS 實現
特別推薦:
比特幣、以太坊、ERC20、PoW、PoS、智能合約、閃電網絡……
想深刻了解及討論這些話題?高可用架構在知識星球(小密圈)建立了區塊鏈學習小組,共同窗習區塊鏈包括數字貨幣前沿技術,歡迎點擊連接加入。
高可用架構
改變互聯網的構建方式
長按二維碼 關注「高可用架構」公衆號