Towards Measuring The Fungibility and Anonymity of Cryptocurrencies

Domokos Miklós Kelen, István András Seres

Abstract

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.

Introduction

While cryptocurrencies are often marketed for their anonymity, most operate on public ledgers where every transaction is visible. This transparency creates a significant traceability problem: if an observer can link a coin back to its source—such as a coinbase transaction or a known exchange address—privacy is effectively lost. Existing metrics for privacy, such as $k$-anonymity or the Boltzmann score, are often non-quantitative, fail to account for the probabilistic nature of fund flows, or are computationally prohibitive (NP-hard) for large-scale transaction graphs. This work addresses these gaps by introducing a mathematically rigorous "untraceability score" that is both fine-grained and computationally feasible for real-world datasets.

Methodology

The proposed framework represents the blockchain as a weighted, directed transaction graph. To quantify untraceability, the authors employ a novel three-step approach:

  1. Reversing the Flow: The edges of the transaction graph are reversed to model the process of tracing funds backward to their origins. Transition probabilities are assigned based on the relative weights of inputs and outputs.
Reversing the transaction flow to calculate transition probabilities for a single transaction.
  1. Absorbing Markov Chains: The reversed graph is converted into an absorbing Markov chain. In this model, "source" nodes (e.g., coinbase transactions where new coins are minted) act as absorbing states. A random walk starting from a specific coin will eventually be absorbed by one or more of these sources.
Modeling a sequence of transactions as an absorbing Markov chain where source nodes act as absorbers.
  1. Shannon Entropy: The core metric is the Shannon entropy of the absorption probabilities. A coin with a 100% probability of originating from a single source has an entropy of zero, indicating zero untraceability. Conversely, a coin that could have originated from thousands of sources with equal probability yields a high untraceability score.

To ensure computational efficiency for graphs with millions of nodes, the authors utilize an iterative approximation for the fundamental matrix of the Markov chain. The framework further distinguishes between objective traceability (visible on the ledger) and subjective traceability (incorporating external adversarial knowledge, such as IP addresses).

Experimental Evaluation

The metric was evaluated on a one-week snapshot (February 1–8, 2021) of five major crypto-assets: Bitcoin (8.6M nodes), Ethereum (3.0M nodes), Zcash (170k nodes), and ERC-20 tokens DAI and USDC.

Key Results

  • Network Comparison: The evaluation revealed that the account-based model (Ethereum) generally exhibits lower untraceability than the UTXO model (Bitcoin). Bitcoin averaged 3.96 bits of entropy, while Ethereum averaged 3.45 bits, indicating that Bitcoin provided quantifiably more "natural mixing" during the study period.
  • Transaction Depth: Random walks in Bitcoin took an average of 25.23 steps to be absorbed, significantly longer than the 7.27 steps observed in Ethereum.
  • Privacy Technologies: Zcash exhibited the highest maximum untraceability (15.70 bits) due to the uncertainty introduced by its shielded pool, which acts as a highly effective mixer.
  • Stablecoins: Despite sharing the same ERC-20 technology, DAI and USDC showed distinct traceability characteristics, suggesting that user behavior and volume are critical factors in natural privacy.

Conclusion

This work provides the first practical and efficient probabilistic measure for cryptocurrency traceability. By utilizing absorbing Markov chains and Shannon entropy, the framework allows for quantitative comparisons between different blockchain architectures and privacy-enhancing technologies. Future work includes applying this metric to other protocols like Monero or Bitcoin’s CoinJoin and integrating it into privacy-focused wallets to assist users in managing their financial privacy.

Summary updated

Abstract

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.
BibTeX
@inproceedings{kelen2025towards,
  author = {Domokos Miklós Kelen and István András Seres},
  title = {{Towards Measuring The Fungibility and Anonymity of Cryptocurrencies}},
  booktitle = {ICBC},
  year = {2025},
  doi = {10.1109/icbc64466.2025.11114667},
}
Figure