88 COMMUNICATIONS OF THE ACM | APRIL 2016 | VOL. 59 | NO. 4 generating a block is so computationally difficult that very few individual users attempt it on their own. Instead, users may join a mining pool, in which they contribute “shares” to narrow down the search space, and earn a small amount of bitcoins in exchange for each share.

Users may also avoid coin generation entirely, and simply purchase bitcoins through one of the many exchanges. They may then keep the bitcoins in a wallet stored on their computer or, to make matters even easier, use a wallet service (although many wallet services have suffered thefts and been shut down).

Finally, to actually spend their bitcoins, users could gamble with one of the popular dice games such as Satoshi Dice. They could also buy items from various online vendors. Finally, users wishing to go beyond basic currency speculation can invest their bitcoins with firms such as Bitcoinica (shut down after a series of thefts) or Bitcoin Savings & Trust (later revealed as a major Ponzi scheme).

3. DATA COLLECTION

To identify addresses belonging to the types of services mentioned in Section 2. 2, we sought to “tag” as many addresses as possible; that is, label an address as being definitively controlled by some known real-world user. As we will see in Section 4. 1, by clustering addresses based on evidence of shared control, we can bootstrap off the minimal ground truth data this provides to tag entire clusters of addresses as also belonging to that user.

Our predominant method for tagging users was simply transacting with them (e.g., depositing into and withdrawing bitcoins from Mt. Gox) and then observing the addresses they used. We additionally collected known (or assumed) addresses that we found in various forums and other Web sites, although we regarded this latter kind of tagging as less reliable than our own observed data.

3. 1. From our own transactions

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.

Mining pools. We mined bitcoins using an AMD Radeon HD 7970, capable of approximately 530 million SHA-256 computations per second, which allowed us to trigger a payout of at least 0.1 BTC with 11 different pools, anywhere from 1 to 25 times. For each payout transaction, we then labeled the input addresses as belonging to the pool.

Wallets. We kept money with most of the major wallet services ( 10 in total), and made multiple deposit and withdrawal transactions for each.

Bank exchanges. Most of the real-time trading exchanges (i.e., in which the exchange rate is not fixed) also function as banks. As such, we tagged these services just as we did the wallets: by depositing into and withdrawing from our accounts. We kept accounts with 18 such exchanges in total.

mpk mpk merchant

1

2

3

4

tx tx ...

?

56
user
miner
block
H( ) = 00000...

tx tx = Sign(upk0.7mpk)

Figure 1. How a Bitcoin transaction works; in this example, a user wants to send 0.7 bitcoins as payment to a merchant. In ( 1), the merchant generates or picks an address mpk, and in ( 2) it sends this address to the user. In ( 3), the user forms the transaction tx to transfer the 0.7 BTC from upk to mpk. In ( 4), the user broadcasts this transaction to his peers, which (if the transaction is valid) allows it to flood the network. In this way, a miner learns about his transaction.

In ( 5), the miner works to incorporate this and other transactions into a block by checking if their hash is within some target range. In ( 6), the miner broadcasts this block to her peers, which (if the block is valid) allows it to flood the network. In this way, the merchant learns that the transaction has been accepted into the global block chain, and thus receives the user’s payment.

Mining

50 BTC BTC Guild Itzod ABC Pool Deepbit Ozcoin Bitclockers EclipseMC Slush Bitminter Eligius

Wallets

Bitcoin Faucet Easywallet Strongcoin My Wallet Flexcoin WalletBit Coinbase Instawallet Easycoin Paytunia

Exchanges

Bitcoin 24 BTC-e Aurum Xchange Bitcoin Central CampBX BitInstant Bitcoin.de CA VirtEx Bitcoin Nordic Bitcurex ICBit BTC Quick Bitfloor Mercado Bitcoin FastCash4Bitcoins Bitmarket Mt Gox Lilion Transfer Bitme The Rock Nanaimo Gold Bitstamp Vircurex OKPay BTC China Virwox

Vendors

ABU Games BTC Buy HealthRX Bitbrew BTC Gadgets JJ Games Bitdomain Casascius NZBs R Us Bitmit Coinabul Silk Road Bitpay CoinDL WalletBit Bit Usenet Etsy Yoku Gambling

Bit Elfin BitZino Gold Game Land Bitcoin 24/7 BTC Griffin Satoshi Dice Bitcoin Darts BTC Lucky Seals with Clubs Bitcoin Kamikaze BTC on Tilt Bitcoin Minefield Clone Dice

Miscellaneous

Bit Visitor Bitfog CoinAd Bitcoin Advertizers Bitlaundry Coinapult Bitcoin Laundry BitMix Wikileaks Table 1. The various services we interacted with, grouped by (approximate) type.