90 COMMUNICATIONS OF THE ACM | APRIL 2016 | VOL. 59 | NO. 4
transaction (according to Heuristic 1) but also the change
address and the input user.
Because our heuristic takes advantage of this idiom of
use, rather than an inherent property of the Bitcoin protocol, it does lack robustness in the face of changing (or adversarial) patterns in the network. Furthermore, it has one very
negative potential consequence: falsely linking even a small
number of change addresses might collapse the entire graph
into large “super-clusters” that are not actually controlled
by a single user (in fact, we see this exact problem occur in
Section 4. 2). We therefore focused on designing the safest
heuristic possible, even at the expense of losing some utility
by having a high false negative rate, and acknowledge that
such a heuristic might have to be redesigned or ultimately
discarded if habitual uses of the Bitcoin protocol change
significantly.
Working off the assumption that a change address has
only one input (again, as it is potentially unknown to its owner
and is not re-used by the client), we first looked at the outputs
of every transaction. If only one of the outputs met this pattern, then we identified that output as the change address. If,
however, multiple outputs had only one input and thus the
change address was ambiguous, we did not label any change
address for that transaction. We also avoided certain transactions; for example, in a coin generation, none of the outputs
are change addresses.
In addition, in custom usages of the Bitcoin protocol it
is possible to specify the change address for a given transaction. Thus far, one common usage of this setting that we
have observed has been to provide a change address that is
in fact the same as the input address. (This usage is quite
common: 23% of all transactions in the first half of 2013 used
self-change addresses.) We thus avoid such “self-change”
transactions as well.
To bring all of these behaviors together, we say that an
address is a one-time change address for a transaction if the
following four conditions are met: ( 1) the address has not
appeared in any previous transaction; ( 2) the transaction is
not a coin generation; ( 3) there is no self-change address;
and ( 4) all the other output addresses in the transaction have
appeared in previous transactions. Heuristic 2 then says that
the one-time change address—if one exists—is controlled by
the same user as the input addresses.
4. 2. Refining Heuristic 2
Although effective, Heuristic 2 is more challenging
and significantly less safe than Heuristic 1. In our first
attempt, when we used it as defined above, we identified
over 4 million change addresses. Due to our concern over
its safety, we sought to approximate the false positive rate.
To do this even in the absence of significant ground truth
data, we used the fact that we could observe the behavior
of addresses over time: if an address looked like a one-time change address at one point in time (where time
was measured by block height), and then at a later time
the address was used again, we considered this a false
positive. Stepping through time in this manner allowed
us to identify 555,348 false positives, or 13% of all labeled
change addresses.
We then considered ways of making the heuristic more
conservative. First, however, a manual inspection of some of
these false positives revealed an interesting pattern: many of
them were associated with transactions to and from Satoshi
Dice and other dice games. By looking further into the payout structure of these games, it became clear that these were
not truly false positives, as when coins are sent to Satoshi
Dice, the payout is sent back to the same address. If a user
therefore spent the contents of a one-time change address
with Satoshi Dice, the address would receive another input
back from Satoshi Dice, which would appear to invalidate the
“one-timeness” of the address. We therefore chose to ignore
this case, believing that addresses that received later inputs
solely from Satoshi Dice could still be one-time change
addresses. By doing so the false positive rate reduces to
only 1%. We next considered waiting to label an address as a
change address; that is, waiting to see if it received another
input. Waiting a day drove the false positive rate down to
0.28%; waiting a week drove it down to 0.17%, or only 7382
false positives total.
Despite all these precautions, when we clustered users
using this modified heuristic, we still ended up with a
giant super-cluster containing the addresses of Mt. Gox,
Instawallet, BitPay, and Silk Road, among others; in total,
this super-cluster contained 1. 6 million addresses. After
a manual inspection of some of the links that led to this
super-cluster, we discovered two problematic patterns.
First, especially within a short window of time, the same
change address was sometimes used twice. Second, certain
addresses were occasionally used as “self-change” addresses,
and then later used as separate change addresses. We thus further refined our heuristic by ignoring transactions involved
with either of these types of behavior. For transactions in
which an output address had already received only one
input, or for transactions in which an output address had
been previously used in a self-change transaction, we chose
to not tag anything as the change address. Doing so, and
manually removing a handful of other false positives (with
no discernible pattern), we identified 3,540,831 change
addresses.
Using this refined Heuristic 2 produces 3,384,179 clusters, which we were able to again collapse slightly (using our
tags) to 3,383,904 distinct clusters. Of these clusters, we were
able to name 2197 of them (accounting for over 1. 8 million
addresses). Although this might seem like a small fraction,
recall that by participating in 344 transactions we hand-tagged only 1070 addresses, and thus Heuristic 2 allowed
us to name 1600 times more addresses than our own manual observation provided. Furthermore, as we will argue in
Section 5, the users we were able to name capture an important and active slice of the Bitcoin network.
Having finally convinced ourselves of the safety of Heuristic
2, by refining it substantially, and its effectiveness, we use
Heuristic 2 exclusively for the results in the next section.
5. ANALYSIS OF ILLICIT ACTIVITY
Exchanges have essentially become chokepoints in the
Bitcoin economy, in the sense that it is unavoidable to
buy into or cash out of Bitcoin at scale without using an
