Ken Jia

摘要：共識(shí)算法在區(qū)塊鏈中有著至關(guān)重要的地位。它不僅可以協(xié)調(diào)數(shù)據(jù)的一致性、還對(duì)代幣的發(fā)行等功能有一定的幫助。自2009年第一個(gè)區(qū)塊鏈系統(tǒng)誕生至今，區(qū)塊鏈的技術(shù)一直在進(jìn)步著，如今已經(jīng)達(dá)到了百花齊放的地步。本文主要介紹了區(qū)塊鏈共識(shí)算法的產(chǎn)生以及發(fā)展，最后還對(duì)區(qū)塊鏈的未來(lái)進(jìn)行了展望。

關(guān)鍵詞：區(qū)塊鏈;共識(shí)算法;拜占庭容錯(cuò);分布式系統(tǒng)

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2019）32-0034-02

共識(shí)問(wèn)題最早可以追溯到1959年。當(dāng)時(shí)就有關(guān)于針對(duì)在某個(gè)特別定義的概率空間內(nèi)，討論一組個(gè)體如何形成概率共識(shí)分布的問(wèn)題。后來(lái)共識(shí)問(wèn)題逐漸進(jìn)入社會(huì)學(xué)、經(jīng)濟(jì)學(xué)，特別是計(jì)算機(jī)學(xué)領(lǐng)域的時(shí)候才廣泛的引起了大家的關(guān)注。早起計(jì)算機(jī)領(lǐng)域內(nèi)的共識(shí)問(wèn)題還集中在分布一致性上面，其中傳統(tǒng)的分布一致性研究還沒(méi)有考慮過(guò)拜占庭容錯(cuò)的問(wèn)題。直到后來(lái)2008年，一名化名為“中本聰”的研究者發(fā)布了一篇意義重大的論文，驗(yàn)證了一類可行的、實(shí)用的、互聯(lián)網(wǎng)規(guī)模的拜占庭容錯(cuò)算法，自此打開(kāi)了區(qū)塊鏈的新時(shí)代大門。

1區(qū)塊鏈共識(shí)算法發(fā)展現(xiàn)狀

1.1區(qū)塊鏈框架概述

目前還沒(méi)有對(duì)于區(qū)塊鏈有一個(gè)統(tǒng)一的定義，但是普遍來(lái)說(shuō)，區(qū)塊鏈?zhǔn)且环N將數(shù)據(jù)區(qū)塊按照時(shí)間順序排列，同時(shí)鏈?zhǔn)浇Y(jié)構(gòu)加密儲(chǔ)存的，不可更改的，去中心化的共享賬本。區(qū)塊鏈的框架由數(shù)據(jù)層、網(wǎng)絡(luò)層、共識(shí)層以及應(yīng)用層組成。

數(shù)據(jù)層包括鏈?zhǔn)浇Y(jié)構(gòu)和數(shù)據(jù)區(qū)塊，其中每個(gè)節(jié)點(diǎn)都利用了哈希指針來(lái)建立數(shù)據(jù)結(jié)構(gòu)。在數(shù)據(jù)交易的過(guò)程中所涉及的哈希算法、時(shí)間戳的要素保證了被交易的區(qū)塊數(shù)據(jù)的不可更改性以及可追溯性。

網(wǎng)絡(luò)層封裝了區(qū)塊鏈系統(tǒng)當(dāng)中的消息傳播等要素。區(qū)塊鏈?zhǔn)欠植际较到y(tǒng)，采用P2P網(wǎng)絡(luò)來(lái)組織全球節(jié)點(diǎn)，這些節(jié)點(diǎn)讓網(wǎng)絡(luò)具備了廣播交易或者區(qū)塊、轉(zhuǎn)發(fā)等功能。

共識(shí)層包括各種共識(shí)算法、這些算法可以實(shí)現(xiàn)節(jié)點(diǎn)間數(shù)據(jù)的一致性。應(yīng)用層則是用來(lái)實(shí)現(xiàn)各種應(yīng)用場(chǎng)景實(shí)現(xiàn)。

1.2區(qū)塊鏈共識(shí)算法創(chuàng)立及發(fā)展

分布式計(jì)算領(lǐng)域的共識(shí)問(wèn)題于1980年提出，該問(wèn)題主要描述的是在一堆可能發(fā)生故障的節(jié)點(diǎn)中，如何針對(duì)非故障節(jié)點(diǎn)對(duì)于一定特征值達(dá)成共識(shí)，后來(lái)在1982年該問(wèn)題被正式命名為“拜占庭將軍問(wèn)題”。自此分布共識(shí)算法可以分為拜占庭容錯(cuò)問(wèn)題以及非拜占庭容錯(cuò)問(wèn)題。1985年由邁克爾·費(fèi)舍爾等人提出了FLP不可能定理，在此基礎(chǔ)上產(chǎn)生的各種算法組成了最早的分布一致性算法。1988年布萊恩·奧奇等人提出了采用主機(jī)備份模式來(lái)保持一致型的VR一致性算法。1989年萊斯利·蘭伯特提出了基于消息傳遞的一致性算法Paxos算法。辛西婭·德沃克于1993年首次提出了工作量證明思想，而在1997年亞當(dāng)·伯克也提出了用于哈希現(xiàn)金的工作量證明機(jī)制。最后由馬庫(kù)斯·雅各布松正式提出了“工作量證明”這一正式概念。1999年由Barbara Liskov等提出了實(shí)用拜占庭容錯(cuò)算法。2000年由埃里克·布魯爾教授提出了后來(lái)對(duì)區(qū)塊鏈體系設(shè)計(jì)帶來(lái)影響和限制的布魯爾定理。最后，在2008年由中本聰發(fā)表的比特幣共識(shí)機(jī)制打開(kāi)了區(qū)塊鏈的大門。

1.3共識(shí)算法的模型及分類

目前大多數(shù)主流共識(shí)算法采用的核心思想包括“選主”和“記賬”兩部分，在具體流程中每一個(gè)輪次都會(huì)分為選主、造塊、驗(yàn)證和上鏈四個(gè)階段。在區(qū)塊鏈系統(tǒng)中全體節(jié)點(diǎn)可以記為P，負(fù)責(zé)打包數(shù)據(jù)的節(jié)點(diǎn)記為M，礦工節(jié)點(diǎn)中的代表節(jié)點(diǎn)為D，最后通過(guò)共識(shí)過(guò)程的記賬節(jié)點(diǎn)為A。選主即M→A的過(guò)程，一般來(lái)說(shuō)A=1。造塊即用A將特定選擇的內(nèi)容打包在發(fā)往全體的M中。驗(yàn)證即節(jié)點(diǎn)M將接收到包裹進(jìn)行驗(yàn)證。上鏈即在包裹通過(guò)驗(yàn)證后更新到區(qū)塊鏈末端的行為。

區(qū)塊鏈共識(shí)模式有很多種區(qū)分方法。比如根據(jù)容錯(cuò)類型判斷，可將區(qū)塊鏈共識(shí)算法分為拜占庭容錯(cuò)算法和非拜占庭容錯(cuò)算法;根據(jù)部署方式可以將區(qū)塊鏈共識(shí)算法分為聯(lián)盟鏈共識(shí)算法、公有鏈共識(shí)算法以及私有鏈共識(shí)算法，最后還可以將區(qū)塊鏈共識(shí)算法分為弱一致性共識(shí)算法和強(qiáng)一致性共識(shí)算法。

2區(qū)塊鏈共識(shí)算法展望

2.1PoW與POS算法的有機(jī)結(jié)合

一些研究者將PoW和PoS有機(jī)結(jié)合起來(lái)發(fā)明了一些新穎的證明方法。其中有權(quán)益一速度證明PoSV、燃燒證明PoB、行動(dòng)證明PoA以及二跳共識(shí)算法。PoSV主要針對(duì)在PoS算法中的幣齡與時(shí)間呈線性關(guān)系這一問(wèn)題，主要是為了解決貨幣擁有著囤積貨幣的現(xiàn)象，其解決方法就是將幣齡與時(shí)間的關(guān)系修改為指數(shù)衰減的形式，這樣就可以讓持有時(shí)間長(zhǎng)的貨幣的幣齡增長(zhǎng)幅度大幅下降，從而有效遏制屯幣現(xiàn)象。PoB共識(shí)算法是為了在網(wǎng)絡(luò)中產(chǎn)生新的貨幣而被發(fā)明出來(lái)的，它通過(guò)讓礦工將原有貨幣進(jìn)行燃燒再進(jìn)行重新挖掘從而獲得更多的貨幣，來(lái)實(shí)現(xiàn)貨幣的產(chǎn)生。同時(shí)PoB算法使燃燒的貨幣不再被召回，而且對(duì)于礦工來(lái)說(shuō)，燃燒的貨幣越多，挖掘出的新的貨幣就會(huì)越多。PoA共識(shí)算法則是將挖掘出來(lái)的一部分貨幣以抽獎(jiǎng)的形式獎(jiǎng)勵(lì)給全部節(jié)點(diǎn)，而中獎(jiǎng)概率則是直接和權(quán)益掛鉤。二跳共識(shí)算法則是為了解決PoW潛在的51%算力攻擊問(wèn)題，從而保障了區(qū)塊鏈的安全性。

2.2原生PoW算法的改進(jìn)

原生PoW算法的改進(jìn)主要是要將比特幣擴(kuò)容或降低比特幣的能耗。

2016年Eyal提出了一種新型的共識(shí)算法Bitcoin-NG。這種算法主要是在每個(gè)時(shí)間段上設(shè)置了一個(gè)領(lǐng)導(dǎo)者，然后利用領(lǐng)導(dǎo)者來(lái)生產(chǎn)更多的區(qū)塊，從而達(dá)共識(shí)算法到擴(kuò)容的目的。同年提出的ByzCoin借鑒了這種思想，在保證強(qiáng)一致性的同時(shí)，提高了Paypal的性能以及降低了延遲。2016年提出的Elastico則是通過(guò)分片的方式來(lái)實(shí)現(xiàn)了拜占庭容錯(cuò)的安全問(wèn)題。2017年ByzCoinX則是利用了上述兩種容錯(cuò)方式將比特幣在擴(kuò)容的同時(shí)還不比犧牲長(zhǎng)期的安全性和去中心性的分布式賬本架構(gòu)。為了降低PoW算法的能耗。研究者提出了消逝時(shí)間證明PoET和運(yùn)氣證明PoL。這兩種證明方式都是以特定的可信執(zhí)行環(huán)境為基礎(chǔ)的隨機(jī)共識(shí)算法。PoET算法的意義在于能夠有效地降低能耗，讓挖礦的消耗大幅降低，并且實(shí)現(xiàn)了"ICPUl票”的公平性。同樣的，PoL算法是通過(guò)降低交易的驗(yàn)證時(shí)間來(lái)降低能源消耗的。

2.3原生PoS算法的改進(jìn)

原生PoS算法的改進(jìn)主要是針對(duì)解決PoS算法中固有的“無(wú)利害關(guān)系”問(wèn)題，由此產(chǎn)生了很多種新的共識(shí)算法。2014年提出的Tendermint實(shí)現(xiàn)了第一個(gè)基于PBFT的PoS共識(shí)算法。這種方法是一收取保證金的方式，來(lái)實(shí)現(xiàn)問(wèn)題的解決，假如礦工作惡，那么保證金就會(huì)被沒(méi)收。2015年提出的Casper尚在完善階段，其分為兩類。一類是有明確PoS共識(shí)的CTFG，另一類是將PoW和PoS有機(jī)結(jié)合的CFFG。2016年提出的HoneyBad-ger共識(shí)是第一個(gè)可以實(shí)用的異步拜占庭容錯(cuò)共識(shí)協(xié)議，這種共識(shí)可以實(shí)現(xiàn)在沒(méi)有任何網(wǎng)絡(luò)的情況下，依舊保證區(qū)塊鏈系統(tǒng)的活性。

2.4傳統(tǒng)分布式一致性算法的改進(jìn)

傳統(tǒng)的分布式一致性算法一直都是非拜占庭容錯(cuò)的。研究者為了突破這一桎梏在2014年提出了拜占庭容錯(cuò)的Tanga-roa算法。2016年提出了拜占庭容錯(cuò)的Raft算法，后來(lái)逐漸發(fā)展成為ScalableBFT的專用拜占庭容錯(cuò)協(xié)議。2015年提出了恒星共識(shí)協(xié)議SCP，這是第一個(gè)具有明確安全機(jī)制的，具有漸進(jìn)安全、靈活信任、低延遲和分散控制四個(gè)關(guān)鍵屬性的共識(shí)機(jī)制。同年，將Ripple和SCP共識(shí)相結(jié)合提出了法定人數(shù)投票共識(shí)算法，以應(yīng)隨需要即時(shí)交易的場(chǎng)景。2016年NEO提出了一種名為dBFT的算法，這種算法改進(jìn)了PoW和PoS最終一致性的問(wèn)題，讓區(qū)塊鏈進(jìn)軍到金融領(lǐng)域內(nèi)。2016年，提出了MgoRand的快速拜占庭容錯(cuò)共識(shí)算法，這是被認(rèn)為真正的民主和高效的分布式賬本共識(shí)技術(shù)。

3結(jié)束語(yǔ)

近年來(lái)隨著區(qū)塊鏈技術(shù)的廣泛發(fā)展，共識(shí)算法技術(shù)也越來(lái)越多地為人們所學(xué)習(xí)。未來(lái)該技術(shù)將會(huì)朝著證明方式多樣化、證明方式混合化、中心化共識(shí)需求增多以及研究合理的激勵(lì)措施等方向努力發(fā)展。相信未來(lái)區(qū)塊鏈技術(shù)將會(huì)得到更加長(zhǎng)足的進(jìn)步。