肖冰冰 李 政 李笑若 祝丙南 金晨光

（1.河南大學軟件學院 開封 475001）（2.河南省智能網絡理論與關鍵技術國際聯(lián)合實驗室 開封 475001）

1 引言

區(qū)塊鏈本質是一種分布式數(shù)據(jù)庫，具有去中心化、不可篡改、可追溯、多方共同維護等特點［1］。它通過數(shù)字加密、共識算法、分布式存儲、P2P協(xié)議等多種技術，共同維護全網數(shù)據(jù)的一致性和有效性［2~4］。通過應用區(qū)塊鏈技術，可以在互不信任的多方間無需任何第三方機構實現(xiàn)可信、對等的價值傳輸。由于點對點網絡存在較高的網絡延遲，各個節(jié)點所觀察到的事物先后順序不可能完全一致，所以在基于區(qū)塊鏈技術的應用中，最核心的問題就是如何在去中心化的環(huán)境中達成信息的一致性。

共識算法作為區(qū)塊鏈的核心技術，其作用是為了解決拜占庭將軍問題，使各節(jié)點在沒有中心管理機構的情況下，遵循一定的規(guī)則實現(xiàn)自治，達成提案的最終一致性。共識算法的優(yōu)劣直接影響著基于區(qū)塊鏈技術應用系統(tǒng)的安全和性能。在2008年，中本聰在《比特幣：一種點對點式的電子現(xiàn)金系統(tǒng)》中，采用工作量證明［6］（Proof of Work，PoW）解決了系統(tǒng)中存在的女巫攻擊［7］問題，實現(xiàn)了節(jié)點間的一致性共識。然而，以PoW為基礎的加密貨幣可能會遭受雙重支付攻擊。為降低風險，交易的完成通常需要六個確認區(qū)塊，這使得拒絕服務攻擊（DoS）［8］成為可能，2015年7月，即發(fā)生了一次針對比特幣網絡的洪泛攻擊［9］。另外，PoW資源浪費嚴重，并且若節(jié)點將彼此的算力聯(lián)合組成礦池，易出現(xiàn)算力中心化和51%攻擊等問題［10］。針對PoW中的問題，Sunny King等在2012年提出了權益證明共識算法（Proof of Stake，PoS）［11］，依據(jù)權益來決定節(jié)點獲得記賬權的概率，縮短了共識達成的時間，并減少了資源的浪費。但PoS本質上仍然是通過算力創(chuàng)建區(qū)塊，而且會出現(xiàn)無成本權益攻擊（Nothing of Stake）［12］，分叉導致富者越富的問題。為解決PoS中存在的嚴重問題——富者更富和權益粉碎攻擊［13~14］，NEM提出了獨特的重要性證明算法（PoI）［15］。然而，因各種環(huán)境的影響，節(jié)點無法保證持續(xù)穩(wěn)定在線，可能會出現(xiàn)重要性最高的節(jié)點因故障離線而無法正常打包記賬的問題。

本文提出一種基于斐波那契分組的重要性證明共識算法。該算法根據(jù)節(jié)點的重要性，利用斐波那契算法將節(jié)點劃分成多個小組，實現(xiàn)了分組共識，提高了共識效率。通過代理權益證明共識算法（Dlegated Proof-of-stake，DPoS）在組內投票選出負責記賬的“替補節(jié)點”，為記賬節(jié)點故障提供了一種災備方案，增強了區(qū)塊鏈系統(tǒng)的可靠性。為了避免節(jié)點冷漠問題，設置了重要性獎懲方案和參與創(chuàng)建區(qū)塊的最低信譽門限值，用以及時處理惡意節(jié)點，提高了區(qū)塊鏈系統(tǒng)的安全性。實驗結果表明，平均10s左右產生一個區(qū)塊，區(qū)塊的生成速率保持穩(wěn)定狀態(tài)；惡意節(jié)點占比的增加，使得惡意節(jié)點成功記賬的概率減少到0.06。

2 預備工作

2.1 重要性證明共識算法（Proof of Importance，PoI）

PoI是重要性證明，一種基于評估個體貢獻在群體中的經濟活躍度的共識算法。PoI在權益計算方面要優(yōu)于PoS，理論上解決了PoS的缺陷-富人更富的問題。PoI就像一個信譽評分系統(tǒng)，系統(tǒng)給區(qū)塊鏈上的每個節(jié)點都分配了重要性分數(shù)。這個分數(shù)將影響競爭記賬權的節(jié)點如何“贏得”區(qū)塊鏈（記賬獲取代幣獎勵）。節(jié)點重要性得分越高，它們獲得記賬獎勵的機會就越大。擁有高信譽值的節(jié)點，意味著該節(jié)點更可靠，會讓其驗證更多的交易，獲取更多的交易獎勵。

無論是PoS還是PoI，依賴幣齡還是重要性決定記賬權，都會導致記賬節(jié)點有過強的確定性，容易產生富者越富的情況，于是在本文中將重要性設定為一個可以動態(tài)平衡的值，為優(yōu)化PoI設定了備選節(jié)點的方案，防止記賬節(jié)點無法正常記賬的災備方案。

2.2 代理權益證明共識算法（Dlegated Proof-ofstake，DPoS）

比特股（Bitshares）項目在2013年8月提出了DPoS，與PoS的主要區(qū)別在于節(jié)點選舉若干代表節(jié)點，由代表節(jié)點驗證和記賬，是一種基于投票選舉的共識算法。簡單理解，持幣人投票選舉出可信的代表節(jié)點，由這些節(jié)點來運營網絡，行駛記賬的權限。

DPoS具有三個優(yōu)點：1）能耗更低，DPOS機制將節(jié)點數(shù)量降低至101個節(jié)點，這樣整體的能耗會變的更低；2）明顯去中心化，因為投票選舉節(jié)點問題，所以個人挖礦的想法根本就無法實現(xiàn)，所以不可能呈現(xiàn)類似于比特幣那種礦池；3）快速出塊，DPOS機制一共節(jié)點101個，比POW節(jié)點數(shù)更少，記賬同步實現(xiàn)更快。

2.3 斐波那契數(shù)列

定義：斐波那契數(shù)列［17］又稱黃金分割數(shù)列，除了前兩個數(shù)，其他的數(shù)都是他的前兩個數(shù)相加，需要求的是第n項的值，也就是第n( n>2)個數(shù)的值。斐波那契數(shù)列以如下被以遞推的方法定義，計算公式為

3 FPoI共識機制算法設計

3.1 優(yōu)化PoI重要性評估部分

針對PoI中記賬節(jié)點確定性高，可能發(fā)生記賬節(jié)點無法正常記賬系統(tǒng)停滯的可能，作出以下優(yōu)化方案。

1）由于存在算力極差的節(jié)點，將此因素考慮到重要性評估中，利用哈希計算，將上一個區(qū)塊生成的時間作為隨機數(shù)。為降低其難度來減少礦工尋找隨機數(shù)所花費的算力，將上一個區(qū)塊生成的時間戳的后四位數(shù)字利用哈希計算設置成隨機數(shù)，以獲得更快的區(qū)塊打包速度。每一個找到Nonce的節(jié)點立刻向全網廣播，記錄下每個節(jié)點找到Nonce的總時長并記為Ltime，作為重要性評估的一個因素。本方案設置了一個10s的時間閾值，超過時間仍沒找到隨機數(shù)的節(jié)點將失去重要性評估機會不參與記賬權競爭。

2）引入節(jié)點每輪活躍度和交易數(shù)量到重要性評估中可以有效降低冷漠節(jié)點打包區(qū)塊的概率。將每個節(jié)點在系統(tǒng)中參與區(qū)塊廣播次數(shù)作為活躍度，記錄為wValue，并將每個節(jié)點從上個區(qū)塊創(chuàng)建結束到評估重要性前的與自己相關的交易數(shù)量記為iTrade。

3）將信譽值引入到重要性的評估方案中來，信譽值用來反應節(jié)點的誠實可靠性，每個節(jié)點都將被賦予一個信譽值Credit，在系統(tǒng)中節(jié)點的行為將決定是被扣除還是增加信譽值。信譽值的增加可以調動節(jié)點挖礦的積極性，解決節(jié)點冷漠問題，扣除信譽值也可以降低節(jié)點作惡的幾率。

（1）信譽值低于50高于45時，將限制5輪記賬資格；

（2）信譽值低于45高于40時，將限制10輪記賬資格；

（3）信譽值低于40高于35時，將限制15輪記賬資格；

（4）信譽值低于35高于30時，將沒收記賬權，但可以參與組內投票；

（5）信譽值低于30分時，剔除該節(jié)點。

重要性評估流程：各節(jié)點按照當前設置的難度值通過哈希計算尋找Nonce，當每個礦工找到隨機數(shù)時立刻向全網廣播，此時記錄下每個礦工尋找隨機數(shù)的時間Ltime，然后找到隨機數(shù)的節(jié)點結合Ltime、wValue、iTrade和Credit這四個值計算出該節(jié)點的重要性分數(shù)iValue，iValue的計算公式為

Ltime/100降低了算力較強的節(jié)點獲得記賬權的幾率，增大信用值、交易量和活躍度的比重，動態(tài)的評估了節(jié)點的重要性。強化了信用值對記賬權競爭的影響，有利于減少礦工節(jié)點作惡行為的發(fā)生。

節(jié)點競爭記賬權的過程如圖1所示。

圖1 記賬權競爭過程

3.2 斐波那契分組策略

在第一輪的FPoI取得共識后，每個節(jié)點在全網廣播自己的重要性分數(shù)，系統(tǒng)根據(jù)節(jié)點的重要性分數(shù)給各個節(jié)點排名，并記錄到C-Table列表中。當分數(shù)最高的節(jié)點無法成功記賬時，分數(shù)較低的節(jié)點可以充當備選節(jié)點。然而僅根據(jù)重要性分數(shù)進行排名，存在分數(shù)相同或相差細微的可能，為了尊重重要性排名，本方案引入了一個分組策略，將分數(shù)相近的節(jié)點歸入一個組內，具體的分組方式如下。

根據(jù)節(jié)點的重要性分數(shù)iValue由高到低排序。

按照斐波那契數(shù)列將節(jié)點分組。數(shù)列中的每個數(shù)值即代表組中的節(jié)點個數(shù)。

采用斐波那契原理實現(xiàn)的分組有以下特征：分組數(shù)量越多，組號越大的組，組內成員數(shù)量呈階梯式遞增。因此，本文基于斐波那契分組的算法將隨著系統(tǒng)中節(jié)點的增加，將大量重要性分數(shù)較低的、排名靠后的節(jié)點劃分在一組內，實現(xiàn)了對低可信節(jié)點的集中處理。

本文采取“尊重重要性排名”來決定記賬權，即分組后第一組中的節(jié)點獲得記賬權，并設定每組中重要性分數(shù)最高值之和的平均值為節(jié)點獲取驗證權的閾值；各組內分數(shù)比平均值高的節(jié)點將參與驗證區(qū)塊的創(chuàng)建。

當重要性分數(shù)最高的首節(jié)點無法正常記賬時則按排名向下輪流選擇備選節(jié)點。同組內的節(jié)點的分數(shù)值相差微小，通過借鑒DPoS思想在組內投票，并按投票結果排名，組成一組有序的備選節(jié)點。當組內只有一個節(jié)點時不再進行投票。如果仍無法選擇出可以正常記賬的節(jié)點時，則開始進行下一組的投票，直到選出的記賬節(jié)點可以正常記賬為止。

本文組內借鑒DpoS投票策略，組內全部節(jié)點合作投票，選民可以給自己投票的代表Coin抵押增加信譽值，選出的代表成功記賬后再將獎勵分給抵押的選民。為了控制集中抵押，根據(jù)選民趨利性，節(jié)點作惡也需要抵押Coin，這樣提高了作惡成本；當選民不參與投票時，系統(tǒng)將會通過獎懲方案扣除該選民的信譽值；當代表節(jié)點惡意記賬時，選該節(jié)點的節(jié)點抵押的Coin也會被系統(tǒng)沒收，并扣除信譽值。

當組內投票選出記賬節(jié)點后，記賬節(jié)點所在組全體不參與投票，剩下的組找出組內重要性分數(shù)最高的組節(jié)點，計算出這些組節(jié)點的重要性分數(shù)平均值，各組內分數(shù)比平均值高的節(jié)點將參與驗證區(qū)塊的創(chuàng)建。

4 引入信譽值的獎懲方案

由于在重要性分數(shù)評估中，信譽占比較大，將信譽值和抵押幣引入到獎懲方案中，大大減少了節(jié)點作惡的幾率。初始系統(tǒng)將給每個節(jié)點分發(fā)1個抵押幣Coin用在備選節(jié)點投票環(huán)節(jié)，誠實節(jié)點成功記賬將獲得信譽值獎勵，在備選節(jié)點分組內押對代表的節(jié)點也將獲得信譽值獎勵，押到惡意節(jié)點的選民將被沒收抵押Coin并且扣除信譽分。當成功記賬時，各選民的抵押幣不會增長，但當惡意節(jié)點記賬時，抵押幣被沒收至零時信譽值已經極低，該節(jié)點的記賬權與投票權都將被沒收。

4.1 獎勵方案

1）若記賬節(jié)點成功創(chuàng)建的區(qū)塊被隨機函數(shù)選出的代表節(jié)點驗證成功，則該節(jié)點獲得的獎勵計算公式為

2）而在組內參與投票并且押對誠實節(jié)點正常記賬的選民也將獲得信譽值獎勵，并將選民抵押的Coin退回，則該選民獲得的獎勵計算公式為

Credit代表該節(jié)點被系統(tǒng)獎懲前原有信譽值；Coin代表選民抵押的Coin；n代表本輪中投票的選民個數(shù)n；rCredit1代表成功記賬節(jié)點獲得的信譽值獎勵；rCredit2代表本次押對成功記賬節(jié)點的選民獲得的信譽值獎勵。

4.2 懲罰方案

1）當出現(xiàn)惡意節(jié)點未成功創(chuàng)建正常區(qū)塊時，系統(tǒng)將懲罰惡意節(jié)點，設置信譽值的懲罰閾值接近自身信譽分數(shù)的百分之十。懲罰方案的計算公式為

2）在組內參與投票并且押中惡意節(jié)點導致惡意節(jié)點成功記賬的選民，也將受到扣除信譽值的懲罰，并且沒收抵押幣。懲罰方案的計算公式為

3）為了避免選民冷漠問題，提高選民投票積極性，在備選節(jié)點的組內不參與投票的節(jié)點也會受到懲罰，懲罰方案的計算公式為

Credit代表該節(jié)點被系統(tǒng)獎懲前原有信譽值；Coin是每個選民抵押的Coin；n代表本輪中投票的選民個數(shù)n；pCredit1是惡意節(jié)點被扣除的信譽值；pCredit2是本次押惡意節(jié)點導致惡意記賬的選民扣除的信譽值。

5 實驗結果與分析

5.1 實驗環(huán)境

使用Python語言實現(xiàn)了一個區(qū)塊鏈原型，模擬出了100個節(jié)點，對FPoI進行了實驗驗證。初始時，信譽值都設置為50，重要性分數(shù)通過各個數(shù)據(jù)計算得出后利用斐波那契數(shù)列的方法分組，信譽值的獎勵與懲罰通過公式計算。

5.2 FPoI的出塊穩(wěn)定性

為了保證區(qū)塊鏈的出塊的穩(wěn)定性，F(xiàn)PoI通過斐波那契數(shù)列來動態(tài)調整節(jié)點的分組充當節(jié)點無法正常記賬時的災備方案，每組再進行DPoS投票選出備選節(jié)點。為了驗證，記錄了50個區(qū)塊出塊所花銷的時間，統(tǒng)計后得到的結果如圖2所示。從實驗結果可以看出，曲線波動幅度不大，基本都在10s上下，可以證明FPoS共識機制下出快速度的穩(wěn)定保持在10s左右。

圖2 50個區(qū)塊的出塊時間

5.3 重要性分組出塊概率

圖3中的實驗目的是將100個節(jié)點節(jié)點用斐波那契按重要性排名分組后，統(tǒng)計各組內個各節(jié)點的出塊概率。從而得出以下結論：區(qū)塊鏈系統(tǒng)對重要性分數(shù)排名第一的節(jié)點來說，通過FPoI共識算法可以得到充分保障，系統(tǒng)中其他節(jié)點獲得記賬權的概率也會隨著分數(shù)高低的分組而明顯不同。因此，F(xiàn)PoI共識算法區(qū)塊鏈系統(tǒng)來說具有良好的適應性。

圖3 每組各節(jié)點記賬的概率

5.4 安全性分析

從圖4可以看出，在惡意節(jié)點占比30%、50%、70%的情況下，即使惡意節(jié)點獲得了記賬資格，但參與驗證的節(jié)點驗證不通過，惡意節(jié)點成功記賬的概率也極小。隨著惡意節(jié)點占比從30%增加到70%，惡意節(jié)點成功記賬的概率也由0.25減小到0.06，極大降低了惡意節(jié)點通過聯(lián)盟獲得成功記賬的可能性。

圖4 惡意節(jié)點獲得記賬權后記賬成功的次數(shù)

6 結語

共識算法作為區(qū)塊鏈的核心，解決了分布式一致性的問題。本文對現(xiàn)有共識算法的研究和改進，提出的一種利用斐波那契方式分組的重要性證明算法，是對重要性算法提出的災備方案。并且通過實驗對改進的共識機制的可行性和性能進行了分析和驗證，實驗結果證明FPoI極大降低了惡意節(jié)點成功記賬的可能，出塊平均時間穩(wěn)定在10s左右。進一步工作為研究更好的重要性評估因素來確保公平性和更好的分組方式提高效率。