Clustering and the common-input ownership heuristic

Almost every on-chain statement about "who" rests on a clustering step. When a report says that an exchange received 40 BTC or that a ransomware group controls 300 addresses, the claim depends on a method that grouped addresses together, and on that method's errors. On UTXO chains, most links in any cluster come from one rule, the common-input ownership heuristic. It is usually right, and when it is wrong it merges entire wallets. This lesson covers what clustering is, why the rule works, which transactions break it, and how to record clusters so that a reviewer can take them apart link by link.

Addresses, clusters and entities

Three levels 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. The output is not a fact read from the chain but an inference built on assumptions about how wallets and people behave. That a transaction spent three inputs is a recorded fact; that one party controlled all three is a heuristic conclusion, and the report must keep the two apart.

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 ownership, and neither is identity (Lesson 4.5).

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; change detection links a sender to its change output (Lesson 4.2); account chains use behavioral links such as shared deposit addresses (Lesson 4.3). 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.

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

The common-input ownership heuristic

The logic

To spend a UTXO, a transaction must provide a valid unlocking script or witness for it, in practice a signature from the controlling key, so three inputs need signatures for three coins. In ordinary use a wallet selects coins from its own balance and signs them all. So if several addresses appear as inputs to one transaction, the most likely explanation is that one wallet, and therefore one controller, holds all their keys.

The idea is as old as Bitcoin: the privacy section of the 2008 white paper warns that multi-input transactions "necessarily reveal that their inputs were owned by the same owner". Reid and Harrigan (2011) used it to build a user network, and Meiklejohn et al. (2013, "A Fistful of Bitcoins") stated it as their Heuristic 1: if two or more addresses are inputs to the same transaction, they are controlled by the same user. It is also called the common-input ownership heuristic (CIOH) or the multi-input heuristic.

A worked example

A decoded transaction, simplified to the fields that matter for clustering (identifiers truncated):

{
  "txid": "7c1e…40ab",
  "vin": [
    {"prevout": "a91f…03:1", "address": "bc1q…k3f7", "value_btc": 0.0400},
    {"prevout": "e2c8…7d:0", "address": "bc1q…m9a2", "value_btc": 0.0250},
    {"prevout": "51b0…e9:4", "address": "bc1q…x0d1", "value_btc": 0.0180}
  ],
  "vout": [
    {"n": 0, "address": "bc1q…p2w8", "value_btc": 0.0700},
    {"n": 1, "address": "bc1q…r4t6", "value_btc": 0.0128}
  ]
}

The three inputs total 0.0830 BTC and the outputs 0.0828 BTC, so the fee is 0.0002 BTC (20,000 satoshis). The common-input rule links bc1q…k3f7, bc1q…m9a2 and bc1q…x0d1. It says nothing about the outputs: whether bc1q…r4t6 is change belonging to the same wallet is a separate and much weaker inference (Lesson 4.2).

If bc1q…m9a2 was already in a cluster of 2,000 addresses and bc1q…x0d1 in a cluster of 300, this one transaction merges them into a cluster of 2,301 addresses. That is the leverage of the rule and its danger.

The rule is at its strongest with services. Custodial exchanges and payment processors periodically consolidate many small deposits into one output, a fan-in transaction that may spend hundreds of deposit addresses at once. Each sweep links all of those addresses to the service's wallet, which is why service clusters grow to millions of addresses and why one verified deposit is often enough to label them (Lesson 4.5). A user who merges a dozen old coins to save future fees reveals the same way that one wallet held them all. Both cases are correct as long as nobody else contributed an input.

How well it works

Meiklejohn et al. applied the rule to the full chain in 2013 and reduced 12,056,684 public keys to about 5.58 million clusters. Nick (2015, a master's thesis) obtained rare ground truth from a privacy leak in the Bloom filters of lightweight wallets, which exposed real wallets' address sets; the common-input rule identified more than 69% of the addresses in those wallets. Note what that figure measures: recall (how much of each wallet was found), not precision (how many links were correct). The rule is generally regarded as high-precision for ordinary transactions, but that is an assumption about wallet behavior, which the transactions below violate (Lesson 4.4 covers measuring cluster quality).

Where the assumption fails

CoinJoin. Several users agree on one transaction; each contributes inputs and signs only their own, and the outputs typically include several of identical value so that no one can tell which output belongs to whom. Applying the common-input rule merges the wallets of every participant, which is precisely the false link CoinJoin is designed to induce (Lesson 6.2).

PayJoin. In a PayJoin (BIP 78), the receiver of a payment adds one of its own inputs to the sender's transaction. The result looks like an ordinary two-input payment, so the rule links the sender's and the receiver's coins, and the apparent payment amount is distorted too. A well-built PayJoin cannot be reliably distinguished from a normal transaction, so its existence puts a ceiling on the strength of any single link. Its adoption has been low, which limits the overall damage but does not rule it out in a specific case.

Other multi-party transactions. Dual-funded Lightning channel openings, some swap and batching protocols, and transactions signed with SIGHASH_ANYONECANPAY, which lets others add inputs after the first signature (used, for example, in crowdfunding-style contracts), all have inputs from several parties.

Shared control. A multisig address held jointly by several people is one "owner" in the script sense; the correct entity is the joint arrangement, not any one signer.

Custody and key import. A custodial service spends customer deposits together, so its cluster is correct for the service but says nothing about the customers. Wallets that let users import or sweep private keys received from others (paper wallets, gift cards) can link coins that had different owners. 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.

Clusters are not entities

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

• One entity, many clusters (under-merge). An exchange's cold wallets may never be spent together with its hot wallets; a person may use three unrelated wallet applications; on account-based chains, with no multi-input spending, one operator often appears as dozens of unconnected addresses.
• One cluster, many entities (over-merge). CoinJoins, custodial pooling and key import, as above, join wallets that belong to different people.

Clusters also change over time: 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, false negatives and how errors spread

A false positive link joins addresses that are not controlled by the same party; a false negative is a real link the method missed. Their costs fall on different users:

No heuristic set is best for everyone: a compliance team that blocks transactions on cluster labels should favor precision; an investigator generating leads can accept more false positives, provided every lead is verified before it reaches a report.

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 produces a cluster of 45,000, and every address now shares whatever label either side carried. Errors also compound with 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 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. Meiklejohn et al. found 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 (Lesson 4.4 covers such superclusters). Downstream, the merged label changes flow statistics and risk scores, and a report ends up stating a conclusion the evidence does not support, through steps that each looked reasonable.

Safeguards and recording the evidence

Screen and watch before linking

1. Screen out likely CoinJoins. The simplest test looks for several outputs of exactly the same value:

-- Flag candidate CoinJoins so their inputs are not linked
WITH same_value AS (
  SELECT transaction_hash, value, COUNT(*) AS n_equal
  FROM outputs
  GROUP BY transaction_hash, value
),
shape AS (
  SELECT t.hash AS transaction_hash, t.input_count,
         MAX(s.n_equal) AS max_equal_outputs
  FROM transactions t
  JOIN same_value s ON s.transaction_hash = t.hash
  GROUP BY t.hash, t.input_count
)
SELECT transaction_hash
FROM shape
WHERE input_count >= 2
  AND max_equal_outputs >= 3;  -- tune this threshold and document it

The query counts, per transaction, how many outputs share each value, keeps the largest such group, and flags multi-input transactions where at least three outputs are identical. The threshold is a judgment call. It also catches some exchange batch payouts with equal amounts; excluding those only costs a few links (a false negative), the safer error. It misses CoinJoin designs that avoid equal outputs, so it is a filter, not a detector; research clustering such as Goldfeder et al. (2018) adds a CoinJoin exclusion for the same reason.

1. Flag unusual input mixes. Inputs of different script types (for example, a legacy P2PKH input next to a P2TR input) are uncommon from single-wallet software and deserve a second look.
2. Watch merges. Review any link that would merge two large clusters, or two clusters that carry different labels. Harrigan and Fretter observed that large clusters rarely merge naturally, so such a merge is a warning sign. Review, too, any cluster that grows sharply between snapshots.

Keep the evidence, not only the clusters

Store one row per piece of linking evidence:

-- 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,
  strength      VARCHAR            -- 'high', 'moderate' or 'low' (see the table below)
);

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

Because clusters are derived from this table, the analyst can rebuild them with a stricter or looser heuristic set, remove a transaction later found to be a CoinJoin or PayJoin and see what falls apart, or show a reviewer why two addresses ended up together. 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. Generating the input pairs at scale, with the same CoinJoin exclusion, is covered in Lesson 2.9 (column names here follow its UTXO schema).

Strength and reporting

On the course's A–D scale (Lesson 3.2) every common-input link is grade C, a single heuristic, whatever its row here; the table ranks the strength of links within that grade and decides which may carry labels (Lesson 4.5). The course keeps the word "confidence" for the basis of a reported judgment (Lesson 9.2), so heuristic links are rated by strength. Name and date the heuristic set, exclusions, thresholds and snapshot block height behind every cluster you cite. Write "addresses clustered by the common-input heuristic, CoinJoin filter on, labeled as Service X on the basis of a test deposit" rather than "Service X's wallet" (Lesson 9.2 covers report language). Finally, 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, and control versus ownership for custodial services; clustering as entity resolution and as the transitive closure (connected components) of linking evidence; why co-spent inputs imply a shared controller and the rule's origin (white paper, Meiklejohn et al.'s Heuristic 1); recall versus precision in the Bloom filter evidence (more than 69% of wallet addresses found); the exceptions (CoinJoin, PayJoin per BIP 78, dual-funded channels, SIGHASH_ANYONECANPAY, multisig, custody and key import); under- and over-merging; the different costs of false positives and false negatives; why one false link merges whole clusters and spreads labels, and the (1 − p)^n reasoning; screening equal-value outputs with a documented threshold; storing evidence with heuristic, transaction and block height so clusters can be rebuilt.