同步可靠網絡環境中區塊鏈系統狀態機研究

劉 鳳 王 欣

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

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

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

0 引 言

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

1 概 念

1.1 區塊鏈(Blockchain)

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

1.2 共識機制(Consensus)

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

1.3 共識算法

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

1.3.1ProofofWork(PoW)

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

1.3.2ProofofStake(PoS)

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

1.3.3ByzantineAgreement

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

1.3.4PracticalByzantineFaultTolerance

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

2 構建狀態機模型

2.1 離散態時間點網絡

2.2 分布式賬本

圖2 區塊鏈狀態示意圖

2.3 狀態無關DLT

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

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

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

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

3 常見DLTs狀態機分析

3.1 工作量證明狀態機

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

3.2 權益證明狀態機

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

3.3 拜占庭協議狀態機

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

3.4 PBFT狀態機

3.5 狀態機應用示例

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

4 結 語

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