基于可信性評估的區(qū)塊鏈共識機制的研究

王 冠， 張文月

(1.北京工業(yè)大學 信息學部 北京 100124； 2.可信計算北京市重點實驗室 北京 100124)

0 引言

在區(qū)塊鏈中，每個節(jié)點都是獨立的，具有自治性。不同的節(jié)點維護著內(nèi)容相同的區(qū)塊鏈賬本，同時也各自獨立地將網(wǎng)絡中產(chǎn)生的新的交易打包成一個區(qū)塊，并廣播給其他節(jié)點。區(qū)塊鏈是線性的，所以同一時期只有一個新打包的區(qū)塊能加入主鏈，以保證數(shù)據(jù)的一致性，因此，如何選擇區(qū)塊是區(qū)塊鏈共識的重要任務之一。這個過程又稱為如何分配記賬權[1]。

基于算力的共識算法存在許多弱點，包括弱一致性、低交易吞吐量和一些共識攻擊，比如51%攻擊(可以導致雙重攻擊[2-3],私自挖礦[4-5])，它意味著當算力達到51%這個閾值時，這種攻擊幾乎可以成功。

現(xiàn)有的基于算力，即工作量證明的區(qū)塊鏈系統(tǒng)都依賴于這樣的假設：攻擊者不能擁有超過33%或者51%的算力，然而隨著比特幣攻擊的復雜性，這個假設有可能不再成立。以SHA256哈希算法為例，產(chǎn)生這個算法的哈希碰撞需要248年，但是隨著量子計算機技術的發(fā)展，此哈希算法有可能會在有限時間內(nèi)被破解[6]?；谒懔Φ墓沧R算法在安全性和性能方面已經(jīng)有了一些改進。有一種利用基于歷史行為的信任值來代替算力的共識算法的機制[7-8]，此機制可以根據(jù)歷史行為檢測惡意節(jié)點，降低惡意節(jié)點爭奪記賬權的成功率。此機制只是對特定的行為(比如身為領導者卻沒有在規(guī)定時間內(nèi)打包新區(qū)塊)進行監(jiān)測，以此來決定每個節(jié)點的信任值，但由于簡單，不適用于復雜的應用場景。文獻[9]提出的Byzcoin共識算法建立在Bitcoin-NG和實用拜占庭容錯算法(practical Byzantine fault tolerance,PBFT)的基礎上。在Byzcoin算法中，經(jīng)過挖掘找到密鑰塊的節(jié)點在有限時間內(nèi)會成為見證人，每次創(chuàng)造一個新的密鑰塊時，都會通過一組見證人之間的PBFT視圖變更協(xié)議選出新的領導者。新領導者每隔幾秒就會提交一個包含新交易的區(qū)塊。如果一組見證人已經(jīng)通過驗證并同意微塊，則領導者提交微塊。協(xié)議本質(zhì)上是一個兩階段的PBFT協(xié)議，通過集體簽名的方案取代了MAC(media access control)認證。通過這種方式，每次創(chuàng)建新的密鑰塊時，證人組基于其計算能力動態(tài)地形成新的領導者，并且每隔幾秒就可以提交一個包含一組事物、并且有足夠數(shù)量證人集體簽字的微塊。當領導者是惡意的并且不產(chǎn)生微塊，雖然Byzcoin可以檢測到它，但是卻沒有其他懲罰，不能阻止其再次成為領導者。所以，Byzcoin遭受共識攻擊的成本是相同的。

本文在現(xiàn)有的基于算力的共識機制的基礎上，提出了一種基于可信性評估的區(qū)塊鏈共識機制，并提出了一種節(jié)點信任值評估算法，經(jīng)過性能測試和安全性分析，表明本文的共識機制對于基于算力的攻擊成本遠超過現(xiàn)有的共識算法。

1 基于可信性評估的區(qū)塊鏈共識機制

共識機制的工作流程為：通過對節(jié)點區(qū)塊鏈的可信性進行評估得到每個節(jié)點的信任值，根據(jù)信任值隨機動態(tài)選出共識組，經(jīng)過工作證明共識挖掘到的密鑰塊決定共識組中成為此輪的領導者的成員，領導者發(fā)布包含交易的微塊，共識組通過改進多重簽名共識算法與領導者達成共識。

為了抵御基于算力的攻擊，本機制采用信任值代替算力進行記賬權的爭奪。首先按照信任值排名，當信任值達到一定的閾值，才可能被隨機選中進入共識組。用信任值代替算力，這樣保證了一個節(jié)點的投票能力是取決于它的綜合表現(xiàn)，而不是某一瞬間的計算能力，而它的綜合表現(xiàn)需要長時間有規(guī)律的工作。只有誠實的節(jié)點，表現(xiàn)正常并且有規(guī)律，才可能成為共識組的一員。所以，即使算力很高的節(jié)點，如果進入系統(tǒng)不久也無法攻擊系統(tǒng)。共識組中會有一節(jié)點被隨機選中成為領導者，領導者可以產(chǎn)生微塊對交易進行打包，其他節(jié)點對微塊進行共識，此輪工作結束，開始下一輪領導者的選舉。

本機制中區(qū)塊鏈由一個個大塊串聯(lián)而成，其中每個大塊由兩種區(qū)塊組成，密鑰塊和微塊。其中大塊中密鑰塊的數(shù)量和微塊數(shù)量都是固定和提前預設的。大塊即區(qū)塊鏈中的區(qū)塊，它包含了固定個數(shù)的密鑰塊和微塊。只是它不包含隨機數(shù)，任何人都可以產(chǎn)生大塊。密鑰塊用于確定領導人。一個秘鑰塊由5個域構成：前一個密鑰塊的散列值；隨機數(shù)；節(jié)點的公鑰；產(chǎn)生這個密鑰塊的節(jié)點的信任值；該塊的散列值。共識組組員通過檢查該塊的散列值的有效性驗證密鑰塊。微塊是一個簡單的塊，每隔幾秒就會驗證一次，包括驗證歷史交易。為了防止雙重支出，每個微塊在被接受之前都要被提議給共識組，如果微塊被驗證成功，則會成為區(qū)塊鏈的一部分。微塊由5個域構成：當前與其對應的密鑰塊的散列值；前一個固定在區(qū)塊鏈中的微塊的哈希值；一組Merkle樹的交易；前三者的散列值；來自共識的簽名。為了驗證微塊的有效性，共識組成員檢查Msig的有效性，驗證密鑰塊和前面的微塊的散列值，并驗證交易TXs。

2 信任值評估算法

2.1 信任值設計原則

通過信任值計算，想要成為領導者不僅要創(chuàng)建足夠的密鑰塊，還要表明其誠實有規(guī)律地工作，每個節(jié)點通過區(qū)塊鏈維護自己的信任值副本。用R來表示信任值，R∈[0,1]。信任值在每一輪開始時，即新的密鑰塊被創(chuàng)建時，都會被更新。信任值的計算要符合社會對系統(tǒng)的3個要求：1) 初期的增長要緩慢；2) 進入一段時間后，通過快速增長信任值，鼓勵它參與共識；3) 后期要緩慢增加防止壟斷現(xiàn)象。

信任值通過節(jié)點對系統(tǒng)的工作量和工作的規(guī)律性進行計算。通過信任值機制，除了創(chuàng)建足夠的近期密鑰塊之外，節(jié)點還必須表明它已經(jīng)誠實地工作一段時間了。本文中的信任評估算法包括內(nèi)部評估和外部評估；內(nèi)部評估表示對節(jié)點的歷史行為表現(xiàn)進行評估，主要從貢獻率和工作規(guī)律性進行評估；外部評估則從與其進行歷史交易的節(jié)點進行評估。

2.2 內(nèi)部信任值計算

內(nèi)部信任值主要表現(xiàn)為節(jié)點對區(qū)塊鏈的貢獻率和工作的規(guī)律性。貢獻率可以用其生產(chǎn)的密鑰塊的個數(shù)決定，規(guī)律性可用其作為領導者所產(chǎn)生的微塊數(shù)量決定。信任值的算法如下。

輸入：L,本輪生產(chǎn)的所有密鑰塊k,微塊m,c,a,λ

輸出： 節(jié)點的信任值R，R∈[0,1]。

5)y1=meank/(1+sm)。

6) ifNl≥1 theny2=meanm/(1+sk)。

7) elsey2=1。

8) end if。

9)x=y1y2L。

上述算法中符號L代表當前區(qū)塊鏈的長度；c代表大塊的大小，大塊中包含系統(tǒng)預先定義數(shù)量的密鑰塊；t代表區(qū)塊鏈中包含的大塊數(shù)量；Ki代表在第i個大塊中節(jié)點創(chuàng)造的密鑰塊數(shù)量；Nl代表節(jié)點被選為領導者的次數(shù)；mj代表在第j輪節(jié)點所生產(chǎn)的微塊被驗證成功的數(shù)量；m代表一個領導者被預定的生成的微塊數(shù)；meani代表由一個節(jié)點或一個領導者在區(qū)塊鏈中創(chuàng)建的密鑰塊(如果i為k)或微塊(如果i為m)的平均值；Si對應平均值的標準差；(a，λ)為系統(tǒng)參數(shù)。

f(x)是一個sigmoid函數(shù)。它確保節(jié)點一開始只能慢慢增加信任值，即使擁有強大的計算能力，一個節(jié)點需要經(jīng)過一段時間的工作，逐步將其信任值提升到轉(zhuǎn)折點，到達轉(zhuǎn)折點的節(jié)點可以證明它足以被信任，信任值增長變快。最后，隨著信任值增加，信任曲線趨于穩(wěn)定，有利于促進節(jié)點之間的權力平衡。信任值函數(shù)也有一些參數(shù)，參數(shù)(a，λ)可以用來調(diào)節(jié)信任值變化的快慢。f(x)的斜率與λ的值直接相關。

因此，節(jié)點的綜合能力是由節(jié)點在其活動期間完成的有效工作總量,以及整個區(qū)塊鏈中該工作的規(guī)律性給出的，而不是節(jié)點在給定時間的采礦能力。所以，當系統(tǒng)運行一段時間后，即使是具有強大計算能力的節(jié)點也無法迅速建立其信任值，它需要誠實而有規(guī)律地為系統(tǒng)做出貢獻，以獲得信任值。

2.3 外部信任值計算

本文從信任的主觀性與不確定性入手提出了外部信任值的計算方法，引入b、d、u3個變量來描述節(jié)點的信任關系，這些變量由交易產(chǎn)生的評價計算所得：b表示對目標節(jié)點的信任度；d表示對目標節(jié)點不信任度；u表示不確定目標節(jié)點的信任程度。3個變量滿足公式b+d+u=1,{b,d,u}∈[0,1]。

在現(xiàn)在研究中不確定因子wc被設置為常數(shù)，忽略了網(wǎng)絡環(huán)境中的不確定因素。本文中設置不確定因子wc與實體間的交互事件相關，計算方法為wc=E-(r+s)；b、d、u的計算公式為b=r/(r+ps+wc)；d=ps/(r+ps+wc)；u=wc/(r+ps+wc),其中p表示對節(jié)點否定事件的懲罰因子，取值大于1。實體的否定行為能夠增大信任觀念空間中的不信任程度，從而實現(xiàn)了對實體否定行為的懲罰機制?；谏鲜霰硎拘湃侮P系的三元組，共識組對節(jié)點的外部信任計算公式為

Ext=b+u/2=(r+E-s)/2(ps+E-s)，

(1)

其中：Ext為外部信任值，由與其進行歷史交互的節(jié)點對其進行信任評價。在本文中，我們定義外部信任值落在[0,1]區(qū)間。信任值為1表示目標節(jié)點完全信任；為0.5則表示無法判斷目標節(jié)點的可信度；為0則表示目標節(jié)點不可信。我們把默認外部信任值設為0.5。r表示關于目標節(jié)點的肯定事件數(shù)；s表示否定事件數(shù)；E為節(jié)點的交易數(shù)。

從式(1)可以看出，外部信任值隨著肯定事件r的增大而增大，隨著否定事件s的減小而減小。而且如果p的取值增大，則外部信任值會減小。因此，最終的信任值R的表達式為R=min(1,f(x)+γ(Ext-0.5))，如果R值為負數(shù)，則直接取0，其中γ為內(nèi)部和外部信任值所占的比例。

3 評估

3.1 性能評估

共識延遲表示交易在構建完成到上鏈的時間。上鏈意味著交易被各個節(jié)點接受、確認。因為本算法每輪只有一位領導者產(chǎn)生，并且每輪發(fā)布的微塊數(shù)量固定，所以本共識算法不會產(chǎn)生分叉，每筆交易達到共識要求即被認為可以上鏈。該時間是衡量共識算法的重要性能指標，用TTXreach表示，TTXreach=TTXBroadcast+TConsensus，其中：TTXBroadcast表示共識從創(chuàng)建到被共識組的成員接收的時間；TConsensus表示共識組的成員與領導者達成共識的時間。

圖1 共識延遲時間Figure 1 Delay time of consensus

為了達成共識，要求至少一半成員就價值達成一致。我們使用大小為1 KB的密鑰塊和大小為512 KB、1 MB、2 MB和4 MB的微塊進行實驗。與微塊不同，密鑰塊通常很小，因為它們不包含任何交易。圖1表明共識延遲隨著塊大小而顯著增加。這種趨勢背后的原因有兩點：領導者向共識組提出微塊需要更長的時間；計算較大塊的哈希值并驗證其包含的交易會消耗更多時間。此外，本共識機制中，當組大小從4增加到16時，共識延遲增加超過50%。雖然延遲增加，但即使在考慮大小為4 MB的塊時，也可以在約0.5～1.2秒內(nèi)達到共識。而以太坊需要15秒的出塊時間，比特幣需要10分鐘出塊時間?；诜植婵紤]，它們還需要后續(xù)多個區(qū)塊上鏈之后才能確認區(qū)塊真正被上鏈，因此以太坊和區(qū)塊鏈的交易時間遠遠高于本共識機制。

吞吐量是衡量共識算法處理交易效率的重要指標。吞吐量表示每秒處理的交易數(shù)量，是交易被創(chuàng)建到確認上鏈的區(qū)塊鏈的交易數(shù)量與此輪時間的比，計算公式為TPSΔt=(TtotalTXΔt)/Δt，其中：Δt表示一輪共識所用時間，即從一位領導者到下一位領導者選舉所耗費的時間；TotalTXΔt表示該時間上鏈的微塊包含的交易數(shù)量。由圖2可見，微塊和共識組的大小直接影響吞吐量。共識組越小，吞吐量越高，達成共識的難度和時間都會減少，上鏈的區(qū)塊越多，吞吐量越高。

3.2 信任值分布

1) 外部信任值分析。首先可以固定外部信任值計算方法中wc和E，即確認肯定事件r與否定事件s的和，然后依次隨機增加肯定事件r和否定事件s到指定數(shù)量，并且使不信任程度d增大。圖3為所選的節(jié)點隨著不信任程度d的增加，信任值的變化情況。由3.1節(jié)的吞吐量測試可知，當微塊大小為4 MB、共識組成員為4時，本共識機制吞吐量可以到達2 000 TPS,我們可以設E=20 000，wc=5 000，隨著r與s的增長，重復試驗次數(shù)100次，信任值變化如圖3所示。

圖2 吞吐量Figure 2 Throughput

圖3 懲罰因子分析Figure 3 Penalty factor analysis

外部信任值通過控制懲罰因子P來調(diào)節(jié)對惡意行為的懲罰程度。在相同的網(wǎng)絡環(huán)境中，設置P分別為1、2，觀察不同參數(shù)對信任值的影響。由圖3可知，P值越大，懲罰程度越大，信任值下降越快。隨著否定事件r的增加，不信任程度d也會增加，P=2時，外部信任值由0.9降到0.3，而P=1時，懲罰力度較小，外部信任值由0.5降到0.4。

2) 內(nèi)部信任值分析。本實驗使用比特幣采礦網(wǎng)絡中的前11個采礦池來模擬本系統(tǒng)中的節(jié)點算力分布，前11個采礦池的總計算能力約為85.74%。如圖4所示為最近一年內(nèi)算力值最大的礦池BTC的內(nèi)部信任值變化曲線。內(nèi)部信任值可由公式(1+(x-a)/λ+|x-a|)/2計算得到，其中：x表示算力在內(nèi)的綜合能力；a、λ可以控制信任值變化快慢。由圖5可知，隨著參數(shù)a、λ的增大，信任值變化也會變快。

圖4 比特幣算力分布Figure 4 Bitcoin power distribution

3) 綜合信任值分析。信任值由內(nèi)部值和外部值計算得到，內(nèi)部信任值和外部信任值的變化快慢不一樣，需要權值進行平衡，權值為γ。

圖5 內(nèi)部信任值變化Figure 5 Change of interior trust value

內(nèi)、外部信任值在不同時間的增長速度不一樣，設Rnew為目前為止所有節(jié)點中最大的信任值，Tsecond表示系統(tǒng)運行的時間，c為信任值變化調(diào)節(jié)因子。則權值為γ=c·Rnew/Tsecond，這樣可以降低外部信任值的變化率，使之趨向于內(nèi)部變化率。

圖6 綜合信任值變化Figure 6 Change of comprehensive trust value

圖6為最近一年內(nèi)，算力值最大的礦池BTC的綜合信任值變化曲線。每個礦池的信任值都會隨著時間增加而增加。

設P=2、c=0.05、a=5 000、λ=1 000進行實驗，結果表明前3個月所有節(jié)點的信任值在(0,0.2]的范圍內(nèi)；第5個月時，64.5%的節(jié)點的信任值在(0,0.2]的范圍內(nèi)，35.5%的節(jié)點進入到(0.2,0.4]范圍內(nèi)；第6個月時，20.6%的節(jié)點的信任值在(0,0.2]的范圍內(nèi)，59.2%的節(jié)點進入到(0.2,0.4]范圍內(nèi)，20.2%的節(jié)點的信任值進入到(0.4,0.6]的范圍內(nèi);到第7個月的時候，15.2%的節(jié)點的信任值進入到(0.6,0.8]范圍內(nèi)；到1年后，才有16.4%的節(jié)點的信任值進入到(0.8, 1]的范圍內(nèi)。

從實驗結果可以看出聲譽值是在時間的基礎上，基于節(jié)點的表現(xiàn)動態(tài)變化的，就算是算力強大的節(jié)點，也需要超過1年才能達到高于0.8的信任值，抵御了賄賂攻擊。因此，當在系統(tǒng)剛剛建立階段，每個節(jié)點信任值都不高，是系統(tǒng)比較脆弱的時候，信任值達到共識組的閾值時間較短。如果惡意節(jié)點在系統(tǒng)建立初期潛伏到系統(tǒng)中，只需要簡單的努力就可使自己的信任值排到前N%；但是當系統(tǒng)達到穩(wěn)定狀態(tài)后再加入系統(tǒng)，則需要相當長的時間來建立自己的信任值，攻破系統(tǒng)的難度也會增加。

3.3 攻擊成本分析

攻擊成本為攻擊成功所需要的時間、算力的乘積。攻擊成功為共識組有半數(shù)成員為惡意節(jié)點。

在選取共識組成員時，前N%的成員進入候選組，然后從候選組隨機挑選成員進入共識組，當共識組成員的分數(shù)之和與全體成員的分數(shù)之和大于Z%時，完成共識組成員的選取。隨著N%和Z%的增長，攻擊成本也會越來越大。我們分析當N%取20%、Z%取30%時的情況，攻擊成本不僅與算力、還與節(jié)點加入系統(tǒng)的時間、系統(tǒng)已經(jīng)運行的時間相關。我們假設α為整個網(wǎng)絡算力的基本單位，g為維持1個算力單位一小時所需要的價錢，所以αg為所需要的攻擊成本。

圖7 綜合信任值變化圖Figure 7 Change of comprehensive trust value

為了成功攻擊比特幣，在最好的情況下，攻擊者需要51%的算力，并且需要6個區(qū)塊確認時間，大約為1小時來延續(xù)自己的私鏈。那么比特幣的攻擊成本為0.51αg。重復此攻擊的成本是相同的。對于ByzCoin，在最好的情況下，攻擊者需要34%的算力，以及整個窗口(1 008個區(qū)塊)維持大約一周的時間。因此，攻擊成本為168*0.34αg，約為57.12αg。在N%=20%時，排名在前20%的節(jié)點信任值最低為Rtarget，一個節(jié)點只有超過此閾值才有機會入選共識組參與共識，所以，攻擊成功的前提是要使惡意節(jié)點的值超過Rtarget。在系統(tǒng)運行的不同時刻，Rtarget的值不同。

圖7為算力占全網(wǎng)20%的節(jié)點的信任值隨著時間的變化情況：如果Rtarget=0.4，則節(jié)點需要工作158天才有可能進入共識組。攻擊成本為0.2α*(150*24g)=720αg；如果Rtarget=0.8，則節(jié)點需要工作210天，才有機會進入共識組。攻擊成本為0.2α*(210*24g)=1 008αg。

本文提出的共識機制明顯優(yōu)于比特幣和ByzCoin，由圖7也可以看出，隨著時間的增加，攻擊者所付出的成本逐漸增大，且一定時間后，攻擊成本高于收益，因此保障了系統(tǒng)的安全性。

共識機制的思想：首先，信任值是基于節(jié)點的歷史表現(xiàn)生成的，只有通過投入大量的算力和時間成本來獲得足夠的信任值，才有可能擁有決策權。這與以往的系統(tǒng)不同，以往系統(tǒng)只通過一瞬間的算力值來決定其是否擁有決策權，這樣避免了51%算力攻擊；其次，以往系統(tǒng)沒有記憶功能，對攻擊者的懲罰太小，本文引入懲罰因子，對攻擊者進行懲罰，從而避免了重復攻擊。

4 結語

本文對現(xiàn)有的基于算力的共識機制的不足進行了分析，提出了一種基于可信性評估的區(qū)塊鏈共識機制，并提出了一種節(jié)點信任值評估算法。每個節(jié)點信任值由內(nèi)部信任值和外部信任值綜合得到，能夠更好地表征節(jié)點的工作表現(xiàn)。通過對共識機制進行測試，表明本文設計的共識機制的攻擊成本是比特幣的幾百倍，是ByzCoin的幾十倍，而且也能防御基于算力的攻擊。本文的共識機制在吞吐量和共識延遲方面均有較好的表現(xiàn)。