Yesterday, I wrote about stolen bitcoins and the issues around a database of stolen coins. The issue is very complex, so today I will add some follow-up issues.

When stolen property changes hands (innocently) the law says that nobody in the chain had authority to transfer title to that property. Let's assume that the law accepts bitcoins as property, and bitcoin transactions as denoting transfer of title, (as well as possession/control) to it. So with a stolen bitcoin, the final recipient is required on the law to return possession of the coin to its rightful owner, the victim of the theft. However, that recipient is also now entitled to demand back whatever they paid for the bitcoin, and so on down the line, all the way to the thief. With anonymous transactions, that's a tall order, though most real world transactions are not that anonymous.

This is complicated by the fact that almost all Bitcoin transactions mix coins together. A Bitcoin "wallet" doesn't hold bitcoins, rather it holds addresses which were the outputs of earlier transactions, and those outputs were amounts of bitcoin. When you want to do a new transaction, you do two things:

1. You gather together enough addresses in your wallet which hold outputs of prior transactions, which together add up to as much as you plan to spend, and almost always a bit more.
2. You write a transaction that lists all those old outputs as "inputs" and then has a series of outputs, which are the addresses of the recipients of the transaction.

There are typically 3 (or more) outputs on a transaction:

1. The person you're paying. The output is set to be the amount you're paying
2. Yourself. The output is the "change" from the transaction since the inputs probably didn't add up exactly to the amount you're paying.
3. Any amount left over -- normally small and sometimes zero -- which does not have a specific output, but is given as a transaction fee to the miner who put your transaction into the Bitcoin ledger (blockchain.)

They can be more complex, but the vast majority work like this. While normally you pay the "change" back to yourself, the address for the change can be any new random address, and nothing in the ledger connects it to you.

So as you can see, a transaction might combine a ton of inputs, some of which are clean, untainted coins, some of which are tainted, and some of which are mixed. After coins have been through a lot of transactions, the mix can be very complex. Not so complex as the computers can't deal with it and calculate a precise fraction of the total coin that was tainted, but much too complex for humans to wish to worry about.

A thief will want to mix up their coins as quickly as possible, and there are a variety of ways to do that.

Right now, the people who bought coins at Mt.Gox (or those who sent them there to buy other currency) are the main victims of this heist. They thought they had a balance there, and its gone. Many of them bought these coins at lower prices, and so their loss is not nearly as high as the total suggests, but they are deservedly upset.

Unfortunately, if the law does right by them and recovers their stolen property, it is likely that might come from the whole Bitcoin owning and using community, because of the fact that everybody in the chain is liable. Of particular concern are the merchants who are taking bitcoin on their web sites. Let's speculate on the typical path of a stolen coin that's been around for a while:

• It left Mt.Gox for cash, sold by the thief, and a speculator simply held onto the coins. That's the "easy" one, the person who now has stolen coins has to find the thief and get their money back. Not too likely, but legally clear.
• It left Mt.Gox and was used in a series of transactions, ending up with one where somebody bought an item from a web store using bitcoin.
• With almost all stores, the merchant system takes all bitcoin received and sells it for dollars that day. Somebody else -- usually a bitcoin speculator -- paid dollars for that bitcoin that day, and the chain continues.

There is the potential here for a lot of hassle. The store learns they sold partially tainted bitcoins. The speculator wants and is entitled to getting a portion of her money back, and the store is an easy target to go after. The store now has to go after their customer for the missing money. The store also probably knows who their customer is. The customer may have less knowledge of where her bitcoins came from.

This is a huge hassle for the store, and might very well lead to stores reversing their decisions to accept bitcoin. If 6% of all bitcoins are stolen, as the Mt.Gox heist alleges, most transactions are tainted. 6% is an amount worth recovering for many, and it's probably all the profit at a typical web store. Worse, the number of stolen coins may be closer to 15% of all the circulating bitcoins, certainly something worth recovering on many transactions.

The "sinking taint" approach

Previously, I suggested a rule. The rule was that if a transaction merges various inputs which are variously reported as stolen (tainted) and not, then the total percentage be calculated, and the first outputs receive all the tainting, and the latter outputs (including the transaction fee, last of all) be marked clear. One of the outputs would remain partial unless the transaction was designed to avoid this. There is no inherent rule that the "change" comes last, it is just a custom, and it would probably be reversed, so that as much of the tainted fraction remains in the change as possible, and the paid amount is as clean as possible. Recipients would want to insist on that.

This allows the creation of a special transaction that people could do with themselves on discovering they have coin that is reported stolen. The transaction would split the coin precisely into one or more purely tainted outputs, and one or more fully clean outputs. Recipients would likely refuse bitcoin with any taint on it at all, and so holders of bitcoin would be forced to do these dividing transactions. (They might have to do them again if new theft reports come on coin that they own.) People would end up doing various combinations of these transactions to protect their privacy and not publicly correlate all their coin.

Tainted transaction fees?

The above system makes the transaction fee clean if any of the coin in the transaction is clean. If this is not done, miners might not accept such transactions. On the other hand, there is an argument that it would be good if miners refused even partially tainted transactions, other than the ones above used to divide the stolen coins from the clean. There would need to be a rule that allows a transaction to be declared a splitting transaction which pays its fees from the clean part. In this case, as soon as coins had any taint at all, they would become unspendable in the legit markets and it would be necessary to split them. They would still be spendable with people who did not accept this system, or in some underground markets, but they would probably convert to other currencies at a discount.

This works better if there is agreement on the database of tainted coins, but that's unlikely. As such, miners would decide what databases to use. Anything in the database used by a significant portion of the miners would make those coins difficult to spend and thus prime for splitting. However, if they are clean in the view of a significant fraction of the miners, they will enter the blockchain eventually.

This is a lot of complexity, much more than anybody in the Bitcoin community wants. The issue is that if the law gets involved, there is a world of pain in store for the system, and merchants, if a large fraction of all circulating coins are reported as stolen in a police report, even a Japanese police report.