Towards Measuring the Traceability of Cryptocurrencies

Domokos M. Kelen, István András Seres

TL;DR

This paper introduces a novel, formal framework to quantitatively measure the traceability of cryptocurrencies, moving beyond qualitative assessments. By modeling transaction networks as absorbing Markov chains, they provide a practical and efficient metric that allows for direct comparison of different cryptocurrencies and privacy-enhancing technologies.

What Problem Does This Paper Address?

Cryptocurrencies like Bitcoin and Ethereum offer transparency through their public ledgers, but this transparency comes at the cost of user privacy. While the pseudonymous nature of these systems is often misunderstood, the reality is that transaction histories are publicly available, making it possible to trace the flow of funds. This traceability can lead to issues like censorship, blacklisting of addresses, and a general lack of fungibility. Existing methods for assessing privacy or anonymity in this context are often non-quantitative, computationally intractable, or not generalizable to complex transaction graphs. This paper aims to bridge this gap by providing a robust, quantitative measure of traceability.

Methods

The core of the paper's contribution lies in its formal framework for measuring traceability. They achieve this by:

  • Transaction Graph Modeling: Representing cryptocurrency transaction networks as weighted, directed graphs where nodes are addresses and edges represent transactions with associated values.
  • Absorbing Markov Chains: Transforming these transaction graphs into absorbing Markov chains. This involves reversing edge directions and introducing auxiliary "absorber" nodes for source entities (like coinbase transactions).
  • Shannon Entropy: Defining the untraceability score for a given sink node (an address that receives funds) as the Shannon entropy of the probability distribution of its potential origins among the source nodes. This entropy quantifies the uncertainty an observer has about the true source of funds.
  • Computational Efficiency: Developing an efficient method to compute this entropy, particularly by approximating the fundamental matrix of the Markov chain, making it feasible for large-scale real-world blockchain data.

Datasets

The authors evaluated their proposed traceability metric on the public ledgers of several major cryptocurrencies, including:

  • Bitcoin
  • Ethereum
  • Zcash
  • DAI (an ERC-20 token)
  • USD Coin (USDC) (an ERC-20 token)

The evaluation was performed on transaction data from a specific one-week interval (February 1st to 8th, 2021) to create comparable transaction graphs.

Key Insights and Ideas

  • Quantitative Traceability is Possible: The paper demonstrates that a formal, quantitative measure of cryptocurrency traceability is achievable and practical, moving beyond anecdotal evidence or qualitative descriptions.
  • Bitcoin vs. Ethereum Mixing: In the studied one-week period, the Bitcoin blockchain offered comparable, but quantifiably better, mixing (higher untraceability) than the Ethereum blockchain.
  • Zcash's Shielded Pool Impact: Zcash's shielded pool significantly enhances untraceability, even for transactions that occur outside the analyzed time window, highlighting the effectiveness of its privacy-preserving mechanisms.
  • Account-Based vs. UTXO-Based: Account-based systems like Ethereum tend to have shorter random walks (faster absorption) compared to UTXO-based systems like Bitcoin, which can influence their untraceability characteristics.
  • Temporal vs. Stationary Graphs: The consideration of transaction timing (temporal graphs) can significantly alter the perceived untraceability by blocking older outgoing transactions from being traced to newer incoming ones.

Key Results

  • Bitcoin: Mean untraceability of 3.96 bits, median 4.07 bits, with an average of 25.23 steps for absorption.
  • Ethereum: Mean untraceability of 3.45 bits, median 3.94 bits, with a notably low average of 7.27 steps for absorption.
  • Zcash: Exhibited the highest untraceability variance (15.36) and a high average untraceability of 2.63 bits (for transparent UTXOs), with an average of 52.66 steps for absorption. When considering shielded transactions, untraceability increased significantly.
  • DAI and USDC: Showed a trend where longer expected absorption times correlated with higher untraceability, though this effect saturated and eventually decreased untraceability.

Limitations and Future Work

  • One-Week Snapshot: The evaluation used a one-week interval, which might not fully capture long-term network dynamics or the full context of all transactions. Future work could analyze longer time periods.
  • Exogenous Knowledge: While the framework can incorporate external knowledge (e.g., from social media or blacklists) to measure subjective traceability or anonymity, this was not fully explored in the current evaluation. Future work could focus on this aspect, potentially by modifying the transition matrix.
  • Specific Privacy Technologies: The paper suggests extending the analysis to other privacy-enhancing technologies like ring signatures, stealth addresses, and confidential transactions to compare their quantitative benefits.
  • Computational Scalability: While the method is efficient, further optimization for extremely large transaction graphs is an ongoing area of research.

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 M. Kelen and István András Seres},
  title = {{Towards Measuring the Traceability of Cryptocurrencies}},
  booktitle = {ICBC},
  year = {2025},
  doi = {10.1109/icbc64466.2025.11114667},
}
Figure