王勁松,呂志梅,趙澤寧,張洪瑋

(天津理工大學(xué) a.計(jì)算機(jī)科學(xué)與工程學(xué)院; b.天津市智能計(jì)算及軟件新技術(shù)重點(diǎn)實(shí)驗(yàn)室;c.計(jì)算機(jī)病毒防治技術(shù)國(guó)家工程實(shí)驗(yàn)室,天津 300457)

0 概述

比特幣自2009年問(wèn)世以來(lái),就因具有分布式、匿名性、可溯源等與傳統(tǒng)貨幣不同的特征而發(fā)展迅速,此后各種類似的加密貨幣也隨之出現(xiàn)。根據(jù)CoinMarketCap的統(tǒng)計(jì)數(shù)據(jù),到2019年4月加密貨幣種類已經(jīng)超過(guò)2 100種。比特幣本質(zhì)是一種基于區(qū)塊鏈的分布式賬本,系統(tǒng)中所有用戶通過(guò)基于公鑰的錢包地址進(jìn)行點(diǎn)對(duì)點(diǎn)的直接交易,無(wú)需通過(guò)任何中心化金融機(jī)構(gòu),所有交易記錄都不可篡改地永久記錄在區(qū)塊鏈上[1-2],交易只與雙方的錢包地址有關(guān),與錢包所有人的真實(shí)身份沒(méi)有直接聯(lián)系,以此來(lái)保護(hù)用戶隱私。比特幣在保護(hù)用戶隱私的同時(shí)也常被用于異常交易活動(dòng),并且給追蹤這些交易團(tuán)體增大了難度。通過(guò)分析交易數(shù)據(jù),可以發(fā)現(xiàn)交易特征并識(shí)別實(shí)體[3-4],同時(shí)推測(cè)實(shí)體類型并發(fā)現(xiàn)實(shí)體之間的聯(lián)系,進(jìn)而對(duì)交易數(shù)據(jù)進(jìn)行可視分析,幫助研究人員更好地感知區(qū)塊鏈交易信息,分析交易中的安全事件。

文獻(xiàn)[5-9]針對(duì)比特幣地址聚類和實(shí)體識(shí)別進(jìn)行研究。文獻(xiàn)[5]利用Petri網(wǎng)對(duì)比特幣網(wǎng)絡(luò)進(jìn)行建模,把所有交易地址和交易映射為矩陣的行和列,通過(guò)分析矩陣來(lái)解決比特幣實(shí)體識(shí)別的問(wèn)題,但是如果交易數(shù)量過(guò)多,會(huì)造成矩陣維數(shù)過(guò)大,這是此方法的不足。文獻(xiàn)[6]提出一個(gè)模塊化的框架BitIodine,通過(guò)解析區(qū)塊鏈和可能屬于同一個(gè)實(shí)體的地址,對(duì)這些實(shí)體分類并貼上標(biāo)簽。文獻(xiàn)[7]對(duì)用戶的交易規(guī)律進(jìn)行抽象,提出一種基于參數(shù)的身份識(shí)別方法,能夠有效識(shí)別匿名區(qū)塊鏈地址對(duì)應(yīng)的真實(shí)用戶身份。文獻(xiàn)[8]通過(guò)分析比特幣交易數(shù)據(jù),基于實(shí)體識(shí)別對(duì)勒索軟件CryptoLocker的攻擊行為進(jìn)行分析。文獻(xiàn)[9]通過(guò)設(shè)計(jì)模擬實(shí)驗(yàn),采用基于行為的聚類技術(shù)對(duì)比特幣交易數(shù)據(jù)進(jìn)行分析,能夠匹配40%的用戶身份和地址。

上述研究都認(rèn)為如果比特幣一條交易中包括多個(gè)輸入地址,那么這些地址都屬于同一實(shí)體,把這一條件作為啟發(fā)式聚類條件,在實(shí)體識(shí)別和進(jìn)一步數(shù)據(jù)分析方面能夠取得很好的效果。文獻(xiàn)[10]分析得到這種啟發(fā)式聚類方法有效的主要原因,即地址重用、可避免的合并、具有高中心性的超級(jí)集群以及地址集群的增量增長(zhǎng)。文獻(xiàn)[11]提出將多輸入地址和找零地址結(jié)合作為啟發(fā)式條件進(jìn)行聚類的方法,并通過(guò)大量實(shí)驗(yàn)驗(yàn)證方法的準(zhǔn)確性和全面性,同時(shí)分析實(shí)驗(yàn)迭代次數(shù)對(duì)聚類效率的影響。文獻(xiàn)[12]對(duì)20個(gè)月中生成的交易進(jìn)行分析,將35 770 360個(gè)地址聚類為13 062 822個(gè)集合,但未對(duì)聚類后的實(shí)體及其之間的聯(lián)系進(jìn)一步分析。文獻(xiàn)[13]提出一個(gè)基于圖的數(shù)據(jù)挖掘工具對(duì)比特幣交易數(shù)據(jù)進(jìn)行可視分析,實(shí)現(xiàn)了對(duì)任意給定的一個(gè)或一組地址的局部聚類,適用于對(duì)已知事件中的地址進(jìn)行詳細(xì)行為和關(guān)聯(lián)分析,但聚類結(jié)果沒(méi)有與實(shí)體類型聯(lián)系。

上述方法都是基于某一時(shí)段的比特幣交易數(shù)據(jù)進(jìn)行聚類,沒(méi)有對(duì)實(shí)體的演變情況進(jìn)行分析。為此,本文提出一種基于比特幣交易數(shù)據(jù)特征的地址增量聚類方法。采集比特幣的區(qū)塊流數(shù)據(jù)對(duì)原始流數(shù)據(jù)進(jìn)行解析和結(jié)構(gòu)化處理,提取符合聚類條件的交易和地址形成聚類地址組,并通過(guò)散列函數(shù)生成聚類地址組的數(shù)據(jù)索引,獲得聚類地址組之間的聚合關(guān)系。在此基礎(chǔ)上,利用并查集算法實(shí)現(xiàn)對(duì)此關(guān)系的增量聚類以發(fā)現(xiàn)交易實(shí)體,進(jìn)而對(duì)交易數(shù)據(jù)進(jìn)行重標(biāo)記和再分析,得到比特幣實(shí)體間的的交易特征。此外,本文通過(guò)對(duì)聚類過(guò)程中各階段實(shí)體的特點(diǎn)及實(shí)體間交易聯(lián)系進(jìn)行可視分析,得到地址增量聚類過(guò)程中實(shí)體的變化特征。

1 增量聚類方法

基于比特幣交易數(shù)據(jù)的地址增量聚類方法主要包括數(shù)據(jù)采集及數(shù)據(jù)預(yù)處理、聚合關(guān)系集合獲取、數(shù)據(jù)增量聚類和存儲(chǔ)聚類4個(gè)部分。

1.1 數(shù)據(jù)采集及預(yù)處理

本文通過(guò)配置區(qū)塊鏈環(huán)境和搭建比特幣客戶端Bitcoin Core,將區(qū)塊流數(shù)據(jù)同步到本地,Dt表示截止至t時(shí)刻的所有區(qū)塊數(shù)據(jù)。

當(dāng)生成新區(qū)塊后,將新的區(qū)塊數(shù)據(jù)同步到本地,Dt′-t表示t到t′時(shí)刻之間產(chǎn)生的區(qū)塊數(shù)據(jù)。同步到本地的區(qū)塊數(shù)據(jù)Dt是二進(jìn)制流數(shù)據(jù),圖1所示為創(chuàng)世區(qū)塊的十六進(jìn)制格式的數(shù)據(jù)。為進(jìn)一步實(shí)驗(yàn),通過(guò)分析區(qū)塊的數(shù)據(jù)結(jié)構(gòu)[14-15],對(duì)原始流數(shù)據(jù)Dt解析和結(jié)構(gòu)化處理[16],得到比特幣交易數(shù)據(jù)集St,St=Json(Dt),該數(shù)據(jù)集為t時(shí)刻之前的區(qū)塊數(shù)據(jù)經(jīng)過(guò)處理后得到的結(jié)構(gòu)化數(shù)據(jù)。圖2所示為創(chuàng)世區(qū)塊經(jīng)過(guò)處理后的交易數(shù)據(jù)。

圖1 創(chuàng)世區(qū)塊原始數(shù)據(jù)Fig.1 Original data of genesis block

圖2 創(chuàng)世區(qū)塊結(jié)構(gòu)化數(shù)據(jù)Fig.2 Structured data of genesis block

基于比特幣交易數(shù)據(jù)集提取用于增量聚類的可聚類交易T。T必須滿足以下條件:交易T不是挖礦交易;交易T包含兩個(gè)以上不同的輸入地址?？删垲惤灰字械牡刂芳礊榫垲惖刂方M,用ci標(biāo)識(shí),i為一個(gè)自增的整數(shù),Ct為t時(shí)刻之前生成的ci。

圖3所示為兩例可聚類交易模型(地址的顏色不同表示地址所屬實(shí)體不同),其中,聚類地址組表示為c0={a1,a2},c1={a1,a6,a8}。

圖3 可聚類交易模型Fig.3 Clustered transaction models

1.2 聚合關(guān)系集合獲取

基于聚類地址組Ct通過(guò)散列函數(shù)生成哈希表Ht,其中,k為地址,v為地址所屬組。當(dāng)讀取到已存在于Ht的地址但地址所屬組與Ht中對(duì)應(yīng)的值不一致時(shí),說(shuō)明這兩個(gè)地址組間存在聚合關(guān)系,其中地址屬于同一實(shí)體,聚合關(guān)系用(rc0,rc1)表示,將t時(shí)刻之前的所有聚合關(guān)系放入集合Rt中:

Ht,c={vt,c|c∈Ct,c=kt}

Rt={(rc0,rc1)|c0,c1∈Ct,Ht,c0≠Ht,c1}

其中,(rc0,rc1)表示關(guān)系對(duì)中的聚類地址組。關(guān)系集合生成算法描述如下:

算法1聚合關(guān)系集合生成算法

輸入t時(shí)刻之前所有聚類地址組Ct

輸出哈希表Ht,聚合關(guān)系集合Rt

for ciin Ctdo

for a in cido

if a as in Ht.k and Ht[a].v≠cithen

(rc0,rc1)←(Ht[a].v,ci)

將聚合關(guān)系(rc0,rc1)添加到Rt中

else

Ht[a].v=ci

end

end

例如圖3交易中的聚類地址組有c0、c1,地址a1在c0中也在c1中,經(jīng)過(guò)算法1處理后,Ht中{a1:c0}更新為{a1:c1},同時(shí)生成一個(gè)聚合關(guān)系r:(c0,c1),存儲(chǔ)最終生成的聚合關(guān)系集合,同時(shí)輸入并查集算法進(jìn)行聚類。

1.3 增量聚類

由于區(qū)塊鏈數(shù)據(jù)是增量的,傳統(tǒng)聚類方法需要獲取創(chuàng)世區(qū)塊到當(dāng)前區(qū)塊的所有關(guān)系集合進(jìn)行聚類,會(huì)導(dǎo)致效率下降,因此本文基于聚類地址組間聚合關(guān)系通過(guò)并查集算法實(shí)現(xiàn)實(shí)體增量聚類。并查集是一種樹(shù)型的數(shù)據(jù)結(jié)構(gòu),常用于判斷兩個(gè)子集是否屬于同一集合以及按照一定順序?qū)儆谕患系淖蛹喜?時(shí)間復(fù)雜度是線性的,適用于解決數(shù)據(jù)量大的應(yīng)用問(wèn)題,基本操作包括初始化、查找、合并。

初始化集合G,集合中的元素為聚類地址組的標(biāo)識(shí)名稱ci。由于比特幣交易數(shù)據(jù)量較大,因此采用路徑壓縮方法優(yōu)化查詢操作,查詢函數(shù)Find(x)如下:

其中,x為G中的元素。執(zhí)行查找函數(shù)后的兩個(gè)元素若屬于不同集合則將其合并,合并函數(shù)Union(x,y)如下:

初始集合和結(jié)果集合同一位置的元素屬于同一集合,元素相同的個(gè)數(shù)代表聚類后實(shí)體的數(shù)量,因此,通過(guò)并查集算法可以對(duì)比特幣交易數(shù)據(jù)中的所有聚類地址組進(jìn)行聚類。基于聚合關(guān)系的并查集算法描述如下:

算法2基于聚合關(guān)系的并查集算法

輸入關(guān)系集合Rt

輸出并查集G

初始化數(shù)組G

if Rt≠? then

for (rc0,rc1) in Rtdo

Find(ci),Find(cj)

if Find(ci)≠Find(cj) then

Union(ci,cj)

end

//合并整理

for k←0 to G.length do

if G[k]≠k then

Find(k)

end

如圖4所示,一個(gè)節(jié)點(diǎn)代表一個(gè)聚類地址組,同一聚合關(guān)系中的兩個(gè)組用實(shí)線連接,用虛線連接關(guān)系之間存在關(guān)聯(lián)的節(jié)點(diǎn)。圖4(a)中虛線圈出的為存在聚合關(guān)系的所有節(jié)點(diǎn),合并之后節(jié)點(diǎn)分布如圖4(b)所示。

圖4 基于聚合關(guān)系的并查集算法模型Fig.4 Model of union-find set algorithm based on aggregation relationship

聚合聚類算法完成后,存儲(chǔ)中間結(jié)果G,并檢查是否有新的區(qū)塊數(shù)據(jù)生成,若有生成新區(qū)塊,則對(duì)新區(qū)塊數(shù)據(jù)進(jìn)行結(jié)構(gòu)化處理,提取區(qū)塊中的所有聚類地址組Ct′-t,執(zhí)行算法1生成新的關(guān)系集合Rt′-t?；谥虚g結(jié)果G集合對(duì)Rt′-t進(jìn)行算法2中操作即可生成新的聚類結(jié)果Ft′,Ft′為基于t′時(shí)刻前數(shù)據(jù)生成的聚類結(jié)果。

重復(fù)使用上述方法對(duì)新數(shù)據(jù)進(jìn)行處理以實(shí)現(xiàn)增量聚類的效果。基于并查集方法實(shí)現(xiàn)增量聚類的時(shí)間復(fù)雜度低,并且在更新G集合的過(guò)程不需要額外的空間,適用于比特幣這種數(shù)據(jù)量大的問(wèn)題。數(shù)據(jù)采集及數(shù)據(jù)預(yù)處理、聚合關(guān)系集合獲取、數(shù)據(jù)增量聚類和存儲(chǔ)聚類4個(gè)模塊之間的數(shù)據(jù)交互過(guò)程如圖5所示。

圖5 基于比特幣交易信息的地址增量聚類方法時(shí)序圖Fig.5 Sequence diagram of address increment clustering method based on Bitcoin transaction information

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

2.1 數(shù)據(jù)集

本文采集比特幣網(wǎng)絡(luò)前278 878個(gè)區(qū)塊數(shù)據(jù)作為實(shí)驗(yàn)的數(shù)據(jù)源,數(shù)據(jù)覆蓋時(shí)間為2009年至2013年,數(shù)據(jù)的具體參數(shù)如表1所示。

表1 實(shí)驗(yàn)參數(shù)Table 1 Experimental parameters

2.2 聚類結(jié)果分析

2009年2月3日前交易的輸入地址都是單個(gè)或重復(fù),實(shí)驗(yàn)處理了2 817個(gè)區(qū)塊后首次出現(xiàn)符合條件的可聚類交易。圖6所示為交易實(shí)體、地址、關(guān)系對(duì)數(shù)量隨時(shí)間的變化?？梢钥闯?2009年至2012年地址增長(zhǎng)速率相對(duì)緩慢,2012年后地址增長(zhǎng)率顯著提高,并且2013年關(guān)系對(duì)增長(zhǎng)量較之前明顯降低。出現(xiàn)此現(xiàn)象原因可能為:在線交易服務(wù)的出現(xiàn),使用比特幣的用戶迅速增長(zhǎng),用戶逐漸意識(shí)到可聚類交易對(duì)隱私的影響。

圖6 實(shí)體、地址、關(guān)系對(duì)數(shù)量及增量隨時(shí)間的變化Fig.6 Change of number and increment of entity,address and relationship pair over time

表2和表3中的數(shù)據(jù)為實(shí)體標(biāo)識(shí),通過(guò)對(duì)實(shí)體中錢包地址進(jìn)行哈希運(yùn)算后取哈希值前十位得到該標(biāo)識(shí)。如果實(shí)體中包含多個(gè)地址,則使用最小的哈希,其中10位哈希值和CoinJoinMess標(biāo)識(shí)的實(shí)體均為普通錢包實(shí)體,提供在線服務(wù)的實(shí)體用服務(wù)的名稱標(biāo)識(shí)。

表2 基于可聚類交易數(shù)量的實(shí)體排名Table 2 Entity ranking based on number of clustering transactions

表3 基于地址數(shù)量的實(shí)體排名Table 3 Entity ranking based on number of addresses

由表2數(shù)據(jù)可以發(fā)現(xiàn):2009年至2011年可聚類交易最多的Top3實(shí)體皆為普通錢包;在2012年前三名的實(shí)體中首次出現(xiàn)了錢包外的新類型,即比特幣在線服務(wù)SatoshiDice,其為一款從2012年開(kāi)始運(yùn)營(yíng)的“基于區(qū)塊鏈的在線服務(wù)”;2013年出現(xiàn)了同類型新實(shí)體BitZillions,其為2013年起開(kāi)始提供的加密貨幣下注的市場(chǎng)[17]。

表3按包含的可聚類地址數(shù)量對(duì)實(shí)體排名,從中可以發(fā)現(xiàn):在2012年前三名的實(shí)體中首次出現(xiàn)了比特幣在線服務(wù)SilkRoad MarketPlace,該服務(wù)成立于2011年,提供各類商品在線匿名交易服務(wù),這一特點(diǎn)使其發(fā)展迅速[18],2012年后成為地址數(shù)量Top3的實(shí)體;2013年出現(xiàn)的新實(shí)體BTC-e,是一個(gè)比特幣交易網(wǎng)站。同時(shí)從表3數(shù)據(jù)也可以看出,2010年后實(shí)體包含的地址明顯增多,這是因?yàn)?010年上半年是比特幣初始階段[19],主要用于挖礦,而2010年下半年是比特幣交易階段,逐漸出現(xiàn)了各種各樣的用戶和在線服務(wù)提供商[20]。

2.3 交易行為可視分析

對(duì)3個(gè)地址數(shù)量最多的實(shí)體進(jìn)行交易行為可視分析。圖7(a)所示為截止至2012年Top3實(shí)體的交易行為,圖7(b)所示為截止至2013年Top3實(shí)體的交易行為,其中不同樣式的節(jié)點(diǎn)與圖例中相應(yīng)樣式的實(shí)體類型相對(duì)應(yīng),交易的數(shù)量用節(jié)點(diǎn)的大小編碼,實(shí)體間的交易次數(shù)越多,節(jié)點(diǎn)間的距離越小。

圖7 Top3實(shí)體交易行為Fig.7 Top3 entity transaction behaviors

可以看出,圖7(a)中形成了2個(gè)明確的交易集群,其中一個(gè)集群的交易中心為SilkRoad實(shí)體,將鼠標(biāo)懸浮在節(jié)點(diǎn)上可以看到中心節(jié)點(diǎn)SilkRoad MarketPlace實(shí)體與圖中其他類型的實(shí)體都有交易行為;另一交易團(tuán)體中心為錢包實(shí)體,與其交易密切的實(shí)體類型也是錢包,推測(cè)其為錢包服務(wù)。

為防止節(jié)點(diǎn)過(guò)密而造成節(jié)點(diǎn)相互遮擋,在圖7(b)中顯示交易數(shù)量超過(guò)500次的實(shí)體。圖中形成3個(gè)交易集群,中心節(jié)點(diǎn)分別是錢包服務(wù)、交易平臺(tái)以及匿名交易網(wǎng)站SilkRoad MarketPlace?？梢钥闯?與圖7(a)相比,圖7(b)中交易平臺(tái)類型的實(shí)體數(shù)量明顯增多,并且出現(xiàn)了新的匿名交易網(wǎng)站Sheep Marketplace,與其交易密切是實(shí)體分別為SilkRoad MarketPlace、BTC-e以及錢包實(shí)體。此外,BTC-e在2013年是地址數(shù)Top3的實(shí)體,出現(xiàn)此現(xiàn)象的原因?yàn)?在2013年在線匿名交易網(wǎng)站Sheep Marketplace通過(guò)BTC-e來(lái)進(jìn)行洗錢[21],產(chǎn)生了大量地址和交易。

2.4 性能分析

與Walletexplorer.com 網(wǎng)站聚類的結(jié)果相比,本文方法進(jìn)行實(shí)體聚類能夠達(dá)到100%正確率。表4為截止至2012年隨機(jī)選取的3個(gè)實(shí)體的地址數(shù)量對(duì)比。

表4 本文方法與Walletexplorer.com網(wǎng)站的聚類結(jié)果對(duì)比Table 4 Comparison of clustering results by the proposed method and WalletExplorer.com

圖8所示為傳統(tǒng)聚類方法與本文方法的執(zhí)行并查集算法時(shí)間對(duì)比。可以看出,第1次實(shí)驗(yàn)即處理2009年的數(shù)據(jù)時(shí)兩種方法用時(shí)相同,而之后由于本文增量聚類方法無(wú)需初始化集合和處理重復(fù)數(shù)據(jù),因此用時(shí)較少,時(shí)間復(fù)雜度較低,因此效率更高。

圖8 并查集算法時(shí)間對(duì)比Fig.8 Comparison of time of union-find algorithm

圖9所示為傳統(tǒng)聚類方法與本文方法的聚類時(shí)間對(duì)比?？梢钥闯?在比特幣初始階段,兩種方法的聚類用時(shí)相同,但隨著時(shí)間推移,每年生成的區(qū)塊數(shù)量和聚合關(guān)系集合越來(lái)越多,本文增量聚類方法性能優(yōu)勢(shì)越明顯。

圖9 聚類時(shí)間對(duì)比Fig.9 Comparison of clustering time

3 結(jié)束語(yǔ)

本文在啟發(fā)式聚類方法的基礎(chǔ)上,提出一種比特幣交易數(shù)據(jù)的增量聚類方法。通過(guò)對(duì)區(qū)塊流數(shù)據(jù)的分析及結(jié)構(gòu)化處理,提取可聚類交易和聚類地址組并獲取聚類地址組間聚合關(guān)系,在此基礎(chǔ)上進(jìn)行增量聚類,實(shí)現(xiàn)對(duì)比特幣實(shí)體類型和數(shù)量的演變分析,同時(shí)對(duì)地址數(shù)量最多的前三名實(shí)體的交易做進(jìn)一步可視分析,發(fā)現(xiàn)不同時(shí)期實(shí)體間的交易特征。實(shí)驗(yàn)結(jié)果表明,本文方法對(duì)多輸入交易的地址具有較好的效果,但不能將全部的交易地址覆蓋到聚類分析中。下一步將對(duì)此進(jìn)行改進(jìn),提高該方法的交易地址覆蓋率。