Ken Jia
摘要:共識算法在區(qū)塊鏈中有著至關(guān)重要的地位。它不僅可以協(xié)調(diào)數(shù)據(jù)的一致性、還對代幣的發(fā)行等功能有一定的幫助。自2009年第一個區(qū)塊鏈系統(tǒng)誕生至今,區(qū)塊鏈的技術(shù)一直在進步著,如今已經(jīng)達到了百花齊放的地步。本文主要介紹了區(qū)塊鏈共識算法的產(chǎn)生以及發(fā)展,最后還對區(qū)塊鏈的未來進行了展望。
關(guān)鍵詞:區(qū)塊鏈;共識算法;拜占庭容錯;分布式系統(tǒng)
中圖分類號:TP311 文獻標識碼:A
文章編號:1009-3044(2019)32-0034-02
共識問題最早可以追溯到1959年。當時就有關(guān)于針對在某個特別定義的概率空間內(nèi),討論一組個體如何形成概率共識分布的問題。后來共識問題逐漸進入社會學(xué)、經(jīng)濟學(xué),特別是計算機學(xué)領(lǐng)域的時候才廣泛的引起了大家的關(guān)注。早起計算機領(lǐng)域內(nèi)的共識問題還集中在分布一致性上面,其中傳統(tǒng)的分布一致性研究還沒有考慮過拜占庭容錯的問題。直到后來2008年,一名化名為“中本聰”的研究者發(fā)布了一篇意義重大的論文,驗證了一類可行的、實用的、互聯(lián)網(wǎng)規(guī)模的拜占庭容錯算法,自此打開了區(qū)塊鏈的新時代大門。
1區(qū)塊鏈共識算法發(fā)展現(xiàn)狀
1.1區(qū)塊鏈框架概述
目前還沒有對于區(qū)塊鏈有一個統(tǒng)一的定義,但是普遍來說,區(qū)塊鏈是一種將數(shù)據(jù)區(qū)塊按照時間順序排列,同時鏈式結(jié)構(gòu)加密儲存的,不可更改的,去中心化的共享賬本。區(qū)塊鏈的框架由數(shù)據(jù)層、網(wǎng)絡(luò)層、共識層以及應(yīng)用層組成。
數(shù)據(jù)層包括鏈式結(jié)構(gòu)和數(shù)據(jù)區(qū)塊,其中每個節(jié)點都利用了哈希指針來建立數(shù)據(jù)結(jié)構(gòu)。在數(shù)據(jù)交易的過程中所涉及的哈希算法、時間戳的要素保證了被交易的區(qū)塊數(shù)據(jù)的不可更改性以及可追溯性。
網(wǎng)絡(luò)層封裝了區(qū)塊鏈系統(tǒng)當中的消息傳播等要素。區(qū)塊鏈是分布式系統(tǒng),采用P2P網(wǎng)絡(luò)來組織全球節(jié)點,這些節(jié)點讓網(wǎng)絡(luò)具備了廣播交易或者區(qū)塊、轉(zhuǎn)發(fā)等功能。
共識層包括各種共識算法、這些算法可以實現(xiàn)節(jié)點間數(shù)據(jù)的一致性。應(yīng)用層則是用來實現(xiàn)各種應(yīng)用場景實現(xiàn)。
1.2區(qū)塊鏈共識算法創(chuàng)立及發(fā)展
分布式計算領(lǐng)域的共識問題于1980年提出,該問題主要描述的是在一堆可能發(fā)生故障的節(jié)點中,如何針對非故障節(jié)點對于一定特征值達成共識,后來在1982年該問題被正式命名為“拜占庭將軍問題”。自此分布共識算法可以分為拜占庭容錯問題以及非拜占庭容錯問題。1985年由邁克爾·費舍爾等人提出了FLP不可能定理,在此基礎(chǔ)上產(chǎn)生的各種算法組成了最早的分布一致性算法。1988年布萊恩·奧奇等人提出了采用主機備份模式來保持一致型的VR一致性算法。1989年萊斯利·蘭伯特提出了基于消息傳遞的一致性算法Paxos算法。辛西婭·德沃克于1993年首次提出了工作量證明思想,而在1997年亞當·伯克也提出了用于哈?,F(xiàn)金的工作量證明機制。最后由馬庫斯·雅各布松正式提出了“工作量證明”這一正式概念。1999年由Barbara Liskov等提出了實用拜占庭容錯算法。2000年由埃里克·布魯爾教授提出了后來對區(qū)塊鏈體系設(shè)計帶來影響和限制的布魯爾定理。最后,在2008年由中本聰發(fā)表的比特幣共識機制打開了區(qū)塊鏈的大門。
1.3共識算法的模型及分類
目前大多數(shù)主流共識算法采用的核心思想包括“選主”和“記賬”兩部分,在具體流程中每一個輪次都會分為選主、造塊、驗證和上鏈四個階段。在區(qū)塊鏈系統(tǒng)中全體節(jié)點可以記為P,負責打包數(shù)據(jù)的節(jié)點記為M,礦工節(jié)點中的代表節(jié)點為D,最后通過共識過程的記賬節(jié)點為A。選主即M→A的過程,一般來說A=1。造塊即用A將特定選擇的內(nèi)容打包在發(fā)往全體的M中。驗證即節(jié)點M將接收到包裹進行驗證。上鏈即在包裹通過驗證后更新到區(qū)塊鏈末端的行為。
區(qū)塊鏈共識模式有很多種區(qū)分方法。比如根據(jù)容錯類型判斷,可將區(qū)塊鏈共識算法分為拜占庭容錯算法和非拜占庭容錯算法;根據(jù)部署方式可以將區(qū)塊鏈共識算法分為聯(lián)盟鏈共識算法、公有鏈共識算法以及私有鏈共識算法,最后還可以將區(qū)塊鏈共識算法分為弱一致性共識算法和強一致性共識算法。
2區(qū)塊鏈共識算法展望
2.1PoW與POS算法的有機結(jié)合
一些研究者將PoW和PoS有機結(jié)合起來發(fā)明了一些新穎的證明方法。其中有權(quán)益一速度證明PoSV、燃燒證明PoB、行動證明PoA以及二跳共識算法。PoSV主要針對在PoS算法中的幣齡與時間呈線性關(guān)系這一問題,主要是為了解決貨幣擁有著囤積貨幣的現(xiàn)象,其解決方法就是將幣齡與時間的關(guān)系修改為指數(shù)衰減的形式,這樣就可以讓持有時間長的貨幣的幣齡增長幅度大幅下降,從而有效遏制屯幣現(xiàn)象。PoB共識算法是為了在網(wǎng)絡(luò)中產(chǎn)生新的貨幣而被發(fā)明出來的,它通過讓礦工將原有貨幣進行燃燒再進行重新挖掘從而獲得更多的貨幣,來實現(xiàn)貨幣的產(chǎn)生。同時PoB算法使燃燒的貨幣不再被召回,而且對于礦工來說,燃燒的貨幣越多,挖掘出的新的貨幣就會越多。PoA共識算法則是將挖掘出來的一部分貨幣以抽獎的形式獎勵給全部節(jié)點,而中獎概率則是直接和權(quán)益掛鉤。二跳共識算法則是為了解決PoW潛在的51%算力攻擊問題,從而保障了區(qū)塊鏈的安全性。
2.2原生PoW算法的改進
原生PoW算法的改進主要是要將比特幣擴容或降低比特幣的能耗。
2016年Eyal提出了一種新型的共識算法Bitcoin-NG。這種算法主要是在每個時間段上設(shè)置了一個領(lǐng)導(dǎo)者,然后利用領(lǐng)導(dǎo)者來生產(chǎn)更多的區(qū)塊,從而達共識算法到擴容的目的。同年提出的ByzCoin借鑒了這種思想,在保證強一致性的同時,提高了Paypal的性能以及降低了延遲。2016年提出的Elastico則是通過分片的方式來實現(xiàn)了拜占庭容錯的安全問題。2017年ByzCoinX則是利用了上述兩種容錯方式將比特幣在擴容的同時還不比犧牲長期的安全性和去中心性的分布式賬本架構(gòu)。為了降低PoW算法的能耗。研究者提出了消逝時間證明PoET和運氣證明PoL。這兩種證明方式都是以特定的可信執(zhí)行環(huán)境為基礎(chǔ)的隨機共識算法。PoET算法的意義在于能夠有效地降低能耗,讓挖礦的消耗大幅降低,并且實現(xiàn)了"ICPUl票”的公平性。同樣的,PoL算法是通過降低交易的驗證時間來降低能源消耗的。
2.3原生PoS算法的改進
原生PoS算法的改進主要是針對解決PoS算法中固有的“無利害關(guān)系”問題,由此產(chǎn)生了很多種新的共識算法。2014年提出的Tendermint實現(xiàn)了第一個基于PBFT的PoS共識算法。這種方法是一收取保證金的方式,來實現(xiàn)問題的解決,假如礦工作惡,那么保證金就會被沒收。2015年提出的Casper尚在完善階段,其分為兩類。一類是有明確PoS共識的CTFG,另一類是將PoW和PoS有機結(jié)合的CFFG。2016年提出的HoneyBad-ger共識是第一個可以實用的異步拜占庭容錯共識協(xié)議,這種共識可以實現(xiàn)在沒有任何網(wǎng)絡(luò)的情況下,依舊保證區(qū)塊鏈系統(tǒng)的活性。
2.4傳統(tǒng)分布式一致性算法的改進
傳統(tǒng)的分布式一致性算法一直都是非拜占庭容錯的。研究者為了突破這一桎梏在2014年提出了拜占庭容錯的Tanga-roa算法。2016年提出了拜占庭容錯的Raft算法,后來逐漸發(fā)展成為ScalableBFT的專用拜占庭容錯協(xié)議。2015年提出了恒星共識協(xié)議SCP,這是第一個具有明確安全機制的,具有漸進安全、靈活信任、低延遲和分散控制四個關(guān)鍵屬性的共識機制。同年,將Ripple和SCP共識相結(jié)合提出了法定人數(shù)投票共識算法,以應(yīng)隨需要即時交易的場景。2016年NEO提出了一種名為dBFT的算法,這種算法改進了PoW和PoS最終一致性的問題,讓區(qū)塊鏈進軍到金融領(lǐng)域內(nèi)。2016年,提出了MgoRand的快速拜占庭容錯共識算法,這是被認為真正的民主和高效的分布式賬本共識技術(shù)。
3結(jié)束語
近年來隨著區(qū)塊鏈技術(shù)的廣泛發(fā)展,共識算法技術(shù)也越來越多地為人們所學(xué)習。未來該技術(shù)將會朝著證明方式多樣化、證明方式混合化、中心化共識需求增多以及研究合理的激勵措施等方向努力發(fā)展。相信未來區(qū)塊鏈技術(shù)將會得到更加長足的進步。