基于交易網絡的公有鏈用戶識別方法

王勁松，趙述佳，趙澤寧，張洪瑋

（1.天津理工大學計算機科學與工程學院，天津 300384；2.智能計算及軟件新技術天津市重點實驗室，天津 300384；3.計算機病毒防治技術國家工程實驗室，天津 300457）

0 概述

比特幣是一種基于P2P 網絡的虛擬加密數字貨幣［1］，不依靠特定貨幣機構發行，根據特定算法并通過大量計算產生，使用整個P2P 網絡中眾多節點構成的分布式賬本確認并記錄所有的交易行為，利用密碼學設計確保貨幣流通各個環節的安全性。以太坊是一個開源的有智能合約功能的公共區塊鏈平臺，通過專用加密貨幣以太幣提供去中心化的以太坊虛擬機來處理點對點合約。比特幣和以太坊是區塊鏈中最具代表性的兩條公有鏈［2］。公有鏈交易以用戶為基礎，比特幣交易發生在交易地址之間，以太坊采用賬戶間一對一的交易模式。

比特幣相較于傳統的中心化交易系統，所具有的匿名性特征能保護用戶隱私不被泄露［3］，但也正因為這一特性，使得比特幣交易系統中產生了許多非法交易行為［4-6］，例如混幣服務［7-9］。混幣服務是一種去中心化的隱私服務，可以使用戶快速高效地與其他用戶的資金進行混合，在現有賬戶和混幣后的新賬戶間創建隨機的映射關系并實現完全匿名［10-12］。該行為掩蓋了資金來源并保護了發款人的隱私，不法分子可以通過這類資金轉移方式來逃避政府監管，并可能危害公民及國家財產安全［13］。因此如何正確識別比特幣交易中地址之間的關聯關系，并由此推斷出用戶的真實身份信息已經成為比特幣研究中的重要方向［14］。目前，已有一些學者對此進行了研究并取得了一定的研究成果。WU 等［15］研究從比特幣的公共交易歷史派生的兩個網絡拓撲結構，并將這些結構與信息和技術相結合調查了比特幣盜竊案。DUPONT 等［16］演示如何收集關于比特幣交易背后的真實世界的用戶信息，并且通過檢查用戶的消費習慣來確定比特幣用戶的物理位置信息。PINNA 等［17］通過一種基于圖的方法來分析身份聚類和比特幣交易中的貨幣流通特性，并深入了解了比特幣匿名性的本質以及比特幣如何在特定的用戶和用戶社區之間流動。ANDROULAKI 等［18］對比特幣的隱私問題進行評估，并提出基于多輸入交易的啟發式地址聚類方法。TASCA 等［19］將比特幣身份的最小單位（單個地址）聚合到一起，并將它們分成近似的業務實體，雖然這些實體在很大程度上可以保持匿名，但通過分析其中一些特定的交易模式，可將其中的許多實體歸為特定的業務類別。

本文以公有鏈中的代表性應用比特幣為例，提出一種基于交易網絡的公有鏈用戶識別方法。通過衡量交易地址間的相似程度將屬于同一用戶的交易地址進行聚合，找出屬于同一用戶的所有交易地址。設計一種比特幣區塊數據預處理方法，通過解析比特幣區塊數據中的腳本信息，將比特幣原始交易數據處理為更加直觀的格式。在實驗中使用真實的比特幣區塊數據，通過可視化方式對用戶識別結果進行分析，以驗證本文方法的可行性及準確性。

1 相關工作

本文通過分析比特幣交易間的關聯關系來實現比特幣用戶識別，與本文相關的工作主要有公有鏈地址聚類和社交網絡分析［20-21］。由于比特幣地址具有匿名的特征，比特幣地址無法關聯到用戶的真實信息，這使得比特幣溯源十分困難［22］，因此許多研究人員對比特幣地址進行了聚類分析，將屬于同一實體的比特幣地址聚合到一起。目前公有鏈地址聚類方法主要分為兩類：一類是基于啟發式的地址聚類；另一類是基于事務的地址聚類。ZHAO 等［23］對比特幣中的交易進行分析，將35 770 360 個地址聚類為13 062 822 個集合，并分析了聚類后的實體及其之間的聯系。ZHANG 等［24］從地址重用的角度重新考慮了基于一次性地址的啟發式聚類方法，提出一種新的啟發式地址聚類方法，通過排除那些被重用為不變地址的地址來確定一次性改變地址。CUI等［25］提出一種將IP 信息與區塊鏈交易記錄相匹配的去匿名方法，并對真實的交易數據進行IP 匹配實驗。

比特幣交易網絡本質上是一個錯綜復雜的社交網絡［26］，其中每一個比特幣地址代表社交網絡中的一個節點，比特幣地址之間的交易代表地址之間的聯系。依據社交網絡分析方法，可以對比特幣交易網絡進行關聯分析。RUFFING 等［27］提出一種基于區塊鏈的社交網絡模型，該模型將用戶的角色作為社交網絡系統的中心。本文提出的用戶識別方法在比特幣地址不符合特定的地址聚類規則時，也能夠通過交易網絡中地址間的關聯等信息對比特幣用戶進行有效識別。本文用戶識別方法的時序圖如圖1 所示。

圖1 本文用戶識別方法的時序圖Fig.1 Sequence diagram of the proposed user identification method

2 比特幣相關技術

2.1 區塊數據解析

比特幣實質上是一個分布式賬本，該賬本中的每一頁對應比特幣中的一個區塊，比特幣的區塊數據中包含了比特幣鏈上的核心信息，比特幣從誕生到現在，每10 分鐘誕生1 個區塊。Dogcoin、Litecoin、DCash、ZCash 等公有鏈中的大部分幣種的底層代碼均參考了比特幣的底層代碼［28］，由比特幣發展而來，因此這些幣種多數與比特幣具有相同的結構。區塊數據結構如圖2所示。每一個數據區塊記錄了神奇數（Magic Number）、區塊大小（Block Size）、區塊頭（Block Header）、交易計數（Transaction Counter）、交易詳情（Transaction List）5個部分。區塊頭的哈希值是下一個新區塊的哈希值的參考目標數，最后一項交易詳情記錄了該區塊中所有的交易記錄。區塊頭中記錄了版本號（Version）、前一個區塊的記錄（Previous Block Hash）、Merkle 樹的根值（Merkle Root）、時間戳（Timestamp）、難度目標（Difficulty Target）和Nonce。比特幣的原始數據保存方式是小端編碼，也就是原始十六進制格式值需要字節逆轉轉化為大端數據，然后才能轉化為正常的數值。大端編碼是內存地址大的空間保存高位，書寫出來就是左邊的數據表示高位，與十進制表示法相同，更符合人們的閱讀習慣。區塊頭數據后邊緊跟的是交易信息，交易信息前面幾個字節表示的是該區塊包含的交易數量，coinbase 交易也計入在內，其中采用可變長整型變量來表示交易數量類型。剩余的信息是普通交易信息，版本號、交易哈希值采用小端編碼。輸入計數器、輸出計數器、解鎖腳本大小和鎖定交易大小均采用變長整型值。

圖2 區塊數據結構Fig.2 Block data structure

2.2 地址聚類算法

ZHENG 等［29］提出以下4種比特幣地址聚類算法，結合這4 種算法可以提高地址聚類效果：

1）多輸入交易地址聚類算法。在一次比特幣交易中，用戶選擇多個比特幣地址作為輸入地址，避免使用單一比特幣地址在余額不足時產生多筆交易成本，實現了多輸入交易。該交易中的所有輸入地址都屬于同一個實體。

2）coinbase 交易地址聚類算法。比特幣中每一個區塊都對應一筆coinbase 交易，該交易只有輸出地址，沒有輸入地址。因此，coinbase 交易中的所有輸出地址都屬于同一個實體。

3）找零地址聚類算法。該算法的核心是找出輸出地址中的找零地址，通常來說找零地址只會在輸出地址中出現一次，而不會同時出現在輸入和輸出地址中，輸出地址也不能只包含找零地址。因此，一筆交易中的找零地址和輸入地址屬于同一個實體。

4）礦池地址聚類算法。如果某一筆交易中的輸出地址數量超過100 個，并且其中的一個地址屬于一個礦池，那么這筆交易中的所有輸出地址屬于同一個實體。

3 比特幣用戶識別方法

本文提出一種比特幣用戶識別方法，包含數據預處理、字典樹構建、用戶識別算法3 個部分，目的是將比特幣交易網絡中具有強關聯關系的地址映射為同一實體。

3.1 數據預處理

通過配置區塊鏈環境并搭建比特幣客戶端Bitcoin Core 將比特幣區塊流數據同步到本地，同步到本地的比特幣區塊數據是二進制流數據，初步解析后的數據結構如下：

比特幣的交易實際上是不依賴地址的，主要依賴于腳本。在支付款項時，將支付的數額與接收者的“贖回腳本”綁定到一起。日后接收者可以用自己的“簽名腳本”來確認使用權。每一筆交易的實現所依賴的只是腳本。兩種常見腳本的格式具體如下：

1）支付到公鑰地址模式（P2PKH）：

OP_DUP OP_HASH160（0x14）［一個20 字節的哈希值］OP_EQUALVERIFY OP_CHECKSIG

2）支付到腳本模式（P2SH），當使用多重簽名時需要使用該模式：

OP_HASH160（0x14）［一個20字節的哈希值］OP_EQUAL

通過初步解析后的數據并不能直接看出某筆交易的輸入輸出地址，也不能看到交易的金額。因此，為了方便實驗，針對比特幣交易中的腳本格式設計了一種算法，用于解析比特幣交易中的輸入和輸出地址以及交易涉及的金額等信息。

算法1在交易腳本中獲取交易地址

3.2 字典樹構建

字典樹又稱單詞查找樹，是哈希樹的變種。典型應用是用于統計、排序和保存大量字符串，經常被搜索引擎用于文本詞頻統計。大量的比特幣地址會出現很多相同的前綴，并且在3.1 節中將比特幣交易數據處理成交易集合的形式，因此基于常規的字典樹結構，本文提出了一種針對比特幣交易數據的改進字典樹結構，在字典樹每個根節點之后追加一個集合，該集合用來存儲與該分支表示的地址有直接交易的地址列表。

算法2在Trie 樹中插入一個地址字符串

算法3在Trie 樹中查找一個地址字符串

3.3 用戶識別算法

目前，多數針對比特幣地址聚類的研究是通過制定交易規則來實現地址聚類的，例如多輸入交易規則、找零交易規則等。ANDROULAKI 等［18］研究比特幣交易中的輸入地址，并設計基于多輸入地址的比特幣地址聚類方法，在不考慮特殊樣例的情況下，基于該方法得到的聚類結果是完全正確的。MEIKLEJOHN 等［30］基于找零交易規則提出一種找零地址聚類算法，該算法會將一筆交易中的輸入地址和找零地址聚合為同一個實體。當部分交易中的地址符合特定的交易規則時，通過傳統地址聚類算法可將這些地址聚合到一起。因此，對于符合特定交易規則的交易而言，使用這些算法能夠得到很好的結果，甚至是完全正確的結果。但對于大部分的普通交易而言，這些算法往往不能取得正確的結果，因為這些交易通常沒有規則可言。針對上述情況，本文通過分析比特幣交易中輸入與輸出地址之間的關聯關系，提出一種具有普適性的比特幣用戶識別算法。

用戶識別算法的具體步驟如下：

步驟1假設算法輸入為起始節點starting_node，交易數據集合trans_network，該集合中的每一條數據代表一筆比特幣交易t。設置隊列Q和集合S，將起始節點starting_node 分別加入到Q和S中，同時設置臨時集合W和E。

步驟2當隊列Q不為空時，遍歷Q中的節點，從交易數據集合trans_network 中將與這些節點直接關聯的節點加入到集合W中。接著遍歷集合W中的節點，判斷這些節點與集合S的Sim 值，如果該節點的Sim 值大于閾值，則將該節點分別加入集合S與集合E中，否則繼續遍歷。在遍歷結束時，將集合E加入到隊列Q中，同時將隊頭元素移出隊列Q，并清空集合W和E。Sim 值定義如下：

其中：Sim(i,S)表示節點i與集合S中節點的相似程度；j表示在集合S中與i直接相連的節點；Ki、Kj分別表示節點i的度數和節點j的度數；Nj表示與節點i直接相連的節點數量；Aj表示節點j的邊的權值。

步驟3重復步驟2，直到隊列Q為空，此時結束循環，返回集合S。

算法4用戶識別

4 實驗與結果分析

選擇比特幣的真實交易數據作為實驗數據，將其解析成改進的字典樹結構，運行本文提出的用戶識別算法對交易地址進行用戶識別。通過可視化方式對算法執行過程進行分析并驗證用戶識別算法的有效性。

4.1 有效性驗證

在算法起始階段，從比特幣交易網絡中任意選取一個節點作為起始節點，由于此時算法中的集合S為空，因此將與該節點直接關聯的節點加入到網絡中構成算法的初始網絡。

圖3 為用戶識別算法經一次迭代后形成的比特幣交易網絡。該網絡中共有3 類節點，其中：第1 類節點出度為0、入度為1，它們只接收不發送交易；第2 類節點的入度為2、出度為n，n代表第1 類節點的數量，它們既發送又接收交易，同時是一個中心節點；第3 類節點的入度為0、出度為2，它們只發送不接收交易。由圖3可以看出，該網絡具有中心化的特性，中間的第2 類節點給周圍大量的第1 類節點發送了交易，并且接收了來自第3 類節點的交易。

圖3 用戶識別算法經一次迭代后形成的比特幣交易網絡Fig.3 Bitcoin transaction network formed after one iteration of the user identification algorithm

圖4 為用戶識別算法經多次迭代后形成的比特幣交易網絡。由圖4 可以看出，相比于經一次迭代后形成的比特幣交易網絡，用戶識別算法經多次迭代后有更多的節點被加入到網絡中，但網絡整體結構不變，仍具有中心化特性。所有節點根據出入度劃分為3 類節點，并且在網絡中的角色也與圖3 相同。

圖4 用戶識別算法經多次迭代后形成的比特幣交易網絡Fig.4 Bitcoin transaction network formed after multiple iterations of the user identification algorithm

圖5 為用戶識別算法迭代穩定后形成的比特幣交易網絡，即用戶識別算法迭代完成后得到的聚類結果，表示這些交易地址屬于同一用戶。由圖5 可以看出，用戶識別算法迭代穩定后形成的網絡結構相比于圖3和圖4 有了較大變化，網絡中不只存在一個中心節點，而是有許多散布在網絡邊緣的“中心節點”，這些邊緣的節點與中心的第1 類節點群有著大量的連接，并且這些節點不同程度地復用了第1 類節點，表明這些節點與第1 類節點具有較強的關聯性。

圖5 用戶識別算法迭代穩定后形成的比特幣交易網絡Fig.5 Bitcoin transaction network formed after the user identification algorithm is iteratively stabilized

由于整個比特幣交易網絡數據過于龐大，因此實驗部分選取比特幣第140 000 個至第160 000 個區塊間的20 000 個區塊作為實驗數據構造交易網絡，將本文提出的用戶識別算法應用于該交易網絡后，得到如圖6 所示的比特幣交易網絡。

圖6 實驗最終得到的比特幣交易網絡Fig.6 Bitcoin transaction network obtained by the experiment

4.2 效率分析

本文提出的用戶識別方法類似于關聯搜索方法，借助隊列進行存儲，從出發點開始逐層向外查找，在查找過程中優先考慮距離出發點近的節點。無論是在鄰接表還是鄰接矩陣中存儲，均需要借助輔助隊列，且N個頂點均需入隊，空間復雜度為O（N），其中N為圖中的節點數。當算法開始迭代時，從一個頂點開始搜索，每個節點和每條邊至少訪問一次，時間復雜度為O（E），算法總時間復雜度為O（N+E），其中E為圖中的邊數。

地址聚類算法的評價標準通常為準確率，即算法得到的結果中正確的地址數量與總地址數量的比值，由于本文用戶識別方法與傳統地址聚類算法的目的相同，因此也采用準確率作為評價標準，并且使用Walletexplorer 中的數據作為實驗對照數據。比特幣區塊是連續的，如果隨機選取區塊鏈中的部分區塊會導致之前區塊中包含的地址間的關系無法被算法發現，為避免影響聚類結果，本文選取比特幣的前160 000 個區塊進行實驗。

圖7 給出了本文用戶識別方法與傳統地址聚類算法的準確率對比結果。相較于傳統地址聚類算法［26-27］基于規則匹配的識別方式，本文用戶識別方法不受交易規則的限制，應用于特殊交易或是常規交易時均能取得穩定的結果。由圖7 可以看出，隨著實驗涉及的區塊數量的增加，傳統地址聚類算法的準確率有明顯的下降趨勢，因為隨著區塊數量的增加，交易數量也不斷增加，傳統地址聚類算法在面對大量常規交易時，受到協議版本變化和混幣服務的影響，聚類效果就會受到明顯影響，從而降低準確率。本文用戶識別方法不受交易規則的限制，隨著區塊數量的增加，準確率雖略有波動，但總體穩定在80%左右，并沒有明顯的下降趨勢，應用于常規交易中也能取得穩定的結果。

圖7 本文用戶識別方法與傳統地址聚類算法的準確率對比Fig.7 Comparison of the accuracy between the proposed user identification method and the traditional address clustering algorithm

5 結束語

本文在分析現有比特幣用戶識別方法的基礎上，提出一種基于交易網絡的用戶識別方法，通過發現交易地址之間的關聯關系，識別出屬于同一用戶的所有交易地址。由于公有鏈中大部分幣種底層數據結構相同，因此本文方法不僅適用于比特幣，而且對其他使用類似比特幣交易模式的公有鏈也能取得同樣的效果。實驗結果表明，本文用戶識別方法無論應用于常規交易還是特殊交易，均能獲得相對穩定的用戶識別準確率，且該結果不會受到協議版本變化和混幣服務的影響而產生大幅波動。后續將繼續優化用戶識別方法中的核心算法，在盡量不增加算法復雜度的情況下提升用戶識別準確率，同時還將在識別過程中加入用戶地理位置等信息，以獲得更好的識別效果。