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

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

中圖分類號(hào)： G354.4 ? ?文獻(xiàn)標(biāo)識(shí)碼： A ? ?DOI：10.3969/j.issn.1003-6970.2019.04.048

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

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

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

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

2 ?常用共識(shí)算法

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

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

2.2 ?股權(quán)證明（Proof of Stake）

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

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

2.3 ?股權(quán)授權(quán)證明算法（Delegated Proof of stake）

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

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

2.4 ?實(shí)用拜占庭容錯(cuò)算法（Practical Byzantine Fault Tolerance）

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

3 ?共識(shí)算法比較

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

4 ?結(jié)語

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

參考文獻(xiàn)

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

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

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

[4] 潘吉飛， 黃德才. 區(qū)塊鏈技術(shù)對(duì)人工智能的影響[J]. 計(jì)算機(jī)科學(xué)， 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ù)真實(shí)性探討[J]. 軟件， 2018， 39（06）： 109-112.