Tracing a coin's lineage

Assuming a goal of bitcoin is to introduce anonymity to online transactions, one of the things that concerns me most is the traceability of coins to previous transactions. I’ve read a lot of discussion about this in the forums, but there’s still some open questions for me.

So first, let me state what I do understand:

1. All transactions are public in their amounts and public key identities as follows: a) In a transaction, you can see the public key of the person who spent the money b) In a transaction, I think but am not completely sure you can see the public key of the person who gets the money. (If you can’t, you’ll see it when they spend the money later, so this isn’t that important.

2. Keeping your public keys from being associated with your identity is required if you don’t want your transactions to be attributable to you.

We need to better educate users on how to do #2. I have an information security background, and it’s not even immediately obvious to me what the best ways of handling bitcoins are to maximize your privacy.

I have these specific questions or comments regarding this topic:

1. Are one-time public keys disposed of when they are no longer required?

For example, I’ve read that a one-time-use private key is created when I generate a bitcoin block. When I spend these coins and I’ve signed them to someone else, I shouldn’t need that private key anymore. The same thing goes for a key created for taking a payment-by-IP. Keeping keys around after they are no longer necessary may make a user vulnerable to later having their wallet seized and used to prove that they originated a transaction.

2. Reusable keys (those created inside the GUI) should be able to be similarly deleted when they are no longer required. This is a bit more dangerous, because once you delete the key you won’t be able to get payments sent to that key, so the user really needs to understand what’s going on in this case. Keys with coins stored under them obviously shouldn’t be deleted.

3. We really need to make it possible to track coin bundle’s lineage to enable the user to know their risk regarding spending specific coins. I think it should be possible, within the GUI, to see all the public keys associated with each coin bundle. It would also be nice to be able to tag keys that are associated with you with comments to aid you in determining which coins to send to someone. That way you could realize that another bitcoin user has seen you use a specific key, and to restrict other coins that are also associated with that key to a similar purpose and not something else that would link the two identities.

4. In addition to making it possible to track a coin bundle’s lineage, we also need to be able to choose which coin bundles to include in a payment.

The important thing here is that we need to make the information that is possible to acquire through digital forensics to be easily accessible by the end user. Only by making this information accessible to the end user will people be able to make good security decisions regarding the spending of bitcoins in sensitive environments.

One more thing that is important: Once these features are available, exchangers need to have clear data retention policies. For example, if I was an exchanger, I might keep track of the public keys of the people that I am doing active trades with. I’d probably retain this information until I had traded out the coins I had acquired through a trade, but would dispose of this information once the coins had left my possession. I would also have a policy to not share that information with third parties unless required to by a court order. If I was trading with an exchanger, I would want to know what their policies were and how they differed from my expectations.

Can’t we force a user to use a new address for receiving payments? Every time a payment is received display another Bitcoin address in the address bar. (only transactions via Bitcoin addresses, NOT IPs of course, since that’d be useless, right?) The actual key would still be kept to ensure that the user would still receive payments of people sending to the same address. (We wanna minimize “lost” Bitcoins, right?)

This yields a couple of questions:

• Is this technologically possible? (Probably.)
• Is this bad to force it upon users? (Probably.)
• Should we implement such a feature? (I don’t know, I wouldn’t unless we don’t have a choice, better half a defense than none!)

So, are there any alternatives to combat “coin lineage”?

BitCoin could automatically send random coins to a new address at random times. This would make knowing a coin’s lineage useless to an attacker, since any of these new addresses could be actual people.

Quote from: Xunie on May 25, 2010, 3:50:04 PM UTC

Can’t we force a user to use a new address for receiving payments?

Every time a payment is received display another Bitcoin address in the address bar. (only transactions via Bitcoin addresses, NOT IPs of course, since that’d be useless, right?) The actual key would still be kept to ensure that the user would still receive payments of people sending to the same address. This is on my list.  I will soon make the “Your Bitcoin Address:” window automatically change whenever you receive anything to the address displayed.

I’m also recommending this approach for the implementation of web apps.  I just posted some sample code showing a suggested way of implementing this.

Versions on SVN since 0.2.4 already have a “New…” button next to the address bar to encourage changing it manually too.

@theymos: If nothing else, we can fall back on that solution in the future.

Quote from: theymos on May 26, 2010, 3:39:50 AM UTC

BitCoin could automatically send random coins to a new address at random times. This would make knowing a coin’s lineage useless to an attacker, since any of these new addresses could be actual people.

Then what if you’ll keep running Bitcoin long enough? Will you get broke? (Or change the “random payment” amount to be very small.) And I thought the transaction amount was public anyways? Because if it is, then it’ll make the function useless since any attacker could just check if the amount transferred is higher than the “random payment limit”.

I dunno, sounds like a bad idea to me.

You’d send the coins to an address owned by yourself. So you lose nothing. It’s impossible to tell that you’re sending the coins to yourself. There’s no need for a “random payment limit” — “laundering” even your entire wallet at once would be harmless.

Choosing random addresses will not be enough, I think. Fiat-to-BitCoin exchangers will always be an “anchor of identity” to a coin, since they know both the identity of the person buying coins and the destination address.

It would be necessary to make random periodic exchanges with other bitcoin holders to separate your identity from your bitcoins.