一種使用量子隨機數(shù)的拜占庭容錯機制

◆任 明 湯紅波 王 理

（信息工程大學 河南 450001）

0 引言

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

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

1 PBFT算法

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

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

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

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

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

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

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

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

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

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

3 解決的問題

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

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

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

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

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

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

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

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

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

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

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

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

4.2 QRBFT機制

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

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

4.2.1 選舉過程

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

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

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

4.2.2 共識過程

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

圖2 Speculation Byzantine Fault Tolerance算法示意

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

圖3 QRBFT共識過程

4.3 QRBFT機制的性能

（1）算法復雜度

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

（2）安全性

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

（3）擴展能力

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

5 結(jié)束語

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