區(qū)塊鏈共識(shí)算法的比較研究

宋燾誼 趙運(yùn)磊

1(復(fù)旦大學(xué)軟件學(xué)院 上海 201203)2(復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院 上海 200433)

0 引 言

去中心化加密數(shù)字貨幣被證明是一種成功的應(yīng)用模式，應(yīng)用的使用者同時(shí)可以成為這個(gè)應(yīng)用的維護(hù)者，卻沒(méi)有一家機(jī)構(gòu)或者個(gè)人可以擁有絕對(duì)的管理權(quán)限，這給軟件開(kāi)發(fā)帶來(lái)了全新的思路。區(qū)塊鏈的去中心化結(jié)構(gòu)[1]、數(shù)據(jù)公開(kāi)透明、不可篡改的特性，吸引了各國(guó)政府和企業(yè)巨頭還有創(chuàng)業(yè)公司的關(guān)注，已經(jīng)成為研究和資本的熱點(diǎn)。比特幣作為第一個(gè)加密貨幣，目前總市值已經(jīng)超過(guò)千億美元，單幣價(jià)格于2017年末一度超過(guò)19 900美元。其他加密貨幣也逐漸顯現(xiàn)其各自的特色，并具備一定規(guī)模的市場(chǎng)價(jià)值。至今金融安全、合約設(shè)計(jì)、信用征集、數(shù)據(jù)保護(hù)等領(lǐng)域紛紛布局區(qū)塊鏈。

工作量證明機(jī)制(POW)為代表的共識(shí)算法的提出，是比特幣這類加密貨幣能夠去中心化的根本原因，也是區(qū)塊鏈系統(tǒng)的底層核心技術(shù)。本文比較了公有鏈和許可鏈的共識(shí)算法，比如POW、POS、DPOS和PBFT，提出了區(qū)塊鏈共識(shí)算法的特點(diǎn)和限制，總結(jié)了區(qū)塊鏈的一些安全原則，比較了不同協(xié)議的可信度。最后，提出了未來(lái)共識(shí)算法的發(fā)展方向。

1 區(qū)塊鏈模型

隨著加密貨幣尤其是比特幣以太幣的交易價(jià)格的不斷攀升，區(qū)塊鏈技術(shù)的研究和應(yīng)用也愈來(lái)愈被學(xué)術(shù)界和資本市場(chǎng)的認(rèn)可。各界對(duì)加密貨幣以及區(qū)塊鏈的研究熱情高漲，并發(fā)展了很多研究方向[4]。區(qū)塊鏈去中心化結(jié)構(gòu)、數(shù)據(jù)公開(kāi)透明、不可篡改的特性，吸引了各國(guó)政府和企業(yè)巨頭還有創(chuàng)業(yè)公司的關(guān)注，已經(jīng)成為研究和資本的熱點(diǎn)。

由于特殊的數(shù)據(jù)結(jié)構(gòu)和共識(shí)方式，區(qū)塊鏈才能夠具備去中心化共同維護(hù)和防篡改的能力。在不同的應(yīng)用場(chǎng)景下，對(duì)區(qū)塊鏈的需求也不一致，安全性、吞吐量、去中心化的能力之間會(huì)有權(quán)衡。區(qū)塊鏈本身也有不同類別適應(yīng)于不同場(chǎng)景條件。

1.1 區(qū)塊鏈的定義與結(jié)構(gòu)

區(qū)塊鏈?zhǔn)窃诟鱾€(gè)節(jié)點(diǎn)互不信任的情況下，建立的一個(gè)可靠系統(tǒng)。從其功能上來(lái)說(shuō)，它為用戶提供了可靠的數(shù)據(jù)，從內(nèi)容上來(lái)說(shuō)，其數(shù)據(jù)在每個(gè)節(jié)點(diǎn)都有副本，可以將其視為分布式數(shù)據(jù)庫(kù)，這個(gè)數(shù)據(jù)庫(kù)只允許通過(guò)添加的方式修改和插入數(shù)據(jù)，不允許刪除的操作。

同一條區(qū)塊鏈的各個(gè)節(jié)點(diǎn)使用密碼學(xué)相關(guān)協(xié)議，在允許存在一定比例的惡意節(jié)點(diǎn)的情況下，共同維護(hù)鏈上數(shù)據(jù)。因此，區(qū)塊鏈作為一個(gè)值得系統(tǒng)節(jié)點(diǎn)信賴的數(shù)據(jù)庫(kù)，來(lái)實(shí)現(xiàn)數(shù)據(jù)的查詢和服務(wù)的提供。由于智能合約[7]的出現(xiàn)，許多區(qū)塊鏈可以自定義代碼，執(zhí)行特定的功能，這使得區(qū)塊鏈除了可以作為比特幣這類數(shù)字貨幣系統(tǒng)，還能夠承擔(dān)更多的功能。

我們以比特幣為例介紹區(qū)塊鏈的結(jié)構(gòu)，在區(qū)塊鏈系統(tǒng)中，每位用戶有自己的公鑰地址和私鑰。區(qū)塊鏈?zhǔn)怯梢粋€(gè)個(gè)區(qū)塊構(gòu)成的鏈狀數(shù)據(jù)結(jié)構(gòu)。每個(gè)區(qū)塊的結(jié)構(gòu)如圖1所示。每個(gè)區(qū)塊的結(jié)構(gòu)中包含了上一個(gè)區(qū)塊的哈希值，從而形成鏈狀結(jié)構(gòu)。交易記錄以Merkle Tree的形式組織起來(lái)。

圖1 常見(jiàn)的區(qū)塊鏈結(jié)構(gòu)

1.2 區(qū)塊鏈分類

通常來(lái)講，區(qū)塊鏈可以分為兩大類：公有鏈和許可鏈，其中許可鏈可以分為私有鏈和聯(lián)盟鏈。

公有鏈(Public blockchain)是指任何人都可以隨時(shí)加入成為鏈用戶并參與共識(shí)過(guò)程，并且有權(quán)利在支付交易費(fèi)的情況下，向區(qū)塊鏈添加交易。公有鏈中，節(jié)點(diǎn)可以自由出入?yún)^(qū)塊鏈網(wǎng)絡(luò)，可以依照規(guī)則參與共識(shí)過(guò)程。第一個(gè)區(qū)塊鏈應(yīng)用比特幣就屬于公有鏈，隨后出現(xiàn)的，以太幣、萊特幣等公眾能夠買到的數(shù)字貨幣大多也屬于公有鏈。共有鏈?zhǔn)钦嬲饬x上去中心化應(yīng)用，密碼學(xué)保證了區(qū)塊鏈的安全性，共識(shí)協(xié)議保證了不會(huì)有一個(gè)節(jié)點(diǎn)或者組織長(zhǎng)時(shí)間占據(jù)管理出塊的權(quán)限。

許可鏈(Permissioned blockchain)則與公有鏈不同，許可鏈一般是由某個(gè)實(shí)體或聯(lián)盟所運(yùn)營(yíng)，每條區(qū)塊鏈由特定成員或者利益相關(guān)的機(jī)構(gòu)管理，區(qū)塊鏈的使用也有著特定的業(yè)務(wù)環(huán)境。目前許多機(jī)構(gòu)在許可鏈的開(kāi)發(fā)成果頗豐，創(chuàng)業(yè)公司Tendermint開(kāi)發(fā)了拜占庭容錯(cuò)的區(qū)塊鏈應(yīng)用平臺(tái)；IBM的HyperLedger Fabric項(xiàng)目，幫助企業(yè)構(gòu)建區(qū)塊鏈服務(wù)；R3 Corda鏈接了42家銀行金融機(jī)構(gòu)共同研究，致力于開(kāi)發(fā)金融場(chǎng)景下的區(qū)塊鏈。具體來(lái)講許可鏈可以有下面兩個(gè)細(xì)分：

私有鏈(Private blockchain)由單一的個(gè)人或企業(yè)運(yùn)營(yíng)，通常是對(duì)該組織內(nèi)部數(shù)據(jù)庫(kù)的管理和審查，公眾一般不參與區(qū)塊鏈的維護(hù)，甚至沒(méi)有權(quán)限發(fā)布交易。

聯(lián)盟鏈(Consortium bockchain)由不同的實(shí)體來(lái)加入?yún)^(qū)塊鏈，通常需要對(duì)各方的共享數(shù)據(jù)類型進(jìn)行限定，鏈上內(nèi)容不會(huì)完全公開(kāi)透明。目前已經(jīng)有很多程序員和創(chuàng)業(yè)公司根據(jù)自己的構(gòu)想來(lái)建立不同的區(qū)塊鏈協(xié)議。致力于區(qū)塊鏈的金融應(yīng)用的區(qū)塊鏈聯(lián)盟R3就是其中之一，該公司已經(jīng)籌得1.07億美元的融資，并且吸引了42家銀行巨頭的參與。

加入許可鏈需要授權(quán)，節(jié)點(diǎn)不能隨意注冊(cè)與退出，甚至整條鏈被單一機(jī)構(gòu)所控制，因此許可鏈中心化程度比較高。目前分布式服務(wù)器已經(jīng)很成熟，像阿里云、騰訊云可以提供計(jì)算資源，企業(yè)可以租用這些不同地域的服務(wù)器來(lái)提供穩(wěn)定高吞吐量的服務(wù)，區(qū)塊鏈提供的服務(wù)相比于這類云服務(wù)器提供的服務(wù)有什么區(qū)別呢？

即便是在同一機(jī)構(gòu)中，信任也不是絕對(duì)的。一個(gè)機(jī)構(gòu)中各個(gè)網(wǎng)點(diǎn)，甚至每個(gè)成員都有可能對(duì)數(shù)據(jù)產(chǎn)生威脅，比如因?yàn)殂y行票據(jù)和理財(cái)資金導(dǎo)致的金融犯罪就層出不窮，違規(guī)套取和非法挪用金額動(dòng)輒上億甚至數(shù)十億，給投資人和銀行造成極大損失。傳統(tǒng)方法下，我們只能通過(guò)權(quán)限管理[8]，保證敏感數(shù)據(jù)修改權(quán)限只在高級(jí)管理人員手中。數(shù)據(jù)修改需要實(shí)行申請(qǐng)審批制度。這不單單增加了管理人員的勞動(dòng)量，一旦系統(tǒng)出現(xiàn)漏洞或者權(quán)限賬號(hào)發(fā)生泄漏等情況，損失會(huì)很嚴(yán)重。

區(qū)塊鏈上的數(shù)據(jù)不可刪除，對(duì)于賬戶的交易記錄在鏈上可以追溯，所有用戶的交易都需要被其他人見(jiàn)證并記錄，這無(wú)疑解決了機(jī)構(gòu)內(nèi)部的信任危機(jī)。

2 分布式系統(tǒng)與共識(shí)

1982年，Lamport首次提出拜占庭問(wèn)題[2]，描述了在互不信任的網(wǎng)絡(luò)中，通信各方達(dá)成共識(shí)的困難性。這個(gè)問(wèn)題是這樣的，多名將軍率領(lǐng)各自的軍隊(duì)共同圍困一座城市，對(duì)于每位將軍，有撤退和進(jìn)攻兩種行動(dòng)方案。將軍們必須在撤退或者進(jìn)攻的問(wèn)題上達(dá)成一致，這樣才能協(xié)心打敗敵人或者最大限度避免傷亡。由于城市地域?qū)拸V，不同將軍位于城市的不同的方向，因此各個(gè)將軍之間只能通過(guò)信使傳遞信件來(lái)溝通。在決策之前，所有將軍會(huì)將自己的投票通過(guò)信使傳遞給其他所有將軍，然后每位將軍通過(guò)自己的意見(jiàn)和其他將軍的投票，來(lái)做出最后的行動(dòng)決定。

問(wèn)題的困難性在于，將軍中有一部分人是叛徒，他們可以發(fā)送干擾性的消息，比如故意發(fā)不同的意見(jiàn)給不同的將軍，或者偽造其他將軍的信件，這樣整個(gè)軍隊(duì)的一致性就會(huì)遭到破壞。

在有叛徒的情況下，將軍們?nèi)绾尾皇芘淹降奶魮苓_(dá)成一致的方案就是需要討論的問(wèn)題。因此，拜占庭將軍問(wèn)題是要解決在一個(gè)可以允許部分比例惡意行為的系統(tǒng)中，達(dá)成共識(shí)的問(wèn)題。

該模型可以被引申為一般的分布式系統(tǒng)一致性問(wèn)題。在分布式計(jì)算機(jī)系統(tǒng)中，位于互聯(lián)網(wǎng)終端的計(jì)算機(jī)可以類比為各個(gè)將軍，互聯(lián)網(wǎng)類比為將軍們的信使，叛徒類比為惡意的計(jì)算機(jī)節(jié)點(diǎn)和通信錯(cuò)誤，互聯(lián)網(wǎng)終端計(jì)算機(jī)的數(shù)據(jù)一致性就是將軍們想要達(dá)到的一致性決策。在沒(méi)有可信的中心節(jié)點(diǎn)的情況下，共識(shí)是難以達(dá)到的。

我們把節(jié)點(diǎn)的消息發(fā)生延時(shí)、丟失、重復(fù)錯(cuò)誤稱為非拜占庭錯(cuò)誤(non-Byzantine fault)，在僅有非拜占庭錯(cuò)誤的情況下，想要保證系統(tǒng)的一致性相對(duì)比較簡(jiǎn)單。然而，如果系統(tǒng)中一個(gè)節(jié)點(diǎn)發(fā)生了拜占庭錯(cuò)誤(Byzantine fault)[2]，那這個(gè)節(jié)點(diǎn)就有惡意破壞這個(gè)分布式系統(tǒng)的能力，比如選擇性不響應(yīng)其他節(jié)點(diǎn)的請(qǐng)求，選擇性對(duì)不同的節(jié)點(diǎn)發(fā)送不同的消息，或者聯(lián)合其他發(fā)生拜占庭錯(cuò)誤的節(jié)點(diǎn)一起破壞這個(gè)分布式系統(tǒng)。總之，節(jié)點(diǎn)能夠發(fā)生最壞的情況就是拜占庭錯(cuò)誤。如果一個(gè)共識(shí)算法可以容納系統(tǒng)中有f個(gè)節(jié)點(diǎn)發(fā)生拜占庭錯(cuò)誤，那么f個(gè)節(jié)點(diǎn)在任何錯(cuò)誤下，共識(shí)算法都可以保證這個(gè)分布式系統(tǒng)的一致性。

3 共識(shí)的安全性分析

對(duì)于分布式系統(tǒng)來(lái)說(shuō)，共識(shí)模型一般會(huì)對(duì)環(huán)境做一些假設(shè)，不同的算法能夠容忍的錯(cuò)誤類型和錯(cuò)誤數(shù)量也是不同的。區(qū)塊鏈本身實(shí)質(zhì)上也是一個(gè)分布式系統(tǒng)，我們可以由分布式系統(tǒng)共識(shí)的評(píng)判標(biāo)準(zhǔn)引申為區(qū)塊鏈的安全性定義。

3.1 時(shí)間模型

Fischer等[9]介紹了FLP不可能性結(jié)果。當(dāng)我們不考慮設(shè)置消息延時(shí)的上界時(shí)，拜占庭將軍問(wèn)題不可解，即沒(méi)有一個(gè)算法可以在甄別網(wǎng)絡(luò)擁塞導(dǎo)致消息延時(shí)與服務(wù)器宕機(jī)的前提下，給出有效的共識(shí)算法。

那么實(shí)際應(yīng)用中分布式算法，又是從何而來(lái)？實(shí)際上，有三類關(guān)于算法的時(shí)間模型，這三種模型出現(xiàn)在不同的分布式算法的假設(shè)中，通常來(lái)說(shuō)，區(qū)塊鏈的共識(shí)模型一般采取第三種時(shí)間假設(shè)[3]。

(1) 同步模型 在同步模型中，消息由發(fā)送方到接收方的延遲時(shí)間Δt是確定的，算法執(zhí)行時(shí)間也是確定的。然而，同步模型過(guò)于理想，在現(xiàn)實(shí)世界中基本不會(huì)存在，在分布式系統(tǒng)中使用這樣的假設(shè)，如果算法被實(shí)際應(yīng)用，那么正確性將完全無(wú)法保證。從另一個(gè)角度想，如果在同步模型的假設(shè)下，依然沒(méi)有算法可以解決某個(gè)問(wèn)題，那么在異步模型下，失去了可以預(yù)測(cè)的時(shí)間，這個(gè)問(wèn)題更加沒(méi)辦法解決。

(2) 異步模型 異步模型中，消息的延時(shí)Δt不確定，可以是任意長(zhǎng)的時(shí)間。在異步模型下，程序的執(zhí)行可能因?yàn)榈却⒌牡竭_(dá)而始終保持阻塞，因而算法的執(zhí)行時(shí)間非常不確定。同樣，使用這類假設(shè)的算法，無(wú)法判斷節(jié)點(diǎn)消息是由于延時(shí)未到達(dá)，還是節(jié)點(diǎn)已經(jīng)失效無(wú)法做出回應(yīng)。這類算法通?？梢员ＷC程序的安全性，但是無(wú)法保證系統(tǒng)的活性。

(3) 半同步/半異步模型 為了尋求同時(shí)具備安全性和活性的算法，時(shí)間模型上我們往往使用半同步/半異步模型。在這個(gè)模型中，對(duì)于消息和計(jì)算會(huì)設(shè)置一個(gè)最長(zhǎng)超時(shí)限制tmax，如果超過(guò)tmax，消息接收方依然無(wú)法收到消息或者依然沒(méi)有得到結(jié)果，那么我們就假設(shè)這個(gè)節(jié)點(diǎn)已經(jīng)失效，我們將不再等待和處理這個(gè)節(jié)點(diǎn)的消息。

3.2 分布式系統(tǒng)的安全模型

在Lamport提出的分布式系統(tǒng)安全模型[11]中，可靠的分布式系統(tǒng)的定義是：系統(tǒng)在不超過(guò)f個(gè)節(jié)點(diǎn)發(fā)生錯(cuò)誤(拜占庭/非拜占庭錯(cuò)誤)的條件下，對(duì)于每一個(gè)請(qǐng)求，分布式系統(tǒng)可以保證有安全性(Safety)和活性(Liveness)。

安全性：程序永遠(yuǎn)不會(huì)產(chǎn)生一個(gè)壞的結(jié)果，即對(duì)于請(qǐng)求，分布式系統(tǒng)給出的回復(fù)是正確的且無(wú)需更改。

活性：程序最終將會(huì)產(chǎn)生一個(gè)好的結(jié)果，即在有限的時(shí)間t內(nèi)，分布式系統(tǒng)會(huì)對(duì)請(qǐng)求做出回復(fù)。

從參與分布式系統(tǒng)的每個(gè)節(jié)點(diǎn)(將軍)，來(lái)判斷這個(gè)系統(tǒng)的算法的有效性，可以從以下三個(gè)標(biāo)準(zhǔn)來(lái)具體評(píng)判：

(1) 可終止性：所有誠(chéng)實(shí)的節(jié)點(diǎn)都會(huì)最終產(chǎn)生一個(gè)結(jié)果。

(2) 合法性：如果誠(chéng)實(shí)的節(jié)點(diǎn)最終的結(jié)果是d，那么d一定是由某個(gè)(些)節(jié)點(diǎn)提議的。

(3) 一致性：所有誠(chéng)實(shí)的節(jié)點(diǎn)決定的結(jié)果是相同的。

如果一個(gè)算法能夠保證可終止性、合法性和一致性，那么就可以稱這個(gè)算法可以解決共識(shí)問(wèn)題。

然而，現(xiàn)實(shí)中通信過(guò)程無(wú)法達(dá)到同步，每個(gè)節(jié)點(diǎn)也無(wú)法保證永遠(yuǎn)在線，當(dāng)一個(gè)可以失效或者節(jié)點(diǎn)所處網(wǎng)絡(luò)擁塞時(shí)，我們需要考慮異步或者宕機(jī)。

3.3 區(qū)塊鏈安全性定義

類比于分布式系統(tǒng)對(duì)于安全性和活性的定義，我們對(duì)于以區(qū)塊鏈為形式的系統(tǒng)，若滿足以下兩個(gè)性質(zhì)，那我們說(shuō)，這個(gè)系統(tǒng)可以正常運(yùn)行。

安全性：存在一個(gè)k∈N，如果所有誠(chéng)實(shí)的節(jié)點(diǎn)都認(rèn)同區(qū)塊Bi距離鏈末端有k個(gè)區(qū)塊及以上的距離，我們能夠稱這個(gè)塊Bi中的交易可信，我們稱這些交易是穩(wěn)定的。

活性：存在一個(gè)最長(zhǎng)等待時(shí)間t和k∈N，使得一筆誠(chéng)實(shí)且有著合理交易費(fèi)的交易tx，在時(shí)間t后，可以滿足安全性定義中交易穩(wěn)定的狀態(tài)。

4 區(qū)塊鏈共識(shí)算法

區(qū)塊鏈?zhǔn)欠植际较到y(tǒng)的一種，對(duì)于中心化不同程度的區(qū)塊鏈，我們需要不同策略來(lái)實(shí)現(xiàn)容錯(cuò)的共識(shí)算法[10，12]，從而保障賬本的安全。

4.1 公有鏈共識(shí)算法

公有鏈?zhǔn)侨ブ行幕姆植际郊軜?gòu)，節(jié)點(diǎn)的注冊(cè)和退出比較頻繁，節(jié)點(diǎn)數(shù)量一直在變化，節(jié)點(diǎn)在線比例也會(huì)不同。在這樣的情況下一般使用證明機(jī)制來(lái)實(shí)現(xiàn)共識(shí)。

4.1.1 工作量證明機(jī)制POW

目前的數(shù)字貨幣大多使用工作量證明機(jī)制來(lái)進(jìn)行維護(hù)賬本。工作量證明機(jī)制是由Nakamoto匿名提出，將其用來(lái)作為比特幣系統(tǒng)的共識(shí)機(jī)制，其主要思想是使用計(jì)算能力尋找特定的數(shù)字來(lái)使區(qū)塊滿足要求。

系統(tǒng)中有激勵(lì)措施鼓勵(lì)用戶通過(guò)維護(hù)區(qū)塊鏈系統(tǒng)來(lái)獲取利益。參與共識(shí)過(guò)程的用戶收集新產(chǎn)生的交易記錄構(gòu)造區(qū)塊，嘗試修改區(qū)塊中Nonce的值，直到該區(qū)塊的哈希值小于特定難度的哈希值，便可以對(duì)外廣播區(qū)塊。該區(qū)塊得到其他用戶驗(yàn)證和認(rèn)可，成功添加到主鏈之后，用戶就可以獲得相應(yīng)的獎(jiǎng)勵(lì)。

在這里我們將一個(gè)區(qū)塊表示為包含三元組的數(shù)據(jù)包B=h′,txs,nonce，其中h′ 是前一個(gè)區(qū)塊的哈希，txs是區(qū)塊中所包含的交易記錄，nonce是一個(gè)32比特的整數(shù)。為了達(dá)到共識(shí)，系統(tǒng)將節(jié)點(diǎn)構(gòu)造區(qū)塊等價(jià)為解一個(gè)困難問(wèn)題，設(shè)定一個(gè)難度值D。D定義了當(dāng)前整個(gè)區(qū)塊哈希值需要有多少位前導(dǎo)0，前導(dǎo)0數(shù)量越多，難度越大。由于nonce改變?nèi)我庖粋€(gè)比特都會(huì)使整個(gè)區(qū)塊的哈希H(B)完全改變，所以沒(méi)有方法可以預(yù)測(cè)哪種形式的nonce可以符合要求。因此為了達(dá)到區(qū)塊的要求，節(jié)點(diǎn)需要用其計(jì)算資源嘗試大量可能的nonce值使得H(B)

算法1pow證明機(jī)制

Input:preHash,txs,D

Output:Block

1:nonce←1

2:while(H(nonce,txs,preHash)>=D):

3: nonce←nonce+1

4:Broadcast()

5:end

如果大多數(shù)計(jì)算資源被誠(chéng)實(shí)節(jié)點(diǎn)所控制，那么比特幣賬本將會(huì)正常維護(hù)。

共識(shí)算法嵌入數(shù)字貨幣系統(tǒng)的流程如下：

1) 新的交易廣播給全網(wǎng)礦工。

2) 每位礦工收集交易記錄，構(gòu)造新的Merkle樹(shù)。

3) 礦工利用計(jì)算資源來(lái)尋找滿足當(dāng)前難度值的nonce。

4) 礦工找到可行的nonce解，將區(qū)塊廣播給全網(wǎng)。

5) 其他礦工驗(yàn)證該區(qū)塊。

6) 如果這個(gè)區(qū)塊中交易記錄有效，區(qū)塊哈希符合難度值要求，并且該區(qū)塊是所有分叉中最長(zhǎng)的區(qū)塊，那么其他誠(chéng)實(shí)節(jié)點(diǎn)將會(huì)在這個(gè)區(qū)塊后構(gòu)造下一個(gè)區(qū)塊。

比特幣網(wǎng)絡(luò)中，如果一個(gè)節(jié)點(diǎn)希望為賬本添加區(qū)塊，它將會(huì)收集并驗(yàn)證當(dāng)前的交易信息，構(gòu)造一個(gè)合法的區(qū)塊。比特幣是一個(gè)開(kāi)放的系統(tǒng)，比特幣的區(qū)塊鏈實(shí)質(zhì)上是一份記錄著轉(zhuǎn)賬記錄的賬本，任何擁有哈希計(jì)算能力的人都可以參與到維護(hù)賬本中來(lái)并有機(jī)會(huì)獲取獎(jiǎng)勵(lì)，這樣的特點(diǎn)吸引了眾多算力加入到賬本維護(hù)中。節(jié)點(diǎn)通過(guò)算力爭(zhēng)取記賬權(quán)的過(guò)程稱為挖礦，參與挖礦的節(jié)點(diǎn)稱為礦工。

工作量證明機(jī)制通過(guò)比拼哈希算力來(lái)爭(zhēng)取出塊的權(quán)利，這造成了大量專門為哈希計(jì)算優(yōu)化的挖礦硬件和電力資源的消耗，使用POW作為共識(shí)算法的區(qū)塊鏈都面臨這樣的問(wèn)題，比特幣總市值很高，但維護(hù)這樣一個(gè)去中心化應(yīng)用同樣花費(fèi)巨大。能否有更廉價(jià)的方式來(lái)維持類似去中心化協(xié)議健康運(yùn)作同時(shí)又不失安全性和活性，這成為很多人研究的問(wèn)題。

4.1.2 股權(quán)證明機(jī)制POS

由于區(qū)塊鏈的特殊的數(shù)據(jù)結(jié)構(gòu)，區(qū)塊鏈的共識(shí)過(guò)程可以視為一種領(lǐng)導(dǎo)人選舉機(jī)制，通過(guò)固定機(jī)制隨機(jī)挑選領(lǐng)導(dǎo)人(記賬礦工)，由這個(gè)人發(fā)布新的塊，避免由單個(gè)用戶或者集團(tuán)長(zhǎng)期控制賬本。然而隨著區(qū)塊鏈的發(fā)展，我們可以看到工作量證明機(jī)制有著種種問(wèn)題。首先，比特幣網(wǎng)絡(luò)電力消耗巨大，有些礦場(chǎng)甚至建在水電站旁邊以節(jié)省資源，很多場(chǎng)景中不需要區(qū)塊鏈進(jìn)行價(jià)值錨定。其次，這樣的機(jī)制安全性并不像想象中的那么高，比如自私挖礦(selfish mining)[13]策略，可以不需要全網(wǎng)51%的算力就有概率成功控制區(qū)塊鏈。

正是由于工作量證明機(jī)制的不足，股權(quán)證明機(jī)制(Proof of Stake)應(yīng)運(yùn)而生。股權(quán)證明希望使用股權(quán)(Stake)來(lái)代替或者部分代替計(jì)算資源來(lái)完成這個(gè)領(lǐng)導(dǎo)人選舉的過(guò)程。股權(quán)證明機(jī)制經(jīng)歷了很多變化，很多數(shù)字貨幣都自稱采用了基于股權(quán)證明的共識(shí)算法。這些算法有很多變種，但是可以總結(jié)出一些共同的特點(diǎn)。

在股權(quán)證明機(jī)制的過(guò)程中，共識(shí)算法根據(jù)參與共識(shí)過(guò)程每個(gè)人所持有股權(quán)比例來(lái)選擇下一個(gè)出塊的人。這一思想也來(lái)源于經(jīng)濟(jì)社會(huì)，一個(gè)人擁有股份數(shù)量越多，其獲得的股息和分紅就會(huì)越高，如果區(qū)塊鏈也能夠按照這樣的形式來(lái)維護(hù)，不需要額外的資源消耗，同時(shí)還可以使得區(qū)塊鏈資產(chǎn)有著自然的通脹。這聽(tīng)起來(lái)很理想，有著類似實(shí)體貨幣的屬性。然而真正設(shè)計(jì)區(qū)塊鏈股權(quán)證明機(jī)制的時(shí)候，卻遠(yuǎn)沒(méi)有那么簡(jiǎn)單，從技術(shù)實(shí)現(xiàn)，協(xié)議安全和資產(chǎn)安全等方面，需要考慮很多。

目前，有Peercoin、NTX、Blackcoin使用了基于POS思想的共識(shí)算法，以太坊未來(lái)也有向POS共識(shí)算法轉(zhuǎn)型的規(guī)劃。

采用POS共識(shí)協(xié)議的Peercoin和Blackcoin使用幣齡作為一個(gè)變量來(lái)影響參與挖礦的哈希難度。我們將共識(shí)算法簡(jiǎn)單歸約為算法2。共識(shí)過(guò)程中，節(jié)點(diǎn)需要提交一份交易記錄來(lái)證明對(duì)區(qū)塊鏈資產(chǎn)的擁有權(quán)，同時(shí)擁有的區(qū)塊鏈資產(chǎn)越多，持有時(shí)間越長(zhǎng)，挖礦就會(huì)越容易。股權(quán)證明算法希望用戶可以自己向自己進(jìn)行一筆轉(zhuǎn)賬，來(lái)證明所擁有的一定數(shù)量的區(qū)塊鏈資產(chǎn)，這些資產(chǎn)可以影響區(qū)塊鏈礦工挖礦的難度，擁有越多的資產(chǎn)，就越有機(jī)會(huì)計(jì)算出符合條件的nonce。因此我們要解決的哈希難題變?yōu)椋?/p>

算法2Peercoin證明機(jī)制算法

Input:preHash,txs,D,

accountBalance,lashTransactionTime

Output:Block

1:nonce←1

2:coins←accountBalance

3:age←currentTime-lashTransactionTime

4:while(H(nonce,txs,preHash)>=coins·age·D):

5: nonce←nonce+1

6:Broadcast()

7:end

雖然POS算法能夠從一定程度上緩解POW帶來(lái)的計(jì)算資源的競(jìng)爭(zhēng)，但其仍舊存在問(wèn)題。比如某個(gè)用戶擁有大量的區(qū)塊鏈資產(chǎn)，或者長(zhǎng)時(shí)間持有，甚至從ICO開(kāi)始就持有區(qū)塊鏈資產(chǎn)，這樣就可以造成嚴(yán)重的貧富不均，對(duì)于網(wǎng)絡(luò)中新加入的節(jié)點(diǎn)也不友好。另外，pos也沒(méi)有完全脫離比拼計(jì)算資源的怪圈，這樣的算法依然會(huì)消耗很多計(jì)算資源。而且會(huì)加劇礦池巨頭壟斷出塊權(quán)利的情況。

4.1.3 股權(quán)授權(quán)證明算法(DPOS)

DPOS是去中心化交易所Bitshares提出并使用的共識(shí)算法。Bitshares允許三類人進(jìn)行投票參與共識(shí)過(guò)程：見(jiàn)證人(witnesses)，代表(delegates)和工人(workers)。見(jiàn)證人通過(guò)處理交易和維護(hù)區(qū)塊鏈來(lái)獲得報(bào)酬。代表不會(huì)獲得報(bào)酬但是他可以發(fā)起更新Bitshare的請(qǐng)求。工人可以提出他們希望做的項(xiàng)目，如果這個(gè)項(xiàng)目被投票支持，那么他們可以從中獲得報(bào)酬。

DPOS的共識(shí)過(guò)程分為見(jiàn)證人的選舉過(guò)程和見(jiàn)證人出塊兩個(gè)過(guò)程。見(jiàn)證人只負(fù)責(zé)對(duì)于交易進(jìn)行見(jiàn)證，驗(yàn)證交易的簽名和時(shí)間戳，并不參與交易，網(wǎng)絡(luò)中每個(gè)賬戶都可以為自己的見(jiàn)證人投票，擁有的區(qū)塊鏈資產(chǎn)越多，票數(shù)也就越多。

1) 見(jiàn)證人選舉 具有被選舉權(quán)的永久節(jié)點(diǎn)接受投票，最終會(huì)有前N名見(jiàn)證人被選出來(lái)。N名見(jiàn)證人所獲得的票數(shù)必須獲得超過(guò)50%的投票。見(jiàn)證人名單按照固定的時(shí)間間隔(一天)輪換。

2) 見(jiàn)證人出塊 見(jiàn)證人每生產(chǎn)一個(gè)塊，都會(huì)獲得報(bào)酬，他們的薪酬水平由其獲得的投票決定。如果見(jiàn)證人沒(méi)有生產(chǎn)區(qū)塊，他們便沒(méi)有收入，并且還有可能被投票失去見(jiàn)證人的身份。

見(jiàn)證人生產(chǎn)區(qū)塊時(shí)，每2 s生產(chǎn)一個(gè)區(qū)塊，如果見(jiàn)證人沒(méi)有在規(guī)定的時(shí)間生產(chǎn)塊，那么這個(gè)見(jiàn)證人將會(huì)被跳過(guò)，下一個(gè)見(jiàn)證人來(lái)生產(chǎn)區(qū)塊。

與比特幣網(wǎng)絡(luò)相同，區(qū)塊鏈的分叉通過(guò)選擇最長(zhǎng)鏈來(lái)解決。網(wǎng)絡(luò)中所有用戶都可以通過(guò)觀察見(jiàn)證人的行為來(lái)監(jiān)測(cè)區(qū)塊鏈的維護(hù)過(guò)程，如果見(jiàn)證人的在線率比較低，將會(huì)影響其下一次被當(dāng)選。

不過(guò)授權(quán)證明過(guò)程并沒(méi)有那么完美，由于循環(huán)出塊，出塊人的身份早已知道，更容易造成合謀攻擊。相比于前兩個(gè)共識(shí)算法，DPOS算法中心化程度更強(qiáng)。

4.2 許可鏈共識(shí)算法

相比之下，Tendermint和Fabric更希望將區(qū)塊鏈做成一類服務(wù)平臺(tái)來(lái)幫助企業(yè)或者機(jī)構(gòu)搭建區(qū)塊鏈應(yīng)用。它們對(duì)底層共識(shí)協(xié)議做了改進(jìn)，可以不依靠計(jì)算資源來(lái)實(shí)現(xiàn)共識(shí)。它們提供PBFT作為共識(shí)算法[5]，并力求將共識(shí)算法做成可插拔式，其身份驗(yàn)證選擇也更多樣化，支持智能合約，主要面向企業(yè)搭建區(qū)塊鏈應(yīng)用。和以太坊不一樣的是，其每個(gè)參與共識(shí)的節(jié)點(diǎn)的加入退出都是需要權(quán)限授予的，并不是對(duì)所有人開(kāi)放，這使得節(jié)點(diǎn)的共識(shí)主要由服務(wù)企業(yè)內(nèi)部掌控，從而對(duì)外提供服務(wù)。但是正是由于這一特點(diǎn)，這樣構(gòu)造的區(qū)塊鏈沒(méi)有價(jià)值錨定，不需要考慮運(yùn)營(yíng)區(qū)塊鏈應(yīng)用需要花費(fèi)多少數(shù)字貨幣，只需要專注于分布式應(yīng)用的開(kāi)發(fā)。

由于許可鏈應(yīng)用場(chǎng)景多種多樣，所以這些聯(lián)盟鏈的共識(shí)算法顯得更為復(fù)雜一些，甚至平臺(tái)會(huì)為不同需求的企業(yè)選擇不同的底層共識(shí)協(xié)議。Tendermint可以利用智能合約將共識(shí)算法和股權(quán)掛鉤，Tendermint構(gòu)造的區(qū)塊鏈數(shù)字貨幣賦予價(jià)值之后，Tendermint可以使用內(nèi)置貨幣參與共識(shí)，節(jié)點(diǎn)向保證金賬戶轉(zhuǎn)入相應(yīng)的保證金，如果節(jié)點(diǎn)正常參與共識(shí)協(xié)議，那么節(jié)點(diǎn)就會(huì)獲得獎(jiǎng)勵(lì)，如果節(jié)點(diǎn)有惡意行為，那么其保證金就會(huì)被扣除。同時(shí)Tendermint可以直接使用PBFT算法來(lái)處理拜占庭錯(cuò)誤的節(jié)點(diǎn)。

Hyperledger Fabric在上層提供docker來(lái)處理不同的數(shù)據(jù)，數(shù)據(jù)的權(quán)限可以為不同的用戶組所設(shè)計(jì)，有些數(shù)據(jù)可以公開(kāi)，有些數(shù)據(jù)可以保持僅特定用戶組可見(jiàn)。

4.2.1 拜占庭容錯(cuò)算法(PBFT)

PBFT共識(shí)的分布式系統(tǒng)中，節(jié)點(diǎn)有主節(jié)點(diǎn)和副節(jié)點(diǎn)，假設(shè)我們用集合R來(lái)表示分布式系統(tǒng)中的節(jié)點(diǎn)，那我們?yōu)槊總€(gè)節(jié)點(diǎn)編號(hào){0,…，|R|-1}，我們有p=vmodR，假設(shè)|R|=3f+1，其中f是發(fā)生錯(cuò)誤的節(jié)點(diǎn)的最大數(shù)目，只要節(jié)點(diǎn)數(shù)不少于3f+1，拜占庭容錯(cuò)算法都可以正常運(yùn)行。節(jié)點(diǎn)當(dāng)前的主副節(jié)點(diǎn)劃分成為view，在view中，有一個(gè)節(jié)點(diǎn)是主節(jié)點(diǎn)p，其他的節(jié)點(diǎn)為副節(jié)點(diǎn)。在主節(jié)點(diǎn)發(fā)生錯(cuò)誤，以及每處理一個(gè)客戶端請(qǐng)求后，view都會(huì)進(jìn)行改變，view是連續(xù)遞增的，所有節(jié)點(diǎn)都有可能被選為主節(jié)點(diǎn)，即p=vmod|R|，view的存在是借鑒了Paxos的思想，可以避免宕機(jī)錯(cuò)誤。

主節(jié)點(diǎn)接收和轉(zhuǎn)發(fā)客戶端的請(qǐng)求，所有節(jié)點(diǎn)均可與客戶端進(jìn)行連接。每個(gè)節(jié)點(diǎn)都有自己的狀態(tài)，包括服務(wù)狀態(tài)，已經(jīng)收到的消息日志和一個(gè)表示當(dāng)前view的標(biāo)號(hào)的整數(shù)。

整個(gè)算法大致按照以下的流程來(lái)進(jìn)行操作，一個(gè)分布式系統(tǒng)中有3f+1個(gè)節(jié)點(diǎn)，可以容忍f個(gè)拜占庭錯(cuò)誤的節(jié)點(diǎn)。

1) 客戶端向主節(jié)點(diǎn)請(qǐng)求調(diào)用服務(wù)。

2) 主節(jié)點(diǎn)多播請(qǐng)求到副節(jié)點(diǎn)。

3) 副節(jié)點(diǎn)執(zhí)行請(qǐng)求，發(fā)送回復(fù)給客戶端。

4) 客戶端接收到f+1個(gè)帶有相同答案的回復(fù)，客戶端得到請(qǐng)求的數(shù)據(jù)。

拜占庭容錯(cuò)算法達(dá)成共識(shí)包括三個(gè)階段：pre-prepare、prepare和commit。

當(dāng)一個(gè)主節(jié)點(diǎn)p收到客戶端請(qǐng)求m，那它就自動(dòng)開(kāi)始向它的副節(jié)點(diǎn)多播這個(gè)請(qǐng)求。

pre-prepare和prepare的存在可以給相同view的請(qǐng)求排序，規(guī)范了請(qǐng)求的執(zhí)行順序，prepare和commit的存在可以為跨view請(qǐng)求排序。

在沒(méi)有錯(cuò)誤節(jié)點(diǎn)的情況下，算法的執(zhí)行如圖2所示，Primary是主節(jié)點(diǎn)，副節(jié)點(diǎn)Replica共有三個(gè)，Client是客戶端。

圖2 PBFT 共識(shí)過(guò)程

除了節(jié)點(diǎn)數(shù)量固定，對(duì)于一個(gè)請(qǐng)求，有n個(gè)節(jié)點(diǎn)的分布式系統(tǒng)，消息數(shù)量級(jí)別是O(n2)，這在節(jié)點(diǎn)數(shù)量很多的情況下是低效糟糕的通信，在共識(shí)數(shù)量有限的許可鏈中，使用PBFT尚能提供高吞吐量的服務(wù)，如果節(jié)點(diǎn)數(shù)量增加，提供服務(wù)的質(zhì)量反而會(huì)下降，這在cosmos(使用Tendermint框架的一個(gè)分布式賬本系統(tǒng))的測(cè)試數(shù)據(jù)中也有所體現(xiàn)[6]。

4.2.2 Paxos 和Raft算法

在有些行業(yè)鏈中，采用了Lamport提出的Paxos算法或者使用其變種Raft算法來(lái)作為共識(shí)協(xié)議。在節(jié)點(diǎn)沒(méi)有拜占庭錯(cuò)誤的情況下，使用這些算法確實(shí)具有優(yōu)勢(shì)，在很多分布式系統(tǒng)中也獲得應(yīng)用，Google的Chubby、Megastore、Spanner等一系列產(chǎn)品都基于Paxos協(xié)議來(lái)確保一致性。

Paxos使用了兩階段提交的模型，提案-批準(zhǔn)制的思想也在后面很多共識(shí)算法中使用，Paxos中有三個(gè)角色proposer，acceptor和learner，proposer提出一個(gè)值，希望更新?tīng)顟B(tài)，acceptor對(duì)提案請(qǐng)求批準(zhǔn)，多輪交互使得系統(tǒng)中寫(xiě)入的消息內(nèi)容和順序保持一致，learner相當(dāng)于存儲(chǔ)機(jī)器，獲取最終批準(zhǔn)的提案并且更新，不參與投票的過(guò)程。

Paxos和Raft都是利用狀態(tài)機(jī)復(fù)制來(lái)實(shí)現(xiàn)容錯(cuò)，為多個(gè)副本提供統(tǒng)一的數(shù)據(jù)更新順序。由于這些協(xié)議基本不具備對(duì)惡意節(jié)點(diǎn)的防御能力，我們?cè)谶@里不作具體介紹。

5 區(qū)塊鏈共識(shí)算法比較

我們對(duì)區(qū)塊鏈共有鏈和許可鏈的共識(shí)算法進(jìn)行了比較，從資源消耗、中心化程度、吞吐量、交易確認(rèn)時(shí)間來(lái)比較各個(gè)算法的優(yōu)缺點(diǎn)，見(jiàn)表1。同時(shí)，我們?cè)诒?中比較了現(xiàn)行采用不同共識(shí)算法的密碼貨幣的市場(chǎng)價(jià)值，這可以從側(cè)面反映出資本市場(chǎng)對(duì)共識(shí)算法的認(rèn)可程度。最后我們?cè)诒?中對(duì)許可鏈常見(jiàn)共識(shí)協(xié)議下的容錯(cuò)能力給出了定量的描述，對(duì)于無(wú)法抵抗該錯(cuò)誤的用“-”表示。

表1 共識(shí)算法比較

表2 區(qū)塊鏈?zhǔn)兄当容^(2018年3月10日)

表3 許可鏈容錯(cuò)情況比較

6 結(jié) 語(yǔ)

本文對(duì)現(xiàn)行的區(qū)塊鏈流行的共識(shí)算法進(jìn)行了總結(jié)，分別從共有鏈和許可鏈兩個(gè)方面來(lái)具體描述其不同的需求和條件。公有鏈闡述了POW、POS和DPOS三種共識(shí)算法的內(nèi)部實(shí)現(xiàn)。對(duì)于許可鏈，我們主要描述了BPFT算法的步驟和細(xì)節(jié)。

新的共識(shí)算法的開(kāi)發(fā)需要兼顧不同場(chǎng)景的需要，并進(jìn)行縝密的安全性論證。區(qū)塊鏈的共識(shí)算法的公開(kāi)評(píng)審是必要的，現(xiàn)行區(qū)塊鏈的共識(shí)算法大多也是以這種方式推進(jìn)，通過(guò)專家提案，公開(kāi)討論，協(xié)議實(shí)現(xiàn)，協(xié)議補(bǔ)充的步驟來(lái)把區(qū)塊鏈共識(shí)協(xié)議一步步改進(jìn)。目前對(duì)于POW-POS混合共識(shí)機(jī)制是研究的熱點(diǎn)方向，利用智能合約構(gòu)建更為透明的共識(shí)規(guī)則也是一個(gè)新方向。共識(shí)算法投入實(shí)踐應(yīng)用也是對(duì)算法的一種檢驗(yàn)，新的攻擊方法可以使我們了解現(xiàn)有共識(shí)算法的不足之處。

另外，對(duì)于許可鏈上的共識(shí)算法，可插拔可切換的方式是一種趨勢(shì)。對(duì)于不同的商業(yè)場(chǎng)景、吞吐量需求和安全假設(shè)，我們可以采用對(duì)應(yīng)不同的底層共識(shí)機(jī)制，從而更好地為頂層應(yīng)用服務(wù)。