Community Detection in Blockchain
Social Networks

There has been a branch of works in the literature on analyzing the Bitcoin transaction data and most of them focus on two issues: anonymization and de-anonymization. The review on these two issues can be found in Refs. [50, 13, 44, 46]. Therein, shared coin and send mixers in Refs. [5, 30, 31, 7, 60] are two basic anonymization approaches, while other approaches such as fair exchange[5], transaction remote release[51] and zero cash[49] are also popular. In this work, our main focus is on de-anonymization. In the literature, there are many approaches for implementing de-anonymization. For example, an early work in Ref. [5] first brought up the notion of “change address” and people realized that one can use the heuristics to associate addresses that involving common spending and one-time change. This approach is widely used as the first step to process Bitcoin data[17, 18, 21, 32, 45, 11, 2]. There are also more advanced approaches. In Refs. [25, 6, 62], the authors tried to de-anonymize user’s identity of Bitcoin by linking the Bitcoin address with IP address. Ref. [53] summarized prior approaches of clustering addresses and implemented a modular framework to group users and classify them with different labels. Sometimes, off-chain information is also useful. For example, in Refs. [44, 17] the authors proposed to use off-chain information to guide different clustering models with a purpose of reducing the algorithm complexity. Ref. [15] and Ref. [35] proposed novel methodologies for analyzing Bitcoin users based on the observation of Bitcoin transactions over time.

In this work, we try to deanonymize a blockchain network by finding users’ communities. Some prior works have been done for Bitcoin. The idea of treating Bitcoin as a social network has appeared in Ref. [52]. Therein, people usually used the notions of “user graph” and “transaction graph”, and some analysis based on these two graphs has been elaborated in Ref. [44]. Ref. [29] studied the anonymity for Bitcoin by analyzing the transaction graph with the help of public data. Ref. [19] studied how different features of the date influence communities results on the “transaction graph” based on the ground truth of some known hack subnetworks. Authors in Ref. [43] and Ref. [22] extracted various features from these two graphs and pointed it out that features on the graph are crucial for the analysis results. Ref. [45] showed that a two-party community detection based on normalization mutual information could be used to re-identify users in Bitcoin. Our community detection approach on the Bitcoin data is based on the above works. Specifically, our approach has the following properties: 1) we study the “user graph” based on the super-address which is associated with addresses that involve common spending and one-time change; 2) we use historical BTC coin amount as the key feature to perform the community detection algorithm; 3) a modified clustering method is proposed for the Bitcoin social graph to find communities.

The above approaches are effective for Bitcoin while it is difficult to be directly carried forward to the Ethereum network, as Ethereum is mechanically different from Bitcoin. In Ethereum, there are two types of accounts: externally-owned accounts (EoAs) and contract accounts (CAs). In Refs. [26, 10], the authors pointed it out that existing methods such as discovering IP addresses and Bitcoin addresses clustering usually do not fit the Ethereum network due to the differences between both networks in the volatility of entry nodes and the way transactions are handled. Some works tried to use traditional clustering methods for Ethereum, such as support vector machine (SVM) and k-means in Ref. [8], the standard k-means in Refs. [42, 23], long short-term memory (LSTM) and cnonvolutional neural network (CNN) models in Ref. [23], affinity propagation k-medoids in Ref. [40], k-means clustering, agglomerative clustering, Birch clustering in Refs. [41, 54] and Neo4j in Ref. [10]. However, they basically equally treat EoAs and CAs as nodes in the transaction graph[42, 10, 54], while these two types of accounts are essentially different. Some works in Refs. [40, 27] also used side information to analyze the on-chain transactions. Therein Ref. [27] utilized the smart contract codes to analyze the smart contract nodes in the transaction graph. It is worth mentioning that our community detection approach in a bipartite graph differs from traditional one in a bipartite graph as we treat nodes on both sides of the bipartite graph as two parties of nodes, therefore utilizing the connections between those two parties to cluster nodes in one party, while the traditional approach usually treats all the nodes in both sides equally and find communities over all the nodes in both sides [4, 1, 61]. Our work on Ethereum data differs from the above work in five aspects: 1) we analyze the on-chain data without any off-chain side information; 2) we separately treat EoAs and CAs as different nodes and put them on two sides of a bipartite social graph; 3) we target on smart contract transactions which involve ICO events; 4) we apply a novel low-rank community detection algorithm based on graph signal processing (GSP) on the bipartite graph; 5) we utilize the clustering results to deliver on-chain advertisement in Ethereum.

The rest of the paper is organized as follows. In Section II, we show an example to define the Bitcoin social graph and then apply a novel clustering method on this graph. Based on this result, Section III demonstrates the difference between the Bitcoin social graph and the Ethereum social graph. We then define the bipartite Ethereum social graph and utilize a particular method to find communities on it. Simulation results are illustrated in Section IV where both Bitcoin data and Ethereum data are analyzed and compared. Moreover, we also test the on-chain advertisement for Ethereum based on the clustering results. We conclude and further discuss with simulation results in Section V.

As mentioned in the previous section, the only purpose of transaction in Bitcoin is to transfer BTC coins. To achieve this goal, each user generates a key pair (represented as the addresses in the transaction) to join the Bitcoin network and transfer BTC coins based on the so-called unspent transaction output (UTXO) model[36]. UTXO can be seen as an abstraction of electronic money, representing a chain of ownership implemented as a chain of digital signatures. In Fig. 2, we show a basic structure of a Bitcoin transaction where we can find multiple addresses in the input and output fields. Every address could contain multiple UTXO, wherein UTXO in the input addresses are consumed while in the output addresses are created.

A basic idea to define the Bitcoin social network is to let each address one-to-one correspond to a node in the social graph. However, a crucial problem here is that one user usually possess multiple addresses. Given that there are so many addresses in the blockchain, the dimensionality of the social network could be huge. To reduce the size of the graph, we try the following way to associate multiple addresses (key pairs) to a super-address in the social graph: 1) multiple input addresses of a transaction; 2) those bitcoin users that have a common change address. More details for such operations will be shown in the numerical experiments. After such a pre-processing, we define a social network where each node corresponds to a processed super-address.

To well define the graph, we need to specify the edge weight between any two nodes (super-addresses). In fact, the edge weight between any two nodes could be defined following criterion in Refs. [19, 43, 22]. Herein, we extract features from the total transaction amount and set them as the edge weight. Then, we run a clustering method which is modified from the spectral clustering algorithm[39, 58] to cluster this Bitcoin social graph. Specifically, we denote the social graph by $\bm{G(V,E)}$, where $\bm{V}$ denotes the user nodes $(v_{1},v_{2},...v_{n})$ and $\bm{E}$ the edges. We let $\bm{W}$ denote the weight matrix where each entry $w_{ij}$ is the edge weight between node $v_{i}$ and node $v_{j}$. In this paper, we let $a_{ij}$ be the historical total transaction amount between node $i$ and node $j$ and

Apparently, we will thus have an undirected graph with $w_{ij}=w_{ji}$. We then apply the following clustering algorithm in Algorithm 1 to find communities in the graph.

Remark 1: It is worth noting that the above clustering algorithm is quite similar to the well known spectral clustering algorithm except for that the similarity matrix is replaced by the weight matrix in our algorithm. This modification is meaningful since we re-define the “similarity” as that two nodes have a significant transaction relationship. This redefinition can help cluster users that have more connections with each other.

Now our purpose is to perform a community detection on this bipartite graph and group all EoA nodes into clusters. In this subsection, we adopt the low-rank community detection algorithm in Ref. [57] to cluster the EoA nodes in the bipartite graph. The idea is to assume that all EoA nodes form a low-rank social sub-graph, where some lead EoA nodes will decide other nodes’ attention on CA nodes. In this spirit, we partition the EoA node set of the bipartite graph into subsets with high edge densities. This could be done by applying a clustering algorithm on the low-rank output covariance matrix of the observed graph signal at EoA nodes. To proceed it, we regard this community detection problem as a problem of GSP, wherein the input of the graph ${\bm{z}}\in\mathbb{R}^{R}$ is on the EoA lead node (see Fig. 3) and it goes through a filter ${\cal H}({\bm{S}})$ :

where $\bm{S}$ is the graph Laplacian matrix, $L$ is the degree of the filter and $R$ is the number of lead node. The output signal ${\bm{x}}\in\mathbb{R}^{N}$ is defined on all the EoA nodes and it is generated by

Herein, ${\bm{V}}$ and ${\bm{\Lambda}}$ are from a SVD decomposition of ${\bm{S}}$. The above equation means that in our graph model, the opinion of the EoA lead node decides all nodes’ status. Based on the above model, the graph signal observed at all the EoA nodes can be expressed as

where $\bm{y}^{t}$ is the observation of the graph signal which represents EoA nodes’ attention on CA node $t$ in our problem setting and ${\bm{w}}^{t}\sim{\cal N}(0,{\sigma}^{2}{\bm{I}})$ is the noise. Notice that the input signal ${\bm{z}}^{t}$ is applied on only a subset of $R$ EoA lead nodes and thus the number of variations in the excitation signal is limited to $R$ mode. To further explore the graph structure, we let

where ${\bm{B}}\in\mathbb{R}^{N\times R}$ with $R<N$. Then, we can recover the community structure in ${\bm{S}}$ by applying Algorithm 2 on the empirical sampled covariance of the observed signal $\bm{y}^{t}$:

which is an estimate of $\bm{C}_{x}=\mathcal{H}(\bm{S})\bm{BB}^{\mathsf{T}}\mathcal{H}(\bm{S})^{\mathsf{T}}$.

An illustration of the algorithm model for Ethereum is depicted in Fig. 4. In practice, $\hat{\bm{C}}_{x}$ could be obtained by observing the graph signals from many instances $t$. For example, in the Ethereum social network, we consider each instance $t$ as one CA node in the bipartite graph. Thus, we obtain the graph signal ${\bm{y}}^{t}$ by observing EoA nodes’ attention on CA nodes and utilize it to detect communities of EoA nodes. For example, we could consider users’ transaction amount on different tokens as their attention on such tokens.

In previous discussion, we discuss how to find communities of EoA nodes by using graph signal processing. In fact, this process can be reversed to cluster tokens by users’ subscription. That is, we exchange the position of the EoA nodes and CA nodes and observe the graph signal at each CA node, which represents all EoA nodes’ attention on a specific CA node. This equals to transposing $\hat{\bm{C}}_{x}$ in Algorithm 2 and performing the same clustering method on the new $\hat{\bm{C}}_{x}$. Numerical results are shown in Section IV-B.

At the end of this part, two remarks are in order. First, the relationship between user clustering and token clustering is analog to that between the user-based collaborative filtering and the item-based collaborative filtering. Second, the token clustering result can also be used to recommend tokens to EoA nodes. A flow chart for the recommendation system is shown in Fig. 5. We will introduce the detailed recommendation process in the next subsection.

The proposed community detection algorithms can help find EoA users sharing the same interests on CA nodes (by user clustering), as well as CA nodes favored by groups of EoA nodes (by token clustering). We then discuss 1) how to deliver advertisements to a user whose community members have shown interest on a specific token, and 2) how to recommend other tokens to a user who has shown interest on a specific token. Specifically, we may resort to the “InputData” field in the transaction script to serve our purpose. In Fig. 6, we show two types of transactions in Ethereum. Transaction $1$ is an ETH coin transaction (left) and Transaction $2$ is a smart contract transaction (right). For both transactions, there is an “InputData” field in the script which can be used to run functions or send messages. We therefore design two on-chain advertisement strategies. One approach is to send a small amount ETH coin (could be zero) to the target user and attach a recommendation message in the “InputData” field in this coin transaction. This implementation can only be done in a one-to-one manner and one has to cost some gas to send the message. Another approach is similar to the so-called “airdrop”[33, 14], wherein new ICO project distributes part of their tokens for free to a community to advertise their ICO project. “Airdrop” could be done via smart contract in a group message manner and no extra ETH coin is consumed except for the gas. Notice that to successfully deliver the message, one has to negotiate with the wallet company to register their token in the target user’s list. Otherwise, users can not see the new-added token, as well as the advertisement message. We remark that our design differs from the original “airdrop” in two aspects: 1) we have resorted to a community detection to target potential users; 2) we utilize the “InputData” field to send the advertisement message.

The Bitcoin data we studied comes from the website http://vo.elte.hu/bitcoin, where the raw Bitcoin data is processed and compressed into several documents; more details could be found in Ref. [16]. In our experiment, we used the document “txhash.txt” which is a list of transaction IDs (indexed by the website) and hash pairs to record the hash for each transactions in chronological order. We intercepted the block data from block number $250,000$ to $252,000$, whose time interval is between “2013-08-03 12:36:23” and “2013-08-13 18:11:30”. By searching transaction hash in “txhash.txt” we found that these transaction IDs range from $21,490,941$ to $22,003,698$. With these IDs, we can search documents “txin.txt” and “txout.txt” to find the input addresses and output addresses. Herein, “txin.txt” records each transaction’s input addresses with the amount of Satoshis¹¹1 The satoshi is currently the smallest unit of the bitcoin currency recorded on the block chain. and “txout.txt” records each transaction’s output addresses with the amount of Satoshis. Within this time interval, we can extract in total $512,756$ transactions involving $515,765$ addresses. It is worth noting that at this moment, the addresses may be duplicated.

Our next step is to pre-process the data by associating the addresses using the heuristic of “common spend” and “change address”. To process the data by “common spend”, we utilized the data set “contraction.txt” from the website http://vo.elte.hu/bitcoin, which is a list of addresses possibly belonging to the same user. The basic idea of this process is that any two input addresses which belong to the same “user” appear as inputs in the same transaction at least once. After this processing, we have in total $132,431$ transactions and $65,811$ identified unique users (super-addresses) left. To better analyze the details of some key users, we assume that the “change address” is used rarely and thus we can eliminate the addresses whose occurrence (appears in the transaction input or output) is less than $30$. This process significantly reduces the size of the graph to $3930$ transactions and $279$ users. Notice that some of the users are the combinations of several common spend addresses, and others are the change addresses which appeared in the output of transactions but never appeared in the inputs of a transaction. In Fig. 7, we plot the graph representation by using the Gephi software[24], where the continuous graph layout algorithm ForceAltas $2$ is adopted to visualize the graph. Note that herein we do not consider to use any features to define the edge weights. The edge weight is either ‘0’ (no transaction) or ‘1’ (with transaction). From the plot we see that after associating common spend, the graph is well clustered while the dimension of the graph is still large.

We then evaluate and visualize the community detection results based on the social graph we have defined for the Bitcoin data. First, we run the Elbow method in Ref. [55] to determine the optimal number of clusters $k$. Fig. 8 (left) shows that the “inflection point” is $k=5$ and thus we consider there are $5$ clusters in our example. Interestingly, this is also roughly consistent with the results in Fig. 7 although they have defined different edge weight. We then run Algorithm 1 under a random initialization with $k=5$ and find that the number of nodes in each cluster are $101$, $78$, $60$, $27$, and $13$, respectively. A $2$D visualization of the clustering results are shown in Fig. 8 (right), where a machine learning algorithm called ${\bm{t}}$-SNE[28] is used for a nonlinear dimensionality reduction. The results show that the target users are indeed clustered in the compressed $2$D space. We use two parameters to evaluate the community results. One is the Silhouette score, which combines the two factors of cohesion and resolution to evaluate the clustering results[47]. The other one is the Modularity score which is usually used to measure the structural of network communities[38]. In this experiment, we have the Silhouette score $0.5871$ and theModularity score $0.3733$. Normally the Silhouette score is at a range of $[-1.0,1.0]$ and the range of the Modularity score is $[-0.5,1.0]$. The more two scores approach to $1$, the better quality of the network partition. The Modularity score around $0.3\sim 0.7$ is considered as a good clustering result[37]. We track the nodes of the gambling website and find that the gambling website nodes and other $55$ nodes that had transactions with the gambling nodes have been all clustered into the same cluster. This cluster has in total $101$ nodes.