高效的實(shí)用拜占庭共識(shí)算法*

王薛平

（西安郵電大學(xué)計(jì)算機(jī)學(xué)院 西安 710121）

1 引言

區(qū)塊鏈技術(shù)［1］因具有去中心化、防篡改等特點(diǎn)被廣泛應(yīng)用到金融、物聯(lián)網(wǎng)和貿(mào)易管理中，是將數(shù)字加密、智能合約［2］、共識(shí)機(jī)制等技術(shù)結(jié)合起來(lái)構(gòu)建而成的一種分布式的系統(tǒng)架構(gòu)，由于去中心化的特性，應(yīng)用領(lǐng)域［3］也越來(lái)越廣泛。區(qū)塊鏈的網(wǎng)絡(luò)架構(gòu)一般采用點(diǎn)對(duì)點(diǎn)網(wǎng)絡(luò)［4］架構(gòu)，所有節(jié)點(diǎn)的地位都是對(duì)等的，并且以拓?fù)浣Y(jié)構(gòu)相互連接，節(jié)點(diǎn)間采用中繼轉(zhuǎn)發(fā)的模式進(jìn)行通信。由于沒(méi)有中心化的參與，所以節(jié)點(diǎn)間的一致性由共識(shí)算法來(lái)保持。

區(qū)塊鏈的共識(shí)算法［5］是為了解決狀態(tài)一致性和拜占庭將軍問(wèn)題。早先為了解決拜占庭將軍問(wèn)題，提出了拜占庭容錯(cuò)（BFT）算法［6］，依靠節(jié)點(diǎn)間傳遞消息對(duì)提案達(dá)成共識(shí)，由于消息復(fù)雜度的問(wèn)題使得BFT 的實(shí)用性較低。1999 年，Castro 等提出實(shí)用拜占庭容錯(cuò)共識(shí)算法（PBFT）［7］，在BFT共識(shí)算法的基礎(chǔ)上進(jìn)行改進(jìn)，降低了復(fù)雜度，在實(shí)際應(yīng)用中有了較高的可行性。

PBFT 算法［8］被應(yīng)用至聯(lián)盟鏈中，但是相對(duì)應(yīng)的也會(huì)產(chǎn)生一些缺陷，首先PBFT 算法的驗(yàn)證階段較為繁瑣，出于安全性的考慮會(huì)對(duì)準(zhǔn)備階段的信息進(jìn)行重新驗(yàn)證，以防止視圖更改后出現(xiàn)信息不一致的情況。在聯(lián)盟鏈的環(huán)境中，會(huì)對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行認(rèn)證以及監(jiān)督，網(wǎng)絡(luò)較為穩(wěn)定，視圖也不會(huì)頻繁發(fā)生變化，即使在視圖發(fā)生變化后增加同步和驗(yàn)證過(guò)程也同樣能夠確保數(shù)據(jù)的一致性［9］，從而可以優(yōu)化共識(shí)過(guò)程。

本文針對(duì)上述問(wèn)題，結(jié)合區(qū)塊鏈應(yīng)用的特點(diǎn)，提出一種改進(jìn)的PBFT算法。本算法淡化了原算法中主節(jié)點(diǎn)的功能轉(zhuǎn)化為客戶端直接向網(wǎng)絡(luò)中的節(jié)點(diǎn)通信，由網(wǎng)絡(luò)中的節(jié)點(diǎn)來(lái)進(jìn)行廣播。在其他節(jié)點(diǎn)收到請(qǐng)求消息后，進(jìn)行消息的驗(yàn)證，其次通過(guò)request和prepare-response兩個(gè)階段來(lái)完成共識(shí)并且減少了節(jié)點(diǎn)間的通信開(kāi)銷(xiāo)。

2 背景及相關(guān)工作

在目前區(qū)塊鏈的共識(shí)算法中工作量證明（PoW）［10］以及權(quán)益證明（PoS）［11］主要應(yīng)用于公有鏈，前者依靠算力后者則依靠數(shù)字貨幣來(lái)進(jìn)行共識(shí)操作，由于資源消耗較大以及實(shí)際場(chǎng)景沒(méi)有數(shù)字貨幣等問(wèn)題，導(dǎo)致了實(shí)用性較差的結(jié)果。方軼等提出一種基于環(huán)簽名的PBFT 共識(shí)算法改進(jìn)方案［12］，通過(guò)特殊的簽名方式有效提高了效率以及吞吐量，但是通信開(kāi)銷(xiāo)的問(wèn)題并沒(méi)有得到解決。張仕將等提出了一種基于Gossip協(xié)議的拜占庭共識(shí)算法［13］，通過(guò)Gossip協(xié)議進(jìn)行通信提升了算法的安全性，但是根本的效率問(wèn)題并沒(méi)有改善。徐浩等提出動(dòng)態(tài)實(shí)用拜占庭容錯(cuò)［14］，該協(xié)議允許節(jié)點(diǎn)的動(dòng)態(tài)加入和退出，具有很好的安全性和魯棒性，在效率方面的表現(xiàn)較差。

3 優(yōu)化后的EPBFT算法

針對(duì)PBFT 算法中通信開(kāi)銷(xiāo)過(guò)大、效率低下的缺點(diǎn)，本文提出了優(yōu)化后的EPBFT 算法。主要應(yīng)用場(chǎng)景為節(jié)點(diǎn)相對(duì)較為固定的聯(lián)盟鏈，根據(jù)聯(lián)盟鏈的特點(diǎn)對(duì)傳統(tǒng)的PBFT 算法進(jìn)行了改進(jìn)，優(yōu)化其共識(shí)過(guò)程，在不影響其安全的前提下，提升了效率并且減少了網(wǎng)絡(luò)開(kāi)銷(xiāo)。

3.1 算法設(shè)計(jì)

在聯(lián)盟鏈中，每個(gè)節(jié)點(diǎn)都有較高的信譽(yù)度，網(wǎng)絡(luò)運(yùn)行環(huán)境相對(duì)穩(wěn)定，在此情景下通過(guò)選取主節(jié)點(diǎn)再進(jìn)行廣播消息的方式極大的影響了效率。因此本文算法通過(guò)數(shù)據(jù)備份和驗(yàn)證階段代替選取主節(jié)點(diǎn)，可以保證安全性［15］的同時(shí)提高了效率。并且改變客戶端向主節(jié)點(diǎn)提交請(qǐng)求的過(guò)程，在聯(lián)盟鏈中所有節(jié)點(diǎn)都可以將消息廣播至整個(gè)網(wǎng)絡(luò)［16］。

3.2 算法過(guò)程

系統(tǒng)初始化后，網(wǎng)絡(luò)中的節(jié)點(diǎn)開(kāi)始進(jìn)行數(shù)據(jù)備份和驗(yàn)證。為了滿足共識(shí)的要求，每個(gè)節(jié)點(diǎn)需有相同的區(qū)塊數(shù)據(jù)、視圖編號(hào)、區(qū)塊高度等。完成驗(yàn)證和備份后，系統(tǒng)進(jìn)入請(qǐng)求階段和準(zhǔn)備響應(yīng)階段，以下為算法具體步驟：

Step 1：系統(tǒng)初始化，進(jìn)行數(shù)據(jù)驗(yàn)證和備份階段，每個(gè)節(jié)點(diǎn)從鏈最長(zhǎng)的節(jié)點(diǎn)開(kāi)始備份，獲取后進(jìn)行驗(yàn)證再將其保存。

Step 2：超過(guò)2f+1 個(gè)節(jié)點(diǎn)備份成功時(shí)驗(yàn)證成功。

Step 3：事務(wù)發(fā)起者C 節(jié)點(diǎn)向其他節(jié)點(diǎn)廣播已簽名的事務(wù)。

Step 4：各節(jié)點(diǎn)接受到消息后，驗(yàn)證其合法性，進(jìn)入請(qǐng)求階段，當(dāng)累計(jì)數(shù)量每個(gè)節(jié)點(diǎn)超過(guò)2f+1時(shí)對(duì)其他節(jié)點(diǎn)進(jìn)行廣播。

Step 5：進(jìn)入準(zhǔn)備響應(yīng)階段并驗(yàn)證消息合法性，如果合法返回C 節(jié)點(diǎn)進(jìn)行緩存，等收到足夠數(shù)量的交易后，生成一個(gè)區(qū)塊。

其算法的流程圖如圖1所示。

圖1 EPBFT算法流程圖

系統(tǒng)初始化后的備份和驗(yàn)證階段，目的是通過(guò)備份使每個(gè)節(jié)點(diǎn)數(shù)據(jù)信息一致，驗(yàn)證獲取數(shù)據(jù)的節(jié)點(diǎn)是否為惡意節(jié)點(diǎn)。

備份階段：需進(jìn)行備份的節(jié)點(diǎn)C1 向最長(zhǎng)鏈節(jié)點(diǎn)C2 發(fā)送請(qǐng)求，待收到請(qǐng)求到檢查視圖編號(hào)是否一致。如果編號(hào)一致，則同步消息到C1，如果不一致，根據(jù)其他節(jié)點(diǎn)擁有的不同數(shù)據(jù)塊，將備份請(qǐng)求和對(duì)應(yīng)數(shù)據(jù)區(qū)塊發(fā)送至其他節(jié)點(diǎn)。

驗(yàn)證階段：其他節(jié)點(diǎn)在收到最長(zhǎng)鏈節(jié)點(diǎn)C2 發(fā)送的備份數(shù)據(jù)后，會(huì)驗(yàn)證其合法性。如果合法，將數(shù)據(jù)保存并把消息廣播至整個(gè)網(wǎng)絡(luò)。如果驗(yàn)證失敗，將其丟棄并保存其他節(jié)點(diǎn)發(fā)送的驗(yàn)證結(jié)果。當(dāng)節(jié)點(diǎn)C1 同步其他節(jié)點(diǎn)返回的消息數(shù)量超過(guò)2f+1時(shí)，可確保每個(gè)節(jié)點(diǎn)的信息狀態(tài)一致。在驗(yàn)證完成后，每個(gè)節(jié)點(diǎn)將信息廣播至整個(gè)網(wǎng)絡(luò)進(jìn)入共識(shí)階段。

以下為具體的共識(shí)過(guò)程。

請(qǐng)求階段：C 向其他節(jié)點(diǎn)進(jìn)行廣播，其他節(jié)點(diǎn)收到消息后，如果消息通過(guò)則進(jìn)入準(zhǔn)備響應(yīng)階段，如果未通過(guò)驗(yàn)證，表明C 節(jié)點(diǎn)可能為惡意節(jié)點(diǎn)需要進(jìn)行驗(yàn)證并廣播更改視圖。

準(zhǔn)備響應(yīng)階段：節(jié)點(diǎn)向其他節(jié)點(diǎn)廣播準(zhǔn)備響應(yīng)消息，并保存請(qǐng)求和準(zhǔn)備響應(yīng)消息。當(dāng)消息數(shù)量超過(guò)2f+1與其他節(jié)點(diǎn)一致，則該階段完成。

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

本節(jié)將通過(guò)通信開(kāi)銷(xiāo)、時(shí)延、吞吐量等指標(biāo)對(duì)EPBFT 算法進(jìn)行測(cè)試，并與原PBFT 算法進(jìn)行對(duì)比以驗(yàn)證算法的實(shí)用性。

4.1 通信開(kāi)銷(xiāo)對(duì)比

1）PBFT通信開(kāi)銷(xiāo)

通過(guò)對(duì)前文的PBFT 算法進(jìn)行分析，共識(shí)過(guò)程總通信次數(shù)為2n（n-1）。

更改視圖時(shí)，通信的次數(shù)為（n-1）2。從其他節(jié)點(diǎn)收到視圖變更后，發(fā)送變更確認(rèn)信息至其他節(jié)點(diǎn)，此階段通信次數(shù)為（n-1）。假設(shè)視圖變更的概率為P時(shí)，通信的總次數(shù)為

C=2n（n-1）+Pn（n-1） （1）

2）EPBFT通信開(kāi)銷(xiāo)

上文對(duì)EPBFT 算法的共識(shí)過(guò)程分析可知通信次數(shù)為n（n-1）。

同步信息在數(shù)據(jù)同步驗(yàn)證階段發(fā)送至其他節(jié)點(diǎn)通信次數(shù)為（n-1）。在同步驗(yàn)證的過(guò)程中，所有節(jié)點(diǎn)將信息發(fā)送到除自身之外的所有節(jié)點(diǎn)，該過(guò)程的通信次數(shù)為（n-1）2，同步完成后，所有節(jié)點(diǎn)將信息返回，通信次數(shù)為（n-1）。因此算法的總通信次數(shù)為

C=n（n-1）+P（n2-1） （2）

以4個(gè)節(jié)點(diǎn)、6個(gè)節(jié)點(diǎn)、8個(gè)節(jié)點(diǎn)為例，當(dāng)不更改視圖的情況下，測(cè)試其通信次數(shù)，實(shí)驗(yàn)結(jié)果如圖2所示。

圖2 通信開(kāi)銷(xiāo)對(duì)比圖

基于以上分析，EPBFT算法的設(shè)計(jì)有效減少了共識(shí)過(guò)程的數(shù)據(jù)傳輸次數(shù)以及通信開(kāi)銷(xiāo)，且不減少系統(tǒng)的容錯(cuò)能力，提高了共識(shí)效率。

4.2 吞吐量對(duì)比

吞吐量指在單位時(shí)間內(nèi)系統(tǒng)處理的事務(wù)數(shù)，用TPS（Transaction Per Second）表示。本次實(shí)驗(yàn)設(shè)置從客戶端發(fā)出1000 條請(qǐng)求，在不同的節(jié)點(diǎn)數(shù)下記錄每秒完成的交易數(shù)并進(jìn)行對(duì)比，如圖3所示。

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

通過(guò)對(duì)圖3 的分析，在節(jié)點(diǎn)越來(lái)越多的情況下吞吐量緩緩下降，在對(duì)比后可知優(yōu)化后的EPBFT算法遠(yuǎn)高于原PBFT 算法。平均吞吐量從原來(lái)的351TPS提高到696TPS。

4.3 通信時(shí)延對(duì)比

本次通信時(shí)延實(shí)驗(yàn)的對(duì)比在搭建的基于java的考試系統(tǒng)上進(jìn)行，環(huán)境搭建在vmware 中，操作系統(tǒng)是ubuntu16.4。

圖4通過(guò)查詢考試結(jié)果信息為例，以40次查詢結(jié)果為例，橫坐標(biāo)x 表示了第x 次查詢，縱坐標(biāo)t 表示查詢時(shí)Fabric 的響應(yīng)時(shí)間。實(shí)驗(yàn)結(jié)果表明，使用原PBFT 算法是時(shí)延均值為39ms，而使用優(yōu)化后的EPBFT 時(shí)延的均值為30ms。相比較之下系統(tǒng)時(shí)延方面有較好的提升，使得用戶擁有更好的體驗(yàn)。

圖4 系統(tǒng)響應(yīng)時(shí)間

5 結(jié)語(yǔ)

提出了一種基于PBFT 算法改進(jìn)的EPBFT 算法。PBFT 算法中選取主節(jié)點(diǎn)的過(guò)程，在不影響整體操作的情況下進(jìn)行了省略，極大地提高了數(shù)據(jù)同步以及驗(yàn)證的效率，同時(shí)優(yōu)化了共識(shí)過(guò)程。通過(guò)優(yōu)化使得EPBFT算法更適用于聯(lián)盟區(qū)塊鏈的環(huán)境。

通過(guò)實(shí)驗(yàn)可知，共識(shí)過(guò)程中通信開(kāi)銷(xiāo)從原來(lái)的2n（n-1）縮短至n（n-1），有效減少了通信開(kāi)銷(xiāo)。吞吐量從原來(lái)的351TPS 提高至696TPS。通過(guò)搭建的區(qū)塊鏈平臺(tái)進(jìn)行測(cè)試，系統(tǒng)響應(yīng)時(shí)延從原來(lái)的39ms減少到30ms。

在未來(lái)的工作中，可對(duì)算法的安全性進(jìn)行提高，增加節(jié)點(diǎn)的動(dòng)態(tài)添加功能，對(duì)算法進(jìn)一步優(yōu)化，提高算法的適用性。