Tracing a coin's lineage

[Dynotor]

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. 

[Xunie]

The points you mentioned are of high concern to me (and should be to the rest of the community.)
Your suggestion of making the information that can found with/through digital forensics available to the user seems very good in securing Bitcoin.
Maybe build a "paranoid mode" switch in Bitcoin that will immediately show all that info to the user!
Also what seems like a good idea is to show that switch in a "first run dialog", but some people find that annoying. (I would too a business environment!)
Maybe distribute a "Home" and "Business" binary that has the "first run dialog" and one without it, ofcourse in that order.

But, as this data is available, and people will trust Bitcoin (sometimes blindly), we'll have to warn users about pitfalls.
Have proper documentation documenting everything, even for the "paranoid users".
Users will have to learn how to make safe transactions, etc...


If someone screws up and gets screwed over by the justice system because he trusted Bitcoin blindly, he'll speak about it and Bitcoin will get a bad name.

My conclusion: the Bitcoin community needs to watch out for the losers dumb users lusers!

[D҉ataWraith]

It's good that someone is thinking along the lines of how security/anonymity could be compromised.

Yes, you know both sender and recipient of a payment. The recipient's key is always included, and from there you can trace the coin back to the previous recipient, i.e. the current sender.

My 2฿ worth of thoughts:

Ideally the Bitcoin wallet should be encrypted, and future versions will implement that. Now, leaving malware out of the picture (which would probably just send all bitcoins to the hacker in question instead of tracing transactions back), when both your computer is confiscated and you are forced to reveal the password, you're probably already in big trouble... you'd have to already have screwed up other than by using bitcoin in an unsafe manner. Personally I don't worry about this, but it is good that somebody does.

As an aside: Bitcoin can be used over the TOR network, so one can hide one's IP address. There are also the web-based wallet services, which might make it harder to trace a transaction that went through them. On the other hand, they could do some tracing of their own... The deciding factor here is which coins are chosen for which transactions.

As for coin lineage, yeah, that might be a problem. Currently it is a best practice to give out a different address to every sender, and only give it to them. An outside observer you can't know if the next recipient (or rather crypographic key) the coin is sent to is one of your aliases or someone else entirely. Bitcoin Currency Exchanges (or any high-volume user) might be a problem here, but otherwise one probably doesn't have enough data to infer much about the transfers, it just becomes untractable if every person has a lot of different addresses. One additional point here is that old transactions expire after a while, and the space is reclaimed -- that wouldn't stop a serious attacker, but it's helping a little.

[Xunie]

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"?

[theymos]

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.

[satoshi]

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.

[Xunie]

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.

[theymos]

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.

[bitcoin1234]

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