郭春梅 朱保平

（南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 南京 210094）

1 引言

2008年，中本聰發(fā)表了《比特幣：一種點(diǎn)對(duì)點(diǎn)的電子信息系統(tǒng)》一文［1］，區(qū)塊鏈的概念首次被提出。區(qū)塊鏈運(yùn)用了密碼學(xué)，分布式共識(shí)，自動(dòng)化腳本等技術(shù)，具有去中心化，可信任的特點(diǎn)［2］。在傳統(tǒng)的支付方法中存在一個(gè)問題：一般需要一個(gè)可信任的第三方機(jī)構(gòu)［3］。而區(qū)塊鏈的去中心化特點(diǎn)恰巧能夠解決這一問題，因此區(qū)塊鏈的概念在被提出之后就立刻吸引了極大的關(guān)注并且被認(rèn)為是最有潛力的技術(shù)之一。

區(qū)塊鏈的最大特點(diǎn)即是去中心化，每個(gè)節(jié)點(diǎn)都能夠驗(yàn)證交易［4］。區(qū)塊鏈的共識(shí)機(jī)制主要是為了解決關(guān)于某個(gè)問題的形成一致性意見的過程，主要解決誰來記賬以及如何維護(hù)賬本的問題，是區(qū)塊鏈的重要部分之一。

本文希望結(jié)合PBFT算法的優(yōu)點(diǎn)，將它與區(qū)塊鏈結(jié)合起來，更加適應(yīng)區(qū)塊鏈。并且考慮到PBFT算法記賬節(jié)點(diǎn)一經(jīng)確定無法修改的缺點(diǎn)［5］，我們對(duì)這一點(diǎn)進(jìn)行改進(jìn)，使得節(jié)點(diǎn)狀態(tài)能夠動(dòng)態(tài)變化。同時(shí)我們考慮到對(duì)于聯(lián)盟鏈并不需要POW共識(shí)算法那么高的容錯(cuò)性，所以用聯(lián)盟鏈以太坊進(jìn)行實(shí)驗(yàn)，與采用傳統(tǒng)POW共識(shí)算法的聯(lián)盟鏈以太坊和選擇改進(jìn)的PBFT算法的聯(lián)盟鏈以太坊進(jìn)行對(duì)比分析，驗(yàn)證我們提出的P-PBFT共識(shí)算法的性能。

2 相關(guān)工作

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

POS共識(shí)機(jī)制即為權(quán)益證明機(jī)制，它的提出主要是為了解決POW算法上擁有大量設(shè)備的礦工更可能挖到新礦的不公平問題［7］。POS共識(shí)機(jī)制緩解了POW共識(shí)機(jī)制不公平及能源浪費(fèi)的問題，但是可能導(dǎo)致節(jié)點(diǎn)離線從而容易造成網(wǎng)絡(luò)攻擊。

DPOS共識(shí)機(jī)制即股份權(quán)益證明機(jī)制［8］，是POS共識(shí)機(jī)制的進(jìn)化版。DPOS共識(shí)機(jī)制沒有挖礦的過程，能夠提高共識(shí)的效率。但是這種共識(shí)機(jī)制將投票的權(quán)益集中到少數(shù)節(jié)點(diǎn)手上，可能會(huì)產(chǎn)生不公正的結(jié)果。

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

3 改進(jìn)的PBFT共識(shí)算法

3.1 基本定義

定義1：假設(shè)系統(tǒng)中夠容忍的最大錯(cuò)誤節(jié)點(diǎn)的個(gè)數(shù)為f，那么根據(jù)拜占庭容錯(cuò)［12］可以假設(shè)區(qū)塊鏈系統(tǒng)中共有3f+1個(gè)節(jié)點(diǎn)。

3.2 狀態(tài)變化

我們?cè)谒惴ㄖ幸M(jìn)狀態(tài)變更，給不同節(jié)點(diǎn)授予不同的狀態(tài)，在一段時(shí)間內(nèi)，如果一個(gè)節(jié)點(diǎn)為共識(shí)表現(xiàn)較差的節(jié)點(diǎn)時(shí)，我們對(duì)該節(jié)點(diǎn)進(jìn)行降級(jí)并且剔除出當(dāng)前正在參與共識(shí)的節(jié)點(diǎn)集合，同時(shí)該時(shí)間段內(nèi)候選節(jié)點(diǎn)集合內(nèi)表現(xiàn)較好的節(jié)點(diǎn)可以進(jìn)行升級(jí)加入到正在參與共識(shí)的節(jié)點(diǎn)集合。通過引進(jìn)這種升降級(jí)的動(dòng)態(tài)變化的機(jī)制，能夠減輕異常節(jié)點(diǎn)的影響。

3.2.1 節(jié)點(diǎn)狀態(tài)

為了減輕惡意節(jié)點(diǎn)的影響，防止惡意節(jié)點(diǎn)持續(xù)性地產(chǎn)生無效區(qū)塊，我們給每種節(jié)點(diǎn)定義一個(gè)狀態(tài)標(biāo)識(shí)。

本文定義了兩種狀態(tài)如下：

1）Good：Good代表節(jié)點(diǎn)狀態(tài)良好，可以正常參加參與共識(shí)；

2）Bad：Bad代表節(jié)點(diǎn)狀態(tài)不佳，可能為惡意節(jié)點(diǎn)，不能正常參與共識(shí)。

3.2.2 狀態(tài)變更

我們將算法中選出來的共識(shí)記賬代表分為兩個(gè)部分，GD部分以及BD部分。GD部分表示節(jié)點(diǎn)狀態(tài)為Good的節(jié)點(diǎn)集合，BD部分表示節(jié)點(diǎn)狀態(tài)為Bad的節(jié)點(diǎn)集合。GD部分節(jié)點(diǎn)存儲(chǔ)在集合R1中，BD部分節(jié)點(diǎn)存儲(chǔ)在集合R2中。

GD中存儲(chǔ)的是正在參與共識(shí)的節(jié)點(diǎn)集合，根據(jù)拜占庭容錯(cuò)，假設(shè)能容忍的最大的惡意節(jié)點(diǎn)的數(shù)量為f，那么GD內(nèi)節(jié)點(diǎn)數(shù)量必須滿足以下公式：

BD中存儲(chǔ)的是候補(bǔ)節(jié)點(diǎn)集合，一段時(shí)間內(nèi)，GD集合內(nèi)排名倒數(shù)x的節(jié)點(diǎn)將被降級(jí)，變?yōu)锽ad狀態(tài)同時(shí)加入到BD中。

為了不失一般性，我們令

狀態(tài)變更的流程圖如下：

圖1 狀態(tài)變更示意圖

1）參與共識(shí)算法的記賬代表節(jié)點(diǎn)，需要在全網(wǎng)注冊(cè)，等待投票審核通過以后，正式成為一名候選代表，并將其信息在全網(wǎng)進(jìn)行廣播。

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

3）我們給每個(gè)節(jié)點(diǎn)進(jìn)行積分，然后根據(jù)積分進(jìn)行排名。當(dāng)一個(gè)主節(jié)點(diǎn)被從節(jié)點(diǎn)懷疑而引發(fā)配置變更，若變更成功，則主節(jié)點(diǎn)積分-2，從節(jié)點(diǎn)積分加1；產(chǎn)生區(qū)塊的節(jié)點(diǎn)積分加1。

4）一段時(shí)間后根據(jù)積分進(jìn)行排名，GD集合內(nèi)排名倒數(shù)x的節(jié)點(diǎn)將被降級(jí)，變?yōu)锽ad狀態(tài)同時(shí)加入到BD中。

3.3 算法流程

PBFT算法進(jìn)行一次正常的執(zhí)行請(qǐng)求的過程主要分為pre-prepare，prepare，commit三個(gè)過程。

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

圖2 系統(tǒng)執(zhí)行一次請(qǐng)求的過程

由于在存在錯(cuò)誤節(jié)點(diǎn)的情況下f的最小取值為1，所以系統(tǒng)中至少有四個(gè)節(jié)點(diǎn)，圖2展示了包含四個(gè)節(jié)點(diǎn)的系統(tǒng)執(zhí)行一次請(qǐng)求的過程，四個(gè)節(jié)點(diǎn)包含一個(gè)主節(jié)點(diǎn)和三個(gè)從節(jié)點(diǎn)。

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

交易合法性的判定如下：

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

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

3）當(dāng)前區(qū)塊的前一個(gè)區(qū)塊是否為區(qū)塊鏈的末尾，如果不是，則區(qū)塊鏈產(chǎn)生分叉，很有可能產(chǎn)生雙重支付，如果是，則為合法交易。

當(dāng)上述條件1）～3）同時(shí)滿足時(shí)交易才判定為合法。

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

1）交易發(fā)起者發(fā)起交易的時(shí)候，首先附上自己的簽名然后向全網(wǎng)廣播；

2）所有節(jié)點(diǎn)獨(dú)立監(jiān)聽全網(wǎng)交易，并且將監(jiān)聽到的記錄在內(nèi)存。當(dāng)節(jié)點(diǎn)收到一筆交易時(shí)，如果是記賬代表則需要驗(yàn)證交易的合法性，如果是合法的則寫入到內(nèi)存中，如果不合法，則丟棄；

3）主節(jié)點(diǎn)發(fā)送共識(shí)準(zhǔn)備信息＜＜PRE-PREPARE，v，n，d＞σp，m＞ ；

4）從節(jié)點(diǎn)收到共識(shí)準(zhǔn)備信息后，先對(duì)收到的信息進(jìn)行檢查，若檢查結(jié)果為真，則向除自己以外的其他從節(jié)點(diǎn)發(fā)送共識(shí)確認(rèn)信息PREPARE：＜PREPARE，v，n，d，i＞＞ ；

5）若結(jié)果為假，則從節(jié)點(diǎn)懷疑主節(jié)點(diǎn)，廣播一條變更消息；

6）當(dāng)主節(jié)點(diǎn)收到的正確信息大于等于2f時(shí)，共識(shí)完成，發(fā)布新的區(qū)塊block；

7）其余節(jié)點(diǎn)收到block之后，本輪共識(shí)結(jié)束開始新的一輪共識(shí)。

4 實(shí)驗(yàn)與分析

為了驗(yàn)證本文的算法，本文將搭建8臺(tái)1GB內(nèi)存虛擬機(jī)，分別搭建采用改進(jìn)的PBFT算法以及POW算法的以太坊聯(lián)盟鏈。實(shí)驗(yàn)的硬件環(huán)境為Intel Pentium G3240，CPU 16GB。

4.1 算力開銷

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

圖3 CPU占用率對(duì)比圖

4.2 容錯(cuò)性

根據(jù)PBFT算法的理論和設(shè)計(jì)，我們改進(jìn)的PBFT共識(shí)算法的容錯(cuò)性依然應(yīng)該是通過實(shí)驗(yàn)來驗(yàn)證改進(jìn)的PBFT算法的容錯(cuò)性以及與以太坊原有的POW共識(shí)算法的容錯(cuò)性進(jìn)行對(duì)比。我們通過使控制8臺(tái)虛擬機(jī)，使它們發(fā)生拜占庭錯(cuò)誤，控制發(fā)生錯(cuò)誤的虛擬機(jī)數(shù)目，看是否能夠正常運(yùn)行來測(cè)試容錯(cuò)性。

表1 容錯(cuò)率分析

實(shí)驗(yàn)結(jié)果如表1所示，改進(jìn)的PBFT算法在節(jié)點(diǎn)錯(cuò)誤數(shù)量為1和2時(shí)能夠正常運(yùn)行，但是節(jié)點(diǎn)錯(cuò)誤數(shù)量為3的時(shí)候就不能正確運(yùn)行，它能夠容忍的最大錯(cuò)誤數(shù)量為2。但是POW共識(shí)算法可以容忍3個(gè)節(jié)點(diǎn)發(fā)生錯(cuò)誤，所以在容錯(cuò)率方面，POW共識(shí)算法更優(yōu)一些，但是改進(jìn)的PBFT算法幾乎可以滿足聯(lián)盟鏈的容錯(cuò)要求。

4.3 吞吐量

吞吐量是衡量一個(gè)系統(tǒng)單位時(shí)間內(nèi)處理事務(wù)、請(qǐng)求、交易的能力［16］。我們選擇TPS（每秒交易數(shù)）來衡量。在區(qū)塊鏈應(yīng)用中，吞吐量可以用交易發(fā)生到交易確認(rèn)并寫入?yún)^(qū)塊鏈的總交易數(shù)除以時(shí)間來確定。

其中AccountTrans指的是交易發(fā)生到確認(rèn)并寫入?yún)^(qū)塊鏈的總的交易數(shù)，t則是交易發(fā)生到確認(rèn)的時(shí)間間隔。

圖4 吞吐量對(duì)比圖

我們選擇不同時(shí)時(shí)間間隔t來測(cè)試TPS，t的取值分別為10s，20s，40s，100s，300s，每個(gè)時(shí)間間隔測(cè)試10次，我們?nèi)?0次的平均值來作為各個(gè)時(shí)間間隔的TPS。

實(shí)驗(yàn)結(jié)果如圖4所示。

根據(jù)實(shí)驗(yàn)結(jié)果我們可以發(fā)現(xiàn)本文提出的P-PBFT算法明顯提高了吞吐量。

5 結(jié)語

針對(duì)傳統(tǒng)的區(qū)塊鏈共識(shí)算法的弊端，本文考慮到將傳統(tǒng)的分布式共識(shí)算法PBFT加以改進(jìn)運(yùn)用于聯(lián)盟鏈。本文主要工作如下：1）本文將傳統(tǒng)的PBFT算法的三階段過程進(jìn)行合并并且簡(jiǎn)化為兩段式過程，減少了復(fù)雜度使之能夠更好地適應(yīng)區(qū)塊鏈。2）引入了狀態(tài)變更的升降級(jí)制度，使得節(jié)點(diǎn)狀態(tài)動(dòng)態(tài)改變，減少惡意節(jié)點(diǎn)的影響。3）在采用傳統(tǒng)POW共識(shí)機(jī)制的聯(lián)盟鏈以太坊進(jìn)行對(duì)比分析，分析提出的算法的性能。