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

潘森杉，徐臘梅

(1.江蘇省工業(yè)網(wǎng)絡(luò)安全技術(shù)重點(diǎn)實(shí)驗室，江蘇 鎮(zhèn)江 212013；2.江蘇大學(xué) 計算機(jī)科學(xué)與通信工程學(xué)院，江蘇 鎮(zhèn)江 212013)

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

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

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

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

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

1 系統(tǒng)細(xì)節(jié)

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

1.1 在RSA累加器中實(shí)例化的DTXO承諾

將區(qū)塊鏈中的所有UTXO初始化為休眠狀態(tài)，即DTXO。首先使用HashToPrime[15-16]函數(shù)將DTXO集合中的元素映射到質(zhì)數(shù)，然后使用RSA累加器[15]將集合DTXO哈?；癁楹啙嵡液愣ǖ某兄Z(DTXO承諾)。在使用累加器計算承諾之前，利用哈希函數(shù)將集合中的DTXO映射到素數(shù)再計算，主要是為了避免沖突?；窘Y(jié)構(gòu)如圖1所示。

圖1 DTXO承諾構(gòu)造過程

算法2DUpdate：在檢查點(diǎn)更新DTXO_C。如果參數(shù)DT為18個月，則需要將DTXO添加到DTXO集合中。如果在該時期內(nèi)硬幣從休眠狀態(tài)變?yōu)榛钴S狀態(tài)，則可以通過刪除操作將其從集合D中刪除。更新的DTXO_C記錄在標(biāo)記的DTXO上。然后可以使用算法1來更新DTXO_C。具體算法如圖2所示。

1.2 在MMR中實(shí)例化的AMR

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

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

1.3 狀態(tài)轉(zhuǎn)換

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

休眠到活躍狀態(tài)：在DorChain中，無論是正常區(qū)塊還是檢查點(diǎn)，UTXO都可以隨時從休眠狀態(tài)更改為活躍狀態(tài)?？梢栽谔峁︰TXO的AMP的前提下隨時執(zhí)行Delete操作，將已刪除的UTXO標(biāo)記為“活躍”，最新的DTXO_C也記錄在UTXO上并在整個網(wǎng)絡(luò)上廣播以進(jìn)行驗證。在檢查點(diǎn)時，最新標(biāo)記“活躍” UTXO攜帶的DTXO_C是刪除操作的最新狀態(tài)。對于這種狀態(tài)的驗證方法，在DorChain中設(shè)計了礦工，以比較基于標(biāo)記的UTXO在Boneh方案中使用BatchDelete算法計算的結(jié)果，如果它們一致，則是正確的。

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

1.4 休眠證明的創(chuàng)建、驗證、更新以及存儲

假設(shè)ATXO需要在一個時期內(nèi)從活躍狀態(tài)再次變?yōu)樾菝郀顟B(tài)，則單個UTXO的休眠證明構(gòu)造參數(shù)為：休眠硬幣(DTXO)，DTXO_C(DTXO承諾)，AMP(ActiveMerkleProof)和DT(休眠時間)，其中AMP是A集合中ATXO利用MMR構(gòu)造的Merkle證明記錄，而DT是記錄硬幣的休眠時間。AMP可以幫助證明硬幣是真實(shí)的而不是偽造的，并且當(dāng)DT達(dá)到18個月時，認(rèn)為該硬幣再次進(jìn)入休眠狀態(tài)，并且可以使用添加操作將其添加到下一個檢查點(diǎn)設(shè)置的DTXO集合中。因此，休眠證明不僅可以證明硬幣的存在，而且是可以確定UTXO再次進(jìn)入休眠狀態(tài)的條件。休眠證明的功能如圖4所示。

圖4 休眠證明的功能圖

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

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

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

1.4.1 休眠證明的創(chuàng)建

函數(shù)1DormantWitCreate←(Xt，Dt+1，AMP，DT )：為了有效判斷在檢查點(diǎn)進(jìn)入休眠狀態(tài)的UTXO，以DT為18個月(通過調(diào)研數(shù)據(jù)發(fā)現(xiàn)在18個月的時候，休眠與活躍的比例接近1∶1)為準(zhǔn)則構(gòu)造了休眠證明。當(dāng)DT為18個月時，AMP是活躍UTXO的Merkle證明路徑，并且AMP還可以確保進(jìn)入休眠狀態(tài)的UTXO不會被偽造。所以休眠證明為DormantProof←(Xn，Dt+1，AMP，DT )。

1.4.2 休眠證明的驗證

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

1.4.3 休眠證明的更新

定義2DormantWitUpdate：當(dāng)UTXO從休眠狀態(tài)變?yōu)榛钴S狀態(tài)時，將休眠證明中的DT置零，并清除之前存儲的AMP。當(dāng)UTXO從活躍狀態(tài)變?yōu)樾菝郀顟B(tài)時，DT開始計時直到DT為18個月，并且用戶節(jié)點(diǎn)開始記錄UTXO所在的路徑AMP。如果在某個時期發(fā)生刪除操作，則參數(shù)Dt也將實(shí)時更新為最新狀態(tài)。

1.4.4 休眠證明的存儲

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

2 分 析

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

2.1 交易證明大小的分析

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

表1 DorChain與其他工作的比較

2.2 區(qū)塊頭大小的分析

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

2.3 驗證時間的分析

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

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

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

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

2.4 其他方面的分析

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

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

2.5 特例

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

3 結(jié)束語

在這項工作中，筆者提出了基于UTXO的休眠比特幣DorChain的概念，以解決區(qū)塊鏈中的驗證問題?；舅枷胧菍^(qū)塊鏈中的所有UTXO劃分為活動狀態(tài)和休眠狀態(tài)。使用RSA累加器實(shí)例化DTXO，并使用MMR實(shí)例化ATXO。筆者提出的方案只需要驗證休眠證明，可以提高驗證效率。同時，在該方案中，也可以很好地控制證明大小和區(qū)塊頭引入的數(shù)據(jù)。

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