基于時序索引的可編輯區塊鏈模型研究

龐俊，劉晨，郝琨，于明鶴，信俊昌，姜承揚

1.武漢科技大學 計算機科學與技術學院，武漢430070

2.智能信息處理與實時工業系統湖北省重點實驗室，武漢430070

3.東北大學 計算機科學與工程學院，沈陽110169

4.東北大學 軟件學院，沈陽110169

區塊鏈是一個分布式共享的賬本數據庫。它可以在互不可信的環境中驗證并永久地記錄數據。這一特性為金融、政治和社會治理等領域提供了新的數據存儲模式[1]。區塊鏈中存在因人為操作失誤或惡意提交產生的非法交易，這些非法交易可借助區塊鏈的透明性和不可篡改性產生永久性的負面影響。例如：惡意節點將不實謠言信息上鏈，經過共識等過程，這些信息最終永久存儲在區塊鏈上，所有節點都能訪問從而受到這些不良信息的危害[2]。區塊鏈的編輯操作是指在達成節點共識之后對歷史交易本身進行修改或刪除，從而減少或消除非法信息的負面影響。現有相關研究還包括把區塊鏈數據遷移至外部數據庫進行分析處理操作[3]，但并不會改變鏈上數據，因此不屬于區塊鏈可編輯的范疇。

可編輯區塊鏈相關研究很多，根據是否對原始數據進行編輯分為兩大類：物理編輯和邏輯編輯。物理編輯一般采用密碼學工具，對區塊原始數據進行替換并保證哈希鏈路完整，具有效率較高且不會產生冗余數據的優點。但存在提高中心化程度與密鑰泄露的問題，并且直接替換會導致原有的非法交易無從考證，使得掌握密鑰的人可隨意抹除對其不利的存證。邏輯編輯不改變原始數據，一般采用追加交易等方法，通過改變追加交易后數據的訪問方式來實現“邏輯”編輯。該種方案保留了錯誤交易記錄以供考證，但沒有將錯誤交易與有效交易進行隔離，因此缺乏安全訪問機制。此外，交易類型數據在區塊鏈中表現為上下文相關和高度依賴的交易鏈條，如果對其中某一個交易進行編輯，可能導致以該交易為頂點的交易子樹中原本合法的交易無法正常執行，最終導致交易失效。除文獻[4]針對UTXO（unspent transaction output）模型進行了簡單探討之外，其余現有相關研究均假設數據編輯不涉及上下文相關的交易類型數據。因此，本文提出一種屬于邏輯編輯的可編輯區塊鏈模型。首先，以一般存證數據為例，為數據增加時序屬性，實現了安全的查詢接口以訪問合法交易，同時保留了錯誤數據存證。在此基礎上，針對交易類型數據的編輯，重構以目標交易為根節點的交易樹，保證了后續交易的一致性和有效性。

Hyperledger Fabric 是一個使用賬戶模型的聯盟鏈平臺。不同于使用UTXO 模型的比特幣[5]等公有鏈，Fabric[6]不僅向用戶提供了豐富的查詢接口，而且支持智能合約，實現多種場景下的應用。不失一般性，本文采用Fabric 作為底層平臺，提出可編輯區塊鏈模型，該模型的思想同樣適用于其他使用賬戶模型的區塊鏈。

本文的主要貢獻如下：

（1）對存證與交易類型的數據分別重新設計了新的底層數據結構，增加了時序屬性并作為索引，提出了基于時序索引的提交、編輯和查詢算法。在實現交易邏輯編輯的同時，保留了錯誤交易存證，并提供了安全的訪問接口以查詢有效交易。

（2）分析了上下文相關的交易級編輯對后續交易的影響，并針對交易類型數據進行了數據結構和相關算法的改進，在編輯交易時重構以該交易為根節點的交易子樹，保證了交易鏈條的一致性。

（3）通過對兩種類型的數據分別編寫智能合約進行實驗，證明了本文提出的可編輯區塊鏈模型可實現對目前所有類型數據的編輯，同時保證了系統的基礎性能。

1 相關工作

本章首先介紹了可編輯區塊鏈研究現狀，然后概述了Fabric區塊鏈模型。

1.1 可編輯區塊鏈研究現狀

現有可編輯區塊鏈相關研究可分為兩大類：物理編輯和邏輯編輯。

1.1.1 物理編輯

物理編輯的核心思想是：在不破壞區塊哈希鏈路完整性的前提下，直接替換區塊數據。Ateniese等人最先提出了利用變色龍哈希函數[7]替換區塊數據的方案[8]。在改變區塊內容的同時保持區塊頭部哈希不變，從而維持哈希鏈路的完整性，實現對區塊鏈的編輯。此方案會導致一定程度的中心化，且陷門本身可能會泄露，造成安全隱患。李佩麗等人對其進行了改進，利用秘密共享方案[9]，將陷門拆分為多份并分發給指定的信任節點，一定程度上解決了上述中心化問題。任艷麗等人利用陷門單項函數，引入機動因子，重構了區塊簽名子塊，在超過閾值節點數同意的情況下便可修改區塊數據[10]。不同于基于密碼學的方案，Deuber 等人提出了雙哈希鏈模型[11]，在改變區塊內容的同時保留原區塊哈希，即同時存在兩條哈希鏈，保證至少一條哈希鏈路成立。

物理編輯方案雖然實現了對區塊鏈數據的編輯，但只支持區塊粒度的編輯，無法定位到區塊中的具體數據。并且錯誤數據一旦被修改，便無從考證。此外，物理編輯方案均沒有考慮對上下文強相關和高度依賴的交易類型數據進行編輯。

1.1.2 邏輯編輯

邏輯編輯的相關研究較少。Marsalek 等人提出了雙區塊鏈模式（數據鏈中存儲原始的區塊數據，修正鏈存儲修正后的區塊數據）[12]，以兩條鏈互補的方式實現對區塊數據的編輯。該方案雖保留了錯誤數據存證，但同樣只以區塊為粒度進行編輯，沒有考慮交易修改后對后續交易的影響。Puddu 等人提出了可變交易的概念（將原始標準交易結構改為交易集合的形式）[4]，通過將后續追加交易進入集合，并指定一個活躍交易作為有效交易，從而實現編輯操作。該方案雖然保留了錯誤存證，但所有錯誤歷史記錄與有效數據均包含在集合中，缺乏安全的訪問機制，難以隱藏不良信息。雖考慮了上下文強相關的交易類型數據的編輯，但僅通過設置約束規則，使交易接收方拒絕接收使用可變交易進行的轉賬，從而在源頭杜絕后續交易可能出現的不一致性，并未從實際意義上實現對交易類型數據的編輯。本文提出的基于時序索引的可編輯區塊鏈模型，在保存錯誤交易存證的基礎上，不但為用戶提供了安全的訪問接口，還重構交易子樹，保證了交易子樹中所交易的貨幣數量守恒，解決了后續交易失效的問題。

1.2 Fabric區塊鏈模型

Fabric 網絡中的參與者都共同保留和維護一條完整的區塊鏈，包括賬本文件和多個數據庫。本節只介紹與本文工作密切相關的賬本文件和狀態數據庫。下文以車管所為車輛設置牌照為例進行解釋。如在時間t時將品牌為Benz所有者有Tom的車輛設置牌照為CX8789，交易

圖1 提交成功后的相應更新Fig.1 Update after submission

提交成功后，客戶端可通過智能合約訪問狀態數據庫中唯一鍵K的最新狀態。但狀態數據庫中僅保存鍵值數據，若想查詢完整的交易信息（如查詢交易發起方和具體參數），則需根據歷史索引查詢到唯一鍵K相關歷史交易所在的區塊，并反序列化區塊，從中提取出具體的完整交易內容[13]。

區塊中所有交易共同進行哈希運算得到“Merkle根”字段以此來驗證區塊體中的交易是否被篡改，而區塊頭中的“前一區塊哈希”字段讓區塊與區塊之間環環相扣，任何歷史區塊內容的改變都引發后續所有區塊哈希值的連鎖改變[14]。因此，區塊鏈不可篡改的特性是指交易數據本身一旦上鏈則不可更改以及唯一鍵K對應數據的更改歷史不可改，但是支持通過提交交易的方式使數據從舊版本更新到新的版本。但這種記錄數據的方式在某些場景下會造成一定的危害。因此，需要在保證區塊鏈“不可篡改”的前提下，實現對歷史記錄的編輯。

2 存證數據的可編輯區塊鏈模型

本章針對存證類型數據，提出了一種基于時序索引的可編輯區塊鏈模型，其流程如圖2所示。客戶端發送提交交易或編輯交易的請求給背書節點進行模擬執行，然后把模擬執行結果發送給排序節點進行排序，根據排序結果為每個交易設置時序屬性[15]。然后將打包后的區塊發送給提交節點進行驗證并提交，獲得最新的帶有時序索引的區塊賬本。最后根據時序索引查詢歷史有效交易。下文分別介紹本文提出的數據結構、交易提交、交易編輯和歷史查詢算法。

圖2 可編輯區塊鏈模型流程圖Fig.2 Process of editable blockchain model

2.1 數據結構

新數據結構在原有交易結構基礎上，為每個交易新增一個時序屬性，即復合字段：Start{S.blockid,S.txid}。S.blockid 和S.txid 分別表示該交易的前置交易所在區塊號與交易在區塊內的序號。前置交易是指與該交易擁有相同唯一鍵的上一個歷史交易。此外，還為狀態數據庫在原有key-value結構的value域中同樣增添兩個字段From{F.blockid，F.txid}和To{T.blockid，T.txid}。F.blockid、F.txid、T.blockid 和T.txid分別表示最新狀態值所在交易對應的區塊號和交易序號以及該唯一鍵在第T.blockid 號區塊的第T.txid個交易被刪除。

若交易包含的唯一鍵是第一次出現，則將Start置為?，因為區塊鏈賬本中沒有唯一鍵相同的歷史交易。屬性To設置為∞，表示該狀態依然有效，尚未刪除。繼續以上一章車輛牌照存證為例，假設CX8789 作為唯一鍵在區塊鏈中第一次出現，且該信息被正確存儲在區塊鏈中第5 個區塊的第10 個交易中。K與V對應的含義與上文相同。區塊賬本和狀態數據庫如圖3所示（方便起見圖中省略了交易序號）。

圖3 可編輯模型數據插入Fig.3 Insert of editable model data

當該車牌在時間t1時更換為品牌為BMW 的車輛，鍵值對

圖4 可編輯模型數據更新Fig.4 Update of editable model data

當車輛報廢，車牌需要注銷時，需要刪除唯一鍵CX8789。該操作與更新操作類似，以提交交易的形式進行：唯一鍵K不變，相應的V賦予空值，即該鍵對應的最新狀態被刪除；Start 的設置與更新操作相同。狀態數據庫中的To設置為與From相同的值，即若查詢到狀態數據庫中某個唯一鍵的復合字段To含有具體的數值而非∞時，認為該唯一鍵被刪除，但仍可以查詢到所有的歷史狀態。

2.2 交易操作與查詢算法

2.2.1 交易提交

交易提交指采用提交交易的方式為賬本添加新的唯一鍵或對已存在的唯一鍵進行狀態更新或“刪除”。由于數據結構新增了時序屬性，交易提交算法需重新設計。算法偽代碼如算法1所示。

算法1交易提交

輸入：客戶端提供的唯一鍵key，對應狀態的值value，方法method。

算法1 第1～4 行判斷狀態數據庫中是否存在對應唯一鍵key，如沒有則將Start 置為?；否則，按要求設置相應值。第5～6行創建寫集并賦值，然后提交排序。第7～12行根據交易排序設置寫集中的時序屬性。第13 行根據寫集更新世界狀態，提交交易并更新賬本。

2.2.2 交易編輯

交易編輯是對已經上鏈的歷史交易進行編輯。交易編輯與交易提交一樣遵循區塊鏈系統中的共識，即得到足夠數量節點的驗證并背書后才會被正確執行。此處不考慮再次惡意和錯誤提交的情況。編輯操作包括對歷史交易本身進行修改或刪除，其中“刪除”操作可看作將目標歷史交易的內容修改為空。交易編輯算法偽代碼如算法2所示。

算法2交易編輯

輸入：歷史交易的輸入參數historyinput，修改交易的唯一鍵key，數據值value。

算法2第1～3行獲取key對應最新狀態所在的交易；第4～6行判斷該交易包含的輸入與待修改交易的輸入是否匹配，如不匹配則不斷地根據交易中的Start 字段獲取前一個有效交易，并把索引路徑中的交易加入交易池；第7～9行表示當匹配到被修改交易后，獲取前置交易的時序屬性作為新交易的Start，并依次執行算法1交易提交步驟，將修改后的交易與目標前置交易鏈接起來；第10～11行按順序提交交易池中的交易，保證正確的歷史交易順序。

2.2.3 歷史交易查詢

原始Fabric 歷史交易查詢返回與唯一鍵相關的所有交易，并不區分錯誤交易與合法交易。使用狀態數據庫中的時序屬性From與交易結構中的時序屬性Start把區塊鏈中每個唯一鍵對應的歷史交易鏈接成一條倒置鏈表，可跳過錯誤交易和無效交易，返回合法交易集合，實現有效的歷史查詢。該查詢的邏輯與算法2 中索引目標交易類似。不同之處：通過Start 是否為?來判斷是否完成歷史查詢，并返回交易集合。限于篇幅不再重復解釋。仍保留Fabric 原有歷史查詢接口，用于查詢錯誤交易存證。

3 交易數據的可編輯區塊鏈模型

與存證類型數據不同，交易類型數據具有強上下文相關性和高度依賴性，修改歷史交易可能會導致后續交易失效。

3.1 問題與解決方案

3.1.1 不適用的交易結構

針對存證數據設計的數據結構并不適用于交易轉賬場景。存證數據的一條交易中只涉及一個唯一鍵狀態的改動，交易轉賬的場景下，由于存在發送方和接收方兩個賬戶，一條交易對應兩個唯一鍵狀態的改變。此外，交易轉賬中的賬戶一旦建立則被認為持久存在。因此，可編輯區塊鏈模型中用于判斷唯一鍵是否被刪除的字段To 失去了作用，相關數據結構需要重新設計。

解決方案：區塊賬本中每個交易新增兩個復合字段SAI{S.blockid，S.txid}和RAI{R.blockid，R.txid}，SAI（RAI）記錄交易發送方（接收方）對應前置交易所在區塊與交易序號，賬戶首次交易則對應設置為?。此外，狀態數據庫value 域添加一個字段AI，記錄該唯一鍵對應賬戶的最新一筆轉賬交易所在的區塊號和交易序號。

3.1.2 余額不足導致的無效交易

不同于比特幣使用UTXO 模型隱式地計算賬戶余額，Fabric每次轉賬交易的提交都會直接更新賬戶余額。因此，修改某個歷史交易可能導致后續多個交易失效。例如，已知順序發生并寫入區塊鏈的3筆交易：（1）(A→B,50)；（2）(B→C,100)；（3）(C→D,150)，假設交易（1）為錯誤交易，修改為(A→B,0)，則原本可正確執行的交易（2）因賬戶B余額不足執行失敗。交易（3）同理執行失敗，賬戶C、D同樣面臨無法執行后續交易的危險。最壞的情況下，區塊鏈中全部交易都受影響。因此，必須要保證交易修改后不會導致后續交易的失效。

解決方案：如果每次轉賬均同時遵循下述的3個約束條件，即可保證修改目標交易不會影響后續交易的正確執行：（1）發送方在交易時只能花費固定余額進行轉賬；（2）接收方基于轉賬得到的貨幣將被存放進臨時余額，在時間Δt之后，臨時余額被轉換成為固定余額；（3）只有在提交交易后的Δt時間段內，才可以對該交易進行修改。緩沖時間Δt的取值根據實際情況進行設置。

因此，將余額改為{balance,temporaryset}的形式。balance為固定余額，temporaryset={b1,b2,…,bn}為臨時余額集合。bi=(temporaryunits,t),temporaryunits和t分別代表著臨時交易的貨幣數額與交易執行的時間戳。交易合法性被驗證通過后，在執行轉賬操作前會將發送方與接收方的臨時余額集合temporaryset里所有滿足時間要求t+Δt≤time.now的temporaryunits更新至固定余額中，以保證實時正確的賬戶余額狀態完成交易。

3.2 操作與查詢算法

3.2.1 交易提交

針對交易類型數據的提交算法偽代碼如算法3所示。

算法3交易提交

輸入：發送方A，接收方B，金額units。

算法3 第1～6 行首先根據狀態數據庫求出本條交易執行前發送方與接收方的固定余額與臨時余額集合；第7～8 行計算出交易執行后賬戶的寫集狀態；第9～12 行判斷是否是賬戶的第一次交易，如果是則將對應賬戶的時序屬性置為?，否則根據狀態數據庫設置為前置交易的時序索引；第13 行對交易進行排序并打包入塊；第14～15行根據本交易所在區塊以及交易序號設置狀態數據庫中的AI并根據寫集更新狀態數據庫，提交交易到區塊鏈賬本。

3.2.2 交易編輯

交易類型數據的編輯涉及的后繼交易包括所有狀態受影響的交易。對歷史交易的“刪除”可看作將交易金額修改為0。算法偽代碼如算法4所示。

算法4交易編輯

輸入：編輯的目標歷史交易中包含的發送方A，接收方B，金額units以及要修改的金額units1。

算法4 第1～6 行根據輸入參數定位目標歷史交易；第7 行判斷是否滿足交易修改條件；第8 行創建新交易trans并設置SAI 與RAI；第9～13 行從目標交易所在區塊的下一區塊開始遍歷至最新區塊，將受影響的交易放入交易池；第14～16行表示更新關聯賬戶集合，并將賬戶恢復至前置交易對應的狀態；第17行表示將trans根據輸入的units1更新寫集并提交交易更新狀態數據庫；第18～19行將交易池中的交易按順序重新提交，重構交易樹。

3.2.3 歷史交易查詢

除以下區別之外，交易類型數據的歷史交易查詢思想與存證類型數據基本相同：存證類型數據由交易中的Start與狀態數據庫中的From進行索引；交易類型數據由賬戶對應的SAI 或RAI 以及狀態數據庫中的AI進行索引。因此交易類型數據的歷史交易查詢算法不再贅述。同樣保留Fabric 原有的歷史查詢接口，用于查詢錯誤交易存證。

4 性能分析

本章在模擬數據集上進行了大量實驗，對比了本文提出的可編輯區塊鏈模型和Fabric的吞吐量、存儲空間開銷和歷史查詢效率，驗證了其可以在保證系統性能的基礎上實現對歷史數據的編輯。

4.1 數據集和實驗環境

采用Fabric SDK 循環生成模擬數據集，每個區塊中交易數量設置為100。（1）在存證數據場景下，每個交易對應的唯一鍵key分別從0到99，對應的值域為key+區塊號。（2）在交易數據場景下，建立200個賬戶，使用隨機轉賬的形式構建模擬交易進行實驗。

在CPU3.2 GHz、64 GB RAM、2 TB磁盤空間的服務器上，使用虛擬機搭建了4個操作系統為Ubuntu16.04的普通節點和1個排序節點。Fabric 版本為1.1，底層數據庫使用LevelDB。baseline 方法為Fabric 原始提交與歷史查詢算法。本文主要研究區塊鏈數據的可編輯和歷史交易的回溯查詢，因此實驗均使用Fabric默認共識，并報道10次實驗的平均結果。

4.2 實驗結果及分析

本節對比本文提出的可編輯區塊鏈模型與Fabric的系統性能。

（1）交易吞吐量測試

分別在存證和交易數據上比較了改進后的可編輯區塊鏈模型與原始區塊鏈的交易吞吐量，其實驗結果如圖5 所示。使用4 個節點同時發送10 000 條交易進行排序出塊，記錄數據從被創建到打包區塊被持久化存儲到賬本文件的總用時，從而計算出每秒的有效交易數[16]。

圖5 交易吞吐量對比Fig.5 Comparison of throughput

圖5表明在兩種數據類型下，可編輯區塊鏈模型均與原始Fabric 具有相近的吞吐量。在存證類型數據下，可編輯模型的吞吐量比原始Fabric低約4%，而在交易數據下則約為8%。因為可編輯區塊鏈在交易提交過程中增加了設置時序屬性的操作；對于交易類型數據，還需遍歷臨時余額集合，實時計算固定余額，因此花費了更多時間，從而降低了交易吞吐量。雖然改進的區塊鏈模型吞吐量略低，但屬于可接受的范圍。

（2）存儲空間開銷對比

分別比較了搭載存證和交易類型數據時，可編輯區塊鏈模型與原始Fabric 在不同數據量下所需的存儲空間大小。實驗結果如圖6和圖7所示。

圖6 表明本文提出的可編輯區塊鏈模型在存儲存證數據的條件下所需存儲空間與原始Fabric 幾乎相同，這是由于交易本身與狀態數據庫中額外的時序數據對整體影響較小。

圖6 存證數據存儲對比Fig.6 Comparison of depository data storage

圖7顯示當交易數據達到一定數量后，可編輯區塊鏈模型所需的存儲空間稍大。因為隨著交易數據的進一步增加，可編輯區塊鏈模型的交易與狀態數據庫中臨時余額集合持續增大，需要更多的存儲空間。綜上，可編輯區塊鏈模型對存儲空間的影響較小。

圖7 交易數據存儲對比Fig.7 Comparison of trade data storage

（3）歷史溯源查詢時間對比

雖然本文對兩種不同的數據類型提出了歷史交易編輯算法，但對于歷史數據溯源效率而言，兩種數據類型并無差異，都是基于時序屬性進行鏈式索引。因此以存證數據為例，對比改進后的可編輯區塊鏈模型與原始Fabric 的溯源時間。即從最新版本的數據溯源查詢到最初版本的數據所花費的時間。

實驗結果如圖8所示，通過時序屬性響應歷史溯源查詢的時間比原始Fabric 通過歷史索引數據庫的查詢響應時間更短，并且隨著唯一鍵更新次數的增加，該優勢愈發明顯。這是由于可編輯模型可以在解析歷史數據的同時獲取到索引信息，而原始方法需要遍歷historyDB進行索引并解析。

圖8 歷史查詢時間對比Fig.8 Comparison of historical query time

（4）更新次數對歷史交易查詢時間的影響

本實驗測試了歷史交易更新次數對歷史交易查詢時間的影響。因為修改歷史交易前需先定位目標歷史交易，定位所花費的時間受目標歷史交易到最新交易之間更新次數的影響。實驗結果如圖9所示：隨著更新次數的增加，查詢時間呈線性增長趨勢；查詢所需時間較少，處于毫秒級。綜上，本文提出的可編輯區塊鏈模型在進行歷史交易查詢時能較好地適應交易更新次數的變化。

圖9 更新次數對查詢時間的影響Fig.9 Impact of update number on query time

5 結束語

本文針對存證與交易類型數據分別重新設計了底層數據結構，提出了新的提交、編輯和查詢算法，在保留錯誤交易存證的基礎上，提供了安全的訪問接口以查詢有效交易。同時，針對交易類型數據進行改進，解決了后續交易失效的問題，實現了對交易類型數據的編輯操作。模擬數據集上的大量實驗結果表明，本文提出的區塊鏈可編輯模型在交易吞吐量和存儲空間開銷方面具有與原始模型相近的表現，并具有更高的歷史溯源查詢效率。針對交易編輯時會產生重復交易的缺陷，下一步擬挑選合適的刪除策略將其剪枝，只保留交易數據的哈希值用于驗證，節約存儲空間。