Decentralised crime fighting using private set intersection protocols

[Peter Todd]

Once it becomes relatively easy to verify whether a Bitcoin was stolen or not, legal pressure will form on exchanges and merchants to not accept them. In most countries, knowingly handling stolen goods is a crime. So step by step, we will get those blacklists in one form or another. And it is better to get them sooner and in a way we can shape - than to passively watch them appear.

(emphasis mine)

If you want your Bitcoins to remain fungible, not just not, but also in the future when a crime is detected long after it was committed you are better off ensuring it isn't possible to know where they came from.

I'm reminded a bit of John Dillon's pull request, particularly the replies by Mark Karpeles (MtGox) and Gavin Andresen. Neither sees anonymity as valuable or something the Foundation should push for, particularly Mark, yet if you receive Bitcoins that you know are anonymous and/or know you can spend anonymously you have a very solid guarantee that you will be able to spend them later without having to worry that a theft may be discovered after the fact, retroactively causing them to be blacklisted.

If Bitcoin wants to be the electronic cash of the internet, it has to be possible to break the inherent lack of anonymity the blockchain implies, or a Bitcoin will never be as fungible as a dollar bill.

[1713572207]

1713572207

[1713572207]

1713572207

[Hermel]

or a Bitcoin will never be as fungible as a dollar bill.

A dollar bill is not as fungible as you think. All bills are numbered. There are blacklists of bills (e.g stolen from a bank heist). When you are detected giving such a blacklisted bill to the bank, you will be asked a few questions, but the bill won't loose its value. Same could happen for blacklisted Bitcoins: as Mike and others have described, they could get white-listed again if you are willing to identify yourself and can make plausible that you are not connected to the reason for their blacklisting (e.g. by showing a receipt that says where you got them from).

[Peter Todd]

or a Bitcoin will never be as fungible as a dollar bill.

A dollar bill is not as fungible as you think. All bills are numbered. There are blacklists of bills (e.g stolen from a bank heist). When you are detected giving such a blacklisted bill to the bank, you will be asked a few questions, but the bill won't loose its value. Same could happen for blacklisted Bitcoins: as Mike and others have described, they could get white-listed again if you are willing to identify yourself and can make plausible that you are not connected to the reason for their blacklisting (e.g. by showing a receipt that says where you got them from).

Yeah, coins are closer, but there are even efforts to have every individual coin serialized.

Right now the serial numbers on dollar bills aren't too much of a worry but there are a lot of efforts underway to incorporate bill scanners into ATM's and even cash registers (with RFID) combined with massive databases to track the movement of every last bill. It might not be many more years where even if you could pay cash, if you did so at most places a RFID scanner in the till would cause an alarm had your bill come from a blacklisted transaction.

Bitcoin doesn't have to go this route if we don't want it too. Provably anonymous trust free mixing is possible among many other solutions: https://bitcointalk.org/index.php?topic=172047.msg1790026#msg1790026 It's actually possible for every single transaction you make to participate in a trust-free mix, and doing so is actually a bit cheaper because making multiple payments in one transaction costs less in transaction fees than doing one payment per transaction.

[TalkingAntColony]

Can someone explain to me how taint would be calculated?

Say we have three inputs:

Code:

In1 - 1 BTC
In2 - 1 BTC from output marked as tainted
In3 - 2 BTC

And three outputs:

Code:

Out1 - 2 BTC
Out2 - 1.5 BTC

Tx fee (leftover): 0.5 BTC

So we now have three new outputs, Out1, Out2, and Coinbase of the block which contains the Tx and thus gets the Tx fee.

What is the "taint level" of each output? I haven't seen a demonstration of a way to calculate it that isn't easily exploitable.

[dillpicklechips]

If Bitcoin is widely adopted I think that many people will opt to use tools that increase their privacy. I fear blockchain analyzing tools will increase removing peoples privacy. Imagine going to a store and buying a pop and the store computer has software installed by the worker that instantly shows I'm likely rich and also like to purchase embarrassing item A. Perhaps he's trying to decide who to rob. Or even corrupt states around the world monitoring it's citizens. If tools, such as zerocoin, or methods of mixing coins become popular to protect our right of privacy, would that make your scheme pretty much useless?

[Hermel]

Can someone explain to me how taint would be calculated?

Say we have three inputs:

Code:

In1 - 1 BTC
In2 - 1 BTC from output marked as tainted
In3 - 2 BTC

And three outputs:

Code:

Out1 - 2 BTC
Out2 - 1.5 BTC

Tx fee (leftover): 0.5 BTC

So we now have three new outputs, Out1, Out2, and Coinbase of the block which contains the Tx and thus gets the Tx fee.

What is the "taint level" of each output? I haven't seen a demonstration of a way to calculate it that isn't easily exploitable.

Excellent question. I don't think there is one single "right" answer that always works. Depending on the severity of the crime, the size of the transaction, the time passed since the crime, and many other factors people will apply different methods. One might even try to follow the transaction fee, as someone might use that to launder his Bitcoins by issuing a transaction whose fee is 100% and mining the block himself.

Here are a number of approaches:

Full taint: every output of a transaction involving tainted coins gets fully tainted as well. One might even want to taint the transaction fee the miner gets from the theft-transaction. This is the most radical approach and only makes sense when trying to track down a once-in-a-decade scale crime. Applied to your example, all outputs as well as the transaction fee would be considered tainted.

Diluted taint: works like dirty water. You start with 100% dirty coins and dilute them as they get combined with clean coins. In your example, the transaction's outputs would be 25% dirty, including the transaction fee. Combined with the other say 99 BTC mined in that block, the miner would get 1% dirty coins. Note that in this case it is reasonable to have a closer look at the miner since a 0.5 BTC transaction fee is somewhat suspicious. If the acceptable dirtiness of a coin is 0.1%, then it takes 999 clean BTC to launder 1 dirty BTC.

Compact taint: here, we try to keep the tainted coins together by applying some more or less random rules to artificially separate the tainted coins from the rest. In your example, one could say that Out2 will take the tainted coin (consisting of 1 dirty and 0.5 clean BTC). The rule behind this is that the tainted coins are always assigned to the output such that dilution is (locally) minimized. So normally, it would go to the smalles output that is at least as large as the amount of tainted coins. You might be bothered by this rule being somewhat unpredictable and random. However, the goal here is not to have a philosophically pure solution, but to find a pragmatist rule to say who is responsible to clean the mess. In your example, it would give the recipient of the 1.5 BTC the responsibility to get the Bitcoins into a clean state again (e.g. by helping to track down the thief). It might not be entirely fair, but effective. It's a little like the rule "the last one leaving the building locks the doors", which also works even though it does not assign that piece of work very fairly considering that it might always be the same one leaving last.

There might be other mechanisms to handle taint. I don't think it is necessary to stick to a specific one. Each blacklist-providing service might apply their own heuristics, depending on the type of crime they are after. Unlike Mike, I don't think we need an elaborate technical solution here. A simple API like "how tainted is address X" is ok in most cases, even though it reveals the fact that someone is interested in that address to the provider. The provider will notice that anyway when a transaction involving that address appears in the block chain. The "private set intersection" proponents have found a very sophisticated hammer, and now they are desperately looking for a nail.

[townf]

Tainted money schemes are completely, idiotically misguided.

This particular idea is an attempt to find the "fairest" way to oppress people. This is totally stupid.

If you use your mind for 5 minutes and follow any tainted money scheme, no matter how "decentralized" or "fair" you think it is, down every path it could possibly take, you will always end up in a place of oppression and control.

Public consensus on any issue, including what dirty money is, is heavily manipulated. Just watch the "news".

When you have a media cartel like we have, public consensus is what they tell you public consensus is, not what it really is. Actual events are what they tell you actual events are, not what they really are. Things the media cartel omits, didn't happen, even though they really did. Issues whose importance is artificially inflated aren't really very important compared to issues that are not reported.

This is the unavoidable, indisputable reality in an environment where the mainstream media outlets are a non-competitive cartel, which is the environment most people trust to get their information from this very day.

Are we going to use misinformation and propaganda to taint people's money?

Furthermore, any other system you can think of to label money as dirty will be manipulated. It already is.

[TalkingAntColony]

Hermel thanks for the reply. I have some concerns with the methods you described:

Full taint:
 - Thief cycles stolen coins through mixer and/or e-wallet before tainting services mark the output(s). Now many people have tainted coins.
 - Thief sends small Tx with fee every block for a while, tainting the Coinbase. Mining pools would distribute tainted coins to participants.

Diluted taint:
 - Assume 0.1% acceptable taint level
 - Thief makes 1000 even bets with SatoshiDice 0.09% which pays out 999.429x the bet
 - At the end, he has 98.1% of original value on average with less than 0.1% taint to all his coins, because SD pays winnings from different coins.
 - Mixers/e-wallets could also dilute the taint enough

Compact taint:
 - Thief creates Tx with 51% of coins to random address and 50% back to him at new address.
 - He now has 50% of the stolen coins taint free

There are ways to mitigate these exploits, but they require compliance from services. For example, force e-wallets to broadcast a Tx for internal transactions and put coin control methods in place that don't mix one account's coins with another. Most major services would have to run blacklists so they could ignore tainted coins sent to them. Basically, non-fungibility requires changes to much of the way bitcoin services currently operate.

Now, we can still use the concept of taint without burdening users. That is, law enforcement can analyze the blockchain after the theft in the same way taint is calculated, but users/services don't have to implement taint avoiding rules. The downside is of course eliminating the possibility of preventing the thief from spending coins in certain ways.

If taint becomes prominent, there will basically be a short window of opportunity for thieves not using the aforementioned exploits or other obfuscation methods. If the time between the theft and the marking as tainted is longer than an hour, then the thief can successfully send someone a 6-confirmation Tx without them knowing the coins will soon be marked. Anonymous P2P cryptocurrency exchanges could be a major victim of this.

[Hermel]

Compact taint:
 - Thief creates Tx with 51% of coins to random address and 50% back to him at new address.
 - He now has 50% of the stolen coins taint free

If you have 1 tainted BTC and split it into 0.49 BTC and 0.51 BTC, then both these outputs will be considered tainted, and not just the bigger one. But I did not mention that.

Now, we can still use the concept of taint without burdening users. That is, law enforcement can analyze the blockchain after the theft in the same way taint is calculated, but users/services don't have to implement taint avoiding rules. The downside is of course eliminating the possibility of preventing the thief from spending coins in certain ways.

If taint becomes prominent, there will basically be a short window of opportunity for thieves not using the aforementioned exploits or other obfuscation methods. If the time between the theft and the marking as tainted is longer than an hour, then the thief can successfully send someone a 6-confirmation Tx without them knowing the coins will soon be marked. Anonymous P2P cryptocurrency exchanges could be a major victim of this.

Taint should always be looked at with reason. If you steal a car and then sell it to someone before the car got reported as stolen, the police won't punish the buyer either. Of course, they will question him to find out how he got the car, but as long as he can make plausible that he is innocent, he won't get into trouble.

Generally, I think a lot of the "reasons" people bring forward here against taint are only valid when thinking in absolutes. But the reality is more differentiated. Sherlock Holmes combines a multitude of hints to catch the criminal. Taint analysis can provide leads, but it cannot automagically bring justice.

[TalkingAntColony]

I have no problem with people using taint analysis techniques on the blockchain to investigate. I do have a problem with taint-marked coins being in any way less spendable than unmarked. I think encouraging people to check public taint-lists before accepting payment is bad for the network. It is in effect guilty-until-proven-innocent.

Nonetheless I remain skeptical of taint analysis until we have seen it in practice. I would like to see someone set up a taint test service which allows one to mark an output as tainted and compare what various taint calculating algorithms say about subsequent outputs. This would allow people to test out exploits and use cases to see if such analysis is worthwhile or not. I know Blockchain.info has a taint analysis tool but it's address-based and I'm not sure how it's calculate.

[CasinoBit]

"A pack of wolves and a flock of sheep voting on what's for dinner" is the phrase that immediately springs to mind. You forget how easily these systems are exploited, and assume that ordinary human beings are clinically rational automatons.

Exactly this, look at the founding fathers and what America is currently is and then think about what will happen to your decentralized crime fighting about 50 years, it will be a mere tool to enforce a system of modern imperialism upon the free.

[meowmeowbrowncow]

This is good shit, Mike.


As a supplement to law and order this is a good idea.  I think it has it's place.  The concept of Nexus to define scope is good.


And I would like to see this realized.  Society's collective apathy let's far too many of ill repute continue to operate without repercussions.


If something like this can be designed to not be gamed by a rogue or powerful entity, and is voluntary - then why not?

[bytemaster]

The problem with this idea is that it does not address the real problem, crime, but instead attempts to provide a decentralized solution to an existing tactic (following the money).    Unfortunately, following the money is a terrible and ineffective tactic that has tremendous negative externalities.

I have been playing with various ideas on providing decentralized 'law enforcement' with the ultimate goal being that it should, in theory, be able to also prevent 'legal plunder' and 'official crime'.

The problem is how do we define 'crime' in a universal / decentralized manner that 'no one can disagree with'.   It seems to me that the only standard that anyone can be held to is 'their own standard' and if someone were to break their 'own law' as judged by 'their own court' that it indisputable that they are in the wrong and owe RESTITUTION to someone.    What is needed is the following:

1) A crypto-graphic secure / unique identity.
2) A set of laws 'independent' laws that are 'brand name' and widely known.  The market would provide these contracts.
3) An individual would select the subset of these laws they agree to follow and sign them with their ID.
    - this subset need not be public, but can be presented only to those you do business with.
4) An individual would select a subset of trusted courts to be judged under.
5) Before doing business with an individual, validate that they have agreed to a compatible subset of laws  AND that they have no judgements against them by their own courts.
6) Shun anyone who has unsatisfied judgments against them.
7) Charge people without a trusted ID more than those who validate their ID.

I started to put my ideas together on a new website: the-iland.net 

The iLand is a new free market solution that aims to secure life, liberty, and property for its members.

The key ingredients to this solution include:

• Individuals publicly commit to abide by their own standard of law.
• Individuals publicly commit to arbitrate via one or more courts of their own choosing.
• Individuals deposit a security bond with one or more trusted agencies.
• Individuals share the burden of injustice by contributing to a common fund.
• Individuals shun anyone whom fails to arbitrate or abide by the outcome.

If such a system could gain wide-spread adoption (read details on my website) then ultimately peer pressure and 'self interest' would eliminate anti-social behavior by government agents.  Public judgements could be issued against cops, IRS agents, etc and these people will end up having to change their ways.  Politicians would have to explain why they will not abide by the same laws as the rest of us or why they will not appear for arbitration in a 'fair court'. 

[townf]

"A pack of wolves and a flock of sheep voting on what's for dinner" is the phrase that immediately springs to mind. You forget how easily these systems are exploited, and assume that ordinary human beings are clinically rational automatons.

Exactly this, look at the founding fathers and what America is currently is and then think about what will happen to your decentralized crime fighting about 50 years, it will be a mere tool to enforce a system of modern imperialism upon the free.

It's unavoidable.

There's no way to taint money accurately. There's no way to do it securely. There's no way to do it impartially. There's no way to keep it out of hands that will ultimately use it to suit themselves. Quit trying already.

Money itself should not become unspendable anyway. That's a harmful solution. Fight crime the real way instead of being a control freak and grafting a tumor onto the monetary system. What's going to happen after a long period of time when half the money is tainted?

A criminal steals a bunch of bitcoins and then all of a sudden he can't spend them? Big effing whoop, he doesn't lose anything. And this is pretty much the best case scenario. It's hilarious.

It's a total waste of time. A control freak's fantasy toy. It's a boondoggle. It will cause 100 times more problems than it will fix. It will be controlled by people and those people will use it for their own purposes. Forget about it.

[townf]

I have been playing with various ideas on providing decentralized 'law enforcement' with the ultimate goal being that it should, in theory, be able to also prevent 'legal plunder' and 'official crime'.

You won't be able to do this. This is a subjective matter, not an objective problem that a computer can be programmed to get "right" every time.

[Stampbit]

I dont follow, is mike trying to get a government job?

[hazek]

The problem with this idea is that it does not address the real problem, crime, but instead attempts to provide a decentralized solution to an existing tactic (following the money).    Unfortunately, following the money is a terrible and ineffective tactic that has tremendous negative externalities.

I couldn't agree more as I have already pointed out in this thread. Following the money, especially following bitcoins is untenable.

I have been playing with various ideas on providing decentralized 'law enforcement' with the ultimate goal being that it should, in theory, be able to also prevent 'legal plunder' and 'official crime'.

The problem is how do we define 'crime' in a universal / decentralized manner that 'no one can disagree with'.   It seems to me that the only standard that anyone can be held to is 'their own standard' and if someone were to break their 'own law' as judged by 'their own court' that it indisputable that they are in the wrong and owe RESTITUTION to someone.    What is needed is the following:

1) A crypto-graphic secure / unique identity.
2) A set of laws 'independent' laws that are 'brand name' and widely known.  The market would provide these contracts.
3) An individual would select the subset of these laws they agree to follow and sign them with their ID.
    - this subset need not be public, but can be presented only to those you do business with.
4) An individual would select a subset of trusted courts to be judged under.
5) Before doing business with an individual, validate that they have agreed to a compatible subset of laws  AND that they have no judgements against them by their own courts.
6) Shun anyone who has unsatisfied judgments against them.
7) Charge people without a trusted ID more than those who validate their ID.

I started to put my ideas together on a new website: the-iland.net 

The iLand is a new free market solution that aims to secure life, liberty, and property for its members.

The key ingredients to this solution include:

• Individuals publicly commit to abide by their own standard of law.
• Individuals publicly commit to arbitrate via one or more courts of their own choosing.
• Individuals deposit a security bond with one or more trusted agencies.
• Individuals share the burden of injustice by contributing to a common fund.
• Individuals shun anyone whom fails to arbitrate or abide by the outcome.

If such a system could gain wide-spread adoption (read details on my website) then ultimately peer pressure and 'self interest' would eliminate anti-social behavior by government agents.  Public judgements could be issued against cops, IRS agents, etc and these people will end up having to change their ways.  Politicians would have to explain why they will not abide by the same laws as the rest of us or why they will not appear for arbitration in a 'fair court'. 

Now this is starting to sound a lot like what I envision is the solution. I will definitely check your site although I'm still clueless how once can create a secure unique and yet anonymous digital ID which is essential for any type of such a solution.

[Carlton Banks]

I have been playing with various ideas on providing decentralized 'law enforcement' with the ultimate goal being that it should, in theory, be able to also prevent 'legal plunder' and 'official crime'.

You won't be able to do this. This is a subjective matter, not an objective problem that a computer can be programmed to get "right" every time.

with just one exception: provable BTC theft. In spite of this, I think the personal responsibility route is the right one. I've given it some careful thought, and there's no way around how it damages Bitcoin's acceptance. You just wouldn't accept BTC if it could be labelled tainted at any given time in the future, it's pretty much taking the uncertainties of future chargebacks when using electronic payment cards and giving Bitcoin it's own (worse) version of the problem.

It damages Bitcoin's properties as a medium of exchange, hence, no.

[bytemaster]

I have been playing with various ideas on providing decentralized 'law enforcement' with the ultimate goal being that it should, in theory, be able to also prevent 'legal plunder' and 'official crime'.

You won't be able to do this. This is a subjective matter, not an objective problem that a computer can be programmed to get "right" every time.

Who said anything about a computer doing it?   Bitcoin doesn't solve banking/money on its own, it is just a tool for people to use.   My system would only be software tools to facilitate the creation of:

  Secure Identity that can be used to sign 'open contracts' or 'commitments' to follow well published and accepted 'laws'.
  Software to quickly validate in seconds whether the person you are about to transact with has already signed a minimum subset of laws and a compatible arbitration path.
  Software to do a 'background check' for published arbitration decisions that have not been followed.
  Software to quickly verify surety deposit for an individual.
  A website to publish / publicly shame individuals whom fail to agree to ANY arbitration path or whom have to followed the result.

In theory the purpose of this software is to allow 'instant' background/credit checks on the individuals you associate with.  It would be a tool to allow honest individuals to recognize one another at a distance and have a high degree of confidence in their transactions. 

   There is nothing for the computer to 'get right' every single time, the computer is merely indexing / searching / comparing digital signatures and web-of-trust graphs.   Ultimately this is enforced by people choosing to trust one or more surety funds, arbitration courts, and insurance funds.

[townf]

bytemaster this is different than what im talking about which is the btc network tainting money that was somehow deemed stolen, used in commerce for "contraband", being the victim of abuse of the term "terror", or for whatever future arbitrary politically correct reason, etc, making it unspendable and extinguished no matter who owns it at the time, decided by what algorithm or person it doesn't matter, it's a bad idea IMO.

It sounds like you're talking about something like bitcoin-otc, except not with trading integrity reputation, but whatever law abiding reputation people choose to care about in their counterparty. People already do this face to face or by word of mouth with local transactions, so i don't really have a problem with it. Your thing might be subject to the same abuses like slander, fraud, pseudonyms, etc that word of mouth or bitcoin-otc might be prone to, just saying. Sounds like you got a lot of thought in it though. Sounds pretty useful actually