王守道，蔣玉明，胡大裟

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065）

0 引言

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

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

通過以太坊提供的編程語Solidity（https://solidity.readthedocs.io/）編寫的智能合約經(jīng)過編譯后以字節(jié)碼的形式存儲(chǔ)在區(qū)塊鏈平臺(tái)上，字節(jié)碼可以被以太坊虛擬機(jī)（Ethereum Virtual Machine，EVM）解釋后執(zhí)行。用戶在執(zhí)行智能合約時(shí)需要向區(qū)塊鏈網(wǎng)絡(luò)中負(fù)責(zé)處理交易的節(jié)點(diǎn)支付一定數(shù)量gas作為手續(xù)費(fèi)，收取費(fèi)用是為了防止惡意節(jié)點(diǎn)生成大量無效的交易對(duì)區(qū)塊鏈網(wǎng)絡(luò)發(fā)起 DDoS（Distributed Denial of Service）攻擊。

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

1 相關(guān)研究

為了減少以太坊平臺(tái)上存儲(chǔ)的數(shù)據(jù)總量，加快節(jié)點(diǎn)加入?yún)^(qū)塊鏈網(wǎng)絡(luò)的速度，以太坊社區(qū)的研究者從不同的角度提出了一些用于減少區(qū)塊鏈上的數(shù)據(jù)的方法。其中節(jié)點(diǎn)同步是基于節(jié)點(diǎn)的功能定位，為節(jié)點(diǎn)設(shè)置不同的同步數(shù)據(jù)量，讓輕節(jié)點(diǎn)可以快速加入?yún)^(qū)塊鏈網(wǎng)絡(luò)并參與交易；而節(jié)點(diǎn)分片是基于分治的思想，將區(qū)塊鏈的節(jié)點(diǎn)劃分到不同的分片中，每個(gè)分片中的節(jié)點(diǎn)只需要參與分片內(nèi)的交易，減輕了節(jié)點(diǎn)的負(fù)擔(dān)，同時(shí)提升了整個(gè)區(qū)塊鏈上的交易處理速能力。

1. 1 節(jié)點(diǎn)同步

以太坊平臺(tái)上的節(jié)點(diǎn)可以自由的加入或退出區(qū)塊鏈網(wǎng)絡(luò)，在同步完區(qū)塊鏈上所有的數(shù)據(jù)之后才可以發(fā)起交易，以太坊平臺(tái)運(yùn)行初期區(qū)塊鏈上的數(shù)據(jù)量很少，節(jié)點(diǎn)可以在短時(shí)間內(nèi)完成數(shù)據(jù)同步。隨著區(qū)塊鏈技術(shù)關(guān)注熱度的提升，以太坊平臺(tái)上的智能合約與關(guān)聯(lián)的交易數(shù)量也在快速增長，區(qū)塊鏈上存儲(chǔ)的數(shù)據(jù)急劇增加，導(dǎo)致新節(jié)點(diǎn)同步數(shù)據(jù)需要的存儲(chǔ)空間越來越多，消耗在同步數(shù)據(jù)上的時(shí)間越來越長。為了使新節(jié)點(diǎn)可以快速加入?yún)^(qū)塊鏈網(wǎng)絡(luò)，以太坊中定義了多種類型的節(jié)點(diǎn)，這些節(jié)點(diǎn)采用不同的同步策略來同步區(qū)塊鏈上的數(shù)據(jù)[5]。節(jié)點(diǎn)按同步模式可歸納為以下三種類型：

●全同步模式：節(jié)點(diǎn)需從創(chuàng)世區(qū)塊開始同步所有區(qū)塊中的數(shù)據(jù)，并對(duì)區(qū)塊中的所有交易進(jìn)行執(zhí)行與驗(yàn)證。

●快同步模式：節(jié)點(diǎn)以快照的形式同步歷史數(shù)據(jù)，在同步到當(dāng)前區(qū)塊之前不處理任何交易，之后像全同步節(jié)點(diǎn)一樣運(yùn)行。

●輕同步模式：節(jié)點(diǎn)只獲取當(dāng)前區(qū)塊的狀態(tài)，如要執(zhí)行交易則需要與網(wǎng)絡(luò)中的全同步節(jié)點(diǎn)進(jìn)行交互。

1. 2 節(jié)點(diǎn)分片

以太坊中節(jié)點(diǎn)分片[6]源于數(shù)據(jù)庫中的分片技術(shù)，數(shù)據(jù)庫中將數(shù)據(jù)表進(jìn)行水平切分后存儲(chǔ)在不同的數(shù)據(jù)庫服務(wù)器上，可以加快數(shù)據(jù)的存取速度。以太坊中則是將整個(gè)網(wǎng)絡(luò)狀態(tài)分為進(jìn)行分片，分片系統(tǒng)由校驗(yàn)器（Validator Manager Contract，VMC）合約負(fù)責(zé)維護(hù)。每個(gè)分片都是一個(gè)單獨(dú)的區(qū)域，分片中的交易處理能力與原區(qū)塊鏈中的處理能力相同，因此區(qū)塊鏈的交易處理速度會(huì)線性增長。分片內(nèi)的節(jié)點(diǎn)可以作為全節(jié)點(diǎn)和輕節(jié)點(diǎn)運(yùn)行，輕節(jié)點(diǎn)在執(zhí)行交易的時(shí)候需要通過RPC（Remote Procedure Call）在全節(jié)點(diǎn)獲取必要的數(shù)據(jù)信息。分片雖然可以加快區(qū)塊鏈的交易速度減輕節(jié)點(diǎn)的負(fù)擔(dān)，但是處理跨分片的交易能力較差，安全方面也有潛在的風(fēng)險(xiǎn)。

2 壓縮存儲(chǔ)方法

2. 1 操作碼定義

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

表1

opcode：為了和EVM中已經(jīng)存在的操作碼進(jìn)行區(qū)分，將COMPRESS的值設(shè)置為“0xf5”；

block height：作為指針的智能合約在區(qū)塊鏈中的位置，當(dāng)前區(qū)塊鏈的區(qū)塊為6502231；

tx index：智能合約在創(chuàng)建時(shí)生成的交易處于區(qū)塊中的位置；

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

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

在上述的結(jié)構(gòu)中，使用9 bytes的長度的指針用于替換智能合約中的字節(jié)碼，被替換的字節(jié)碼的長度應(yīng)大于指針的長度。

2. 2 智能合約分類

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

圖1 智能合約的分類流程

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

2. 3 相同片段計(jì)算

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

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

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

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

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

（2）對(duì)合成的字符串構(gòu)造后綴數(shù)SA和名次數(shù)Rank，SA與Rank[10]為互逆運(yùn)算，使SA和Rank將后綴數(shù)組按字典序進(jìn)行排列；

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

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

2. 4 字節(jié)碼替換

計(jì)算出智能合約字節(jié)碼之間存在的公共連續(xù)子串后，需要恰當(dāng)?shù)倪x取部分子串對(duì)智能合約進(jìn)行壓縮。為了確定哪些子串可以作為指針替換對(duì)應(yīng)合約的字節(jié)碼，定義了一些參數(shù)用于篩選這些子串：

臨近合約數(shù)量k：用于與目標(biāo)合約計(jì)算公共字節(jié)碼片段的智能合約數(shù)量，即在目標(biāo)合約以前的部署的k個(gè)合約才會(huì)作為候選合約。

替換指針數(shù)量p：每個(gè)智能合約可以被替換的子串?dāng)?shù)量的上限，p并不是越大越好，p值過大智能合約還原需要的時(shí)間也會(huì)變長；

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

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

在智能合約執(zhí)行的時(shí)候，EVM會(huì)如同處理操作碼CALLCODE一樣對(duì)指針進(jìn)行處理，即把指針還原成對(duì)應(yīng)的字節(jié)碼。由于指針代表的字節(jié)碼存儲(chǔ)在其他智能合約中，因此需要提前將部署在它前面的k個(gè)合約的字節(jié)碼讀取出來，然后目標(biāo)合約中的所有指針進(jìn)行轉(zhuǎn)換，最后拼接成完整的可執(zhí)行的智能合約。

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

3 實(shí)驗(yàn)與結(jié)果分析

本次實(shí)驗(yàn)環(huán)境為：CPU為Intel Core i5 6300HQ，主頻為2.30GHz，內(nèi)存為8GB，操作系統(tǒng)為Windows 10。

實(shí)驗(yàn)數(shù)據(jù)是從etherscan.io上下載的1210個(gè)有開源的代碼信息的智能合約，經(jīng)過分類處理后，各種類別的智能合約比例如圖2所示。

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

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

圖3 臨近合約數(shù)量為10的壓縮率

圖4 臨近合約數(shù)量為50的壓縮率

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

4 結(jié)語

本文提出的對(duì)智能合約壓縮存儲(chǔ)方法，通過對(duì)存儲(chǔ)在以太坊區(qū)塊鏈上的智能合約字節(jié)碼進(jìn)行重用，使智能合約的存儲(chǔ)空間可以節(jié)省近47%，對(duì)智能合約分類后的壓縮效果明顯優(yōu)于分類前的壓縮效果。智能合約在經(jīng)過壓縮存儲(chǔ)后，不僅可以減少區(qū)塊鏈上存儲(chǔ)的數(shù)據(jù)，還可以減輕節(jié)點(diǎn)同步數(shù)據(jù)的負(fù)擔(dān)，使節(jié)點(diǎn)可以更快地加入?yún)^(qū)塊鏈網(wǎng)絡(luò)。