Source-linked AI summary
The Unreasonable Effectiveness of Address Clustering
Martin Harrigan, Christoph Fretter
TL;DR
Bitcoin’s public transaction data can disclose information about transactors, motivating methods that map entities to addresses. This paper analyzes why the multi-input heuristic is effective, identifying reuse, merging, central super-clusters, and incremental cluster growth as primary reasons. The findings inform blockchain analysis while showing that some services avoid super-clusters and that further work is needed on cluster structure.
Problem
Bitcoin’s broadcast transactions expose contents and relationships that interested parties can analyze, while address clustering seeks to map addresses to likely common entities.
Method
The paper analyzes Bitcoin’s blockchain using the multi-input heuristic, measuring address reuse, cluster merging, super-cluster centrality, and incremental cluster growth.
Results
The paper identifies high address reuse and avoidable merging, highly central super-clusters, and incremental cluster growth as primary reasons for address clustering’s effectiveness.
Takeaways & Limitations
The findings can inform blockchain analysts by identifying super-clusters as targets for re-identification attacks and flagging clusters that may contain addresses from multiple entities.
Takeaways & Limitations
Some major services avoid super-clusters, so the multi-input heuristic alone may be insufficient to identify all of their on-chain activity.
Abstract
from arXiv · showhide
Address clustering tries to construct the one-to-many mapping from entities to addresses in the Bitcoin system. Simple heuristics based on the micro-structure of transactions have proved very effective in practice. In this paper we describe the primary reasons behind this effectiveness: address reuse, avoidable merging, super-clusters with high centrality, and the incremental growth of address clusters. We quantify their impact during Bitcoin's first seven years of existence.
1 Introduction
Bitcoin transactions can reveal information about transactors, making address clustering central to analyses that connect blockchain activity to entities. This paper examines why a simple transaction heuristic is effective and illustrates its analytical reach through major address-cluster flows.
- Bitcoin’s public transaction contents, relationships, and broadcasts can unintentionally disclose information about transactors.Interested parties systematically analyze this information for market research, competitor analysis, compliance, and law enforcement.
- Address clustering partitions Bitcoin addresses into maximal subsets likely controlled by the same entity.Combined with address tagging and graph analysis, it supports micro- and macro-level Bitcoin activity analysis.
- A single multi-input heuristic identified more than 69% of addresses in wallets stored by lightweight clients.
- Figure 1 maps major bitcoin flows among address clusters, identifying darknet markets, gambling services, exchanges, and mining pools while leaving some gray clusters unidentified.The summary relies on address clustering and publicly available information.
- The paper quantifies address reuse, cluster merging, super-cluster centrality, and incremental cluster growth as reasons for the multi-input heuristic’s effectiveness.The analysis focuses on Bitcoin’s blockchain and studies cluster counts, sizes, centrality, and formation.
2 Related Work
Related work established address clusters as foundations for blockchain analysis, evaluated extensions and performance, and examined their privacy, network, mixing, anti-money-laundering, and forensic implications.
- The multi-input heuristic can be augmented with change heuristics, temporal behavior, and transaction fingerprinting, although this paper uses the multi-input heuristic alone.The authors state that their analyses can be extended to combinations of heuristics.
- One evaluation found that the multi-input heuristic identified more than 69% of addresses in vulnerable lightweight-client wallets.
- Prior studies use address clusters to analyze anonymity, cluster structure, network centrality, and activity involving major services.Related analyses identify scale-free cluster sizes and major darknet markets, gambling services, exchanges, and mining pools as network hubs.
- CoinJoin and related mixing protocols are important counterexamples because CoinJoin can cause false positives for the multi-input heuristic.The related work distinguishes centralized protocols such as CoinJoin, Mixcoin, and Blindcoin from decentralized protocols such as CoinSwap, CoinShuffle, and CoinParty.
- Blockchain analyses involving address clustering have also been studied for anti-money-laundering and digital-forensics applications.
3 Counting Address Clusters
Address and cluster counts reveal substantial address reuse and cluster merging: new addresses grew with transactions, while multi-address clusters grew more slowly, and both normalized ratios remained stable with new addresses far exceeding newly merged clusters.
- The monthly number of new addresses grew in line with transactions, whereas address clusters containing at least two addresses grew much more slowly.Figure 2 compares monthly transaction, new-address, and multi-address-cluster counts.
- An order-of-magnitude gap separated new addresses per transaction from newly merged address clusters per transaction, with both ratios relatively stable over the past two years.Figure 3 uses ordinal transaction numbers to adjust for Bitcoin’s rapid transaction growth.
- The gap between the maximum possible new addresses per transaction and observed new addresses measures address reuse.Transaction-output counts provide the upper bound, adjusted for OP_RETURN, multisignature, and known Pay-to-Script-Hash scripts.
- The gap between non-trivial transactions and newly merged clusters measures cluster merging, although merge avoidance can narrow it.Non-trivial transactions spend at least two outputs assigned to different addresses.
- Address reuse and cluster merging allow the multi-input heuristic to link addresses to a common owner, contributing to its effectiveness.
4 Measuring Cluster Sizes
Address clusters exhibit a heavy-tailed structure, with large super-clusters covering a substantial share of observed addresses and transaction activity. Their centrality makes clustering especially useful for tracing service activity, although some services avoid forming such clusters.
- Cluster sizes: 1,955 clusters contain between 1,000 and 10 million addresses, covering 22% of addresses represented in Figure 4 and 16% of all observed addresses.Figure 4 uses logarithmic scales on both axes; the single cluster exceeding 10 million addresses is excluded.
- Cluster centrality: Super-clusters account for 23% of transaction outputs and 18% of transaction inputs in the analyzed 107 million-transaction dataset.They produced or redeemed 72 million outputs and 51 million inputs, respectively.
- Cluster centrality: Linking identities to super-clusters can identify at least one transactor in many transactions and expose service-user deposits and withdrawals.The paper connects this centrality to wallet explorers and re-identification attacks.
- Limits: Coinbase avoids a single super-cluster spanning its user activity, so the multi-input heuristic alone cannot identify all of its on-chain activity.This does not mean Coinbase creates no large clusters.
5 Formation and Structure
Cluster growth is usually incremental: small clusters attach to large ones, while mergers of two large clusters are rare. This supports stable and real-time analyses, while unusual large mergers can flag false positives or motivate splitting heuristics.
- Merging behavior: Cluster-size increases are concentrated around one, and large mergers are rare because the heuristic usually joins one large cluster with smaller clusters.Figure 5 reports quantiles over every 250,000 transactions; for the past 30 million transactions, the 99th percentiles are also one.
- Cluster structure: Typical cluster graphs form when singleton address vertices connect to a large cluster, whereas two large disconnected components rarely merge into one component.Figure 6 represents addresses as white vertices, transactions as gray vertices, and spending relationships as edges.
- Merging behavior: Rare mergers of two large clusters can signal a multi-input false positive and can be used to develop heuristics for splitting clusters.The paper illustrates this possibility using unusually large increases during Mt. Gox’s lifetime.
- Implications: Incremental growth keeps clustering relatively stable over time and supports real-time analysis because small clusters merge with identifiable large clusters early.A merger of two large clusters may drastically change an earlier analysis, but such events are rare.
6 Conclusion and Future Work
The paper identifies four primary reasons for address clustering’s effectiveness and shows how the results can support both blockchain analysis and measurement of privacy-enhancing techniques. It also leaves the internal structure of address clusters as future work.
- Address reuse, avoidable merging, high-centrality super-clusters, and incremental cluster growth are identified as the primary reasons for clustering effectiveness.
- The findings can help blockchain analysts target super-clusters for re-identification attacks and flag clusters that may combine addresses from multiple entities.
- The gap between non-trivial transactions and clusters created or merged per transaction can indirectly measure the adoption and impact of privacy-enhancing techniques.
- Future work will examine address-cluster internal structure through representations such as the bipartite graph in Fig. 6.