基于斐波那契分組的重要性證明共識算法*

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

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

1 引言

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

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

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

2 預備工作

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

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

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

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

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

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

2.3 斐波那契數列

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

3 FPoI共識機制算法設計

3.1 優化PoI重要性評估部分

針對PoI中記賬節點確定性高，可能發生記賬節點無法正常記賬系統停滯的可能，作出以下優化方案。

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

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

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

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

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

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

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

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

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

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

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

圖1 記賬權競爭過程

3.2 斐波那契分組策略

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

根據節點的重要性分數iValue由高到低排序。

按照斐波那契數列將節點分組。數列中的每個數值即代表組中的節點個數。

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

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

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

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

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

4 引入信譽值的獎懲方案

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

4.1 獎勵方案

1）若記賬節點成功創建的區塊被隨機函數選出的代表節點驗證成功，則該節點獲得的獎勵計算公式為

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

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

4.2 懲罰方案

1）當出現惡意節點未成功創建正常區塊時，系統將懲罰惡意節點，設置信譽值的懲罰閾值接近自身信譽分數的百分之十。懲罰方案的計算公式為

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

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

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

5 實驗結果與分析

5.1 實驗環境

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

5.2 FPoI的出塊穩定性

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

圖2 50個區塊的出塊時間

5.3 重要性分組出塊概率

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

圖3 每組各節點記賬的概率

5.4 安全性分析

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

圖4 惡意節點獲得記賬權后記賬成功的次數

6 結語

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