區(qū)塊鏈共識(shí)算法研究與趨勢(shì)分析

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

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

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

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

引言

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

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

1 共識(shí)的目的及拜占庭問(wèn)題

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

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

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

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

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

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

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

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

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

各參數(shù)的含義為

nVersion：版本號(hào)，記錄版本信息

hashPrevBlock：父區(qū)塊哈希

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

nTime：時(shí)間戳

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

nNonce：隨機(jī)值

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

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

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

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

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

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

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

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

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

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

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

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

與 PoW 這種具體算法相比，PoS 更確切的是一個(gè)方向，多個(gè)衍生算法各具特色，甚至相互在實(shí)現(xiàn)上差異很大。但有一點(diǎ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é)點(diǎn)的不斷增加，網(wǎng)絡(luò)結(jié)構(gòu)日趨復(fù)雜，系統(tǒng)完成共識(shí)的成本也會(huì)不斷升高。另外，由于PoW 共識(shí)中收益取決于算力的高低，這使得部分用戶只著眼于如何通過(guò)多種途徑來(lái)提高算力，卻不在意區(qū)塊鏈系統(tǒng)本身的生態(tài)與維護(hù)。雖然后來(lái)出現(xiàn)了改進(jìn)的算法，設(shè)定了內(nèi)存難解等策略來(lái)對(duì)抗 ASIC 礦機(jī)。但這種補(bǔ)丁方式無(wú)法從根本上解決算力與股權(quán)間的矛盾。

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

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

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

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

2.4 綜合對(duì)比

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

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

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

表1 三種共識(shí)算法對(duì)比Table 1 The comparison of three consensus

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

3 其它共識(shí)算法

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

3.1 PBFT

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

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

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

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

3.2 dBFT

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

3.3 瑞波共識(shí)

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

(1) 驗(yàn)證節(jié)點(diǎn)會(huì)收到兩類信息：交易和候選集。接收的交易會(huì)被驗(yàn)證，通過(guò)的將被匯總到交易候選集中。

(2) 每個(gè)驗(yàn)證節(jié)點(diǎn)會(huì)周期性的把自己的候選集發(fā)送給其他節(jié)點(diǎn)。

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

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

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

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

3.4 權(quán)威證明

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

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

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

4 總結(jié)與展望

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

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

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

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

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

[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.