面向區(qū)塊鏈交易可視分析的地址增量聚類方法

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

(天津理工大學 a.計算機科學與工程學院; b.天津市智能計算及軟件新技術重點實驗室;c.計算機病毒防治技術國家工程實驗室,天津 300457)

0 概述

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

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

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

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

1 增量聚類方法

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

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

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

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

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

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

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

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

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

1.2 聚合關系集合獲取

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

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

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

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

算法1聚合關系集合生成算法

輸入t時刻之前所有聚類地址組Ct

輸出哈希表Ht,聚合關系集合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)

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

else

Ht[a].v=ci

end

end

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

1.3 增量聚類

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

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

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

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

算法2基于聚合關系的并查集算法

輸入關系集合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所示,一個節(jié)點代表一個聚類地址組,同一聚合關系中的兩個組用實線連接,用虛線連接關系之間存在關聯(lián)的節(jié)點。圖4(a)中虛線圈出的為存在聚合關系的所有節(jié)點,合并之后節(jié)點分布如圖4(b)所示。

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

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

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

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

2 實驗與結果分析

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

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

表1 實驗參數(shù)Table 1 Experimental parameters

2.2 聚類結果分析

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

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

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

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

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

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

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

2.3 交易行為可視分析

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

圖7 Top3實體交易行為Fig.7 Top3 entity transaction behaviors

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

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

2.4 性能分析

與Walletexplorer.com 網站聚類的結果相比,本文方法進行實體聚類能夠達到100%正確率。表4為截止至2012年隨機選取的3個實體的地址數(shù)量對比。

表4 本文方法與Walletexplorer.com網站的聚類結果對比Table 4 Comparison of clustering results by the proposed method and WalletExplorer.com

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

圖8 并查集算法時間對比Fig.8 Comparison of time of union-find algorithm

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

圖9 聚類時間對比Fig.9 Comparison of clustering time

3 結束語

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