  Cryptocurrencies aim to replicate physical cash in the digital realm while
removing centralized middlemen. 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 fungibility and anonymity. Even though cryptocurrencies attracted
millions of users in the last decade with their total market cap reaching
approximately one trillion USD, their anonymity guarantees are poorly
understood. Indeed, previous notions of privacy, anonymity, and fungibility 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 fungibility 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 is the first to assess the fungibility of
cryptocurrencies. Among other results, we find that in the studied one-week
interval, the Bitcoin network, on average, provided comparable but quantifiably
more fungibility than the Ethereum network.

Cryptography and Security