What clustering is and why it matters

Almost every on-chain statement about "who" rests on a clustering step. When an analyst writes that an exchange received 40 BTC, that a ransomware group controls 300 addresses, or that a wallet has "exposure" to a sanctioned service, the claim depends on a method that grouped addresses together, and on that method's errors. Understanding what clustering does, and how its mistakes spread, is the foundation for every other lesson in this module.

Addresses, clusters and entities

Analysts work on three levels that are easy to confuse:

Clustering is the blockchain version of entity resolution, the general data problem of deciding which records refer to the same underlying thing. Customer databases do it with names and postal addresses; blockchain analysts do it with spending patterns. The output is not a fact read from the chain but an inference built on assumptions about how wallets and people behave.

Note the word controlled. A heuristic can at best show that the same keys, or the same software acting for one operator, moved the funds. A custodial exchange controls the keys for millions of customers, so a cluster labeled "Exchange X" represents the service, not any of its customers. Control is not the same as ownership, and neither is the same as identity.

How clusters are built

Clustering has two stages. First, heuristics produce linking evidence: pairs of addresses that, according to some rule, share a controller. The common-input rule links all inputs of a transaction (see the lesson The common-input ownership heuristic); change detection links a sender to its change output (see Change detection heuristics); account chains use behavioral links such as shared deposit addresses (see Account-model heuristics). Second, the analyst takes the transitive closure of those links: if A is linked to B and B to C, then A, B and C form one cluster, even though no single piece of evidence connects A and C. In graph terms, clusters are the connected components of the evidence graph.

A small example. Transaction 4f3a…c21e spends coins from addresses a1 and a2, and transaction 9b7d…e014, a week later, spends from a2 and a3. The common-input rule yields two links, a1–a2 and a2–a3, and the closure yields one cluster {a1, a2, a3}. The link between a1 and a3 was never observed; it is inherited. If either transaction was in fact a collaborative transaction with two owners, the whole cluster is wrong, not only one link.

A good practice is to store the evidence, not only the finished clusters:

-- One row per piece of linking evidence, not one row per cluster
CREATE TABLE cluster_evidence (
  addr_a        VARCHAR NOT NULL,
  addr_b        VARCHAR NOT NULL,
  heuristic     VARCHAR NOT NULL,  -- e.g. 'common_input', 'change_v3'
  evidence_tx   VARCHAR NOT NULL,  -- txid or transaction hash
  block_height  BIGINT  NOT NULL,
  confidence    DECIMAL(3,2)       -- analyst-assigned, 0.00 to 1.00
);

-- Rebuild clusters from the strongest evidence only
SELECT addr_a, addr_b
FROM cluster_evidence
WHERE heuristic = 'common_input'
  AND confidence >= 0.90;

The table records which rule created each link, which transaction justified it, at what block height, and with what confidence. Because the finished clusters are derived from this table, the analyst can rebuild them with a stricter or looser heuristic set, remove one bad transaction and see what falls apart, or prove to a reviewer why two addresses ended up together. The final step, computing connected components, is awkward in plain SQL (recursive CTEs work but scale badly); most teams export the selected edges to a graph library or a union-find routine.

Clusters are not entities

The mapping between clusters and real-world entities fails in both directions.

One entity, many clusters. An exchange may keep cold wallets that are never spent together with its hot wallets, so no heuristic links them. A person may use three unrelated wallet applications. On account-based chains, where there is no multi-input spending, a single operator often appears as dozens of unconnected addresses. These are under-merges.

One cluster, many entities. A CoinJoin transaction combines inputs from several unrelated users; treating them as one owner merges their wallets. A custodial service pools the funds of many customers. Some early web wallets let users import private keys, which caused the common-input rule to link addresses that belonged to different people: Harrigan and Fretter ("The Unreasonable Effectiveness of Address Clustering", 2016) excluded the largest Bitcoin cluster, over 10 million addresses originally belonging to Mt. Gox, for exactly this reason. These are over-merges.

Clusters also change over time. New transactions keep adding evidence, so a cluster computed at block 800,000 may merge with another by block 850,000. Every cluster is a snapshot and should carry the block height at which it was computed.

False positives and false negatives

Two kinds of error matter:

• A false positive link joins addresses that are not controlled by the same party.
• A false negative is a link that exists in reality but that the method missed.

Their consequences differ, and so does their cost for different users:

There is no universally "best" heuristic set. A compliance team that blocks transactions on the basis of cluster labels should favor precision; an investigator generating leads can accept more false positives, provided every lead is verified before it reaches a report.

How errors propagate

Clustering errors are not proportional to the number of bad links. Because clusters are transitive closures, a single false link between a cluster of 5,000 addresses and one of 40,000 addresses produces a cluster of 45,000 addresses, and every one of them now shares whatever label either side carried.

Errors also compound with cluster size. If each link independently has a probability p of being wrong, a cluster assembled from n links is error-free with probability (1 − p)^n. With p = 0.001 and n = 1,000 links, that probability is 0.999^1,000 ≈ 0.37: a 63% chance that the cluster contains at least one false merge. Large clusters are therefore more likely to be contaminated, which is exactly where analysts tend to place the most trust.

The research literature shows how quickly this happens in practice. Meiklejohn et al. (2013, "A Fistful of Bitcoins") reported that a naive version of their change heuristic produced a supercluster of 1.6 million public keys containing Mt. Gox, Instawallet, BitPay and Silk Road, unrelated services that clearly did not share an owner. Only after adding conservative refinements did the clusters become usable. The lesson Evaluating cluster quality returns to these superclusters.

Errors then move downstream:

1. A heuristic creates a false link.
2. Two clusters merge.
3. A label on one side spreads to the whole merged cluster.
4. Flow statistics and risk scores computed from cluster labels change.
5. A report states a conclusion that the underlying evidence does not support.

Each step looks reasonable on its own, which is why the error is hard to see at the end.

Practical habits

• Keep the evidence. Store links with their heuristic, transaction and block height, as in the table above.
• Version the method. Name and date the heuristic set and thresholds used for every cluster you cite.
• Watch for jumps. Review any cluster that grows sharply between snapshots, and any merge between two clusters that carry different labels.
• Use precise language. Write "addresses clustered by the common-input heuristic, labeled as Service X on the basis of a test deposit" rather than "Service X's wallet". The lesson Confidence, uncertainty and language covers how to express this in a report.
• Test sensitivity. Rerun key findings without the weakest heuristic and report whether they still hold.

Exam focus: the difference between an address, a cluster and an entity; clustering as entity resolution and as the transitive closure (connected components) of linking evidence; control versus ownership, especially for custodial services; under-merging and over-merging and their typical causes; the definitions and different costs of false positives and false negatives; why one false link can merge whole clusters and spread labels; the (1 − p)^n reasoning for why large clusters are more likely to be contaminated; storing evidence with heuristic, transaction and block height so clusters can be rebuilt and audited.