段希楠,延志偉,耿光剛,閻保平
1. 中國科學(xué)院計(jì)算機(jī)網(wǎng)絡(luò)信息中心,北京 100190
2. 中國科學(xué)院大學(xué),北京 100049
3. 中國互聯(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è)無需中心權(quán)威機(jī)構(gòu)的、去中心化的電子現(xiàn)金系統(tǒng)。在沒有第三方擔(dān)保的條件下,數(shù)字貨幣面臨著兩大問題——拜占庭問題[2]和雙花[3],即參與節(jié)點(diǎn)如何構(gòu)造統(tǒng)一的賬本,以及如何保證一筆資金不被同時(shí)用于多個(gè)交易。問題的實(shí)質(zhì),就是在沒有中心權(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í)算法、梅克爾樹[4]等多個(gè)元素。所以嚴(yán)格意義上說,區(qū)塊鏈并不是一種全新的技術(shù),而是多種已有成熟技術(shù)的巧妙整合。比如其中的共識(shí)算法,作為區(qū)塊鏈中解決一致性問題的關(guān)鍵,它最初誕生于分布式系統(tǒng)中,經(jīng)過多年的研究探索,共識(shí)已經(jīng)演變出多種體系。如何選用合適的算法使系統(tǒng)達(dá)到相對(duì)最優(yōu)的性能,是在設(shè)計(jì)區(qū)塊鏈中必不可少的環(huán)節(jié)。本文旨在介紹幾種具有代表性的共識(shí)算法,并分析其各自特點(diǎn)以及在區(qū)塊鏈中的應(yīng)用情況。
在分布式系統(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è)過程中,如果將主鏈視為賬本,共識(shí)算法所做的就是決定將哪個(gè)節(jié)點(diǎn)整理的賬目寫入總賬,即如何分配記賬權(quán)。
區(qū)塊鏈系統(tǒng)中,多節(jié)點(diǎn)協(xié)同處理事務(wù)時(shí)會(huì)常常遇到各種問題。比如,不同節(jié)點(diǎn)接收信息有時(shí)間先后,信息在傳輸過程中可能丟失,節(jié)點(diǎn)間使用系統(tǒng)有差異,節(jié)點(diǎn)本身也會(huì)發(fā)生故障……除這些非人為因素外,系統(tǒng)實(shí)際運(yùn)行時(shí),節(jié)點(diǎn)間的通訊信息也可能受到人為的惡意干預(yù),即經(jīng)典的拜占庭將軍問題。此問題最初由 Leslie Lamport 于 1982 年提出,具體指在有少數(shù)作惡節(jié)點(diǎn)存在,消息可能會(huì)被偽造或篡改的情況下,如何讓誠實(shí)節(jié)點(diǎn)仍能保持行動(dòng)的一致。
Leslie Lamport 證明,在作惡節(jié)點(diǎn)占比不超過 1/3的情況下,存在有效的算法使得誠實(shí)節(jié)點(diǎn)始終保持一致[6]。此類算法也可稱為拜占庭容錯(cuò) (Byzantine Fault Tolerant,BFT) 算法。對(duì)應(yīng)的,在只考慮節(jié)點(diǎn)崩潰或者網(wǎng)絡(luò)不暢等問題的非拜占庭場景下,也存在容忍值:1/2。即有半數(shù)以上節(jié)點(diǎn)發(fā)出同樣的“提案”時(shí),才能使得系統(tǒng)達(dá)成一致。
工作量證明機(jī)制 (ProofofWork, PoW)[7],最初在HashCash[8]中用于垃圾郵件的過濾。之后中本聰于2008 年,創(chuàng)新性的采用此算法來實(shí)現(xiàn)比特幣中節(jié)點(diǎn)數(shù)據(jù)的一致性。作為一個(gè)去中心化的虛擬現(xiàn)金系統(tǒng),比特幣首要解決的就是如何記賬,以及在沒有第三方權(quán)威機(jī)構(gòu)監(jiā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)來決定系統(tǒng)的走向,也就是所謂的女巫攻擊 (Sybil Attack)[9]。
工作量證明機(jī)制是抵御上述攻擊的一種有效手段。所謂工作就是指節(jié)點(diǎn)需要花費(fèi)自己的算力資源來進(jìn)行“挖礦”,先完成“挖礦”任務(wù)的節(jié)點(diǎn)可以將此工作量的證明連同記賬信息 (也就是整理好的區(qū)塊) 一起廣播給其他節(jié)點(diǎn)。其它節(jié)點(diǎn)接收到此消息后,會(huì)首先驗(yàn)證工作的有效性,如果有效且記賬信息也驗(yàn)證無誤,該節(jié)點(diǎn)就將此區(qū)塊加入本地維護(hù)的鏈中,并著手下一輪的算力競賽。如驗(yàn)證失敗,則丟棄此信息,并繼續(xù)當(dāng)輪的“挖礦”工作[5]。
考慮到系統(tǒng)的性能,“挖礦”過程應(yīng)具有工作量可以被度量并且結(jié)果易于驗(yàn)證的特點(diǎn)。因此 PoW 采用哈希運(yùn)算的方式:對(duì)于特定輸入,哈希的結(jié)果每次都一樣,任何人都可以復(fù)現(xiàn)并驗(yàn)證;反之,要生成一個(gè)特定的哈希值,只能不斷變化輸入而無法直接做出選擇。比特幣的工作量證明就是對(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)于競爭到記賬權(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ì)來源主要有兩種,其一是產(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 萬枚比特幣將會(huì)產(chǎn)出完畢[10]。
激勵(lì)措施會(huì)不斷吸引節(jié)點(diǎn)加入系統(tǒng)中,同時(shí)也導(dǎo)致全網(wǎng)算力提高,若“挖礦”難度保持不變,區(qū)塊的生成速度將越來越快。難度調(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à)上漲又不斷吸引著用戶通過“挖礦”獲利,節(jié)點(diǎn)數(shù)量上升也增強(qiáng)了系統(tǒng)的安全性,減少被 51% 攻擊[11]的可能,防范了雙花。綜上,算法中各種附加機(jī)制相輔相成,促進(jìn)了區(qū)塊鏈整體系統(tǒng)的平穩(wěn)運(yùn)行。
比特幣在 PoW 中引入激勵(lì)等機(jī)制,為之后區(qū)塊鏈共識(shí)算法的設(shè)計(jì)研究奠定了基礎(chǔ)。然而它的弊端在于,隨著“挖礦”難度的提高,消耗的資源也越來越大,并且用如此高的算力所計(jì)算的內(nèi)容,從科學(xué)角度上講幾乎沒有價(jià)值。鑒于此,權(quán)益證明 (Proof of Stake,PoS) 應(yīng)運(yùn)而生。
PoS 最先由 Sunny King 的點(diǎn)點(diǎn)幣 (Peercoin)[12]實(shí)現(xiàn),后來蘋果幣 (Applecoin V2 (v1 用的是 PoW))、未來幣 (Nextcoin)、黑幣 (Blackcoin) 等多個(gè)應(yīng)用都做了不同的改進(jìn)。PoS 延續(xù)了 PoW 中的競爭打包區(qū)塊權(quán)的理念,不同之處在于 PoS 中是根據(jù)用戶持有的系統(tǒng)代幣來決定打包出塊的概率。
以 Peercoin 為例,決定記賬權(quán)的唯一要素是幣齡。開啟“挖礦”模式后,幣齡就可以累積。錢包中的每枚代幣每天都可產(chǎn)生 1 幣齡?!暗V工”用于“挖礦”的總幣齡越高,獲得收益的概率也就越大。舉例來說,用戶甲有 1000 枚代幣,持有 50 天,那么他的幣齡就為 5 萬。當(dāng)他用這一千枚代幣競爭到記賬權(quán)后,幣齡也會(huì)一同清空。Peercoin 的獎(jiǎng)勵(lì)機(jī)制也同幣齡相關(guān),它的利息 (或可理解為年利率) 為 1%,即每清空 365 幣齡,用戶會(huì)獲得 0.01 枚的代幣。
公有鏈的安全性非常依賴于其維護(hù)節(jié)點(diǎn)的數(shù)量,由于 Peercoin 的幣齡具有無需接入系統(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ì)近些年也在積極開發(fā)一種名為 Casper[14]的 PoS 共識(shí)機(jī)制。以往的“挖礦”和區(qū)塊驗(yàn)證工作都由“礦工”來完成,而 Casper試圖將這兩種職能分離,將“挖礦”過程虛擬化,并使驗(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ì)被沒收。為獲取收益,節(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ī)制。
隨著“挖礦”節(jié)點(diǎn)的不斷增加,網(wǎng)絡(luò)結(jié)構(gòu)日趨復(fù)雜,系統(tǒng)完成共識(shí)的成本也會(huì)不斷升高。另外,由于PoW 共識(shí)中收益取決于算力的高低,這使得部分用戶只著眼于如何通過多種途徑來提高算力,卻不在意區(qū)塊鏈系統(tǒng)本身的生態(tài)與維護(hù)。雖然后來出現(xiàn)了改進(jìn)的算法,設(shè)定了內(nèi)存難解等策略來對(duì)抗 ASIC 礦機(jī)。但這種補(bǔ)丁方式無法從根本上解決算力與股權(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)。該算法也被之后的億書 (Ebookchain)、柚子 (Enterprise Operation System, Eos)、公信寶(GXChain)、阿希 (ASCH) 等項(xiàng)目采用。
在創(chuàng)立比特股時(shí),Dan 提出了一個(gè)概念——DAC (去中心化自治公司)。正如一家公司,每個(gè)持有貨幣的人都相當(dāng)于掌握著部分股權(quán),用戶可以用自己的股權(quán)來參與公司的管理。首先,DPoS 中的區(qū)塊只由小部分的可信賬戶生成,這些賬戶被稱為見證人(Witnesses),由選舉產(chǎn)生。每個(gè)持股人都可投票給其他用戶,票數(shù)中前 N (通常為 101) 的候選者就可當(dāng)選為見證人。見證人的候選名單每個(gè)維護(hù)周期 (1 天) 會(huì)更改一次。選舉完成后,見證人隨機(jī)排列,每人有 2秒的時(shí)間輪流獲得記賬權(quán)。若在規(guī)定時(shí)間內(nèi)未能生成區(qū)塊,權(quán)限仍會(huì)交給下一名見證人。任何人都可實(shí)時(shí)監(jiān)測見證人的狀況,如果某人被發(fā)現(xiàn)打包率過低或是有作惡行為,該見證人就會(huì)失去公信,再競選成功難度提高。
除見證人外,比特股還加入了對(duì)代表的競選。選出的代表擁有提出更改網(wǎng)絡(luò)參數(shù)的權(quán)利,如:交易費(fèi)用、區(qū)塊大小、見證人費(fèi)用以及區(qū)塊間隔。若大多數(shù)代表都同意某項(xiàng)提案,持股人會(huì)得到兩周的審查期決定是否罷免代表并撤除所提議的改變。這一設(shè)計(jì)確保了代表無法直接對(duì)參數(shù)進(jìn)行修改,并且所有的更改都是經(jīng)過持股人同意的。
可以說,DPoS 算法使持股人的股權(quán)得以更充分的使用,使共識(shí)過程變的更加民主。但由于投票的多少與用戶持股的占比有關(guān),DPoS 增加了少數(shù)大股東的話語權(quán)。
不難發(fā)現(xiàn),區(qū)塊鏈的分布式網(wǎng)絡(luò)也是拜占庭環(huán)境,難免會(huì)有作惡節(jié)點(diǎn)的存在。傳統(tǒng)的拜占庭共識(shí)算法都有作惡節(jié)點(diǎn)不能超過總結(jié)點(diǎn)數(shù) 1/3 的限制,否則系統(tǒng)可能無法達(dá)成一致。而在區(qū)塊鏈中,通常所說的安全隱患是 51% 攻擊而非 33%。之所以能將攻擊成本提高,是由于從區(qū)塊鏈采用的第一個(gè)共識(shí)算法 PoW開始,就引入了競爭挖礦和分叉處理的機(jī)制。首先,競爭挖礦相當(dāng)于為區(qū)塊的生成設(shè)立了門檻,節(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ò)傳播的過程中,某處節(jié)點(diǎn)也挖掘出了有效區(qū)塊,這兩個(gè)區(qū)塊很可能會(huì)在原來鏈的基礎(chǔ)上,形成不同的分叉。區(qū)塊鏈系統(tǒng)允許在一段時(shí)間內(nèi)有數(shù)據(jù)不一致的情況出現(xiàn),并設(shè)置了相應(yīng)的分叉處理。當(dāng)節(jié)點(diǎn)收到新的區(qū)塊但發(fā)現(xiàn)無法加入到自身維護(hù)的鏈中時(shí),它會(huì)將節(jié)點(diǎn)所在的鏈與自身存儲(chǔ)的鏈進(jìn)行對(duì)比,然后將全部數(shù)據(jù)更新為較長鏈。PoW 中,鏈的長度是指各區(qū)塊中難度的累加和,而在以 Peercoin 為代表的 PoS 中,長度指的是幣齡的累加之和。
從攻擊者角度而言,攻擊的思路不應(yīng)是如何讓系統(tǒng)無法達(dá)成一致,而是要利用系統(tǒng)的一致性處理,用新數(shù)據(jù)覆蓋舊數(shù)據(jù),以造成貨幣的雙花。從表 1 中,可看出三種共識(shí)的安全威脅各不相同。在 PoW 中,如果某組織長期持有 50% 以上的全網(wǎng)算力,那他們產(chǎn)生區(qū)塊的速度會(huì)快于其他節(jié)點(diǎn),就有可能用他們偽造的鏈來替代正常鏈。而在 PoS 中要達(dá)到同樣的效果,攻擊者就需要掌握參與當(dāng)前網(wǎng)絡(luò)競爭的 50% 以上的貨幣。這樣無論共識(shí)采用幣齡還是其它的一些方式,攻擊者總能以足夠高的股權(quán)來影響區(qū)塊內(nèi)容。PoS 把威脅來源從 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)的公平性。但其先競選后挖礦的流程,注定了被選中節(jié)點(diǎn)產(chǎn)生作弊行為時(shí),只能被動(dòng)應(yīng)對(duì)而無法提前預(yù)防,這也為系統(tǒng)帶來了新的安全隱患。
從性能上講,對(duì)系統(tǒng)的評(píng)價(jià)指標(biāo)有出塊速度和每秒交易處理數(shù) (TransactionsPerSecond,TPS)。比特幣的 PoW 規(guī)定是平均 10 min 出一個(gè)塊,之所以設(shè)置這么長的時(shí)間,中本聰認(rèn)為這對(duì)一個(gè)支付系統(tǒng)已經(jīng)足夠。而目前看來,比特幣設(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,未來幣的是 60 s。一般來說,這個(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)之一。
上述算法不僅可用于公有鏈,在聯(lián)盟鏈和私有鏈中也同樣有效,是目前被廣泛承認(rèn)和應(yīng)用的共識(shí)方式。而下面介紹的幾種算法雖知名度稍差,僅用于個(gè)別系統(tǒng)中,但本文認(rèn)為它們也同樣擁有良好的性能,設(shè)計(jì)思路非常值得研究和借鑒。
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é)議是確保來自客戶端的請(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í)過程中,節(jié)點(diǎn)會(huì)隨時(shí)記錄日志,如果日志得不到及時(shí)清理,會(huì)導(dǎo)致系統(tǒng)資源被無用信息占用,從而影響整體性能。同時(shí),由于系統(tǒng)的異步性無法保證每一個(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)來源比較可靠的私有鏈或聯(lián)盟鏈場景。目前 IBM 的的 Fabric 項(xiàng)目中,PBFT 被做成可插拔的共識(shí)模塊供用戶選擇。
dBFT (delegated Byzantine Fault Tolerance)[18]是國內(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ā)送交易。算法過程大致如下:確定議長-議長廣播提案-議員驗(yàn)證提案并廣播-任意節(jié)點(diǎn)收到足夠多的確認(rèn)信息后即可廣播完整區(qū)塊-其它節(jié)點(diǎn)收到完整區(qū)塊后就接收并刪除已包含入?yún)^(qū)塊的交易。
瑞波算法 (Ripple)[19]的出發(fā)點(diǎn)是想通過減少信息的確認(rèn)次數(shù),來降低網(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í)過程基本如下:
(1) 驗(yàn)證節(jié)點(diǎn)會(huì)收到兩類信息:交易和候選集。接收的交易會(huì)被驗(yàn)證,通過的將被匯總到交易候選集中。
(2) 每個(gè)驗(yàn)證節(jié)點(diǎn)會(huì)周期性的把自己的候選集發(fā)送給其他節(jié)點(diǎn)。
(3) 驗(yàn)證節(jié)點(diǎn)在收到其他節(jié)點(diǎn)發(fā)來的候選集后,會(huì)首先驗(yàn)證發(fā)送節(jié)點(diǎn)是否在 UNL 中:若是,則將之與自身候選集中的交易一一進(jìn)行比對(duì)。如果有相同的交易,那么該交易獲得一票。
(4) 驗(yàn)證節(jié)點(diǎn)把所有達(dá)到80%確認(rèn)的交易寫入本地?cái)?shù)據(jù)庫,表示此交易已加入該節(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í)刻可能無法保證一致,但這不一致是暫時(shí)性的,長期看來節(jié)點(diǎn)數(shù)據(jù)會(huì)趨于相同。
由于交易達(dá)到 80% 以上的確認(rèn)后才被加入賬本,因此網(wǎng)絡(luò)中一旦有超過 20% 的惡意節(jié)點(diǎn),瑞波算法就很可能無法完成共識(shí),這也是該算法為何要求驗(yàn)證節(jié)點(diǎn)具有高可信度的原因。但如果想對(duì)賬本數(shù)據(jù)產(chǎn)生影響,惡意節(jié)點(diǎn)也要達(dá)到 80% 才可能成功。
PoA (Proof of Authority)[20]共識(shí)目前僅用于以太坊的Kovan測試網(wǎng)中,與瑞波的思路相似,PoA 也是一種利用高信任度來減少處理時(shí)延的算法。網(wǎng)絡(luò)中所有節(jié)點(diǎn)分為普通節(jié)點(diǎn)和小部分的權(quán)威節(jié)點(diǎn),僅權(quán)威節(jié)點(diǎn)參與共識(shí)過程。權(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)上沒有做任何更改,而是重用difficulty 字段來區(qū)分區(qū)塊是否由主節(jié)點(diǎn)打包:(1) 是副節(jié)點(diǎn);(2) 是主節(jié)點(diǎn)。同時(shí),nonce 字段也被重用,表示提議加入或刪除某個(gè)共識(shí)節(jié)點(diǎn)。
PoA 在測試網(wǎng)中的出塊間隔為 5 s,用于真實(shí)場景中最大的區(qū)別也僅是網(wǎng)絡(luò)傳輸速度的變化,預(yù)計(jì)仍能保持較好的性能。目前共識(shí)節(jié)點(diǎn)在收到區(qū)塊時(shí)只是檢查區(qū)塊頭中記錄的某些屬性,沒有對(duì)區(qū)塊內(nèi)容進(jìn)行驗(yàn)證,說明共識(shí)節(jié)點(diǎn)間是高度信任的。因此 PoA 算法非常適合在聯(lián)盟鏈或私有鏈中使用。
近年來,隨著區(qū)塊鏈技術(shù)得到廣泛的關(guān)注,共識(shí)算法也被越來越多的人所學(xué)習(xí)和研究。作為區(qū)塊鏈的重要組成部分,共識(shí)算法體現(xiàn)著區(qū)塊鏈系統(tǒng)的性能與功能。目前,新的共識(shí)方式層出不窮,經(jīng)分析與總結(jié),該技術(shù)呈現(xiàn)著如下幾個(gè)發(fā)展趨勢:
證明方式多樣化:早期的工作量證明、權(quán)益證明方式存在著資源浪費(fèi),節(jié)點(diǎn)積極性不高的問題。研究者們出于降低“挖礦”競爭的成本或是提高資源利用率、增加應(yīng)用場景等目的,開發(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)的足夠分散,增加攻擊者掌握大部分競爭力的難度,減少單個(gè)節(jié)點(diǎn)或組織改寫區(qū)塊鏈的可能。通過這樣,才能有效的防范雙花,保證系統(tǒng)的安全與穩(wěn)定。
證明方式混合化:PoW 的威脅來自擁有高算力的礦場,而 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ì)因過高的中心化而失去價(jià)值。理論上混合模式具有獨(dú)特優(yōu)勢,但目前成熟項(xiàng)目不多。
中心化共識(shí)需求增多:公有鏈中,任何人都可加入并維護(hù)一個(gè)節(jié)點(diǎn),公平享有全部的數(shù)據(jù)。但在涉及到企業(yè)或組織內(nèi)部信息的情況下,聯(lián)盟鏈或私有鏈無疑是更好的選擇。由于這兩種鏈中節(jié)點(diǎn)是聯(lián)盟成員或企業(yè)內(nèi)部提供,可信度有一定保證。因此在設(shè)計(jì)共識(shí)算法時(shí),可以免去中間選舉、驗(yàn)證或競爭挖礦權(quán)等過程。比如瑞波和 PoA 共識(shí),它們雖然加入了選舉機(jī)制,但不作為必要流程,共識(shí)節(jié)點(diǎn)完全可以由組織內(nèi)部指定,節(jié)點(diǎn)間依據(jù)共同規(guī)則輪流生成區(qū)塊。這些算法具有一定的中心化程度,若用于公有鏈中,必然會(huì)因其不公平性而受到質(zhì)疑。但在不需要徹底去中心化的聯(lián)盟鏈中,由于簡化了共識(shí)流程,此類算法普遍會(huì)表現(xiàn)出優(yōu)于公有鏈算法的性能。隨著企業(yè)對(duì)聯(lián)盟鏈或私有鏈需求的增多,中心化的共識(shí)算法也會(huì)得到相應(yīng)的關(guān)注和發(fā)展。
研究合理的激勵(lì)措施:區(qū)塊鏈中往往會(huì)引入激勵(lì)機(jī)制來處理技術(shù)上的難題,比如公有鏈的安全依賴于大量節(jié)點(diǎn)的維護(hù),于是加入激勵(lì)機(jī)制來調(diào)動(dòng)用戶積極性;比如用于解決區(qū)塊鏈存儲(chǔ)問題的 IPFS[24]技術(shù),也是結(jié)合勵(lì)機(jī)制來鼓勵(lì)用戶協(xié)助存儲(chǔ)數(shù)據(jù)碎片,才得以形成一個(gè)完整的項(xiàng)目 Filecoin。因此,如果能結(jié)合共識(shí)的具體過程,設(shè)計(jì)合理的激勵(lì)措施,在實(shí)際運(yùn)行中往往會(huì)達(dá)到事半功倍的效果,對(duì)系統(tǒng)的安全與延續(xù)也會(huì)有積極作用。此外,研究者們對(duì)于聯(lián)盟鏈中是否需要內(nèi)部代幣一直存在爭論,本文認(rèn)為在一些信任度不完全的聯(lián)盟中,加入幣來實(shí)施獎(jiǎng)懲功能是有必要的。而聯(lián)盟鏈中若采用有一定中心化的共識(shí),節(jié)點(diǎn)間不設(shè)競爭而用設(shè)定的順序生成區(qū)塊。此種情況下,怎樣加入合理的激勵(lì)措施就變成了問題。通過大家的不斷探索,相信以后會(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.