  Cryptocurrencies aim to replicate physical cash in the digital realm while
removing centralized and trusted intermediaries. Decentralization is achieved
by the blockchain, a permanent public ledger that contains a record of every
transaction. The public ledger ensures transparency, which enables public
verifiability but harms untraceability, fungibility, and anonymity. In the last
decade, cryptocurrencies attracted millions of users, with their total market
cap reaching approximately three trillion USD at its peak. However, their
anonymity guarantees are poorly understood and plagued by widespread
misbeliefs. Indeed, previous notions of privacy, anonymity, and traceability
for cryptocurrencies are either non-quantitative or inapplicable, e.g.,
computationally hard to measure.
  In this work, we put forward a formal framework to measure the
(un)traceability and anonymity of cryptocurrencies, allowing us to
quantitatively reason about the mixing characteristics of cryptocurrencies and
the privacy-enhancing technologies built on top of them. Our methods apply
absorbing Markov chains combined with Shannon entropy. To the best of our
knowledge, our work provides the first practical, efficient, and probabilistic
measure to assess the traceability of cryptocurrencies quantitatively, which
also generalizes to entire cryptocurrency transaction graphs. We implement and
extensively evaluate our proposed traceability measure on several
cryptocurrency transaction graphs. Among other quantitative results, we find
that in the studied one-week interval, the Bitcoin blockchain, on average,
provided comparable but quantifiably more natural mixing than the Ethereum
blockchain.
