I have been looking at the algorithm Bitcoin uses to choose coins. The algorithm does not lend itself to obscuring the trail of coin transfers. In fact, I think it makes it easier for someone analyzing the transactions to figure out things.
Suppose, for example, there is a transaction with two coins in and two coins out (one for the payment, one for the change). The source code randomizes which output is the payment, and which is the change, but in most cases it is trivial to look at the transaction and figure it out. For example, suppose there's a transaction with two inputs, 50 coins and 20 coins; and two outputs, 65 coins and 5 coins. It's pretty clear that the payment is 65 coins, and the change - which goes back to the owner - is 5 coins. You have now linked two coin transactions to a single person (whether or not you can identify that person is another matter).
Or, suppose Bitcoin creates a transaction with several (or even many) coins on the input side. If an analyst links just one of those coins to you, that person now knows for certain that all the other coins in that transaction also belonged to you. So, for anonymity sake, the fewer the coins on the 'in' side, the better.
And, of course, if a transaction has one input and one output, it's a no-brainer to figure it out.
The program uses what I call a "best fit" algorithm - i.e. it chooses one or more coins that come as close as possible to the exact value requested, giving preference to selecting a single coin with the exact payment value. So you will likely find many transactions that have multiple coins coming in, and one or two transactions out - the payment, and a small amount of change, or with exactly one input and one output. In either case, it's pretty easy to figure out what's going on.
Fortunately, the default behaviour of the program is to choose a new key each time you receive a payment, so that's a plus at least.
I don't know if this is the correct place to make these suggestions, but I would suggest modifying the standard Bitcoin program as follows:
- Eliminate the transaction logging in the wallet. Your wallet should contain only the coins you haven't spent (after having been confirmed, of course).
- Accounting entries should never be linked to specific coins or addresses used to create that entry.
- Automatically "shuffle" the coins. By "shuffling" I mean generating transactions within your own wallet - take one or two coins, and pay them to a Bitcoin address - NOT an IP address - under your control. (Note that for this to work, transaction logging MUST be removed.) This helps strengthen the plausible deniability mentioned in the article: since the program automatically generates these transactions, if someone questions where a particular payment went to you can legitimately say you don't know. Transactions would created at random intervals (but ideally not more frequently than once every 10 minutes or so, to keep them on separate blocks), using coins selected at random, and the transaction would be chosen at random from the following list:
- Combine two coins into a single coin.
- split a single coin into two coins
- Rearrange two coins into two coins of different values, for example 5+2 in, 1+6 out. In order for this to be indistinguishable from an actual transaction, one output must be larger than the larger of the two inputs. In this example, the larger input is 5, so one output must be > 5. If not, then it will be obvious that this is a shuffling transaction. For example, if the outputs are 3+4, then you could obviously have paid with just the 5 BTC coin and there's no reason to include the 2BTC coin.
- Modify the coin selection routine to randomly choose one of the following algorithms:
- Select two coins, the value of each coin being greater than the value of the payment. For example, payment amount is 5. Choose 50+20 in, giving 65+5 out. In this case, the payment is 5 and the change is 65. Randomize which is the payment and which is the change.
- Select two coins, the value of each coin being smaller than the value of the payment. For example, payment amount is 65. Choose 50+20 in, 65+5 out. Randomize which is the payment and which is the change.
- Select two coins which equal exactly the payment amount (this matches the "combine two coins into a single coin" shuffle operation above).
- Select a single coin for payment, with a value much greater than the value of the payment (for some definition of "much greater"). About 2x the payment value is good, because then the payment and the change are about the same, and a snooper won't be able to tell which is which.
- Choose multiple coins such that the value of the payment is greater than the value of the smallest coin, but less than the value of the largest coin. For example, your payment is 7 BTC. Choose coins valued at 5, 8, and 10, giving a payment of 7 and change of 16.
- The existing "best fit" algorithm, modified so that it only selects a single coin with the exact value as a last resort.
- That does sound like an improvement. I don't think most people care much about anonymity right now, though, and it's not that easy to track transactions, so the solution needs to be good for average users (or there needs to be an option). Most of those changes will increase transaction sizes, which will increase fees. theymos 05:10, 5 March 2011 (GMT)