一種面向公有鏈的輕量級可擴展技術

陳 幻 王意潔

(并行與分布處理國家重點實驗室(國防科技大學) 長沙 410073)(國防科技大學計算機學院 長沙 410073)

區塊鏈技術[1-3]被視為繼云計算、物聯網、人工智能之后的又一項顛覆性技術，受到了金融機構、政府部門以及各科技企業的高度關注，將開啟下一代互聯網——價值交換網絡的新時代.區塊鏈解決了在不可信環境中建立信任的基礎難題，具有去中心化、不可篡改、不可抵賴、抗審查等特征，能夠廣泛運用于支付清算、物聯網、政務服務、醫療、物流、博彩娛樂等多種領域.

然而，區塊鏈存在2個嚴重的問題：1) 系統吞吐率低.目前比特幣每秒處理交易數量(transactions per second， TPS)在3～7筆之間，以太坊TPS在7～15筆之間.相比之下，主流的中心化支付系統，例如Visa和MasterCard，平均每秒能處理2 000筆交易，峰值性能能夠達到56 000 TPS.低吞吐率導致網絡中未處理的交易無限堆積，交易平均處理時間延長，使得區塊鏈無法運用于實時領域.此外，隨著越來越多的分布式應用(distributed applications, DApps)運行于同一條鏈上，低吞吐率的問題將會越發嚴重，極大地限制了區塊鏈的運用.2)每個驗證節點都需要獨立保存一份完整的歷史數據賬本和對應的狀態信息，這將消耗大量的存儲資源.一方面，賬本大小隨著新區塊的產生持續增長，存儲全部歷史區塊需要消耗大量的磁盤空間.可以預測在不久的將來，區塊鏈賬本數據將輕松到達1TB，超過目前絕大多數普通商用機的存儲能力.另一方面，由于區塊鏈歷史數據過于龐大，從區塊中檢索信息需要消耗大量的時間開銷.為了加速對交易和區塊的驗證，驗證節點會在內存中維護一個叫驗證狀態的索引結構.盡管驗證狀態相比于歷史區塊占用的空間較少，但他們需要被快速訪問，通常放在內存數據庫中(例如LevelDB)，對節點內存容量提出了較高要求.如果驗證狀態大小超過了節點的內存容量，一部分狀態信息需要保存在磁盤或其他二級存儲器中.由于二級存儲器訪問時間較長，容易遭受分布式拒絕服務(distributed denial of service, DDoS)攻擊.例如在2016年9月[4]，攻擊者利用以太坊EXTCODESIZE指令的漏洞，讓交易頻繁訪問放置在硬盤上的狀態信息，導致了單個區塊的驗證時間長達60 s.

區塊鏈歷史數據以及驗證狀態不斷增長的特點，將帶來以下問題.首先，由于對磁盤和內存容量的較高要求，只有少量的“超級”節點能夠運行完整的區塊鏈全節點，將導致中心化的出現.其次，大量資源較少的節點只能運行輕客戶端(例如移動錢包、輕節點)，它們依賴全節點提供的查詢服務，不能獨立驗證交易和區塊的有效性，容易遭受長城等類型的攻擊.此外，對于新加入網絡的全節點，它們需要同步從創世區塊到最近的所有歷史區塊，并建立驗證狀態的索引結構，需要消耗大量的時間開銷.

針對系統吞吐率低的問題，研究人員提出了多種擴容技術.然而，絕大多數擴容技術無法完全破除區塊鏈的三角難題，即同時實現安全、去中心化和可擴展.目前，分片技術被廣泛視為一種能夠解決區塊鏈三角難題的有效方法，通過將交易和狀態進行分割，使得不同的分片能夠并行處理不相關的交易，線性提升系統的處理能力.然而，為了避免惡意節點集中到某個特定分片發起攻擊，需要周期性地將分片節點進行重組.由于分片節點只存儲了當前分片的數據，當被劃分到其他分片后，需要下載新分片的數據，這個過程被稱為狀態遷移.狀態遷移需要下載大量數據，不僅中斷了系統的處理，同時也限制了分片切換的頻率.

針對節點存儲資源占用高的問題，研究人員首先提出了賬本剪枝技術[5]，將對于驗證交易和區塊無用的歷史數據進行裁剪，只維護驗證狀態信息.該方法可以有效降低整個區塊鏈的賬本大小和歷史區塊同步問題.然而，賬本剪枝技術只解決了歷史數據對于磁盤的負擔，并不能減輕狀態對于內存的需求.針對內存占用高的問題，研究人員進一步提出了無狀態客戶端[6-10]的概念.無狀態客戶端利用承諾(commit-ment)技術，將不斷增長的狀態壓縮到固定字節的承諾.但與賬本剪枝技術不同的是，節點并不需要保留具體的驗證狀態.然而，無狀態客戶端面臨3個挑戰：

1) 證明信息過大，增加網絡帶寬開銷.基于默克爾樹(Merkle)構建的承諾需要提交從葉子節點到根節點的Merkle路徑，以目前比特幣未消費交易輸出(unspent transaction outputs, UTXO)集合和以太坊賬戶的規模，構建的Merkle證明分別是交易大小的4倍與20倍.

2) 承諾更新代價高.基于Merkle樹的承諾更新，需要已修改節點的所有數據；而基于通用累加器的承諾更新，刪除操作需要進行大量的計算.

3) 由于每個證明只對應1個承諾，當承諾更新后，會導致交易有效性證明過期無效.由于網絡傳輸延遲過高，新發起的交易并不能得到及時地處理，交易過期將會成為一個常態問題.讓用戶頻繁提交更新后的證明信息無疑會增加用戶使用的負擔.

基于3個挑戰的問題，構建一種可擴展的輕量級區塊鏈，不僅具有較高的系統吞吐率，同時讓所有節點只需利用少量的存儲資源(包括磁盤和內存)，便可以獨立驗證和打包交易，成為了加密貨幣領域一個迫切需要解決的難題.為此，本文提出了PocketChain，一種面向UTXO模型的公有鏈的輕量級擴容技術.首先，PocketChain使用無狀態客戶端設計，創新性地提出了基于RSA累加器構建的已消費交易輸出(spent transaction outputs, STO)承諾技術，極大提升了狀態累加器的更新效率，使得驗證節點只需存儲區塊頭便可以驗證交易的有效性.其次，將本文提出的無狀態客戶端與分片技術相集合，利用無狀態客戶端低存儲的優勢，克服分片周期性隨機重組導致的狀態遷移問題，從而能進一步提升分片重組頻率，增加分片系統安全性.

綜上所述，本文聚焦區塊鏈數據膨脹和低吞吐的問題，提出了PocketChain，一種面向UTXO模型的可擴展輕量級區塊鏈.本文的主要貢獻有4個方面：

1) 提出了基于RSA累加器構造的具有批處理能力的增量STO承諾技術，將狀態累加器更新效率從O(n2)提升到O(n)；

2) PocketChain使用STO承諾技術構建無狀態客戶端，驗證節點只需要保存歷史區塊頭以及少量的緩存數據，有效降低了對磁盤和內存的負擔；

3) PocketChain將無狀態客戶端與分片技術進行結合，避免了分片周期性隨機重組導致的狀態遷移問題，從而能進一步提升分片重組頻率，增加了分片系統的安全性；

4) 實驗結果表明:在不犧牲去中心化與安全性的前提下，PocketChain能夠極大降低節點的存儲壓力，并且系統吞吐率能夠隨著分片數量的增加線性增長.

1 相關工作

在本節中，我們主要介紹無狀態客戶端與分片技術的相關概念以及研究現狀.

1.1 無狀態客戶端

1.1.1 無狀態客戶端系統結構

定義1.區塊鏈狀態.給定一個數據結構Sstate={s1,s2,…,sn}，表示系統中當前所有賬戶(或地址)的快照.節點可以通過訪問Sstate來驗證交易的合法性，從而避免遍歷所有歷史區塊.這樣的數據結構稱為區塊鏈狀態.

需要注意的是，狀態信息對于區塊鏈完整性并不是必須的.由于狀態信息相比歷史區塊鏈占用的存儲空間較少，可以放入內存數據庫中，從而提高檢索效率，對于加速交易的驗證具有十分重要的作用.根據驗證節點是否保存完整的狀態信息，區塊鏈可以分為2類：狀態區塊鏈與無狀態區塊鏈.

Fig. 1 Stateful blockchain architecture圖1 狀態區塊鏈系統結構

狀態區塊鏈的系統結構如圖1所示，每個節點根據歷史區塊建立狀態信息，并用狀態信息來驗證交易的合法性.當新區塊產生后，根據區塊中的具體交易，對狀態進行更新.狀態區塊鏈的優點在于，用戶不需要保存任何狀態就可以發起交易.然而，狀態區塊鏈存在狀態“爆炸”的隱患.隨著有效賬戶(或地址)的增加，狀態空間不斷增長，一方面需要節點不斷提升內存容量，另一方面會降低驗證交易和區塊的效率.

相比之下，無狀態區塊鏈只需要維護狀態的承諾，不需要保存任何具體的狀態信息.如圖2所示，每個區塊頭包含當前狀態的承諾，每個節點只需要保存歷史區塊頭，并根據用戶提交的交易有效性證明對交易進行驗證.無狀態區塊鏈的優點在于，不需要保留具體的歷史區塊和維護狀態信息，降低了節點對磁盤和內存的需求，使得配置較低的節點(包括手機等移動設備)能夠運行完整的驗證節點.其缺點在于，承諾更新效率低下，無法適用于高吞吐的環境下.

1.1.2 無狀態區塊鏈研究現狀

無狀態區塊鏈概念首次由以太坊創始人Buterin[7]提出，用于解決以太坊狀態爆炸問題.使用默克爾帕特里夏樹(Merkle patricia tree, MPT)存儲所有用戶賬戶的狀態信息.礦工節點在打包區塊時，需要負責生成相關賬戶狀態的Merkle證明，并附加在每個區塊的后面.全節點只需要存儲狀態樹根，便可以驗證區塊.然而，每筆交易的默克爾證明的字節大小是交易的20倍，極大地增加了網絡帶寬開銷.

Todd[9]基于默克爾山脈(Merkle mountain range, MMR)提出了交易輸出(transactions outputs, TXO)承諾技術來解決比特幣UTXO無限增長的問題.它將舊的UTXO進行歸檔，允許全節點丟棄歸檔的具體數據.當交易消費已歸檔UTXO時，全節點(或服務節點)生成對應的默克爾分支.驗證節點根據默克爾分支對MMR進行重建，從而能夠對舊的UTXO進行驗證，并相應更新MMR.證明MMR中的任意狀態，可以僅使用大小為lbn的證明.然而，正如作者提到的，檢查承諾是否被正確更新會產生較大的開銷.

Reyzin等人[8]提出使用加密認證數據結構來提升交易驗證效率.礦工節點需要持有完整的狀態，在處理交易時對狀態進行更新，并發布每筆交易導致狀態改變的證明.相比之下，驗證節點僅需要持有狀態的簡短摘要，驗證證明并計算出新摘要.由于驗證節點不需要存儲具體的狀態信息，使得配置較低的節點依然能夠獨立驗證交易，提升了系統的安全.

Chepurnoy等人[6]提出了一種無狀態交易驗證的通用框架，稱為EDRAX.所有節點，包括礦工和驗證節點只需持有最新被確認的區塊，便可以驗證交易并更新狀態.他們提供了EDRAX的2種實例:一種使用稀疏默克爾樹(sparse Merkle tree, SMT)構建基于UTXO模型的區塊鏈；另一種使用代數向量承諾(vector commitment， VC)構建基于賬戶模型的區塊鏈.然而，EDRAX并沒有考慮證明過期問題導致用戶頻繁提交更新后的證明，增加了用戶使用的負擔.

Boneh等人[10]首先針對通用累加器和向量承諾，提出了多種批處理技術，極大地提升了累加器的驗證效率并降低了傳輸開銷.其次，使用Class Group未知階群構建無陷門的通用RSA累加器，避免進行可信的初始化設置.最后，將以上具有批處理能力、無陷門特征的RSA累加器用于創建基于UTXO模型的無狀態公有鏈，極大地降低了交易的證明大小和驗證開銷.然而，在不知道群階的情況下，RSA累加器批量刪除操作的復雜度為O(n2)，效率低下.基于RSA累加器構建的UTXO承諾，需要進行大量刪除操作，導致累加器更新效率低，無法適用于高吞吐的環境下.

1.2 分片技術

1.2.1 區塊鏈分片技術基礎模型

分片技術在運用于區塊鏈之前，已經在數據庫領域得到了廣泛運用，用于提升數據庫的吞吐能力，例如OpenDHT[11]，Google spanner[12]等.簡單來說，分片技術將數據庫的不同表(或相同表中的不同行)分別放置在不同的服務器中，根據數據訪問請求的對象，將請求分發到對應的服務器.從而，數據庫的響應能力能隨著服務器數量的增加呈線性增長，極大地提升了數據庫的服務能力.類似地，在區塊鏈中，可以將單鏈拆分多條并行運行的子鏈(分片).從實現的角度，分片可以進一步分為交易分片和狀態分片.交易分片根據特定規則，將網絡中的交易分發到不同的子鏈，各子鏈并行驗證和打包交易，從而使區塊鏈的吞吐量實現質的提升.狀態分片將區塊鏈的驗證狀態(廣義上來講，包括歷史數據)分為多個不相交的子集，各分片只需保存其中的一個狀態子集和處理與狀態相關的交易，從而降低每個節點的數據存儲量，如圖3所示.實現狀態分片往往意味著同時實現交易分片.

Fig. 3 State sharding architecture圖3 狀態分片架構

1.2.2 區塊鏈分片技術研究現狀

Elastico[13]是最早面向公有鏈的交易分片技術.首先，各節點需要進行第1輪工作量證明(proof of work, PoW)建立身份，避免遭受女巫攻擊.為了防止惡意節點集中到特定分片中，利用絕對的算力(或權益)對該分片進行攻擊(稱為1%攻擊)，需要將節點隨機地分配到各個分片.分片形成后，分片內部采用PBFT[14]協議達成共識，形成micro block發往0號分片.0號分片通過驗證和打包mirco block，再次運行PBFT共識，生成最終區塊.然而，Elastico不支持跨片交易處理，并且分片內部采用傳統的PBFT協議，參與共識的節點數量較少，具有較高的錯誤率.此外，Elastico為了避免1%攻擊，需要周期性地對節點進行重新分配.為了避免每次分片切換時下載大量新分片的數據，各節點需要保存所有分片的數據，節點存儲壓力較大.

Zillqa團隊[15]在Elastico的基礎上，進行了架構和性能優化.在設計架構上，提出雙鏈架構，一條是交易鏈，一條是目錄服務鏈.交易鏈上保存交易數據，目錄服務鏈存放礦工元數據信息.其中最近的c個節點形成最終委員會，負責劃分分片以及收集各分片的micro block形成final block.在共識方面，Zillqa借鑒了CoSi[16]多重簽名技術，并用數字簽名代替MAC，極大提升了PBFT的擴展性，使得PBFT可以適用于幾百個節點.此外，Zillqa第1次創新性地提出數據流編程框架，利用全網算力來實現大規模計算，如MapReduce和神經網絡計算等.雖然Zilliqa在共識方面有較大改善，但是依然沒有實現狀態分片.

OmniLedger[5]首次實現了狀態分片并提出了并行共識算法.通過移除塊的全序要求，將塊組織成有向無環圖(directed acyclic graph, DAG)結構，增加了系統的吞吐量、降低了交易確認延遲.此外，OmniLedger使用原子提交協議來處理跨分片交易；并使用賬本剪枝技術，引入檢查點，將檢查點之前的歷史數據進行裁剪，降低節點的存儲壓力.然而，原子提交協議采用以用戶為中心的2階段提交方法，需要用戶參與跨分片交易處理；每次分片切換，都會導致狀態遷移.

RapidChain[17]在OmniLedger的基礎上，加入了基于糾刪碼[18-20]的信息分發技術來加快大區塊的傳播速度，實現了覆蓋通信、計算與存儲的全分片技術.為了降低狀態遷移代價，RapidChain采用了Cuckoo協議，每次分片切換只需替換部分節點.

以太坊2.0[21]在階段0將引入基于權益證明(proof of stake, PoS)的信標鏈(beacon chain)，完成從PoW到PoS共識機制的轉變.在階段1將引入分片，分片是以太坊網絡未來擴容技術的核心，允許同時進行交易、存儲和信息處理，從而線性地增加整體網絡的吞吐量.根據以太坊2.0規范，信標鏈將支持1 024個分片鏈，每條分片鏈將有128個節點進行驗證工作.信標鏈的關鍵功能是管理PoS協議以及所有的分片鏈：在每一步為每個分片隨機選擇區塊的提議者，組織驗證者進入委員會，對擬議的區塊進行投票；對驗證者實施獎勵和處罰；執行交聯(crooslinks)的處理，將整個分片系統連接在一起，并協助完成跨片交易處理.整體而言，以太坊2.0分片技術較為完善，能夠同時實現交易分片和狀態分片，但每個分片依然會面臨數據與狀態增長問題.

2 系統簡介

2.1 主要思想

針對目前公有鏈系統吞吐率低下和節點存儲壓力不斷增加的難題，本文提出了PocketChain，它需要滿足3個目標：

1) 低存儲.節點不需要保留具體的歷史區塊和狀態信息便可以驗證交易的有效性，大大降低運行驗證節點的存儲資源開銷.

2) 高吞吐.系統吞吐率能夠隨著網絡節點數量的增長線性增加.

3) 安全與去中心化.系統不犧牲任何安全性和去中心化的特性.

2.2 挑 戰

為了降低驗證節點的存儲開銷，已有的賬本剪枝技術只能降低歷史賬本大小.隨著系統中有效地址和賬戶的不斷增加，節點內存開銷逐漸加大.無狀態客戶端采用累加器將狀態數據壓縮到固定字節的承諾，能夠同時解決歷史區塊與狀態數據膨脹問題，但面臨交易證明信息過大(基于Merkle的累加器)、承諾更新代價高(通用累加器)的挑戰.

此外，分片技術被廣泛視為提升區塊鏈吞吐率最有效的方法之一，已被多個公有鏈采用.然而，為了避免惡意節點集中到某個特定分片發起定向攻擊，需要周期性地將節點隨機分配到各個分片中.由于每個分片只保留了當前分片的數據，當節點劃分到其他分片后，需要同步下載新分片的數據，這個過程稱為狀態遷移.狀態遷移需要下載大量數據，不僅增加了網絡帶寬開銷，同時限制了分片切換的頻率，對系統安全性造成負面影響.

綜上所述，本文將結合無狀態客戶端與分片技術來解決區塊鏈數據增長與吞吐率低下的雙重難題，其面臨的主要挑戰有2點：1)構造證明信息短小、更新效率高的狀態累加器.2)克服分片技術周期性隨機重組導致的狀態遷移問題.

2.3 技術路線

無狀態客戶端的關鍵在于構造證明信息短小、更新效率高的狀態累加器.RSA累加器建立在冥模運算之上，具有證明信息短小、固定等優點，能夠滿足以上需求.此外，RSA累加器支持批處理操作，多個證明可以合并為一個證明，能有效減少交易證明的字節大小，并降低驗證的時間開銷.在公有鏈環境下，沒有任何可信的第三方，需要借助未知階群，構造無陷門的RSA累計器.然而，在不知道群階的情況下，RSA累加器刪除操作的復雜度為O(n2)，添加操作的復雜度為O(n).當需要進行大量刪除操作時，累加器的更新效率將快速下降.例如UTXO承諾技術需要動態刪除大量已消費的交易輸出，導致UTXO承諾更新效率低下.

針對以上問題，在3.2節中，本文首先創新性地提出了STO承諾技術，使用RSA累加器將所有已消費的交易輸出進行壓縮.STO是一個只支持添加操作的數據結構，從而避免進行代價較高的刪除操作.接著，PocketChain基于STO承諾技術建構無狀態客戶端.用戶為了證明交易有效，需要提供交易輸入的存在性證明和交易輸入的未花費證明.輸入存在性證明可以通過輸入產生時的Merkle路徑進行自證；輸入的未花費證明可以通過提交STO非成員見證.只要輸入不在STO集合內，便不存在雙花.最后，在第4節中將無狀態客戶端運用于分片技術架構下，利用低存儲的優勢，降低分片技術周期性隨機重組導致的狀態遷移代價.

3 基于RSA累加器的無狀態客戶端

無狀態客戶端設計將交易驗證的一部分工作分配給用戶，用戶在發起交易時，需要附加提交交易有效性證明.驗證節點和礦工節點只需保存狀態的簡短摘要，根據交易有效性證明和當前狀態摘要進行交易驗證.無狀態客戶端不需要存儲具體區塊和狀態信息，大大降低了節點的磁盤和內存壓力.然而，目前無狀態客戶端主要面臨交易有效性證明過大、狀態累加器更新效率低，以及交易頻繁過期問題.

為此，本節針對UTXO模型的公有鏈，提出了基于RSA累加器的無狀態客戶端PocketChain.首先，使用無陷門、具有批處理能力的RSA累加器壓縮狀態，使得證明信息簡潔短小，并且能將多個證明合并為一個證明，有效降低了證明的字節大小；將RSA累加器作用于STO集合，STO是一個只支持添加操作的數據結構，避免了進行代價較高的RSA累加器的刪除操作，大大提升了累加器的更新效率；最后，引入緩存，使得交易可以在接下來的n個區塊時間內被處理，避免每次新區塊產生后都需要重新提交更新后的有效性證明.

3.1 累加器

1993年累加器(accumulator)首次被Benaloh等人[22]提出，能夠將一個大集合的數據壓縮到一個短小的、固定字節的值，稱為累加值.對于每一個在集合內的數據，都存在一個成員見證(membership witness)證明該數據在集合內.對于不在集合內的數據，無法偽造成員見證.Camenisch等人[23]進一步提出了動態累加器(dynamic accumulator)，能夠高效地向累加值添加或刪除指定元素.在動態累加器的基礎上，Li等人[24]提出了通用累計器(universal accumulator)，不僅支持成員見證，對于不在集合內數據，也能夠生成非成員見證(non-membership witness)，證明該數據不在集合內.目前，累加器已廣泛運用到多個領域，包括成員測試、數據外包時的隱私保護、匿名電子現金系統等.

RSA累加器是在強RSA的假設下，基于RSA模數的模冪運算.其最簡單的形式工作為:累加器的秘鑰是RSA的模數N=pq的因子，其中p和q為強素數，累加值初始化為g∈ZN.對于任意大小的素數集合S={x1,x2,…,xn}，其累加值為

A(S)=gx1×x2×…×xnmodN.

(1)

對于任何在集合S中的數據xi，其成員見證wi為S集合中除去xi的累加值：

wi=gx1×x2×…×xn-1×xn+1×xnmodN.

(2)

驗證成員見證wi是否正確可以通過判斷：

(3)

是否成立.

傳統的RSA累加器在初始化時需要生成2個強素數p和q，任何知道素數p和q的人都可以使用歐幾里得定理φ(N)=(p-1)(q-1)計算RSA群的階，從而可以進一步偽造任何成員證明和非成員證明.然而，在公有鏈環境下，不存在任何可信第三方，如何確保RSA累加器秘鑰不泄露是需要解決的首要問題.這里我們借鑒了Boneh等人[10]的工作，他將動態累加器建立在未知階的群之上，避免進行可信的初始化設置.Class Group作為一種虛構的二次方階群，可以用于構建去信任化的RSA累加器.相關工作本文不做展開，讀者可以參考Boneh以及其他相關工作.

3.2 STO承諾技術

在UTXO模型的區塊鏈中，狀態由所有的UTXO組成.每筆交易消費已有的UTXO，并產生新的UTXO記錄.已有的工作將RSA累加器作用于UTXO集合上，通過構建UTXO承諾來壓縮狀態.當新區塊產生后，從UTXO承諾中刪除所有已消費的UTXO并添加新產生的UTXO.然而，在不知道群階的情況下，從RSA累加器中刪除元素的復雜度為O(n2)，而添加操作的復雜度僅為O(n)，頻繁地從累加器中刪除元素將導致累加器更新效率低下.

為此，本文提出了STO承諾技術，使用RSA累加器將所有STO進行壓縮.由于STO是一個只支持添加操作的數據結構，避免了進行代價較高的累加器刪除操作.

3.3 基于STO承諾的無狀態客戶端

PocketChain基于STO承諾技術構建無狀態客戶端，其系統結構如圖4所示，主要包含3個模塊：STO承諾、證明生成與更新.

Fig. 4 System architecture of PocketChain 圖4 PocketChain系統結構

3.3.1 STO承諾

每個區塊頭除了包含交易的Merkle樹根(Merkle transactions root, MTR)，還包含了由所有已消費的交易輸出組成的STO累加值ACC.當新區塊產生后，需要向ACC中添加區塊中已消費的交易輸出，構造新的STO累加值.此外，RSA累加器的輸入必須限制為素數才能保證其無碰撞的特性，為此我們需要將STO轉變為素數，這可以通過函數HashToPrime[25]進行轉化.具體過程如算法1所示：

算法1.狀態累加器批處理更新與驗證算法.

FuncGGen(λ):

①GRSA←GGen(λ);

②A0←GRSA；

③ returnA0.

FuncAccUpdate(At,tx):

①p=1;

② for eachuintx.inputsdo

③p*=HashToPrime(u);

④ end for

⑥Q←NI_POE_PROVE(At,p,At+1);

⑦ returnAt+1,Q.

FuncAccVerify(At,tx,At+1,Q):

①p=1;

② for eachuintx.inputsdo

③p*=HashToPrime(u);

④ end for

⑤ returnNI_POE_VERIFY(At,p,At+1,Q).

1)Gen(λ)首先根據系統安全參數λ對系統進行初始化，返回累加初始值A0；

2)AccUpdate(At,tx)根據新區塊所消耗的交易輸出，對累加器進行批處理更新.首先，使用HashToPrime對每個交易的輸入進行求質運算，并計算它們的乘積，然后進行冥模運算更新累加值.最后使用非交互式NI-POE協議提交正確更新的證明Q.

3)AccVerify(At,tx,At+1,Q)根據交易和證明Q，使用NI-POE協議驗證累加值是否被正確更新.

其中，NI-POE[10,26]協議允許證明人P向驗證人V證明(u,w,x)滿足w=ux，V只需進行少量計算，便可以相信P進行了正確計算.NI-POE協議能夠很大程度上降低驗證累加器被正確更新的代價.

3.3.2 交易有效性證明生成

交易有效性證明需要包括2個部分：交易輸入的存在性證明和交易輸入的未花費證明.其中，輸入的存在證明可以使用交易輸入產生時的Merkle證明，包含從葉子節點到MTR的路徑.由于不同的交易輸入可能產生于不同的區塊，所以無法對存在性證明進行合并.

交易輸入的未花費證明是對當前STO累加值的非成員見證.由于STO包含了所有已消費的輸入，只要能提供非成員見證，就能證明輸入沒有被消費.具體過程如算法2所示.其中，非成員見證生成算法NonMemWitCreate以UTXO生成時所在區塊的STO累加值作為初始值，獲取之后所有的STO記錄進行求質運行并計算乘積，利用通用累加器的非成員見證生成算法進行生成.類似地，NonMemWitVerify算法對非成員見證進行驗證，具體可以參考Li等人[24]關于通用累加器的非成員見證生成與驗證算法.值得注意的是，交易輸入的未花費證明可以被合并.例如2個分別產生于區塊t與區塊t+1的輸入，我們可以構造一個從區塊t開始的合并證明，因為產生于區塊t+1的輸入并不能提前被消費.

算法2.證明生成、更新和驗證算法.

FuncNonMemWitCreate(An,STOn:m,Am,xn):

①p=1;

②xn←HashToPrime(xn)；

③ for eachstoinSTOn:mdo

④p*=HashToPrime(sto);

⑤ end for

⑥a,b←Bezout(xn,p);

⑧ returnum(xn)←(d,b).

FuncNonMemWitVerify(An,Am,xn，um(xn)):

①xn←HashToPrime(xn)；

②d,b←um(xn)；

FuncNonMemWitUpdate(An,un(xt),x,STOn:m):

①d,b←um(xn),p=1;

② for eachstoinSTOn:mdo

④p*=HashToPrime(sto);

⑤ end for

⑥a0,b0=Bezout(HashToPrime(xt),p);

⑦r=a0b;

3.3.3 交易有效性證明更新

交易輸入的存在性證明使用輸入產生時的Merkle路徑，該證明保持不變，不需要更新.然而，交易輸入的未花費證明是對當前STO集合累加值的非成員見證，當STO累加值更新后，需要同步更新未花費證明.

用戶在發起交易時提交的最新有效性證明，可能會因為網絡傳播延遲或礦工無法及時打包交易，導致交易有效性證明會過期.讓用戶重復提交更新后的有效性證明無疑會增加用戶使用的負擔與體驗.為此，PocketChain引入了STO緩存機制，每個驗證節點保存最近n個區塊(例如 1 h或1 d)的數據以及對應的STO集合，通過驗證輸入存在性證明與未花費證明后，附加驗證輸入不在STO緩存內，從而允許交易在發起后的n個區塊時間內被處理，避免用戶重復提交證明信息.

對于那些長期沒有更新的未花費證明，用戶可以選擇自己更新或交由服務節點更新.用戶自己更新的算法見UpdateNonMemWit，通過獲取上次更新之后所有的STO記錄，逐個區塊地進行更新.然而，在計算資源較少的環境下，更新非成員證明較為耗時.在忽略網路傳輸延遲的情況下，一個2.6 GHz Intel Core i5 處理核心每秒只能處理150個添加操作.因此，我們引入了服務節點，服務節點利用算力為用戶更新證明從而獲得報酬.

4 基于分片的擴容技術

分片技術的主要思想可以簡單描述為分而治之，將單鏈結構拆分為多條并行運行的子鏈(分片)，通過增加分片數量來提升系統的處理能力.分片技術可以分為交易分片和狀態分片.交易分片僅僅實現交易的并行處理，每個節點依然需要保存所有分片的數據.當大量提升系統吞吐后，節點的存儲壓力極具增大.相比之下，狀態分片不僅僅將交易的處理并行化，每個分片只需保存與自己處理交易相關的狀態信息，降低了分片的存儲壓力.然而，為了防止惡意節點集中到某個特定分片發起攻擊，目前的分片技術通常建立在周期性隨機重組的架構下，每次分片重組都需要重新下載新分片的數據和狀態，節點的帶寬開銷增加，并且嚴重限制了分片切換的頻率.為此，本節將無狀態客戶端與分片技術相結合，利用無狀態客戶端低存儲的特點，降低分片切換時的狀態遷移量.介紹了分片周期性隨機重組的系統結構，將分片技術與無狀態客戶端進行結合，消除分片周期性隨機重組導致的狀態遷移問題.

4.1 分片周期性隨機重組

分片技術將全網算力(或權益)劃分為多個部分，每個分片只擁有全網算力的一小部分，為了避免惡意節點集中到某個特定分片發起定向攻擊，目前絕大部分基于分片的擴容技術都采用周期性隨機重組的架構.如圖5所示，每個階段開始，全網節點都會根據上一階段末產生的新的隨機數進行分片重組，節點無法預知它將分配到具體哪個分片中.此外，為了防止分片內節點串通作惡，分片切換的周期越短，系統越安全.

Fig. 5 Periodically reshuffling architecture of sharding圖5 分片周期性隨機重組結構

然而，周期性隨機重組的架構面臨2矛盾：1)在支持狀態分片的情況下，每個分片只保留了當前分片的狀態與數據，當切換到其他分片后，需要重新下載新分片的狀態與數據，這個過程稱為狀態遷移.狀態遷移極大地增加了網絡帶寬開銷，同時也限制了分片切換的頻率；2)在不支持狀態分片的情況下，節點存儲每個分片的狀態與數據，雖然不存在狀態遷移問題，但節點的存儲壓力急劇增大.

4.2 無狀態客戶端降低狀態遷移代價

在第3節中，我們介紹了無狀態客戶端，節點只需要保存區塊頭以及最近n個區塊的數據，不僅降低了節點存儲歷史區塊的開銷，同時將GB級的狀態壓縮到固定的KB級，降低了節點對內存的開銷.在周期性隨機重組的分片架構下，主要面臨分片重組時的狀態遷移問題，無狀態客戶端設計能夠完美解決以上問題.在支持狀態分片的情況下，每次分片切換只需要下載新分片的區塊頭和少量的緩存數據，大大降低狀態遷移代價.此外，由于區塊頭占用極少的存儲空間，驗證節點有能力存儲所有分片的區塊頭，在每次分片重組后，節點可以不進行任何狀態遷移，可以立即切換到新分片開始工作.

5 實驗與結果

在本節中，我們使用本文提供的技術構建了一個輕量級、可擴展的區塊鏈模型PocketChain，并測試了系統的吞吐量和節點的存儲開銷.

5.1 實驗環境與設置

我們基于RSA累加器、Merkle樹以及非成員見證的源碼實現了PocketChain的無狀態客戶端.其中，RSA累加器使用3 072 b的模，素數采用128 b，Merkle節點為32 B，這些參數在密碼領域被公認為安全的.我們使用60個物理節點構建了本地集群，每個節點配置一個8核Intel Xeon E5-1620 3.6 GHz處理器、48 GB內存、3 TB硬盤和10 Gbs的以太網卡.在測試分片的擴展性時，我們使用docker模擬了1 800個節點.

5.2 RSA累加器更新效率

本節我們測試了RSA累加器在未知秘鑰的情況下，針對批量刪除和添加操作的更新效率.累加器的更新效率直接影響了系統的吞吐能力.其中，Boneh使用RSA累加器構建UTXO承諾，需要進行大量刪除操作，而PocketChain使用RSA累加器構建STO承諾，只需要進行添加操作.

圖6展示了PocketChain與Boneh累加器的更新效率對比.實驗結果表明，PocketChain STO承諾的更新效率遠大于Boneh UTXO承諾的更新效率，并且隨著操作數量的增加，性能差距越明顯.例如，當操作數量達到1 000時，Boneh累加器更新時間是PocketChain的50倍.這就導致，依賴于RSA累加器刪除操作的無狀態客戶端設計面臨嚴重的性能問題.

Fig. 6 Performance of accumulator update圖6 累加器更新效率

我們綜合考慮累加器更新效率、交易驗證時間開銷，測試了系統支持的最高吞吐.我們假設每個區塊包含500筆交易，每筆交易有2個輸入和2個輸出.同樣，我們與Boneh的工作進行了對比.實驗結果如表1所示，Boneh由于累加器更新效率低，最高吞吐只能實現3.2 TPS，相比之下，PocketChain能實現100 TPS.

Table 1 A Single Chain Maximum TPS表1 單鏈系統最高吞吐

5.3 單節點存儲

在本節中，我們測試了單鏈環境下節點的存儲壓力.我們獲取了比特幣從2015-01—2019-01的歷史交易數據，并將其運用到PocketChain中.此外，我們將STO緩存設置為1 d，足夠絕大多數交易被處理.

圖7展示了PocketChain和比特幣的內存開銷對比.比特幣內存開銷從2015—2019年增加了4倍，目前已經到達了2.7 GB，相比之下，PocketChain采用無狀態客戶端設計，每個節點只需要保存58 MB(最近一天)的STO緩存數據.

Fig. 7 RAM usage comparison between Bitcoin and PocketChain圖7 比特幣與PocketChain內存使用量對比

Fig. 8 Disk usage comparison between Bitcoin and PocketChain圖8 比特幣與PocketChain磁盤使用量對比

圖8展示了PocketChain與比特幣硬盤使用開銷對比.比特幣需要保存所有歷史區塊的數據，目前已經占用了233 GB的硬盤存儲空間.相比之下，PocketChain只需要保存區塊頭，增長速度緩慢，目前僅需0.27 GB的存儲空間.

5.4 分片擴展能力

本節我們首先測試了分片的擴展能力，然后與最新的分片工作進行了對比，結果如表2所示.其中：k表示分片數量.

在TPS方面，所有的工作都能線性提升系統吞吐.在磁盤消耗方面，OmniLedger采用基于檢查點賬本剪枝技術，只需存儲從上一個檢查點到最近的歷史區塊，能夠大大降低磁盤存儲空間；相比之下，PocketChain僅需要存儲所有歷史區塊頭，由于區塊頭占用極少的存儲空間，依然能有效降低磁盤存儲.

Table 2 Comparison of PocketChain with State-of-the-art Sharding-based Blockchain Protocols表2 PocketChain與最新的分片協議的對比

在內存的消耗方面，OmniLedger，RapidChain，SSChain支持狀態分片，只需存儲1k的狀態，隨著時間的增長，狀態空間依然保持增長.相比之下，PocketChain使用無狀態客戶端，節點只需保存最近n個區塊的狀態信息(MB級)，內存消耗為常數.

在狀態遷移方面，OmniLedger和RapidChain在分片切換時，都需要下載大量狀態信息；SSChain在雙層架構下，利用經濟激勵機制避免了分片重組.PocketChain可以存儲所有分片鏈的區塊頭，分片切換時不需要下載額外數據；在沒有保存其他分片鏈的情況下，也只需要同步區塊頭，大大降低同步帶寬和時間開銷.

5.5 去中心化與安全性分析

PocketChain采用無狀態客戶端來降低節點存儲壓力，節點僅需存儲歷史區塊頭與最近n個區塊，硬盤消耗增長緩慢，內存開銷固定，大大降低了運行一個礦工節點和驗證節點的存儲成本，去中心化程度得到提升.相比之下，目前的公有鏈，例如比特幣和以太坊，硬盤和內存資源消耗隨著時間快速增長，運行礦工節點和驗證節點的成本不斷增加，可以預測在不久的將來，只有少數“超級”節點能夠完成交易的驗證，系統中心化程度逐漸增加.

在安全性方面，使用Class Group構建RSA累加器，避免了可信第三方的初始化設置.此外，分片重組頻率與分片系統的安全性密切相關，在賄賂攻擊模型下，惡意節點可以通過賄賂改變任何誠實節點的行為.假設全網節點數量為m，分片數量為n，惡意節點數量為k，分片切換周期為x.在隨機分組下，每個分片初始分配的惡意節點數量為kn.假設攻擊者平均每t時間成功賄賂1個誠實節點，那么必須保證:

PocketChain將無狀態客戶端運用于分片技術架構下，由于無狀態客戶端低存儲的特點，降低了分片周期性隨機重組導致的狀態遷移代價，從而可以提升分片重組頻率，進一步增加分片系統的安全性.

6 結論與下一步工作

本文聚焦于公有鏈低吞吐和數據增長問題，提出了一種面向UTXO模型的輕量級、可擴展的公有鏈PocketChain.首先，PocketChain使用具有批處理能力的RSA累加器構建無狀態客戶端，驗證節點只需保存歷史區塊頭和最近的n個區塊，避免存儲大量歷史區塊和狀態信息.然后，將無狀態客戶端運用于分片技術架構下，一方面通過增加分片數量，能大大提升系統的處理能力；另一方面，由于無狀態客戶端低存儲的特點，克服了分片周期性隨機重組導致的狀態遷移問題，從而能進一步提升分片重組頻率，增加分片系統安全性.實驗結果表明，本文提出的PocketChain能有效解決驗證節點存儲增長問題，并降低分片技術周期性隨機重組導致的狀態遷移代價.

本文提出的將無狀態客戶端與分片技術相結合的方法，還遺留2個問題有待進一步研究：1)針對服務提供者提出恰當的經濟激勵機制.對于那些長久沒有更新未消費證明的用戶，他們依賴服務提供者的計算服務，如何激勵服務提供者為用戶服務是一個有待解決的經濟問題；2)進一步降低見證更新頻率.基于RSA累加器的狀態壓縮方法，每次累加值更新后，對應的(非)成員見證都需要同步更新.雖然PocketChain引入了緩存機制，僅僅避免了在交易沒被及時處理的情況下頻繁更新見證的問題.如何設計更優秀的累加器、降低見證的更新頻率，是一個非常值得研究的方向.