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

關鍵詞： 區(qū)塊鏈;分布式系統(tǒng);共識算法;拜占庭協(xié)議;PoW;PoS

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

本文著錄格式：陳玎樂. 區(qū)塊鏈共識算法的比較研究[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 ?引言

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

1 ?主流區(qū)塊鏈共識算法

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

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

2 ?常用共識算法

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

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

2.2 ?股權證明（Proof of Stake）

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

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

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

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

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

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

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

3 ?共識算法比較

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

4 ?結語

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

參考文獻

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

[2] 黨京， 孫弋. 基于區(qū)塊鏈的電子投票系統(tǒng)關鍵技術的實現(xiàn)[J]. 軟件， 2018， 39（11）： 140-144.

[3] 焦英楠， 陳英華. 基于區(qū)塊鏈技術的物聯(lián)網(wǎng)安全研究[J]. 軟件， 2018， 39（02）： 88-92.

[4] 潘吉飛， 黃德才. 區(qū)塊鏈技術對人工智能的影響[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] 李靜彧， 李兆森. 基于區(qū)塊鏈存證的電子數(shù)據(jù)真實性探討[J]. 軟件， 2018， 39（06）： 109-112.