◆任 明 湯紅波 王 理

（信息工程大學(xué) 河南 450001）

0 引言

隨著區(qū)塊鏈技術(shù)在最近幾年的快速發(fā)展，該領(lǐng)域內(nèi)的應(yīng)用項目也在逐步增多。包括金融、物聯(lián)網(wǎng)、醫(yī)療在內(nèi)的諸多行業(yè)，都已經(jīng)開始在各自的業(yè)務(wù)內(nèi)使用區(qū)塊鏈技術(shù)。區(qū)塊鏈技術(shù)通過使用加密技術(shù)，可以為多種形式的業(yè)務(wù)場景提供可溯源。由于其具有不易篡改的特性，能夠在非信任的條件下為業(yè)務(wù)的參與者們提供可信的業(yè)務(wù)環(huán)境，有效地提升了業(yè)務(wù)邏輯的可信程度。

共識機(jī)制是區(qū)塊鏈技術(shù)中的重要組成部分之一。隨著區(qū)塊鏈技術(shù)的快速發(fā)展與應(yīng)用項目的逐步增多，在最初比特幣[1]系統(tǒng)中使用的 PoW(工作量證明)機(jī)制遠(yuǎn)不能達(dá)到業(yè)內(nèi)人士對于網(wǎng)絡(luò)性能的期望。因此，學(xué)者們陸續(xù)提出了不少關(guān)于共識機(jī)制改進(jìn)和優(yōu)化的方案。比較典型的包括PoS機(jī)制[2]、DPoS機(jī)制[3]、Raft協(xié)議[4]、Ripple協(xié)議[5]、SCP[6][7]，等等。拜占庭容錯(BFT)算法也是其中之一，用來解決在網(wǎng)絡(luò)通信可靠、但是節(jié)點自身可能出現(xiàn)問題的情況下如何達(dá)成共識的問題，該類算法的可靠性可以通過嚴(yán)格的數(shù)學(xué)證明作為保障。但是，所有的BFT問題的解決方案都存在復(fù)雜度過高而難以實現(xiàn)的問題。在2002年Castro與Liskov提出的PBFT算法[8]雖然將拜占庭容錯算法的復(fù)雜度由指數(shù)級降低到了多項式級別，但是其實現(xiàn)的復(fù)雜度仍然較高。同時，在Hyperledger Fabric項目V0.6版本中對其的應(yīng)用中，有研究學(xué)者發(fā)現(xiàn)PBFT算法的網(wǎng)絡(luò)擴(kuò)展能力會受到很大的限制[10]。因此，本文基于PBFT算法，提出一種簡易的拜占庭容錯共識協(xié)議來提升網(wǎng)絡(luò)中的共識效率。與此同時，將量子隨機(jī)數(shù)的概念引入共識機(jī)制的設(shè)計中，用來解決傳統(tǒng)的偽隨機(jī)數(shù)在共識參與者選擇過程中的偽造問題以及控制共識過程的安全問題。

1 PBFT算法

拜占庭容錯算法起源于1980年Leslie Lamport等人發(fā)表的論文《Polynomial Algorithms for Byzantine Agreement》，文中提出了針對拜占庭問題[9]的容錯算法。這種算法既要在保證節(jié)點間網(wǎng)絡(luò)狀態(tài)一致，同時也要確保記錄數(shù)據(jù)的正確性。

PBFT算法在一定程度降低了算法復(fù)雜度的同時，在密碼學(xué)方面引入了 RSA簽名算法與消息驗證的編碼、摘要技術(shù)來保證信息在傳遞的過程中不會受到惡意的篡改和破壞。此算法具有1/3的容錯率，當(dāng)出現(xiàn)不超過1/3的失效節(jié)點時，該算法可以保證網(wǎng)絡(luò)的安全性與活躍程度。事實上，即使有超過1/3的節(jié)點聯(lián)合作惡，雖然有可能因此造成系統(tǒng)出現(xiàn)分叉，但是仍然在密碼學(xué)方面會留下可溯源的證據(jù)。

在共識過程中，PBFT算法通過輪換或者隨機(jī)算法選擇主節(jié)點，在主節(jié)點沒有更換的時間段內(nèi)系統(tǒng)的配置信息稱作一個視圖（view）。通過三個階段的協(xié)議過程，PBFT算法能夠保證請求的發(fā)送順序在同一個視圖內(nèi)是正確的，并且可以確保在不同的視圖之間對請求進(jìn)行確認(rèn)的順序是具有確定性的。結(jié)果會在所有節(jié)點處理完請求之后返回給客戶端。在客戶端，將會檢查來自不同節(jié)點產(chǎn)生相同結(jié)果的數(shù)量，驗證該數(shù)量是否大于f+1（f為系統(tǒng)允許的最大失效節(jié)點數(shù)量）。如果滿足這個條件，就把它作為最終的排序結(jié)果。這個結(jié)果會通過有記賬功能的節(jié)點寫入?yún)^(qū)塊鏈。該算法的共識過程如圖1所示。

PBFT機(jī)制出現(xiàn)在包括聯(lián)盟鏈和私有鏈在內(nèi)的權(quán)限鏈場景中。這是因為PBFT算法重點解決的是對請求的排序共識問題。當(dāng)排序過程完成之后，網(wǎng)絡(luò)中的狀態(tài)已經(jīng)具有確定性，任何區(qū)塊都是最終確定的，不會產(chǎn)生分叉。因此，參與網(wǎng)絡(luò)的節(jié)點僅需要按照這個確定的排序結(jié)果，在處理完請求之后將最終結(jié)果記入本地賬本即可。當(dāng)網(wǎng)絡(luò)規(guī)模過大，需要經(jīng)過對共識機(jī)制進(jìn)行一定程度的調(diào)整，才能夠使用這種算法。在共識過程開始之前，首先通過選舉或者隨機(jī)算法選擇出一定數(shù)量的共識參與者(本文中稱為group)，這個數(shù)量可以通過其他機(jī)制進(jìn)行確認(rèn)，并且 group的成員可以進(jìn)行更替。之后，共識過程將在group內(nèi)進(jìn)行，其他的網(wǎng)絡(luò)節(jié)點可以通過廣播的方式從記賬節(jié)點獲取最終產(chǎn)生的區(qū)塊即可。

已經(jīng)有學(xué)者對PBFT進(jìn)行過簡化[11][12]。這兩種方案都是在提升了對網(wǎng)絡(luò)環(huán)境信任程度之后進(jìn)行的簡化，特別是文獻(xiàn)[12]的方式，基本需要建立在完全可信的環(huán)境中。他們在提升網(wǎng)絡(luò)吞吐量的同時，增加了較強(qiáng)的限定條件或者預(yù)先設(shè)定好的節(jié)點身份，這在網(wǎng)絡(luò)規(guī)模的擴(kuò)展方面會產(chǎn)生不利影響。

2 隨機(jī)數(shù)和隨機(jī)性

隨機(jī)數(shù)很早就已經(jīng)得到業(yè)內(nèi)人士的重視，在學(xué)者們對它的研究過程中誕生了不少產(chǎn)生隨機(jī)數(shù)的方法。這些產(chǎn)生隨機(jī)數(shù)的方法被統(tǒng)稱為隨機(jī)數(shù)發(fā)生器。在現(xiàn)代社會中的仿真學(xué)、物理學(xué)、密碼學(xué)等諸多領(lǐng)域中，隨機(jī)數(shù)都存在著重要的應(yīng)用，其本身應(yīng)當(dāng)具有不可預(yù)測的特性。目前，在上述領(lǐng)域?qū)嶋H的應(yīng)用中，通常會使用具有確定性的算法，通過隨機(jī)種子來產(chǎn)生隨機(jī)數(shù)。這種由算法產(chǎn)生的隨機(jī)數(shù)，其熵含量在很大程度上依賴于種子序列的熵值。雖然看似是均勻分布的，但是在這些隨機(jī)數(shù)之間存在自相關(guān)性，導(dǎo)致產(chǎn)生結(jié)果仍然是可以被預(yù)測的。隨著科技水平以及計算機(jī)計算能力的不斷提升，使用此類方式生成的偽隨機(jī)數(shù)會導(dǎo)致相關(guān)系統(tǒng)的安全性受到嚴(yán)重的威脅。不論是在密碼學(xué)，還是在區(qū)塊鏈的共識機(jī)制當(dāng)中，都會存在被破解、被利用的隱患。

目前，量子技術(shù)已經(jīng)成為密碼學(xué)和網(wǎng)絡(luò)安全業(yè)內(nèi)的熱門技術(shù)，在很多的應(yīng)用中都被認(rèn)為能夠起到重要作用。由于很難證明已經(jīng)形成的隨機(jī)數(shù)序列是否具有真正的隨機(jī)性，所以需要在隨機(jī)數(shù)的產(chǎn)生源頭及產(chǎn)生過程之中予以保證。隨機(jī)序列需要實現(xiàn)包含有最大熵含量的真正不可預(yù)測特性。量子隨機(jī)數(shù)的隨機(jī)特性是基于量子物理自身的不確定性，是能夠通過信息論進(jìn)行證明的。因此，通過物理隨機(jī)現(xiàn)象產(chǎn)生真正的隨機(jī)數(shù)來保證系統(tǒng)安全是可行的有效方式。

在區(qū)塊鏈技術(shù)中，隨機(jī)數(shù)能夠起到至關(guān)重要的作用，使用量子隨機(jī)數(shù)可以有效提升網(wǎng)絡(luò)中的安全性。從密碼學(xué)角度看，隨機(jī)數(shù)的可靠性會嚴(yán)重影響區(qū)塊鏈系統(tǒng)中密鑰體系的安全問題。共識機(jī)制作為區(qū)塊鏈技術(shù)的一個重要組成部分，同樣可以通過使用隨機(jī)數(shù)的方式提升網(wǎng)絡(luò)性能。一些共識機(jī)制為了提升網(wǎng)絡(luò)的可擴(kuò)展能力，會利用隨機(jī)數(shù)選擇共識協(xié)議的參與者，這樣既不會降低共識效率，也使網(wǎng)絡(luò)的擴(kuò)展能力得到有效提升。在這個過程中，可以利用量子物理學(xué)的理論生成真正的隨機(jī)數(shù)。此外，在主節(jié)點的更替機(jī)制中，量子隨機(jī)數(shù)同樣能夠發(fā)揮作用。

在對生成序列進(jìn)行隨機(jī)性檢測的問題研究中，有學(xué)者提出使用復(fù)雜度量化[13]以及其他一些統(tǒng)計測試方式進(jìn)行保證。但是，這些方式的核心思想是通過觀測進(jìn)行判斷，并不能有效檢測到惡意的人為設(shè)定。在一篇關(guān)于隨機(jī)數(shù)發(fā)生器的研究[14]中作者認(rèn)為，真正的隨機(jī)性只能通過物理原理上內(nèi)在的隨機(jī)性來進(jìn)行保證，可以利用量子測量中固有的隨機(jī)性來產(chǎn)生真隨機(jī)數(shù)；同時，可以通過量子信號與經(jīng)典噪聲的信噪比來估算真隨機(jī)性的大小。

3 解決的問題

在目前使用拜占庭容錯算法的共識機(jī)制中，存在以下三點關(guān)鍵的性能問題。

（1） BFT算法普遍復(fù)雜度高，通信開銷大

雖然業(yè)內(nèi)對BFT算法的研究已經(jīng)持續(xù)了將近四十年的時間，但是，其中大多數(shù)的研究長期停留在理論階段，缺少與之相符的程序代碼。這是由于 BFT算法普遍復(fù)雜度過高，難以實現(xiàn)造成的。雖然PBFT算法已經(jīng)在前人研究的基礎(chǔ)上明顯降低了算法的復(fù)雜度，但是在完成共識的過程中會產(chǎn)生大量的通信開銷。在網(wǎng)絡(luò)帶寬固定的條件下，當(dāng)網(wǎng)絡(luò)擴(kuò)展到一定規(guī)模之后，會由于節(jié)點間的通信開銷過大導(dǎo)致出現(xiàn)網(wǎng)絡(luò)擁塞，造成共識失敗，使得網(wǎng)絡(luò)的擴(kuò)展能力受到限制。同時，在現(xiàn)有的PBFT算法實現(xiàn)中，其復(fù)雜度依然相對較高。在確認(rèn)算法安全程度的前提下，簡化節(jié)點之間的通信過程，對共識協(xié)議進(jìn)行優(yōu)化等方式可以有效解決這類問題，使參與共識節(jié)點規(guī)模的擴(kuò)展能力得到提升。

（2） 隨機(jī)數(shù)的可靠性

使用傳統(tǒng)隨機(jī)數(shù)發(fā)生器產(chǎn)生的隨機(jī)數(shù)通常會使用長度有限的種子序列及確定性的算法生成。通過使用量子隨機(jī)數(shù)發(fā)生器，產(chǎn)生具有真正隨機(jī)性的隨機(jī)數(shù)。使用量子隨機(jī)數(shù)的共識機(jī)制能夠得到更高的可靠性。

（3） BFT算法的網(wǎng)絡(luò)擴(kuò)展能力

BFT算法的主要作用是解決請求的排序共識問題，通常是在強(qiáng)一致性要求下的聯(lián)盟鏈和私有鏈場景中使用。但是，隨著業(yè)務(wù)規(guī)模的發(fā)展，網(wǎng)絡(luò)中的節(jié)點數(shù)量也會越來越多。在這種情況下，當(dāng)參與共識的節(jié)點的數(shù)量達(dá)到一定規(guī)模的時候，共識效率會由于通信過程開銷過大造成的網(wǎng)絡(luò)擁塞，進(jìn)而造成共識失敗[15]。因此，當(dāng)網(wǎng)絡(luò)規(guī)模達(dá)到一定程度的時候，共識過程并不一定需要全部的節(jié)點參與。可以通過事先約定的機(jī)制對共識參與者進(jìn)行選擇，這個group的成員規(guī)?？梢栽诖_定節(jié)點間彼此信任的條件下盡可能小，以此來保證共識效率，并有效降低通信開銷。

4 基于量子隨機(jī)數(shù)的拜占庭容錯機(jī)制

4.1 量子隨機(jī)數(shù)發(fā)生器

量子隨機(jī)數(shù)發(fā)生器能夠為區(qū)塊鏈技術(shù)中的共識機(jī)制帶來多角度可靠性的提高。

通過理論建模的隨機(jī)數(shù)發(fā)生器可以實現(xiàn)較高的隨機(jī)數(shù)產(chǎn)生速率。但是，這種方式仍然依賴于隨機(jī)數(shù)發(fā)生器設(shè)備的可信程度，惡意的制造商仍然可以提前通過提前內(nèi)置的字符串預(yù)測隨機(jī)數(shù)的輸出情況。

基于設(shè)備的可信度，量子隨機(jī)數(shù)發(fā)生器（QRNG）可以分為三類。第一類是建立在完全可信設(shè)備上的實用QRNG，通?？梢酝ㄟ^對設(shè)備進(jìn)行適當(dāng)程度的校準(zhǔn)和建模高速生成隨機(jī)數(shù)。第二類是自我測試QRNG，它是在不信任設(shè)備的情況下生成隨機(jī)性可驗證的隨機(jī)數(shù)，其生成速率可能會受到信任條件的限制。第三類是半自測QRNG，它是一種在設(shè)備的可信程度和隨機(jī)數(shù)生成速率之間進(jìn)行一定程度權(quán)衡之后的中間產(chǎn)物。

4.2 QRBFT機(jī)制

QRBFT(Quantum Random Byzantine Fault Tolerance)是為區(qū)塊鏈技術(shù)服務(wù)的一種共識機(jī)制。提出此共識機(jī)制的目的是在網(wǎng)絡(luò)的擴(kuò)展能力以及共識效率的提升方面做出平衡。通過在協(xié)議中使用量子隨機(jī)數(shù)，能夠有效提升選取共識參與者的隨機(jī)性，能夠保證在非完全可信的網(wǎng)絡(luò)環(huán)境中參與共識過程節(jié)點的可靠性。

QRBFT機(jī)制可以分為兩個子過程：選舉和共識。

4.2.1 選舉過程

在當(dāng)前區(qū)塊鏈技術(shù)的研究過程中，也存在不少通過選舉過程生成區(qū)塊的共識協(xié)議。但是，它們大多采用選舉產(chǎn)生leader負(fù)責(zé)區(qū)塊生成的方式。這種方式在一定程度上確實能夠提升共識效率。但是，通常在使用此類方案的同時，也必須要配合使用leader的更替機(jī)制來解決可能發(fā)生的記賬節(jié)點崩潰等問題。

而在BFT算法中，解決的是共識與一定程度的容錯問題，在共識協(xié)議的擴(kuò)展能力方面會受到限制，這在其本身的算法中很難得到有效的解決。為了使 BFT算法能夠在更大規(guī)模的網(wǎng)絡(luò)環(huán)境中使用，同時，希望在盡可能多地讓網(wǎng)絡(luò)節(jié)點在參與共識過程的前提下不再引入其他額外的協(xié)議，提出將選舉過程與 BFT算法結(jié)合使用的共識機(jī)制。在此機(jī)制中，選舉過程將為BFT算法過程提供共識的參與者。

在超級賬本（Hyperledger）的子項目Sawtooth中使用了PoET共識機(jī)制[16]，節(jié)點上會部署統(tǒng)一的可靠計時器，基于對時間消逝的證明選擇記賬節(jié)點。我們在此基礎(chǔ)上進(jìn)行了思路的拓展，使用量子隨機(jī)數(shù)的方式對共識參與者進(jìn)行g(shù)roup的選取。當(dāng)新一輪共識過程開始前，全部的網(wǎng)絡(luò)節(jié)點通過各自的量子隨機(jī)數(shù)發(fā)生器生成一個隨機(jī)數(shù)，以廣播的方式發(fā)送給網(wǎng)絡(luò)中的其他節(jié)點。在一個時間周期內(nèi)，系統(tǒng)將直接選擇中間若干個隨機(jī)數(shù)對應(yīng)的節(jié)點作為共識過程的參與者，若干輪共識過程結(jié)束之后會重新要求節(jié)點生成隨機(jī)數(shù)，實現(xiàn)對 group的成員進(jìn)行更替。當(dāng)網(wǎng)絡(luò)中出現(xiàn)延遲，一些隨機(jī)數(shù)無法在指定的時間周期內(nèi)到達(dá)其他節(jié)點，節(jié)點間對選舉過程可能因此無法達(dá)成一致，即不同的網(wǎng)絡(luò)節(jié)點可能選擇了不同的group。因此，在節(jié)點選擇出group之后，會將group的信息形成摘要，發(fā)送給其他節(jié)點，收到此信息的節(jié)點將進(jìn)行驗證。只有在確認(rèn)group信息得到全網(wǎng)一半以上節(jié)點的情況下，該group的成員才能夠開始共識過程。此外，也可以引入檢查點機(jī)制來進(jìn)行一致性校驗和全網(wǎng)狀態(tài)的同步，但這樣做會帶來額外的開銷。

4.2.2 共識過程

當(dāng)選舉過程結(jié)束之后，網(wǎng)絡(luò)將進(jìn)入共識過程。在對PBFT算法的優(yōu)化方案中，文獻(xiàn)[11]在沒有收到信息的前提下使節(jié)點根據(jù)之前計算產(chǎn)生的結(jié)果直接進(jìn)行后續(xù)計算，副本節(jié)點不經(jīng)過共識過程直接執(zhí)行請求，也不需要考慮系統(tǒng)中的一致性問題，如圖2所示。文獻(xiàn)[12]則是通過指定一個區(qū)塊生成者（block generator）負(fù)責(zé)收集并驗證網(wǎng)絡(luò)中提出的交易信息，周期性地將它們批量打包成一個新的區(qū)塊提案。共識過程由區(qū)塊生成者和指定的區(qū)塊簽名者（小部分）依照配置好的規(guī)則完成，而其他的區(qū)塊簽名者（大多數(shù)）負(fù)責(zé)驗證區(qū)塊提案，并通過使用數(shù)字簽名批準(zhǔn)該提案。

圖2 Speculation Byzantine Fault Tolerance算法示意

在QRBFT的共識過程中，由選舉產(chǎn)生的共識group成員之間通過與選舉過程相同的隨機(jī)數(shù)方式選舉產(chǎn)生 leader。leader的更替采用輪換制度。因為參與共識過程的group是通過選舉過程產(chǎn)生的，因此可以認(rèn)為 group的成員是可以信任的。同時，QRBFT在算法中也進(jìn)行了相應(yīng)的調(diào)整。副本節(jié)點在收到來自leader節(jié)點的排序請求后，將會依據(jù)事先約定的規(guī)則對排序信息的合法性進(jìn)行驗證（如圖3所示）。如果排序信息符合條件，則可以確認(rèn)該排序是合法的；否則，副節(jié)點將向主節(jié)點重新請求排序信息。

圖3 QRBFT共識過程

4.3 QRBFT機(jī)制的性能

（1）算法復(fù)雜度

QRBFT算法針對PBFT算法在共識過程中復(fù)雜的通信開銷進(jìn)行了適度的簡化，將兩次的提交確認(rèn)過程轉(zhuǎn)變?yōu)閷π畔⒁?guī)則與格式的校驗。該驗證過程在節(jié)點本地進(jìn)行，不與其他節(jié)點進(jìn)行通信。在減少算法邏輯步驟的同時，也可以大幅度降低共識過程中的通信開銷。

（2）安全性

由于在共識機(jī)制中引入了量子隨機(jī)數(shù)，本地節(jié)點在選舉過程中無法預(yù)測其他節(jié)點產(chǎn)生的隨機(jī)數(shù)，并且在生成隨機(jī)數(shù)的過程中不可能進(jìn)行人為干預(yù)。所以，選舉group成員的過程與leader選舉的過程中，所有節(jié)點都是在公平可靠的環(huán)境中進(jìn)行的。由選舉產(chǎn)生的 group成員是真正隨機(jī)、無法被預(yù)測的，共識過程中的leader也是可靠的、可以被信任的。因此，在QRBFT共識機(jī)制中可以避免出現(xiàn)拜占庭問題，系統(tǒng)只需要解決leader節(jié)點出現(xiàn)故障情況下的更換問題。

（3）擴(kuò)展能力

在 BFT算法進(jìn)行之前增加選舉過程的目的是提升網(wǎng)絡(luò)的擴(kuò)展能力。傳統(tǒng)的BFT算法，特別是PBFT算法，不僅算法復(fù)雜度過高，而且共識過程繁雜的通信過程會使網(wǎng)絡(luò)規(guī)模受到非常嚴(yán)重的限制。通過引入選舉過程，可以使參與共識過程的節(jié)點規(guī)模得到有效控制，減少系統(tǒng)內(nèi)總體的通信次數(shù)，使由于通信信息占據(jù)的內(nèi)存盡可能降低，從而在保證網(wǎng)絡(luò)吞吐量的前提下使網(wǎng)絡(luò)的擴(kuò)展能力得到有效提升。

5 結(jié)束語

本文在PBFT的基礎(chǔ)上提出了一種引入選舉制度的拜占庭共識機(jī)制QRBFT，用以解決BFT算法在實際應(yīng)用過程中的擴(kuò)展能力問題。同時，該機(jī)制通過使用量子隨機(jī)數(shù)的方式提升選舉的隨機(jī)性，增強(qiáng)了共識機(jī)制的安全性能。改進(jìn)后的共識機(jī)制在一致性校驗和leader的更替機(jī)制方面還有待進(jìn)一步提高，尚存在改進(jìn)的需要。