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

1(北京理工大學(xué) 計算機(jī)學(xué)院,北京 100081)

2(香港浸會大學(xué) 計算機(jī)系,香港)

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

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

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

從數(shù)據(jù)管理的角度,區(qū)塊鏈?zhǔn)且粋€在分布式環(huán)境下存儲大量存在全序關(guān)系的數(shù)據(jù)記錄系統(tǒng).數(shù)據(jù)以及對數(shù)據(jù)的操作均存儲在區(qū)塊內(nèi)并以區(qū)塊的粒度進(jìn)行管理.一個典型的區(qū)塊結(jié)構(gòu)如圖1 所示,包括前一區(qū)塊哈希值(PreBkHash)、共識驗證字段(ConsProof)以及區(qū)塊內(nèi)事務(wù)的哈希值(MerkleRoot).其中,節(jié)點可利用共識驗證字段驗證其存儲的區(qū)塊是否滿足共識條件,并確保網(wǎng)絡(luò)中少量節(jié)點的惡意行為不會影響區(qū)塊鏈的一致性,從而使其支持拜占庭容錯.

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

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

· 數(shù)據(jù)存儲方面

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

· 事務(wù)執(zhí)行方面

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

· 查詢處理方面

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

· 可擴(kuò)展性方面

為了提高分布式系統(tǒng)的可擴(kuò)展性,傳統(tǒng)的數(shù)據(jù)庫可采用分片機(jī)制以提高性能.分片技術(shù)會將網(wǎng)絡(luò)中的節(jié)點分割為多個獨(dú)立的片,每個片內(nèi)包含多個節(jié)點.片與片的數(shù)據(jù)一般存在一定的共有數(shù)據(jù),從而可以保證當(dāng)部分節(jié)點失效時,依然可以恢復(fù)全部數(shù)據(jù).而在區(qū)塊鏈系統(tǒng)中,由于節(jié)點的不可信,需要利用共識機(jī)制確保節(jié)點執(zhí)行的事務(wù)等的一致性,并能抵御惡意節(jié)點的惡意攻擊.因此,區(qū)塊鏈的分片技術(shù)要確保某一分片內(nèi)的惡意節(jié)點不能控制該分片,使其惡意攻擊行為成功.其次,為了將分片機(jī)制應(yīng)用到區(qū)塊鏈系統(tǒng)中,要確保分片環(huán)境下的共識機(jī)制的開銷遠(yuǎn)小于分片所帶來的性能的提升.最后,一般的分布式數(shù)據(jù)庫存在master 節(jié)點,來分配及協(xié)調(diào)事務(wù)的處理.而在區(qū)塊鏈系統(tǒng)中,直接利用master 節(jié)點來分配事務(wù)需要考慮到master 節(jié)點可能是惡意節(jié)點的情況.

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

1 區(qū)塊鏈的核心構(gòu)成

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

1.1 區(qū)塊結(jié)構(gòu)與事務(wù)

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

1.2 共識機(jī)制

由于區(qū)塊鏈網(wǎng)絡(luò)中節(jié)點不可信并且其要求所有節(jié)點均存儲數(shù)據(jù)的相同狀態(tài),當(dāng)對其中一個節(jié)點的數(shù)據(jù)準(zhǔn)備進(jìn)行更新時,所有節(jié)點需要對更新操作達(dá)成共識.共識協(xié)議往往基于兩種思路,分別為基于計算的共識協(xié)議和基于通訊的協(xié)議.現(xiàn)有的共識機(jī)制大部分采用以上兩種之一或者二者之間做一定的平衡[45].

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

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

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

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

1.3 UTXO與Account模型

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

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

1.4 智能合約

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

1.5 區(qū)塊鏈類型

根據(jù)節(jié)點加入或退出區(qū)塊鏈系統(tǒng)的方式,區(qū)塊鏈系統(tǒng)可分為公有鏈、聯(lián)盟鏈、私有鏈這3 類.

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

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

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

2 區(qū)塊鏈的數(shù)據(jù)存儲

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

· 一個方向為基于鍵值對的存儲模式,該模式下存儲的任一數(shù)據(jù)記錄包含一個可以確定該記錄的主鍵,并將其余部分視為該主鍵所對應(yīng)的數(shù)值進(jìn)行存儲.該模式數(shù)據(jù)結(jié)構(gòu)簡單,可以在處理大規(guī)模數(shù)據(jù)時獲得很好的性能;

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

由于區(qū)塊鏈上數(shù)據(jù)存儲的成本遠(yuǎn)高于一般數(shù)據(jù)庫,部分工作采用重新編碼、鏈上-鏈下結(jié)合等方式來減少區(qū)塊鏈數(shù)據(jù)存儲的開銷.因此,我們也將從鍵值對模型和關(guān)系數(shù)據(jù)模型兩個方向?qū)ζ溥M(jìn)行綜述,并介紹針對區(qū)塊鏈數(shù)據(jù)存儲的優(yōu)化技術(shù).表1 分別從性能、可拓展性以及技術(shù)復(fù)雜度方面,比較現(xiàn)有關(guān)于數(shù)據(jù)存儲的工作.

Table 1 Comparision of the approaches for data storage in blockchains表1 區(qū)塊鏈存儲技術(shù)的比較

2.1 基于鍵值對的數(shù)據(jù)存儲模式

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

在典型的區(qū)塊鏈系統(tǒng)中,各個節(jié)點均要存儲區(qū)塊鏈內(nèi)數(shù)據(jù)的備份.在這種情況下,數(shù)據(jù)在鏈上的存儲代價極高.同時,考慮到部分共識協(xié)議需要大量的網(wǎng)絡(luò)開銷,在數(shù)據(jù)規(guī)模極大的情況下,直接將所有數(shù)據(jù)存儲于區(qū)塊鏈中將產(chǎn)生巨大的存儲開銷和網(wǎng)絡(luò)通訊代價.因此,部分工作旨在以較小的代價提高數(shù)據(jù)存儲規(guī)模,包括分布式存儲、鏈下存儲等技術(shù).

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

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

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

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

2.2 基于關(guān)系型數(shù)據(jù)的存儲模式

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

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

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

· 在Offline 驗證方法中,采用延遲驗證方式,即:當(dāng)用戶提交驗證請求且驗證請求達(dá)到系統(tǒng)設(shè)定的參數(shù)e時,BlockchainDB 開始進(jìn)行驗證.

3 區(qū)塊鏈?zhǔn)聞?wù)處理

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

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

3.1 確保原子性的處理技術(shù)

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

為了保證事務(wù)的原子性,文獻(xiàn)[72]提出了兩類方法.

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

· 第2 類方法沒有相應(yīng)的排序節(jié)點,但是各個區(qū)塊鏈有部分節(jié)點參與跨鏈?zhǔn)聞?wù)的排序.具體而言,與第1種方法類似,首先,各個區(qū)塊鏈生成獨(dú)自的事務(wù)執(zhí)行順序;在形成順序之后,區(qū)塊鏈的節(jié)點同樣將需要參與跨鏈操作的事務(wù)以及該事務(wù)在本地區(qū)塊鏈?zhǔn)聞?wù)順序中的前一個事務(wù)的哈希值,合并為一個消息進(jìn)行廣播.與第1 種方法不同,該廣播發(fā)送到所有區(qū)塊鏈的各個參與排序的節(jié)點中.參與排序的節(jié)點利用PBFT 或Paxo 等基于投票的共識協(xié)議,確定跨鏈?zhǔn)聞?wù)產(chǎn)生的順序,并將其廣播到所有鏈的節(jié)點.各個區(qū)塊鏈依據(jù)產(chǎn)生的順序執(zhí)行事務(wù).

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

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

3.2 確保隔離性的處理技術(shù)

為了提高區(qū)塊鏈系統(tǒng)的事務(wù)處理效率,分布式系統(tǒng)中的部分并發(fā)控制技術(shù)已經(jīng)被應(yīng)用到區(qū)塊鏈系統(tǒng)中.本小節(jié)主要綜述針對事務(wù)隔離性的技術(shù).

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

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

· 在排序階段,排序服務(wù)節(jié)點接受所有提交的事務(wù)并確定事務(wù)執(zhí)行順序.默認(rèn)情況下,事務(wù)會按照提交時間的順序進(jìn)行排序.在排序結(jié)束之后,這些事務(wù)被組織成一個區(qū)塊并分發(fā)給網(wǎng)絡(luò)中的節(jié)點;

· 在驗證階段,節(jié)點按照順序確定事務(wù)是否可執(zhí)行.在該階段需驗證兩部分內(nèi)容:

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

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

· 在執(zhí)行階段,所有可行與不可行的事物均被寫入?yún)^(qū)塊中.同時,可行的事務(wù)被執(zhí)行.

常用的先排序后執(zhí)行的策略在排序之后,區(qū)塊鏈中的各個節(jié)點只能順序地執(zhí)行相應(yīng)的事務(wù).而Hyperledger Fabric 則可以利用模擬階段的結(jié)果,并發(fā)地執(zhí)行事務(wù)并保證數(shù)據(jù)的一致性,從而提高系統(tǒng)性能.針對Hyperledger Fabric 的各個階段,如表2 所示,許多工作針對不同階段提出相應(yīng)的優(yōu)化技術(shù),以提高系統(tǒng)的并發(fā)度.

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

· 首先,一個區(qū)塊中的事務(wù)默認(rèn)按照提交時間的順序進(jìn)行處理.然而,可以通過改變區(qū)塊內(nèi)事務(wù)的順序,使得原本被終止的事務(wù)在新的順序下沒有沖突,從而可以順利執(zhí)行;

· 其次,事務(wù)的處理過程需要4 個階段,而現(xiàn)有工作只能在驗證階段判斷事務(wù)是否被執(zhí)行或終止.如果可以在該階段之前判斷事務(wù)不可執(zhí)行,則可以提前將事務(wù)標(biāo)記為終止?fàn)顟B(tài),從而節(jié)省后續(xù)階段的開銷.

基于以上兩點,針對區(qū)塊內(nèi)事務(wù)的順序問題,文獻(xiàn)[75]提出了利用沖突圖的方法產(chǎn)生執(zhí)行順序的算法.具體而言,在沖突圖中,圖中的一個節(jié)點表示一個事務(wù).當(dāng)兩個事務(wù)Ti,Tj存在讀寫沖突時,相應(yīng)的事務(wù)的點之間存在一條有向邊Ti←Tj,表示Ti應(yīng)在Tj之前執(zhí)行.而一個區(qū)塊中,代表所有可執(zhí)行事務(wù)的點以及之間的邊所構(gòu)成的圖一定是沖突圖中的一個無環(huán)子圖,因而作者提出了啟發(fā)式的算法,在沖突圖中,通過查找其中最大的無環(huán)圖,進(jìn)而產(chǎn)生相應(yīng)的事務(wù)執(zhí)行順序的算法.

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

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

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

3.3 確保一致性的處理技術(shù)

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

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

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

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

4 區(qū)塊鏈查詢處理

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

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

4.1 一般查詢處理

LineageChain[84]研究區(qū)塊鏈環(huán)境下數(shù)據(jù)溯源查詢的效率問題,并支持需要數(shù)據(jù)溯源的智能合約.

LineageChain 針對每個數(shù)據(jù),賦予其初始版本號.當(dāng)一個事務(wù)對數(shù)據(jù)進(jìn)行讀寫操作時,事務(wù)的輸出可能是新的數(shù)據(jù)或者更新現(xiàn)有數(shù)據(jù)的版本.這鐘情況下,如果一個區(qū)塊內(nèi)還有不同事務(wù)時,則可以視作一個區(qū)塊的事務(wù)對前一區(qū)塊數(shù)據(jù)庫狀態(tài)進(jìn)行的修改.因此,數(shù)據(jù)版本號與區(qū)塊同步遞增.LineageChain 將這種遞增關(guān)系建模成為一個無環(huán)圖.當(dāng)需要溯源查詢時,利用無環(huán)圖中點的拓?fù)湫蜻M(jìn)行搜索.

與文獻(xiàn)[84]需額外構(gòu)建圖結(jié)構(gòu)不同,文獻(xiàn)[85]研究利用智能合約確定數(shù)據(jù)的關(guān)系,并對數(shù)據(jù)進(jìn)行溯源查詢.當(dāng)一個數(shù)據(jù)的創(chuàng)建者創(chuàng)建一個文檔時,創(chuàng)建者可在區(qū)塊鏈中部署一個智能合約.該合約的功能包括更改數(shù)據(jù)擁有者、添加可訪問用戶、進(jìn)行溯源查詢等.同時,該合約要求所有對指定文件的更改需經(jīng)過投票過程.參與投票的用戶由數(shù)據(jù)擁有者確定.對數(shù)據(jù)的任意一次更改需至少半數(shù)以上的用戶投票同意才可進(jìn)行.在這種環(huán)境下,惡意的用戶若對數(shù)據(jù)進(jìn)行惡意篡改,需控制半數(shù)以上參與投票的用戶.同時,由于所有的修改均利用部署的智能合約,因而對數(shù)據(jù)的溯源查詢轉(zhuǎn)化為對智能合約調(diào)用的查詢.

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

4.2 可信查詢處理

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

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

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

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

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

5 區(qū)塊鏈可擴(kuò)展性

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

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

5.1 基于分片的區(qū)塊鏈系統(tǒng)

為了提高吞吐量,將數(shù)據(jù)庫中的分片技術(shù)引入到區(qū)塊鏈系統(tǒng)中是研究的一個熱點問題[104].表4 總結(jié)了部分區(qū)塊鏈可擴(kuò)展性的特點.

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

Table 4 Comparision of the scalability of blockchains表4 區(qū)塊鏈可擴(kuò)展性比較

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

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

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

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

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

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

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

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

5.2 區(qū)塊鏈的鏈下事務(wù)處理

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

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

而與Lightning,Raiden 等網(wǎng)絡(luò)直接對賬戶內(nèi)的金額進(jìn)行交易不同,文獻(xiàn)[116]提出了Sprites,這一利用智能合約確保事務(wù)執(zhí)行的網(wǎng)絡(luò).通過智能合約,當(dāng)多個事務(wù)存在線性關(guān)系時,Sprites 可以部分地并行執(zhí)行多個事務(wù),從而提高鏈下交易的執(zhí)行效率.

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

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

6 區(qū)塊鏈數(shù)據(jù)管理的未來研究趨勢

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

· 區(qū)塊鏈內(nèi)數(shù)據(jù)的隱私保護(hù)技術(shù)

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

· 鏈間事務(wù)處理優(yōu)化技術(shù)

現(xiàn)有的多數(shù)工作考慮單一區(qū)塊鏈,并對單一區(qū)塊鏈下的事務(wù)處理等問題提出了高效的算法.但是當(dāng)一個事務(wù)需要訪問多個區(qū)塊鏈時,會產(chǎn)生諸多問題,包括如何保證數(shù)據(jù)的一致性、高效的并發(fā)控制算法等.文獻(xiàn)[72]考慮了多鏈情況下的視圖以及驗證問題.現(xiàn)有的工作多考慮如何保證跨鏈?zhǔn)聞?wù)一致性的問題.與單鏈相比,較少工作考慮跨鏈?zhǔn)聞?wù)處理的效率.在跨鏈?zhǔn)聞?wù)的執(zhí)行過程中,可能會對一條鏈的數(shù)據(jù)進(jìn)行加鎖等操作,這種操作將會影響與該鏈相關(guān)的事務(wù)執(zhí)行.因此,僅僅考慮單鏈的事務(wù)或者僅考慮跨鏈的事務(wù)都可能降低整個系統(tǒng)的吞吐量.對鏈間事務(wù)處理效率問題的研究將著眼于:如何設(shè)計針對多鏈環(huán)境下的事務(wù)處理優(yōu)化,以達(dá)到在保證一致性的同時,提高吞吐量的目標(biāo).

· 面向智能合約的事務(wù)處理優(yōu)化技術(shù)

區(qū)塊鏈所部署的智能合約可以對數(shù)據(jù)進(jìn)行添加、修改等操作.現(xiàn)有的工作往往將智能合約視為一個事務(wù)處理.但是由于智能合約執(zhí)行的復(fù)雜度并不一致,且一個智能合約可以調(diào)用其他智能合約,僅將一個智能合約視為一個事務(wù)并不能完全衡量系統(tǒng)的性能優(yōu)劣.因此,需要一個更適用于區(qū)塊鏈的衡量標(biāo)準(zhǔn),以比較不同區(qū)塊鏈系統(tǒng)的性能.該標(biāo)準(zhǔn)的難點在于,如何設(shè)計基本的語義以及如何將智能合約與智能合約的嵌套關(guān)系同時考慮在性能衡量的指標(biāo)中.

7 總結(jié)

我們從區(qū)塊鏈數(shù)據(jù)存儲、區(qū)塊鏈?zhǔn)聞?wù)處理、區(qū)塊鏈查詢處理、區(qū)塊鏈可擴(kuò)展性等幾個方面,對區(qū)塊鏈環(huán)境下的數(shù)據(jù)管理相關(guān)研究工作進(jìn)行了較為系統(tǒng)的綜述,分析了各種區(qū)塊鏈數(shù)據(jù)管理方法的優(yōu)點與不足,最后介紹了區(qū)塊鏈的未來研究趨勢.從數(shù)據(jù)管理的角度,區(qū)塊鏈的現(xiàn)有系統(tǒng)與方法仍然有非常多的工作需要進(jìn)行.并且在一個不可信場景下構(gòu)造一個可信計算環(huán)境,仍然具有非常巨大的應(yīng)用前景,因此,通過本文的綜述與介紹,也希望有更多的研究者,尤其是數(shù)據(jù)庫研究者,更多地開展區(qū)塊鏈數(shù)據(jù)管理研究工作.