區塊鏈的數據管理技術綜述?

張志威 , 王國仁 , 徐建良 , 杜小勇

1(北京理工大學 計算機學院,北京 100081)

2(香港浸會大學 計算機系,香港)

3(中國人民大學 信息學院,北京 100872)

最近幾年,由于加密貨幣以及去中心化應用的興起,區塊鏈技術在工業界與學術界得到了極大的關注,并產生了巨大的影響.加密貨幣中的比特幣[1]、以太坊[2]等已被允許在新加坡、加拿大等國家進行支付.從數據處理的角度,區塊鏈是一種由網絡中一組節點維護、只可添加的鏈式數據結構.在區塊鏈系統中,數據與事務以區塊為最小單位進行存儲.區塊與區塊之間以鏈表的方式進行連接,且新的區塊只能在鏈表末尾添加.因此,區塊鏈中每個節點均按照區塊被添加的順序來存儲區塊內的數據內容.在這種情況下,所有的區塊形成了一個存在全局順序的鏈表.區塊鏈因此也常被稱作賬本.與此同時,區塊鏈系統可在不可信的網絡中支持數據的一致性以及不可篡改等特點.為了在不可信的網絡中保證數據不可篡改,區塊鏈將每個區塊及前一區塊的哈希值存儲在區塊中,因此網絡中的節點可通過哈希值,驗證自身數據以及前一區塊的數據是否與相應的哈希值一致.同時,考慮到不可信網絡中惡意節點的惡意攻擊行為,區塊鏈系統要求可以支持拜占庭容錯,即:當網絡中存在少量惡意節點時,依然可以確保網絡中數據的一致性.由于以上特性,整個區塊鏈網絡構成了一個去中心化且不可篡改的一致數據存儲系統.

區塊鏈系統的去中心化特點使其與傳統的分布式數據庫在技術,應用等方面有很大不同.傳統的分布式數據庫往往假定存在中心節點,且節點不存在惡意行為,因此大部分分布式數據庫只需要考慮崩潰性故障.而區塊鏈中節點之間是不可信的,即節點可能惡意地發送消息或執行計算,因而區塊鏈需考慮拜占庭容錯.諸多企業,例如IBM[3]、Oracle[4]、SAP[5]、華為[6]等,均建立了自身的區塊鏈系統.隨著區塊鏈技術的推廣以及對智能合約的支持,區塊鏈技術也被進一步應用于多個領域,包括物聯網[7,8]、醫療健康[9,10]、專利保護[11]、政府監管[12]、資產管理[13]等.與此同時,越來越多的工作對區塊鏈各個方面進行了優化,包括系統模型[14,15]、共識算法[16,17]、數據安全[18-21]、數據存儲[22]以及性能評價基準[23]等.

從數據管理的角度,區塊鏈是一個在分布式環境下存儲大量存在全序關系的數據記錄系統.數據以及對數據的操作均存儲在區塊內并以區塊的粒度進行管理.一個典型的區塊結構如圖1 所示,包括前一區塊哈希值(PreBkHash)、共識驗證字段(ConsProof)以及區塊內事務的哈希值(MerkleRoot).其中,節點可利用共識驗證字段驗證其存儲的區塊是否滿足共識條件,并確保網絡中少量節點的惡意行為不會影響區塊鏈的一致性,從而使其支持拜占庭容錯.

在分布式數據庫系統中,由于其假定節點不存在惡意攻擊行為,因此分布式數據庫中節點共識只需考慮節點崩潰的情況.典型的共識算法有Paxos[24],Raft[25]等.這類共識算法已經被應用于全球化的分布式數據庫中,并已經取得了很好的性能.而在區塊鏈中,為了支持拜占庭容錯,區塊鏈中典型的共識機制包括工作量證明PoW[26]、實用拜占庭容錯PBFT[27]等.關于區塊結構以及共識算法,將在“區塊鏈的核心構成”部分介紹.

雖然與分布式數據庫相比,區塊鏈可以支持在不信任網絡環境中的去中心化數據管理,但是區塊鏈系統在數據管理方面仍然面臨著諸多問題,其核心問題包括數據存儲、事務處理性能、查詢處理優化等方面.例如,現階段區塊鏈的每秒可執行事務數(TPS)遠小于傳統的分布式數據庫,也很難滿足實際公司級別的交易量需求.最廣泛使用的電子貨幣比特幣支持平均每秒7 筆交易,而visa 等信用卡公司每秒需執行4 000 筆左右的交易[28,29].具體而言,區塊鏈系統中的數據管理與現有分布式數據庫有如下方面的不同.

· 數據存儲方面

在區塊鏈系統中,數據以區塊作為基本存儲單位.為了方便數據的存取,以太坊[3]等利用LevelDB 這一基于Key-Value 結構的數據庫存取數據,而部分區塊鏈則選擇利用文件系統或關系型數據庫進行存儲.與傳統的分布式數據庫或其他分布式存儲系統相比,由于區塊鏈網絡中的節點均存儲數據的備份,導致數據的存儲在區塊鏈框架下產生新的挑戰.首先,直接將所有數據存儲于區塊鏈上將導致區塊鏈上的數據規模極大.在一般情況下,系統中的節點均需要存儲所有歷史和新添加的數據,因而導致整個系統的存儲開銷極大.這將使得部分節點可能由于存儲空間的限制,不能加入到區塊鏈的網絡中.其次,由于區塊鏈中存儲了大量的歷史數據,在這種情況下,一個數據在區塊鏈中可以存在多個歷史版本.現有的諸多操作需要基于數據的不同版本進行,因此,數據存儲需支持多版本的存儲、查詢等操作,且可以在各個版本上進行獨立的數據添加更改等操作.

· 事務執行方面

在區塊鏈中,智能合約的一次執行相當于數據庫中的一個事務.在傳統的數據庫中,事務處理需滿足ACID特性,包括原子性(atomicity)、一致性(consistency)、隔離性(isolation)與持久性(durability).在區塊鏈系統中,其事務的處理同樣需滿足以上特性.為了提高系統的吞吐量,部分區塊鏈的事務處理同樣會采用并發機制.但是,區塊鏈系統的并發控制與分布式數據庫的并發控制相比有諸多不同[30,31].首先,區塊鏈系統中的事務的提交(commit)是以區塊為單位,而不是以每個事務為單位.一個區塊內將包含多個事務,這將導致針對事務的并發控制需要考慮區塊的提交順序.當一個事務與其他事務并發執行卻沒有在同一區塊中提交,將不會明顯提高系統的執行效率.其次,部分區塊鏈中的事務處理流程與數據庫中的事務不同.例如Hyperledger Fabric 中,事務的處理包含模擬、驗證等過程.當其共識協議達成之后,每個節點才會執行區塊內的事務.第三,分布式數據庫往往基于master-slave[32,33]或者master-master 模式[34,35],其中,master 節點是可信任節點.由于區塊鏈運行在不可信環境,事務的處理過程需要考慮區塊鏈系統所采用的共識協議影響.以上不同使得分布式數據庫的并發控制無法直接應用于區塊鏈系統.

· 查詢處理方面

由于區塊鏈應用于不可信的環境,其查詢處理的過程可歸類為一般查詢處理和可信查詢處理.一般查詢主要針對的是溯源查詢等.針對可信查詢問題,傳統的針對查詢結果的驗證技術需要數據擁有者產生一個利用私鑰生成的簽名,后續會利用該簽名進行驗證.而在區塊鏈系統中,不存在絕對的數據擁有者.網絡中的多個節點(例如工作量證明共識協議下的挖礦者)均有機會添加區塊到區塊鏈中.這些有機會添加區塊到區塊鏈的節點不一定是數據本身的擁有者,進而不可能擁有相應的私鑰以及簽名.其次,傳統的數據庫簽名方法針對不同的查詢產生不同簽名,并且均存儲在數據庫中.而在區塊鏈系統中,由于區塊鏈系統不可篡改的特點,簽名一旦寫入區塊中就不可以更改.因而,當應對不同的查詢時,寫入的簽名需要滿足不同查詢的驗證條件.最后,基于傳統數據庫生成的簽名往往基于的是靜態數據庫.區塊鏈是一個動態,且對數據格式、大小無限制的系統,因而可驗證的簽名需滿足可驗證動態添加的數據的要求.

· 可擴展性方面

為了提高分布式系統的可擴展性,傳統的數據庫可采用分片機制以提高性能.分片技術會將網絡中的節點分割為多個獨立的片,每個片內包含多個節點.片與片的數據一般存在一定的共有數據,從而可以保證當部分節點失效時,依然可以恢復全部數據.而在區塊鏈系統中,由于節點的不可信,需要利用共識機制確保節點執行的事務等的一致性,并能抵御惡意節點的惡意攻擊.因此,區塊鏈的分片技術要確保某一分片內的惡意節點不能控制該分片,使其惡意攻擊行為成功.其次,為了將分片機制應用到區塊鏈系統中,要確保分片環境下的共識機制的開銷遠小于分片所帶來的性能的提升.最后,一般的分布式數據庫存在master 節點,來分配及協調事務的處理.而在區塊鏈系統中,直接利用master 節點來分配事務需要考慮到master 節點可能是惡意節點的情況.

本文將從以上幾個不同的數據管理方面問題,分析區塊鏈與現有技術的異同.我們將基于現有的數據管理技術,尤其是分布式數據庫管理技術,來梳理并分析現有的區塊鏈環境下數據管理問題.針對現有區塊鏈的工作,從安全與可信性[36,37]、系統架構[38]、智能合約技術[39,40]、訪問控制[41]等方面進行了綜述.同時,文獻[42]主要從區塊鏈與數據庫外聯結合的角度,綜述了在區塊鏈中基于數據庫的存儲與查詢的研究工作.與之前工作不同,本文將從數據管理的角度,聚焦區塊鏈中的數據存儲、事務處理、查詢處理以及系統性能的方面的研究工作.

1 區塊鏈的核心構成

在一個區塊鏈網絡中,包含互相不信任的多個節點,節點間無法確認某個節點是否為惡意節點.區塊鏈網絡假定某些節點可能產生惡意攻擊,但是網絡中大多數節點是誠實節點.整個區塊鏈系統的節點一般可分為全節點、礦工節點和輕節點.全節點同步區塊鏈上的所有數據,包括各個區塊的頭部哈希值、事務列表等.輕節點一般是用戶的客戶端.輕節點不存儲區塊鏈上的全部數據,而往往只存儲區塊頭部的哈希值.輕節點有時會提交針對區塊鏈上數據的查詢等,并利用返回的結果以及自身存儲的哈希值對結果進行驗證.礦工節點是一種特殊的全節點,該節點不但存儲區塊鏈的全部數據,同時參與區塊鏈的共識過程.在一些區塊鏈系統中,礦工節點與全節點是相同的節點.本節我們將介紹區塊鏈的核心構成,包括區塊結構與事務、共識機制、UTXO 與Account模型、智能合約以及區塊鏈的類型.

1.1 區塊結構與事務

區塊鏈網絡節點存儲整個區塊鏈系統的數據以及事務的日志,數據以區塊的方式進行存儲并鏈接.節點中一個區塊的數據如圖1 所示,后一個區塊均包含前一個區塊的哈希值(PreBkHash 表示).除此之外,區塊內還包含共識驗證字段(ConsProof)、默克爾哈希樹根的哈希值(MerkleRoot)以及事務日志所構成的默克爾哈希樹.默克爾哈希樹是一種二叉樹[43],其葉子節點存儲事務,而非葉子節點則存儲其子節點內容的哈希值.默克爾哈希樹的一個特點是:對于數據的任何變動,會影響從葉子節點到根節點路徑上所有節點的哈希值.因此,所有針對數據的修改都會從葉子節點向上傳遞到根節點.因此,利用該性質可驗證數據是否被篡改.由于區塊鏈以鏈式方式存儲數據并執行事務,且區塊鏈只允許在現有區塊鏈的尾部添加新的區塊,該性質使得區塊鏈可以記錄所有對數據進行更改的操作,因而其也被稱為分布式日志或分布式賬本.區塊鏈中的一個事務對應于一次智能合約的完整執行.區塊鏈的事務也同樣要求滿足數據庫中事務的原子性、一致性、隔離性以及持久性.區塊中的共識驗證字段可以在部分共識機制中,驗證節點廣播的消息是否符合系統設定的條件,其具體細節將在“共識機制”部分介紹.同時,區塊鏈要求區塊只能添加在區塊鏈的尾部且不能刪除.雖然有部分工作討論修改區塊鏈數據的方法[44],但是該類工作并不修改區塊鏈存儲的數據.其方法通過設計視圖隱藏需要修改的數據,因而并不改變區塊鏈對數據的存儲和管理.

1.2 共識機制

由于區塊鏈網絡中節點不可信并且其要求所有節點均存儲數據的相同狀態,當對其中一個節點的數據準備進行更新時,所有節點需要對更新操作達成共識.共識協議往往基于兩種思路,分別為基于計算的共識協議和基于通訊的協議.現有的共識機制大部分采用以上兩種之一或者二者之間做一定的平衡[45].

基于計算的共識協議代表是比特幣所使用的工作量證明(proof-of-work,簡稱PoW)[26],其原理為:網絡中的節點通過工作量證明,確定下一個有權利將生成的區塊添加到鏈中的節點.參與工作量證明的節點稱為挖礦節點.例如:當一個區塊的結構如圖1 所示,包括前一區塊的哈希值、共識的驗證字段以及區塊內事務的哈希值時,挖礦節點利用這些哈希值計算出該區塊的共識的驗證字段,使得驗證字段滿足以下條件:

其中,Z這一參數控制工作量的大小.最先計算出相應驗證字段的挖礦節點將其結果全網廣播,其他的挖礦節點驗證其收到的驗證字段是否滿足方程(1)的條件:若結果滿足,則將區塊添加到已有區塊鏈的尾部,而最先計算出結果的節點則獲得相應的獎勵.工作量證明的共識協議可以很好地應用于公有鏈網絡中,并且可以抵御女巫攻擊[46].當惡意的算力達到全網算力的10%時,在6 個區塊后確認的交易可以保證超過99.9%的真實性[47].同時,在工作量證明方程的結果廣播的過程中,PoW 共識可利用中繼節點,通過多輪傳遞方式來減少工作量證明共識機制的冗余網絡開銷[48].

另一類型的共識協議則是基于通訊的共識協議,基于通訊的協議將投票權分配給網絡中的節點,并利用多輪通訊達成共識.該協議的代表為實用拜占庭容錯協議(PBFT)[27].PBFT 共識協議需經過3 個過程:pre-prepare階段、prepare 階段以及commit 階段.當用戶提交請求時,一個主節點會在pre-prepare 階段廣播其請求.在prepare階段,所有的節點收到請求后判斷是否執行該操作:如同意執行,則將自己的簽名添加在消息中,并廣播給其他節點;若不同意執行,則不發送消息.當節點接收到其他節點發送的執行操作的消息達到一定數量時,則說明執行操作達成了共識.在commit 階段,節點執行相應的請求,并將執行結果回報給主節點.由于所有的節點都將全網發送并接受來自所有其他節點的消息,因而在網絡中有N個節點的情況下,其網絡開銷復雜度為O(N2).

以上兩種共識分別基于計算和通訊.同時,有其他共識協議改進PoW 共識協議中的條件方程,或在兩種共識協議中做一定的取舍.例如,Elastico[49],RapidChain[50],Byzcoin[51],Tendermint[52]等均利用采樣的方式選取領導者節點,并在領導者節點中利用PBFT、工作量證明或其他基于投票的算法達成共識,從而減少其共識階段的開銷.需要注意的是,基于計算的工作量證明共識并不能確定保證網絡中的事務均合法.當惡意節點控制全網33%的算力時,則惡意節點已有可能控制整個網絡[53,54].與之不同,PBFT 共識則是確定性的.但是由于其網絡開銷為O(N2),當增加網絡節點個數時,網絡產生的額外開銷會超過增加算力所節省的時間,使得系統的性能隨著算力增加而降低.因此,直接使用PBFT 共識將會降低整個網絡的可擴展性[55],并成為部分區塊鏈系統的性能瓶頸[22].關于其他共識機制的綜述可見文獻[56,57].

1.3 UTXO與Account模型

在區塊鏈系統中,典型的數據模式是比特幣所基于的Unspent Transactions Outputs(UTXO)結構.以比特幣為例,在UTXO 模型中,不存在一個賬戶記錄一個用戶所持有的所有比特幣.每個交易均是通過已有的UTXO 生成新的UTXO.換言之,交易只是代表UTXO 集合的變更,而一個用戶所擁有的全部比特幣是其所擁有的UTXO總和.例如,假定用戶A分別在事務1 和事務2 中轉賬2 個比特幣到B用戶.此時,B用戶有兩個UTXO:UTXO1與UTXO2,且分別包含2 個比特幣.當用戶B計劃生成事務3,并在事務3 中轉賬3 個比特幣到用戶C的賬戶時,事務3 的輸入需要包含的是B用戶的UTXO.本例中,事務3 的輸入可以為UTXO1以及UTXO2.之后,在事務執行過程中,事務將輸入的UTXO 標記為已花費的狀態,并生成一個新的包含3 個比特幣的UTXO,并將其轉移到C用戶.同時,事務生成一個UTXO 包含剩下的一個1 個比特幣,并將其轉移到B用戶.通過UTXO 這一模型,所有交易均在已有的UTXO 之上進行,大多數交易只需要判定是否存在雙花(一個UTXO 被多次交易)即可.因而,交易是否被執行可以很快地驗證,并且具有很高的隱私性.但是由于其不存在賬戶的概念且交易需要基于UTXO,其編程復雜度較高.

另一種數據模型是Ethereum 所采用的Account 模型,該模型下一個賬戶包含用戶所有可用的電子貨幣.當一個交易被提交時,相應的事務首先判斷賬戶內的電子貨幣是否足以完成該交易:如果可以,則該交易被執行;否則,交易被取消.與UTXO 相比,Account 模型更容易理解,并節省了大量的存儲空間.而UTXO 則可以更好地保護用戶隱私.

1.4 智能合約

智能合約最早于1994 年由Szabo 提出[58],其設想為:在一個計算機系統中,當一些事務被執行時,可以激發相應的代碼自動執行,并產生相應的輸出合約.但是由于很難確保智能合約的代碼等不被篡改,因而其在實際的應用受到了很大的限制.隨著區塊鏈技術的發展,利用區塊鏈所支持的數據不可篡改的特點,區塊鏈上的智能合約得到了越來越多的重視.智能合約可以看作是一段區塊鏈所有節點都認可的代碼.部署在區塊鏈上的智能合約需采用該區塊鏈系統可執行的代碼,并同樣存儲于區塊中.當智能合約的條件被滿足時,合約自動被激活并執行相應的代碼.例如,一個執行轉賬功能的智能合約會首先判斷其激活條件是否被滿足:若被滿足,則進一步驗證相應的事務是否可執行,包括事務是否被篡改、支出賬戶的金額是否足夠等.在驗證合法之后,合約將自動執行相應的事務.

1.5 區塊鏈類型

根據節點加入或退出區塊鏈系統的方式,區塊鏈系統可分為公有鏈、聯盟鏈、私有鏈這3 類.

· 公有鏈系統也稱為非許可鏈,允許任何節點參與區塊鏈數據維護和讀取,同時,節點也可以隨時加入或離開該網絡.因此,公有鏈系統是一個完全的去中心化的系統.典型的公有鏈系統包含比特幣[1]、以太坊[60]等.在公有鏈中,其共識機制一般是基于計算的工作量證明共識.理論上,惡意節點需占有網絡中51%的算力,才可以控制該區塊鏈;

· 聯盟鏈也稱許可鏈,是一種新加入的節點需要獲得許可的區塊鏈.聯盟鏈限制可參與的成員節點,且節點的讀寫權限以及所負責的計算由聯盟鏈的設計規則來確定.典型的聯盟鏈包括 Hyperledger Fabric[59]等.整個聯盟鏈由所有節點共同維護,但是與公有鏈不同,聯盟鏈可以假定網絡中部分節點是可信的.節點的加入以及共識過程一般通過可信的節點控制.聯盟鏈一般不采用工作量證明的共識機制,而是多采用PBFT 等基于通訊的共識算法;

· 私有鏈則僅限信任的個體使用,且不完全能夠解決信任問題.網絡節點彼此之間需要透明,但不對外公開.

2 區塊鏈的數據存儲

在區塊鏈的各種應用中,數據的存儲是底層設計中非常重要的層次.由于數據庫的廣泛應用及其豐富的數據管理工具,很多工作研究利用數據庫的存儲來實現區塊鏈的數據存儲管理.針對區塊鏈數據的存儲模式主要集中在兩個方向.

· 一個方向為基于鍵值對的存儲模式,該模式下存儲的任一數據記錄包含一個可以確定該記錄的主鍵,并將其余部分視為該主鍵所對應的數值進行存儲.該模式數據結構簡單,可以在處理大規模數據時獲得很好的性能;

· 另一個方向是采用關系型數據的存儲模式,該模式將數據以關系模型的方式建模并存儲.在該模式下,可以保證數據滿足諸多限定條件,例如數據庫的一致性、原子性等.因此,部分公司已經推出了基于數據庫的區塊鏈系統,包括Amazon QLDB(https://aws.amazon.com/cn/qldb/)以及ORACLE blockchain table(https://blogs.oracle.com/blockchain/)等.該類區塊鏈在數據庫的基礎上,通過設計共識機制,確保各個節點數據的一致性.

由于區塊鏈上數據存儲的成本遠高于一般數據庫,部分工作采用重新編碼、鏈上-鏈下結合等方式來減少區塊鏈數據存儲的開銷.因此,我們也將從鍵值對模型和關系數據模型兩個方向對其進行綜述,并介紹針對區塊鏈數據存儲的優化技術.表1 分別從性能、可拓展性以及技術復雜度方面,比較現有關于數據存儲的工作.

Table 1 Comparision of the approaches for data storage in blockchains表1 區塊鏈存儲技術的比較

2.1 基于鍵值對的數據存儲模式

在區塊鏈的應用中,許多系統采用基于鍵值對的文件系統存儲其數據狀態.由于基于鍵值對的數據庫往往具有比較高效的查詢處理性能,Hyperledger Fabric[60],Ethereum[59]均采用鍵值對數據庫存儲其數據.比較常見的區塊鏈鍵值對存儲系統包括LevelDB[61],RocksDB[62]等.

在典型的區塊鏈系統中,各個節點均要存儲區塊鏈內數據的備份.在這種情況下,數據在鏈上的存儲代價極高.同時,考慮到部分共識協議需要大量的網絡開銷,在數據規模極大的情況下,直接將所有數據存儲于區塊鏈中將產生巨大的存儲開銷和網絡通訊代價.因此,部分工作旨在以較小的代價提高數據存儲規模,包括分布式存儲、鏈下存儲等技術.

文獻[63]研究通過分布式編碼的方式提高區塊鏈存儲規模.具體而言,區塊鏈的節點分為多個區域,并且保證每個區域內的所有節點數據可以通過整合,生成整個區塊鏈數據.因而在這種情況下,一個區域的單一節點不需要存儲整個區塊鏈內數據副本,而只需要存儲部分數據即可達到數據一致性的要求.在編碼過程中,首先假定要將數據分割為n個不同的塊,并將其分配到一個區域的m個節點中.利用分布式存儲的編碼技術,例如MDS編碼,可以生成相應的數據分配方案,使得在m個節點中,獲取任意k個節點的數據,即可獲得所有原始數據.因此,整個系統的數據可以在存在不超過k個惡意節點的情況下,依然保證一致性.與此同時,為了保護數據隱私,數據利用Shamir’s secret sharing 技術加密,并將密鑰分配給一個區域內的各個節點.Shamir’s secret sharing 技術可以保證各個節點獨自的密鑰均不相同,且不與原始密鑰相同.當需要獲得完整數據時,系統可通過各個節點的密鑰計算出原始密鑰,再對數據進行解密.由于該方法減少了每一個節點的存儲開銷,因而其具有很好的拓展性.但是由于需要對數據進行編碼操作,因而在數據動態輸入的過程時,需要額外的編碼計算開銷.

當利用區塊鏈存儲相應的數據時,如果數據規模極大,直接在鏈上存儲所有的原始數據會導致存儲開銷極大,且降低系統的性能.為了減少相應的數據存儲開銷,文獻[64,65]研究基于區塊鏈的鏈上鏈下混合存儲的方式.在鏈上鏈下混合存儲的模型中,數據均以鍵值對〈key,value〉的格式進行存儲.原始數據往往直接儲存在相應的云服務器中.云服務器中的數據不在區塊鏈中,而是相當于在鏈下.在區塊鏈中存儲相應數據的哈希值,即〈key,hash(value)〉.這樣,鏈上的數據不包含原始數據,而只有key以及數據的哈希值.當用戶通過云服務獲得數據時,可利用區塊鏈上的哈希值對數據進行驗證,從而可以保證數據的完整性與一致性.同時,由于在區塊鏈上存儲數據以及部署智能合約均需要存儲開銷以及相應的貨幣開銷,文獻[66,67]提出了多種基于鏈下存儲的優化技術.其中,在計算方面,可以將狀態檢查等計算采用鏈下驗證的方式,而不需要采用鏈上的智能合約,從而進一步降低存儲開銷.Ekiden[62]則提出:為了保證智能合約的隱私性,智能合約也可以在需要的情況下采用鏈下存儲.為了保證安全性,鏈下的執行環境需為可信的執行環境(例如采用Intel SGX 處理器).同時,區塊鏈存儲相應的智能合約狀態的哈希值.在這樣的結構下,網絡同時存在計算節點與共識節點.計算節點負責智能合約的狀態的改變以及計算等,而共識節點只負責針對智能合約的狀態哈希形成共識.

由于區塊鏈存儲全部的歷史數據,部分區塊鏈操作需獲取不同歷史版本的數據,Forkbase[22]設計了支持數據版本查詢的數據存儲系統.針對版本控制問題,Forkbase 將數據拆分為塊,并在塊的級別減少重復的數據冗余存儲.具體而言,Forkbase 利用POS-Tree(pattern-oriented-split tree)這一索引來快速地確定重復數據.

類似于B+Tree,在POS-Tree 中,每個葉子節點包含相應的數據,而非葉子節點保存其子樹的鍵值.非葉子一般存在多個不同的分支.與此同時,POS-Tree 利用默克爾樹的特性,對每個節點計算其相應的哈希簽名.內部節點的簽名由其子節點的簽名決定.因此,當一個分支的根節點哈希值沒有變化時,則可以確定該節點的所有子節點所包含的內容均沒有更新版本.相應的,當兩個Pos-Tree 中節點的數據不同時,必然導致其祖先節點的簽名不同.因而在查找不同的數據時,只需從簽名不同的根節點開始,搜索其子樹中帶有不同簽名的節點即可.在文獻[22]中,Forkbase 被應用于Hyperledger Fabric,以取代Hyperledger Fabric 的存儲層.

2.2 基于關系型數據的存儲模式

在關系型數據中,數據往往以表的形式進行存儲.存儲于同一表的數據具有相同的模式,而不同表之間的數據根據主外鍵等產生關聯關系.關系型數據一直以來都被廣泛應用于企業的管理等諸多方面.文獻[68,69]提出了BlockchainDB 這一將數據庫的關系模型概念與區塊鏈結合的系統.由于企業間的交易往往希望將部分關系型數據在二者之間公開并獲得共識,BlockchainDB 主要針對共享表類型數據,并在多個用戶均需要對共享表進行操作的情況下,支持對表進行數據驗證.該系統采用聯盟鏈的設計方式并假定節點不可信.區塊鏈作為數據的存儲層,保證數據在不可信環境下的一致性.在一個BlockchainDB 系統內部,節點間存在多個分塊.每一塊獨立地維護一個區塊鏈并存儲共享表的部分數據.每一塊獨立的區塊鏈保證了分塊內數據的一致性.

在每一塊的區塊鏈存儲層之上,BlockchainDB 構建數據庫層.數據庫層負責的任務包括:(1) 數據庫層記錄表的任一條記錄存儲在哪一些分塊中;(2) 提供用戶可直接調用的API;(3) 保證用戶提交的事務處理一致性.當需要進行讀寫操作時,用戶需提交數據所在分片的ID.之后,BlockchainDB 會在相應的分片中執行讀寫操作.由于采用分塊的方式管理數據,當用戶獲得數據時,需驗證所得到的數據是否被惡意篡改及其完整性.作者在文中提出了Online 和Offline 兩種驗證方法.

· 在Online 驗證方法中,用戶在提交讀請求并獲得相應的數據之后,廣播其所讀數據并要求所有存儲該數據的節點進行驗證.如果大部分節點返回的消息表示所需要驗證的請求以及數據符合本地的數據,則返回認可讀取到的數據的消息.當大多數的節點均認可所讀數據時,則認為數據已被驗證;否則,則判定讀取的數據被惡意篡改;

· 在Offline 驗證方法中,采用延遲驗證方式,即:當用戶提交驗證請求且驗證請求達到系統設定的參數e時,BlockchainDB 開始進行驗證.

3 區塊鏈事務處理

與數據庫中對事務處理的要求類似,區塊鏈中的事務同樣要求保證其原子性(atomicity)、一致性(consistency)、隔離性(isolation)與持久性(durability).原子性要求事務的所有操作或者全部完成,或者全部不完成,而不會存在中間狀態.在區塊鏈中,當一個智能合約對多個區塊鏈進行操作時,同樣要求其所有操作全部完成或全部不完成.隔離性則是針對數據資源的并發訪問,規定了各個事務之間相互影響的程度.在區塊鏈中,為了提高吞吐量,區塊鏈中的并發控制也得到極大的關注[71].在本部分,我們將從原子性、隔離性、一致性這3 個角度,綜述現有工作中區塊鏈的事務處理技術.表2 總結了部分工作針對事務的3 個特性所采用的主要技術方式及其針對的事務處理的階段與對象.

Table 2 Comparison of the approaches for transaction execution表2 針對事務處理的技術比較

3.1 確保原子性的處理技術

文獻[72]研究多鏈之間事務的處理過程,以保證其原子性.當一個事務需要在不同的鏈上進行讀寫操作時,一個保證原子性的直接做法是:將多個鏈合并成一個鏈,進而使得所有的事務處理只需在一個鏈上進行.這種方式在不需要考慮數據隱私的情況下是可行的,但是實際中,用戶或組織之間進行交易時,不希望自身內部的交易也被公開.換言之,當事務涉及多個鏈時,需要考慮每個鏈上單獨的數據隱私問題,同時也要確保跨鏈操作的可信性.因而,文獻[72]提出事務應存儲在所有與其相關的鏈上.同時,跨鏈的事務應該保證原子性,即只能在所有相關的鏈上均執行操作,或者均不執行(即abort).

為了保證事務的原子性,文獻[72]提出了兩類方法.

· 第1 類方法需要區塊鏈網絡中存在額外的負責排序的節點.首先,所有的事務均廣播其簽名,從而確保發送消息的真實性;之后,所有的區塊鏈針對其自身所需要處理的事務,形成自身的事務處理順序;在形成順序之后,區塊鏈的節點將需要參與跨鏈操作的事務以及該事務在本地區塊鏈事務順序中的前一個事務的哈希值,合并為一個消息進行廣播;對于負責排序的節點,其獲得的消息包括跨鏈事務以及跨鏈事務在各個區塊鏈中前一個執行事務的哈希;排序節點根據獲得的消息,確定跨鏈事務是否執行以及執行順序;

· 第2 類方法沒有相應的排序節點,但是各個區塊鏈有部分節點參與跨鏈事務的排序.具體而言,與第1種方法類似,首先,各個區塊鏈生成獨自的事務執行順序;在形成順序之后,區塊鏈的節點同樣將需要參與跨鏈操作的事務以及該事務在本地區塊鏈事務順序中的前一個事務的哈希值,合并為一個消息進行廣播.與第1 種方法不同,該廣播發送到所有區塊鏈的各個參與排序的節點中.參與排序的節點利用PBFT 或Paxo 等基于投票的共識協議,確定跨鏈事務產生的順序,并將其廣播到所有鏈的節點.各個區塊鏈依據產生的順序執行事務.

文獻[72]利用額外的節點或已有區塊鏈網絡中的部分節點,負責事務中所有操作的執行順序問題,以保證事務的原子性.與之不同,文獻[73]考慮利用鎖機制實現跨鏈事務的原子性.當需要跨鏈事務時,首先,區塊鏈A的用戶利用智能合約對其資產進行加鎖操作,使其不能被其他事務使用.同時,利用哈希函數h=H(s)產生簽名并將簽名與資產寫入到智能合約中.該智能合約中需添加條件為:如果另一方可以提供s′,使得h=H(s′),則向另一方轉賬A中被鎖定的資產.另一方可通過查看智能合約,確認合約的條件以及相應的h值.之后,在自身的區塊鏈部署智能合約.合約的框架為:如果A提供S,使得h=H(S),則向A轉賬.文獻[73]利用以上的基于哈希函數鎖機制,實現了跨鏈交易的原子性.

文獻[73]的方法可以保證跨鏈事務的原子性,但是其要求所有的參與者需先選舉一個領導者,并由領導者串行地部署相應的智能合約,而串行的方式導致部署智能合約的開銷很大.文獻[74]針對文獻[73]的問題,研究如何在多條區塊鏈并發地部署智能合約,同時保證跨鏈事務的原子性.其核心思想在于:通過智能合約,確保當事務的原子性沒有被滿足時,相應的事務被終止并且回滾所有已經執行的操作.例如A持有比特幣與B持有的以太幣進行兌換,只有當A,B均獲得對方的貨幣時候,整個事務才可以結束.當A轉賬給B,但是B沒有轉回相應的金額時,則該事務在被終止的同時,需確保A拿回自己的那一部分金額.在文獻[74]中,作者假定每一組交換類型的事務中有一個發起者,并且有一組節點負責各個區塊鏈間的共識.該組節點被稱為觀察網絡.事務的發起者負責部署智能合約到該組節點中.首先,多組交換的事務可以建模為一個圖.圖中的節點表示一個賬戶,邊表示賬戶間的交易.一個合法的交換事務需要滿足的條件為:該事務所對應的圖,在刪掉表示發起者的節點之后,余下的圖不可以存在環.發起者將事務所對應的圖結構簽名并廣播.其余參與交易的賬戶驗證該圖結構,并部署相應的智能合約在自身的區塊鏈中.同時,發起者部署一個智能合約到觀察網絡中.該智能合約的觸發條件為:當所有相應的賬戶均執行對應的智能合約后,確認交易;否則,則將所有智能合約鎖住的資產回退到相應的賬戶中.在文獻[74]中,觀察者網絡既可以是可信的節點,也可以是非可信的環境.

3.2 確保隔離性的處理技術

為了提高區塊鏈系統的事務處理效率,分布式系統中的部分并發控制技術已經被應用到區塊鏈系統中.本小節主要綜述針對事務隔離性的技術.

在數據庫中,針對事務的并發處理,典型的方式采用先排序后執行的策略.在區塊鏈系統中,很多系統依然沿用這種策略[1,59].首先,在排序過程中,所有的節點需要達成一個針對所有事務順序的全局共識;之后,在執行階段,所有節點在本地按照已經達成共識的順序執行相應的事務.與數據庫中的先排序后執行的策略不同,在Hyperledger Fabric[60]區塊鏈系統中,其工作流程則是采用先模擬后排序的思路,如圖2 所示.整個流程包含了模擬階段、排序階段、驗證階段、執行階段這4 個部分.

· 在模擬階段,客戶端將一系列的事務處理請求提交給部分節點.收到請求的節點將在本地的數據中模擬事務的執行.節點會產生一個簽名并將簽名以及事務所需進行的讀寫數據集合進行廣播;

· 在排序階段,排序服務節點接受所有提交的事務并確定事務執行順序.默認情況下,事務會按照提交時間的順序進行排序.在排序結束之后,這些事務被組織成一個區塊并分發給網絡中的節點;

· 在驗證階段,節點按照順序確定事務是否可執行.在該階段需驗證兩部分內容:

? 首先,節點驗證事務的簽名是否滿足共識條件.如果不滿足,證明存在節點篡改了客戶提交的事務.此時,該事務被標記為不可行;

? 其次,節點驗證提交的事務順序是否存在讀寫沖突.如果某一事務與排序在其前面的事務存在讀寫沖突,則該事務被標記為不可行.

· 在執行階段,所有可行與不可行的事物均被寫入區塊中.同時,可行的事務被執行.

常用的先排序后執行的策略在排序之后,區塊鏈中的各個節點只能順序地執行相應的事務.而Hyperledger Fabric 則可以利用模擬階段的結果,并發地執行事務并保證數據的一致性,從而提高系統性能.針對Hyperledger Fabric 的各個階段,如表2 所示,許多工作針對不同階段提出相應的優化技術,以提高系統的并發度.

在事務的并發控制過程中,如果事務間存在讀寫沖突,那么只有部分事務可以成功執行.其他的事務將被中止.在文獻[75]中,通過實驗發現:即使Hyperledger Fabric 可以提高事務的并發度,直接利用讀寫沖突處理區塊鏈的事務依然導致大量的事務被終止.文獻[75]研究通過改變事務的執行順序,減少事務中止的個數,從而提高并發度.在Hyperledger Fabric 的“模擬-排序-驗證-執行”過程中,可以從兩個方面提高事務的并發度.

· 首先,一個區塊中的事務默認按照提交時間的順序進行處理.然而,可以通過改變區塊內事務的順序,使得原本被終止的事務在新的順序下沒有沖突,從而可以順利執行;

· 其次,事務的處理過程需要4 個階段,而現有工作只能在驗證階段判斷事務是否被執行或終止.如果可以在該階段之前判斷事務不可執行,則可以提前將事務標記為終止狀態,從而節省后續階段的開銷.

基于以上兩點,針對區塊內事務的順序問題,文獻[75]提出了利用沖突圖的方法產生執行順序的算法.具體而言,在沖突圖中,圖中的一個節點表示一個事務.當兩個事務Ti,Tj存在讀寫沖突時,相應的事務的點之間存在一條有向邊Ti←Tj,表示Ti應在Tj之前執行.而一個區塊中,代表所有可執行事務的點以及之間的邊所構成的圖一定是沖突圖中的一個無環子圖,因而作者提出了啟發式的算法,在沖突圖中,通過查找其中最大的無環圖,進而產生相應的事務執行順序的算法.

同時,針對區塊間的事務讀寫沖突,作者提出分別在模擬階段與排序階段判斷事務是否可行的機制.如果不可行,則事務不需進入到下一個階段.在模擬階段,系統的節點需對數據進行讀操作.節點的數據都添加了相應的版本號.當一個事務的多個讀數據的版本號不一致時,則證明部分讀入的數據已經被其他事務修改,則該事務被標記為不可行.在排序階段,當兩個事務都需讀入相同數據且后一事務讀入的版本號與前一事務不相同時,則后一事務被標記為不可行.其原因在于:Fabric 的事務執行不是以單一事務為單位,而是以區塊內所有事務為單位,因而區塊內事務讀入的數據應具有相同的版本號.

ParBlockchain[76]以及文獻[77]研究了在Hyperledger Fabric 中事務的并行問題,并針對執行階段進行優化.在ParBlockchain 的執行階段,與文獻[75]類似,部分節點根據事務的讀寫沖突建立關系依賴圖.圖中的節點表示事務,并用有向邊表示事務的沖突.該圖在建立后,被傳送到負責排序階段的節點中.排序節點根據關系依賴圖確認事務的執行順序.在執行層面,當多個事務屬于不同的應用,或者不同事務之間不存在讀寫沖突時,則這些事務可以并行執行.ParBlockchain 將執行事務的節點按照不同的應用進行分類,一個節點只負責處理一部分應用的事務.當需并行執行不同應用的事務時,處理不同應用的節點可并行地執行對應應用的事務.在執行完成之后,各個節點廣播其執行結果,即可保證所有節點數據的一致性.

以上工作主要針對的是排序與執行過程.針對驗證階段,文獻[78,79]研究針對智能合約驗證過程的并發控制.智能合約在公有鏈上的執行一般分為兩個階段:在第1 個階段,挖礦節點負責串行的執行智能合約代碼并將新生成的事務、智能合約的新狀態、前一個區塊的哈希等均存儲在一個新的區塊中,之后,該區塊會通過挖礦節點間的共識,加入到區塊鏈中;在第2 個階段,所有網絡中的節點會驗證該區塊內的事務與結果是否與本地的數據一致,只有當對應的數據均一致時,該區塊才會被節點所接受.因此在第2 個階段,智能合約所產生的事務會串行的被節點重新執行.文獻[78,79]通過不同的機制實現該階段智能合約的并發驗證.在文獻[78]中,作者利用加鎖的方式實現并發控制.對于挖礦節點,其在執行智能合約代碼的同時生成happens-before 圖.該圖中,每個節點代表一個智能合約,節點與節點的邊記錄智能合約的執行需遵循的先后順序,該順序可根據智能合約間的讀寫沖突確定.挖礦節點在生成happens-before 圖之后,將其寫在區塊內.區塊鏈網絡的節點需要驗證區塊內容時,可根據happens-before 圖,確認可以并發執行的智能合約.與文獻[78]中加鎖機制不同,文獻[79]則利用軟件事務內存(STM)機制來處理智能合約的并發執行.文獻[79]將一個智能合約視作一個原子事務,原子事務中包含的操作只可能全部執行或者全部取消.在驗證過程中,所有智能合約均會按照時間戳的順序并發地執行.同時,節點會檢測智能合約之間是否存在讀寫沖突.當智能合約間存在沖突時,則終止其中一個合約,并在之后重新提交該智能合約的事務.文獻[80]則研究事務處理的順序如何滿足拜占庭容錯.

3.3 確保一致性的處理技術

針對事務的一致性,文獻[81]提出利用數據庫的一致性來處理區塊鏈中并發事務的一致性問題.現有數據庫可以支持執行多種事務與查詢,因而在數據庫上建立區塊鏈的一個核心問題是:如何確保所有數據庫節點執行事務的順序完全一致,從而可以保證節點數據的一致性.在文獻[81]中,為了保證區塊鏈的安全性,作者假定在聯盟鏈的環境中,每一個節點均需要對其提交的每一個事務進行簽名.其余節點可根據簽名驗證事務的真實性.為提高吞吐量,在確定事務處理順序時,作者優化了快照隔離的并發控制方法[82,83],使其從針對事務的并發拓展到針對區塊的并發,并提出兩種針對一般事務的并發控制策略.

(1) 傳統的先排序后執行并發控制.在該方式框架下,系統中的部分節點負責對提交的事務進行驗證并排序.由于在區塊鏈中,一個區塊內的事務需全部執行之后方能完成,當存在寫操作時,若采用傳統數據庫中的快照隔離方法,在多個事務均對一個數據進行寫操作時,一個事務需等待之前所有的事務寫操作均完成之后方可開始執行,這將導致系統性能大幅下降.因而作者提出:在事務執行階段不考慮事務所處的區塊,而是直接對事務進行排序.與此同時,對數據的寫操作會產生多個副本.當事務完成時,按照事務在區塊鏈中的順序確認所產生的多個副本中的一個為合法的副本.

(2) 先執行后排序的并發控制方式.在該種方式下,同樣利用快照隔離來進行事務的并發處理.但是該方式需要處理3 個問題:首先,先執行再排序要避免幻讀的可能,即讀入還未寫入的數據;其次,要避免臟讀的可能,即讀入已被更新的數據;最后,網絡中不同的節點由于延遲等原因,數據可能未達成一致,進而可能使得事務所需訪問的數據不存在.為了處理這些問題,作者提出了基于區塊高度的快照隔離.具體而言,每一個數據庫節點都按照區塊鏈的內容來存儲數據.每一個節點記錄相應的已寫入的區塊鏈的個數.區塊鏈的個數可區分現有區塊鏈的快照.當一個節點A的區塊的個數多于另一節點B時,則A節點的數據已更新,而B的數據還未更新.作者設計了基于區塊鏈高度的并發快照隔離方法,確保所有的節點均可在事務完成后,保證數據的一致性.

文獻[68,69]提出了BlockchainDB,一個將數據庫與區塊鏈相結合的系統,并設計了多種一致性水平,以提高事務寫的效率.在這種情況下,當用戶提交查詢時,數據庫層的TransactionManager 負責分發提交的查詢并確保不同的一致性.具體而言,BlockchainDB 有兩種一致性水平可供選擇.第1 種為串行一致性.在串行一致性中,所有的寫操作按照提交的順序插入隊列中.當多個寫操作同時對一個數據進行寫操作時,只有隊列中的第1 個寫操作可以被執行.其他的寫操作均處于等待狀態,直到寫操作完成.第2 種為最終一致性.在最終一致性中,寫操作依然按照順序插入到隊列中,但是所有的讀操作可以馬上執行.在這種情況下,臟讀的情況可能會發生,即數據在被讀入之后,被其他的寫操作覆蓋,因而之前所讀的數據與存儲的數據不一致.當用戶提交查詢時,由分片管理器確認查詢所需的數據處于區塊鏈中的位置.之后,該位置的數據會被并行地讀寫.由于BlockchainDB 支持不同的一致性,查詢的效率在不同的一致性下將會不同.例如,在串行一致性下,BlockchainDB 的查詢可能需要等待隊列中寫操作的完成之后才可進行.

4 區塊鏈查詢處理

在區塊鏈中,所有數據均以鏈表的形式存儲.與一般數據庫的查詢不同,區塊鏈存儲的數據包含在所有事務當中.區塊鏈查詢分為一般查詢與可信查詢.表3 從對關系型查詢語句的支持、可信性查詢以及鏈上鏈下數據查詢等多方面比較了最新的研究工作.

Table 3 Comparison of the query processing in blockchains表3 區塊鏈查詢處理比較

4.1 一般查詢處理

LineageChain[84]研究區塊鏈環境下數據溯源查詢的效率問題,并支持需要數據溯源的智能合約.

LineageChain 針對每個數據,賦予其初始版本號.當一個事務對數據進行讀寫操作時,事務的輸出可能是新的數據或者更新現有數據的版本.這鐘情況下,如果一個區塊內還有不同事務時,則可以視作一個區塊的事務對前一區塊數據庫狀態進行的修改.因此,數據版本號與區塊同步遞增.LineageChain 將這種遞增關系建模成為一個無環圖.當需要溯源查詢時,利用無環圖中點的拓撲序進行搜索.

與文獻[84]需額外構建圖結構不同,文獻[85]研究利用智能合約確定數據的關系,并對數據進行溯源查詢.當一個數據的創建者創建一個文檔時,創建者可在區塊鏈中部署一個智能合約.該合約的功能包括更改數據擁有者、添加可訪問用戶、進行溯源查詢等.同時,該合約要求所有對指定文件的更改需經過投票過程.參與投票的用戶由數據擁有者確定.對數據的任意一次更改需至少半數以上的用戶投票同意才可進行.在這種環境下,惡意的用戶若對數據進行惡意篡改,需控制半數以上參與投票的用戶.同時,由于所有的修改均利用部署的智能合約,因而對數據的溯源查詢轉化為對智能合約調用的查詢.

部分工作研究區塊鏈查詢處理語,使其與數據庫的SQL 查詢語句類似[86-88],文獻[88]提出了SEBDB,并設計了與數據庫SQL 語句類似的查詢語句,使之可以完成在區塊鏈中對關系型表的建表、插入、選擇等操作.在SEBDB 中,數據分別采用鏈上鏈下存儲方式.鏈下存儲的數據由一個本地關系型數據庫進行管理.針對鏈上與鏈下的數據,SEBDB 設計了包括連接操作等語句.當只需要鏈下數據進行連接操作時,SEBDB 可以直接利用本地數據庫的Join 語句來進行.當需要鏈上鏈下數據同時進行連接時,SEBDB 首先掃描鏈上數據,并利用hash-join的方法將其與鏈下數據進行連接.為了提高查詢效率,SEBDB 設計了區塊層級的B+-Tree.SEBDB 利用區塊ID、事務ID 以及時間戳作為每一個B+-Tree 里面數據的排序鍵值.當給定區塊ID、事務ID 或者時間戳時,可利用區塊級的B+Tree,快速找到存儲相應數據的區塊.同時,SEBDB 建立表與區塊的索引,即每個表的索引指向所有包含對該表進行操作的事務的區塊.利用以上索引,使得對鏈上數據的訪問不需掃描所有區塊.文獻[89]在SEBDB 基礎上,通過建立數據的視圖,進一步提高其查詢效率.

4.2 可信查詢處理

考慮到區塊鏈應用在不可信的環境下,當用戶提交查詢并獲得查詢結果時,往往需驗證其查詢結果的可信性[90-93].文獻[94]提出了一個區塊鏈系統vChain,實現了高效的可驗證查詢處理算法.該系統假定用戶節點并不一定存儲整個區塊鏈的全部數據,而是只存儲所有區塊中的哈希值.由于一個區塊的哈希值所占的存儲空間遠遠小于區塊內存儲事務所花費的空間,因而該假設即使在輕量級的硬件環境下也可實現.為了驗證查詢結果,在每個區塊中添加一個額外的命名為AttDigest 的字段.具體而言,AttDigest 由多集合加密累加器(cryptographic multiset accumulator)所生成.所生成的AttDigest 具有如下性質:給定同一公鑰,當需驗證兩個集合的交集是否為空時,可以通過各自的AttDigest 直接驗證.利用該性質,當查詢條件可以表達為集合交集的形式時,可利用返回結果的AttDigest 與查詢條件中集合的AttDigest 進行比較,來確定返回的結果與查詢的條件是否存在交集.如果發現二者不存在交集的關系,則驗證查詢結果和查詢條件不匹配.

文獻[94]進一步將該方法推廣到范圍查詢.范圍查詢中,用戶會對值域為數字的屬性給定一個區間.查詢結果返回在該區間中滿足條件的數據.當驗證范圍查詢的查詢結果時,無法直接將AttDigest 應用到范圍查詢中.其原因在于,AttDigest 只適用于判定集合的關系.因此,作者將范圍查詢轉化為集合查詢.具體而言,首先,vChain將所有數字以二進制形式進行標識,并將其視作字符串.利用二進制表示,vChain 構建了前綴樹來表示所有數字.每個葉子節點是一個具體的數字,而非葉子節點對應一個數字的范圍.當一個查詢中包含范圍條件時,該范圍對應前綴樹的一部分連續的葉子節點.因此,可將其轉化為基于前綴的集合表示形式.例如,當查詢范圍為[0,6],且該屬性數據的范圍為[0,7]時,其對應的表達形式可為0*∩10*∩110.符號*表示二進制的0 或1.基于此集合表示,則可以將AttDigest 的簽名同樣應用于范圍查詢.

同時,為了提高驗證效率,vChain 提出了區塊內以及區塊間的索引.區塊內的索引為一種類似于默克爾樹的結構.樹中的每一個節點包含3 個域,分別為左子樹哈希值、右子樹的哈希值和集合屬性所包含的元素.利用該樹結構,查詢處理可以看作對樹的搜索.當搜索到樹中節點時,如果該節點的集合的AttDigest 不滿足查詢條件,則不需要繼續搜索該節點的子節點.同樣的思想也被用來建立區塊間的索引.vChain 將區塊按照指數遞增的方式來分段.例如,每段區塊域包含的區塊的個數分別為2,4,8 等.每一個區塊域均計算相應的AttDigest.當一個區塊域所包含的所有集合元素所產生的Attigest 均不滿足查詢條件時,則整個區塊域可以不被搜索.利用區塊內以及區塊間的索引,vChain 提高了查詢驗證的效率.

同樣針對范圍查詢,文獻[95]研究在以太坊框架下,查詢結果驗證的開銷問題.開銷是指在以太坊框架下,執行操作所產生的gas 開銷.在以太坊的框架下,當用戶需要存儲以及執行智能合約時,需要支付相應的gas.gas 可由以太幣兌換.在智能合約中,不同的操作需要支付不同數量的gas.例如,從區塊中讀數據需要200gas,更新操作需要5 000gas,而寫操作需要20 000gas.在這種情況下,當用戶執行查詢驗證時,一個考量是如何用盡量少的gas來達到驗證的目的.基于此,作者提出了GEM2-Tree 這一數據結構,來達到減少gas 開銷的目的.一般驗證查詢結果需要區塊鏈以及用戶端均產生相應的驗證簽名,并在查詢返回結果之后,通過簽名進行查詢結果驗證.針對區塊鏈這一讀寫操作開銷差別極大的情況,作者提出利用代價低的讀操作代替代價高的寫操作的思想,并提出了SMB 樹.SMB 樹是一種壓縮的默克爾樹,它并不顯示地存儲默克爾樹的非根節點,而是只在區塊中存儲其根節點的哈希值.整個智能合約的索引包含一個完整的默克爾樹以及多個SMB 樹.新加入的數據總是先加入到SMB 樹中.由于SMB 樹一般規模較小,所以針對插入操作,其gas 開銷較小.由于區塊鏈中包含一個默克爾樹和多個SMB 樹,當執行范圍查詢時,服務器需要搜索整個默克爾樹,并在相應數據上執行查詢處理過程.在得到結果的同時,服務器也需要將包含結果的默克爾樹或者SMB 樹的驗證信息全部返回.客戶端獲得所有驗證信息后,需要利用相應的驗證重構默克爾樹或SMB 樹并進行查詢驗證.

Veritas[96]針對數據庫共享表的情況,設計支持驗證的區塊鏈.Veritas 將數據存儲在數據庫中,并且允許共享表可被網絡中的節點訪問.在數據庫之外,數據簽名以及共識投票則存儲在區塊鏈中.為了保證共享表在各個數據庫的一致性,Veritas 利用可信的節點來對事務進行排序.與一般的區塊鏈系統不同,Veritas 的各個節點只在自身的數據庫中執行針對共享表的事務.所有節點在一段時間內廣播其所有新生成的日志以及執行事務所進行的讀寫數據.所有節點對于廣播的日志以及數據,利用投票的方式來確保一致性.

5 區塊鏈可擴展性

分布式系統的可擴展性主要考慮兩個方面的因素:每秒處理事務數(TPS)和網絡節點數.而區塊鏈在這兩方面均受到一定的制約[23].其原因在于:為了滿足拜占庭容錯,節點間需要滿足共識協議條件.無論是基于計算的共識協議還是基于通訊的共識協議,都會產生極大的計算開銷和網絡開銷.另一方面,傳統的中心化系統可利用平衡不同節點的工作量等方式提高系統的吞吐量.但是在區塊鏈中,節點均存儲區塊鏈中的數據且均需執行相應的事務.

文獻[97]討論了提高區塊鏈吞吐量的諸多挑戰.部分工作,例如BigchainDB[87]等,針對比特幣所支持的UTXO 這類交易數據模式進行優化,以提高可拓展性.而大部分提高區塊鏈吞吐量的工作針對的是Account 模型下的數據模式.由于區塊鏈系統中,共識的達成是基于區塊的粒度,所以一種簡單的提高吞吐量的方法是通過調整系統的各個參數,例如區塊的大小,使得系統的TPS 得到提升.該種方法在公有鏈環境下對性能有一定的提升.但是StreamChain[98]指出,改變區塊的大小可以提高基于工作量證明共識協議下的區塊鏈系統吞吐量.而在聯盟鏈中,多采用的是基于通訊的共識.在這種情況下,增加區塊的容量反而會使系統性能降低.部分工作提出了將區塊鏈的鏈式結構拓展到無環圖[99,100]或利用側鏈[101-130]的方式,以提高區塊鏈的共識效率.但是由于無環圖同樣可以產生一個全局的區塊順序,并且可以根據該序列轉化為鏈式結構,因而本節主要針對鏈式結構下提高區塊鏈可擴展的技術,尤其是分片以及鏈下事務處理技術.

5.1 基于分片的區塊鏈系統

為了提高吞吐量,將數據庫中的分片技術引入到區塊鏈系統中是研究的一個熱點問題[104].表4 總結了部分區塊鏈可擴展性的特點.

Elastico[49],RapidChain[50],Omniledger[105]等系統利用分片技術大幅度提升了系統的吞吐量.在一般情況下,系統中所有節點劃分為多個片且每個片包含多個節點.這樣,每個片都具有一定的算力可以支持區塊鏈的共識協議.由于采用了分片技術,且區塊鏈系統運行在非可信環境中,片的劃分需要保證存在惡意節點前提下,依然可以安全進行事務處理.因此,現有的基于分片的區塊鏈工作大多需要在每個事務處理過程中,進行片的隨機再構建等操作[23,49,105],以保證惡意節點無法控制一個片.同時,為了降低共識階段的開銷,大多數系統會選取一部分節點組成委員會,且只有委員會節點參與共識階段.為了保證安全性,部分區塊鏈會在一段時間后,對委員會節點進行重新選擇或替換.

Table 4 Comparision of the scalability of blockchains表4 區塊鏈可擴展性比較

Elastico[49]最早提出在公有鏈系統中采用分片模型.在Elastico 中,整個網絡被分為多個片.Elastico 首先會要求所有節點計算基于工作量證明的驗證字段(公式(1)).最先得到該函數哈希值的C個節點稱為字典節點.字典節點負責記錄整個網絡所有節點所對應的片.網絡中的節點由其PoW 提交的結果決定該節點將被分配到哪個片,因而節點的分配具有隨機性,并且惡意節點無法確定其是否分配到同一個片.同時,為防止女巫攻擊,每個新加入Elastico 公有鏈的新節點都必須先執行PoW,網絡中的現有節點驗證新節點的PoW 并授權其加入網絡.

當一筆交易提交到網絡時,Elastico 會根據事務發送者的地址,隨機分配到不同的片中執行.各個委員會內對事務利用PBFT 等機制達成共識,并最終將達成共識的事務提交到最終委員會.其中,最終委員會的節點也是根據委員會節點ID 進行隨機選擇.最終委員會在節點中運行PBFT 共識協議,從而確保整個網絡的一致性.由于分片具有隨機性,當每個分片的節點數量不低于600 個時,其中三分之一的節點是惡意的概率為百萬分之一,因而系統的安全性可以得到保證.每執行一定數量的事務,Elastico 中所有的節點重新計算PoW,以便重新分配節點所屬的片.為減少片間的通訊,Elastico 的消息通過C個字典節點進行傳遞,使得其最優的通訊復雜度為O(Cn).

Elastico 在處理跨片事務的過程中,如果事務所需訪問的數據在一個片被加鎖,但在另一個片被拒絕,將會導致被加鎖的數據始終處于鎖的狀態.為了解決該問題,Omniledger[105]在進行跨片事務驗證時,采取兩步驗證來避免出現由于部分非法輸入而導致的事務中斷.首先,在第1 階段,Omniledger 鎖定所有輸入分片以及輸出分片.所有輸入分片檢查自身所在的片內輸入是否合法:如果合法,則生成一個包含本交易的區塊簽名的接收證明;類似的,如果非法,則生成拒絕證明.當所有的輸入都生成相應的證明,則可判定該事務可執行或取消.在第2階段,如果所有的輸入都返回接受證明,那么事務被執行.同時,終端創建并分發一個解鎖請求.每個參與該事務的節點驗證并更新賬本狀態.如果存在一個輸入所在的片返回拒絕證明,則事務取消.同時,終端生成并分發一個解鎖取消請求,輸入所在的片接受該請求并將已加鎖的數據解鎖.

RapidChain[50]同樣在Pow 共識協議下利用分片提高區塊鏈可擴展性.與Elastico 不同,RapidChain 不需要所有節點都存儲區塊鏈的全部數據.在這種情況下,對于一個事務,例如輸入輸出分別為In,Out的事務tx(In,Out),有兩種情況產生.第1 種情況是事務的輸入與輸出均在同一片內.由于數據都存儲于同一片中,這種情況下,直接利用片中的節點間的共識機制即可處理該事務(RapidChain 利用近似的PBFT 共識協議處理片中的事務).第2種情況為輸入In與輸出Out的數據處于不同片中.在這種情況下,不失一般性,假定輸入包含p組數據In={l1,l2,…,lp},輸出包含一組數據Out.RapidChain 在處理該事務時,Out所在的片將生成p個新的事務txi(li,Oi).每個事務輸入為li,輸出為Oi,并且滿足|li|=|Oi|.同時生成一個事務txp+1(O,Out).其中,輸入O包含O1,O2,…,Op,Out為原事務的輸出.在進行事務驗證時,輸出所在的片首先要求li所在的片驗證事務txi(li,Oi)是否可執行:如可執行,li所在的片將事務txi寫入其賬本,并發送Oi至Out所在的片.最終,txp+1(O,Out)可利用片內的共識機制進行驗證.整個過程通過將事務分割,實現了片間的共識.

Chainspace[106]則旨在解決分片情況下數據的一致性問題.當數據在多個片均存在相同的備份,且不同片通過不同的智能合約,均對該數據進行了修改,則可能導致不同片中數據不一致的情況出現.為了解決這個問題,作者提出了事務痕跡的概念.事務痕跡包含這個事務所需要訪問的所有數據,以及產生這些數據所調用的智能合約.基于事務痕跡,作者提出了S-BAC 共識算法.具體而言,當客戶端提交事務時,Chainspace 根據事務痕跡,在所有可能產生數據不一致的分片中分別執行共識算法,并且判斷在一個分片內,該事務是否和其他事務產生沖突:如果沒有沖突,則該事務在該分片內可執行;否則,返回取消命令.一個事務只有在它的痕跡在所有分片均可執行時,方可執行.當有任意分片返回取消命令時,則該事務會被終止.利用S-BAC 共識,Chainspace 解決了不同片之間的數據一致性問題,但是代價是一個事務需執行多輪共識.

文獻[107]提出了Monoxide 區塊鏈系統,該系統采用分片架構來對公有鏈系統進行優化.Monoxide 可以有效地解決分片結構中算力分散的問題.由于系統中存在多個片,且每個片獨立地進行共識計算,當攻擊者可以聚集算力攻擊特定片時,極有可能攻擊者具有該片超過51%的算力,從而使得共識協議失效.為了處理這種攻擊,作者提出了“連弩挖礦”這一協議.在該種協議下,Monoxide 允許一次成功地解決哈希問題可以確認多個片中的塊.連弩挖礦允許礦工同時參與多個編號連續的片.一般的工作證明方程如方程(1)所示,其中,默克爾哈希樹根包含區塊內事務的哈希值.而在連弩挖礦中,方程(1)的默克爾哈希樹根替換為由多個區塊塊頭部分的哈希值組成的新哈希值.這樣,在確認塊時,哈希函數將覆蓋多個塊的塊頭,同時,這些塊頭將共用一個驗證字段.這個結構允許連弩挖礦包含算力難度不同的共識組.一旦一個節點計算出驗證字段,則該節點將所有其涵蓋的區塊索引以及相應的默克爾樹的根節點的哈希值均記錄到區塊鏈中.其他節點也可根據此記錄,驗證其數據的真實性.最后,當區塊鏈出現分叉時,為了保證正確性,所有區塊鏈分支上的事務的后續原子操作均不會被執行,直到一個分叉被舍棄.

在文獻[108]中,作者研究在PBFT 共識協議下,通過分片的方式提高區塊鏈系統的吞吐量.為了提高系統的可擴展性同時保證安全性,該文獻將可信執行環境(trusted execution environment)融入到區塊鏈節點中.在可信執行環境中,數據的可認證性以及完整性均受保護,不被惡意程序所篡改.在共識協議達成階段,可利用可信執行環境的節點計算結果,減少共識達成所需要的開銷.在事務處理方面,作者將分布式數據庫中二階段確認與二階段鎖引入到區塊鏈中.具體而言,當節點需要處理跨片的多個事務時,首先向事務輸入所在的片發送確認請求,確認事務處理輸入是否合法.在收到所有確認之后,節點進行事務的執行并將執行的結果(commit 或者abort)回傳給所在的片.在事務執行階段,利用二階段鎖機制,將多個事務并發處理,進而提高整個系統的吞吐量.

針對共識算法,Algorand[109]提出了基于委員會節點的共識算法,以提高區塊鏈網絡的吞吐量.在Algorand中,共識算法會通過可驗證隨機函數,隨機地選擇一組節點作為委員會.委員會節點會根據其所持有的區塊鏈網絡中的貨幣份額來分配權重,并利用權重證明來實現共識.由于委員會的選擇采用隨機函數生成,因而攻擊者并不能確定哪一部分節點將會屬于委員會.同時,Algorand 會定期替換屬于委員會的節點,從而保證網絡的安全性.

5.2 區塊鏈的鏈下事務處理

為了提高系統的吞吐量,部分事務可從鏈上處理遷移到鏈下,即部分交易不在區塊鏈所記錄且不需要節點間達成共識.但是,由于存在不需要達成共識的事務存在,鏈下事務處理往往解決節點之間的可信問題[104,110].現有的工作多應用在鏈下的轉賬交易等(例如比特幣).通過建立鏈下的信任網絡[111-113],區塊鏈允許在鏈下執行特定用戶之間的事務,并最終合并成一個事務存儲在鏈上.通過這樣的方式,大量的信任節點之間的交易不需要通過區塊鏈的共識驗證,從而提高整個網絡的吞吐量.

文獻[113,114]分別基于比特幣和以太坊,提出了支持比特幣的Lighting 網絡和支持以太幣的Raiden 鏈下支付網絡,來作為比特幣和以太坊交易的補充.在鏈下支付網絡中,當用戶與用戶確認彼此可信時,可以在他們之間建立支付通道.支付通道內的交易所產生的事務可以不需要經過鏈上的共識確認,而可以直接確認.在鏈下的支付網絡中,參與的用戶需提前存入一定量的比特幣或以太幣.當一個支付產生時,付款方需將存入的一部分金額轉入收款方.因而,鏈下支付需保證支付的金額小于用戶在網絡中所剩的金額.與此同時,鏈下交易網絡滿足傳遞性.當用戶A與B、B與C之間分別存在支付通道,即使A與C之間沒有建立支付通道,A依然可以通過路徑A,B,C,將一定金額通過鏈下交易網絡轉入C的賬戶中.因此,在鏈下支付網絡中,部分工作旨在減少支付事務的時間開銷.文獻[115]通過設計多個查找支付路線的算法,降低查找支付路線的平均時間開銷.

而與Lightning,Raiden 等網絡直接對賬戶內的金額進行交易不同,文獻[116]提出了Sprites,這一利用智能合約確保事務執行的網絡.通過智能合約,當多個事務存在線性關系時,Sprites 可以部分地并行執行多個事務,從而提高鏈下交易的執行效率.

鏈下網絡的另一個問題是再平衡問題.在鏈下支付網絡中,用戶需先存于一定的金額于支付通道中,并且該金額只能用于該支付通道中的兩個用戶之間的支付.假定用戶A,B,C這3 個用戶兩兩之間均有支付通道.在某一時刻,假定三者的金額狀態為AB通道之間A有200 元,AC通道之間C有200 元.則當A想轉賬50 元于C時,由于AC之間的支付通道中A的所剩金額為0,因而,A不能通過AC之間的支付通道轉賬于C.一個可行的通路是A通過AB以及BC之間的通道轉賬于C.但是實際上,用戶A的賬戶金額含有AB之間的200 元.金額上A足夠支付AC間的轉賬金額.因此,支付網絡中支付通道的不平衡導致支付需要訪問更多的節點,才能完成支付.

為了解決再平衡的問題,文獻[117]提出了Revive系統.該文獻作者構建了支付網絡圖.該圖中的一個節點為一個用戶,節點與節點的邊為建立的支付通道.利用該圖結構,一個支付網絡的支付能力為圖中所有支付通道可支付的金額總和.在這種情況下,最大化支付網絡的支付能力可以建模為線性規劃問題.但是,直接求解線性規劃問題是NP 難的問題.因此在Revive 中,一個支付網絡的再平衡過程可以首先找到圖中一個環形的結構,并在環形結構中的所有節點轉移相同的金額.由于是環形結構,該過程不會減少任何用戶的賬戶金額.基于此,作者設計了基于環形結構的再平衡算法,并提出了相應的啟發式優化算法.

6 區塊鏈數據管理的未來研究趨勢

區塊鏈作為近幾年被廣泛討論的技術,在數據管理方面尚有許多值得深入探索的問題.在本文的最后,我們提出一些值得進一步挖掘的針對數據管理的研究問題,希望對本領域其他研究者有所啟發.

· 區塊鏈內數據的隱私保護技術

在一個典型的區塊鏈中,所有的數據以及事務需要獲得所有節點的共識,因此所有的數據均可被網絡中的節點訪問.在這種情況下,需要研究數據隱私保護問題.文獻[88]初步嘗試了將部分數據存儲于鏈上,而將敏感數據存儲于鏈下的方式.在這種情況下,需要人為地將數據分割為敏感數據與非敏感數據.對需要保護的敏感數據,無法在區塊鏈的環境下對其進行管理.因此,解決該類隱私保護問題,從數據管理的角度,其難點在于如何對區塊鏈中的數據進行訪問控制.已有的針對數據庫的訪問控制方式對數據或者表設定訪問權限.直接將其應用于區塊鏈中會導致每個區塊的哈希值無法與所獲得的數據對應,因而用戶無法驗證該鏈中的數據是否被篡改.

· 鏈間事務處理優化技術

現有的多數工作考慮單一區塊鏈,并對單一區塊鏈下的事務處理等問題提出了高效的算法.但是當一個事務需要訪問多個區塊鏈時,會產生諸多問題,包括如何保證數據的一致性、高效的并發控制算法等.文獻[72]考慮了多鏈情況下的視圖以及驗證問題.現有的工作多考慮如何保證跨鏈事務一致性的問題.與單鏈相比,較少工作考慮跨鏈事務處理的效率.在跨鏈事務的執行過程中,可能會對一條鏈的數據進行加鎖等操作,這種操作將會影響與該鏈相關的事務執行.因此,僅僅考慮單鏈的事務或者僅考慮跨鏈的事務都可能降低整個系統的吞吐量.對鏈間事務處理效率問題的研究將著眼于:如何設計針對多鏈環境下的事務處理優化,以達到在保證一致性的同時,提高吞吐量的目標.

· 面向智能合約的事務處理優化技術

區塊鏈所部署的智能合約可以對數據進行添加、修改等操作.現有的工作往往將智能合約視為一個事務處理.但是由于智能合約執行的復雜度并不一致,且一個智能合約可以調用其他智能合約,僅將一個智能合約視為一個事務并不能完全衡量系統的性能優劣.因此,需要一個更適用于區塊鏈的衡量標準,以比較不同區塊鏈系統的性能.該標準的難點在于,如何設計基本的語義以及如何將智能合約與智能合約的嵌套關系同時考慮在性能衡量的指標中.

7 總結

我們從區塊鏈數據存儲、區塊鏈事務處理、區塊鏈查詢處理、區塊鏈可擴展性等幾個方面,對區塊鏈環境下的數據管理相關研究工作進行了較為系統的綜述,分析了各種區塊鏈數據管理方法的優點與不足,最后介紹了區塊鏈的未來研究趨勢.從數據管理的角度,區塊鏈的現有系統與方法仍然有非常多的工作需要進行.并且在一個不可信場景下構造一個可信計算環境,仍然具有非常巨大的應用前景,因此,通過本文的綜述與介紹,也希望有更多的研究者,尤其是數據庫研究者,更多地開展區塊鏈數據管理研究工作.