Privacy through cloning the value of other transactions

Bitcoins have quite a bit of divisibility, and often people want to send coins without traceability. Now if I send 146.252394BTC from address a to address b, even through a mixer like the one at blockchain.info, anyone can simply watch the block chain for transaction pairs with the same values at either end (taking fees into account) and quickly destroy the privacy provided. (even if the "taint" is nominally removed)

Now services like torwallet and bitcoinfog recommend you never transfer in and out the same number of coins, and ideally leave at least a small balance hanging around to obscure the fund amounts. However it is still far from certain that someone couldn't still use statistical analysis to link up address groups. If everyone used a set of fixed values, like 0.1BTC, 1BTC, 10BTC etc. there would be less of a problem, but people don't do that. Besides, using small-int values may be suspicious in of itself. (note that this is the solution Chaums suggested for Chaum-style currency tokens)

However, lets suppose you clone the amounts of other transactions? Now any statistics have to deal with the fact that multiple, unrelated, transactions happen to have the same numerical value. The stats can use transaction time, but if you act quickly it's you can simply clone a transaction as it enters your memory pool, which on the bitcoin network means the only way to know which is first is to use your thousand node sybil network to watch which transaction the watched nodes relayed first. If the attacker has only the blockchain to look at sometime in the future they have even less ability to distinguish the two transactions.

Essentially the set of possible source and destination addresses in the "related set" just doubled, with only half the addresses being actually related.

Now, to be more rigorous lets assume the existence of a shared mixing service, where any deposits or withdrawals go to a single mixing pot. To withdraw from the service, wait until a pending outgoing transaction from the service happens to have a value useful to you, and tell the service to send another transaction with the same value. If fees are selectable that's ok, so long as the amount going to your destination matches another transaction.

Deposits are ideally done in the same way, although in practical terms this would require giving the signed transaction to the service directly, and not broadcasting it on the network.

The next example uses an online wallet where funds are not commingled. IE it should keep track of many different addresses, and avoid whenever possible using multiple addresses to fund one outgoing transaction. If we think the attacker can figure out what addresses the online wallet controls, we just use it as above, if we think the attacker does not know that, we can use clone the value of any transaction on the network. Similarly if we can ask the wallet for new addresses on demand, we can clone and transaction on the network to send funds to the wallet.

A nice implementation would be for a service like instawallet to provide the ability to say "I want to transfer at least x BTC to address a, and pay no more than y% extra", with y <5%, and then instawallet would wait until a user of the service happened to submit a transfer request matching the desired value.

Of course there are pitfalls, and nasty ones. For instance lets suppose you want to move every coins from "dirty" address a to "clean" address b; maybe b is your archival brainwallet. If the move is done in a short period of time any attacker can see which addresses matched regardless of how many moves it took. It's just a matter of how many sets of transactions can fill that knapsack. You really need multiple b's, b1, b2, etc. and if you ever use them all, or even a subset of them, to fund one transaction your anonymity is lost. Similarly if you are trying to claim that coins at address a in your possession didn't come from b, you're going to have a hard time if the cloned transaction masking the move was spent long ago.

If your cloned transaction happens to be one that the attacker has info on, say they know of it because they happen to operate instawallet, they can rule it out of their statistical analysis. (note how this provides an incentive to attackers to operate useful, easy to use, high-profile, reliable, trustworthy, bitcoin related services with excellent security... who does piuk work for anyway?)

It also occurs to me that while I've seen good analysis of "taint" in the bitcoin network, (for instance by piuk's blockchain.info) I haven't seen this type of matching value analysis attempted. It'd be useful if someone with more statistics knowledge than me was researching this, and posting their results publicly. We can be sure some TLA is already doing it after all.

The actual algorithm to implement this attack would be some multiple-knapsack variant of the knapsack problem. Do you guys with actual comp-sci/stats degrees have any idea of how feasible this is? My understanding is that the knapsack problem itself is NP-hard, but I don't know what shortcuts can be taken in this particular example, especially given we only care about probabilities. I certainly wouldn't want to assume it's infeasible; even O(k*n^n) is cheap if n and k are small enough...