chase confirmation, and so on). Thus, the vendor can trivially link the public key with its owner, in a strong sense. Moreover, this information may be extracted by others (for example, in case the vendor is hacked or a government agency issues a subpoena). Combined with “Know-your-Customer” anti-money laundering policies that enforce the collection of such data (like the one included in the USA Patriot Act of 2001) this can seriously compromise the privacy of cryptocurrency users.

Bitcoin Mixing

As discussed, a Bitcoin address can be potentially mapped to a physical entity by examining its related history of transactions (namely edges on the transaction graph) that are stored on the publicly accessible blockchain. This has prompted researchers to introduce various techniques for achieving anonymity. 22 One such prominent approach is Bitcoin mixing (or Bitcoin tumbling).

Suppose each one of the addresses A, B, C, and D wish to send one bitcoin to addresses A′, B′, C′, and D′ respectively. If these transactions are posted directly on the blockchain, everybody can deduce exactly how money flows. Bitcoin mixing “mixes” these transactions so the amount of information that becomes public is minimized— with Bitcoin mixing one would just find out that A’s bitcoin went to one of A′, B′, C′, or D′, but not to which address exactly. The simplest way to achieve that is to use a trusted mixer (as we will discuss) who first receives the money from A, B, C, and D and then sends the money to A′, B′, C′, and D′ respectively. Clearly such an approach does not reveal information about the exact transaction edges. In order for this process to truly hide the link between input and output addresses, all users must participate with the same amount. (One can always use a larger amount and specify a fresh “change” address.) This provides privacy similar to k-anonymity36 (assuming k participants) since no observer can distinguish which coins end up at each recipient.

Bitcoin mixing methods. There are
various ways of Bitcoin mixing, achiev-
ing different levels of privacy, security,
and efficiency. One key distinction has
to do with how the parties that partici-
pate are coordinated. In theory, it is
always possible for a party that wants
to mix its coins to find a friend with
similar goals and coordinate the ex-
change of some amount of bitcoins via
an out-of-bound channel (for example,
phone). This is a valid solution but in
order to truly improve their privacy,
users should try to hide inside a set of
parties that is as large as possible. On
the other hand, point-to-point coordi-
nation of hundreds or thousands of us-
ers can be very impractical, especially
if the execution of the mixing protocol
requires multiple rounds of commu-
nication. Therefore, many centralized
solutions have been proposed where a
third-party server, that receives a mix-
ing fee, is utilized to handle the logis-
tics of the transaction, under varying
threat models (fully trusted, account-
able, or untrusted). Finally, one must
consider whether or not the identities
of the mixing participants (or even the
link between sender and recipient) will
be revealed to other participants.
Centralized mixers. The simplest
and easiest way to implement a form
of Bitcoin mixing is via a trusted third
party that serves as the mixer (shown
in Figure 1). To send an amount of bit-
coins from an address A to another ad-
dress A′, A first performs a transaction
transferring a fixed amount to the mix-
er and sends an encryption of A′ under
the mixer’s public key to the latter. Af-
ter collecting a number of such trans-
actions (assuming the same amount
in each transaction) from multiple
users—or, alternatively, after a cer-
tain amount of time has elapsed—the
mixer sends, in a single Bitcoin trans-
action containing the recipients’ ad-
dresses in a randomly permuted order,
the same amount back to recipients’
addresses. This achieves k-anonymity
for a set that is as large as the number
of parties that use the mixer within
the given time increment, as there is
no way for an external observer to dis-
tinguish the mapping between input
and output addresses. The anonymity
set can be further increased beyond
the number of parties that use the
mixer in the given time increment by
sequentially mixing the coins mul-
tiple times (using several mix transac-
tions), at the cost of reduced efficien-
cy. One thing to note is this approach
does not hide the fact these users used
the mixer (and may, therefore, have
A Bitcoin address
can be potentially
mapped to a
physical entity
by examining its
related history of
transactions that
are stored on the
publicly accessible
blockchain.