Bitcoin transaction chart analysis

1. Introduction

Bitcoin has recently become an increasingly popular cryptocurrency, as users can use it to conduct transactions electronically and to provide greater anonymity than traditional electronic payments. By design, Bitcoin stores all transactions in a public ledger. The initiator and recipient of each transaction are identified only by cryptographic public keys. This leads to a common misconception that Bitcoin inherently provides anonymity. In fact, while Bitcoin's presumed anonymity has enabled new ways of doing business, recent use cases have raised concerns about user privacy. In this paper, we explore the level of anonymity in the Bitcoin system. Our approach is twofold: (i) we annotate the Bitcoin transaction graph by associating Bitcoin public keys with real people (either in a limited or statistical sense). (ii) We run the annotated graph within our graph analysis framework to discover and summarize the behavior of known and unknown users.

2. Contribution

We propose a system for annotating Bitcoin transaction graphs that consists of two parts. First, we develop a system for scraping Bitcoin addresses from public forums. Second, we introduce a mechanism for associating users with transactions using incomplete transaction information. For example, suppose we hear Bob say to Alice: "Yesterday at noon I sent you $100 worth of Bitcoin"; even though we don't know the exact time of the transaction (because 'noon' could be 11:50 or 12:10) or the exact amount (exchange rates often fluctuate significantly), we are still able to derive candidate transactions and associate matching probabilities.

We also proposed a graph analysis framework that can be used to track and cluster user behaviors. For example, on October 25, 2013, without any prior knowledge of the FBI or Silk Road's public key address, our framework suggested that the FBI's seizure of Silk Road's assets was an "interesting" behavior. In addition, through the identification of the annotation system, our system discovered close connections between Silk Road and real users.

3. Background

Recently, several studies [3, 2, 4] have raised potential privacy limitations in Bitcoin transactions. [3] uses external information sources and integrates this information using text discovery and flow analysis techniques to investigate an alleged thief. [4] On the other hand, statistical characteristics of the transaction graph are analyzed to answer questions about typical user behavior, such as spending habits, income habits, and flow habits between different accounts of the same user. In order to achieve stricter privacy in the Bitcoin graph, the authors of [2] proposed adding an extension to Bitcoin to allow the Bitcoin protocol to support completely anonymous currency transactions.

4. Threat Model

4.1 Attacker’s goal: Bind the “real” name of the transaction

The “real name” here could be someone’s real name, or a username from an online public forum (or any other public data resource). The goal is to link a large number of unrelated encrypted IDs to a real user.

4.2 Attacker Capabilities

First, an attacker enters and obtains all public information, including forums, donation sites, public social networks, etc., where the attacker can grab Bitcoin addresses that are leaked intentionally or unintentionally. In other words, the attacker may directly obtain the matching of "real name" and public key from the website.

Second, an attacker may also "eavesdrop" on inaccurate transaction information from a known user. For example, an attacker may eavesdrop on "Alice, my name is Bob, and I sent you $100 worth of Bitcoin yesterday at noon." That is, the attacker may hear the match between the "real name" and some rough transaction information.

Figure 4: Uncertain number of transactions, by uncertain time and approximate dollar value

Continuing with the example at the beginning of this section, assuming the transaction took place in March 2012, we would have a 10% chance of determining Bob's correct public key.

Whether through time fingerprinting tools or by scraping data from online resources, we can add additional annotations to the blockchain that identify the user. In the previous example, the annotations may have relevant probabilities.

5.3 Graphical Analysis

We developed a graph analysis framework that can de-anonymize users’ identities by using publicly available information, such as scraping Bitcoin forum user information or analyzing Bitcoin transaction information. Figure 5 shows the different parts of the framework.

Figure 5: Graphical analysis route used to display user identity, build user network graph, and mark users in web crawling result graph

5.3.1 Trading Chart

Once transactions are extracted from the blockchain, we construct a transaction graph that shows the flow of public key bitcoins over time. Furthermore, the transaction graph is a directed graph where nodes represent public addresses of anonymous individuals or “groups” and directed edges represent specific transactions from source addresses to destination addresses. Because both the source and destination “groups” can artificially create new public-private key pairs for each sub-transaction, many public key addresses may appear only once or a few times in the transaction graph. Also, typical transactions on the blockchain today are multi-input/multi-output transactions. For more details, see [1]. We use a similar technique to [2] to organize the transactions in the graph. In our experiments, we create a 24-hour transaction graph on October 25, 2013. The graph contains 89,806 transactions with 80,030 unique public key addresses. We also create a 7-month transaction graph containing 1,669,728 transactions from March to October 2013 in an attempt to reveal any possible connections between Bitcoin forum users and Silk Road nodes. Later the Silk Road collapsed.

5.3.2 User Graphics

In this section, we focus on a one-day transaction graph, which becomes visually useful for constructing and describing specific behaviors after using our graph analysis algorithm. Using the transaction graph, we construct a proxy directed graph, called the user graph U, which is similar to the one described in [2], but the users, or groups, are composed of public key addresses used in individual transactions. As mentioned in [1], we merge multi-input transactions as if they were initiated by a single user. Since the multi-input public keys are merged together, this allows us to construct the user graph in a way that the set of public key addresses involved in all transactions is passed through. We use existing tools to construct the group/user graph, where the vertices in the graph represent real groups/users and the edges represent transactions between source and destination users. Since we use a 24-hour time period to construct the user graph, our user network is not a perfect representation of the real user network, as public key addresses that appeared before or after this time period may not have had any activity. The user graph for October 25, 2013 contains 54,941 users and 89,806 transactions.

Figure 6: A graph of “groups” as of October 25, 2013. The top 30 page rank nodes are indicated. Although many users are difficult to track, the variety of activities and network behaviors such as communities, individual groups, and large transactions is still striking.

5.4 Page Rank

Due to the nature of Bitcoin transactions in a directed user graph, we can immediately see the similarity between this graph and the graph constructed by search engines. Most search engines, especially Google, use page rank as the most important dimension to distinguish websites. Obviously, the nodes favored by the algorithm in a directed graph, the ones that are easiest to obtain, or in our case, the ones that get enough transactions, are marked as important. We use page rank as a guide to indicate the most interesting nodes or users in our user graph and further investigate their connections with known forum users. Figure 6 shows the user graph on October 25, 2013, with nodes with the highest page rank indicated by larger node areas. As expected, most users are not connected in this graph, which means that these nodes are not very important because they are not attractive to other users. On the other hand, one can notice several activities or transactions related to communities and single groups, and even large transactions are marked by thickened borders. Using the most active public key address data obtained from BlockChain.info, we can conclude that one of the single group nodes, with a lot of inputs and outputs, is actually the Bitcoin gambling website Satoshi Dice.

5.5 User De-anonymization

One very interesting activity was the seizure of the Silk Road Funds, which transferred 324 Bitcoins to a known FBI address in 445 transactions. Our graph analysis algorithm concluded that this particular FBI address was a user with high importance (high page rank node). This validated the effectiveness of our algorithm in roughly selecting nodes of interest, and we can further investigate these high page rank nodes. With this information and the Bitcoin forum user information from the page crawl, we can also work backwards from the transaction to the Bitcoin forum user and find that they were just one step away from the Silk Road node, which means that the forum user just completed a transaction with a Silk Road user. Since DPR was arrested earlier this month, we analyzed the transactions from the 7 months before his arrest (March 25, 2013 to October 25, 2013). We can also find transactions between multiple Bitcoin forum users and the Satoshi Dice website, which means that they may have gambled during these 7 months. More interestingly, we also found some direct transactions between forum users and Wikileaks.

Figure 7: Transaction graph for October 25, 2013. High page rank nodes are shown, and first-level boundaries are annotated with web scraping results. Several notable activities, including the transfer of confiscated Silk Road bitcoins to FBI addresses, appear as high-ranking nodes.

6. Conclusion

In summary, we have shown that the Bitcoin transaction network is not completely anonymous by using several publicly available information, including web scraping and Bitcoin transaction records. Furthermore, we were able to find that some Bitcoin forum users were only separated from the Silk Road nodes by a middleman. We were also able to successfully find direct transactions between Bitcoin forum users and Satoshi Dice and WikiLeaks, suggesting that they may have contact with, involvement with, or support for these groups.