本文介紹了近期美圖區塊鏈實驗室在學習和研究過程中的一些成果。Ethereum是比較成熟和智能化的案例，對美圖日後發展區塊鏈技術有相當的借鑑性，因此選擇其作為研究對象。
我們基於 Ethereum(1.7.3版本) 實現 DPoS 共識算法主要有兩個⽬的, ⼀個是我們之前主要是通過看代碼的⽅式來研究區塊鏈的⼀些技術，修改代碼可以進⼀步加深和鞏固代碼設計上的理解。另外⼀點是通過將修改的代碼開源，吸引更多的⼈來關注這個項⽬，那麼也算是對社區的⼀種回饋。
Github 地址: https://github.com/meitu/go-ethereum
共識算法
開始分析 DPoS 實現之前，先簡單介紹一下當前幾個主流的數字貨幣共識算法。下面羅列的只是一部分共識算法，還有其他許多算法沒有提及，羅列的順序以及時間序不代表算法的優劣。
PoW(Proof of Work)
1993 年由 Cynthia Dwork 和 Moni Naor 提出，主要是用來解決垃圾郵件問題
2009 年 Satoshi 使用 PoW 作為 bitcoin 的共識算法，PoW 成為區塊鏈第一個共識算法。隨著 GPU 挖礦算法的出現, Satoshi 預期的每個 CPU 一票的機制被破壞
2011年 萊特幣(比特幣的第一個山寨幣)， 採用 scrypt(由一個黑客發明) ，特點是挖礦需要更多內存以及並行計算困難，相比 SHA256 更加能夠抵禦礦機， 但由於安全性上沒有經過嚴格的驗證所以並未大規模應用
2013 年 primecoin 把算力用來尋找最大素數，解決算力浪費問題
2015 年 etherum 使用 PoW 作為共識算法, 提出 dagger-hashimoto 的改良版本，具備內存難解性以及更好的抵抗 ASIC
算法可以簡單描述如下:
PoW 不斷窮舉的方式找到滿足條件的整數需要消耗大量的計算資源， 而算力純粹是為了找到一個沒有任何意義的隨機數，這成為大家詬病 PoW 的重要原因之一，現在有一些團隊正在嘗試把這些算力結合到現實中的一些場景，比如 AI 模型計算等。PoW 另外一個問題就是性能低下，當前比特幣的性能差不多在 7 qps 左右，以太坊大概是比特幣的兩倍。現在比較知名的 offchain的 代表 lightning 主要就是為了解決比特幣的性能問題，還有就是 V 神正在做的 ethereum sharding 等
PoS(Proof of Stake)
2012 年 sunny king 提出 PoS 算法， 主要是為了解決 PoW 對於算力消耗過大的問題
2013 年 peercoin 首個實現 PoS 的數字貨幣但仍然保留 PoW。PoW 作為冷啟動階段使用，後續逐步降低 PoW 權重。同時使用幣齡(coin age) 來解決財富累積的問題，這個也引入新的問題(下面的提到的幣齡累積問題)。
2013 年 11 月 NXT 實現了首個純 PoS 的數字貨幣
2014 年 blackcoin 也使用 PoS 作為共識算法同時去掉了幣齡
PoS 算法描述如下：
上面公式中唯一的變量只有左邊的 t，同時變化範圍在固定空間內(比如不超過 1h，那麼 t 的取值區間只有 7200 個，找不到就退出)，這樣就不再需要像 PoW 一樣用窮舉的方式來找隨機數，也就不會存在消耗大量算力的問題。另外， 我們可以看到計算閾值時加上了用戶餘額，意味著如果用戶擁有的資產越多，那麼就找到正確隨機數的概率也會越大。
PoS 在解決算力的同時也引入了潛在的攻擊問題：
Nothing at stake， 由於 PoS 不需要消耗太多算力，所以當出現分叉時，礦工為了利益最大化會選擇同時在兩個分叉進行挖礦，從而導致更多的分叉。而 PoW 是算力敏感的，礦工只能選擇押注其中一條路徑。
長距離攻擊，在 PoW 中惡意節點即使擁有 51% 以上的算力，如果想篡改賬本也是需要花費大量的成本。而 PoS 對於算力的要求很低，那麼就存在被篡改的風險
幣齡累積攻擊，有些算法實現中除了考慮擁有的資產之外還加上了幣齡，那麼就有可能導致部分節點不需要持有 51% 的資產就可以產生攻擊
DPoS(Delegated Proof of Stake)
2014 年 4 月Bitshares 的首席開發者 Dan Larimer 提出 DPoS 算法並應用到 Bitshares， 截止到當前(2018年 5 月) 已經運行了 4 年左右
2016 年7 月 Steemit 公司發佈 Steemit 項目以及今年的 EOS 測試網絡也都是使用 DPoS 作為共識算法
DPoS 被認為是 PoS 的改進版本，DPoS 通過每隔一段時間進行一次選舉，然後由這些選舉出來的節點來負責出塊和互相監督驗證，這樣就可以大大降低出塊以及塊確認的時間。這樣的選舉方式帶來的問題是出塊節點會比 PoW 以及 PoS 更加中心化。
DPoS 算法概要
當前以太坊的共識算法是 PoW，後續會逐漸過渡為 PoW + PoS。目前為了解決算力消耗過大和性能問題，我們做的一個嘗試是將共識算法從 PoW 修改為 DPoS。
DPoS 共識算法最大的特點是出塊人是由選舉產生而不是通過算隨機數。算法設計上和中心化的投票選舉機制和 Bitshares 提出的 DPoS 算法 沒有太本質的區別，唯一的區別就是把投票的過程變成一筆交易。家詳解的介紹我們整體的流程以及具體的實現。
整體流程如下:
算法主要包含兩個核心部分:
塊驗證人選舉
塊驗證人調度
第一批塊驗證人由創世塊指定，後續每個週期(週期由具體實現定義)都會在週期開始的第一個塊重新選舉。驗證人選舉過程如下:
踢掉上個週期出塊不足的驗證人
統計截止選舉塊(每個週期的第一塊)產生時候選人的票數，選出票數最高的前 N 個作為驗證人
隨機打亂驗證人出塊順序，驗證人根據隨機後的結果順序出塊
驗證人調度根據選舉結果進行出塊，其他節點根據選舉結果驗證出塊順序和選舉結果是否一致，如果不一致則認為此塊不合法，直接丟棄。
DPoS 實現
以太坊當前代碼裡面已經包含了幾種共識算法的實現:
PoW在主網使用FakePow在單元測試使用PoA(Proof of Authority)在測試網絡中使用
為了在代碼中實現多種共識算法，以太坊抽象了一套共識算法接口，實現不同的共識算法只要實現幾個接口即可。另外由於 DPoS 為了避免每次選舉都從創世塊開始回放歷史數據，增加了幾個全局狀態樹用來記錄選舉和投票的狀態， 並把樹對應的 root 存儲到塊頭，其中包括：
EpochTrie 記錄每個週期的驗證人列表
VoteTrie 記錄投票人對應驗證人
CandidateTrie 記錄候選人列表
DelegateTrie 記錄驗證人以及對應投票人的列表
MintCntTrie 記錄驗證人在週期內的出塊數目
接口
核心實現
我們先看看打包塊的流程:
礦工會定時通過 CheckValidator去檢查當前的 validator 是否為當前節點，如果是的話則通過CreateNewWork來創建一個新的打塊任務，CreateNewWork主要包含三部分的內容：
Prepare，上面看到的共識算法需要實現的接口，主要是初始化塊頭基礎信息CommitTransactions， 主要是從 transaction pool 按照 gas price 將交易打包到塊中Finalize，將 prepare 和 CommitNewWork 內容打包成新塊，同時裡面還有包含出塊獎勵、選舉、更新打塊計數等功能
最後 Seal 會對新塊進行簽名，之後再將新塊廣播到鄰近的節點，其他節點接收到新塊會根據塊的簽名以及選舉結果來看新塊是否應該由該驗證人來出塊。相對其他的共識算法來說，DPoS 的共識算法主要區別在於選舉，所以可以重點來看這塊實現:
我們在打包每個塊之前都會調用 tryElect來看看當前塊是否是新週期的第一塊，如果是第一塊則需要觸發選舉。 整體的選舉的實現比較簡單，主要是做了三個事情:
根據上個週期出塊的情況把一些被選上但出塊數達不到要求的候選人踢掉
截止到上一塊為止，選出票數最高的前 N 個候選人作為驗證人
打亂驗證人順序
接下來看看計票實現(忽略一些不重要的代碼):
計票的邏輯也很簡單:
先找出候選人對應投票人的列表
所有投票人的餘額作為票數累積到候選人的總票數中
之前我們看到除了上面看到幾個接口之外，共識算法接口還要求實現比如像 VerifyHeader，VerifySeal，VerifyUncles等幾個驗證接口，主要是當其他人接收到新塊時會使用這幾個方法分別來驗證塊頭，內容以及叔塊的信息是否符合驗證規則。由於篇幅的關係這裡不進行詳細介紹。
成為候選人/投票
某個節點想要成為驗證人，首先要成為候選人，接著其他人才能對這個候選人進行投票。不管是投票還是成為候選人，對於節點來說其實都是一筆交易，之前的交易主要是轉賬或者合約調用，因此現在多增加幾種交易類型。
在一個新塊打包時會執行所有塊內的交易，如果發現交易類型不是之前的轉賬或者合約調用類型，那麼會調用 applyDposMessage進行處理。
可以看到投票/成為候選人跟我們傳統的實現差別不大，本質還是對於數據的增刪查改，只是在數據的更新上區塊鏈會比普通的 KV 更加複雜和特殊一些。
測試
第一批創世驗證人在 dpostestgenesis.json 修改，為了方便測試可以將驗證人數目(maxValidatorSize)調小
開發遇到的問題
fast sync 模式下不接收廣播的塊導致節點之間一直無法互相同步新塊
以太坊同步有三種同步機制：
full sync同步全量區塊並回放所有交易數據來構造全局狀態樹fast sync（默認） 同步全量區塊數據以及第 N 塊的全局狀態樹，同時只回放從第 N 塊之後的交易數據。這個機制很像 Redis 的 RDB + AOF 機制，這種方式避免回放所帶來的性能問題(回放交易主要的性能瓶頸是在於隨機 IO 讀寫)。light sync只同步區塊頭部信息不同步具體交易內容，主要是用於錢包實現 SPV 功能
fast sync 模式下會直接丟棄廣播的塊，只有在進入 full sync 之後才會接收。如果我們同時以默認同步方式(fast sync)啟動多個節點，由於節點之間出塊的頻率一樣導致所有節點都無法進入 full sync 模式，節點之間同步的塊都會被丟棄。解決方案是創始節點以 full sync 方式啟動，我們開源的代碼為了方便測試，默認也會使用 full sync。
加入 DPoS 之後，區塊的存儲結構發生一些變化，之前一些驗證流程邏輯需要調整。比如驗證人是否合法理論上需要在
VerifyHeader來做校驗 ，因為塊頭只是存儲需要對應樹的 root, 而沒有具體的內容，需要等到新塊寫入 DB 之後再來校驗(注意這裡的寫入本地指的是塊數據寫入 KV，而塊本身並未插入鏈)。由於以太坊一些實現機制上也相對複雜一些，開始對於設計細節瞭解不是特別深入，在調試過程中也會花費比較多的時間。另外就是單元測試龐大，在對代碼修改過程中需要不斷地理解和修正單元測試。
參考
[1] https://steemit.com/dpos/@dantheman/dpos-consensus-algorithm-this-missing-white-paper
[2] https://github.com/ethereum/go-ethereum/pull/1889
[3] https://bitfury.com/content/downloads/pos-vs-pow-1.0.2.pdf
[4] https://bitshares.org/technology/delegated-proof-of-stake-consensus/
[5] https://github.com/ethereum/go-ethereum
[6] https://github.com/meitu/go-ethereum
閱讀更多 高可用架構 的文章
