"A Fistful of Bitcoins: Characterizing Payments Among Men with No Names", Meiklejohn et al 2013; excerpts:

"Bitcoin has the un-intuitive property that while the ownership of money is implicitly anonymous, its flow is globally visible. In this paper we explore this unique characteristic further, using heuristic clustering to group Bitcoin wallets based on evidence of shared authority, and then using re-identification attacks (i.e., empirical purchasing of goods and services) to classify the operators of those clusters. From this analysis, we characterize longitudinal changes in the Bitcoin market, the stresses these changes are placing on the system, and the challenges for those seeking to use Bitcoin for criminal or fraudulent purposes at scale.

Our methodology has two phases. First, in Section 3, we describe a re-identification attack wherein we open accounts and make purchases from a broad range of known Bitcoin merchants and service providers (e.g., Mt. Gox and Silk Road). Since one endpoint of the transaction is known (i.e., we know which public key we used), we are able to positively label the public key on the other end as belonging to the service; we augment this attack by crawling Bitcoin forums for “self-labeled” public keys (e.g., where an individual or organization explicitly advertises a key as their own). Next, in Section 4, we build on past efforts [2, 17, 18, 21] to cluster public keys based on evidence of shared spending authority. This clustering allows us to amplify the results of our re-identification attack: if we labeled one public key as belonging to Mt. Gox, we can now transitively taint the entire cluster containing this public key as belonging to Mt. Gox as well. The result is a condensed graph, in which nodes represent entire users and services rather than individual public keys.
...Using the dissolution of a large Silk Road wallet and notable Bitcoin thefts as case studies, we demonstrate that an agency with subpoena power would be well placed to identify who is paying money to whom. Indeed, we argue that the increasing dominance of a small number of Bitcoin institutions (most notably services that perform currency exchange), coupled with the public nature of transactions and our ability to label monetary flows to major institutions, ultimately makes Bitcoin unattractive today for high-volume illicit use such as money laundering.

Not surprisingly, until approximately April 2010 — the first 15 months that Bitcoin was deployed — almost all transactions involved exactly 50 bitcoins (the initial reward for mining a block), and indeed these transactions became a minority of all transactions only in January 2011. This activity reflects the adoption phase of Bitcoin, in which most blocks contained the coin generation transaction and nothing more. (In later phases, the mining reward is likely a little more than 50 because it includes miner fees, which is why we created a separate bin for values between 50 and 55.) We also see a second turning point in early 2012, in which the percentage of transactions carrying less than a single bitcoin in total value doubled abruptly (from 20% to 40%), while the percentage of transactions carrying less than 0.1 BTC tripled.
We also observed how quickly bitcoins were spent; i.e., once they were received, how long did it take the recipient to spend them? Figure 3 shows breakdowns both in terms of public keys (how many recipient public keys spent their contents in a certain time window) and in terms of value (how many of the bitcoins that were received were spent in a certain time window).
Looking at this figure, we again see two clear turning points. The first, in early 2011, represents a point at which users began meaningfully spending bitcoins, rather than just “hoarding” them; in fact, from this point on a negligible fraction of bitcoins are hoarded. Nevertheless, these early hoarders in fact took most of the bitcoins out of circulation; as observed by Ron and Shamir [18], a significant majority of all bitcoins are in these “sink” addresses that have to date never spent their contents (at the time they parsed the block chain it was 75%, whereas we observed it to be 64%), meaning only 4 million bitcoins are currently in circulation. Nevertheless, these remaining coins are circulating quite actively, as seen in the second turning point in Figure 3: in April 2012, the percentage of bitcoins being spent immediately (i.e., in the same block in which they were received) doubled, and more generally half of all bitcoins are now spent within an hour of being received and 80% of bitcoins are spent within a day.
As it turns out, and as we see in Section 5.1, both these recent trends of smaller transactions and faster spending can be largely attributed to a single service: the gambling site Satoshi Dice. Thus, even a longitudinal study of the Bitcoin network already makes clear the effect that services have on current Bitcoin usage.

We engaged in 344 transactions with a wide variety of services, listed in Table 1, including mining pools, wallet services, bank exchanges, non-bank exchanges, vendors, gambling sites, and miscellaneous services.

Miscellaneous. Four of the additional services we interacted with were mix or laundry services: when provided with an output address, they promised to send to that address coins that had no association with the ones sent to them; the more sophisticated ones offered to spread the coins out over various transactions and over time. One of these, BitMix, simply stole our money, while Bitcoin Laundry twice sent us our own coins back, indicating we were possibly their only customer at that time.

Figure 4: The physical items we purchased with bitcoins, including silver quarters from Coinabul, coffee from Bitcoin Coffee, and a used Boston CD from Bitmit. The items in green were purchased from CoinDL; in blue from Bitmit; and in red using the payment gateway BitPay.

Because of its immense popularity, and the extent to which it has inflated the size of the block chain (an extra 30,000 transactions translates into an extra 14MB added to the overall block chain daily), the opinion of Satoshi Dice in the Bitcoin community is somewhat mixed: some decry it as a DoS attack,5 while others appreciate that it has stress-tested the Bitcoin network. It might be tempting to additionally think that, given the large amounts of bitcoins flowing through it, Satoshi Dice could act as a mix service:6 if “dirty” bitcoins were gambled using 97% winning odds, and the resulting bitcoins were paid out to a different address, these bitcoins might at first glance appear to have no association with the gambled money (especially if they came from a different address than the gambled money was sent to, as is sometimes the case). Because the addresses that Satoshi Dice uses are public, however, it is trivial to observe when users are gambling; furthermore, in sending a bet to Satoshi Dice, a user must explicitly identify where the payout should be sent. Thus, without using services such as Satoshi Dice as a co-conspirator (which they seem to have no incentive to do, as they made over $500,000 in their first eight months alone [11]), the bitcoins paid out are indelibly linked to the ones that were placed as a bet.

Indeed, the Bitcoin community has recently demonstrated both the inherent traceability of thefts and the unwillingness to accept stolen money (see bitcointalk.org/index.php?topic= 14085.msg1910231). After 923 BTC was stolen from the mining pool Ozcoin and transferred to a Strongcoin wallet, Strongcoin intercepted the bitcoins when the thief attempted to withdraw them and returned them to Ozcoin.

One of the most well-known and heavily scrutinized addresses in Bitcoin’s history is 1DkyBEKt,8 which is believed to be associated with Silk Road and was active between January and September 2012. Starting in January, the address began to receive large aggregate sums of bitcoins; in the first of these, the funds of 128 addresses were combined to deposit 10,000 BTC into the 1DkyBEKt address, and many transactions of this type followed (including one transaction in which the funds of 589 addresses were combined to deposit 8,000 BTC). All together, the address received 613,326 BTC in a period of eight months, receiving its last aggregate deposit on August 16 2012. Then, starting in August 2012, bitcoins were aggregated and withdrawn from 1DkyBEKt: first, amounts of 20,000, 19,000, and 60,000 BTC were aggregated and sent to separate addresses; later, 100,000 BTC each was sent to two distinct addresses, 150,000 BTC to a third, and 158,336 BTC to a fourth, effectively emptying the 1DkyBEKt address of all of its funds. The balance of this address over time, as well as the balance of Silk Road and of vendors as a whole (as we consider Silk Road a vendor), is shown in Figure 8. Due to its large balance (at its height, it contained 5% of all generated bitcoins), as well as the curious nature of its rapidly accumulated wealth and later dissolution, this address has naturally been the subject of heavy scrutiny by the Bitcoin community. While it is largely agreed that the address is associated with Silk Road (and indeed our clustering heuristic did tag this address as being controlled by Silk Road), some have theorized that it was the “hot” (i.e., active) wallet for Silk Road, and that its dissipation represents a changing storage structure for the service. Others, meanwhile, have argued that it was the address belonging to the user pirate@40, who was responsible for carrying out the largest Ponzi scheme in Bitcoin history (the investment scheme Bitcoin Savings & Trust, which is now the subject of a lawsuit brought by the SEC [20]). To see where the funds from this address went, and if they ended up with any known services, we first plotted the balance of each of the major categories of services, as seen in Figure 9. Looking at this figure, it is clear that when the address was dissipated, the resulting funds were not sent en masse to any major services, as the balances of the other categories do not change significantly. To nevertheless attempt to find out where the funds did go, we turn to the traffic analysis described above.
In particular, we focus on the last activity of the 1DkyBEKt address, when it deposited 158,336 BTC into a single address. This address then peeled off 50,000 BTC each to two separate addresses, leaving 58,336 BTC for a third address; each of these addresses then began a peeling chain, which we followed using the methodology described above (i.e., at each hop we continued along the chain by following the change address, and considered the other output address to be a meaningful recipient of the money). After following 100 hops along each chain, we observed peels to the services listed in Table 2.
Looking at this table, we see that, although a longitudinal look at the balances of major services did not reveal where the money went, following these chains revealed that bitcoins were in fact sent to a variety of services. The overall balance was not highly affected, however, as the amounts sent were relatively small and spread out over a handful of transactions. Furthermore, while our analysis does not itself reveal the owner of 1DkyBEKt, the flow of bitcoins from this address to known services demonstrates the prevalence of these services (54 out of 300 peels went to exchanges alone) and provides the potential for further de-anonymization: the evidence that the deposited bitcoins were the direct result of either a Ponzi scheme or the sale of drugs might motivate Mt. Gox or any exchange (e.g., in response to a subpoena) to reveal the account owner corresponding to the deposit address in the peel, and thus provide information to link the address to a real-world user.

Even the thief we had the most difficulty tracking, who stole bitcoins by installing a trojan on the computers of individual users, seemed to realize the difficulty of cashing out at scale. Although we were unable to confidently track the flow of the stolen money that moved, most of the stolen money did not in fact move at all: of the 3,257 BTC stolen to date, 2,857 BTC was still sitting in the thief’s address, and has been since November 2012.

Most recently, Möser [14] examined the anonymity of three Bitcoin mix services, and found that some were more successful than others, although all had a distinct transaction graph pattern due to their centralized nature.

M. Möser. Anonymity of Bitcoin Transactions: An Analysis of Mixing Services. In Proceedings of Münster Bitcoin Conference, 2013. https://www.wi.uni-muenster.de/sites/default/files/public/department/itsecurity/mbc13/mbc13-moeser-paper.pdf "

#bitcoin #silkroad #anonymity