區塊鏈共識算法的比較研究

摘 ?要： 區塊鏈是一種去掉中心管理結構的通過分布式的節點運行的公共數據庫。區塊鏈是從2008年提出，經過多年的發展，近些年來收到社會的特別關注。區塊鏈的項目較多，例如以太坊、Fabric、萊特幣和比特幣等等。其中熱度最高的就是比特幣。比特幣是區塊鏈最本質和最原始的應用。區塊鏈的共識算法，可以保證區塊鏈中的節點參與共識過程的有效性。本文梳理了各種區塊鏈共識算法（如POW、POS、DPOS和PBFT）的思想，分析各類算法的優點和缺點[1]。

關鍵詞： 區塊鏈;分布式系統;共識算法;拜占庭協議;PoW;PoS

中圖分類號： G354.4 ? ?文獻標識碼： A ? ?DOI：10.3969/j.issn.1003-6970.2019.04.048

本文著錄格式：陳玎樂. 區塊鏈共識算法的比較研究[J]. 軟件，2019，40（4）：219221

【Abstract】： Block chain is a public database running through distributed nodes without central management structure， which was put forward in 2008. With years of development， it has received special attention from society in recent years. There are many items of block chain， including Ethernet square， Fabric， Wright coin and Bitcoin， etc. And Bitcoin is the hottest among them， which is the most essential and original application of block chain. Consensus algorithm of block chain can ensure validity of block chain nodes in participating consensus process. The paper combs ideas of various block chain consensus algorithms （such as POW， POS， DPOS and PBFT）， and analyses advantages and disadvantages of these algorithms[1].

【Key words】： Block chain; Distributed system; Consensus algorithms; Byzantine protocol; PoW; PoS

0 ?引言

區塊鏈（Blockchain）技術是一種去掉中心管理結構的，通過分布式的節點運行的公共數據庫。其具有自治性、防篡改性、去中心化和完備可追溯等特點。分布式網絡是區塊鏈建立的基礎。為了維護系統中的每一個節點，將指定時間內的數據打包整理成一個區塊，每一個區塊保存前一個區塊的哈希信息，保證區塊形成連貫的鏈。所以區塊鏈的本質是數據存儲技術。經過多年的區塊鏈的發展，比特幣、Fabric、萊特幣、BigchainDB和以太坊等項目應運而生，并且受到了廣泛的關注。其中最成功的項目是比特幣[2]。比特幣是近些年最成功的一個分布式的點對點加密貨幣。其本質就是一種用分布式的數字賬本記錄商務交易的金融平臺。比特幣實現了無需第三方擔保的電子現金系統，但數字貨幣面臨著兩大問題：拜占庭問題[1]和雙花[2]（參與運算的節點如何建立統一的賬目，如何保證同一筆資金不被用于多個金融交易）。問題的本質，就是在沒有第三方中心擔保的電子金融系統的環境中，如何保證每個節點對同一數據的認可。為了實現高效、公平、穩定的分布式系統，區快鏈融合了共識算法，密碼學，Merkle trees等多個技術。所以區快連是多個成熟技術的完美融合。這個成熟技術中，共識算法是解決區塊鏈中一致性問題。經過多年的科學研究和商業的發展，共識算法已經發展和演變出多個體系。如何選擇合適的算法使區塊鏈的系統達到最優的效果，是設計區塊鏈中重要的環節[3-6]。

1 ?主流區塊鏈共識算法

共識算法也稱為分布式一致算法。這些算法包含Paxos 算法、Zab算法、Kafka算法等等[3]。該算法針對分布式數據庫的操作，并且不考慮拜占庭容錯問題。綜合考慮算法的安全性和實際應用中需求，區塊鏈的公有鏈 和許可鏈的共識算法也不一樣。在公有鏈中，例如POS（Proof of Stake）、POW（Proof of Work）[4]等一系列的拜占庭容錯類的共識算法被應用起來。

根據打包節點方式、一致性的程度和容錯能力等特點，區塊鏈共識算法可以分為多了不同維度的類別。根據打包節點的方式，區塊鏈共識算法分為聯盟類、選舉類、證明類、隨機類等。其中常見的區塊鏈共識算法是選舉類。常見的證明類算法包括POW（Proof of Work）和POS（Proof of Stake）。這兩種算法不同的是POW證明的點是礦工的算力，而POS 證明的點是參與者占有系統虛擬資源的權益;隨機類算法中常見的是通過依賴隨機數字選取打包節點的Algorand[6]和PoET3;聯盟類算法中的一種以 DPOS[7]為代表的“民主集中式”輪流獲得打包權;還有很多混合類的共識算法，類如很多系統采用 PoW+PoS 的共識機制[7]。

2 ?常用共識算法

2.1 ?工作量證明算法（Proof of Work）

比特幣早期的應用的過程中，其核心的思想是通過各個節點的算力競爭選擇打包節點。比特幣系統通過分布式系統的各個節點的計算機算力通過互相競爭解決復雜并且驗證容易的SHA256數學難題。最快解決問題的節點將獲得下一區塊的記賬權利以及系統生成的比特幣獎勵。POW在比特幣的應用中具有重要的意義。工作量證明機制（Proof of Work）簡稱POW，簡單解釋就是做的多獲得就多。POW是一種應對抵御服務攻擊或者其他濫用的經濟對策，其要求發起者進行一定量的運算，該理論是1993年Cymhia Dwork和Moni Naor提出。比特幣系統中的每一個節點都時刻進行高強度的復雜運算，獲得一個隨機數，然后根據這個隨機數獲取生成區塊的機會。因此該系統也需要一定的獎勵機制，即代幣，生成區塊獲得定制的代幣獎勵。Proof of Work高度依賴分布式系統中的各個分點的計算機，計算機的性能越高，POW的性能就越高。與其他共識算法相比，Proof of Work構成的成本較高，但區塊生成的效率較低。其性能如表1所示。

2.2 ?股權證明（Proof of Stake）

為了解決POW算法巨大浪費計算能力的問題，POS（Proof of Stake）共識算法被提出。權益證明機制（POS）是一種 依賴于驗證者在網絡中的經濟利益的公共區塊鏈的共識算法。在基于工作量證明（POW）的區塊鏈中，該算法鼓勵解決密碼難題的參與的區塊，以驗證交易的成功并創建新的區塊-—簡稱采礦。在基于權益證明機制（POS）的公共區塊鏈中，驗證者循環在下一個區塊提出投票和投票，每一位驗證者投票的權重取決于該驗證者存款的大小——股權。簡單來說，股份越多，挖礦越容易;擁有的股份越少，越難產生區塊。所以權益證明機制是對工作量證明的升級，根據各個分布式節點擁有的代幣動態求出隨機數的難度，擁有的代幣越多則容易求出[8]。

雖然權益證明機制（POS）算法能在一定程度上降低工作量證明（POW）算法帶來的巨大浪費，避免了計算資源的競爭，但其仍然存在一些問題。例如某一用戶長時間持有區塊鏈資產，或者持有大比重的區塊鏈資產。如果首次幣發行（Initial Coin Offering，簡稱ICO）最初就持有一定量區塊鏈資產，這樣就造成了分配不均，同時對網絡中新加入的分布式節點也不公平。但是POS 也沒有完全避免計算資源的競爭怪圈，該算法依然浪費一定的計算資源。其優缺點總結如下表所示：

2.3 ?股權授權證明算法（Delegated Proof of stake）

股份授權證明機制（DPOS，Delegated Proof of stake）又稱為“股東代表機制”，將擁有一定數量的代幣的每個節點看作為股東，各個節點根據持有的代幣的數量做出定量的投票，最后選出定量的節點。這些節點作為代表，輪流生成區塊，同時其代表們也會收到等同于一個平均水平的 區塊所包含交易費的10%作為報酬[8]。如果一些代表在生成區塊的過程中發現了問題，股東將會重新投票，并選取新的代表進行替換[9]。

如果將POW共識算法看作“算力為王”的記賬方式，POS共識算法看作“權益為王”的記賬方式，那么DPOS就是“民主集中制”的記賬方式。該算法不僅有效的解決了POW資源浪費的問題和礦池對去中心化[5]構成的威脅的問題，還能夠彌補POS中有記賬權益的參與者但沒有記賬實權的缺點。所以，該算法設計者認為DPOS是當時最高效、最靈活、最快速和去中心化的共識算法。其明顯的優缺點如下：

2.4 ?實用拜占庭容錯算法（Practical Byzantine Fault Tolerance）

實用拜占庭容錯算法（PBFT，Practical Byzantine Fault Tolerance）是由Liskov和Castro提出一種基于狀態機復制的一致性算法[10]。該算法被廣泛應用于分布式系統中。在Peer-to-peer networking中，各個分布式節點通過節點間傳遞的信息達成共識，最終生成區塊。但是由于系統、網絡等等外在因素影響，使節點間傳遞的信息損毀或者丟失，導致在進行信息驗證時產生錯誤信息。為了解決該問題，一種信息容錯率比較高的解決方案的PBFT 算法應運而生[9]。綜合考慮了拜占庭將軍問題，該算法依據問題節點的數量驗證本次共識是否可信。假設對等網絡中節點的總數量為M，問題節點的數量為m，則在本次共識過程中，依據條件：M>=3m是否成立，判斷本次共識過程是否有效。PBFT算法優缺點如下表所示：

3 ?共識算法比較

在第2節介紹完共識算法后，以下列表對其進行比較。從表5中可以發現，POW算法用時最長，但資源消耗最高，但其在研究和商業領域仍然有重要的意義。DPOS算法雖然具有髙效和節能的優點，但是在應對拜占庭容錯節點的問題沒有POW算法效果好。以下是對常用的四種共識算法機制進行比較[10]。

4 ?結語

該文對現有的區塊鏈的共識算法進行了總結，并且分別從公有鏈和許可鏈具體描述了不同的共識算法。對于公有鏈，我們介紹了POW、POS和DPOS三種共識算法，并分析了算法的優缺點。針對許可鏈，我們注重描述了BPFT算法的思想和優缺點。最后針對上述幾種算法，分別從資源消耗、中心化程度、吞吐量等進行分析對比。我們充分了解現有共識算法。

參考文獻

[1] 張偲. 區塊鏈技術原理?應用及建議[J]. 軟件， 2016， 37（11）： 51-54.

[2] 黨京， 孫弋. 基于區塊鏈的電子投票系統關鍵技術的實現[J]. 軟件， 2018， 39（11）： 140-144.

[3] 焦英楠， 陳英華. 基于區塊鏈技術的物聯網安全研究[J]. 軟件， 2018， 39（02）： 88-92.

[4] 潘吉飛， 黃德才. 區塊鏈技術對人工智能的影響[J]. 計算機科學， 2018， 45（S2）： 53-57+70.

[5] Gencer A E， Basu S， Eyal I， et al. Decentralization in Bitcoin and Ethereum Networks[C]//International Conference on Financial Cryptography and Data Security， 2018.

[6] Y. Gilad， R. Hemo， S. Micali， ， et al. Algorand： Scaling byzantine agreements for cryptocurrencies//[C] SOSP. Shanghai， China： ACM， 2017.

[7] Larimer D. Delegated proof-of-stake （dpos）. Bitshare Whitepaper. 2014.

[8] Thompson K. Reflections on trusting trust[C]// Communications of the ACM. 2012： 761-763.

[9] Eyal I， Sirer E G. Majority Is Not Enough： Bitcoin Mining Is Vulnerable[M]//Financial Cryptography and Data Security. Springer Berlin Heidelberg， 2014.

[10] 李靜彧， 李兆森. 基于區塊鏈存證的電子數據真實性探討[J]. 軟件， 2018， 39（06）： 109-112.