Evaluating cluster quality

A cluster is a hypothesis about control, and hypotheses need testing. Analysts who cannot say how good their clusters are cannot say how much to trust any finding built on them. This lesson covers how cluster quality is measured, what the research literature has found about heuristic error rates, how to detect cluster collapse, and how to show that a conclusion survives reasonable changes in method.

Ground truth and its biases

Evaluating clusters requires ground truth: addresses whose controller is known independently of the heuristics being tested. Real ground truth is scarce, and every source is biased:

Nick (2015, a master's thesis on de-anonymization in Bitcoin) is a rare leak-based example: a privacy flaw in the Bloom filters of lightweight wallets exposed real wallets' address sets, and the common-input heuristic found more than 69% of the addresses in them. Möser and Narayanan (2022, "Resurrecting Address Clustering in Bitcoin") used behavior-revealed labels, 35.26 million transactions whose change was later exposed by the common-input rule. Neither is a random sample of all users, and both are tied to their period. Treat every published error rate as "measured on this ground truth, at this time".

Precision and recall for clusters

Precision asks how much of what the method put together really belongs together; recall asks how much of what belongs together the method found. For clusters there are two common ways to count.

A worked example. Entity E controls 10 addresses and entity F controls 4. The method produced cluster C containing 8 of E's addresses and all 4 of F's (a false merge), while E's other 2 addresses sit in a separate cluster.

• Address level (C judged as E's cluster): precision = 8 ÷ 12 = 0.67; recall = 8 ÷ 10 = 0.80.
• Pairwise: C contains 12 × 11 ÷ 2 = 66 address pairs. Correct pairs are E–E (8 × 7 ÷ 2 = 28) plus F–F (4 × 3 ÷ 2 = 6), so 34. Pairwise precision = 34 ÷ 66 = 0.52. True pairs in reality are 45 for E plus 6 for F, so 51; pairwise recall = 34 ÷ 51 = 0.67.

Pairwise counting punishes false merges harder, because a merge creates many wrong pairs at once, which matches how merges damage analysis. Always state which counting method a figure uses.

-- Address-level precision and recall of each cluster vs ground truth
WITH overlap AS (
  SELECT c.cluster_id, g.entity_id, COUNT(*) AS shared
  FROM clusters c
  JOIN ground_truth g ON g.address = c.address
  GROUP BY c.cluster_id, g.entity_id
),
ranked AS (
  SELECT o.*, SUM(shared) OVER (PARTITION BY cluster_id) AS labeled_in_cluster,
         ROW_NUMBER() OVER (PARTITION BY cluster_id ORDER BY shared DESC) AS rk
  FROM overlap o
),
entity_size AS (SELECT entity_id, COUNT(*) AS n FROM ground_truth GROUP BY entity_id)
SELECT r.cluster_id, r.entity_id,
       r.shared * 1.0 / r.labeled_in_cluster AS precision,
       r.shared * 1.0 / e.n                  AS recall
FROM ranked r
JOIN entity_size e ON e.entity_id = r.entity_id
WHERE r.rk = 1;

The query counts, for each cluster, how many of its ground-truth addresses belong to each entity, picks the dominant entity, and divides the overlap by the cluster's labeled addresses (precision) and by the entity's known size (recall). Addresses without ground truth are ignored, which is the honest choice: they are unknown, not correct. Multiplying by 1.0 avoids integer division in engines that truncate.

Checks that need no ground truth

Most real investigations have no ground truth for the entities involved. Internal consistency checks still reveal problems:

• Fingerprint consistency. Addresses controlled by one wallet tend to share a script type, transaction version, locktime habit and fee style. A cluster whose spending transactions show many unrelated fingerprints probably merges several wallets. Kappos et al. (2022, "How to Peel a Million: Validating and Expanding Bitcoin Clusters") used cluster-wide features of this kind to separate clusters contaminated by CoinJoins from clean ones.
• Temporal coherence. A cluster whose addresses were active in widely separated periods, with nothing linking the periods except one transaction, deserves a look at that transaction.
• Behavioral coherence. A cluster that behaves like an exchange in one part (thousands of deposits and sweeps) and like a single user in another (a handful of manual payments) may be two entities joined by one link.
• Size distribution. A sudden jump in the size of the largest clusters after a method change points to new false links rather than new knowledge.

None of these proves a cluster right, but each can show that it is probably wrong.

What research shows about error rates

Four conclusions follow. Error rates depend heavily on how they are measured: the same change heuristic scores 0.17% against its authors' own falsification test and 51.64% against independent verified clusters nine years later. Heuristics age as wallet software and user habits change. Combining several signals beats any single rule. And account-model heuristics remain largely unvalidated.

Cluster collapse

Cluster collapse occurs when false links merge unrelated entities into a supercluster. The literature offers several examples:

• Meiklejohn et al.'s naive change heuristic produced a 1.6-million-key cluster containing Mt. Gox, Instawallet, BitPay and Silk Road.
• Möser and Narayanan found that naive merging on their change classifier produced a cluster of 223.9 million addresses that absorbed 113 of 273 independently tagged clusters. Constraints based on predicted spending behavior blocked 413,608 merges; the largest remaining cluster had 40.5 million addresses, and seven pairs of tagged clusters still merged.
• Harrigan and Fretter (2016, "The Unreasonable Effectiveness of Address Clustering") excluded the Mt. Gox cluster entirely because a key-import feature made the common-input rule unreliable there.

Practical warning signs:

1. Label conflicts: two different exchanges, or an exchange and a mixer, ending up in one cluster.
2. Large-to-large merges: Harrigan and Fretter observed that large clusters rarely merge naturally, so such merges deserve review.
3. Sudden growth: a cluster that gains a large share of its size in one snapshot.
4. Single points of failure: one transaction responsible for joining two big components; find it in the evidence table and examine it.

Sensitivity analysis

Sensitivity analysis reruns a finding under different reasonable methods and reports how it changes. A typical ladder:

Here, the first two rows agree closely while the third nearly triples the figure. A careful report would state "at least 120 BTC, and about 141 BTC including high-confidence change links" and would treat 410 BTC as unreliable, probably inflated by a merge. Research shows the same effect at scale: Möser and Narayanan found that adding their change clustering raised estimated flows from darknet markets to exchanges by 13.8% and lowered an estimate of coin velocity by about 11.9%. Method choices move headline numbers.

Documenting assumptions

Every report that relies on clusters should record:

• the heuristic set, its version and thresholds (for example, the CoinJoin filter and change score cutoff);
• the data snapshot: chain, block height and node or dataset version;
• the ground truth used to evaluate the clusters, its size and its known biases;
• measured or cited error rates, with their source and date;
• known collapses excluded and merges reviewed;
• the sensitivity results for each key finding;
• label sources and grades (see the lesson Attribution and labeling).

This record lets a reviewer reproduce the clusters, challenge a specific link, and see which conclusions would survive if a heuristic turned out to be wrong. The lesson Writing the analytical report shows where it belongs in the final document.

Exam focus: ground-truth sources and their biases, including circularity in vendor labels; address-level versus pairwise precision and recall, and computing both from a small example; why pairwise metrics punish false merges; what the research figures show, above all 0.17% versus 51.64% for the same change heuristic and why even a 0.06% false-positive rate can collapse clusters at scale; cluster collapse and its warning signs; sensitivity analysis and reporting a robust lower bound; documenting heuristics, thresholds, snapshot, ground truth and error rates.