同步可靠網絡環(huán)境中區(qū)塊鏈系統(tǒng)狀態(tài)機研究

劉 鳳 王 欣

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

2(奧斯特拉發(fā)技術大學電氣工程與計算機科學學院 捷克 奧斯特拉發(fā) 70800)

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

0 引 言

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

1 概 念

1.1 區(qū)塊鏈(Blockchain)

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

1.2 共識機制(Consensus)

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

1.3 共識算法

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

1.3.1ProofofWork(PoW)

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

1.3.2ProofofStake(PoS)

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

1.3.3ByzantineAgreement

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

1.3.4PracticalByzantineFaultTolerance

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

2 構建狀態(tài)機模型

2.1 離散態(tài)時間點網絡

2.2 分布式賬本

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

2.3 狀態(tài)無關DLT

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

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

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

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

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

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

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

3.2 權益證明狀態(tài)機

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

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

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

3.4 PBFT狀態(tài)機

3.5 狀態(tài)機應用示例

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

4 結 語

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