段希楠，延志偉，耿光剛，閻保平

1. 中國科學(xué)院計算機(jī)網(wǎng)絡(luò)信息中心，北京 100190

2. 中國科學(xué)院大學(xué)，北京 100049

3. 中國互聯(lián)網(wǎng)絡(luò)信息中心，北京 100190

引言

區(qū)塊鏈 (Blockchain) 技術(shù)由于其具有去中心化、自治性、防篡改性、完備可追溯等特點，近些年受到了廣泛的關(guān)注。區(qū)塊鏈建立在分布式網(wǎng)絡(luò)上，維護(hù)系統(tǒng)的節(jié)點將一段時間內(nèi)的數(shù)據(jù)整合打包為一個區(qū)塊，后生成的區(qū)塊包含之前區(qū)塊的哈希信息，以保證區(qū)塊間可形成連貫的鏈條。區(qū)塊鏈本質(zhì)上是一種數(shù)據(jù)存儲技術(shù)，最初它實現(xiàn)于比特幣[1]中負(fù)責(zé)保存所有的交易記錄。比特幣的初衷是實現(xiàn)一個無需中心權(quán)威機(jī)構(gòu)的、去中心化的電子現(xiàn)金系統(tǒng)。在沒有第三方擔(dān)保的條件下，數(shù)字貨幣面臨著兩大問題——拜占庭問題[2]和雙花[3]，即參與節(jié)點如何構(gòu)造統(tǒng)一的賬本，以及如何保證一筆資金不被同時用于多個交易。問題的實質(zhì)，就是在沒有中心權(quán)威機(jī)構(gòu)的環(huán)境中，如何保證節(jié)點對同一份數(shù)據(jù)的認(rèn)可。

為實現(xiàn)公平、安全、可靠的分布式系統(tǒng)，區(qū)塊鏈引入了 P2P 網(wǎng)絡(luò)、密碼學(xué)、共識算法、梅克爾樹[4]等多個元素。所以嚴(yán)格意義上說，區(qū)塊鏈并不是一種全新的技術(shù)，而是多種已有成熟技術(shù)的巧妙整合。比如其中的共識算法，作為區(qū)塊鏈中解決一致性問題的關(guān)鍵，它最初誕生于分布式系統(tǒng)中，經(jīng)過多年的研究探索，共識已經(jīng)演變出多種體系。如何選用合適的算法使系統(tǒng)達(dá)到相對最優(yōu)的性能，是在設(shè)計區(qū)塊鏈中必不可少的環(huán)節(jié)。本文旨在介紹幾種具有代表性的共識算法，并分析其各自特點以及在區(qū)塊鏈中的應(yīng)用情況。

1 共識的目的及拜占庭問題

在分布式系統(tǒng)中，每個終端都可看做是一個獨立的、有自治性的節(jié)點。不同節(jié)點都各自維護(hù)著一條內(nèi)容相同的數(shù)據(jù)鏈，同時也獨立地將網(wǎng)絡(luò)中新產(chǎn)生的數(shù)據(jù)打包為一個區(qū)塊，廣播給其他節(jié)點。由于區(qū)塊鏈?zhǔn)蔷€性的，同一周期內(nèi)各節(jié)點打包的區(qū)塊內(nèi)容雖不盡相同，但最終只能有一個區(qū)塊加入到主鏈中，以保證數(shù)據(jù)的一致性，因此如何選擇區(qū)塊是區(qū)塊鏈共識的重要任務(wù)之一。在這個過程中，如果將主鏈視為賬本，共識算法所做的就是決定將哪個節(jié)點整理的賬目寫入總賬，即如何分配記賬權(quán)。

區(qū)塊鏈系統(tǒng)中，多節(jié)點協(xié)同處理事務(wù)時會常常遇到各種問題。比如，不同節(jié)點接收信息有時間先后，信息在傳輸過程中可能丟失，節(jié)點間使用系統(tǒng)有差異，節(jié)點本身也會發(fā)生故障……除這些非人為因素外，系統(tǒng)實際運行時，節(jié)點間的通訊信息也可能受到人為的惡意干預(yù)，即經(jīng)典的拜占庭將軍問題。此問題最初由 Leslie Lamport 于 1982 年提出，具體指在有少數(shù)作惡節(jié)點存在，消息可能會被偽造或篡改的情況下，如何讓誠實節(jié)點仍能保持行動的一致。

Leslie Lamport 證明，在作惡節(jié)點占比不超過 1/3的情況下，存在有效的算法使得誠實節(jié)點始終保持一致[6]。此類算法也可稱為拜占庭容錯 (Byzantine Fault Tolerant，BFT) 算法。對應(yīng)的，在只考慮節(jié)點崩潰或者網(wǎng)絡(luò)不暢等問題的非拜占庭場景下，也存在容忍值：1/2。即有半數(shù)以上節(jié)點發(fā)出同樣的“提案”時，才能使得系統(tǒng)達(dá)成一致。

2 主流區(qū)塊鏈共識算法及對比

2.1 工作量證明機(jī)制與挖礦

工作量證明機(jī)制 (ProofofWork, PoW)[7]，最初在HashCash[8]中用于垃圾郵件的過濾。之后中本聰于2008 年，創(chuàng)新性的采用此算法來實現(xiàn)比特幣中節(jié)點數(shù)據(jù)的一致性。作為一個去中心化的虛擬現(xiàn)金系統(tǒng)，比特幣首要解決的就是如何記賬，以及在沒有第三方權(quán)威機(jī)構(gòu)監(jiān)管的情況下，怎樣保證記錄的公平性、正確性問題。由于比特幣底層使用的是公有鏈，任何參與到系統(tǒng)中的用戶都可充當(dāng)一個節(jié)點，并且節(jié)點間權(quán)利對等，皆可公平地享有數(shù)據(jù)并發(fā)送信息。在此情況下，如果每個節(jié)點都可任意提案，并且采取少數(shù)服從多數(shù)的方式達(dá)成共識，那么難免會有不法分子控制“僵尸網(wǎng)絡(luò)”，制造大量節(jié)點加入到系統(tǒng)中，這樣他就能夠以占多數(shù)的提案權(quán)來決定系統(tǒng)的走向，也就是所謂的女巫攻擊 (Sybil Attack)[9]。

工作量證明機(jī)制是抵御上述攻擊的一種有效手段。所謂工作就是指節(jié)點需要花費自己的算力資源來進(jìn)行“挖礦”，先完成“挖礦”任務(wù)的節(jié)點可以將此工作量的證明連同記賬信息 (也就是整理好的區(qū)塊) 一起廣播給其他節(jié)點。其它節(jié)點接收到此消息后，會首先驗證工作的有效性，如果有效且記賬信息也驗證無誤，該節(jié)點就將此區(qū)塊加入本地維護(hù)的鏈中，并著手下一輪的算力競賽。如驗證失敗，則丟棄此信息，并繼續(xù)當(dāng)輪的“挖礦”工作[5]。

考慮到系統(tǒng)的性能，“挖礦”過程應(yīng)具有工作量可以被度量并且結(jié)果易于驗證的特點。因此 PoW 采用哈希運算的方式：對于特定輸入，哈希的結(jié)果每次都一樣，任何人都可以復(fù)現(xiàn)并驗證；反之，要生成一個特定的哈希值，只能不斷變化輸入而無法直接做出選擇。比特幣的工作量證明就是對當(dāng)前區(qū)塊的頭部數(shù)據(jù)做雙重哈希運算，具體算式如下：

SHA256 (SHA256(nVersion + hashPrevBlock +hashMerkleRoot + nTime + nBits + nNonce)) ＜ Target

各參數(shù)的含義為

nVersion：版本號，記錄版本信息

hashPrevBlock：父區(qū)塊哈希

hashMerkleRoot：當(dāng)前區(qū)塊所包含交易的梅克爾根

nTime：時間戳

nBits：當(dāng)前的挖礦難度

nNonce：隨機(jī)值

Target：目標(biāo)值，可以由難度值計算出

其中，前五個參數(shù)基本固定，“挖礦”所做工作就是不斷嘗試新的隨機(jī)值，一旦找到使哈希結(jié)果小于目標(biāo)值的隨機(jī)數(shù)，他就相當(dāng)于競爭到記賬權(quán)，可以將自己的區(qū)塊廣播給他人進(jìn)行驗證接收。

PoW 其本身的算法并不復(fù)雜，但它更為精妙的地方在于與激勵措施、難度調(diào)整等要素的結(jié)合。由于節(jié)點只有主動花費自己的資源用于工作量證明，新的數(shù)據(jù)才能夠加入到區(qū)塊鏈中，保證系統(tǒng)的正常運轉(zhuǎn)。為鼓勵更多的節(jié)點加入到系統(tǒng)維護(hù)中，共識算法因此引入了“挖礦”的激勵措施。比特幣 PoW 中激勵來源主要有兩種，其一是產(chǎn)生交易時，發(fā)起方需額外支付一筆手續(xù)費，供“礦工”將交易打包入?yún)^(qū)塊后獲得；另外就是每次系統(tǒng)加入新的區(qū)塊時，生成此區(qū)塊的節(jié)點還會有一定數(shù)目的比特幣獎勵，最初是50 枚，每隔 210000 個區(qū)塊后 (大約四年時間) 收益減半，如今為 12.5 枚。隨區(qū)塊而誕生的幣，是比特幣系統(tǒng)在去中心的情況下，唯一發(fā)行貨幣的方式。預(yù)計到2140 年，全部的 2100 萬枚比特幣將會產(chǎn)出完畢[10]。

激勵措施會不斷吸引節(jié)點加入系統(tǒng)中，同時也導(dǎo)致全網(wǎng)算力提高，若“挖礦”難度保持不變，區(qū)塊的生成速度將越來越快。難度調(diào)整機(jī)制就是為避免此類情況的發(fā)生。為了使區(qū)塊的生成速度維持在大約十分鐘一個，比特幣系統(tǒng)每生成2016個區(qū)塊后都會調(diào)整一次難度，調(diào)整函數(shù)為：

新難度=實際生成 2016 塊的時間×舊難度/ 14 天的秒數(shù)

難度的增大使“挖礦”的成本也逐漸增加，同時發(fā)幣的速度保持不變，這就導(dǎo)致了區(qū)塊鏈數(shù)字貨幣價值的上漲。而幣價上漲又不斷吸引著用戶通過“挖礦”獲利，節(jié)點數(shù)量上升也增強(qiáng)了系統(tǒng)的安全性，減少被 51% 攻擊[11]的可能，防范了雙花。綜上，算法中各種附加機(jī)制相輔相成，促進(jìn)了區(qū)塊鏈整體系統(tǒng)的平穩(wěn)運行。

2.2 權(quán)益證明機(jī)制

比特幣在 PoW 中引入激勵等機(jī)制，為之后區(qū)塊鏈共識算法的設(shè)計研究奠定了基礎(chǔ)。然而它的弊端在于，隨著“挖礦”難度的提高，消耗的資源也越來越大，并且用如此高的算力所計算的內(nèi)容，從科學(xué)角度上講幾乎沒有價值。鑒于此，權(quán)益證明 (Proof of Stake，PoS) 應(yīng)運而生。

PoS 最先由 Sunny King 的點點幣 (Peercoin)[12]實現(xiàn)，后來蘋果幣 (Applecoin V2 (v1 用的是 PoW))、未來幣 (Nextcoin)、黑幣 (Blackcoin) 等多個應(yīng)用都做了不同的改進(jìn)。PoS 延續(xù)了 PoW 中的競爭打包區(qū)塊權(quán)的理念，不同之處在于 PoS 中是根據(jù)用戶持有的系統(tǒng)代幣來決定打包出塊的概率。

以 Peercoin 為例，決定記賬權(quán)的唯一要素是幣齡。開啟“挖礦”模式后，幣齡就可以累積。錢包中的每枚代幣每天都可產(chǎn)生 1 幣齡。“礦工”用于“挖礦”的總幣齡越高，獲得收益的概率也就越大。舉例來說，用戶甲有 1000 枚代幣，持有 50 天，那么他的幣齡就為 5 萬。當(dāng)他用這一千枚代幣競爭到記賬權(quán)后，幣齡也會一同清空。Peercoin 的獎勵機(jī)制也同幣齡相關(guān)，它的利息 (或可理解為年利率) 為 1%，即每清空 365 幣齡，用戶會獲得 0.01 枚的代幣。

公有鏈的安全性非常依賴于其維護(hù)節(jié)點的數(shù)量，由于 Peercoin 的幣齡具有無需接入系統(tǒng)也可累積的特點，有的用戶會在大多數(shù)時間選擇離線狀態(tài)，待幣齡積攢到一定程度時才連線挖礦。久而久之，隨著節(jié)點的減少，系統(tǒng)被攻擊的風(fēng)險會不斷增高。因此在之后Blackcoin 實現(xiàn)的 PoS 共識中，不再沿用幣齡這一設(shè)計，取而代之的是權(quán)重[13]，節(jié)點只有盡可能多的維持在線狀態(tài)，才能進(jìn)行權(quán)重累積，而權(quán)重又是執(zhí)行權(quán)益證明的關(guān)鍵。這就鼓勵了節(jié)點保持活躍，從而提高系統(tǒng)的穩(wěn)定安全。

鑒于 PoW 會造成資源浪費、并且有礦池占據(jù)全網(wǎng)大部分算力等缺陷，以太坊團(tuán)隊近些年也在積極開發(fā)一種名為 Casper[14]的 PoS 共識機(jī)制。以往的“挖礦”和區(qū)塊驗證工作都由“礦工”來完成，而 Casper試圖將這兩種職能分離，將“挖礦”過程虛擬化，并使驗證人替代“礦工”。擁有以太幣的用戶可以用自己的貨幣作為驗證金，當(dāng)他們發(fā)現(xiàn)新的區(qū)塊時就可以用這筆資金進(jìn)行驗證并押注。如果該區(qū)塊被成功收錄于主鏈中，對應(yīng)的驗證人可以獲得本金以及額外的收益。除此之外，Casper 還加入了“懲罰機(jī)制”，如果有驗證人同時押注多個區(qū)塊或惡意押注不合格區(qū)塊，那么他們的保證金也會被沒收。為獲取收益，節(jié)點最好的選擇就是押注人數(shù)最多的、最合格的區(qū)塊，這就促使了網(wǎng)絡(luò)整體能夠更快的達(dá)成一致。

與 PoW 這種具體算法相比，PoS 更確切的是一個方向，多個衍生算法各具特色，甚至相互在實現(xiàn)上差異很大。但有一點共性是，這些算法都與系統(tǒng)代幣密切相關(guān)。將代幣類比為股權(quán)的話，擁有的股權(quán)越多，權(quán)益和責(zé)任也就越大，因此 PoS 被稱為權(quán)益證明機(jī)制，或股權(quán)證明機(jī)制。

2.3 股權(quán)授權(quán)機(jī)制

隨著“挖礦”節(jié)點的不斷增加，網(wǎng)絡(luò)結(jié)構(gòu)日趨復(fù)雜，系統(tǒng)完成共識的成本也會不斷升高。另外，由于PoW 共識中收益取決于算力的高低，這使得部分用戶只著眼于如何通過多種途徑來提高算力，卻不在意區(qū)塊鏈系統(tǒng)本身的生態(tài)與維護(hù)。雖然后來出現(xiàn)了改進(jìn)的算法，設(shè)定了內(nèi)存難解等策略來對抗 ASIC 礦機(jī)。但這種補(bǔ)丁方式無法從根本上解決算力與股權(quán)間的矛盾。

為了增強(qiáng)系統(tǒng)效率，同時保證持股人權(quán)利，Dan Larimer 設(shè)計了股權(quán)授權(quán)證明機(jī)制 (Delegated Proof of Stake，DPoS)[15]，并在其比特股 (BitShares)[16]項目中首次實現(xiàn)。該算法也被之后的億書 (Ebookchain)、柚子 (Enterprise Operation System, Eos)、公信寶(GXChain)、阿希 (ASCH) 等項目采用。

在創(chuàng)立比特股時，Dan 提出了一個概念——DAC (去中心化自治公司)。正如一家公司，每個持有貨幣的人都相當(dāng)于掌握著部分股權(quán)，用戶可以用自己的股權(quán)來參與公司的管理。首先，DPoS 中的區(qū)塊只由小部分的可信賬戶生成，這些賬戶被稱為見證人(Witnesses)，由選舉產(chǎn)生。每個持股人都可投票給其他用戶，票數(shù)中前 N (通常為 101) 的候選者就可當(dāng)選為見證人。見證人的候選名單每個維護(hù)周期 (1 天) 會更改一次。選舉完成后，見證人隨機(jī)排列，每人有 2秒的時間輪流獲得記賬權(quán)。若在規(guī)定時間內(nèi)未能生成區(qū)塊，權(quán)限仍會交給下一名見證人。任何人都可實時監(jiān)測見證人的狀況，如果某人被發(fā)現(xiàn)打包率過低或是有作惡行為，該見證人就會失去公信，再競選成功難度提高。

除見證人外，比特股還加入了對代表的競選。選出的代表擁有提出更改網(wǎng)絡(luò)參數(shù)的權(quán)利，如：交易費用、區(qū)塊大小、見證人費用以及區(qū)塊間隔。若大多數(shù)代表都同意某項提案，持股人會得到兩周的審查期決定是否罷免代表并撤除所提議的改變。這一設(shè)計確保了代表無法直接對參數(shù)進(jìn)行修改，并且所有的更改都是經(jīng)過持股人同意的。

可以說，DPoS 算法使持股人的股權(quán)得以更充分的使用，使共識過程變的更加民主。但由于投票的多少與用戶持股的占比有關(guān)，DPoS 增加了少數(shù)大股東的話語權(quán)。

2.4 綜合對比

不難發(fā)現(xiàn)，區(qū)塊鏈的分布式網(wǎng)絡(luò)也是拜占庭環(huán)境，難免會有作惡節(jié)點的存在。傳統(tǒng)的拜占庭共識算法都有作惡節(jié)點不能超過總結(jié)點數(shù) 1/3 的限制，否則系統(tǒng)可能無法達(dá)成一致。而在區(qū)塊鏈中，通常所說的安全隱患是 51% 攻擊而非 33%。之所以能將攻擊成本提高，是由于從區(qū)塊鏈采用的第一個共識算法 PoW開始，就引入了競爭挖礦和分叉處理的機(jī)制。首先，競爭挖礦相當(dāng)于為區(qū)塊的生成設(shè)立了門檻，節(jié)點需要利用自身資源達(dá)成一定條件后才能夠發(fā)送有效數(shù)據(jù)。這樣在一個共識周期中，新誕生的區(qū)塊數(shù)量會遠(yuǎn)遠(yuǎn)小于節(jié)點的規(guī)模，因此降低了達(dá)成共識的難度。如果一個有效區(qū)塊已產(chǎn)生，并在網(wǎng)絡(luò)傳播的過程中，某處節(jié)點也挖掘出了有效區(qū)塊，這兩個區(qū)塊很可能會在原來鏈的基礎(chǔ)上，形成不同的分叉。區(qū)塊鏈系統(tǒng)允許在一段時間內(nèi)有數(shù)據(jù)不一致的情況出現(xiàn)，并設(shè)置了相應(yīng)的分叉處理。當(dāng)節(jié)點收到新的區(qū)塊但發(fā)現(xiàn)無法加入到自身維護(hù)的鏈中時，它會將節(jié)點所在的鏈與自身存儲的鏈進(jìn)行對比，然后將全部數(shù)據(jù)更新為較長鏈。PoW 中，鏈的長度是指各區(qū)塊中難度的累加和，而在以 Peercoin 為代表的 PoS 中，長度指的是幣齡的累加之和。

從攻擊者角度而言，攻擊的思路不應(yīng)是如何讓系統(tǒng)無法達(dá)成一致，而是要利用系統(tǒng)的一致性處理，用新數(shù)據(jù)覆蓋舊數(shù)據(jù)，以造成貨幣的雙花。從表 1 中，可看出三種共識的安全威脅各不相同。在 PoW 中，如果某組織長期持有 50% 以上的全網(wǎng)算力，那他們產(chǎn)生區(qū)塊的速度會快于其他節(jié)點，就有可能用他們偽造的鏈來替代正常鏈。而在 PoS 中要達(dá)到同樣的效果，攻擊者就需要掌握參與當(dāng)前網(wǎng)絡(luò)競爭的 50% 以上的貨幣。這樣無論共識采用幣齡還是其它的一些方式，攻擊者總能以足夠高的股權(quán)來影響區(qū)塊內(nèi)容。PoS 把威脅來源從 PoW 共識的外部算力，轉(zhuǎn)到了系統(tǒng)內(nèi)部的貨幣中，一方面使用戶擁有越多代幣就越傾向于維護(hù)系統(tǒng)的安全穩(wěn)定，但另一方面在實際運行中，最活躍的節(jié)點可能是少部分股東一直維持的。DPoS 中將股權(quán)和挖礦權(quán)做了一定分離，增加了系統(tǒng)的公平性。但其先競選后挖礦的流程，注定了被選中節(jié)點產(chǎn)生作弊行為時，只能被動應(yīng)對而無法提前預(yù)防，這也為系統(tǒng)帶來了新的安全隱患。

從性能上講，對系統(tǒng)的評價指標(biāo)有出塊速度和每秒交易處理數(shù) (TransactionsPerSecond，TPS)。比特幣的 PoW 規(guī)定是平均 10 min 出一個塊，之所以設(shè)置這么長的時間，中本聰認(rèn)為這對一個支付系統(tǒng)已經(jīng)足夠。而目前看來，比特幣設(shè)立的十分鐘以及 1M 大小區(qū)塊的限制似乎已經(jīng)難以應(yīng)付如今的需求，解決方案一方面是發(fā)明了隔離證明、閃電網(wǎng)絡(luò)等技術(shù)，另一方面在后續(xù)的大多系統(tǒng)中也都調(diào)整了出塊間隔時間，如零幣 (Zcash) 的間隔時間減少為 2.5 min，以太坊 PoW的間隔就達(dá)到大約 15 s。PoS 由于計算量較少，理論上出塊速度應(yīng)該能比 PoW 快。目前 PoS 主流項目很少，黑幣的間隔 64 s，未來幣的是 60 s。一般來說，這個速度與網(wǎng)絡(luò)規(guī)模密切相關(guān)，以比特股為代表的DPoS，由于共識只在 101 個節(jié)點中進(jìn)行，所以它的出塊速度只有 3 s。

表1 三種共識算法對比Table 1 The comparison of three consensus

出塊速度體現(xiàn)著區(qū)塊鏈共識的完成速度，而 TPS則代表了系統(tǒng)的吞吐量。TPS 受區(qū)塊大小和區(qū)塊間隔的制約，目前性能較好的系統(tǒng)也只能達(dá)到幾千筆的量級，如何提高 TPS 已成為業(yè)內(nèi)共同的努力目標(biāo)之一。

3 其它共識算法

上述算法不僅可用于公有鏈，在聯(lián)盟鏈和私有鏈中也同樣有效，是目前被廣泛承認(rèn)和應(yīng)用的共識方式。而下面介紹的幾種算法雖知名度稍差，僅用于個別系統(tǒng)中，但本文認(rèn)為它們也同樣擁有良好的性能，設(shè)計思路非常值得研究和借鑒。

3.1 PBFT

PBFT (Practical Byzantine Fault Tolerance)[17]由Miguel Castro (卡斯特羅) 和 Barbara Liskov (利斯科夫)在1999年發(fā)表的論文中提出。相比于傳統(tǒng)的拜占庭容錯算法，PBFT 將復(fù)雜度由指數(shù)級降低到多項式級，不僅大大提高了效率，也使其成為第一個被廣泛使用的拜占庭共識算法。

PBFT 算法將節(jié)點分為兩種類型，其中有一個是主節(jié)點，負(fù)責(zé)將客戶端的請求排序，其余是備份節(jié)點，它們按照主節(jié)點提供的順序執(zhí)行請求。算法規(guī)定了三種基本協(xié)議：一致性協(xié)議 (agreement)，檢查點協(xié)議 (checkpoint)，視圖更換協(xié)議 (view change)。

一致性協(xié)議是確保來自客戶端的請求在每個服務(wù)器上都能按照固定的順序執(zhí)行。它至少包含發(fā)送請求(request)，序號分配 (pre-prepare) 和結(jié)果返回 (reply)三個階段。通常情況下，一個共識流程會在同個視圖下進(jìn)行。但當(dāng)主節(jié)點發(fā)生故障時，視圖更換協(xié)議會依序?qū)⒅鞴?jié)點用備份節(jié)點替換掉，并且保證已被正常節(jié)點執(zhí)行完畢的請求不被篡改。在共識過程中，節(jié)點會隨時記錄日志，如果日志得不到及時清理，會導(dǎo)致系統(tǒng)資源被無用信息占用，從而影響整體性能。同時，由于系統(tǒng)的異步性無法保證每一個節(jié)點都執(zhí)行了相同的請求，不同節(jié)點的狀態(tài)可能不一致。因此，檢查點協(xié)議會周期性的執(zhí)行，作用是處理日志和糾正節(jié)點狀態(tài)。

PBFT 最多容忍 33% 的拜占庭節(jié)點，但在性能上有著良好的表現(xiàn)。因此它一般適合于節(jié)點來源比較可靠的私有鏈或聯(lián)盟鏈場景。目前 IBM 的的 Fabric 項目中，PBFT 被做成可插拔的共識模塊供用戶選擇。

3.2 dBFT

dBFT (delegated Byzantine Fault Tolerance)[18]是國內(nèi)小蟻團(tuán)隊首創(chuàng)的一種改進(jìn)的拜占庭容錯算法，被用于其 NEO (原 AntShares) 項目中。該算法糅合改進(jìn)了 DPoS 中的選舉與 PBFT 中的共識流程，最多可容忍錯誤節(jié)點為 33%。dBFT 中節(jié)點分為兩大類，共識節(jié)點和普通節(jié)點，共識節(jié)點由 NEO 持有人選出，主要負(fù)責(zé)生成，普通節(jié)點只能夠發(fā)送交易。算法過程大致如下：確定議長-議長廣播提案-議員驗證提案并廣播-任意節(jié)點收到足夠多的確認(rèn)信息后即可廣播完整區(qū)塊-其它節(jié)點收到完整區(qū)塊后就接收并刪除已包含入?yún)^(qū)塊的交易。

3.3 瑞波共識

瑞波算法 (Ripple)[19]的出發(fā)點是想通過減少信息的確認(rèn)次數(shù)，來降低網(wǎng)絡(luò)節(jié)點間的溝通成本。它設(shè)定了一個小規(guī)模的、可以被高度信任的節(jié)點群體主要負(fù)責(zé)共識的達(dá)成，這些節(jié)點稱作驗證節(jié)點。所有節(jié)點都維護(hù)著一份驗證節(jié)點列表 (Unique Node List，UNL)，用于對投票信息的篩選。共識過程基本如下：

(1) 驗證節(jié)點會收到兩類信息：交易和候選集。接收的交易會被驗證，通過的將被匯總到交易候選集中。

(2) 每個驗證節(jié)點會周期性的把自己的候選集發(fā)送給其他節(jié)點。

(3) 驗證節(jié)點在收到其他節(jié)點發(fā)來的候選集后，會首先驗證發(fā)送節(jié)點是否在 UNL 中：若是，則將之與自身候選集中的交易一一進(jìn)行比對。如果有相同的交易，那么該交易獲得一票。

(4) 驗證節(jié)點把所有達(dá)到80%確認(rèn)的交易寫入本地數(shù)據(jù)庫，表示此交易已加入該節(jié)點維護(hù)的賬本中。

瑞波共識中實質(zhì)上舍棄了區(qū)塊的概念，每條交易都獨立存在。并且由于系統(tǒng)的異步性，一筆交易可能在多個節(jié)點中的確認(rèn)狀態(tài)都不一致，比如交易 1 在節(jié)點 a 中的確認(rèn)為 60%，而在 b 中已將近 80%。雖然這會導(dǎo)致各節(jié)點中存儲的數(shù)據(jù)內(nèi)容在同一時刻可能無法保證一致，但這不一致是暫時性的，長期看來節(jié)點數(shù)據(jù)會趨于相同。

由于交易達(dá)到 80% 以上的確認(rèn)后才被加入賬本，因此網(wǎng)絡(luò)中一旦有超過 20% 的惡意節(jié)點，瑞波算法就很可能無法完成共識，這也是該算法為何要求驗證節(jié)點具有高可信度的原因。但如果想對賬本數(shù)據(jù)產(chǎn)生影響，惡意節(jié)點也要達(dá)到 80% 才可能成功。

3.4 權(quán)威證明

PoA (Proof of Authority)[20]共識目前僅用于以太坊的Kovan測試網(wǎng)中，與瑞波的思路相似，PoA 也是一種利用高信任度來減少處理時延的算法。網(wǎng)絡(luò)中所有節(jié)點分為普通節(jié)點和小部分的權(quán)威節(jié)點，僅權(quán)威節(jié)點參與共識過程。權(quán)威節(jié)點在每輪共識周期中都保持著固定編號。打包區(qū)塊前，權(quán)威節(jié)點會先將區(qū)塊高度與共識節(jié)點數(shù)量取余，運算結(jié)果對應(yīng)的節(jié)點為主節(jié)點，其余為副節(jié)點。所有共識節(jié)點都可生成相同高度的區(qū)塊，但只有主節(jié)點的區(qū)塊具有被廣播并加入主鏈的優(yōu)先級。

具體實現(xiàn)時，以太坊希望既引入新的共識作為一個可選設(shè)定，又不影響原本 PoW 的使用。因此 PoA算法在區(qū)塊的數(shù)據(jù)結(jié)構(gòu)上沒有做任何更改，而是重用difficulty 字段來區(qū)分區(qū)塊是否由主節(jié)點打包：(1) 是副節(jié)點；(2) 是主節(jié)點。同時，nonce 字段也被重用，表示提議加入或刪除某個共識節(jié)點。

PoA 在測試網(wǎng)中的出塊間隔為 5 s，用于真實場景中最大的區(qū)別也僅是網(wǎng)絡(luò)傳輸速度的變化，預(yù)計仍能保持較好的性能。目前共識節(jié)點在收到區(qū)塊時只是檢查區(qū)塊頭中記錄的某些屬性，沒有對區(qū)塊內(nèi)容進(jìn)行驗證，說明共識節(jié)點間是高度信任的。因此 PoA 算法非常適合在聯(lián)盟鏈或私有鏈中使用。

4 總結(jié)與展望

近年來，隨著區(qū)塊鏈技術(shù)得到廣泛的關(guān)注，共識算法也被越來越多的人所學(xué)習(xí)和研究。作為區(qū)塊鏈的重要組成部分，共識算法體現(xiàn)著區(qū)塊鏈系統(tǒng)的性能與功能。目前，新的共識方式層出不窮，經(jīng)分析與總結(jié)，該技術(shù)呈現(xiàn)著如下幾個發(fā)展趨勢：

證明方式多樣化：早期的工作量證明、權(quán)益證明方式存在著資源浪費，節(jié)點積極性不高的問題。研究者們出于降低“挖礦”競爭的成本或是提高資源利用率、增加應(yīng)用場景等目的，開發(fā)出了時間證明 (Proof of Time)[21]、存儲證明 (Proof of Store)、存在證明 (Proof of Existence)[22]、貢獻(xiàn)證明 (Proof of Contribution) (以太霧使用)、有效流量證明 (Proof of Flow) (yoyow 使用)、品味證明 (Proof of Taste)(steemit 使用)、概念證明 (Proof of Concept)[23]、消逝時間量證明 (Proof of Elapsed Time) (超級賬本“鋸齒湖”使用) 等機(jī)制。新的證明方式仍會層出不窮，但在設(shè)計共識算法中，需要考慮的關(guān)鍵一點就是要做到挖礦權(quán)的足夠分散，增加攻擊者掌握大部分競爭力的難度，減少單個節(jié)點或組織改寫區(qū)塊鏈的可能。通過這樣，才能有效的防范雙花，保證系統(tǒng)的安全與穩(wěn)定。

證明方式混合化：PoW 的威脅來自擁有高算力的礦場，而 PoS 的安全隱患是活躍的大股東，此二者的共同特點都是決定挖礦權(quán)的算力或權(quán)益被少部分人所控制。為增加攻擊難度，研究者們提出是否可以嘗試將 PoW 與 PoS 混合，這樣如果想發(fā)動 51% 攻擊，惡意節(jié)點就需掌握大部分的算力和大部分的股權(quán)。這是一個相對難以達(dá)成的條件，如果真有人做到這點，那么整個區(qū)塊鏈系統(tǒng)也會因過高的中心化而失去價值。理論上混合模式具有獨特優(yōu)勢，但目前成熟項目不多。

中心化共識需求增多：公有鏈中，任何人都可加入并維護(hù)一個節(jié)點，公平享有全部的數(shù)據(jù)。但在涉及到企業(yè)或組織內(nèi)部信息的情況下，聯(lián)盟鏈或私有鏈無疑是更好的選擇。由于這兩種鏈中節(jié)點是聯(lián)盟成員或企業(yè)內(nèi)部提供，可信度有一定保證。因此在設(shè)計共識算法時，可以免去中間選舉、驗證或競爭挖礦權(quán)等過程。比如瑞波和 PoA 共識，它們雖然加入了選舉機(jī)制，但不作為必要流程，共識節(jié)點完全可以由組織內(nèi)部指定，節(jié)點間依據(jù)共同規(guī)則輪流生成區(qū)塊。這些算法具有一定的中心化程度，若用于公有鏈中，必然會因其不公平性而受到質(zhì)疑。但在不需要徹底去中心化的聯(lián)盟鏈中，由于簡化了共識流程，此類算法普遍會表現(xiàn)出優(yōu)于公有鏈算法的性能。隨著企業(yè)對聯(lián)盟鏈或私有鏈需求的增多，中心化的共識算法也會得到相應(yīng)的關(guān)注和發(fā)展。

研究合理的激勵措施：區(qū)塊鏈中往往會引入激勵機(jī)制來處理技術(shù)上的難題，比如公有鏈的安全依賴于大量節(jié)點的維護(hù)，于是加入激勵機(jī)制來調(diào)動用戶積極性；比如用于解決區(qū)塊鏈存儲問題的 IPFS[24]技術(shù)，也是結(jié)合勵機(jī)制來鼓勵用戶協(xié)助存儲數(shù)據(jù)碎片，才得以形成一個完整的項目 Filecoin。因此，如果能結(jié)合共識的具體過程，設(shè)計合理的激勵措施，在實際運行中往往會達(dá)到事半功倍的效果，對系統(tǒng)的安全與延續(xù)也會有積極作用。此外，研究者們對于聯(lián)盟鏈中是否需要內(nèi)部代幣一直存在爭論，本文認(rèn)為在一些信任度不完全的聯(lián)盟中，加入幣來實施獎懲功能是有必要的。而聯(lián)盟鏈中若采用有一定中心化的共識，節(jié)點間不設(shè)競爭而用設(shè)定的順序生成區(qū)塊。此種情況下，怎樣加入合理的激勵措施就變成了問題。通過大家的不斷探索，相信以后會有適合聯(lián)盟鏈激勵的解決方案。

[1]Nakamoto S. Bitcoin: A peer-to-peer electronic cash system[J]. 2008.

[2]Lamport L, Shostak R, Pease M. The Byzantine generals problem[J]. ACM Transactions on Programming Languages and Systems (TOPLAS), 1982, 4(3): 382-401.

[3]Chohan U W. The Double Spending Problem and Cryptocurrencies. SSRN[J]. 2017.

[4]Becker G. Merkle signature schemes, merkle trees and their cryptanalysis[J]. Ruhr-University Bochum, Tech.Rep, 2008.

[5]Clark J B A M J, Edward A N J A K, Felten W.Research Perspectives and Challenges for Bitcoin and Cryptocurrencies[J]. url: https://eprint. iacr. org/2015/261.pdf.

[6]Dolev D, Strong H R. Authenticated algorithms for Byzantine agreement[J]. SIAM Journal on Computing,1983, 12(4): 656-666.

[7]Gervais A, Karame G O, Wüst K, et al. On the security and performance of proof of work blockchains[C]//Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. ACM, 2016: 3-16.

[8]Back A. Hashcash-a denial of service counter-measure[J].2002.

[9]Sybil attack. https://en.wikipedia.org/wiki/Sybil_attack.

[10]Antonopoulos A. Mastering bitcoin.2015.

[11]Bastiaan M. Preventing the 51%-attack: a stochastic analysis of two phase proof of work in bitcoin[C]//Availab le at http://referaat. cs. utwente. nl/conference/22/paper/7473/preventingthe-51-attack-astochastic-analysisof-two-phase-proof-of-work-in-bitcoin. pdf. 2015.

[12]King S, Nadal S. Ppcoin: Peer-to-peer crypto-currency with proof-of-stake[J]. self-published paper, August, 2012, 19.

[13]Vasin P. Blackcoin’s proof-of-stake protocol v2[J].URL: https://blackcoin. co/blackcoin-pos-protocol-v2-whitepaper. pdf, 2014.

[14]Zamfir V. Introducing Casper ‘the Friendly Ghost’[J]. Ethereum Blog URL: https://blog. ethereum.org/2015/08/01/introducing-casper-friendly-ghost, 2015.

[15]Larimer D. Delegated proof-of-stake white paper[J]. 2014

[16]Schuh F, Larimer D. BitShares 2.0: Financial Smart Contract Platform[J]. 2015.

[17]Castro M, Liskov B. Practical Byzantine fault tolerance[C]//OSDI. 1999, 99: 173-186.

[18]NEO Whitepaper. URL:http://docs.neo.org/zh-cn/

[19]Rizzo P. Royal Bank of Canada Reveals Blockchain Trial With Ripple[J]. 2016.

[20]https://en.wikipedia.org/wiki/Proof-of-authority

[21]Chrono Logic Whitepaper. URL: https://chronologic.network/uploads/Chronologic_Whitepaper.pdf

[22]Crosby M, Pattanayak P, Verma S, et al. Blockchain technology: Beyond bitcoin[J]. Applied Innovation, 2016,2: 6-10.

[23]Kim H M, Laskowski M. Towards an ontology-driven blockchain design for supply chain provenance[J]. 2016.

[24]Benet J. IPFS-content addressed, versioned, P2P file system[J]. arXiv preprint arXiv:1407.3561, 2014.