DorChain：利用休眠幣提高交易驗證效率

潘森杉，徐臘梅

(1.江蘇省工業網絡安全技術重點實驗室，江蘇 鎮江 212013；2.江蘇大學 計算機科學與通信工程學院，江蘇 鎮江 212013)

自中本聰[1](Satoshi Nakamoto)在2008年提出區塊鏈的概念以來，以其去中心化和分布式存儲等特點吸引了許多專家和研究人員。由于其驗證程序可以保留所有分類賬數據的安全性，它在許多領域也具有廣闊的應用前景，包括物聯網環境中的數據共享[2]、車輛社交網絡[3]、醫療[4-5]、教育[6]、邊緣計算[7]和數據驗證搜索[8-9]等。但是，每個驗證者都需要保留所有分類賬數據，這對于普通用戶節點而言，存儲負擔非常大。從2008年到2020年，區塊鏈上新生產數據的日增長率達到0.135 3 GB。如果根據比特幣鏈中數據的增長率進行估算，在過去的兩年中，整個比特幣網絡的數據量將超過6 TB。針對這種不斷增長的數據情況以及所帶來的驗證負擔，許多研究人員提出了相關驗證方法[10]。

Boneh方案[11]：提出了兩種解決方案。一種是基于UTXO的無狀態區塊鏈技術，另一種是應用于IOP(交互式oracle證明)的矢量承諾技術。主要討論無狀態區塊鏈。Boneh主要使用未知階群構造RSA累加器，然后在此基礎上實現成員證明和非成員證明的批處理技術。未知階群的使用在證明大小和證明傳輸方面具有明顯的優勢，尤其是批量更新和聚合成員證明技術。

Edrax方案[12]：主要提出兩個示例。一種是基于UTXO的比特幣的貨幣類型，另一種是基于賬戶的以太坊的貨幣類型。仍然基于UTXO模型介紹比特幣。作者主要使用稀疏Merkle樹的技術來實現它，其中每個UTXO都采用[鍵，值]的形式。主要原理可以概括如下：整個樹中都有最新的證明，用過的TXO(交易輸出)在樹中用null表示。當UTXO處于事務流通中時，可以將此事務添加到最新事務的右側，然后計算和更新最新證明。可以理解為以這種方式，最右邊的交易證明是最新證明，可用于更新或驗證。

MiniChain方案[13]：使用STXO(已花費的交易輸出)代替UTXO，從另一個角度看問題，將用過的TXO放在一個集合中以形成STXO承諾。作者主要提出了兩種方案：一種是MiniChain +同時包含STXO和TXO承諾，另一種是僅STXO承諾的MiniChain-方案。另一方面，作者還提出了STXO緩存機制，該機制可有效減少狀態更改引起的重新計算量。 STXO承諾使用RSA累加器技術將大量STXO映射到質數，然后形成一個簡短的承諾過程，并且沒有刪除操作的計算量。TXO的承諾主要是使用MMR技術進行構造。與Boneh的工作相比，作者將累加器更新的復雜性從O(m2)降低到O(m)，其中m是區塊中的事務數。

Ethanos方案[14]：主要討論定期清理不活動賬戶節點的方案。Ethanos解決方案主要基于以太坊賬戶模型設計。如果賬戶節點狀態更改，則運行恢復事務以恢復其狀態。建議定期清理不活動的賬戶節點，而不下載舊的事務以節省啟動成本。因此，該賬戶節點可以完成在其自己的設備上驗證數據的任務。此解決方案可以將賬戶狀態的大小減少一半。

1 系統細節

在DorChain中，小于18個月活躍的UTXO稱為ATXO，大于18個月活躍的UTXO稱為DTXO。首先，將區塊鏈中的所有UTXO初始化為休眠狀態(新開采的硬幣設置為活躍狀態)，存儲在集合DTXO中，稱為D。如果UTXO處于活躍狀態，從集合D中刪除UTXO存儲在集合ATXO中，稱為A。其次，使用MMR技術實例化A中的UTXO。同時構造休眠證明，使用變量DT來判斷休眠時間。最后，D中的UTXO使用RSA累加器技術來實例化。該種設計方式的優勢在于將休眠UTXO獨立，僅利用MMR技術對活躍UTXO實例化，在引入最低區塊頭數據的同時，只需要提供存在性證明，即可達到驗證幣真偽的目的，降低計算開銷，大大提高驗證效率。接下來介紹DorChain的主要構成：DTXO承諾，AMR (ActiveMerkleRoot)，休眠證明的構造，驗證，更新以及存儲等方法。

1.1 在RSA累加器中實例化的DTXO承諾

將區塊鏈中的所有UTXO初始化為休眠狀態，即DTXO。首先使用HashToPrime[15-16]函數將DTXO集合中的元素映射到質數，然后使用RSA累加器[15]將集合DTXO哈希化為簡潔且恒定的承諾(DTXO承諾)。在使用累加器計算承諾之前，利用哈希函數將集合中的DTXO映射到素數再計算，主要是為了避免沖突。基本結構如圖1所示。

圖1 DTXO承諾構造過程

算法2DUpdate：在檢查點更新DTXO_C。如果參數DT為18個月，則需要將DTXO添加到DTXO集合中。如果在該時期內硬幣從休眠狀態變為活躍狀態，則可以通過刪除操作將其從集合D中刪除。更新的DTXO_C記錄在標記的DTXO上。然后可以使用算法1來更新DTXO_C。具體算法如圖2所示。

1.2 在MMR中實例化的AMR

在該解決方案中，區塊鏈中的所有UTXO被視為處于休眠狀態(新開采的硬幣除外)。因此，當UTXO即將變為活躍狀態時，將此UTXO視為集合D中的刪除操作。已刪除的DTXO被標記為“活躍”，并且用戶在UTXO上記錄了最新刪除后的DTXO_C，將刪除的DTXO存儲在代表活躍UTXO集合A中。在A集合中，主要使用MMR[17-18]技術來構造AMR。

筆者以m塊到n塊為例，詳細描述其構造方案。Bm記錄為區塊m，此塊中有t個ATXO，然后使用這t個ATXO作為葉子來構造MMR，最終可以得到root0(此時記錄root0的高度)，并記錄為Rm和存儲在區塊Bm中。區塊m+1表示為Bm+1，該塊中的q個ATXO繼續將數據追加到前一個區塊的山中的右邊。當該區塊的哈希值的高度與前一個區塊root0記錄的高度一致時，與root0一起進行哈希，然后后續的ATXO繼續以僅追加的形式向后哈希。如果該區塊的哈希值的高度與前一個塊root0記錄的高度不一致，則使用裝袋方法輸入哈希以獲取root1，其記錄為Rm+1。當它是最新的塊時，AMR反映最新的ATXO的狀態。AMR可用作ATXO的驗證基礎。

1.3 狀態轉換

在這一部分中，主要介紹UTXO在休眠狀態和活躍狀態之間切換的詳細操作流程。

休眠到活躍狀態：在DorChain中，無論是正常區塊還是檢查點，UTXO都可以隨時從休眠狀態更改為活躍狀態。可以在提供UTXO的AMP的前提下隨時執行Delete操作，將已刪除的UTXO標記為“活躍”，最新的DTXO_C也記錄在UTXO上并在整個網絡上廣播以進行驗證。在檢查點時，最新標記“活躍” UTXO攜帶的DTXO_C是刪除操作的最新狀態。對于這種狀態的驗證方法，在DorChain中設計了礦工，以比較基于標記的UTXO在Boneh方案中使用BatchDelete算法計算的結果，如果它們一致，則是正確的。

活躍到休眠狀態：在DorChain中，僅在檢查點對DT為18個月的UTXO執行加法操作。添加操作發生后，UTXO被標記為“休眠”狀態，Boneh方案中的BatchAdd算法用于添加最新的“活躍”狀態的 UTXO，且該UTXO攜帶最新的狀態DTXO_C，此時更新的DTXO_C是最新狀態。具體操作如圖3所示。

1.4 休眠證明的創建、驗證、更新以及存儲

假設ATXO需要在一個時期內從活躍狀態再次變為休眠狀態，則單個UTXO的休眠證明構造參數為：休眠硬幣(DTXO)，DTXO_C(DTXO承諾)，AMP(ActiveMerkleProof)和DT(休眠時間)，其中AMP是A集合中ATXO利用MMR構造的Merkle證明記錄，而DT是記錄硬幣的休眠時間。AMP可以幫助證明硬幣是真實的而不是偽造的，并且當DT達到18個月時，認為該硬幣再次進入休眠狀態，并且可以使用添加操作將其添加到下一個檢查點設置的DTXO集合中。因此，休眠證明不僅可以證明硬幣的存在，而且是可以確定UTXO再次進入休眠狀態的條件。休眠證明的功能如圖4所示。

圖4 休眠證明的功能圖

在詳細介紹休眠證明之前，首先給出一個例子來解釋AMP的構造方法。以下面的圖5為例來構造ATXO 15的Merkle證明。

圖5 AMP示例圖(最底層數字表示葉子節點，依次往上數字為哈希結果在示例中有4個小的山峰，峰點分別為14、21、24、25)

具體創建方法如下：① 創建從葉子節點15到山21的Merkle證明，證明為{16，20}。② 袋裝右邊的山峰，右邊只有24和25。結果為hash (25，24)并添加證明，證明為 {16，20，hash (25，24)}。③ 從左到右，將左側的山峰插入到證明中。左邊只有14個，因此證明為 {16，20，hash (25，24)，14}。因此，最終證明是ATXO 15的Merkle證明。

1.4.1 休眠證明的創建

函數1DormantWitCreate←(Xt，Dt+1，AMP，DT )：為了有效判斷在檢查點進入休眠狀態的UTXO，以DT為18個月(通過調研數據發現在18個月的時候，休眠與活躍的比例接近1∶1)為準則構造了休眠證明。當DT為18個月時，AMP是活躍UTXO的Merkle證明路徑，并且AMP還可以確保進入休眠狀態的UTXO不會被偽造。所以休眠證明為DormantProof←(Xn，Dt+1，AMP，DT )。

1.4.2 休眠證明的驗證

定義1DormantWitVerification：在最新區塊中使用AMR進行驗證。根據休眠證明中包含的參數AMP，如果重新計算AMR與最新的塊一致，則驗證成功；否則，驗證將失敗并且ATXO被認為是偽造的。

1.4.3 休眠證明的更新

定義2DormantWitUpdate：當UTXO從休眠狀態變為活躍狀態時，將休眠證明中的DT置零，并清除之前存儲的AMP。當UTXO從活躍狀態變為休眠狀態時，DT開始計時直到DT為18個月，并且用戶節點開始記錄UTXO所在的路徑AMP。如果在某個時期發生刪除操作，則參數Dt也將實時更新為最新狀態。

1.4.4 休眠證明的存儲

筆者為每個用戶設計存儲自己的UTXO休眠證明，當用戶想要使用休眠UTXO，需提供休眠證明說明該筆交易的真實性，并將自身存儲的證明數據進行廣播，以便其他用戶節點使用該用戶廣播休眠證明中的AMP進行驗證。如果一致，則驗證成功；如果不一致，則驗證失敗。

2 分 析

本節將從多個參數中討論該提議方案與其他相關方案的比較研究。詳細信息顯示在表1中。令n為UTXO大小，m為每個區塊中的事務，L為區塊鏈的長度，NA表示未有相關數據。

2.1 交易證明大小的分析

Minichain-方案包括存在性證明和未花費證明，因此總數為810字節。在Minichain+方案中，比Minichain-方案多一個TXO_C參數，并且存在性證明也多一個，因此它是1 450字節。在Boneh方案中，只有436個字節的未花費證明。在Edrax方案中，使用SparseMerkleTree的結構證明字節為371字節。Ethanos方案中使用MerklePatriciaTries結構證明字節為3 kB。在DorChain的解決方案中，僅需要AMP證明(只有320字節)，這是最小的同步證明長度，可有效節省節點的存儲空間。

表1 DorChain與其他工作的比較

2.2 區塊頭大小的分析

在Minichain +解決方案中，區塊頭包括3部分：TXO_C，STXO_C和TMR。首先，該區塊中的所有事務都使用Merkle樹[15]技術來形成每個TMR；然后，使用MMR技術實例化每個TMR來形成峰值，并對所有峰值使用普通的Merkle樹來獲得TXO_C；最后，使用RSA累加器技術將每個區塊中的STXO存儲在區塊頭中，以形成STXO_C。在該解決方案中，檢查點的參數為DTXO_C及AMR，普通塊的參數僅為AMR，大小為32字節。DorChian基于UTXO，將UTXO分為兩種狀態，使用RSA累加器將休眠的UTXO實例化為DTXO_C，MMR技術將活躍的UTXO實例化為AMR并將其存儲在區塊頭中。因此，與Minichain +解決方案相比，該方案少引入了一個參數TXO_C，即少引入了384個字節。如表1中所示，比較特定的數據大小。Flyclient中的每個區塊記錄Merkle Mountain Root和8個字節來存儲難度，因此它是40字節，而Ethanos在每個塊頭中引入Bloom Fliter，因此增加了10 MB。

2.3 驗證時間的分析

在Minichain方案中，作者首先將區塊鏈中的所有STXO集映射到素數，然后計算STXO_C，將該值存儲在區塊頭中。其次，作者使用區塊鏈中的所有交易以普通Merkle樹的形式在每個區塊中形成一個TMR。MMR技術用于實例化為每個塊形成的TMR，然后形成實例化的峰值。TXO_C以普通的Merkle樹的形式形成，并存儲在塊頭中。但是，每個塊的更新需要4輪計算。在第1輪中，每個STXO都映射到素數以計算STXO_C。在第2輪中，計算當前塊中的所有事務以獲取TMR。在第3輪中，使用MMR技術基于TMR計算峰值。在第4輪中，使用普通的Merkle樹技術計算峰值以獲取TXO_C。因此，計算開銷很高。證明驗證(在1 000個事務驗證的情況下)包括存在性證明(100 ms)和未花費證明(20 000 ms)。由于Minichain+比Minichain-方案具有更多的TMR包含證明，因此驗證時間要長200 ms。在Boneh方案中，由于不僅需要驗證成員資格證明，而且還需要驗證非成員證明，因此驗證時間大約是Minichain中非成員證明的驗證時間的兩倍(40 000 ms)。在Edrax方案中，驗證時間為264 ms。在Ethanos方案中，選擇了100個普通事務，并在檢查點執行恢復事務。第5個檢查點的恢復時間為150 ms，因此1 000個事務大約需要 1 500 ms。

驗證程序使用NI-POE協議檢查累加器是否正確更新。驗證器的最大負擔是映射要添加到每個塊中的塊頭的元素，然后計算乘積。在DorChain的方案中，每個檢查點僅使用BachAdd進行計算。另一方面，Boneh解決方案需要兩輪NI-POE驗證，而Minichain解決方案只需要一輪NI-POE驗證。具體證明開銷如表2所示。

在筆者提出的解決方案中，由于不需要驗證成員資格和非成員資格證明，因此僅需要MMP(Merkle Mountain Proof)驗證，而無須進行NI-POE驗證。盡管從表1可以看出，DorChain方案中的證明大小和驗證復雜性稍微增加了通信開銷，但在該方案的驗證過程中，用戶只需要提供一個存在性證明，且方案中使用的MMR是樹形結構，復雜度為對數級。在Windows系統中的VSCode平臺上利用Python做實驗，得到的存在性證明驗證時間約為100 ms。驗證時間大大減少了。

表2 DorChain方案與Minichain和Boneh的證明成本比較

2.4 其他方面的分析

在DorChain的方案中，使用RSA累加器實例化休眠的UTXO，而MMR實例化活動的UTXO。首先，區塊鏈中的所有UTXO都被初始化為休眠狀態，除了新挖礦產生的UTXO之外，因此該方案沒有掃描休眠賬戶的開銷。如果它從睡眠狀態變為活躍狀態，則使用刪除算法進行操作；如果狀態從活躍狀態變為睡眠狀態，則使用添加算法進行操作。另一方面，在狀態更改過程中需要提供AMP，以證明UTXO是真實的而不是偽造的。因此，用戶只需要存儲其自己擁有幣的AMP即可。在文獻[11]的方案中，提出了Ethanos技術來定期清理不活動的賬戶。首先，需要建立一個空狀態來掃描休眠賬戶。當閑置的帳戶想要調用交易時，它需要提供一個Merkle證明，一個無效證明以及先前存儲在其中的值。通過向每個區塊引入布隆過濾器，它解決了由于過多的睡眠時間而導致的大量存儲和驗證問題。因此，每個區塊增加了10 MB。具體信息如表3所示。

表3 與Ethanos方案的激活條件比較

2.5 特例

在區塊鏈中，所有UTXO都是實時變化的。筆者通過對近一年內的所有數據進行統計分析，發現有22%的比特幣在大于5年的時間里都沒有移動過。此數據僅是當前的實時狀態，以后可能會稍有變化。即使如此，筆者仍假定由于區塊鏈中持有人的行為而沒有UTXO休眠，但是由于早期階段的密鑰管理不當，私鑰的丟失是真實的，并且這部分產生了不可移動的UTXO(根據調查結果)，丟失的硬幣約占所有已發行硬幣的21%，并且永久丟失了400萬個比特幣，這也適用于DorChain的方案。

3 結束語

在這項工作中，筆者提出了基于UTXO的休眠比特幣DorChain的概念，以解決區塊鏈中的驗證問題。基本思想是將區塊鏈中的所有UTXO劃分為活動狀態和休眠狀態。使用RSA累加器實例化DTXO，并使用MMR實例化ATXO。筆者提出的方案只需要驗證休眠證明，可以提高驗證效率。同時，在該方案中，也可以很好地控制證明大小和區塊頭引入的數據。

未來，關于最新狀態的驗證，每次休眠的UTXO被刪除時，最新的DTXO_C都會記錄在UTXO中。該驗證工作將移交給DorChain中的礦工通過BatchDel進行驗證。為了使DorChain的方案長期穩定發展，可以建立相應的激勵機制，以鼓勵礦工進行驗證并獲得獎勵。