Tracing Stolen Bitcoin

Ross Anderson has a really interesting paper on tracing stolen bitcoin. From a blog post:

Previous attempts to track tainted coins had used either the "poison" or the "haircut" method. Suppose I open a new address and pay into it three stolen bitcoin followed by seven freshly-mined ones. Then under poison, the output is ten stolen bitcoin, while under haircut it's ten bitcoin that are marked 30% stolen. After thousands of blocks, poison tainting will blacklist millions of addresses, while with haircut the taint gets diffused, so neither is very effective at tracking stolen property. Bitcoin due-diligence services supplant haircut taint tracking with AI/ML, but the results are still not satisfactory.

We discovered that, back in 1816, the High Court had to tackle this problem in Clayton's case, which involved the assets and liabilities of a bank that had gone bust. The court ruled that money must be tracked through accounts on the basis of first-in, first out (FIFO); the first penny into an account goes to satisfy the first withdrawal, and so on.

Ilia Shumailov has written software that applies FIFO tainting to the blockchain and the results are impressive, with a massive improvement in precision. What's more, FIFO taint tracking is lossless, unlike haircut; so in addition to tracking a stolen coin forward to find where it's gone, you can start with any UTXO and trace it backwards to see its entire ancestry. It's not just good law; it's good computer science too.

Posted on March 28, 2018 at 6:30 AM • 14 Comments


WinterMarch 28, 2018 8:39 AM

The comments in the linked blog post point out some reasons for caution. However, It seems to be a better way of tracing stolen money than the alternatives.

I doubt its use for reclaiming stolen bitcoins outside of "English" jurisdictions. Over here, any transaction entered in good faith is final. Stolen goods cannot be reclaimed from those who accepted them in good faith.

keinerMarch 28, 2018 9:15 AM

Hmmm, could all bitcoins be fully tracked over their entire life time? Nightmare for the darknet, I would guess...

SethMarch 28, 2018 9:38 AM

Winter, the paper seems to address your concern, and those of most of the commenters. Surprisingly, it is very light on the technology side, it seems to be focused on practical applications and policies. It seems that the goal is not recovery of bitcoins as much as tracking and preventing stolen bitcoin from being easily used.

The researchers have created a list of known stolen bitcoin, which they're calling the "taintchain", that any bitcoin can be compared against. Using current methods of tracking stolen bitcoin most bitcoins in use are tainted, but with the proposed FIFO approach it reduces it to 20% or so that are bad. So, it would be possible (or even required) for bitcoin exchanges to refuse "bad" bitcoin.

Of course it seems that any intelligent thief would quickly change their strategy so that the bitcoin couldn't be tracked using FIFO, but perhaps I missed that part of the paper. I also wonder how quickly it could react to new reports of stolen coins.

jbmartin6March 28, 2018 11:23 AM

I'm not sure I understand the point here. Bitcoin is just a ledger operation, i.e. plus or minus some amount. It is inherently fungible, meaning there is nothing to distinguish one portion of it from another. If I have a bitcoin and they use this method to decide that bitcoin was one stolen ten hops ago, I could potentially be required to return it? The paper touches on this, noting the danger of damaging the fungibility of bitcoin. My best guess is it is a way of identifying money launderers or other miscreants by looking at nodes with an unusually high number of 'tainted' coins

WinterMarch 28, 2018 11:56 AM

"It is inherently fungible, meaning there is nothing to distinguish one portion of it from another. "

Indeed, but the addresses that received the stolen money would be like bank account numbers. We could envision that these addresses would be blacklisted so the bitcoins could not be moved or spend. I do not see how this could be implemented in any way given the speed of bitcoin transactions. By following the money trail, the receiving ends could be leaned upon to "help the police with their inquiries".

I doubt this would be practical, but knowledge is power. If tainted bitcoin can be tracked, things will be learned about the thieves.

Jesse ThompsonMarch 28, 2018 1:58 PM

Yeah, this still attacks fungibility.

The basic response to a FIFO analysis is that fugitive pours bitcoins into a mixer first, non-fugitive pours bitcoin in next, mixer is set to pay out in unpredictable order and winds up paying non-fugitive first and fugitive next.

Now fugitive's bitcoins are no longer traced by FIFO (we're presuming they poured in equal amounts for the simplest to envision outcome) while non-fugitive is completely on the hook. Now non-fugitive can't bring their bitcoin to an exchange to cash out without allowing LEO to shove a camera up their bum first in a series of humiliating attempts to prove they weren't original fugitive, but ultimately just punishment for ever using a mixer or attempting to be anonymous to begin with.

Things get even darker when inputs and outputs fail to match up precisely, you wind up with a position a lot like Haircut where each user has X% of their funds tainted. How is that supposed to pan out, anyhow? Everyone who tries to cash out at the exchange gets only X% of their funds locked? We could have just done that with haircut and ignored FIFO entirely.

I think I'll let my distant ancestor handle this one:

We are to look upon it as more beneficial that many guilty persons should escape unpunished than one innocent person should suffer. The reason is because it’s of more importance to community that innocence should be protected than it is that guilt should be punished, for guilt and crimes are so frequent in the world that all of them cannot be punished, and many times they happen in such a manner that it is not of much consequence to the public whether they are punished or not.

But when innocence itself is brought to the bar and condemned — especially to die — the subject will exclaim: "it is immaterial to me whether I behave well or ill, for virtue itself is no security." And if such a sentiment as this should take place in the mind of the subject there would be an end to all security what so ever.

- - John Adams

BobMarch 28, 2018 2:27 PM

"We also looked at bitcoin laundries or mixes. These are based on the idea
that if you put one black coin in a bag with nine white ones and shake hard
enough, you’ll get ten white ones out. But depending on the algorithm in use,
FIFO tainting will decide that one of the outputs is black (and no owner of
a white coin will want to risk that outcome)"

"It's not just good law; it's good computer science too."

I don't see how it is good to falsely accuse people with a crime or manipulate them into thinking that it is better not exercise their right to privacy not to be mixed with the criminals.

David LeppikMarch 28, 2018 3:56 PM

I bet Etherium's smart contracts could be used to get around FIFO. That is, set up a smart contract where a wallet pays out to the intended recipient only after the same wallet has been used for unrelated transactions. Of course, such an obvious rule would be a red flag.

Sergey BabkinMarch 28, 2018 4:09 PM

In practice it probably isn't any different from the haircut, because the main problems are probably how to locate and deal with the thief, and whether the coin should be reposessed or not.

If the coin is still owned by the thief, it should definitely be reposessed. If the thief had used the coin to pay to a valid merchant, the coin should probably be not reposessed (although if the thief is caught and whatever he bought has been reposessed, the transaction should possibly be undone, returning the coin and the merchandise back).

This means that for each account containing the stolen coins we need to figure out somehow if it's a valid merchant or just another account owned by the thief and used to launder the coins. One way to do it would be to physically catch the thief and find all the accounts owned by him, which is not easy. Another way would be to look at the percentage of the stolen coins in the account. If the percentage is high, that is probably a laundering account, if the percentage is low then it's probably a valid merchant. And the percentage computation gives pretty much exactly the same computation with the haircut as with the FIFO. FIFO is actually worse in this regard because it introduces more randomness.

Of course, the percentage can be misleading too: if you open a new account, put 10 count into it, and then unknowingly get a payment of 90 stolen coins, suddently the account looks like a laundering one.

But in this sense FIFO works much worse than haircut: if you get a payment from a valid merchant who has 100K coins with 100 of them tainted, and FIFO gives you 90 out of these 100 tainted coins, your account suddenly becomes 90% tainted. But with teh haircut method you'd get 90 coins that are 0.1% tainted, and your acount would be only 0.09% tainted. So the dilution in the haircut method is not a bug, it's a feature.

Ann OminousMarch 28, 2018 5:01 PM

Bad currency drives out good. If FIFO tainting becomes popular but not universal, people will preferentially spend tainted coins by sorting the untainted ones into another wallet.

WinterMarch 29, 2018 4:56 AM

"U.S. authorities are absolutely in the wrong to tolerate Bitcoin or other digital "blockchain" currencies even for a minute. It is a scam."
"I see you as a troll, had to say it."

Actually, I think he has a point.

The same point has been made about gold. That was introduced as a payment method a few centuries BC to pay for mercenaries and other terrorists. It was a scam by the likes of King Midas (who lived in what is now Turkey, go figure) to finance his criminal campaigns to loot the neighborhood.

Ever since that time, cash has been used for criminal and terrorist purposes. Bitcoin is just as much a criminal means as cash is.

JG4March 29, 2018 6:13 AM

@Winter - The flipside of every tool of oppression is a tool for the advancement of human rights. One of my buddies got out of Vietnam for 8 ounces of gold, which bought him a ride in a badly overloaded boat. With the gold watch that he managed to keep through the multiple stops by pirates, he purchased cooking lessons in a refugee camp in Malaysia. He is an expert at cooking anything that you might catch. I was told in the past couple of years that the (past?) Chief Rabbi of Israel was a child of perhaps 6 or 7 years of age when he was sent to the camps. His mother sewed gold into the lining of his jacket. He spent all of the gold on bribes in the first 24 hours, but somehow managed to keep himself and his younger brother alive. His mother was not so fortunate. I probably said that Leo Szilard lived for four years in Nazi Germany with his suitcase packed. It was a great place to do nuclear research. He knew that he was leaving, and that when he was leaving, that he might want to leave quickly. The rest is history.

I think that the divisibility, fungibility, (relative) durability, and recognizability of both barley and gold have been discussed before. People who live on roots and cabbages are more difficult to tax than those who eat grains. One of the aims of empire is to wipe out the peasants who are impossible to tax, because they live at the margin of survival, and replace them with more profitable tenants, who will use the coin of the new realm. So much the better if a high-functioning local psychopath can be found to run the show via a network of sociopaths. Your point is well taken that this highly portable medium of exchange is particularly convenient for hiring mercenaries and assassins. I doubt that was the first use, but certainly an early use. It may be noted that cash serves the same purpose and that many hundreds of billions of dollars of no-bid contracts have been paid to mercenaries in the past 15 years. I've probably pointed out, but not for a long time, that these media of exchange are proxies for Gibbs free energy. There is a lot of diesel fuel in every ounce of gold.

Every living system requires a steady supply of high-quality energy to maintain homeostasis. I may have posted the links to tie the emergence of self-replicating entropy maximizers back to the spontaneous emergence of order in any non-equilibrium thermodynamic system. It goes a long way to explaining pretty much everything. Empires are entropy maximization systems, but their entropy maximization is not necessarily your entropy maximization. Entropy maximizer is just another word for self-optimizing resource-extraction asset-stripping engine, a self-organizing adaptive system. The four mechanisms of adaptation in living systems are genetics, epigenetics, gene regulation and intelligence. The machines use various forms of artificial intelligence.

I think that someone (possibly me) posted a brilliant article a few months ago about corporations being the first artificial intelligences, a sort of crowd-sourced intelligence for optimizing cashflow. Vance Packard wrote many good books, and one of them was The Pyramid Climbers. It has been too long since I read it to remember if he identified sociopaths and psychopaths as the ones who would climb fastest to hold the reins of power. Another of his excellent books is The Hidden Persuaders. Again, too far back in time to remember if he included Bernays in the bibliography. Persuasion is just another tool for entropy maximization, as are sugar, alcohol, slavery, whaling, opium smuggling, petroleum, and all of the other businesses of empire. Or as they call it, manufactured consent. Just make sure that your consent is not manufactured by them.

If blockchain is a mechanism for scaling trust, it will turn out to be very important. One of the many problems with psychopaths and sociopaths is that they can't always be trusted.

WinterMarch 29, 2018 6:45 AM

"If blockchain is a mechanism for scaling trust, it will turn out to be very important. One of the many problems with psychopaths and sociopaths is that they can't always be trusted."

I should have added the [SARCASM] tags. ;-)
Obviously, I agree. However, those who are against money are the likes of the churches. They are not opposed to money for the sake of the people, but because money also makes free.

However, I disagree about psychopaths. They are like sharks and can never be trusted.

Leave a comment

Allowed HTML: <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre>

Photo of Bruce Schneier by Per Ervland.

Schneier on Security is a personal website. Opinions expressed are not necessarily those of IBM Resilient.