I think there's a lot I, and others, can do to prevent it from happening. The first thing is to make stakeholders understand that this is a huge threat. The second thing is to come up with better responses that don't involve tainting coins. (Which, from the evidence I've seem so far, seems to be what Mt. Gox is doing. So kudos to Gox.)

Agreed. Let's hope it is too much of a hassle. But let's hope MtGox, who is by far the biggest and possibly indispensible exchange, sees it that way also.

Anything adding an extra layer of complexity is a massive NO-GO for bitcoin IMO.

You have to take into account that there are hundreds of ways such a system would be gamed. A complexity arms race is the least thing bitcoin needs.

For example: order of transactions within a block is not deterministic. I can have a clean account with, say, only freshly mined coins, and a tainted account. I give you the clean address and you accept the payment by some automatic means of checking taint. Then I immediately transfer a boatload of highly tainted coins to this address. Both transactions happen in the same block and you cannot reliably tell which happened first. Your account is now highly tainted, you may just have lost a lot of value if untainted coins have a big premium due to this system. Then you have to add even more delay to the already high delay there is to have a proper number of confirmations, and you really cannot have an automated system.

Off the top of my head I can think of dozens of attacks.

I wouldn't work in a system like this. Not while I still have coins.

+1

As soon as there's such a mechanism, stolen coins will find a way to avoid being detected, there's just no way you can do that 100% reliably. This would only result in a great big mess - people wrongfully accusing others of having their coins stolen (even if it was a regular payment or donation) just to get them into trouble, people fighting over evidence and reputation, online wallet services getting into trouble because some think their acceptance policies are not strict enough, tainting coins of innocent others in the process, people flooding donation addresses with tainted coins,...
Also, what would be the next step? Refuse blocks from "shady" miners who include transactions with tainted fees?

We really don't need that - fighting Bitcoin thefts at that level is just not the way to go. You'd only make it a bit harder for Bitcoin thieves at the cost of making Bitcoin a much more miserable experience for everyone else!

Oh and I'm not trying to talk anybody out of implementing such a system, please go ahead and do it, just don't expect it to become widely adopted. Even people thinking such a system would be a good idea in principle are likely to disagree on the details, fighting and lobbying for their favored policies, etc... In the end, it would have been much more effective to just make two-factor authentication easy to use for everyone.

Who cares?... 

A coin is a coin is a coin, just like a dollar bill is a dollar bill is a dollar bill, with or without coke on it.

1)  product idea:  "level of taint on my bitcoin" site, with a formula to determine level of taint, how many transactions ago, etc

2)  I agree, Gox or any other exchange shouldn't judge your coins, a coin is a coin and it's a brutal, unforgiving system but that's what it has been created here can't police the coins.

I wonder if this could become a sort of marketing tool:

• bad security incident happens to company
• company gets negative press, loads of it
• company acts responsibly and betters itself, improves security
• company shines, gets new customers who think company must now be very secure

it worked for mtgox

I myself didn't even know of linode before. If they act correctly now, I might even consider them next time I look for a VPS provider -> successful marketing.

+1

If all you need is to accept Bitcoin in an e-commerce, then you do not need to leave your private keys on the server. For example, you can use a deterministic wallet to generate your addresses without the private keys.

If your server needs to send bitcoins to customers (which was the case for bitcoinica and slush's pool), it is probably not reasonable to use a VPS, especially if large amounts are involved.

Public addresses are derived from the private key, so deterministic wallet is not the solution.  However, you are correct that you don't need the private keys.  You can simple keep a buffer of a few thousand address in your db that match private keys you store in a safe location.