具有狀態(tài)合法性驗(yàn)證的區(qū)塊鏈一致性算法研究

, ,,

(1.中國科學(xué)院計(jì)算機(jī)網(wǎng)絡(luò)信息中心,北京 100190; 2.中國互聯(lián)網(wǎng)絡(luò)信息中心,北京 100190; 3.中國科學(xué)院大學(xué),北京 100190)

0 概述

區(qū)塊鏈在不可靠的分布式環(huán)境中維護(hù)了一個公共的總賬[1],這個總賬由一系列的匿名參與者來維護(hù)和擴(kuò)展。近年來,區(qū)塊鏈網(wǎng)絡(luò)吸引了越來越多的工程人員、學(xué)者和投資者的注意。伴隨著大量的資本投入[2],區(qū)塊鏈得到了快速部署,已經(jīng)成為了一項(xiàng)公共基礎(chǔ)設(shè)施。

由于區(qū)塊鏈沒有可信任的中心節(jié)點(diǎn),這使得設(shè)計(jì)和實(shí)現(xiàn)去中心化的域名系統(tǒng)(Domain Name System,DNS)[3]、公鑰基礎(chǔ)設(shè)施(Public Key Infrastructure,PKI)和去中心化的文件存儲成為現(xiàn)實(shí)。

現(xiàn)有金融體系中,為了確保安全,當(dāng)涉及大額交易和可疑交易時通常需要特殊的監(jiān)管和審查[4]。而對于去中心化的比特幣來說,不受監(jiān)管是其能夠流行的部分原因之一,但同時也會給大額交易的交易方帶來潛在的風(fēng)險。研究者提出讓國際貨幣基金組織(International Monetary Fund,IMF)參與到比特幣的運(yùn)營中[5],但如何保證監(jiān)管者IMF不成為新的中心,還尚未解決。

對于去中心化的域名系統(tǒng),當(dāng)域名注冊存在沖突,即權(quán)威機(jī)構(gòu)和個人同時申請一個權(quán)威域名,權(quán)威域名的歸屬問題是由獲得區(qū)塊寫入機(jī)會的單個節(jié)點(diǎn)決定,單個節(jié)點(diǎn)一旦出錯,將導(dǎo)致此權(quán)威域名被個人注冊而無法更改。

去中心化的文件存儲系統(tǒng)中,有版權(quán)問題或者不合法規(guī)的資源一旦上傳成功,除了上傳者本身,其他人很難刪除。對于廣泛運(yùn)行的點(diǎn)對點(diǎn)(Peer to peer,P2P)網(wǎng)絡(luò)而言[6],通常是在其部署爬蟲網(wǎng)絡(luò)來檢測非法資源的路徑,并將其加入黑名單,從而達(dá)到保護(hù)網(wǎng)絡(luò)的目的。爬蟲軟件只能檢測哪些資源是非法,而無法阻止資源的上傳,并且引入第三方的檢測方法,會帶來更多的問題。

上述基于區(qū)塊鏈的3種應(yīng)用,都需要在不安全的分布式環(huán)境中保持全局一致性。轉(zhuǎn)賬交易的記錄、域名的管理、文件的上傳和更改,對外都需要保持一致性。每一個具體的操作,都涉及了狀態(tài)的轉(zhuǎn)換。上述問題的根源在于,區(qū)塊鏈在寫入時,只需要提供正確工作量的證明,而不對其狀態(tài)轉(zhuǎn)換進(jìn)行合法性驗(yàn)證。

不安全的分布式環(huán)境中的一致性問題稱為拜占庭一致性[7]。最初拜占庭一致性問題需要指數(shù)級的算法才能解決,隨后人們提出了多項(xiàng)式級別的拜占庭協(xié)議[8],極大降低了拜占庭系統(tǒng)的開銷,使其在分布式系統(tǒng)中的應(yīng)用成為可能。解決拜占庭一致性的算法大致可分為2類:中心化算法和去中心化的算法。

去中心化算法能夠解決中心化算法中存在的單點(diǎn)故障,并且能夠容忍更多的故障節(jié)點(diǎn)。區(qū)塊鏈技術(shù)作為去中心化算法的代表,其有效性經(jīng)歷了廣泛的實(shí)踐驗(yàn)證。但去中心化一致性算法存在未考慮到狀態(tài)轉(zhuǎn)換的合法性由誰決定的問題。區(qū)塊鏈的處理方法是由獲得區(qū)塊寫入權(quán)力的單個節(jié)點(diǎn)決定,這就違背了去中心化的初衷。因此,本文在區(qū)塊鏈協(xié)議上引入了合法性驗(yàn)證的法定人數(shù)投票,由法定人數(shù)對系統(tǒng)的狀態(tài)轉(zhuǎn)換有效性進(jìn)行驗(yàn)證。

1 相關(guān)研究

拜占庭將軍問題是點(diǎn)對點(diǎn)通信中的基本問題,其含義是一些拜占庭將軍率領(lǐng)他們的部隊(duì)要攻占敵人的一個城池,每個將軍只能控制自己的部隊(duì),并且通過信使傳遞消息給其他將軍,將軍之中存在叛徒,如何設(shè)計(jì)一種策略使忠誠的將軍達(dá)成一個不算壞的行動協(xié)議而不受叛徒的挑撥。

隨后研究者提出了中心化的拜占庭一致性協(xié)議[9],協(xié)調(diào)者的引入降低了消息傳遞的復(fù)雜度,同時提高了最好情況下的性能。中心化算法在最好情況下,需要α輪消息交換(α是常數(shù)),但在最壞情況下,則需要α(t+1)輪消息交換[10](t是最大出錯節(jié)點(diǎn)個數(shù))。中心化一致性協(xié)議中協(xié)調(diào)者的更換通常由超時條件觸發(fā),因此,協(xié)調(diào)者能夠在不被檢測到的情況下,故意推遲消息的發(fā)送,降低系統(tǒng)的吞吐[11]。這促使了去中心化一致性算法的發(fā)展。因此,本文研究的重點(diǎn)在于如何使去中心化的區(qū)塊鏈一致性算法具有狀態(tài)合法性驗(yàn)證,并提高系統(tǒng)容錯率。

1.1 單節(jié)點(diǎn)合法性驗(yàn)證

兩階段提交協(xié)議[12]是在計(jì)算機(jī)網(wǎng)絡(luò)、數(shù)據(jù)庫領(lǐng)域內(nèi),為了在進(jìn)行事務(wù)處理過程中能夠保持原子性和一致性而設(shè)計(jì)的一種算法。兩階段提交將一個事務(wù)的提交處理過程分成了投票和執(zhí)行2個階段,協(xié)調(diào)者向所有的參與者廣播投票請求,當(dāng)協(xié)調(diào)者收到了所有參與者的同意消息后,協(xié)調(diào)者廣播提交請求,當(dāng)協(xié)調(diào)者收到了所有參與者的提交完成消息后,這個事務(wù)才算是提交成功。兩階段提交的優(yōu)點(diǎn)在于消息傳遞次數(shù)少,實(shí)現(xiàn)方便。其缺點(diǎn)是容錯率低,只要有一個參與者拒絕投票或者提交失敗,整個事務(wù)無法完成。此外,兩階段協(xié)議要應(yīng)用在拜占庭環(huán)境中,還需要解決選舉協(xié)調(diào)者和更換協(xié)調(diào)者的問題。

本文在兩階段提交基礎(chǔ)上,設(shè)計(jì)了選舉和更換協(xié)調(diào)者的策略,使其能夠在區(qū)塊鏈中完成法定人數(shù)的投票確認(rèn)。當(dāng)正常節(jié)點(diǎn)獲得區(qū)塊寫入機(jī)會進(jìn)行統(tǒng)計(jì)投票時,執(zhí)行了類似的兩階段提交協(xié)議,區(qū)別在于傳統(tǒng)兩階段的法定集合是所有節(jié)點(diǎn),而本文的法定集合是半數(shù)節(jié)點(diǎn),這提高了系統(tǒng)的容錯率。

1.2 多節(jié)點(diǎn)合法性驗(yàn)證

文獻(xiàn)[13]提出了實(shí)用拜占庭容錯協(xié)議(Practical Byzantine Fault Tolerance,PBFT),使得拜占庭協(xié)議在分布式系統(tǒng)中應(yīng)用成為可能。PBFT采用了主從模式(Primary and backups)和法定人數(shù)(Quorum),法定人數(shù)為2f+1,其中,f為出錯節(jié)點(diǎn)個數(shù),總結(jié)點(diǎn)個數(shù)為3f+1。正常情況下PBFT協(xié)議的運(yùn)行如圖1所示。當(dāng)主節(jié)點(diǎn)收到客戶的請求后,向其他的從屬節(jié)點(diǎn)發(fā)送PRE-PREPARE消息,當(dāng)從屬節(jié)點(diǎn)收到PRE-PREPARE消息后,如果其同意,那么向網(wǎng)絡(luò)中的其他從屬節(jié)點(diǎn)廣播PREPARE消息,并收集來自其他節(jié)點(diǎn)的PREPARE消息,如果收到的PREPARE消息數(shù)目超過2f,那么這個節(jié)點(diǎn)進(jìn)入了準(zhǔn)備就緒的狀態(tài),然后發(fā)送再次向其他節(jié)點(diǎn)廣播COMMIT消息,并收集來自其他節(jié)點(diǎn)的COMMIT消息,如果COMMIT消息的數(shù)目超過2f,那么這個節(jié)點(diǎn)進(jìn)入了提交狀態(tài),開始執(zhí)行客戶發(fā)起的請求,操作完成后,向客戶回復(fù)REPLY消息。

圖1 正常情況下實(shí)用拜占庭容錯協(xié)議運(yùn)行情況

可以看到PBFT協(xié)議最多只能容忍總結(jié)點(diǎn)數(shù)的1/3的出錯節(jié)點(diǎn),并且在一次同步過程中需要兩輪兩兩交互,才能使得非出錯節(jié)點(diǎn)達(dá)到一致,數(shù)據(jù)處理量較大。

文獻(xiàn)[14]提出了混合法定人數(shù)(Hybrid Quorum,HQ)來改進(jìn)PBFT,其運(yùn)行情況如圖2所示。HQ將寫入過程分成了2個階段,首先客戶端發(fā)起請求的同時收集服務(wù)器的狀態(tài)信息,如果有2f+1個節(jié)點(diǎn)處于相同狀態(tài),并且同意執(zhí)行請求,則客戶端第2次發(fā)起請求,服務(wù)器開始執(zhí)行請求;否則,執(zhí)行PBFT協(xié)議,由主節(jié)點(diǎn)重新安排請求序號。

圖2 混合法定人數(shù)協(xié)議運(yùn)行情況

HQ協(xié)議并沒有從根本上改變PBFT的結(jié)構(gòu),由于其對客戶端發(fā)送請求沒有競爭,服務(wù)器正常運(yùn)行的情況進(jìn)行了優(yōu)化,使得其性能得到了提升。

PBFT協(xié)議需要兩輪的兩兩交互信息,才能容忍1/3的出錯節(jié)點(diǎn),在保證狀態(tài)轉(zhuǎn)換有效的前提下,如何快速將分布式系統(tǒng)從一個一致性狀態(tài)同步到另一個一致性狀態(tài),是本文待解決的問題。本文提出與PBFT不同的法定人數(shù)(Quorum),即數(shù)目為n/2+1,n為系統(tǒng)中節(jié)點(diǎn)個數(shù),在只需要一輪兩兩交互的情況下,容忍38%的出錯節(jié)點(diǎn)。

2 系統(tǒng)模型

一個蒙特卡洛一致性協(xié)議[15]需要滿足如下3個條件:

1)可終結(jié)性,所有的過程需要在一個有限時間內(nèi)做出決定。

2)一致性,所有的過程最終能夠達(dá)到一致性。

3)輸入的有效性,最終決定的值一定是過程產(chǎn)生的值。

2.1 消息傳遞過程

整個網(wǎng)絡(luò)被看做n個獨(dú)立配置的過程(process),{p1,p2,…,pn}。一個執(zhí)行過程可以看做是一系列的狀態(tài)和轉(zhuǎn)換,π0,s0,π1,s1,…,πi,si,…,從狀態(tài)到可行的轉(zhuǎn)換之間由以下規(guī)則決定:

每一個轉(zhuǎn)換由一個單調(diào)遞增的時間戳,一個時間戳稱為一輪(round)。每一個過程在每一輪中只能執(zhí)行一次compute指令。

匿名的過程之間通過broadcast(m)指令來傳遞消息。每條消息的最大延遲為Δ,如果消息在時間r廣播,那么每一個過程在不超過r+Δ的時間里執(zhí)行receive(m)指令。

2.2 合法狀態(tài)轉(zhuǎn)換

計(jì)算模型引入了狀態(tài)合法性驗(yàn)證后,原有的規(guī)則發(fā)生了變化。

2.2.1 狀態(tài)轉(zhuǎn)換

一個狀態(tài)轉(zhuǎn)換需要經(jīng)過兩階段,從s0轉(zhuǎn)換到s1需要經(jīng)過中間狀態(tài)π0,當(dāng)一個節(jié)點(diǎn)發(fā)布了一個狀態(tài)轉(zhuǎn)換的消息后,收到這個消息的節(jié)點(diǎn)開始對這個轉(zhuǎn)換廣播自己的投票結(jié)果,同時節(jié)點(diǎn)開始收集消息,如果存在一個法定人數(shù)(Quorum)集合,里面所有的節(jié)點(diǎn)都同意,則網(wǎng)絡(luò)能夠被轉(zhuǎn)換到狀態(tài)s1。

2.2.2 不確定性

2.2.3 拜占庭錯誤

有f個出錯的過程,這些拜占庭錯誤節(jié)點(diǎn)能夠共謀對其他的正常節(jié)點(diǎn)發(fā)送錯誤消息。拜占庭出錯過程反對正常過程,正常過程可能會贊成拜占庭過程。正常過程提出的方案通過的概率為:

拜占庭錯誤過程提出的方案能通過的概率為:

2.3 具有狀態(tài)合法性驗(yàn)證的區(qū)塊鏈算法

每一個過程在每一輪中執(zhí)行一次compute過程,oracle過程將任意的輸入映射到0～1的區(qū)間,verify過程驗(yàn)證事先給定的CRS,挖礦節(jié)點(diǎn)提供的信息nonce,區(qū)塊的哈希值Prefer三者組合是否滿足規(guī)則。一致性算法如下所示。

procedure oracle(x)

return H(x)

precedure verify(nonce,Prefer)

hash = oracle(CRS || Prefer || nonce)

Initially do

Votes = {}

Prefer = proposed_i

on receive(Votes’,Prefer’) do

If verify(v,Prefer’) and on receive_op(u,op)for all v in Votes’,all u in v and |Votes’| > |Votes| then

Votes = Votes’

Prefer = Prefer’

S = Prefer’ - Prefer

for u in S

broadcast(u,op),op = {0,1}

on receive_op(u,op)

If count(op) >= n/2

return True

else return False

on compute(r) do

nonce = coinflip

for u in Prefer

If on receive_op(u,op)

set u.status = 1

if verify(nonce,Prefer)then

broadcast(Votes || nonce,Prefer)

算法過程如下:

每一個節(jié)點(diǎn)Pi同時執(zhí)行on receive、on receive_op和compute過程。

on receive過程當(dāng)收到新的區(qū)塊時,執(zhí)行verify過程驗(yàn)證每一個區(qū)塊是否滿足工作量,對于區(qū)塊中的每一個待完成的狀態(tài)轉(zhuǎn)換,執(zhí)行on receive過程,驗(yàn)證其是否滿足合法性驗(yàn)證。如果上述條件均滿足,并且區(qū)塊長度大于本地長度,則將這個區(qū)塊作為新的區(qū)塊。

對于新增區(qū)塊中與原有區(qū)塊鏈的差集中的中間狀態(tài),對其狀態(tài)轉(zhuǎn)換進(jìn)行投票廣播。

on receive_op過程對收到的投票進(jìn)行統(tǒng)計(jì),如果超過半數(shù),就返回成功,否則返回失敗。

on compute過程執(zhí)行挖礦過程,首先調(diào)用coinflip過程得到nonce,對于收到的待完成狀態(tài)轉(zhuǎn)換請求,調(diào)用on receive_op過程,修改其狀態(tài)。隨后調(diào)用verify過程,如果滿足了正確的工作量證明,則廣播這個區(qū)塊。

2.4 一致性證明

在n個process中有f

當(dāng)np>5,n(1-p)>5,使用N(np,np(1-p))擬合Binom(n,p)得到:

區(qū)塊鏈協(xié)議中每個過程只會選擇最長的鏈,協(xié)議需要保證Blockc-Blockf>0,由正態(tài)分布性質(zhì)得到:

而對于標(biāo)準(zhǔn)正態(tài)分布有如下性質(zhì):

prob=P{u-kσ

當(dāng)k=3時,prob=99.73%,當(dāng)k=4時,prob=99.99%。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 出錯節(jié)點(diǎn)比例上限

假設(shè)正確節(jié)點(diǎn)和出錯節(jié)點(diǎn)的提案有很大概率通過,令p≈1/n,根據(jù)公式:

圖3 執(zhí)行輪數(shù)隨出錯節(jié)點(diǎn)比例變化曲線

算法需要保證正常節(jié)點(diǎn)的轉(zhuǎn)換率大于出錯節(jié)點(diǎn)的轉(zhuǎn)換率,這是系統(tǒng)正確達(dá)成最終一致性的必要條件。pc和pf隨出錯節(jié)點(diǎn)比例f變化曲線如圖4所示,可以看出,要使得pc>pf,則f<0.41n。

圖4 正確和出錯狀態(tài)轉(zhuǎn)換概率隨出錯節(jié)點(diǎn)比例變化曲線

圖5 執(zhí)行輪數(shù)隨出錯節(jié)點(diǎn)比例f(f<0.38n)變化曲線

3.2 贊成概率的選擇

根據(jù)之前的實(shí)驗(yàn),選取f=0.38n作為合理的出錯節(jié)點(diǎn)個數(shù)。根據(jù)之前的公式:

將p′作為自變量,繪制u和v隨其變化的曲線,如圖6所示。當(dāng)p′>0.75的時候,u和v差不多都趨近于1。所以,當(dāng)節(jié)點(diǎn)對于一個狀態(tài)轉(zhuǎn)換通過的概率至少為0.75時,上述算法才能夠有效運(yùn)行。

圖6 正常和出錯節(jié)點(diǎn)投票通過概率隨贊成概率變化曲線

4 結(jié)束語

本文分析具有狀態(tài)合法性驗(yàn)證的拜占庭一致性協(xié)議的研究現(xiàn)狀,介紹多節(jié)點(diǎn)合法性驗(yàn)證的一致性協(xié)議。針對其存在的總節(jié)點(diǎn)數(shù)1/3的容錯上限和2次兩兩信息交換的問題,本文提出一種具有狀態(tài)合法性驗(yàn)證的區(qū)塊鏈一致性算法,設(shè)計(jì)新的法定人數(shù)集合,改進(jìn)現(xiàn)有的區(qū)塊鏈協(xié)議。實(shí)驗(yàn)結(jié)果表明,該算法使得區(qū)塊鏈一致性算法能夠具備合法性驗(yàn)證,并能解決拜占庭一致性,只使用了一次兩兩信息交換,使容錯上限達(dá)到38%。

本文在網(wǎng)絡(luò)規(guī)模、工作量難度和通信延遲給定的假設(shè)下,使用概率模型證明了算法的正確性。下一步工作將研究如何避免這些較強(qiáng)的假設(shè)條件,以提高算法的健壯性。

[1] 袁 勇,王飛躍.區(qū)塊鏈技術(shù)發(fā)展現(xiàn)狀與展望[J].自動化學(xué)報,2016,42(4):481-494.

[2] DWYER G P.The Economics of Bitcoin and Similar Private Digital Currencies[J].Journal of Financial Stability,2015,17(1):81-91.

[3] ALI M,NELSON J,SHEA R.Blockstack:A Global Naming and Storage System Secured by Blockchains[C]//Proceedings of USENIX Annual Technical Conference.[S.l.]:USENIX Association,2016.

[4] 楊勝剛,何 靖.反洗錢領(lǐng)域大額與可疑信息報告制度的經(jīng)濟(jì)學(xué)分析[J].金融研究,2004,10(1):113-119.

[5] PLASSARAS N A.Regulating Digital Currencies:Bringing Bitcoin Within the Reach of IMF[J].Chicago Journal of International Law,2013,14(1):377-407.

[6] 陳 晗,施 勇,薛 質(zhì).P2P 網(wǎng)絡(luò)資源傳播模型分析及監(jiān)測[J].信息安全與通信保密,2011,9(5):56-58.

[7] LAMPORT L,SHOSTAK R,PEASE M.The Byzantine Generals Problem[J].ACM Transactions on Programming Languages and Systems,1982,4(3):382-401.

[8] CLEMENT A,KAPRITSOS M,LEE S.Upright Cluster Services[C]//Proceedings of the 22nd ACM SIGOPS Symposium on Operating Systems Principles.New York:ACM Press,2009:277-290.

[9] LAMPORT L.The Part-time Parliament[J].ACM Transactions on Computer Systems,1998,16(2):133-169.

[10] BORRAN F,HUTLE M,SCHIPER A.Timing Analysis of Leader-based and Decentralized Byzantine Consensus Algorithms[J].Journal of the Brazilian Computer Society,2012,18(1):29-42.

[11] 范 捷,易樂天,舒繼武.拜占庭系統(tǒng)技術(shù)研究綜述[J].軟件學(xué)報,2013,24(6):1346-1360.

[12] LAMPORT L.Time,Clocks,and the Ordering of Events in a Distributed System[J].Communications of the ACM,1978,21(7):558-565.

[13] CASTRO M,LISKOV B.Practical Byzantine Fault Tolerance and Proactive Recovery[J].ACM Transactions on Computer Systems,2002,20(4):398-461.

[14] COWLING J,MYERS D,LISKOV B.HQ Replication:A Hybrid Quorum Protocol for Byzantine Fault Tolerance[C]//Proceedings of the 7th Symposium on Operating Systems Design and Implementation.[S.l.]:USENIX Association,2006:177-190.

[15] ATTIYA H.Lower Bounds for Randomized Consensus Under a Weak Adversary[J].SIAM Journal on Computing,2010,39(8):3995-3904.