一種改進的區塊鏈共識算法*

郭春梅 朱保平

（南京理工大學計算機科學與工程學院 南京 210094）

1 引言

2008年，中本聰發表了《比特幣：一種點對點的電子信息系統》一文［1］，區塊鏈的概念首次被提出。區塊鏈運用了密碼學，分布式共識，自動化腳本等技術，具有去中心化，可信任的特點［2］。在傳統的支付方法中存在一個問題：一般需要一個可信任的第三方機構［3］。而區塊鏈的去中心化特點恰巧能夠解決這一問題，因此區塊鏈的概念在被提出之后就立刻吸引了極大的關注并且被認為是最有潛力的技術之一。

區塊鏈的最大特點即是去中心化，每個節點都能夠驗證交易［4］。區塊鏈的共識機制主要是為了解決關于某個問題的形成一致性意見的過程，主要解決誰來記賬以及如何維護賬本的問題，是區塊鏈的重要部分之一。

本文希望結合PBFT算法的優點，將它與區塊鏈結合起來，更加適應區塊鏈。并且考慮到PBFT算法記賬節點一經確定無法修改的缺點［5］，我們對這一點進行改進，使得節點狀態能夠動態變化。同時我們考慮到對于聯盟鏈并不需要POW共識算法那么高的容錯性，所以用聯盟鏈以太坊進行實驗，與采用傳統POW共識算法的聯盟鏈以太坊和選擇改進的PBFT算法的聯盟鏈以太坊進行對比分析，驗證我們提出的P-PBFT共識算法的性能。

2 相關工作

POW共識機制即為工作量證明機制，它采用解決一個復雜的數學難題的方式來決定新區塊的歸屬問題［6］。因此POW主要依靠算力，算力越大，挖到礦的概率越大。由于POW共識算法極大的依靠算力，造成能源的浪費，因此主要適用于公有鏈。

POS共識機制即為權益證明機制，它的提出主要是為了解決POW算法上擁有大量設備的礦工更可能挖到新礦的不公平問題［7］。POS共識機制緩解了POW共識機制不公平及能源浪費的問題，但是可能導致節點離線從而容易造成網絡攻擊。

DPOS共識機制即股份權益證明機制［8］，是POS共識機制的進化版。DPOS共識機制沒有挖礦的過程，能夠提高共識的效率。但是這種共識機制將投票的權益集中到少數節點手上，可能會產生不公正的結果。

隨著共識機制的進一步發展，人們不單單把目光集中在POW等共識機制上，逐漸地轉向傳統的分布式共識算法。拜占庭容錯技術是一種解決分布式系統容錯的通用方案［9］。由于安全問題越來越受到人們的重視，而拜占庭容錯技術能夠解決安全漏洞等問題［10］，而很多經典算法并沒有能夠解決拜占庭容錯問題，所以PBFT算法的出現具有重要的意義。PBFT算法于1999年由Miguel Castro和Barbara Liskov提出，是一種能夠容忍拜占庭錯誤的狀態機復制算法［11］。

3 改進的PBFT共識算法

3.1 基本定義

定義1：假設系統中夠容忍的最大錯誤節點的個數為f，那么根據拜占庭容錯［12］可以假設區塊鏈系統中共有3f+1個節點。

3.2 狀態變化

我們在算法中引進狀態變更，給不同節點授予不同的狀態，在一段時間內，如果一個節點為共識表現較差的節點時，我們對該節點進行降級并且剔除出當前正在參與共識的節點集合，同時該時間段內候選節點集合內表現較好的節點可以進行升級加入到正在參與共識的節點集合。通過引進這種升降級的動態變化的機制，能夠減輕異常節點的影響。

3.2.1 節點狀態

為了減輕惡意節點的影響，防止惡意節點持續性地產生無效區塊，我們給每種節點定義一個狀態標識。

本文定義了兩種狀態如下：

1）Good：Good代表節點狀態良好，可以正常參加參與共識；

2）Bad：Bad代表節點狀態不佳，可能為惡意節點，不能正常參與共識。

3.2.2 狀態變更

我們將算法中選出來的共識記賬代表分為兩個部分，GD部分以及BD部分。GD部分表示節點狀態為Good的節點集合，BD部分表示節點狀態為Bad的節點集合。GD部分節點存儲在集合R1中，BD部分節點存儲在集合R2中。

GD中存儲的是正在參與共識的節點集合，根據拜占庭容錯，假設能容忍的最大的惡意節點的數量為f，那么GD內節點數量必須滿足以下公式：

BD中存儲的是候補節點集合，一段時間內，GD集合內排名倒數x的節點將被降級，變為Bad狀態同時加入到BD中。

為了不失一般性，我們令

狀態變更的流程圖如下：

圖1 狀態變更示意圖

1）參與共識算法的記賬代表節點，需要在全網注冊，等待投票審核通過以后，正式成為一名候選代表，并將其信息在全網進行廣播。

2）全網所有利益持有節點投票選舉出自己的記賬代表，共計N位。初始的時候，我們將這N位記賬代表隨機分配，分為3∶2的兩部分。其中GD占三分之二，BD占三分之一，所有初始記賬代表的初始值都是0。

3）我們給每個節點進行積分，然后根據積分進行排名。當一個主節點被從節點懷疑而引發配置變更，若變更成功，則主節點積分-2，從節點積分加1；產生區塊的節點積分加1。

4）一段時間后根據積分進行排名，GD集合內排名倒數x的節點將被降級，變為Bad狀態同時加入到BD中。

3.3 算法流程

PBFT算法進行一次正常的執行請求的過程主要分為pre-prepare，prepare，commit三個過程。

然而，PBFT算法是一種經典的分布式共識算法，它的三段式執行請求的過程也是基于分布式設計的［13］。PBFT算法是一種經典的C/S響應模式的算法，它的三段式執行請求的目的主要是為了在以狀態機副本為主的分布式系統中指令順序依然執行正確。區塊鏈共識機制的根本目標是全網達成共識，而并不要求指令的順序完全正確［14］。區塊鏈達成共識需要信息在全網的廣播，而信息在pre-prepare階段和prepare階段，信息已經在全網實現廣播，所以我們可以將原本的三段式過程進行合并并且簡化，合并成兩段式過程。這樣我們能夠減少信息在全網的一次傳播，提高效率。

圖2 系統執行一次請求的過程

由于在存在錯誤節點的情況下f的最小取值為1，所以系統中至少有四個節點，圖2展示了包含四個節點的系統執行一次請求的過程，四個節點包含一個主節點和三個從節點。

在區塊鏈中，交易是以區塊的形式存在并在永久記錄并保存在區塊鏈中［15］。在生成區塊之前，先檢驗交易的合法性，如果交易合法，再將交易批量寫入區塊中。

交易合法性的判定如下：

1）交易是否已經存在，如果已經存在則為非法交易，如果并不存在則為合法交易；

2）交易是否符合交易書寫規則，如果不符合則為非法交易，如果符合則為合法交易；

3）當前區塊的前一個區塊是否為區塊鏈的末尾，如果不是，則區塊鏈產生分叉，很有可能產生雙重支付，如果是，則為合法交易。

當上述條件1）～3）同時滿足時交易才判定為合法。

所以，P-PBFT的具體算法流程如下：

1）交易發起者發起交易的時候，首先附上自己的簽名然后向全網廣播；

2）所有節點獨立監聽全網交易，并且將監聽到的記錄在內存。當節點收到一筆交易時，如果是記賬代表則需要驗證交易的合法性，如果是合法的則寫入到內存中，如果不合法，則丟棄；

3）主節點發送共識準備信息＜＜PRE-PREPARE，v，n，d＞σp，m＞ ；

4）從節點收到共識準備信息后，先對收到的信息進行檢查，若檢查結果為真，則向除自己以外的其他從節點發送共識確認信息PREPARE：＜PREPARE，v，n，d，i＞＞ ；

5）若結果為假，則從節點懷疑主節點，廣播一條變更消息；

6）當主節點收到的正確信息大于等于2f時，共識完成，發布新的區塊block；

7）其余節點收到block之后，本輪共識結束開始新的一輪共識。

4 實驗與分析

為了驗證本文的算法，本文將搭建8臺1GB內存虛擬機，分別搭建采用改進的PBFT算法以及POW算法的以太坊聯盟鏈。實驗的硬件環境為Intel Pentium G3240，CPU 16GB。

4.1 算力開銷

POW共識機制的最大弊端就是高額的算力開銷，我們首先進行POW共識機制與我們改進的PBFT共識機制的算力開銷實驗比較。在驗證算力開銷的時候，我們選擇相同的機器，分別運行基于POW共識算法和改進的PBFT共識算法來比較它們的算力開銷。實驗結果如圖2所示，POW共識算法CPU的占用率幾乎達到了100%，而改進的PBFT共識算法僅需要30%左右。所以說在以太坊中采用PBFT共識算法，將它運用于聯盟鏈能夠大大地減少算力的開銷。

圖3 CPU占用率對比圖

4.2 容錯性

根據PBFT算法的理論和設計，我們改進的PBFT共識算法的容錯性依然應該是通過實驗來驗證改進的PBFT算法的容錯性以及與以太坊原有的POW共識算法的容錯性進行對比。我們通過使控制8臺虛擬機，使它們發生拜占庭錯誤，控制發生錯誤的虛擬機數目，看是否能夠正常運行來測試容錯性。

表1 容錯率分析

實驗結果如表1所示，改進的PBFT算法在節點錯誤數量為1和2時能夠正常運行，但是節點錯誤數量為3的時候就不能正確運行，它能夠容忍的最大錯誤數量為2。但是POW共識算法可以容忍3個節點發生錯誤，所以在容錯率方面，POW共識算法更優一些，但是改進的PBFT算法幾乎可以滿足聯盟鏈的容錯要求。

4.3 吞吐量

吞吐量是衡量一個系統單位時間內處理事務、請求、交易的能力［16］。我們選擇TPS（每秒交易數）來衡量。在區塊鏈應用中，吞吐量可以用交易發生到交易確認并寫入區塊鏈的總交易數除以時間來確定。

其中AccountTrans指的是交易發生到確認并寫入區塊鏈的總的交易數，t則是交易發生到確認的時間間隔。

圖4 吞吐量對比圖

我們選擇不同時時間間隔t來測試TPS，t的取值分別為10s，20s，40s，100s，300s，每個時間間隔測試10次，我們取10次的平均值來作為各個時間間隔的TPS。

實驗結果如圖4所示。

根據實驗結果我們可以發現本文提出的P-PBFT算法明顯提高了吞吐量。

5 結語

針對傳統的區塊鏈共識算法的弊端，本文考慮到將傳統的分布式共識算法PBFT加以改進運用于聯盟鏈。本文主要工作如下：1）本文將傳統的PBFT算法的三階段過程進行合并并且簡化為兩段式過程，減少了復雜度使之能夠更好地適應區塊鏈。2）引入了狀態變更的升降級制度，使得節點狀態動態改變，減少惡意節點的影響。3）在采用傳統POW共識機制的聯盟鏈以太坊進行對比分析，分析提出的算法的性能。