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.
H( ) = 00000...
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.
50 BTC BTC Guild Itzod
ABC Pool Deepbit Ozcoin
Bitclockers EclipseMC Slush
Bitcoin Faucet Easywallet Strongcoin
My Wallet Flexcoin WalletBit
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
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
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
Bit Visitor Bitfog CoinAd
Bitcoin Advertizers Bitlaundry Coinapult
Bitcoin Laundry BitMix Wikileaks
Table 1. The various services we interacted with, grouped by