王日宏，張立鋒，周 航，徐泉清

1.青島理工大學(xué)信息與控制工程學(xué)院，山東青島266520

2.螞蟻金服，杭州310012

近幾年，作為比特幣底層技術(shù)的區(qū)塊鏈技術(shù)取得了重大發(fā)展[1].所謂區(qū)塊鏈，概括來(lái)說(shuō)，就是去中心化的分布式記賬本，綜合了密碼學(xué)、分布式原理等[2].它通過(guò)加密鏈?zhǔn)絽^(qū)塊結(jié)構(gòu)完成數(shù)據(jù)的存儲(chǔ)，利用共識(shí)算法驗(yàn)證數(shù)據(jù).區(qū)塊鏈的產(chǎn)生對(duì)互聯(lián)網(wǎng)乃至整個(gè)社會(huì)信用機(jī)制的建立帶來(lái)了至關(guān)重要的影響.

作為區(qū)塊鏈核心部分的共識(shí)算法主要分為非拜占庭容錯(cuò)共識(shí)算法和拜占庭容錯(cuò)(Byzantine fault tolerance, BFT)共識(shí)算法.非拜占庭容錯(cuò)共識(shí)算法的發(fā)展由來(lái)已久，例如：文獻(xiàn)[3]提出了一個(gè)在副本出現(xiàn)宕機(jī)情況下仍能正常工作的主從節(jié)點(diǎn)備份算法；文獻(xiàn)[4]提出了Paxos 算法；文獻(xiàn)[5]在文獻(xiàn)[4]的基礎(chǔ)上提出了更容易理解的Raft算法，并憑借著高可拓展性和高吞吐量的優(yōu)勢(shì)在聯(lián)盟鏈中得到了應(yīng)用.文獻(xiàn)[6]就在Quorum 項(xiàng)目中將Raft 算法作為可選算法.針對(duì)Raft 算法無(wú)法實(shí)現(xiàn)拜占庭容錯(cuò)問(wèn)題，提出了一種結(jié)合Raft 算法優(yōu)勢(shì)的拜占庭容錯(cuò)算法.

拜占庭容錯(cuò)算法可以分為3 類(lèi)：狀態(tài)機(jī)拜占庭容錯(cuò)算法、帶可信部件的拜占庭容錯(cuò)算法和針對(duì)區(qū)塊鏈應(yīng)用場(chǎng)景進(jìn)行優(yōu)化的拜占庭容錯(cuò)算法.狀態(tài)機(jī)拜占庭系統(tǒng)的代表算法主要是PBFT 算法及其改進(jìn)算法，例如沒(méi)有主節(jié)點(diǎn)排序（hybrid quorum, HQ）算法[7]、基于投機(jī)的Zyzzyva 算法[8]、基于拜占庭鎖的Zzyzx 算法[9]、優(yōu)化主節(jié)點(diǎn)切換代價(jià)的Spining 算法[10]等.帶有可信部件的拜占庭系統(tǒng)的代表算法主要包括A2M[11]和MinBFT[12]等，其主要思路是利用可信硬件解決節(jié)點(diǎn)模棱兩可問(wèn)題，從而提升拜占庭容錯(cuò)能力，實(shí)現(xiàn)了2f+1 的拜占庭容錯(cuò)能力.針對(duì)區(qū)塊鏈應(yīng)用場(chǎng)景進(jìn)行優(yōu)化的拜占庭容錯(cuò)算法主要包括權(quán)益證明（proof of stake, PoS）與實(shí)用拜占庭容錯(cuò)（practical Byzantine fault tolerance, PBFT）結(jié)合的Tendermint[13]、股份授權(quán)證明（delegated proof of stake, DPoS）[14]與PBFT結(jié)合的授權(quán)拜占庭容錯(cuò)（delegated Byzantine fault tolerance, dBFT）[15].除此之外，在區(qū)塊鏈中還有一類(lèi)基于密碼學(xué)的共識(shí)算法，如采用聚合簽名降低通信復(fù)雜度的Byzcoin[16]、采用可驗(yàn)證隨機(jī)數(shù)的Algorand 以及利用閾值簽名實(shí)現(xiàn)異步共識(shí)的HoneyBadgerBFT[17].

通過(guò)對(duì)已有拜占庭容錯(cuò)算法進(jìn)行分析，提出了結(jié)合BLS 閾值簽名[18]實(shí)現(xiàn)Raft 算法的拜占庭容錯(cuò)算法（Raft Byzantine fault tolerance, RBFT）.該算法實(shí)現(xiàn)了Leader 節(jié)點(diǎn)選舉和日志復(fù)制過(guò)程的拜占庭容錯(cuò)，同時(shí)又保證了O(n)的算法復(fù)雜度，并且提出了安全狀態(tài)，保證了算法的最終一致性[19].

針對(duì)Raft 算法中的問(wèn)題，RBFT 算法進(jìn)行了如下改進(jìn)：

1）將BLS 簽名與Raft 算法中的消息傳遞過(guò)程結(jié)合，實(shí)現(xiàn)了Leader 節(jié)點(diǎn)選舉和日志復(fù)制過(guò)程的拜占庭容錯(cuò).

2）基于增量哈希提出了安全狀態(tài)，能保證算法在每輪共識(shí)完成之后的一致性，進(jìn)一步保證了算法的安全性.

3）提出了結(jié)合Raft 算法超時(shí)時(shí)間機(jī)制的選舉方案，簡(jiǎn)化了傳統(tǒng)BFT 算法在視圖切換過(guò)程中的算法復(fù)雜度.

4）引入客戶端監(jiān)控機(jī)制以動(dòng)態(tài)監(jiān)測(cè)Leader 節(jié)點(diǎn)運(yùn)行情況，避免了拜占庭Leader 節(jié)點(diǎn)消極反饋情況的發(fā)生.

1 背景知識(shí)

1.1 Raft 算法

Raft 算法是一種非拜占庭容錯(cuò)的狀態(tài)機(jī)副本復(fù)制算法[5]，分為3 種狀態(tài)模型：Follower、Candidate 和Leader.狀態(tài)轉(zhuǎn)化模型如圖1所示.

圖1 Raft 算法狀態(tài)轉(zhuǎn)移圖Figure 1 State transition diagram of Raft algorithm

在Raft 共識(shí)算法中，消息包含RequestVote 和AppendEntries 兩種消息.當(dāng)Leader 節(jié)點(diǎn)宕機(jī)時(shí)，Candidate 在選舉時(shí)通過(guò)RequestVote 消息可以獲取Follower 的唯一投票.Leader 節(jié)點(diǎn)通過(guò)AppendEntries 消息發(fā)送日志條目到Follower 節(jié)點(diǎn)，此時(shí)AppendEntries 消息中包含心跳（heartbeat）信息，以證明Leader 節(jié)點(diǎn)能正常運(yùn)行.兩種消息的存在，讓Raft 節(jié)點(diǎn)間在實(shí)現(xiàn)數(shù)據(jù)交流的同時(shí)完成日志復(fù)制的共識(shí)任務(wù).

1.2 BLS 簽名

BLS 簽名算法是基于雙線性映射構(gòu)造的一種加密算法[18]，主要分為4 部分：算法初始化、密鑰生成、簽名和驗(yàn)證.

1）算法初始化

G1和G2是階為p的乘法群，生成元分別為g1和g2,e表示雙線性映射:G1×G2→GT,H:{0,1}?→G1表示安全哈希函數(shù)，(G1,G2,GT,e,g1,g2,p,h)表示公開(kāi)參數(shù).

2）密鑰生成

選擇一個(gè)隨機(jī)數(shù)x ∈ZP，計(jì)算v=gx2∈G2，私鑰為sk=x，公鑰為pk=v.

3）簽名

例如對(duì)接收到的消息M進(jìn)行簽名生成σ=xH(M)，H(M)表示對(duì)消息M進(jìn)行哈希運(yùn)算的過(guò)程.

4）驗(yàn)證

輸入消息M和簽名σ，判斷e(σ,g2)=e(H(M),v)是否成立.

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

2.1 RBFT 算法基礎(chǔ)

RBFT 算法改進(jìn)了Raft 算法，利用BLS 簽名實(shí)現(xiàn)閾值簽名，以閾值簽名過(guò)程代替投票過(guò)程，實(shí)現(xiàn)了算法的拜占庭容錯(cuò).RBFT算法同樣保留了Raft 算法中的3 種節(jié)點(diǎn)狀態(tài)：Leader、Follower 和Candidate，并且針對(duì)日志結(jié)構(gòu)也同樣保留了任期（Term）、索引（Index）和命令（Command）的結(jié)構(gòu).為了實(shí)現(xiàn)拜占庭容錯(cuò)，RBFT 算法包含AppendEntries消息、RequestVote 消息、Request 消息和Update 消息，其中Request 消息受到了Omniledger的啟發(fā)[20]，用于監(jiān)測(cè)Leader 節(jié)點(diǎn)運(yùn)行狀況的Update 消息.

詳細(xì)介紹如下：

1）AppendEntries 消息

AppendEntries 消息包含Leader 節(jié)點(diǎn)發(fā)往Follower 節(jié)點(diǎn)的日志消息、Leader 節(jié)點(diǎn)的心跳和Leader 節(jié)點(diǎn)選舉成功的證據(jù).證據(jù)由Leader 節(jié)點(diǎn)收集的簽名組成，并通過(guò)結(jié)合BLS 的閾值簽名組合成一個(gè)可供其他節(jié)點(diǎn)驗(yàn)證的總簽名A，該過(guò)程如圖2所示.

圖2 BLS 閾值簽名圖Figure 2 BLS threshold signature diagram

2）AppendEntriesResponse 消息

AppendEntriesResponse 消息是在包含AppendEntries 消息的基礎(chǔ)上增加了可供其他節(jié)點(diǎn)驗(yàn)證的總簽名A.

3）RequestVote 消息

RequestVote 消息包含Candidate 節(jié)點(diǎn)的當(dāng)前任期和用來(lái)驗(yàn)證當(dāng)前任期的遞增哈希值.遞增哈希值由日志的任期、索引、命令三部分組成，可以通過(guò)索引號(hào)順序計(jì)算命令的哈希得到.遞增哈希值一方面可以驗(yàn)證當(dāng)前Candidate 節(jié)點(diǎn)提供的任期號(hào)是否正確，保證了RBFT 算法Leader 選取的最優(yōu)性；另一方面可以防止拜占庭Leader 節(jié)點(diǎn)對(duì)日志的舍棄或任意重排序.

4）RequestVoteResponse 消息

RequestVoteResponse 消息除了包含RequestVote 消息之外，還包含可供其他節(jié)點(diǎn)驗(yàn)證的總簽名A.

5）Request 消息

Request 消息包含客戶端發(fā)送到Leader 節(jié)點(diǎn)的消息和便于Follower 節(jié)點(diǎn)驗(yàn)證客戶端消息完整性和正確性的數(shù)字簽名.數(shù)字簽名的存在能有效防止Leader 節(jié)點(diǎn)對(duì)消息的篡改.

6）Update 消息

Update 消息能增加客戶端的干預(yù)，防止Leader 節(jié)點(diǎn)對(duì)客戶端的消極反饋而引發(fā)的算法活性問(wèn)題[20].

RBFT 算法針對(duì)4 種消息的節(jié)點(diǎn)狀態(tài)轉(zhuǎn)移如圖3所示.

最后根據(jù)CAP 原則[21]，引入了安全狀態(tài)增強(qiáng)來(lái)RBFT 算法的可用性，即共識(shí)完成之后實(shí)現(xiàn)所有非拜占庭節(jié)點(diǎn)狀態(tài)的一致性.設(shè)立安全狀態(tài)可以保證節(jié)點(diǎn)達(dá)到最終一致性，即任何達(dá)到安全狀態(tài)的非拜占庭節(jié)點(diǎn)都將擁有相同的狀態(tài).

圖3 RBFT 算法狀態(tài)轉(zhuǎn)移圖Figure 3 State transition diagram of RBFT algorithm

2.2 容錯(cuò)機(jī)制的實(shí)現(xiàn)

RBFT 算法容錯(cuò)機(jī)制的實(shí)現(xiàn)依賴于結(jié)合BLS 簽名的閾值簽名，閾值簽名的構(gòu)造過(guò)程是通過(guò)Shamir 秘密分享方法[22]進(jìn)行的.引入閾值簽名的目的是將投票過(guò)程轉(zhuǎn)化為簽名過(guò)程，并且以2/3 節(jié)點(diǎn)數(shù)作為簽名收集的閾值.結(jié)合了BLS 簽名的閾值簽名方案主要分為四部分：算法初始化、密鑰生成、簽名和驗(yàn)證.

1）初始化

初始化過(guò)程與1.2 節(jié)BLS 簽名中的初始化過(guò)程相同.

2）密鑰生成

首先選擇一個(gè)隨機(jī)數(shù)x ∈ZP，計(jì)算v=gx2∈G2，總私鑰為msk=x，總公鑰為mpk=v；然后進(jìn)行隨機(jī)化過(guò)程，隨機(jī)選取xi ∈ZP上的t ?1 階多項(xiàng)式P，并且滿足P(0) =x，計(jì)算簽名者i的私鑰為xi，公鑰為vi；最后公開(kāi)mpk 以及所有用戶的公鑰

3）簽名

簽名過(guò)程即針對(duì)日志的復(fù)制過(guò)程，與投票過(guò)程相同.節(jié)點(diǎn)i對(duì)Leader 節(jié)點(diǎn)接收來(lái)的攜帶有客戶端簽名的AppendEntries 消息M進(jìn)行驗(yàn)證，根據(jù)數(shù)字簽名驗(yàn)證消息是否被Leader 節(jié)點(diǎn)篡改，驗(yàn)證通過(guò)后計(jì)算簽名σi=H(M)xi，然后將σi廣播給Leader 節(jié)點(diǎn)，Leader 節(jié)點(diǎn)收到σi后進(jìn)行驗(yàn)證.首先通過(guò)雙線性映射函數(shù)驗(yàn)證簽名的正確性，即e(σi,g2) =e(H(M),vi)，若等式成立則驗(yàn)證通過(guò)，Leader 將簽名記錄下來(lái)；其次等待收到其余2/3 的Follower 節(jié)點(diǎn)的正確簽名；最后Leader 節(jié)點(diǎn)根據(jù)這些簽名計(jì)算出完整的簽名

式中

4）驗(yàn)證

Leader 節(jié)點(diǎn)通過(guò)AppendEntriesResponse 消息向Follower 節(jié)點(diǎn)傳遞消息M和簽名σ，判斷e(σ,g2)=e(H(M),mpk)是否成立，從而完成整個(gè)驗(yàn)證過(guò)程.

2.3 Leader 節(jié)點(diǎn)選舉

在Raft 算法中，Leader 節(jié)點(diǎn)選舉依賴于隨機(jī)超時(shí)時(shí)間.超時(shí)時(shí)間短的Candidate 節(jié)點(diǎn)優(yōu)先向其他節(jié)點(diǎn)發(fā)送RequestVote 命令進(jìn)行索票，票數(shù)多的Candidate 節(jié)點(diǎn)當(dāng)選為L(zhǎng)eader 節(jié)點(diǎn).在不存在拜占庭節(jié)點(diǎn)的情況下，Leader 節(jié)點(diǎn)選舉過(guò)程將順利達(dá)成，但在存有拜占庭節(jié)點(diǎn)的情況下，Leader 節(jié)點(diǎn)選舉過(guò)程會(huì)遇到偽造投票消息的情況，即拜占庭節(jié)點(diǎn)在選舉過(guò)程中偽造自己接收到了大多數(shù)其他節(jié)點(diǎn)的投票消息.RBFT 算法針對(duì)Leader 節(jié)點(diǎn)選舉問(wèn)題，采用了結(jié)合BLS 簽名的閾值簽名方案，將Raft算法中通過(guò)RequestVote 獲取選票的過(guò)程轉(zhuǎn)化為通過(guò)RequestVote 獲取Follower 節(jié)點(diǎn)對(duì)該消息進(jìn)行閾值簽名的過(guò)程.在第1 階段，當(dāng)某個(gè)Candidate 節(jié)點(diǎn)優(yōu)先收集到超過(guò)2/3的Follower 節(jié)點(diǎn)的部分簽名后會(huì)得到完整簽名.在第2 階段，該節(jié)點(diǎn)轉(zhuǎn)發(fā)附有完整簽名的RequestVoteResponse 消息，等待其他節(jié)點(diǎn)驗(yàn)證這個(gè)完整簽名的有效性.如果驗(yàn)證通過(guò)則返回一個(gè)正反饋，否則返回一個(gè)負(fù)反饋，最后當(dāng)選的Candidate節(jié)點(diǎn)發(fā)送攜帶正反饋的可驗(yàn)證消息給其他節(jié)點(diǎn)，完成整個(gè)選舉過(guò)程.圖4為L(zhǎng)eader 節(jié)點(diǎn)選舉階段示意圖.

圖4 RBFT 算法Leader 節(jié)點(diǎn)選舉過(guò)程圖Figure 4 RBFT algorithm Leader election process diagram

RBFT 算法引入結(jié)合BLS 簽名的閾值簽名方案，保證了Leader 節(jié)點(diǎn)選舉的安全性和效率，將同類(lèi)型PBFT 的算法復(fù)雜度由O(n2)（在最壞情況下的算法復(fù)雜度為O(n4)）降低到O(n).

2.4 日志復(fù)制

RBFT 算法在Raft 算法基礎(chǔ)上，針對(duì)Leader 節(jié)點(diǎn)和Follower 節(jié)點(diǎn)可能出現(xiàn)的拜占庭錯(cuò)誤進(jìn)行了容錯(cuò).當(dāng)Leader 節(jié)點(diǎn)是拜占庭節(jié)點(diǎn)時(shí)，拜占庭錯(cuò)誤分為以下幾種：Leader 節(jié)點(diǎn)篡改來(lái)自客戶端的消息、Leader 節(jié)點(diǎn)提交未經(jīng)驗(yàn)證的消息和Leader 節(jié)點(diǎn)忽略或消極反饋客戶端消息.當(dāng)Follower 節(jié)點(diǎn)是拜占庭節(jié)點(diǎn)時(shí)，拜占庭Follower 節(jié)點(diǎn)可能會(huì)篡改來(lái)自Leader 節(jié)點(diǎn)的消息.

針對(duì)以上問(wèn)題，RBFT 算法進(jìn)行如下優(yōu)化：

1）針對(duì)拜占庭Leader 節(jié)點(diǎn)篡改來(lái)自客戶端的消息問(wèn)題，RBFT 算法引入數(shù)字簽名，使客戶端發(fā)往Leader 節(jié)點(diǎn)的Request 消息中包含客戶端對(duì)消息的數(shù)字簽名.如果Leader 節(jié)點(diǎn)對(duì)消息進(jìn)行篡改，則接收到消息的Follower 節(jié)點(diǎn)將會(huì)通過(guò)客戶端公鑰進(jìn)行檢驗(yàn)，這種機(jī)制可以阻止拜占庭Leader 節(jié)點(diǎn)對(duì)消息的篡改.

2）針對(duì)拜占庭Leader 節(jié)點(diǎn)提交未經(jīng)驗(yàn)證的消息問(wèn)題，RBFT 算法引入了容錯(cuò)機(jī)制，其過(guò)程如圖5所示：

圖5 RBFT 算法日志復(fù)制過(guò)程圖Figure 5 Diagram of RBFT algorithm log replication process

該過(guò)程分為3 個(gè)階段：Pre-commit 階段、Commit 階段、Reply 階段.在Pre-commit階段，Leader 節(jié)點(diǎn)發(fā)送AppendEntries 消息到Follower 節(jié)點(diǎn)，F(xiàn)ollower 節(jié)點(diǎn)在驗(yàn)證AppendEntries 中的數(shù)字簽名確實(shí)來(lái)自客戶端后對(duì)其進(jìn)行簽名，并將結(jié)果返回給Leader 節(jié)點(diǎn).當(dāng)Leader 節(jié)點(diǎn)接收到超過(guò)2/3 的Follower 節(jié)點(diǎn)的簽名后，通過(guò)閾值簽名組成完整簽名，這樣就完成了Pre-commit 階段.在Commit 階段，Leader 節(jié)點(diǎn)發(fā)送AppendEntriesResponse 消息到Follower 節(jié)點(diǎn)，F(xiàn)ollower 節(jié)點(diǎn)驗(yàn)證AppendEntriesResponse 中的完整簽名的正確性，并將驗(yàn)證結(jié)果返回給Leader 節(jié)點(diǎn).當(dāng)Leader 節(jié)點(diǎn)收到超過(guò)2/3 的Follower 節(jié)點(diǎn)的驗(yàn)證通過(guò)后返回正反饋，完成Commit 階段.在Reply 階段，Leader 節(jié)點(diǎn)發(fā)送攜帶可驗(yàn)證正反饋的消息給Follower 節(jié)點(diǎn)后，F(xiàn)ollower 節(jié)點(diǎn)同步狀態(tài)，使所有非拜占庭Follower 節(jié)點(diǎn)達(dá)到安全模式，此時(shí)Leader 節(jié)點(diǎn)提交消息給客戶端，完成Reply 階段.

RBFT 算法采用結(jié)合BLS 簽名的閾值簽名方案，將PBFT 中Prepare 階段和Commit 階段O(n2)的算法復(fù)雜度優(yōu)化到了O(n)，大大增加了數(shù)據(jù)吞吐量，降低了交易延遲，提升了算法的可拓展性.

3 算法分析

RBFT算法作為拜占庭容錯(cuò)的Raft 算法，需要在拜占庭節(jié)點(diǎn)存在的情況下滿足安全性和活性的要求.算法分析部分參考了Raft 算法文獻(xiàn)中的安全性和活性要求，并以此作為參照標(biāo)準(zhǔn)分析RBFT 算法的安全性和活性.

3.1 安全性分析

安全性指的是所有壞的事情不會(huì)發(fā)生[23]，也就是所有誠(chéng)實(shí)節(jié)點(diǎn)最終提交一致性結(jié)果.Raft 算法的安全性體現(xiàn)在：Leader 節(jié)點(diǎn)選舉的安全性、Leader 節(jié)點(diǎn)只允許附加不允許刪除和修改、Leader 節(jié)點(diǎn)的完整性、日志匹配機(jī)制以及狀態(tài)機(jī)的安全性.針對(duì)以上內(nèi)容，結(jié)合拜占庭容錯(cuò)問(wèn)題對(duì)RBFT 算法進(jìn)行了以下分析.

3.1.1 Leader 節(jié)點(diǎn)選舉的安全性

在Raft 算法運(yùn)行過(guò)程中，Leader 節(jié)點(diǎn)會(huì)定期發(fā)送包含日志和心跳的AppendEntries 消息給Follower 節(jié)點(diǎn)，以證明Leader 節(jié)點(diǎn)的正常運(yùn)行.當(dāng)Leader 節(jié)點(diǎn)宕機(jī)時(shí)，F(xiàn)ollower 節(jié)點(diǎn)因收不到Leader 節(jié)點(diǎn)的心跳消息而觸發(fā)選舉.選舉需要規(guī)定隨機(jī)超時(shí)時(shí)間，優(yōu)先完成這個(gè)時(shí)間的節(jié)點(diǎn)可以向其他節(jié)點(diǎn)發(fā)送RequestVote 消息.這個(gè)消息包含當(dāng)前節(jié)點(diǎn)的任期，以此保證了整個(gè)選舉過(guò)程的安全性.然而，拜占庭Leader 節(jié)點(diǎn)可能以偽造投票的方式當(dāng)選.為了保證RBFT算法Leader 節(jié)點(diǎn)選舉的安全性，提出了采用結(jié)合BLS 簽名的閾值簽名方案來(lái)防止這種情況的發(fā)生，具體可見(jiàn)2.2 部分.

3.1.2 Leader 節(jié)點(diǎn)的安全性問(wèn)題分類(lèi)

在Raft 算法中，Leader 節(jié)點(diǎn)的安全性問(wèn)題分為兩類(lèi)：Leader 節(jié)點(diǎn)的日志完整性和Leader節(jié)點(diǎn)只允許附加日志而不允許刪除日志.針對(duì)Leader 節(jié)點(diǎn)的日志完整性問(wèn)題，RBFT 算法通過(guò)增量哈希和日志復(fù)制的容錯(cuò)機(jī)制保證了所有非拜占庭節(jié)點(diǎn)都處于同樣的安全狀態(tài)，并且通過(guò)選舉機(jī)制保證了所有當(dāng)選的Leader 節(jié)點(diǎn)都是到達(dá)安全狀態(tài)的節(jié)點(diǎn)，即保證了Leader 節(jié)點(diǎn)的日志完整性.針對(duì)Leader 節(jié)點(diǎn)只允許附加日志而不允許刪除的問(wèn)題，RBFT 算法依賴于增量哈希的安全狀態(tài)，保證了所有通過(guò)共識(shí)的日志都會(huì)被保存，而不允許任意的節(jié)點(diǎn)刪除或修改.

3.1.2.1 日志

RBFT 算法保留了Raft 算法的日志結(jié)構(gòu)，并在此基礎(chǔ)上提出了日志復(fù)制過(guò)程中的拜占庭容錯(cuò)方法，通過(guò)兩輪提交保證了拜占庭節(jié)點(diǎn)存在情況下日志的正確性，具體可見(jiàn)2.4 部分.

3.1.2.2 狀態(tài)機(jī)

RBFT 算法修改了狀態(tài)機(jī)提交需要1/2 節(jié)點(diǎn)同意的前提，為了實(shí)現(xiàn)拜占庭容錯(cuò)，將狀態(tài)機(jī)提交前提修改為2/3 節(jié)點(diǎn)，并且結(jié)合區(qū)塊鏈的使用場(chǎng)景將提交狀態(tài)機(jī)過(guò)程轉(zhuǎn)化為L(zhǎng)eader 節(jié)點(diǎn)把交易寫(xiě)入?yún)^(qū)塊的過(guò)程.

以上分析表明：RBFT 算法符合安全性要求.

3.2 活性分析

活性指的是所有好的事情一定發(fā)生[23]，也就是在一定時(shí)間范圍內(nèi)完成整個(gè)共識(shí)過(guò)程.在Raft 共識(shí)算法中，活性主要體現(xiàn)在隨機(jī)超時(shí)時(shí)間t的設(shè)立.t ?[T,2T]并且滿足T ?T(broadcast time)的條件，以避免因?yàn)橄⒀舆t而導(dǎo)致的不必要的Leader 節(jié)點(diǎn)切換，同時(shí)t的設(shè)立又可以讓系統(tǒng)在有限的時(shí)間內(nèi)產(chǎn)生一個(gè)Leader 節(jié)點(diǎn)，保證系統(tǒng)的正常運(yùn)行.

RBFT 算法保留了Raft 算法關(guān)于保證算法活性的內(nèi)容.針對(duì)隨機(jī)超時(shí)時(shí)間t，文獻(xiàn)[5]給出了一個(gè)t ?[150 ms, 300 ms]的建議，T(broadcast time)=15 ms，Leader 節(jié)點(diǎn)心跳間隔T(heartbeat)=50 ms.隨機(jī)超時(shí)時(shí)間的產(chǎn)生是在考慮AppendEntries 消息延遲的基礎(chǔ)上進(jìn)行的，同時(shí)文獻(xiàn)[5]建議采用這種較大時(shí)間間隔的原因也是考慮到可能存在的節(jié)點(diǎn)分票的情況.增大時(shí)間間隔既可以有效地降低分票的可能性，又可以降低因消息延遲而導(dǎo)致的不必要的Leader節(jié)點(diǎn)切換.

RBFT 算法是通過(guò)設(shè)置最大消息延遲時(shí)間來(lái)保證算法活性的.該算法將隨機(jī)超時(shí)時(shí)間t設(shè)置為t ?[150 ms, 600 ms]，是因?yàn)槌丝紤]消息延遲外還要考慮拜占庭容錯(cuò)過(guò)程中的多輪消息交換和聚合簽名過(guò)程.Leader節(jié)點(diǎn)心跳間隔設(shè)置為T(mén)(heartbeat)=150 ms，并且通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)在這個(gè)心跳間隔內(nèi)算法可以避免不必要的Leader 節(jié)點(diǎn)切換.如果在心跳間隔內(nèi)Leader節(jié)點(diǎn)無(wú)響應(yīng)，就重新進(jìn)行節(jié)點(diǎn)切換，保證了算法的活躍度.另外，受到Omniledger 分布式一致性算法[20]的客戶端監(jiān)測(cè)機(jī)制的啟發(fā)，客戶端對(duì)Leader 節(jié)點(diǎn)進(jìn)行監(jiān)控.當(dāng)發(fā)現(xiàn)Leader 節(jié)點(diǎn)消極反饋來(lái)自客戶端的消息時(shí)，通過(guò)Update 消息進(jìn)行新一輪的Leader 選舉，防止了拜占庭Leader 節(jié)點(diǎn)消極反饋的情況.

4 仿真實(shí)驗(yàn)

RBFT 算法將BLS 簽名容錯(cuò)過(guò)程與Raft 算法結(jié)合，實(shí)現(xiàn)了Raft 算法的拜占庭容錯(cuò).RBFT 算法高可拓展性和高數(shù)據(jù)吞吐量的實(shí)現(xiàn)，一方面得益于BLS 簽名容錯(cuò)過(guò)程的低算法復(fù)雜度，另一方面得益于Raft 算法高效的共識(shí)邏輯.

首先，本文采用go 語(yǔ)言實(shí)現(xiàn)了Raft 算法，并在改進(jìn)Raft 算法的基礎(chǔ)上得到了RBFT 算法；然后，采用本地多節(jié)點(diǎn)模擬共識(shí)過(guò)程，記錄數(shù)據(jù)吞吐量、共識(shí)時(shí)延等關(guān)鍵數(shù)據(jù)，完成對(duì)比實(shí)驗(yàn)；最后，通過(guò)實(shí)驗(yàn)對(duì)比發(fā)現(xiàn)，RBFT 算法實(shí)現(xiàn)了高數(shù)據(jù)吞吐量、低延遲以及高可拓展性.

4.1 數(shù)據(jù)吞吐量測(cè)試

數(shù)據(jù)吞吐量作為衡量區(qū)塊鏈共識(shí)算法性能的關(guān)鍵指標(biāo)，表示的是區(qū)塊鏈每秒可處理的交易數(shù)量（transaction per second, TPS）.

數(shù)據(jù)吞吐量的測(cè)試過(guò)程如下：首先在本地開(kāi)啟8 個(gè)節(jié)點(diǎn)作為服務(wù)器節(jié)點(diǎn)，另外開(kāi)啟一個(gè)新端口作為客戶端節(jié)點(diǎn)，客戶端節(jié)點(diǎn)可以發(fā)送Request 消息和Update 消息；然后分別測(cè)試PBFT 算法、Raft 算法和RBFT 算法在相同環(huán)境下的數(shù)據(jù)吞吐量，同時(shí)測(cè)試公有鏈企業(yè)級(jí)操作系統(tǒng)(enterprise operation system, EOS)項(xiàng)目的股份授權(quán)證明（delegated proof of stake, DPoS）算法的數(shù)據(jù)吞吐量.測(cè)試過(guò)程采用EOSBenchTool 工具，設(shè)置Thread number為8，Transaction pool size 為3 000，Transaction batch size 為2 500; 最后隨機(jī)選取測(cè)試數(shù)據(jù)中的20組進(jìn)行比較，如圖6所示.

圖6 吞吐量圖Figure 6 Throughput diagram

圖6結(jié)果顯示：RBFT 算法基本保留了Raft 算法的高數(shù)據(jù)吞吐量，比PBFT 算法的數(shù)據(jù)吞吐量提高了25%，但作為實(shí)現(xiàn)拜占庭容錯(cuò)的代價(jià)是比Raft 算法的數(shù)據(jù)吞吐量下降了58%，其主要原因是在容錯(cuò)過(guò)程中多輪的消息傳遞和簽名收集.RBFT 算法的數(shù)據(jù)吞吐量比EOS 中DPoS 算法的數(shù)據(jù)吞吐量下降9%，主要原因是RBFT算法的代碼實(shí)現(xiàn)存在可優(yōu)化空間.

主節(jié)點(diǎn)切換速度會(huì)對(duì)共識(shí)效率產(chǎn)生影響，因?yàn)橹鞴?jié)點(diǎn)切換時(shí)共識(shí)停止，所以主節(jié)點(diǎn)切換時(shí)間也會(huì)影響算法的數(shù)據(jù)吞吐量產(chǎn)生.采用同樣的配置環(huán)境，模擬主節(jié)點(diǎn)宕機(jī)的情況，分別記錄Raft 算法、RBFT 算法和PBFT 算法的主節(jié)點(diǎn)切換時(shí)間，隨機(jī)選取10 組數(shù)據(jù)進(jìn)行對(duì)比，如圖7所示.

由圖7可以看出：RBFT 算法相比于PBFT 算法在主節(jié)點(diǎn)切換時(shí)間方面有了30%的提升，相比于非拜占庭容錯(cuò)的Raft算法僅僅降低了20%.分析圖6和7 可以得出RBFT 算法和Raft 算法的性能差異，RBFT 算法的主節(jié)點(diǎn)切換性能提升明顯，一方面是因?yàn)楹侠淼淖畲笙⒀舆t時(shí)間和高效的容錯(cuò)算法；另一方面是因?yàn)榘踩珷顟B(tài)保證了當(dāng)選Leader 的正確性，避免了重復(fù)選舉.

圖7 Leader 選舉時(shí)間圖Figure 7 Leader election time diagram

RBFT 算法作為一種高可拓展性算法，在客戶端發(fā)送相同請(qǐng)求數(shù)量的情況下，服務(wù)器節(jié)點(diǎn)數(shù)和數(shù)據(jù)吞吐量的關(guān)系如圖8所示.實(shí)驗(yàn)過(guò)程分別針對(duì)4 節(jié)點(diǎn)、8 節(jié)點(diǎn)、12 節(jié)點(diǎn)、16 節(jié)點(diǎn)的情況對(duì)數(shù)據(jù)吞吐量進(jìn)行測(cè)試.實(shí)驗(yàn)結(jié)果顯示：相比于PBFT 算法，RBFT 算法的數(shù)據(jù)吞吐量受節(jié)點(diǎn)數(shù)目增加的影響較弱，并且就線段趨勢(shì)而言，RBFT 算法的優(yōu)勢(shì)將伴隨著節(jié)點(diǎn)數(shù)目的增多而增強(qiáng).關(guān)于RBFT 算法保持高可拓展性的原因在于：一方面RBFT 算法保留了Raft 算法高效的共識(shí)邏輯，另一方面RBFT 算法具有低通信復(fù)雜度.

圖8 節(jié)點(diǎn)數(shù)與數(shù)據(jù)吞吐量關(guān)系圖Figure 8 Relationship between node and throughput

4.2 共識(shí)時(shí)延測(cè)試

共識(shí)時(shí)延表示的是客戶端向區(qū)塊鏈提交交易到另一方看到交易被提交的時(shí)間差，低的共識(shí)時(shí)延將會(huì)大大提升區(qū)塊鏈的性能.PBFT 算法和RBFT 算法的共識(shí)時(shí)延測(cè)試同樣在本地8節(jié)點(diǎn)的前提下進(jìn)行.根據(jù)4.1 節(jié)返回的時(shí)間戳計(jì)算共識(shí)時(shí)延，進(jìn)而得到如圖9所示的時(shí)延圖.

圖9顯示了RBFT 算法擁有更低的共識(shí)時(shí)延.共識(shí)時(shí)延是算法性能的最終體現(xiàn)，表明RBFT算法相比于PBFT 算法擁有更高的性能.

5 結(jié) 語(yǔ)

圖9 時(shí)延圖Figure 9 Time delay diagram

RBFT 算法是一種可拜占庭容錯(cuò)的Raft 算法，解決了Raft 算法在拜占庭場(chǎng)景下的Leader選舉和日志篡改問(wèn)題.首先，將容錯(cuò)過(guò)程與Raft 算法的AppendEntries 消息和RequestVote消息結(jié)合，利用BLS 閾值簽名代替投票過(guò)程，實(shí)現(xiàn)了RBFT 算法的高可拓展性和高數(shù)據(jù)吞吐量.安全狀態(tài)的提出，保證了所有非拜占庭節(jié)點(diǎn)日志在每輪共識(shí)結(jié)束后的最終一致性；然后，結(jié)合Raft 算法對(duì)RBFT 算法的安全性和活性進(jìn)行了分析證明；最后，由實(shí)驗(yàn)數(shù)據(jù)表明：RBFT算法相比于PBFT 算法，其數(shù)據(jù)吞吐量提升了25%，主節(jié)點(diǎn)切換速度提升了30%；相比于非拜占庭容錯(cuò)的Raft 算法，其數(shù)據(jù)吞吐量和主節(jié)點(diǎn)切換速度下降也不明顯.綜上所述，RBFT算法是一種可應(yīng)用于公鏈的高拓展性、高數(shù)據(jù)吞吐量、高安全性的共識(shí)算法.