劉 鳳 王 欣

1(河北地質(zhì)大學(xué)信息工程學(xué)院 河北 石家莊050000)

2(奧斯特拉發(fā)技術(shù)大學(xué)電氣工程與計(jì)算機(jī)科學(xué)學(xué)院 捷克 奧斯特拉發(fā) 70800)

3(河北軟件評測中心 河北 石家莊 050000)

0 引 言

1978年Leslie Lamport將分布式系統(tǒng)定義為,由一組不同的進(jìn)程組成,這些進(jìn)程在空間上是分開的,并且通過交換消息彼此通信,如果消息傳輸延遲與單個進(jìn)程中事件之間的時間相比不可忽略,則系統(tǒng)是分布式的[1]。自此,分布式系統(tǒng)逐步引起計(jì)算機(jī)學(xué)術(shù)界的關(guān)注,文獻(xiàn)[2-3]提出了分布式系統(tǒng)協(xié)議。自2002年起,Peer-to-Peer體系的研究和應(yīng)用廣泛開展[4]。2008年Satoshi[5]提出了基于Peer-to-Peer的電子現(xiàn)金系統(tǒng)——比特幣。到2020年,以分布式系統(tǒng)為基礎(chǔ)的區(qū)塊鏈技術(shù)逐步發(fā)展,并開始在不同行業(yè)應(yīng)用。Bonnet等[6]在采用SnowWhite、Algorand和Ouroboros協(xié)議的PoS機(jī)制區(qū)塊鏈基礎(chǔ)上,提出了基于分布式賬本技術(shù)(DLTs)狀態(tài)機(jī)模型理論,該模型要求網(wǎng)絡(luò)節(jié)點(diǎn)之間必須建立兩兩實(shí)時互聯(lián),存在模型構(gòu)造單一、設(shè)定的前提條件過于理想、與實(shí)際應(yīng)用相差較大的不足。本文在Bonnet提出的基于分布式賬本技術(shù)(DLTs)狀態(tài)機(jī)模型的基礎(chǔ)上進(jìn)一步抽象建立了離散節(jié)點(diǎn)分布網(wǎng)絡(luò)狀態(tài)機(jī)模型并開展雙射證明。新建立的狀態(tài)機(jī)模型可以更廣泛應(yīng)用于不同共識機(jī)制的區(qū)塊鏈分析,適用性和實(shí)用性得到擴(kuò)展和提升。

1 概 念

1.1 區(qū)塊鏈(Blockchain)

區(qū)塊鏈沒有精準(zhǔn)的定義。Satoshi將電子現(xiàn)金定義為數(shù)字簽名鏈。即每個擁有者通過數(shù)字簽名前一個交易的散列和下一個擁有者的公鑰并將其添加到現(xiàn)金鏈的末尾,將現(xiàn)金轉(zhuǎn)移給下一個人,收款人則可以通過驗(yàn)證簽名來確定鏈的所有權(quán)[5]。Buterin將其定義為：一種神奇的計(jì)算機(jī),任何人都可以上傳程序并讓程序自動執(zhí)行,其中每個程序的當(dāng)前和以前所有的狀態(tài)均是公開可見的;其具有強(qiáng)大的加密安全保證,且在區(qū)塊鏈鏈上的程序?qū)⒁詤f(xié)議指定的方式運(yùn)行[7]。袁勇等[8]將區(qū)塊鏈定義為狹義和廣義兩種,狹義是指一種按照時間順序?qū)?shù)據(jù)區(qū)塊以鏈條的方式組合成特定的數(shù)據(jù)結(jié)構(gòu),并以密碼學(xué)方式保證其不可篡改和不可偽造的去中心化共享總賬(Decentralized Shared Ledger),能夠安全存儲簡單的、有先后關(guān)系的、能在系統(tǒng)內(nèi)驗(yàn)證的數(shù)據(jù)。廣義的區(qū)塊鏈技術(shù)則是利用加密鏈?zhǔn)絽^(qū)塊結(jié)構(gòu)來驗(yàn)證與存儲數(shù)據(jù)、利用分布式節(jié)點(diǎn)共識算法來生成和更新數(shù)據(jù)、利用自動化腳本代碼(智能合約)來編程和操作數(shù)據(jù)的一種全新的去中心化基礎(chǔ)架構(gòu)與分布式計(jì)算范式。分布式賬本(DLT)是區(qū)塊鏈的底層核心技術(shù),本文研究的區(qū)塊鏈狀態(tài)機(jī)系統(tǒng)是應(yīng)用DLT對比特幣、以太幣等應(yīng)用系統(tǒng)進(jìn)行模型化抽象,以保證研究結(jié)論不受具體應(yīng)用場景的限制。

1.2 共識機(jī)制(Consensus)

分布式系統(tǒng)通過建立所有節(jié)點(diǎn)共同遵守的機(jī)制,使系統(tǒng)作為一個整體能夠在有限數(shù)量的子節(jié)點(diǎn)出現(xiàn)故障的情況下繼續(xù)工作。這些制度被稱為“共識機(jī)制”(也稱為“共識協(xié)議”),它們負(fù)責(zé)分布式系統(tǒng)中所有子節(jié)點(diǎn)之間的協(xié)作[9-10]。區(qū)塊鏈的運(yùn)行規(guī)則是共識機(jī)制。共識機(jī)制一般是由設(shè)計(jì)分布式系統(tǒng)的團(tuán)隊(duì)編制,并開發(fā)出相應(yīng)的程序,提供給節(jié)點(diǎn)使用。區(qū)塊鏈的共識機(jī)制的升級、改變需要所有子節(jié)點(diǎn)一致同意,如果不能達(dá)成共識,任何參與節(jié)點(diǎn)都可以實(shí)施硬分叉,另建一條區(qū)塊鏈。這也是區(qū)塊鏈共識機(jī)制的去中心化特性。區(qū)塊鏈通過去中心化解決信任問題,基于算法使陌生節(jié)點(diǎn)在不借助于第三方的情況下能夠達(dá)成共識。

1.3 共識算法

共識算法是共識機(jī)制的一部分。區(qū)塊鏈系統(tǒng)的共識算法首先需要解決非信任網(wǎng)絡(luò)環(huán)境中的拜占庭將軍問題(Byzantine General Problem)[11],即區(qū)塊鏈網(wǎng)絡(luò)中存在惡意節(jié)點(diǎn),會主動違反協(xié)議或傳輸錯誤的數(shù)據(jù),從而對整體區(qū)塊鏈網(wǎng)絡(luò)造成干擾和破壞。因此區(qū)塊鏈系統(tǒng)必須采用能夠容忍拜占庭將軍問題的一致性算法(共識算法)。目前最常見的共識算法有Proof of Work、Proof of Stake、Byzantine agreement等。

1.3.1ProofofWork(PoW)

工作量證明協(xié)議(PoW)設(shè)定發(fā)起節(jié)點(diǎn)需要進(jìn)行特定形式的數(shù)學(xué)運(yùn)算,只有計(jì)算出正確結(jié)果的節(jié)點(diǎn)才具備訪問資源的權(quán)力。通過強(qiáng)制節(jié)點(diǎn)運(yùn)行計(jì)算程序消耗一定量的電力,造成節(jié)點(diǎn)實(shí)際付出計(jì)算力和能耗成本,從而增加節(jié)點(diǎn)進(jìn)行惡意破壞行為的成本[12-13]?；赑oW協(xié)議的區(qū)塊鏈?zhǔn)堑谝环N穩(wěn)定運(yùn)行的分布式賬本(DLT)技術(shù),任何節(jié)點(diǎn)都可以自主地選擇加入或者離開。包括比特幣在內(nèi)的所有基于PoW協(xié)議的區(qū)塊鏈都需要運(yùn)行在同步網(wǎng)絡(luò),并假設(shè)正確的節(jié)點(diǎn)算力大于拜占庭節(jié)點(diǎn)[6]。對于Bitcoin、Ethereum所使用的POW共識協(xié)議,每個節(jié)點(diǎn)都可能取得DLT記賬權(quán),在驗(yàn)證工作量證明后,便確定了記賬的效力[14]。

1.3.2ProofofStake(PoS)

權(quán)益證明協(xié)議(PoS)設(shè)定驗(yàn)證者不再通過消耗大量的電力進(jìn)行工作量證明,而是通過投票提出下一個區(qū)塊,驗(yàn)證者投票的權(quán)重取決于其“幣齡”的大小[15]?！皫琵g”被簡單地定義為貨幣數(shù)量乘以持有時間。與比特幣中的“Coinbase”相似,權(quán)益生成過程被稱為“Coinstake”,在Coinstake事務(wù)中,PoS協(xié)議區(qū)塊的生成類似于PoW的過程,需要進(jìn)行協(xié)議規(guī)定的Hash運(yùn)算。一個重要的區(qū)別在于,PoS協(xié)議的Hash操作是在很小的搜索空間內(nèi)進(jìn)行,而不同于PoW協(xié)議的廣泛搜索空間,因此能量消耗會顯著下降。驗(yàn)證者可以通過消耗“幣齡”來減少相應(yīng)的Hash難度,而PoW協(xié)議中的Hash難度相對于每個節(jié)點(diǎn)是固定的。因此,在PoS協(xié)議中節(jié)點(diǎn)持有的“幣齡”越多,就越容易生成區(qū)塊。

1.3.3ByzantineAgreement

拜占庭協(xié)議(Byzantine Agreement)也稱為拜占庭容錯(Byzantine Fault Tolerance,BFT)是分布式計(jì)算容錯技術(shù)。拜占庭問題是對現(xiàn)實(shí)問題的抽象表示,指分布式系統(tǒng)由于硬件故障、網(wǎng)絡(luò)擁塞或中斷、遭到惡意攻擊等原因,系統(tǒng)可能出現(xiàn)的不可預(yù)料行為。BFT技術(shù)用于維護(hù)在存在拜占庭問題的網(wǎng)絡(luò)上保持一致狀態(tài)。它可以容忍系統(tǒng)部分崩潰或拜占庭式的故障,最多可容忍的數(shù)量取決于通信的同步性假設(shè)。BFT共識算法的目的是在不信任網(wǎng)絡(luò)(如互聯(lián)網(wǎng))中的節(jié)點(diǎn)間建立信任。Lamport等[11]證明了在同步環(huán)境中算法可行。

1.3.4PracticalByzantineFaultTolerance

實(shí)用拜占庭容錯算法PBFT(Practical Byzantine Fault Tolerance)是BFT算法的改進(jìn),由Castro等[16]提出,解決了BFT算法效率不高的問題,將算法復(fù)雜度由指數(shù)級降低到多項(xiàng)式級,使得拜占庭容錯算法在實(shí)際系統(tǒng)應(yīng)用中變得可行。PBFT主要針對主節(jié)點(diǎn)副本復(fù)制為主的分布式系統(tǒng)執(zhí)行環(huán)境,用系統(tǒng)中多數(shù)可靠節(jié)點(diǎn)來覆蓋惡意節(jié)點(diǎn)或無效節(jié)點(diǎn)的行為。PBFT算法的節(jié)點(diǎn)數(shù)量固定,一個節(jié)點(diǎn)代表一票,以少數(shù)服從多數(shù)的方式實(shí)現(xiàn)了拜占庭的容錯演算。至多容錯量不超過全部節(jié)點(diǎn)數(shù)的1/3,即如果有超過2/3的正常節(jié)點(diǎn),整個系統(tǒng)可正常運(yùn)轉(zhuǎn)。

2 構(gòu)建狀態(tài)機(jī)模型

2.1 離散態(tài)時間點(diǎn)網(wǎng)絡(luò)

2.2 分布式賬本

圖2 區(qū)塊鏈狀態(tài)示意圖

2.3 狀態(tài)無關(guān)DLT

在區(qū)塊鏈系統(tǒng)中,新加入網(wǎng)絡(luò)的節(jié)點(diǎn)會從網(wǎng)絡(luò)中的其他節(jié)點(diǎn)獲得當(dāng)前分布式賬本的狀態(tài)。如果新加入的節(jié)點(diǎn)能夠根據(jù)DLT的初始狀態(tài)和從當(dāng)前網(wǎng)絡(luò)中接收到的信息推斷出DLT的當(dāng)前狀態(tài),則這個DLT是狀態(tài)無關(guān)。

定義1(弱狀態(tài)無關(guān)性DLT)如果存在一個函數(shù)f,使得f(I,Mt)=St,則DLT為弱狀態(tài)無關(guān)。

定義2(強(qiáng)狀態(tài)無關(guān)性DLT)如果存在一個函數(shù)f,使得f(I,Mt)=St,并且對于任意的子集A?Mt,f(I,A)=Stor ⊥(⊥表示截短),則DLT為強(qiáng)狀態(tài)無關(guān)。

定義3(隨機(jī)態(tài)DLT)如果存在一個函數(shù)f,對于?k,t,t′∈N,k≤t≤t′,f(I,Mt)-k≤St′的概率大于1-O(e-ck)(O為隨機(jī)函數(shù)),常數(shù)c>0,那么DLT是隨機(jī)態(tài)。

3 常見DLTs狀態(tài)機(jī)分析

3.1 工作量證明狀態(tài)機(jī)

證明設(shè)f是返回最大PoW(St)的本地狀態(tài)的函數(shù),f(I,Mt)=argmaxs({PoW(S)|?u,(u,S)∈Mt})。這樣的本地狀態(tài)可能是由敵對節(jié)點(diǎn)產(chǎn)生。如果k表示截斷的區(qū)塊數(shù)量來得到前邊正確的狀態(tài)St,當(dāng)k趨向于無窮時,其可能性呈指數(shù)速度降低。實(shí)際上,分別使用pt和qt表示在t時間點(diǎn)正確節(jié)點(diǎn)的計(jì)算力和敵對節(jié)點(diǎn)的計(jì)算力。假設(shè)?t,pt>qtλt=maxt′≤t(pt′qt′)根據(jù)文獻(xiàn)[17]推論,在給定的時間點(diǎn)t敵對節(jié)點(diǎn)重寫最后k個區(qū)塊的可能性是O(e-cz)c=log(1/(4λt))>0。

3.2 權(quán)益證明狀態(tài)機(jī)

定理2在每個時間點(diǎn)即使所有擁有令牌的節(jié)點(diǎn)是正確的,PoS DLT也不是弱狀態(tài)無關(guān)的。

3.3 拜占庭協(xié)議狀態(tài)機(jī)

當(dāng)集合C中多數(shù)節(jié)點(diǎn)是正確節(jié)點(diǎn)時,C以外的任意節(jié)點(diǎn)u可以通過詢問C內(nèi)的節(jié)點(diǎn)獲取當(dāng)前狀態(tài)。u接收到的當(dāng)前狀態(tài)是通過C內(nèi)多數(shù)節(jié)點(diǎn)決定的,可保證其正確性。從這里可以推導(dǎo)出下面的定理：

3.4 PBFT狀態(tài)機(jī)

3.5 狀態(tài)機(jī)應(yīng)用示例

物聯(lián)網(wǎng)區(qū)塊鏈。物聯(lián)網(wǎng)(IoT)是一個由相互關(guān)聯(lián)的設(shè)備、機(jī)器、對象組成的系統(tǒng),嵌入了傳感器、軟件和其他技術(shù),這些設(shè)備具有唯一標(biāo)識符(UID),并且能夠通過網(wǎng)絡(luò)交換數(shù)據(jù),而不需要人與人或人與計(jì)算機(jī)的交互[18]。由于多種技術(shù)、實(shí)時分析、機(jī)器學(xué)習(xí)、傳感器和嵌入式系統(tǒng)的融合,物聯(lián)網(wǎng)的定義已經(jīng)演變,延伸到工業(yè)、生活等各方面。在物聯(lián)網(wǎng)中應(yīng)用區(qū)塊鏈技術(shù),可以實(shí)現(xiàn)去中心化,不用中央控制系統(tǒng)來驗(yàn)證,設(shè)備之間能互相匿名傳輸,并管理軟件的更新、錯誤,或者進(jìn)行能源管理。在物聯(lián)網(wǎng)中的設(shè)備通常是功能簡單、算力較弱的節(jié)點(diǎn),不能部署實(shí)施復(fù)雜協(xié)議和策略。通過上述研究,拜占庭狀態(tài)機(jī)為強(qiáng)狀態(tài)無關(guān),其DLTs狀態(tài)可以基本不受節(jié)點(diǎn)影響,適合在物聯(lián)網(wǎng)區(qū)塊鏈中應(yīng)用。

4 結(jié) 語

通過對區(qū)塊鏈?zhǔn)褂玫某Ｒ姽沧R機(jī)制底層技術(shù)進(jìn)行狀態(tài)機(jī)分析,本文從底層機(jī)制上系統(tǒng)證明了不同的區(qū)塊鏈共識機(jī)制特性,可以對區(qū)塊鏈實(shí)際應(yīng)用提供理論支撐。由于區(qū)塊鏈應(yīng)用正在興起,對于不同應(yīng)用場景應(yīng)采用的共識機(jī)制和共識協(xié)議,可以使用本文狀態(tài)機(jī)研究成果進(jìn)行具體分析。目前,區(qū)塊鏈狀態(tài)機(jī)研究仍處于初級階段,還存在應(yīng)用場景設(shè)定苛刻的局限,建議下一步應(yīng)著重加強(qiáng)寬條件域下區(qū)塊鏈狀態(tài)機(jī)充分條件研究。