基于區塊鏈的智能合約壓縮存儲方法

王守道，蔣玉明，胡大裟

（四川大學計算機學院，成都610065）

0 引言

區塊鏈（Blockchain）最早出現在中本聰發表的論文《比特幣：一種點對點的電子現金系統》中[1]，它是一種基于加密算法、時間戳、梅克爾樹（Merkle tree）和共識機制實現的分布式數據管理技術，主要特點有去中心化、數據可追溯、不可篡改，并在以比特幣（Bitcoin）和以太坊（Ethereum）為代表的區塊鏈平臺上得到了應用[2]。

智能合約（Smart Contract）的概念由尼克·薩博在1994年提出，由于智能合約在提出的初期缺少特定的編程腳本和可信的運行環境，因此并未受到廣泛關注，區塊鏈技術的橫空出世與其天然適用于智能合約的特性重新定義了智能合約。以太坊是一個基于公有鏈的區塊鏈平臺，除了擁有類似于比特幣等數字加密貨幣的轉賬功能外，還提供了圖靈完備的編程語言并為智能合約的編寫、編譯、部署與運行提供了良好的條件[3]。

通過以太坊提供的編程語Solidity（https://solidity.readthedocs.io/）編寫的智能合約經過編譯后以字節碼的形式存儲在區塊鏈平臺上，字節碼可以被以太坊虛擬機（Ethereum Virtual Machine，EVM）解釋后執行。用戶在執行智能合約時需要向區塊鏈網絡中負責處理交易的節點支付一定數量gas作為手續費，收取費用是為了防止惡意節點生成大量無效的交易對區塊鏈網絡發起 DDoS（Distributed Denial of Service）攻擊。

比特幣中每個區塊的大小為1M，而以太坊中區塊的大小由區塊中可供消耗的gas數量決定，因此以太坊中每個區塊的大小是不固定的。智能合約的可重用性是初期提出的設想，通過在區塊鏈上部署特定功能的合約，并將其作為一個子模塊提供給其他合約使用，從而實現功能更多樣化的智能合約，目前以太坊區塊鏈平臺上已經部署了超過60萬個智能合約[4]。本文提出了一種對部署在區塊鏈上的智能合約的壓縮存儲方法，通過將智能合約間相同的字節碼片段進行重復利用，達到減小區塊鏈數據量的目的。

1 相關研究

為了減少以太坊平臺上存儲的數據總量，加快節點加入區塊鏈網絡的速度，以太坊社區的研究者從不同的角度提出了一些用于減少區塊鏈上的數據的方法。其中節點同步是基于節點的功能定位，為節點設置不同的同步數據量，讓輕節點可以快速加入區塊鏈網絡并參與交易；而節點分片是基于分治的思想，將區塊鏈的節點劃分到不同的分片中，每個分片中的節點只需要參與分片內的交易，減輕了節點的負擔，同時提升了整個區塊鏈上的交易處理速能力。

1. 1 節點同步

以太坊平臺上的節點可以自由的加入或退出區塊鏈網絡，在同步完區塊鏈上所有的數據之后才可以發起交易，以太坊平臺運行初期區塊鏈上的數據量很少，節點可以在短時間內完成數據同步。隨著區塊鏈技術關注熱度的提升，以太坊平臺上的智能合約與關聯的交易數量也在快速增長，區塊鏈上存儲的數據急劇增加，導致新節點同步數據需要的存儲空間越來越多，消耗在同步數據上的時間越來越長。為了使新節點可以快速加入區塊鏈網絡，以太坊中定義了多種類型的節點，這些節點采用不同的同步策略來同步區塊鏈上的數據[5]。節點按同步模式可歸納為以下三種類型：

●全同步模式：節點需從創世區塊開始同步所有區塊中的數據，并對區塊中的所有交易進行執行與驗證。

●快同步模式：節點以快照的形式同步歷史數據，在同步到當前區塊之前不處理任何交易，之后像全同步節點一樣運行。

●輕同步模式：節點只獲取當前區塊的狀態，如要執行交易則需要與網絡中的全同步節點進行交互。

1. 2 節點分片

以太坊中節點分片[6]源于數據庫中的分片技術，數據庫中將數據表進行水平切分后存儲在不同的數據庫服務器上，可以加快數據的存取速度。以太坊中則是將整個網絡狀態分為進行分片，分片系統由校驗器（Validator Manager Contract，VMC）合約負責維護。每個分片都是一個單獨的區域，分片中的交易處理能力與原區塊鏈中的處理能力相同，因此區塊鏈的交易處理速度會線性增長。分片內的節點可以作為全節點和輕節點運行，輕節點在執行交易的時候需要通過RPC（Remote Procedure Call）在全節點獲取必要的數據信息。分片雖然可以加快區塊鏈的交易速度減輕節點的負擔，但是處理跨分片的交易能力較差，安全方面也有潛在的風險。

2 壓縮存儲方法

2. 1 操作碼定義

在以太坊中定義了多種操作碼用于表示智能合約在EVM中的運行流程[3]，文中模仿CALLCODE定義了一個新的操作碼COMPRESS。COMPRESS的功能定義為：在一個新合約的字節碼即將部署在區塊鏈上時，通過對比它和已經部署在區塊鏈上的舊合約字節碼尋找它們的公共連續子串，并用舊合約上的子串作為指針來代替新合約中的子串。在智能合約執行時，當EVM檢測到操作碼COMPRESS后會將指針還原為具體的字節碼然后繼續向下執行。為了使COMPRESS操作有意義，指針的長度必須小于子串的長度，這樣才能對智能合約進行有效壓縮。為此對COMPRESS的結構定義如表1。

表1

opcode：為了和EVM中已經存在的操作碼進行區分，將COMPRESS的值設置為“0xf5”；

block height：作為指針的智能合約在區塊鏈中的位置，當前區塊鏈的區塊為6502231；

tx index：智能合約在創建時生成的交易處于區塊中的位置；

string start：作為指針的子串在字節碼中的起始下標，自從EIP150[7]中規定了智能合約的長度不超過0x6000或24576 bytes，這意味著2 bytes足夠表示智能合約字節碼中所有位置的起始下標；

string size：作為指針的子串長度；

在上述的結構中，使用9 bytes的長度的指針用于替換智能合約中的字節碼，被替換的字節碼的長度應大于指針的長度。

2. 2 智能合約分類

以太坊區塊鏈提供了公開智能合約源代碼的功能，在以太坊平臺上有部分智能合約的源代碼可供查看。對于從Ethereum Blockchain Explorer（https://etherscan.io/）爬取的智能合約源代碼與字節碼構建的數據集，源代碼比編譯后的字節碼有更好的可讀性、易于對智能合約分出類別，因此使用智能合約的源代碼對其進行分類處理。

圖1 智能合約的分類流程

為了對智能合約分類，設計了如圖1所示的分類流程，用于快速地對智能合約進行標記。首先爬取了文獻[8]中指明的GitHub上以太坊智能合約的公共代碼庫；然后將從etherscan.io上爬取的智能合約與公共代碼庫進行相似度分析，如果合約間的字符串相似度較高則通過人工閱讀README等信息為智能合約添加類標簽，否則通過直接閱讀源代碼的方式為智能合約添加類標簽；最后根據智能合約的類標簽，將對應的字節碼進行分類處理。

2. 3 相同片段計算

在對智能合約中的字節碼進行替換時只能在先部署的智能合約中選取合適長度的字節碼片段去取代后部署的智能合約中相同的字節碼片段，因此需要對獲取的智能合約的字節碼按其部署在區塊鏈上的時間進行排序。計算智能合約序列中臨近合約間相同字節碼片段的問題可以認為是求字符串的最長公共子串（Longest Common Substring，LCS）的簡單擴展。這個問題可以定義如下：

給定一個智能合約序列{C0,C1,…,Cn-1,Cn}，為了對其中的智能合約Ci進行壓縮，需要計算Ci與{Ci-k,…,Ci-2,Ci-1}i-k≥0}中每個智能合約字節碼的公共連續子串LCS。

給定∑表示字符串的集合，給定兩個字符串s1,s2∈∑，它們的公共連續子串集合 ω1,ω2可以定義為：

計算LCS的算法主要有動態規劃（Dynamic Programming）、廣義后綴樹（General Suffix Tree）和后綴數組（Suffix Array）。動態規劃算法實現簡單但是計算效率低，適用于短串；廣義后綴樹算法雖然計算復雜度是線性的，但是原理比較復雜，代碼實現困難；后綴數組算法的計算復雜度略高于后綴樹算法，但它占用的內存空間會小很多，而且實現起來也更為容易。使用基于后綴數組的最長公共前綴（Longest Common Prefix，LCP）[9]來計算智能合約相同字節碼片段的具體步驟如下：

（1）將字符串 s1和 s2拼接為一個新的字符串“ s1#s2”，其中“#”是在 s1和 s2中均未出現過的一個字符；

（2）對合成的字符串構造后綴數SA和名次數Rank，SA與Rank[10]為互逆運算，使SA和Rank將后綴數組按字典序進行排列；

（3）定義一個元組( )s1,s2,p1,p2,size 來表示后綴數組中相鄰子串的LCP，其中 p1,p2分別為LCP在s1,s2中起始處的下標，size表示LCP的長度；

（4）對LCP數組進行剪枝操作，首先將LCP數組按size從小到大排序，然后對數組進行遍歷，對于子串ωi如果數組中存在相應的元素(s1,s2,p1+1,p2+1,size-1)，則將當前元素從數組中移除。

2. 4 字節碼替換

計算出智能合約字節碼之間存在的公共連續子串后，需要恰當的選取部分子串對智能合約進行壓縮。為了確定哪些子串可以作為指針替換對應合約的字節碼，定義了一些參數用于篩選這些子串：

臨近合約數量k：用于與目標合約計算公共字節碼片段的智能合約數量，即在目標合約以前的部署的k個合約才會作為候選合約。

替換指針數量p：每個智能合約可以被替換的子串數量的上限，p并不是越大越好，p值過大智能合約還原需要的時間也會變長；

公共子串長度t：作為被自定義的操作碼替換的子串的最小長度，如果用16 bytes的操作碼去替換17 bytes的字符串顯然是不值得的，t的大小會影響替換合約的數量和智能合約的壓縮率。

為了確保作為指針的子串在原字符串中存在且處于連續的位置，如果字符串s1中的子串ω1作為指針去替換字符串s2中的子串ω2，那么字符串s2中的子串ω2就不會作為指針去替換字符串s3中的子串ω3，這樣就不會出現指針替換指針的情況，智能合約的還原時間也可以得到保證。

在智能合約執行的時候，EVM會如同處理操作碼CALLCODE一樣對指針進行處理，即把指針還原成對應的字節碼。由于指針代表的字節碼存儲在其他智能合約中，因此需要提前將部署在它前面的k個合約的字節碼讀取出來，然后目標合約中的所有指針進行轉換，最后拼接成完整的可執行的智能合約。

在一個子串作為指針替換了其他合約中的子串后，與這兩個合約相關的子串的可用性會受到影響，部分子串會變得不可用，導致智能合約的壓縮效果會變差。以合理的順序選取子串進行替換有利于提升智能合約字節碼的壓縮率，本文以長度優先的規則去將子串作為指針去進行替換，因此在替換開始需要將子串按照長度進行排序。

3 實驗與結果分析

本次實驗環境為：CPU為Intel Core i5 6300HQ，主頻為2.30GHz，內存為8GB，操作系統為Windows 10。

實驗數據是從etherscan.io上下載的1210個有開源的代碼信息的智能合約，經過分類處理后，各種類別的智能合約比例如圖2所示。

在將智能合約分類后，按照圖2中的類別順序將智能合約進行排序。使用基于后綴數組的最長前綴算法計算智能合約字節碼間的相同子串，在向前查找智能合約數量為10的平均查找時間為1.7s，當查找數量增加到50時平均查找時間為5.8s。圖3和圖4分別是向前查找智能合約數量為10和50的分類前后的壓縮率對比。由圖中可知，最早部署的智能合約字節碼是不會被替換的，隨著區塊鏈上智能合約的增加，可作為指針進行字節碼替換的字符串數量也在變多，智能合約的壓縮率就逐漸增高并在一定數量之后趨于平穩。在向前查找智能合約數量為10和50時，分類后智能合約壓縮率分別為28%和47%，比起分類前的壓縮率分別高出6%和11%。隨著向前查找合約數量的增加，智能合約的壓縮效果在逐漸變好，從而字節碼在區塊鏈上存儲需要的空間會減少，同時分類后與分類前的智能合約壓縮效果差距也在變大。

在字節碼替換時對每個智能合約可被替換的指針數量無限制的情況下，字節碼替換完后每個智能合約被替換的字節碼片段數量分布如圖5所示，大多數合約被替換的字節碼片段數量在0到40之間。

圖3 臨近合約數量為10的壓縮率

圖4 臨近合約數量為50的壓縮率

圖5 智能合約壓縮后的替換指針數量

4 結語

本文提出的對智能合約壓縮存儲方法，通過對存儲在以太坊區塊鏈上的智能合約字節碼進行重用，使智能合約的存儲空間可以節省近47%，對智能合約分類后的壓縮效果明顯優于分類前的壓縮效果。智能合約在經過壓縮存儲后，不僅可以減少區塊鏈上存儲的數據，還可以減輕節點同步數據的負擔，使節點可以更快地加入區塊鏈網絡。