Change detection heuristics

Most Bitcoin payments return part of the spent value to the sender as change. Identifying the change output lets an analyst follow the sender's remaining funds, reconstruct peel chains and add the change address to the sender's cluster. Unlike the common-input rule, though, change detection is always a probabilistic guess, and the research record shows that badly chosen change heuristics are the main cause of runaway clusters.

Why change exists

A UTXO must be spent in full. A wallet holding a 0.09 BTC coin that wants to pay 0.05 BTC spends the whole coin, sends 0.05 BTC to the recipient and sends the remainder, minus the fee, to an address it controls. Here is such a transaction, decoded and simplified:

{
  "txid": "b52d…0e7a", "version": 2, "locktime": 861203,
  "vin": [
    {"address": "bc1q…h8e2", "type": "p2wpkh", "value_btc": 0.09000000,
     "sequence": "0xfffffffd"}
  ],
  "vout": [
    {"n": 0, "address": "1Kx3…9vQe", "type": "p2pkh", "value_btc": 0.05000000},
    {"n": 1, "address": "bc1q…7k3f", "type": "p2wpkh", "value_btc": 0.03985860}
  ]
}

The fee is 0.09000000 − 0.08985860 = 0.00014140 BTC (14,140 satoshis). Nothing in the data says which output is the payment. The analyst must infer it, and several independent clues point the same way here.

The classic heuristics

The fresh-address idea comes from Androulaki et al. (2013, "Evaluating User Privacy in Bitcoin"), who called change outputs "shadow addresses", and from Meiklejohn et al. (2013, "A Fistful of Bitcoins"), whose Heuristic 2 labels an output as change if it is the only output address appearing for the first time, the transaction is not a coinbase, and no output sends back to an input address (no self-change). Later work added conditions: Goldfeder et al. (2018, a study of privacy risks in web payments) excluded CoinJoins, and Ermilov et al. (2017, "Automatic Bitcoin Address Clustering") required exactly two outputs and a value significant to at least the fourth decimal place.

In the example: output 1 is a fresh address, it matches the input's P2WPKH type, and its amount is not round, while output 0 is a round 0.05 BTC to a legacy address that has received funds before. All signals agree that output 1 is change.

Later transactions can confirm or refute the guess. If bc1q…7k3f is eventually spent together with other coins already in the sender's cluster, the common-input rule now links it independently, and the change label becomes strong evidence rather than inference. If instead it is spent together with coins from a known exchange cluster, output 1 was probably the payment after all, and the label must be reversed along with every link built on it. This delayed confirmation is exactly how Möser and Narayanan (2022) built their ground truth, described below, and it is why change labels should be re-evaluated as the chain grows rather than fixed at the moment they were assigned.

Wallet fingerprints

Wallet software leaves consistent traces in fields that consensus does not fix:

• Version. Transactions using relative timelocks (BIP 68) must set version 2; many wallets still use version 1. In data analyzed by Möser and Narayanan (2022), about 80% of transactions used version 1, so version 2 alone narrows the field only partly.
• Locktime. Some clients, notably Bitcoin Core, set nLockTime to the current block height by default to discourage fee sniping. A locktime close to the confirmation height is a fingerprint.
• Replace-by-fee signaling. A transaction signals BIP 125 replaceability when an input has nSequence below 0xfffffffe, as in the example (0xfffffffd).
• Ordering. BIP 69 defines optional lexicographic sorting of inputs and outputs; wallets that follow it produce a recognizable pattern.
• Script and fee behavior. Address types, fee-rate rounding and multisig layouts also differ between wallets.

The fingerprint heuristic compares the transaction that spends each candidate output with the original. If the original had version 2, a locktime set to the block height and RBF signaling, and output 1 is later spent by a transaction with the same three traits while output 0 is spent by a version 1 transaction with locktime 0, output 1 is probably change. Fingerprints are dated evidence: defaults change between releases, so record the period your fingerprint rules describe.

What the research says about accuracy

The same heuristic can look excellent or poor depending on when and how it is measured.

• Meiklejohn et al. (2013) treated an address later reused as a sign of a false positive. Their naive Heuristic 2 gave 13% false positives and a 1.6-million-key supercluster; after refinements (waiting a week before labeling, exempting dice-game transactions, excluding some address patterns, manual review) they estimated 0.17%.
• Kappos et al. (2022, "How to Peel a Million") tested the same family of heuristics against manually verified clusters. They measured a false discovery rate of 51.64% for the Meiklejohn heuristic, 64.19% for the Androulaki heuristic and 12.7% for the stricter Ermilov heuristic, attributing the gap to how much Bitcoin usage has changed since 2013. Their own method, which uses the cluster's past change behavior and spending patterns, reached 0.62% and 0.02% in two variants.
• Möser and Narayanan (2022, "Resurrecting Address Clustering in Bitcoin") built ground truth from change later revealed by address reuse. Individual heuristics had low false-positive rates but found only a minority of change outputs: optimal change identified 30.6% at a 2.6% false-positive rate, address type 23.7% at 3.1%. A random-forest classifier combining heuristics and fingerprints found about 82% of change at a false-positive rate near 0.06%.

Two lessons follow. First, error rates are tied to their dataset and period; quote them with their source, never as constants. Second, even a 0.06% false-positive rate is large when applied to hundreds of millions of transactions: Möser and Narayanan found that merging naively on their classifier's output produced a supercluster of 223.9 million addresses, and they had to add constraints to prevent it (see the lesson Evaluating cluster quality).

Scoring and confidence

A transparent approach scores each candidate output and accepts a change label only when one output is clearly ahead:

-- Score each output of two-output transactions as a change candidate
SELECT o.tx_id, o.output_index, o.address,
       (CASE WHEN o.script_type = s.input_script_type THEN 1 ELSE 0 END)
     + (CASE WHEN MOD(o.value_sat, 100000) <> 0 THEN 1 ELSE 0 END)
     + (CASE WHEN f.first_seen_block = o.block_height THEN 1 ELSE 0 END)
       AS change_score
FROM outputs o
JOIN tx_summary s          ON s.tx_id = o.tx_id
JOIN address_first_seen f  ON f.address = o.address
WHERE s.output_count = 2
  AND s.single_input_type = TRUE;  -- skip mixed-type inputs

Each output earns one point for matching the input script type, one for a non-round value (not a multiple of 100,000 satoshis, or 0.001 BTC) and one for being seen for the first time in this block. Some engines write MOD(a, b) as a % b. The query scores both outputs; a downstream step accepts output 1 as change only if, say, it scores 3 and output 0 scores 0 or 1. Ties mean "unknown", not a coin flip. Lesson Querying UTXO data shows how to build the helper tables.

Failure modes to remember

• No change at all. Coin selection methods such as Bitcoin Core's Branch and Bound look for input sets that match the payment exactly, producing changeless transactions. A heuristic forced to pick an output will then label the payment as change.
• Self-transfers and consolidations, where every output belongs to the sender.
• Batch payouts with many outputs, where several look fresh.
• PayJoin and CoinJoin, which are designed to defeat these rules.
• Uniform address types, which remove the script-type signal.

Change links should carry their confidence into the evidence table, and reports should state whether a finding depends on them.

Exam focus: why change outputs exist; the fresh-address, script-type, round-amount and optimal-change heuristics and the failure mode of each; Meiklejohn et al.'s Heuristic 2 conditions and its naive supercluster; wallet fingerprints (version and BIP 68, locktime and anti-fee-sniping, BIP 125 RBF signaling, BIP 69 ordering) and why they are dated evidence; the contrast between 0.17% (Meiklejohn, 2013) and 51.64% (Kappos et al., 2022) for the same heuristic; why low false-positive rates still cause collapse at scale; scoring outputs and treating ties as unknown; changeless transactions.