Bitcoin Address Clustering Method Based on Multiple Heuristic Conditions

We analyzed the associations between Bitcoin transactions and addresses to cluster address and further find groups of addresses controlled by the same entity. It revealed the vulnerabilities of Bitcoin anonymity mechanism, which could be used by the law enforcement agencies to track and crack down illegal transactions. However, single heuristic method and incomplete heuristic conditions were difficult to cluster a large number of addresses comprehensively and accurately. Therefore, this paper reviewed a variety of heuristics, and used multiple heuristics comprehensively to cluster addresses to improve the degree of address aggregation and address recall rate, which laid a foundation for further inferring of entity identity. Keywords—Bitcoin, Blockchain, Anonymity, Heuristic, Address Clustering


Introduction
Since Bitcoin became a peer-to-peer digital payment system, it has attracted the attention of a legion of researchers. Currently there is a lot of research which has focused on various areas of the Bitcoin system, such as privacy security [1],transaction pattern [2], network analysis [3], price prediction [4] etc. In addition, many authors have also made detailed summaries about this field in their literature reviews [5]. Authors tended to expound the research issues, summarize the methods, and analyze the results and findings. Also, they presented the main challenges and several future directions in this area. Another thrust of Bitcoin entity research, closer to our own interest, has focused on the community discovery. At present, there is not much literature on the Bitcoin network community. Researchers mainly focused on analyzing the network graph property of various communities [8] and then speculating on the characteristics of large entities in the Bitcoin network [10]. Therefore, studying the network of the community, obtaining the structure of the community, and then explaining the transaction pattern of the large Bitcoin community are our research goals in the future. Blockchain technology is favored by many people, because it breaks the traditional centralization and establishes a trust mechanism. The birth of the Bitcoin system, based on blockchain technology, makes it easier and faster to transact among people. The anonymity and decentralization of the Bitcoin system play an important role when people use it to conduct peer-to-peer transactions. Meanwhile, the anonymity of Bitcoin also provides protection for some illegal transactions. Since anyone can create multiple Bitcoin accounts for transactions on the network where their identity is represented by a Bitcoin address consisting of numbers and letters, Bitcoin address cannot reflect the identity of the transaction entity. At the same time, some illegal entities rarely reuse addresses to avoid tracking from enforcement agencies, and instead, they create new addresses for each transaction to reduce their presence on the network. However, previous studies [13] indicated that with the combination of off-chain information [14], addresses could be clustered to the same transaction entity by analyzing the transaction records of addresses in the full ledger data of blockchain , which is beneficial to further identifying entities and inferring relationships between entities. On the other hand, it also exposes the problems of anonymous Bitcoin system mechanisms. Researchers have used these heuristics and off-chain information to develop blockchain analysis software, such as Bitlodine [15], Bitconeview [16], Bitconduite [17] and Bitextract [18]. In this study, we aimed to cluster the addresses using existing heuristic algorithm comprehensively based on the previous work, and to further explore the potential relationships between entities using community detection algorithm.

Contributions of this article
The main contributions of this paper are as follows.
(1). The current methods of Bitcoin address clustering are analyzed and summarized in detail. This paper also aims to explore the relationship among Bitcoin addresses comprehensively, so as to improve the degree of address aggregation.
(2). We analyze the reasons for the low accuracy of detection of Bitcoin change address, combine with a variety of limited conditions for detection of change address, and propose a change address detection process based on different number of output address transactions.
(3). We use the Louvain community detection algorithm and combine the idea of complex network to analyze the relationship among transaction entities, to detect the potential relationships between entities, which could not be identified by ordinary heuristic algorithm.
(4). The clustering rules of the well-known wallet analysis website(wallet explorer, a smart Bitcoin block explorer) are revealed for the first time, and the rules for marking the change address of the website are obtained. And all of these rules are confirmed by the website developer. (5). Through a large amount of data and experiments, we have proved the effectiveness of applying multiple heuristic algorithms, and we can analyze bitcoin transaction activities (e.g. mixing service ) using the research methods of the paper, thus laying a good foundation for the identification of transaction entities.
The remaining of the paper is organized as follows. In Section 2, we briefly introduce the traceability of Bitcoin transaction entities. In Section 3, we summarize the current heuristic algorithms, analyze the problems of the change address detection method in detail, and put forward the change address algorithm process after classifying in accordance with the number of output addresses. In Section 4, we use a variety of heuristic algorithms mentioned in Section 3 to carry out experimental implementation. We elaborate the experimental environment and data sources, give the algorithm flow of address clustering and entity community division, and analyze the performance of the experimental results and method. Finally, Section 5 is the conclusion and prospect of this paper.

Traceability of Bitcoin transaction entities
Blockchain technology makes the Bitcoin ledger public, immutable and stable, which provides a solid basis for inferring the identity of the entity.
Bitcoin transactions have the following important characteristics.
(1). Each transaction acquires the sender's private key to sign. (2). Every transaction will be recorded in the blockchain ledger and anyone can view its transaction details.
Transactions are conducted through Bitcoin address by Bitcoin holders. For scattered Bitcoin users, it is difficult for us to label the users who belong to these Bitcoin addresses. This is one of the reasons why it is difficult to trace the entity when a single user conducts illegal transactions. However, except for a single user, there are many large-scale transaction entities in the Bitcoin system, such as Exchanges, gambling companies, mining pools, currency mixing service providers, etc. Since large entities involve many transactions, it is possible for us to extract the transaction characteristics of these large entities through machine learning, and then use the model to identify other unknown entities that are similar but not labeled.
In general, the traceability of the transaction activities of Bitcoin transaction entities can be started from two aspects. On the one hand, cluster analysis of transaction addresses could be used to find the address groups controlled by each transaction entity. On the other hand, collecting off-chain data is also conducive to linking Bitcoin addresses with entity identities, such as the contextual information with bitcoin addresses appearing on various web pages, personal information filled in by users when registering in bitcoin forums, and website data that specifically analyze bitcoin address tags, etc. Through the methods mentioned above, the transaction activities in which the entity participates can be traced and the information dimension of the entity's identity increased as well.

Methodology
Multiple heuristics were used to address clustering to improve the degree of entity aggregation. In this section, we described a total of six heuristic algorithms, and some of the existing methods were improved. Louvain Community Detection Algorithm was used to divide the entities into communities for further analysis of the relationship among entities.

Multiple heuristic address clustering
Satoshi Nakamoto mentioned in his paper [19] Bitcoin: A Peer-to-Peer Electronic Cash System that in order to reduce transaction fees, no one is willing to make small transfers many times, but tends to combine the balances in his multiple accounts to meet the amount required for the transaction. Based on this statement, many scholars have carried out clustering studies on Bitcoin addresses. One of the most important methods is called the common-input-ownership-heuristic. Because the clustering accuracy of this method is truly high, most current analysis of Bitcoin transaction still relies on this method for clustering study of transaction addresses.

Heuristic algorithm (H1): A heuristic algorithm based on transaction input address, common-input-ownership heuristic
According to the protocol of the Bitcoin system, if you want to use the bitcoin of one address, the private key of that address must be provided, which means that the user of the address must sign for the transaction. Consequently, when multiple addresses are used as the input of a transaction together, we believe that all the input addresses of the transaction can be clustered into an address group. In other words, all the input addresses are controlled by the same transaction entity. The clustering accuracy of H1 can reach 100% without considering the fact that users use mixing services to avoid clustering analysis intentionally. A simple example illustrates the transaction process, as shown in the Figure1. In Figure1. (a), the three input addresses belong to the same transaction entity. In the output addresses, the transaction receiver's account is Address 4, the change amount is 0.4 BTC, and the handling fee for this transaction is 0.1 BTC. If a transaction requires no change, as shown in Figure1.(b), the input amount equals the output amount plus the transaction fee.
In addition to the common-input-ownership heuristic, another heuristic for address clustering is the change address detection heuristic algorithm. In the Bitcoin system, every time a transaction occurs, a node will package the transaction and record it on the blockchain ledger. After removing the transfer amount and transaction fees, the remaining bitcoins will be stored in the change address. Obviously, the bitcoin in the change address belongs to the entity where the input address in the transaction is located. Thus, there is an association between the current change address and the input address. That is to say, they are both controlled by the same entity. At the same time, the bitcoins in the change address will be used as the input amount for a later transaction. So, if you can detect the change address in a transaction record over time, you can link multiple transactions together, increasing the degree of aggregation between multiple different addresses. The research of Elli Androulaki [20] and Sarah Meiklejohn [21] et al. also indicates that change address is an important mechanism to enhance user privacy. The vulnerability existing in the anonymous mechanism of Bitcoin once again proves that the recognition of change

Figure1. Common-input-ownership Schematic diagram
Heuristic algorithm (H2): A heuristic algorithm based on transaction input address and output address, change address detection heuristic In previous studies, there were not many researches on bitcoin change address recognition alone, because the accuracy of the change address detected by the four constraints proposed by Sarah Meiklejohn et al is not high enough to be clustered into the same entity with the input address of the transaction. The four constraints for an output address to be determined as a change address are as follows [21]: (1). The address can only be used as the output of transaction once; (2). The transaction that this address participates in is not a Coinbase transaction; (3). The output address is different from the input address.(It is not a "self-change" transaction); (4). There is no other address in the output accounts which is different from the change address and only appears once in the blockchain ledger.
It should be emphasized that "self-change" refers to the fact that in the Bitcoin protocol, the system specifies the change address for the transaction automatically. The common practice is to provide a change address that is the same as the input address. We should eliminate this kind of "self-change" transaction when we detected the change address.
Consequently, we concluded that the cause of low accuracy of change address clustering mainly lies in: (1). The heuristic condition is based on empirical observation and has strong subjectivity； (2). Bitcoin transaction happens all the time. The first of the four qualifications proposed by Sarah Meiklejohn et al.
required traversal of the entire blockchain ledger transaction data to ensure the address is only used as the output of a transaction once. This process is quite time consuming. And the data set that people used to conduct the experiment could not have included the transaction records that were generated during the experiment. People usually tend to take a certain time node as the criterion and only analyze the transaction data within that time period； (3). The change address can be used as input for a subsequent transaction. When a non-change address is associated with the input address of multiple other transactions, the program cannot detect such an error. Then a large number of addresses are clustered through multiple iteration cycles, and they are wrongly assigned to the same entity. This makes it more troublesome to find and eliminate such false positives when we conduct data inspection in the later stage.
On the basis of previous studies about the detection method of change address, this paper synthesizes the limiting conditions of many scholars on the change address. At the same time, we classify the number of the output address of the transaction, and put forward the process of change address identification.
The change address detection algorithm proposed in this paper can be divided into the following two situations for discussion.
(1). There are only two output addresses for a transaction. a) In the blockchain ledger, address A1 appears only once, while address A2 appears more than once; b) The amount of A1 has more than three decimal places than A2.
If A1 meets the above two conditions, A1 is considered to be a change address.
(2). There are more than two output addresses for a transaction.
When the number of output addresses exceeds two, it can be marked as a change address if a certain output address meets the four qualification conditions proposed by Arah Meiklejohn et al.. The four conditions are described above and will not be repeated here.
In summary, this paper proposed the detection process of change address, as shown in Figure 2.
Output address A1 Determine whether A1 appears only once in all the outputs of the transaction ledger data  Figure 2. Change address detection process Next, combined with the common input ownership heuristic, the change address is used as a link to connect multiple transactions, and then the correlation clustering analysis is conducted for more addresses.
Heuristic algorithm (H3): A heuristic algorithm based on transaction output address, Coinbase transaction mining address clustering heuristic In the Bitcoin system, when a transaction occurs, a node will package the transaction and record it on the blockchain ledger. In this process, the full node is calculated by a random number to obtain the right to billing. When a full node completes transaction packaging first and passes the entire network verification, the node will receive a mining reward. This is a minting transaction belonging to the current block, also known as a Coinbase transaction or a mining transaction. Specifically, in the early days when the Bitcoin system was launched, mining could be divided into two situations: pit mining and single miner mining. However, with the development of technology, the situation of self-mining by users is disappearing gradually, and the trend of mining is evolving towards the emergence of large mining pools. The main reason is that individual miners not only need to spend more money when mining, but also need to purchase mining-specific Application Specific Integrated Circuit (ASIC) chips to get faster computing efficiency. On the other hand, he has to undertake other responsibilities besides mining as a full node, such as maintaining the UTXO set in memory and monitoring the transaction information on the Bitcoin network to verify the validity of the transaction. For pool mining, the owner of the pool will gather the miners together and use a full node to drive a number of mining machines, in which each miner is only responsible for calculating the hash value, and the income from mining belongs to the owner. In the later stage, the owner will conduct secondary distribution of the income according to the proof of work of each miner. As a result, more and more miners are inclined to join the mining pool to reduce the financial and time costs and obtain more stable income. To sum up, we can assume that the output address of a Coinbase transaction is controlled by the same entity. An example of a Coinbase transaction is shown in Figure 3. The difference between H4 and H3 is that the clustering objects of H4 are for multiple mining pools. The heuristic clustering rule is that if there are more than one hundred output addresses in a transaction, and one of the output addresses is known to belong to a certain mining pool, then we assign all output addresses to the mine owner of the certain mining pool [22]. Figure 4, if the Mining pool 1 in the output address is known to be Ant Pool, then the Mining income of all other Mining pools belongs to Ant Pool.

Entity relationship recognition Heuristic algorithm (H5): A heuristic algorithm based on equal currency multi-input multi-output, mixed transaction recognition heuristic
The anonymity of Bitcoin brings convenience for people's transactions and protects the privacy of both parties to the transaction at the same time. Although several heuristic algorithms mentioned above can identify the address group controlled by a single entity, this is a judgment without considering the mixed currency transactions. The mixing service exposes the pseudo anonymity of Bitcoin. The mechanism of the mixing service is that if someone wants to transfer illegally through Bitcoin, he can use the mixing service to hide the illegal proceeds. Mixing services enable users to mix with other users' funds quickly and efficiently and create random mapping relationships between existing user accounts and new accounts to achieve anonymity. Simply put, a mixed transaction is a transaction consisting of multiple inputs and multiple outputs, which makes it difficult to find a one-to-one mapping between the input address and the output address. Thus, it is necessary for regulators to identify mixed currency transactions to narrow the scope of investigation of illegal entities. Judging from the transaction characteristics, we assume that if there are more than four input addresses and output addresses of a transaction, there will be mixed transactions in the transaction [24]. The schematic diagram of mixing service is shown in Figure 5. Based on a large number of address groups clustered by the four heuristic algorithms (H1 to H4), we used Louvain community detection algorithm to further explore the relationship between entities, such as group activities between two different entities through intermediary, so as to achieve the purpose of community division of the transaction entity.
We used Louvain algorithm [25] , combined with complex network theory to identify entity relationships.
(1) Evaluation model  Modularity Louvain algorithm uses modularity to evaluate the quality of a community network division [26]. The physical meaning of modularity is the difference between the number of connected edges of nodes in the community and the number of edges under random conditions. Its value range is , and is generally taken as a measure of obvious community structure in the network. can be calculated as follows: The represents the weight of edges between and . When the network is not a weighted graph, the weight of all edges can be regarded as .
refers to the sum of the weights of all the edges connected to node .
represents the sum of the weights of all the edges in the network. is the community to which node belongs.

Function
indicates that if node is in the same cluster as , the return value is , otherwise returns .  The gain of modularity When a new node joins the community, for example, when node is assigned to community where neighbor node is located, the Louvain algorithm will recalculate the modularity of the community.
can be calculated as follows: represents the sum of the weights of all edges in the current community. represents the sum of the weights of all external edges connected to the community . For a single node, the sum of the weights of the edges connected to the external community is equal to the sum of the weights of all the edges connected to it, i.e., .
(2) Iterative process Step 1: Each node in Figure 6 is treated as an independent community. Corresponding to the Bitcoin network, the address group belonging to the same entity is regarded as an independent community, and the initial number of communities is the same as the number of nodes.
Step 2: For each node , we try to assign the node to the community where each of its neighbor nodes is located, calculate ∆Q before and after the assignment, and record the neighbor node with the largest ∆Q. If Max , node I is assigned to the community where the neighbor node of is the largest; otherwise, it remains unchanged.
Step 3: We repeat step 2 until the communities of all nodes no longer change.
Step 4: We compress all nodes in the same community into a new node and recalculate the weights of edges between nodes.
Step 5: We repeat step 1 until there is no change in the modularity of the entire diagram. In this paper, we use the clustering results of H1, H2, H3 and H4 methods as the input of H6.
Step 1: Groups of addresses belonging to the same entity were clustered by H1, H2, H3, and H4 were used as nodes of the network. At this point, a community corresponds to an entity.
Step 2: To consider the relationship among the entities in the experimental data set, we added an edge between the entities if they meet the following two conditions [27].
-There are less than 10 entities in the output of the transaction; -All recipients are different from the sender.

Experiments and results
In this section, we explained the experimental environment and data sources. We discussed the specific process of the experiment and analyzed the results of the experiment. This included the results of the address aggregation analysis, the effectiveness of the change address detection algorithm, and the entity relationship recognition results.

Experiental environment and data preparation
The experimental data used in this experiment is divided into two parts. One is the Bitcoin addresses to be clustered, and the other one is all transaction records in which these addresses participate. Firstly, we designed a web crawler to crawl Bitcoin addresses. We obtained the Bitcoin address filled in by the user from the user interface in the Bitcointalk forum 1 . The user interface with the bitcoin address is shown in Figure 7. As of February 2021, the forum has approximately 3.1 million user registrations. We crawled the information of the first 30,000 registered users since the establishment of the forum and saved it in csv format.
The record of all transactions that a Bitcoin address participates in comes from the blockchain ledger. We extracted the key fields of information such as the transaction hash of the experimental address, the transaction amount, the hash of the transaction record in which the experimental address participated, and the input and output addresses. And we saved the information in json format.
The operating environment of our experiment is shown in the Table 1.

Experiment process
In this section, we explained the algorithm process of experimental scheme clustering, including the multi-heuristic address clustering algorithm process and entity community division process respectively.

Address clustering process
We combined H1 with the improved change address detection algorithm H2, H3 and H4 to cluster the addresses we collected from the Bitcoin Forum. The clustering algorithm flow is as follows. m--; 26:return ClusterList. Since Bitcoin transactions occur all the time, to reduce the complexity of the experiment, we obtained all transactions involving addresses to be identified in the blockchain ledger (as of September 10, 2020). In the process of detecting the change address in the output of the transaction, we put the change address founded by the program into the list separately for subsequent analysis of the accuracy of the change address.

Community division process
In the initial stage, we regarded a single entity clustered by H1 + H2 + H3 + H4 as an independent community. The number of initial communities is the same as the number of entities. Then, using the complex network idea, edges are added between entities to form an entity transaction network under the two conditions mentioned above. Then we use Louvain algorithm to divide the community. The algorithmic process for dividing the entity community is as follows.

Algorithm 2:
The entity community division algorithm Input: The result of addresses clustering by H1 + H2 + H3 + H4; Output: Community user set. 1:Extract all transactions for the experimental address; 2:Build a transaction network diagram; 3: Initialize best_partition ; 4: while true: 5: while true: 6: for in : 7: Add node to neighbor node and calculate ∆Q; 8: Move into the community where ∆Q is largest; 9: if no vertex moves to new community: 10: break; 11: Rebuild the community, compress all nodes in the same community into a new node； 12: if best_partition not change: 13: break; 14:return communities.

Address clustering results analysis
We selected an address randomly from the experimental data set for analysis. We take the address 18yVghacMaDU8SzG487h2eQvj2SaUCbtXj as an example and iterate twice under the methods H1, H1 + H2, H1 + H2 + H3, and H1 + H2 + H3 + H4 respectively. Through experiments, we found that under different heuristic conditions, the number of addresses obtained was 35,39,120 and 6,469. The result was shown in Figure 8. We plotted them on a logarithmic 10-scale. From the experimental results, it can be seen that one more heuristic condition used, the number of clustered addresses increased with that. This is due to the fact that with each iteration, new addresses associated with the destination address are incorporated into the entity. Also, we need to traverse the transaction records of these new addresses in order to continue to associate with other addresses in the next iteration. By comparison, the number of clustered addresses in our method after two iterations is far more than the number of addresses marked for the wallet belonging to the experimental address in WalletExplorer.
In addition, we noticed that many previous works did not explain the clustering rules of WalletExplorer when comparing their experimental results with WalletExplorer. Therefore, we revealed the rules for address clustering of the website. We found that Walletexplorer adopt the first heuristic algorithm to cluster address that we mentioned in the previous section, so the clustering results of this website can only be used to verify the effectiveness of H1. You can find the interpretation from the website 2 .Besides, we found that the site also marked the change address in each transaction (if already present). Meanwhile, we also inferred the rules of the website for marking the change address through experiments, and obtained his confirmation by contacting the Author (Aleš Janda) of the website. The content of this part will be presented in the following chapters.

4.3.2.Validity analysis of change address detection algorithm
Since there is no perfect standard for the detection of change address, no one can say that his work can be absolutely 100% correct in finding change address. However, based on the previous work, we classified the number of different output addresses of transactions and hope it will be helpful to further improve the accuracy of change address detection. In order to prove whether the change address detection algorithm we proposed is more effective than the previous algorithm, we used two methods to verify.
Method 1:Compare and analyze the marking results of Walletexplorer.
Through a large number of experimental analysis on the change address marked in Walletexplorer and the data of its transaction, we found that the website's judgment on the change address is based on only one principle, that is, output is a change address if it belongs to the same wallet as sender. We still analyze the transactions involved in the experimental address selected in this article. After iterating twice through H1 + H2, we compared the experimental results with the change address marked in Walltexplorer, as depicted in Table 2. Obviously, our detection results for change addresses are more comprehensive than Walletexplorer's detection results, and the results identified by our method for each address all include the change address marked by Walletexplorer, and the coincidence rate is 100%.

Target address
Walletexplorer Our method 18y**j 16 18 Method 2: Compare the address reduction rate of different algorithms.
We compare the experimental results of the change address between the original change address algorithm and our improved algorithm. The results (tTable 3) indicated that the original algorithm found 8,821 change addresses, and our integrated algorithm detected 5,751 change addresses. The average contribution of our algorithm to the address reduction rate is 34.8%. By using the two methods above to analyze the effectiveness of change address detection, the experimental results indicated that our integrated algorithm is more effective than the original algorithm.

Analysis of entity relationship recognition results
(1) Mixed currency transaction recognition results We identified a total of 3,252 transactions using the heuristic conditions defined by H5 in the experimental data that may contain mixing services.
(2) Analysis of community division results Using the Louvain algorithm combined with the complex network, the entities clustered by H1 + H2 + H3 + H4 are further divided into communities. Through experiments, we divided 74,286 entity nodes into 1,247 communities. We used Gephi 3 ,a complex network analysis software, to map transaction networks to further visualize the relationships between entities. The entities incidence relation diagram is acquired as depicted in Figure 9.

Conclusion and futher work
This paper reviewed and summarized six heuristic algorithms for address clustering and entity relationship analysis on the basis of previous work. The comprehensive use of multiple heuristic methods to cluster addresses is conducive to clustering the addresses of large entities. We analyzed the reasons for the low accuracy of the detection results of the existing change address algorithm and improved it. The experimental results indicated that our algorithm is more effective than the original algorithm. In addition, we divided the address groups that have been clustered by the first four heuristic algorithms into communities. For future work, we will further expand the experimental data set and consider the conditions of the heuristic algorithm strictly to further improve the accuracy of address clustering. Moreover, we will collect more off-chain information to add more identity dimensions for the transaction entities, so as to achieve the purpose of tracing the transaction entities and some illegal transaction activities.