肖冰冰 李 政 李笑若 祝丙南 金晨光
(1.河南大學(xué)軟件學(xué)院 開封 475001)(2.河南省智能網(wǎng)絡(luò)理論與關(guān)鍵技術(shù)國際聯(lián)合實(shí)驗(yàn)室 開封 475001)
區(qū)塊鏈本質(zhì)是一種分布式數(shù)據(jù)庫,具有去中心化、不可篡改、可追溯、多方共同維護(hù)等特點(diǎn)[1]。它通過數(shù)字加密、共識(shí)算法、分布式存儲(chǔ)、P2P協(xié)議等多種技術(shù),共同維護(hù)全網(wǎng)數(shù)據(jù)的一致性和有效性[2~4]。通過應(yīng)用區(qū)塊鏈技術(shù),可以在互不信任的多方間無需任何第三方機(jī)構(gòu)實(shí)現(xiàn)可信、對(duì)等的價(jià)值傳輸。由于點(diǎn)對(duì)點(diǎn)網(wǎng)絡(luò)存在較高的網(wǎng)絡(luò)延遲,各個(gè)節(jié)點(diǎn)所觀察到的事物先后順序不可能完全一致,所以在基于區(qū)塊鏈技術(shù)的應(yīng)用中,最核心的問題就是如何在去中心化的環(huán)境中達(dá)成信息的一致性。
共識(shí)算法作為區(qū)塊鏈的核心技術(shù),其作用是為了解決拜占庭將軍問題,使各節(jié)點(diǎn)在沒有中心管理機(jī)構(gòu)的情況下,遵循一定的規(guī)則實(shí)現(xiàn)自治,達(dá)成提案的最終一致性。共識(shí)算法的優(yōu)劣直接影響著基于區(qū)塊鏈技術(shù)應(yīng)用系統(tǒng)的安全和性能。在2008年,中本聰在《比特幣:一種點(diǎn)對(duì)點(diǎn)式的電子現(xiàn)金系統(tǒng)》中,采用工作量證明[6](Proof of Work,PoW)解決了系統(tǒng)中存在的女巫攻擊[7]問題,實(shí)現(xiàn)了節(jié)點(diǎn)間的一致性共識(shí)。然而,以PoW為基礎(chǔ)的加密貨幣可能會(huì)遭受雙重支付攻擊。為降低風(fēng)險(xiǎn),交易的完成通常需要六個(gè)確認(rèn)區(qū)塊,這使得拒絕服務(wù)攻擊(DoS)[8]成為可能,2015年7月,即發(fā)生了一次針對(duì)比特幣網(wǎng)絡(luò)的洪泛攻擊[9]。另外,PoW資源浪費(fèi)嚴(yán)重,并且若節(jié)點(diǎn)將彼此的算力聯(lián)合組成礦池,易出現(xiàn)算力中心化和51%攻擊等問題[10]。針對(duì)PoW中的問題,Sunny King等在2012年提出了權(quán)益證明共識(shí)算法(Proof of Stake,PoS)[11],依據(jù)權(quán)益來決定節(jié)點(diǎn)獲得記賬權(quán)的概率,縮短了共識(shí)達(dá)成的時(shí)間,并減少了資源的浪費(fèi)。但PoS本質(zhì)上仍然是通過算力創(chuàng)建區(qū)塊,而且會(huì)出現(xiàn)無成本權(quán)益攻擊(Nothing of Stake)[12],分叉導(dǎo)致富者越富的問題。為解決PoS中存在的嚴(yán)重問題——富者更富和權(quán)益粉碎攻擊[13~14],NEM提出了獨(dú)特的重要性證明算法(PoI)[15]。然而,因各種環(huán)境的影響,節(jié)點(diǎn)無法保證持續(xù)穩(wěn)定在線,可能會(huì)出現(xiàn)重要性最高的節(jié)點(diǎn)因故障離線而無法正常打包記賬的問題。
本文提出一種基于斐波那契分組的重要性證明共識(shí)算法。該算法根據(jù)節(jié)點(diǎn)的重要性,利用斐波那契算法將節(jié)點(diǎn)劃分成多個(gè)小組,實(shí)現(xiàn)了分組共識(shí),提高了共識(shí)效率。通過代理權(quán)益證明共識(shí)算法(Dlegated Proof-of-stake,DPoS)在組內(nèi)投票選出負(fù)責(zé)記賬的“替補(bǔ)節(jié)點(diǎn)”,為記賬節(jié)點(diǎn)故障提供了一種災(zāi)備方案,增強(qiáng)了區(qū)塊鏈系統(tǒng)的可靠性。為了避免節(jié)點(diǎn)冷漠問題,設(shè)置了重要性獎(jiǎng)懲方案和參與創(chuàng)建區(qū)塊的最低信譽(yù)門限值,用以及時(shí)處理惡意節(jié)點(diǎn),提高了區(qū)塊鏈系統(tǒng)的安全性。實(shí)驗(yàn)結(jié)果表明,平均10s左右產(chǎn)生一個(gè)區(qū)塊,區(qū)塊的生成速率保持穩(wěn)定狀態(tài);惡意節(jié)點(diǎn)占比的增加,使得惡意節(jié)點(diǎn)成功記賬的概率減少到0.06。
PoI是重要性證明,一種基于評(píng)估個(gè)體貢獻(xiàn)在群體中的經(jīng)濟(jì)活躍度的共識(shí)算法。PoI在權(quán)益計(jì)算方面要優(yōu)于PoS,理論上解決了PoS的缺陷-富人更富的問題。PoI就像一個(gè)信譽(yù)評(píng)分系統(tǒng),系統(tǒng)給區(qū)塊鏈上的每個(gè)節(jié)點(diǎn)都分配了重要性分?jǐn)?shù)。這個(gè)分?jǐn)?shù)將影響競爭記賬權(quán)的節(jié)點(diǎn)如何“贏得”區(qū)塊鏈(記賬獲取代幣獎(jiǎng)勵(lì))。節(jié)點(diǎn)重要性得分越高,它們獲得記賬獎(jiǎng)勵(lì)的機(jī)會(huì)就越大。擁有高信譽(yù)值的節(jié)點(diǎn),意味著該節(jié)點(diǎn)更可靠,會(huì)讓其驗(yàn)證更多的交易,獲取更多的交易獎(jiǎng)勵(lì)。
無論是PoS還是PoI,依賴幣齡還是重要性決定記賬權(quán),都會(huì)導(dǎo)致記賬節(jié)點(diǎn)有過強(qiáng)的確定性,容易產(chǎn)生富者越富的情況,于是在本文中將重要性設(shè)定為一個(gè)可以動(dòng)態(tài)平衡的值,為優(yōu)化PoI設(shè)定了備選節(jié)點(diǎn)的方案,防止記賬節(jié)點(diǎn)無法正常記賬的災(zāi)備方案。
比特股(Bitshares)項(xiàng)目在2013年8月提出了DPoS,與PoS的主要區(qū)別在于節(jié)點(diǎn)選舉若干代表節(jié)點(diǎn),由代表節(jié)點(diǎn)驗(yàn)證和記賬,是一種基于投票選舉的共識(shí)算法。簡單理解,持幣人投票選舉出可信的代表節(jié)點(diǎn),由這些節(jié)點(diǎn)來運(yùn)營網(wǎng)絡(luò),行駛記賬的權(quán)限。
DPoS具有三個(gè)優(yōu)點(diǎn):1)能耗更低,DPOS機(jī)制將節(jié)點(diǎn)數(shù)量降低至101個(gè)節(jié)點(diǎn),這樣整體的能耗會(huì)變的更低;2)明顯去中心化,因?yàn)橥镀边x舉節(jié)點(diǎn)問題,所以個(gè)人挖礦的想法根本就無法實(shí)現(xiàn),所以不可能呈現(xiàn)類似于比特幣那種礦池;3)快速出塊,DPOS機(jī)制一共節(jié)點(diǎn)101個(gè),比POW節(jié)點(diǎn)數(shù)更少,記賬同步實(shí)現(xiàn)更快。
定義:斐波那契數(shù)列[17]又稱黃金分割數(shù)列,除了前兩個(gè)數(shù),其他的數(shù)都是他的前兩個(gè)數(shù)相加,需要求的是第n項(xiàng)的值,也就是第n( n>2)個(gè)數(shù)的值。斐波那契數(shù)列以如下被以遞推的方法定義,計(jì)算公式為
針對(duì)PoI中記賬節(jié)點(diǎn)確定性高,可能發(fā)生記賬節(jié)點(diǎn)無法正常記賬系統(tǒng)停滯的可能,作出以下優(yōu)化方案。
1)由于存在算力極差的節(jié)點(diǎn),將此因素考慮到重要性評(píng)估中,利用哈希計(jì)算,將上一個(gè)區(qū)塊生成的時(shí)間作為隨機(jī)數(shù)。為降低其難度來減少礦工尋找隨機(jī)數(shù)所花費(fèi)的算力,將上一個(gè)區(qū)塊生成的時(shí)間戳的后四位數(shù)字利用哈希計(jì)算設(shè)置成隨機(jī)數(shù),以獲得更快的區(qū)塊打包速度。每一個(gè)找到Nonce的節(jié)點(diǎn)立刻向全網(wǎng)廣播,記錄下每個(gè)節(jié)點(diǎn)找到Nonce的總時(shí)長并記為Ltime,作為重要性評(píng)估的一個(gè)因素。本方案設(shè)置了一個(gè)10s的時(shí)間閾值,超過時(shí)間仍沒找到隨機(jī)數(shù)的節(jié)點(diǎn)將失去重要性評(píng)估機(jī)會(huì)不參與記賬權(quán)競爭。
2)引入節(jié)點(diǎn)每輪活躍度和交易數(shù)量到重要性評(píng)估中可以有效降低冷漠節(jié)點(diǎn)打包區(qū)塊的概率。將每個(gè)節(jié)點(diǎn)在系統(tǒng)中參與區(qū)塊廣播次數(shù)作為活躍度,記錄為wValue,并將每個(gè)節(jié)點(diǎn)從上個(gè)區(qū)塊創(chuàng)建結(jié)束到評(píng)估重要性前的與自己相關(guān)的交易數(shù)量記為iTrade。
3)將信譽(yù)值引入到重要性的評(píng)估方案中來,信譽(yù)值用來反應(yīng)節(jié)點(diǎn)的誠實(shí)可靠性,每個(gè)節(jié)點(diǎn)都將被賦予一個(gè)信譽(yù)值Credit,在系統(tǒng)中節(jié)點(diǎn)的行為將決定是被扣除還是增加信譽(yù)值。信譽(yù)值的增加可以調(diào)動(dòng)節(jié)點(diǎn)挖礦的積極性,解決節(jié)點(diǎn)冷漠問題,扣除信譽(yù)值也可以降低節(jié)點(diǎn)作惡的幾率。
(1)信譽(yù)值低于50高于45時(shí),將限制5輪記賬資格;
(2)信譽(yù)值低于45高于40時(shí),將限制10輪記賬資格;
(3)信譽(yù)值低于40高于35時(shí),將限制15輪記賬資格;
(4)信譽(yù)值低于35高于30時(shí),將沒收記賬權(quán),但可以參與組內(nèi)投票;
(5)信譽(yù)值低于30分時(shí),剔除該節(jié)點(diǎn)。
重要性評(píng)估流程:各節(jié)點(diǎn)按照當(dāng)前設(shè)置的難度值通過哈希計(jì)算尋找Nonce,當(dāng)每個(gè)礦工找到隨機(jī)數(shù)時(shí)立刻向全網(wǎng)廣播,此時(shí)記錄下每個(gè)礦工尋找隨機(jī)數(shù)的時(shí)間Ltime,然后找到隨機(jī)數(shù)的節(jié)點(diǎn)結(jié)合Ltime、wValue、iTrade和Credit這四個(gè)值計(jì)算出該節(jié)點(diǎn)的重要性分?jǐn)?shù)iValue,iValue的計(jì)算公式為
Ltime/100降低了算力較強(qiáng)的節(jié)點(diǎn)獲得記賬權(quán)的幾率,增大信用值、交易量和活躍度的比重,動(dòng)態(tài)的評(píng)估了節(jié)點(diǎn)的重要性。強(qiáng)化了信用值對(duì)記賬權(quán)競爭的影響,有利于減少礦工節(jié)點(diǎn)作惡行為的發(fā)生。
節(jié)點(diǎn)競爭記賬權(quán)的過程如圖1所示。
圖1 記賬權(quán)競爭過程
在第一輪的FPoI取得共識(shí)后,每個(gè)節(jié)點(diǎn)在全網(wǎng)廣播自己的重要性分?jǐn)?shù),系統(tǒng)根據(jù)節(jié)點(diǎn)的重要性分?jǐn)?shù)給各個(gè)節(jié)點(diǎn)排名,并記錄到C-Table列表中。當(dāng)分?jǐn)?shù)最高的節(jié)點(diǎn)無法成功記賬時(shí),分?jǐn)?shù)較低的節(jié)點(diǎn)可以充當(dāng)備選節(jié)點(diǎn)。然而僅根據(jù)重要性分?jǐn)?shù)進(jìn)行排名,存在分?jǐn)?shù)相同或相差細(xì)微的可能,為了尊重重要性排名,本方案引入了一個(gè)分組策略,將分?jǐn)?shù)相近的節(jié)點(diǎn)歸入一個(gè)組內(nèi),具體的分組方式如下。
根據(jù)節(jié)點(diǎn)的重要性分?jǐn)?shù)iValue由高到低排序。
按照斐波那契數(shù)列將節(jié)點(diǎn)分組。數(shù)列中的每個(gè)數(shù)值即代表組中的節(jié)點(diǎn)個(gè)數(shù)。
采用斐波那契原理實(shí)現(xiàn)的分組有以下特征:分組數(shù)量越多,組號(hào)越大的組,組內(nèi)成員數(shù)量呈階梯式遞增。因此,本文基于斐波那契分組的算法將隨著系統(tǒng)中節(jié)點(diǎn)的增加,將大量重要性分?jǐn)?shù)較低的、排名靠后的節(jié)點(diǎn)劃分在一組內(nèi),實(shí)現(xiàn)了對(duì)低可信節(jié)點(diǎn)的集中處理。
本文采取“尊重重要性排名”來決定記賬權(quán),即分組后第一組中的節(jié)點(diǎn)獲得記賬權(quán),并設(shè)定每組中重要性分?jǐn)?shù)最高值之和的平均值為節(jié)點(diǎn)獲取驗(yàn)證權(quán)的閾值;各組內(nèi)分?jǐn)?shù)比平均值高的節(jié)點(diǎn)將參與驗(yàn)證區(qū)塊的創(chuàng)建。
當(dāng)重要性分?jǐn)?shù)最高的首節(jié)點(diǎn)無法正常記賬時(shí)則按排名向下輪流選擇備選節(jié)點(diǎn)。同組內(nèi)的節(jié)點(diǎn)的分?jǐn)?shù)值相差微小,通過借鑒DPoS思想在組內(nèi)投票,并按投票結(jié)果排名,組成一組有序的備選節(jié)點(diǎn)。當(dāng)組內(nèi)只有一個(gè)節(jié)點(diǎn)時(shí)不再進(jìn)行投票。如果仍無法選擇出可以正常記賬的節(jié)點(diǎn)時(shí),則開始進(jìn)行下一組的投票,直到選出的記賬節(jié)點(diǎn)可以正常記賬為止。
本文組內(nèi)借鑒DpoS投票策略,組內(nèi)全部節(jié)點(diǎn)合作投票,選民可以給自己投票的代表Coin抵押增加信譽(yù)值,選出的代表成功記賬后再將獎(jiǎng)勵(lì)分給抵押的選民。為了控制集中抵押,根據(jù)選民趨利性,節(jié)點(diǎn)作惡也需要抵押Coin,這樣提高了作惡成本;當(dāng)選民不參與投票時(shí),系統(tǒng)將會(huì)通過獎(jiǎng)懲方案扣除該選民的信譽(yù)值;當(dāng)代表節(jié)點(diǎn)惡意記賬時(shí),選該節(jié)點(diǎn)的節(jié)點(diǎn)抵押的Coin也會(huì)被系統(tǒng)沒收,并扣除信譽(yù)值。
當(dāng)組內(nèi)投票選出記賬節(jié)點(diǎn)后,記賬節(jié)點(diǎn)所在組全體不參與投票,剩下的組找出組內(nèi)重要性分?jǐn)?shù)最高的組節(jié)點(diǎn),計(jì)算出這些組節(jié)點(diǎn)的重要性分?jǐn)?shù)平均值,各組內(nèi)分?jǐn)?shù)比平均值高的節(jié)點(diǎn)將參與驗(yàn)證區(qū)塊的創(chuàng)建。
由于在重要性分?jǐn)?shù)評(píng)估中,信譽(yù)占比較大,將信譽(yù)值和抵押幣引入到獎(jiǎng)懲方案中,大大減少了節(jié)點(diǎn)作惡的幾率。初始系統(tǒng)將給每個(gè)節(jié)點(diǎn)分發(fā)1個(gè)抵押幣Coin用在備選節(jié)點(diǎn)投票環(huán)節(jié),誠實(shí)節(jié)點(diǎn)成功記賬將獲得信譽(yù)值獎(jiǎng)勵(lì),在備選節(jié)點(diǎn)分組內(nèi)押對(duì)代表的節(jié)點(diǎn)也將獲得信譽(yù)值獎(jiǎng)勵(lì),押到惡意節(jié)點(diǎn)的選民將被沒收抵押Coin并且扣除信譽(yù)分。當(dāng)成功記賬時(shí),各選民的抵押幣不會(huì)增長,但當(dāng)惡意節(jié)點(diǎn)記賬時(shí),抵押幣被沒收至零時(shí)信譽(yù)值已經(jīng)極低,該節(jié)點(diǎn)的記賬權(quán)與投票權(quán)都將被沒收。
1)若記賬節(jié)點(diǎn)成功創(chuàng)建的區(qū)塊被隨機(jī)函數(shù)選出的代表節(jié)點(diǎn)驗(yàn)證成功,則該節(jié)點(diǎn)獲得的獎(jiǎng)勵(lì)計(jì)算公式為
2)而在組內(nèi)參與投票并且押對(duì)誠實(shí)節(jié)點(diǎn)正常記賬的選民也將獲得信譽(yù)值獎(jiǎng)勵(lì),并將選民抵押的Coin退回,則該選民獲得的獎(jiǎng)勵(lì)計(jì)算公式為
Credit代表該節(jié)點(diǎn)被系統(tǒng)獎(jiǎng)懲前原有信譽(yù)值;Coin代表選民抵押的Coin;n代表本輪中投票的選民個(gè)數(shù)n;rCredit1代表成功記賬節(jié)點(diǎn)獲得的信譽(yù)值獎(jiǎng)勵(lì);rCredit2代表本次押對(duì)成功記賬節(jié)點(diǎn)的選民獲得的信譽(yù)值獎(jiǎng)勵(lì)。
1)當(dāng)出現(xiàn)惡意節(jié)點(diǎn)未成功創(chuàng)建正常區(qū)塊時(shí),系統(tǒng)將懲罰惡意節(jié)點(diǎn),設(shè)置信譽(yù)值的懲罰閾值接近自身信譽(yù)分?jǐn)?shù)的百分之十。懲罰方案的計(jì)算公式為
2)在組內(nèi)參與投票并且押中惡意節(jié)點(diǎn)導(dǎo)致惡意節(jié)點(diǎn)成功記賬的選民,也將受到扣除信譽(yù)值的懲罰,并且沒收抵押幣。懲罰方案的計(jì)算公式為
3)為了避免選民冷漠問題,提高選民投票積極性,在備選節(jié)點(diǎn)的組內(nèi)不參與投票的節(jié)點(diǎn)也會(huì)受到懲罰,懲罰方案的計(jì)算公式為
Credit代表該節(jié)點(diǎn)被系統(tǒng)獎(jiǎng)懲前原有信譽(yù)值;Coin是每個(gè)選民抵押的Coin;n代表本輪中投票的選民個(gè)數(shù)n;pCredit1是惡意節(jié)點(diǎn)被扣除的信譽(yù)值;pCredit2是本次押惡意節(jié)點(diǎn)導(dǎo)致惡意記賬的選民扣除的信譽(yù)值。
使用Python語言實(shí)現(xiàn)了一個(gè)區(qū)塊鏈原型,模擬出了100個(gè)節(jié)點(diǎn),對(duì)FPoI進(jìn)行了實(shí)驗(yàn)驗(yàn)證。初始時(shí),信譽(yù)值都設(shè)置為50,重要性分?jǐn)?shù)通過各個(gè)數(shù)據(jù)計(jì)算得出后利用斐波那契數(shù)列的方法分組,信譽(yù)值的獎(jiǎng)勵(lì)與懲罰通過公式計(jì)算。
為了保證區(qū)塊鏈的出塊的穩(wěn)定性,F(xiàn)PoI通過斐波那契數(shù)列來動(dòng)態(tài)調(diào)整節(jié)點(diǎn)的分組充當(dāng)節(jié)點(diǎn)無法正常記賬時(shí)的災(zāi)備方案,每組再進(jìn)行DPoS投票選出備選節(jié)點(diǎn)。為了驗(yàn)證,記錄了50個(gè)區(qū)塊出塊所花銷的時(shí)間,統(tǒng)計(jì)后得到的結(jié)果如圖2所示。從實(shí)驗(yàn)結(jié)果可以看出,曲線波動(dòng)幅度不大,基本都在10s上下,可以證明FPoS共識(shí)機(jī)制下出快速度的穩(wěn)定保持在10s左右。
圖2 50個(gè)區(qū)塊的出塊時(shí)間
圖3中的實(shí)驗(yàn)?zāi)康氖菍?00個(gè)節(jié)點(diǎn)節(jié)點(diǎn)用斐波那契按重要性排名分組后,統(tǒng)計(jì)各組內(nèi)個(gè)各節(jié)點(diǎn)的出塊概率。從而得出以下結(jié)論:區(qū)塊鏈系統(tǒng)對(duì)重要性分?jǐn)?shù)排名第一的節(jié)點(diǎn)來說,通過FPoI共識(shí)算法可以得到充分保障,系統(tǒng)中其他節(jié)點(diǎn)獲得記賬權(quán)的概率也會(huì)隨著分?jǐn)?shù)高低的分組而明顯不同。因此,F(xiàn)PoI共識(shí)算法區(qū)塊鏈系統(tǒng)來說具有良好的適應(yīng)性。
圖3 每組各節(jié)點(diǎn)記賬的概率
從圖4可以看出,在惡意節(jié)點(diǎn)占比30%、50%、70%的情況下,即使惡意節(jié)點(diǎn)獲得了記賬資格,但參與驗(yàn)證的節(jié)點(diǎn)驗(yàn)證不通過,惡意節(jié)點(diǎn)成功記賬的概率也極小。隨著惡意節(jié)點(diǎn)占比從30%增加到70%,惡意節(jié)點(diǎn)成功記賬的概率也由0.25減小到0.06,極大降低了惡意節(jié)點(diǎn)通過聯(lián)盟獲得成功記賬的可能性。
圖4 惡意節(jié)點(diǎn)獲得記賬權(quán)后記賬成功的次數(shù)
共識(shí)算法作為區(qū)塊鏈的核心,解決了分布式一致性的問題。本文對(duì)現(xiàn)有共識(shí)算法的研究和改進(jìn),提出的一種利用斐波那契方式分組的重要性證明算法,是對(duì)重要性算法提出的災(zāi)備方案。并且通過實(shí)驗(yàn)對(duì)改進(jìn)的共識(shí)機(jī)制的可行性和性能進(jìn)行了分析和驗(yàn)證,實(shí)驗(yàn)結(jié)果證明FPoI極大降低了惡意節(jié)點(diǎn)成功記賬的可能,出塊平均時(shí)間穩(wěn)定在10s左右。進(jìn)一步工作為研究更好的重要性評(píng)估因素來確保公平性和更好的分組方式提高效率。