clustering addresses, what's the most effective way?

Question

The Fistful of Bitcoins paper by Meiklejohn et al has some nice heuristics. i.e.

HEURISTIC 1. If two (or more) addresses are inputs to the same transaction, they are controlled by the same user; i.e., for any transaction t, all pk ∈ inputs(t) are controlled by the same user.

HEURISTIC 2. The one-time change address is controlled by the same user as the input addresses; i.e., for any transaction t, the controller of inputs(t) also controls the one-time change address pk ∈ outputs(t) (if such an address exists).

Are there any others that are particularly effective?

Is it possible to bootstrap my clustering, for instance, maybe if some people have already associated a certain cluster with Kraken or Satoshi Dice, is this information available?

Answer 1

Are there any others that are particularly effective?

Yes, if you know what wallet was used and if its transactions have distinguishing features. For example, multisig wallets usually use p2sh change, but the recipient rarely uses p2sh, which allows to determine the correct change output with high probability.

Data-Driven De-Anonymization in Bitcoin introduces two new general heuristics:

CONSUMER HEURISTIC. Consumer wallets only create transactions with two outputs. Therefore, if an output is spent by a transaction with 3 outputs it is not change.

OPTIMAL CHANGE HEURISTIC. The assumption is that wallet software does not spend outputs unnecessarily. Therefore the change value is smaller than any of the spent outputs. Because if the change was larger than one output then this output would be left out and the change would be reduced by the output’s value.

The thesis also evaluates the effectiveness of the heuristics using data captured from Android Bitcoin Wallet with the Bloom filter address leak in late 2014. It turns out that Multi-Input heuristic is by far the most effective: if applied to one address, in total 68.59% used addresses of the wallet are revealed.

By the way, the Heuristic 2 you mention was first described by Androulaki et al. in Evaluating User Privacy In Bitcoin.

Is it possible to bootstrap my clustering, for instance, maybe if some people have already associated a certain cluster with Kraken or Satoshi Dice, is this information available?

Blockchain.info has a database of tags (https://blockchain.info/tags).