一種基于分組的區(qū)塊鏈共識算法

張思賢 文 捷

(復(fù)旦大學(xué)計算機科學(xué)技術(shù)學(xué)院 上海 200433)

0 引 言

區(qū)塊鏈最先于文獻[1]中提出，作為虛擬貨幣比特幣的底層技術(shù)，因其去中心、不可篡改等特性而為大眾所熟悉，但也因為其基于算力的Pow算法浪費大量算力進行共識運算和吞吐量低而為人所詬病。Pow算法的出塊時間為10分鐘，一個交易從上鏈到確定不能被篡改，需要后續(xù)六個區(qū)塊的確認，也就是一個小時確認時間。并且基于Pow共識算法的區(qū)塊鏈系統(tǒng)每秒鐘只能處理七筆交易，并不能適用于當今的物聯(lián)網(wǎng)或者金融系統(tǒng)。為了緩解這一問題，Ethereum平臺嘗試提出Pos共識算法。Pos算法加入了幣齡的概念，提高了出塊的速度，但同時也引入了其他問題，如出塊速度不穩(wěn)定，導(dǎo)致分叉的出現(xiàn)，以及持幣不出塊等問題。另一方面，在聯(lián)盟鏈系統(tǒng)中，以IBM的Fabric平臺為例使用的為PBFT算法，其吞吐量能夠比公有鏈系統(tǒng)高出上千倍，并且不需要后續(xù)6個區(qū)塊的確認交易不可逆轉(zhuǎn)。在聯(lián)盟鏈系統(tǒng)中，交易一旦打包即可被認為不可逆，但隨著系統(tǒng)中節(jié)點的增多，為了達成共識其系統(tǒng)中需要進行的通信量也將上升，不具備很好的擴展性。文獻[3-4]嘗試從兩種途徑對PBFT算法進行改進，一個是引入gossip協(xié)議，另外一個是引入信用機制。文獻[7]提出一種交替式的共識算法進行交替出塊，文獻[8]提出了一種RMBC的區(qū)塊鏈使用DBFT共識算法，嘗試以分組的形式提高用戶節(jié)點進入?yún)^(qū)塊鏈的數(shù)量。文獻[10]嘗試分析Pow類的共識算法以及BFT類的共識算法。

由于現(xiàn)行區(qū)塊鏈技術(shù)存在的瓶頸，并不適用于當今的物聯(lián)網(wǎng)技術(shù)，現(xiàn)行的物聯(lián)網(wǎng)技術(shù)都是廠商各自定義的標準，彼此之間并不能互聯(lián)，數(shù)據(jù)不能打通，而區(qū)塊具有可信任、不可篡改等特性，因此可以嘗試將其應(yīng)用于物聯(lián)網(wǎng)系統(tǒng)中，用于處理涉及到兩個物聯(lián)網(wǎng)域的問題。

本文嘗試從共識算法出發(fā)，提出一種兩個階段式的區(qū)塊鏈共識算法，并以此算法提出一種物聯(lián)網(wǎng)設(shè)備互聯(lián)的架構(gòu)。

1 預(yù)備知識

1.1 盲簽名

盲簽名[9]因為具有盲性這一特點，可以有效保護所簽署的具體內(nèi)容，廣泛應(yīng)用于電子選舉的實現(xiàn)中。投票者先將自己所投的選票進行盲化，然后讓簽名者對于盲化信息進行簽名。在投票系統(tǒng)中，盲化后的信息即為選票。

對簽名進行盲化處理：

盲化消息：m′=mre(modN)

(1)

簽名消息：s′=(m′)d(modN)

(2)

除盲信息：s=s′×r-1(modN)

(3)

原理為：

red≡r(modN)

s≡s′×r-1≡(m′)dr-1≡mdredr-1≡mdrr-1≡md(modN)

盲簽名的盲化、簽署及除盲過程如圖1所示。

圖1 盲簽名的盲化、簽署以及除盲過程

1.2 實用拜占庭算法(PBFT)

文獻[5]提出實用拜占庭算法，用于解決分布式系統(tǒng)中出現(xiàn)的拜占庭問題，其容錯率為：f≤(n-1)/3。其中：n為系統(tǒng)的總節(jié)點數(shù)；f為出現(xiàn)故障的節(jié)點數(shù)。

該算法的主要流程分為3個階段：

pre-prepare：主節(jié)點向所有備份節(jié)點發(fā)送準備消息，此時節(jié)點狀態(tài)為pre-prepare。

prepare：包括主節(jié)點在內(nèi)的所有備份節(jié)點在收到準備消息后，確定無誤，向外廣播信息，并且進入prepare階段。

commit：當收到若干個來自其他副本的prepare信息后即可進入commit階段。

實用拜占庭算法相對簡單高效，但隨著節(jié)點數(shù)目的增多，其通信量會急速上升，不適用于大規(guī)模的聯(lián)盟鏈環(huán)境。文獻[6]嘗試在Fabric平臺中對其進行測試節(jié)點與性能的關(guān)系，文獻[13]嘗試改造Fabric的架構(gòu)，以此提高其吞吐量。

2 算法設(shè)計

2.1 算法介紹

整個算法大致分為三個階段，前期階段為進入該系統(tǒng)，然后將各節(jié)點分配到每個組中。第一階段使用盲簽名投票的形式進行主節(jié)點的選取。第二階段使用實用拜占庭算法從上一個階段中勝利的節(jié)點中選出主節(jié)點進行區(qū)塊的生成。

第一階段中，參與競選的i到i+4節(jié)點，將其選票以盲化的形式(盲化內(nèi)容為競選者的地址)，連同區(qū)塊信息傳遞至下一個節(jié)點，后續(xù)節(jié)點首先對區(qū)塊信息進行驗證，然后對各個節(jié)點盲化后的信息進行簽署。

由于經(jīng)過盲處理各個節(jié)點并不知道其為哪個節(jié)點投票，只需要對交易記錄進行驗證與傳遞。等到區(qū)塊信息回到i至i+4節(jié)點，i至i+4節(jié)點則可進行除盲處理，根據(jù)選票選出勝利節(jié)點，并且廣播獲勝信息，將交易數(shù)據(jù)連同簽署信息寫入?yún)^(qū)塊鏈中。在傳播的過程中，投票節(jié)點并不知道到底投的是i到i+4中的哪一個節(jié)點。

1) 前期階段。區(qū)塊鏈網(wǎng)絡(luò)中的各個節(jié)點都保存著一份列表，列表上面會出現(xiàn)一個聯(lián)盟內(nèi)節(jié)點的地址，這個地址標識著這些節(jié)點之間為一個聯(lián)盟。此聯(lián)盟內(nèi)節(jié)點數(shù)存在一個上限，下文假設(shè)為M。

新加入到網(wǎng)絡(luò)中的節(jié)點a，向周邊發(fā)放自己的公鑰P，然后進入等待狀態(tài)，網(wǎng)絡(luò)中的其他節(jié)點b收到來自a的請求加入信息后，確定自己的聯(lián)盟內(nèi)節(jié)點數(shù)目仍未到達上限，將接受加入信息附帶上時間戳，以及本節(jié)點的公鑰S，使用P加密，并以報文的形式傳送，表示該節(jié)點已被加入至本聯(lián)盟。

在收到確定報文后(可能同時會收到多個報文，以時間戳最早的為主)， 確定加入該聯(lián)盟，并且發(fā)送回執(zhí)報文，使用S加密，表示接收成功。b收到報文后向全組節(jié)點廣播，更新聯(lián)盟節(jié)點列表，并向節(jié)點a同步最新的節(jié)點列表，a隨即同步全網(wǎng)中區(qū)塊的所有數(shù)據(jù)。

2) 第一階段。聯(lián)盟中的節(jié)點以某種環(huán)的形式進行連接，如圖2所示。

圖2 節(jié)點以環(huán)的形式進行連接

(1) 從聯(lián)盟中隨機選取一個節(jié)點i作為初始節(jié)點，i以及i后序的i+1、i+2、i+3、i+4將作為本輪的候選節(jié)點。

(2) 以環(huán)的形式從i+4開始傳遞其投票信息，后續(xù)每個節(jié)點將從上寫入其投票狀況，其投票信息使用上文提及的盲簽名進行生成，進行盲化。

(3) 當投票信息傳遞回i節(jié)點時可確認本輪投票結(jié)束，參與競選的各節(jié)點依次對盲簽名結(jié)果進行除盲處理，即可統(tǒng)計得到相應(yīng)的票數(shù)。

(4)i至i+4節(jié)點可觀察到投票的結(jié)果，確定自己是否獲勝，并且對外傳遞信息。

(5) 參與本輪投票并且成功選出勝利者的節(jié)點，將能獲得獎勵。

(6) 下一輪的共識將從i+5開始。

(7) 待下次循環(huán)進行至i節(jié)點，則可判定一次循環(huán)結(jié)束，重新排列其環(huán)狀結(jié)構(gòu)，再次進行主節(jié)點的選取。

(8) 勝出節(jié)點進入第二階段共識。

3) 第二階段。由于使用分組的形式，因此將有若干個勝利節(jié)點進入第二階段的共識。在第二階段中將使用PBFT算法進行數(shù)據(jù)的同步，其中主節(jié)點的選取將以j=h%N的形式進行選取，h為區(qū)塊鏈的長度，N為參與共識的節(jié)點個數(shù)，結(jié)束后回到第一輪共識。

2.2 算法分析

1) 運行效率。將此節(jié)點應(yīng)用于規(guī)模較大的聯(lián)盟鏈環(huán)境中，能夠有效降低網(wǎng)絡(luò)中節(jié)點需要進行交流的通信量。使用PBFT算法，當節(jié)點數(shù)目上升的時候?qū)?dǎo)致性能的下降。在達成共識的過程中，需要進行信息的交換，節(jié)點數(shù)目越多需要的數(shù)據(jù)交換量就越多，在未限定節(jié)點數(shù)目的PBFT算法中需要的通信量為O(n2)；在節(jié)點數(shù)目為1 000的情況下所需要交換的通信量為1 000 000；改進后，由于進入PBFT算法的節(jié)點由原來的1 000個分為現(xiàn)在的5組，每組中只存在一個節(jié)點的勝出，因此通信量為25，為原本的1/4 000。由于在第一階段中，只需要進行一輪投票就能選出勝者，其通信量為O(n)。若基于效率的原因考慮，勝出第一輪進入第二輪的節(jié)點可以選擇復(fù)制后續(xù)若干個區(qū)塊的生成，然后將出塊權(quán)轉(zhuǎn)給下一個leader節(jié)點，此時整個系統(tǒng)的運行效率與PBFT算法相仿，并且能夠容納更多的節(jié)點。

2) 安全性。由于使用盲簽名的形式進行投票，節(jié)點間并不知道彼此間投票的結(jié)果，并且投票結(jié)果不能篡改，這提高了選票結(jié)果的隨機性。由于投票者并不知道其投票的候選人為哪一位，因此只能隨機從候選節(jié)點中選取一人進行投票，直到最后結(jié)果公布，參與投票的候選節(jié)點才會知道知道自己所投選的節(jié)點為哪一個。

3) 獎勵機制。在Pow類型的共識算法中，獎勵機制是基于挖礦的性質(zhì)，節(jié)點進行哈希運算，成功挖掘出區(qū)塊就能獲得獎勵。本文算法由于不存在挖礦這一環(huán)節(jié)，可以將獎勵的機制加入至前期投票的過程中，參與投票并且成功票選出勝利的節(jié)點以及勝出節(jié)點將能獲得獎勵，以降低節(jié)點間的相互競爭，使系統(tǒng)穩(wěn)定運行下去。

4) 硬分叉。由于節(jié)點的最終出塊是基于PBFT算法，因此能夠有效避免分叉的問題。因為區(qū)塊的節(jié)點都是經(jīng)過最終投票來決定的，不存在像Pow算法中節(jié)點同時挖塊成功所導(dǎo)致的分叉問題。

5) 聯(lián)盟鏈。該算法能在聯(lián)盟鏈環(huán)境下進行使用，以此緩解PBFT算法帶來的通信量大的問題，以此容納更多的節(jié)點進入網(wǎng)絡(luò)。

6) 使用環(huán)進行連接。該算法在分組中使用環(huán)進行連接的主要原因在于，分組中的節(jié)點相對于全網(wǎng)節(jié)點，數(shù)量較少，使用環(huán)傳遞數(shù)據(jù)更加高效，若在全網(wǎng)進行環(huán)的連接，傳遞投票信息與區(qū)塊信息將受網(wǎng)絡(luò)的嚴重影響。數(shù)據(jù)的傳遞時間將隨著節(jié)點數(shù)目的上升而上升，節(jié)點越多這個環(huán)就越大，不能保證穩(wěn)定的出塊速度。

3 應(yīng) 用

可嘗試將該算法應(yīng)用于物聯(lián)網(wǎng)[11]系統(tǒng)中?，F(xiàn)行的物聯(lián)網(wǎng)系統(tǒng)中，并沒有一個嚴格的標準，還處于不同的廠商之間互相制定標準，并且大多數(shù)為一些性能較弱的設(shè)備。另一方面由于節(jié)點的性能相對較弱，不能進行較為復(fù)雜的共識算法，如Pow與Pos共識算法。文獻[2]提出基于物聯(lián)網(wǎng)系統(tǒng)進行改造的算法，改變Pow算法的計算公式，讓節(jié)點更加容易計算出結(jié)果。我們嘗試從上文中提出的共識算法出發(fā)，提出一種新的基于區(qū)塊鏈物聯(lián)網(wǎng)共識架構(gòu)。

我們所提出的物聯(lián)網(wǎng)系統(tǒng)將分為兩層：內(nèi)部系統(tǒng)與外部系統(tǒng)。內(nèi)部系統(tǒng)負責(zé)管理一系列性能相對較弱的節(jié)點，外部系統(tǒng)負責(zé)管理一系列性能相對較強的節(jié)點。內(nèi)部系統(tǒng)對應(yīng)一系列性能較弱的設(shè)備，如：燈、共享自行車等，其主節(jié)點為一系列性能較好的節(jié)點，對應(yīng)一些性能相對較好、對于電力不是瓶頸的設(shè)備，如路由器、平板電腦等。

3.1 內(nèi)部系統(tǒng)

內(nèi)部系統(tǒng)的組成為一系列性能相對較差的節(jié)點以及一部分性能相對較好的節(jié)點，彼此組成環(huán)的形式，其中內(nèi)部系統(tǒng)負責(zé)維護一條關(guān)于自身內(nèi)部系統(tǒng)的區(qū)塊鏈用于記錄每一筆交易操作。

性能較差節(jié)點：負責(zé)投票，不負責(zé)數(shù)據(jù)的存儲以及與外部系統(tǒng)直接交互。若需要數(shù)據(jù)，則需向性能較好的節(jié)點發(fā)起查詢操作即可，可部署智能合約，進行投票以及數(shù)據(jù)的自動轉(zhuǎn)發(fā)至下一個節(jié)點。當發(fā)起主節(jié)點選取時，投票信息在節(jié)點間進行傳遞，性能較差的節(jié)點需要調(diào)用智能合約隨機地從候選地址中進行選取，并且對候選地址生成的信息進行盲簽，然后將數(shù)據(jù)傳遞至下一個節(jié)點中。

性能較好節(jié)點：負責(zé)打包交易，負責(zé)與外部系統(tǒng)進行交互。一般情況下，一個內(nèi)部系統(tǒng)中將存在若干個性能較好的節(jié)點，彼此間互相參與競選成為本回合的勝利節(jié)點，彼此對本系統(tǒng)的所有數(shù)據(jù)進行備份，并且與外部系統(tǒng)進行交互。基于性能的考慮，一次節(jié)點競選成為本回合的勝出節(jié)點后，需要負責(zé)后續(xù)若干個區(qū)塊的生成，以此減少節(jié)點間來回投票所帶來的消耗。對于內(nèi)部系統(tǒng)來說，其效率較高，一旦主節(jié)點被選取成功，后續(xù)任何打包數(shù)據(jù)上鏈的操作，將不需要進行耗費資源的Pow計算，只要副本節(jié)點間沒有任何異議，則可直接進行數(shù)據(jù)的上鏈。性能較差的節(jié)點只需要接受來自主節(jié)點的指令或者查詢交易記錄即可，無需進行數(shù)據(jù)的全量備份。

具體流程如下：

1) 內(nèi)部系統(tǒng)中的每個節(jié)點將以某種環(huán)的形式進行連接，彼此只需知道下一個節(jié)點的地址。

2) 參與競選的i，i+1、i+2、i+3、i+4等若干個性能較好的節(jié)點，發(fā)起競選操作，將其公鑰使用盲簽的形式，生成一個地址，同時寫進一個區(qū)塊中，連同交易進行傳遞。

3) 接收到的節(jié)點，將從i到i+4的所生成的數(shù)據(jù)中隨機選取一個進行盲簽，然后往下一個區(qū)塊進行傳遞。

4) 若下一個接收到的節(jié)點并不為i，則重復(fù)3)的操作。

5) 當區(qū)塊傳遞到i至i+4節(jié)點時，可將區(qū)塊中被盲簽化的數(shù)據(jù)進行除盲處理，統(tǒng)計結(jié)果并選出勝利節(jié)點，向網(wǎng)絡(luò)中廣播本輪勝出的節(jié)點。

6) 勝出的節(jié)點，將交易進行打包，生成區(qū)塊，并且廣播至相鄰的i+1至i+4節(jié)點，待若干個區(qū)塊成功生成后，則重新發(fā)起競選操作。

3.2 外部系統(tǒng)

外部系統(tǒng)為一系列性能較好的節(jié)點，在這里我們可以理解為不同的系統(tǒng)，作為聯(lián)盟間的系統(tǒng)共同維護著一條聯(lián)盟之間的區(qū)塊間的區(qū)塊鏈。由于節(jié)點數(shù)目相對內(nèi)部系統(tǒng)較少，因此可直接使用PBFT算法進行數(shù)據(jù)的同步與寫入，其中主節(jié)點的選取沿用j=h%N(h仍然為區(qū)塊鏈的長度，N為涉及到的廠商的數(shù)目)的形式進行選取?；谝晥D切換帶來消耗等原因，假如在外部系統(tǒng)的主節(jié)點不存在作惡的情況下，將負責(zé)若干個回合區(qū)塊的生成，再重新選取。

3.3 跨鏈操作

外部系統(tǒng)可作為系統(tǒng)間跨鏈操作的媒介。跨鏈指的是兩個相互獨立的區(qū)塊鏈系統(tǒng)進行互操作，大多用于虛擬貨幣的交換。文獻[12]指出了區(qū)塊鏈跨鏈系統(tǒng)中架構(gòu)，在物聯(lián)網(wǎng)系統(tǒng)中我們可以使用內(nèi)部系統(tǒng)的主節(jié)點作為內(nèi)部系統(tǒng)以及外部系統(tǒng)之間的調(diào)節(jié)點。在此可以理解為兩個互為獨立的系統(tǒng)之間的互操作或者兩個不同的物聯(lián)網(wǎng)系統(tǒng)之間數(shù)據(jù)的傳遞，區(qū)塊鏈技術(shù)保證了數(shù)據(jù)的正確性。由于使用兩層的形式，任何來自外部的指令都能經(jīng)被內(nèi)部系統(tǒng)的主節(jié)點攔截，并且由于使用了區(qū)塊鏈技術(shù)可溯源不可篡改等性質(zhì)，保證了交易數(shù)據(jù)的真實性，操作一旦發(fā)生并且上鏈，將不能被篡改與抵賴，可使用智能合約的形式進行數(shù)據(jù)格式的轉(zhuǎn)換。

具體流程如下：

1) 首先內(nèi)部系統(tǒng)A中的某一節(jié)點向當前的leader節(jié)點發(fā)起一筆向外部節(jié)點進行操作。

2) leader將其廣播至外部系統(tǒng)中，涉及到的相關(guān)內(nèi)部系統(tǒng)B的主節(jié)點，對相應(yīng)信息進行驗證，若無任何異議，則發(fā)送至相應(yīng)的內(nèi)部節(jié)點中進行操作。

3) 相應(yīng)的內(nèi)部節(jié)點接收到請求后，若確認無誤執(zhí)行操作，并要求主節(jié)點將其交易打包進塊，內(nèi)部系統(tǒng)B的主節(jié)點將數(shù)據(jù)打包上鏈，結(jié)果最終寫進區(qū)塊鏈中。

4) 外部系統(tǒng)接收到該結(jié)果已被B系統(tǒng)執(zhí)行后，將該交易記錄上鏈，并且通知A系統(tǒng)。

5) A系統(tǒng)將交易上鏈，確定本次跨鏈操作執(zhí)行完畢。

3.4 出錯處理

1) 若中間某一環(huán)節(jié)出現(xiàn)錯誤，整個系統(tǒng)將進行回滾，若在外部系統(tǒng)中涉及到的相關(guān)節(jié)點將操作回絕，則內(nèi)部系統(tǒng)A將立即得到反饋，并將其反饋至相應(yīng)的內(nèi)部節(jié)點。若此筆操作由于某種原因被取消，交易信息可自行選擇記錄上鏈。

2) 若內(nèi)部系統(tǒng)B中將操作進行回絕，則B中的節(jié)點則會將操作失敗以及其原因回調(diào)給內(nèi)部系統(tǒng)A，后續(xù)操作如1)。

3.5 整體優(yōu)勢

1) 由于使用了三層區(qū)塊鏈的形式，其操作數(shù)據(jù)將全程上鏈，此時各個區(qū)域的節(jié)點都能從區(qū)塊鏈中獲取交易信息，若對歷史操作記錄存疑，可直接在鏈上進行查詢。

2) 該系統(tǒng)相對穩(wěn)定，若系統(tǒng)出現(xiàn)宕機或其他問題，則可由其他性能相差無幾的節(jié)點接替其主節(jié)點的位置。性能較差的節(jié)點并不需要進行區(qū)塊鏈的維護，只需要接受來自主節(jié)點的指令，以及進行主節(jié)點的選取。

3) 由于使用leader節(jié)點代為跟蹤后續(xù)的操作，因此內(nèi)部系統(tǒng)中發(fā)起交易的節(jié)點可以繼續(xù)做相應(yīng)的操作，等待事件執(zhí)行完畢后，會得到回傳。

4) 使用層層驗證的機制，涉及到三個環(huán)節(jié)的校驗：內(nèi)部系統(tǒng)A的主節(jié)點，內(nèi)部系統(tǒng)B的主節(jié)點，以及內(nèi)部系統(tǒng)相應(yīng)執(zhí)行的節(jié)點。這保證了跨域系統(tǒng)中的節(jié)點不會頻繁收到惡意的指令。

5) 所有存儲在區(qū)塊上的信息，使用Merkle Tree(默克爾樹)[3]的形式進行組織，用于快速驗證和快速查找。

6)使用了智能合約進行數(shù)據(jù)格式的轉(zhuǎn)換，解決不同廠商之間存在的數(shù)據(jù)格式不一致的問題。

7)為了防止節(jié)點的作惡，可使用保證金的形式，每當涉及到跨鏈的操作，需要向內(nèi)部系統(tǒng)中的主節(jié)點發(fā)一筆交易以及保證金，其保證金在交易已經(jīng)確定正式被執(zhí)行之前將鎖定。隨著操作記錄的上鏈，保證金將解鎖。在確定交易記錄被上鏈之前，可使用智能合約對保證金進行鎖定。

8) 使用分域的形式，可實現(xiàn)兩個物聯(lián)網(wǎng)設(shè)備域之間跨域操作，使用leader節(jié)點進行后續(xù)交易的跟蹤，各個域內(nèi)的其他節(jié)點可繼續(xù)其自身的其他任務(wù)，而無需時刻跟蹤其發(fā)出去的操作，待后序操作成功leader節(jié)點將會告知。

4 結(jié) 語

本文提出一種兩階段式的共識算法，在第一階段中使用投票的形式選取勝利節(jié)點，在第二階段中進行PBFT算法實現(xiàn)區(qū)塊的生成，解決了PBFT算法無法適用于節(jié)點規(guī)模較大的情況。未來將嘗試從第二階段進行改進?；诖怂惴ㄌ岢鲆环N物聯(lián)網(wǎng)設(shè)備的架構(gòu)體系，內(nèi)部系統(tǒng)組織性能較低的節(jié)點，只負責(zé)隨機進行投票，選舉出主節(jié)點和執(zhí)行主節(jié)點，或者對外部系統(tǒng)分發(fā)命令，外部系統(tǒng)使用性能較好的節(jié)點管理內(nèi)部系統(tǒng)的數(shù)據(jù)上鏈、外部系統(tǒng)的數(shù)據(jù)上鏈以及跨鏈操作等，使用智能合約進行數(shù)據(jù)格式的轉(zhuǎn)換，用于解決各個產(chǎn)商之間數(shù)據(jù)格式不兼容的問題。