Couldn't find an existing thread, and I wanted to post my experience with the recently opened BTC Store (btcstore.eu)...

They are based in Finland and sell Bitcoin merchandise, physical bitcoins, Raspberry Pis etc. They ship to other European countries but it costs €15 for orders of up to €50 At least VAT is included.

I ordered the bitcoin cufflinks and a bitcoin t-shirt, delivered to the UK. Website ordering and bitcoin payment went smoothly, and the goods arrived really quickly after 3 days 5 days (correction). I haven't had a chance to wear them yet, but they look really nice - good job, thanks!

I've realised that bitprivacy owes a lot to the original CoinJoin concept, and updated the github page appropriately.

When/if I get time I'll work on making it "just work".

I hereby claim part of this bounty for my work on bitprivacy.

It is MIT licensed, and furthers the goal of making improved transaction privacy a practical reality for Bitcoin users. It might help if you clarify whether funds can be paid for work done before the setting up of this bounty. I'm assuming solutions don't need to be called coinjoin, if this isn't the case you should say.

It's great to see so many people contribute to this bounty.

If you want to help bitprivacy directly, you could try it out and post in the thread.

Thanks for the heads-up of this thread.

I spent a month working on a peer-to-peer Bitcoin privacy solution back in May, it's called BitPrivacy.

It's aim is a fully decentralized solution providing strong privacy, and as such it is more ambitious and complicated than genjix's CoinJoin.

A decentralized solution spreads the legal risk over everyone running nodes - I'd rather be a developer of privacy software than someone running a privacy service. I spent a couple of days reading the laws of my country (UK), and they are surprisingly broad.

Technically the plan is to have a peer-to-peer network over Tor. Privacy is achieved by everyone writing their inputs to the network; when all are supplied they make a new Tor connection & write their outputs.  

BitPrivacy version 0.2 featured:
- Bitcoinj-based
- Arbitrary N-party transaction schemes
- Blind signatures via the Bouncy Castle library
- All communication over a DHT, via the mature TomP2P library
- Aggressive trading strategy - it tries to transact with everyone simultaneously

Some things I didn't get round to:
- Peer discovery & running a well-known node - you have to enter an IP to connect to
- Adding a command-line switch for ProdNet (an easy code change)
- Tor

You can download the jar file right now, and join some testnet coins between N wallets. There is a thorough description of the protocol at DETAILS.md, and the threat model and defenses are in THREATS.md. The code quality is rough, but it does have some test cases. Forks, code-plundering, etc all welcome!

I actually put in a grant request to the Foundation for this. I don't think I'll ever get it, at least it gave me an incentive to document everything.

I've been thinking a lot about what privacy features are missing, and it's a lot more than I thought before. There's several months of work here.

So, if any developers are interested in things like fidelity bonds, Tor integration, automatic wallet "coin-joining" strategies, or integration with MultiBit, then please get in touch.

I've written about the threat model & defences on github in THREATS.md.

Widely used personal wallets with built in p2p mixers should have plenty of clean money and people mixing. If mixing is legit, I don't see why that wouldn't happen - everyone wants privacy if the cost is low.

Maybe people wouldn't cooperate for no reward as you say. So do you think a reward-based scheme might work? Remember that with the MPC algorithm the authority won't actually learn anything about you, only about the victim of the trace.

Oops, yes. I look forward to reading your research.

Thanks for all the support in this thread Mike.

I'll delve briefly into the political debate myself:

Once there's a significant number of Bitcoin businesses using tax evasion as their competitive edge, the authorities are going to get nasty pretty quick. Where do people see this going? So far I've really only seen 2 responses:

• Go black-market. Sure, you can. But if at least part of the Bitcoin market is legitimate, Bitcoin can have a much greater influence and utility.
• Some form of tainting. If we're really lucky this might be something like what Mike's proposed in the other thread. I suspect what we'll end up with will be much more draconian though. You can still have your black-market at the same time as this.

EDIT: This sounds pessimistic, but I'm actually really enthusiastic about Bitcoin's long-term prospects, and of course have some coins myself. I just think it's good to think about the bigger problems when there's actually a lot of stuff you can do to combat it.

Thanks for your thoughts everyone.

I probably should have done a bit more reading and led with the MPC solution, which doesn't leak your private data to the authority at all. If used over Tor (ouch, slow!) it fully addresses the concerns about unmixing being voluntary.

Basically multi-party computation (MPC) is a magic box for lots of people combining their secret data and calculating some aggregate values, without anyone knowing anyone else's data. The aggregate values can be shown only to certain people.

The theory says that there's an MPC algorithm for every problem in NP, the only question is how fast it is (these algorithms can be prohibitively slow). There's a ton of research being done here, and it's getting faster every day. The paper Mike referenced had working code for doing private set intersection on an Android phone in a reasonable amount of time, and I also found a later paper claiming to have beaten that performance using a custom PSI protocol.

I think this problem needs MPC signature verification as well as set intersection - you want every (input, output) pair to be doubly signed, otherwise malicious colluding adversaries can wholly implicate non-participating parties.

On quotas, I was imagining quotas would be an incentive for greater transparency; people have bigger quotas for more transparent/democratic organizations.

Payment/reward for financial history is really interesting. There might be some gaming attacks to be done for profit. I wonder if a contract could be devised such that if someone pays the asking price for some output in a tx, they'd be guaranteed to get back a signed input in the same tx.

I see what you're saying. But if you assume the criminals don't all know each other and group together (which they might well do) the statistics do imply more cooperating people is good:

Say we have 900 people who would cooperate, and 1 criminal, and 99 non coops.
Now if only 100 cooperating people use mixing,
the total mix pool is 100 coops + 100 non coops.
If we're doing 10 person mixes, on average we'll get 5 coops and 5 non coops in a mix. Tracing an individual criminal is now pretty hard - you'll get 5 leads per investigation.
But if 900 cooperating people use mixing, the total mix pool is 900 coops + 100 non coops, and on average there'll be only one lead per investigation.

The whole public-ledger setup of Bitcoin can lead to a technological arms race on mixing/tainting. Of course, tainting only works if it's done on an international level as otherwise there'll be a p2p market for swapping US-tainted coins for Russian-tainted coins.

Anyway, sounds like no-one is really interested in this. I suspected as such but I thought I'd throw it out there anyway.

EDIT: Having thought about coin-swapping a bit more, it's a pretty complicated problem with a lot of attacks so I don't think it would immediately kill off more local tainting.

Suppose everyone routinely mixes every coin they receive. A haven for money-launderers? Not if we don't want it to be...

TL;DR If a large enough % of people in a mix decide to secretly report their (input, output) mix pair to a chosen AML organisation, the organization can trace dirty money going through the mix. This can all be done automatically. This might lead to AML organizations encouraging model citizens to use mixers routinely to keep that % high.

Protocol

Whenever you make a payment to anyone with a freshly mixed coin, you generate a new Bitcoin address as a "notify" address for that coin. You sign the notify address with the address key you're paying from, and encrypt the result with Interpol's well-known public key (or it might be the UN, Bitcoin Foundation, etc).
You give this encrypted "notify" data to the person you've just paid.
If you haven't mixed your coin, you can forward any notify data you received with the coin to whoever you give your coin to, or you can decide you want to block the unmix and just don't pass on any data.

Now when Interpol sees the known proceeds of crime, address X, go into a mix, they wait for the mix outputs to hit well-known businesses like exchanges or Mike Hearn's whitelists in "Decentralized crime fighting". They talk with the exchange and ask for some help tracing address X. The exchange gives them the notify data they have for each coin coming from address X.
Then Interpol makes a standard low-value Bitcoin payment (eg min tx fee) to each notify address, from their well-known Bitcoin address corresponding to their public key.

Your wallet is watching your notify address, and can automatically take some action when it detects the payment from Interpol's address.
You'll have set your wallet to only let Interpol do so many unmixes per year, so they can't abuse the system. If they're within quota, your wallet makes a Tor connection to Interpol's server and securely submits your mix (input, output) pair, with signatures for both the mix input key and mix output key.

So every person who decides to help out Interpol sends them part of the information needed to reverse the mix, enabling them to follow the criminal's money and catch him when he spends it with a well-known business/whitelist server.

http://bitprivacy.org/files/unmixing.png

If it was a 100-person mix, and 90% decide to help Interpol, this system narrows their leads to 10 outputs. Interpol might actively encourage model citizens to routinely mix their coins, to push that percentage higher.

Adversaries
There can be any number of adversaries in a mix.
Adversaries can just be people who don't want to help that AML organization, or they may be malicious and colluding with each other and the criminal in order to implicate an honest participant.
By using the AML organization as a trusted 3rd party this algorithm is resilient to adversaries.

Why use a low-value Bitcoin transaction for notification, shouldn't this use a proper p2p messaging system like Bitmessage?
You could, but every wallet owner would have to sync up with this other messaging system just to help out with AML - I don't think the incentive is really there, hence this lightweight protocol.
Also as Bitcoin transactions are public, everyone can see exactly how much unmixing the AML organization is trying to do, and could adjust their unmix quota for them accordingly.

This tells the AML organization where my coins came from! Isn't there a better way?
Maybe. Here's what I've thought about so far:

• Broken Probabilistic Technique
  Instead of submitting your mix input/output pair to the authority, you could submit your input + a set of m outputs containing your actual output. This hides which your exact output was, and statistical analysis on the data could be able to narrow down the criminal to a few candidates. Repeat the process until you've got them.
  But if there are many malicious participants, they can now totally subvert the process, and completely implicate an innocent party. So we can't use this algorithm.
  
  
• Secure Multi-Party Computation
  You might be able to use MPC to identify the criminal without leaking private data - I don't know enough about this to say.
  

I'll have a go with an example:

Bob hears about Bitcoin from a man in a bar, who sells him ten dollars worth.
Later that day, Bob decides to gamble his Bitcoin on Satoshi Dice and wins big time!
The next day he's in the same bar, and that man sidles up to him, angling for a handout from his big win.
Bob is really creeped out by this - how did this man even know he'd been gambling?
He loses interest in Bitcoin and advises his friends to stay away from it.

You could provide this privacy with a centralised mixer like the one at blockchain.info, and they can store logs to keep the feds happy. But if you don't want to sacrifice decentralization, you end up aiming at full anonymity.

This is a good point, and it's certainly what the politicians will be thinking. I think what we'll see are coin tainting and government mandated blacklist checking. It's just so easy to implement with a public ledger it's inevitable. On the conference security panel, Peter Vessenes talks like Bitcoin tainting is here already.

When blacklists are commonplace, you can still have your anonymity, you just use a "clean coins only" mixer.

Excellent question.

If you don't use blinding, any random person could submit an output, and DOS the trade. But with blinding, the blinding server can verify that the blinded outputs came from trade members -IF the members sign the message with their peerId. But I didn't mention that, because I haven't implemented it yet. I will update the notes.

I've just tried it with maven 3 myself, and it worked for me (no special flags required). Did you do every step of these instructions? You have to download and build bitcoinj seperately because it isn't hosted in a maven repository:

Hmm. What version of maven (mvn --version)? I used maven 2 rather than 3.
If you're on maven 3, you might have to pass the -U flag to mvn. Can you try that?

That sounds a lot like Chaumian cash. Open-Transactions works like this. As far as I understand, you do have to trust the receipt issuers to redeem it back to bitcoins/gold/whatever, although the trust gets spread out between several issuers. See https://github.com/FellowTraveler/Open-Transactions/wiki/CENTRALIZED for how that works.

It's great to see people are keen for this  

I'd like to fix the privacy issues, and do a security review to check malicious peers couldn't exploit data parsing or validation issues to steal coins. It would be great if another pair of eyes could check the protocol for mistakes.

I've just written https://github.com/dustyneuron/bitprivacy/blob/master/DETAILS.md. It may be a bit too in-depth about the data layout, but it's certainly easier than looking at the code, and I can use it as a reference when I need to change things.

I'm building a p2p trustless Bitcoin privacy solution that operates like this - many thanks for the description, killerstorm!

Current status is testnet only, as there are various privacy-breaking attacks that I haven't countered yet. But it seems to work, and I was really happy to find this algorithm as implementing secure multi-party sorting didn't look easy.

Here's the thread, with source etc: https://bitcointalk.org/index.php?topic=200952

Version 0.2:

• Chaumian blind signatures for outputs (https://bitcointalk.org/index.php?topic=150681.0)
• New trading strategy to cope with unresponsive parties
• Fully peer-to-peer
• Lots of unit tests

It's still testnet only as there are some timing attacks and traffic analysis attacks possible, it doesn't yet cope with misbehaving parties, doesn't save trades to disk, etc, etc.

Download ready-to-go: http://bitprivacy.org/files/bitprivacy-0.2-jar-with-dependencies.jar
Source & instructions: https://github.com/dustyneuron/bitprivacy
Donation address in my sig