Communications of the ACM

an external observer can make an educated guess that links A′ to the owner of A. Indeed, there has been a growing amount of literature1, 23, 30, 31 showing how the transaction graph can be used to link together addresses. This, combined with external information (for example, vendor purchases) and further heuristic analysis, can lead to user identification. Currently, there even exist Bitcoin tracking companies (for example, Elliptica and Chainalysisb) that monitor the body of transactions, aiming at identifying illicit activity.

Network-level deanonymization. By default, the Bitcoin peer-to-peer protocol does not protect the IP addresses of the participants since they are communicated in the clear. Researchers4 have shown how this information can be used to deduce user identities. However, most Bitcoin client implementations can be configured to run over an anonymous Tor proxy, hiding the participants’ addresses. Unlike what one might expect, this approach does not solve the problem. Subsequent work5 has demonstrated how the interaction between Bitcoin and Tor can be exploited by an adversary who not only compromises user privacy (negating the anonymizing effect of the latter) but can also launch a stealthy man-in-the-middle attack, targeting the security of the Bitcoin protocol itself. While Biyukov5 discusses a number of partial countermeasures, to the best of our knowledge there is no definitive way to protect the network-level anonymity of Bitcoin users yet. One likely candidate solution is the evolution of Bitcoin to operate over a tailor-made anonymity network that will not suffer from the issues discussed here. It should be noted that none of the techniques we mention in the sequel addresses network anonymity explicitly.

Real-world anonymity. We stress the
gap between anonymity as a property
of the cryptocurrency protocol execu-
tion and “real-world anonymity.” For
example, when one uses a crypto-
currency to purchase goods or services
from a vendor they must provide the
latter with certain personal informa-
tion (identity for registration, physi-
cal address for delivery, email for pur-
a https://www.elliptic.co
b https://www.chainalysis.com
by design, aim to achieve strong privacy
properties. We discuss and compare the
privacy guarantees achieved by known
mechanisms, as well as their perfor-
mance and practical adoption.

Background: Bitcoin and Privacy

Bitcoin in a nutshell. The full mechanics of the Bitcoin protocol are rather involved and we refer interested readers to Bonneau et al. 7 and Nakamoto28 (also see the "Inside Risks" column p. 20 in this issue). In the sequel, we provide a high-level abstraction of the protocol, highlighting the aspects that have the most impact on user privacy. A Bitcoin user participates in the protocol by first generating a cryptographic public/private key pair. The first operates as her public address: she can use it to send money to or receive money from other users in the same way one uses a bank account. Unlike a bank account though, a user can generate as many public/private key pairs as she wants—even one for every transaction. A simple transaction from user A to B contains a declaration of “A sends x bitcoins to B” signed with A’s secret key.

These transactions are propagated
via a flooding mechanism over an ad
hoc, peer-to-peer network and are thus
visible to every participant. Special us-
ers known as miners collect transac-
tions and store them into blocks. These
blocks are subsequently stored in a glob-
al public ledger of transactions known
as blockchain. This chain is a sequential
order of blocks, each of which referenc-
es the previous one. Who appends the
latest block is decided in a randomized
manner using a proof-of-work mecha-
nism that generally guarantees that the
amount of blocks a miner gets to gener-
ate (receiving a corresponding miner’s
fee) is proportional to the ratio of its
computational power over the total pow-
er of all miners in the protocol.
In order for a miner to add a transac-
tion in the next block it must first be val-
idated. Consider the case of the transac-
tion from A to B. Before adding it to the
current block, the miner must check
that it is signed by A, and A did not pre-
viously spend these bitcoins. The for-
mer is easy to achieve given the public
key of A (embedded in the transaction).
The latter can be verified by tracing A’s
entire transaction history to check that
the bitcoins in question where not pre-
viously spent (in practice, it suffices to
just trace unspent transactions).

Deanonymization attacks. This scenario highlights a crucial issue regarding Bitcoin’s privacy: Transaction validation is founded on public access to the transaction history. While the physical identity of the owner of address A (Alice) cannot be directly deduced from this, any observer can see that the same individual performed a given set of transactions. Even worse, although Alice can always create a new address A′ she might have to transfer money from her old one to the new one in order to use it, at which point