CoinJoin: Bitcoin privacy for the real world

[gmaxwell]

Note that attackers don't actually have to spend that input if they disrupt the protocol. They can use the same one over and over, even many times simultaneously.

You're missing my point.  If you detect them disrupting the protocol the participants blacklist that input and never participate with it again (ideally the protocol would be such that they got proof of the disruption that they could show to others). But since success consumes the input you don't have a problem with long term identity linking. Yes, simultaneous is a possible but even in the worst case a given input could only be used to jam each group of users once. If recovering from a jamming is just a few packet round trip times and signature operations to redo the mix, this isn't so bad.

In any case, I've probably given you enough of my thoughts on this. Go out and code. Practice trumps theory.  As I said in my initial post, I suspect that it might be better to just start out with very weak dos protection and then adapt to the actual threats rather than trying to predict all possible threats in advance. Unlike a global consensus system there is no great harm in evolving this technology.

[Natanael]

It isn't certain that you'd be able to tell WHICH input that the attacker used, at least not with my scheme where you hide who's using what input. Revealing who's using what input might not be optimal if a user want to use inputs already tied to himself AND some inputs that aren't already, and doesn't want the unlinked ones to become linked to him.

Also, it's hard to convince other that the attacker maliciously broke the scheme where none of the participants has any long-term pseudonym, thus it's hard to blacklist that one input. Also, a single input can STILL be used many times simultaneously, even if not many times in a row.

I don't have enough experience with programming, and absolutely not of crypto implementations, to be able to make a proper proof-of-concept of this, sorry. I'm hoping that somebody else *who does* will find this interesting enough to implement.

So far I'm thinking that my two-round version SMPC scheme with initial PoW before starting SMPC would be pretty decent, where you'd remember which pseudonyms that mixing has worked with in the past. Participants that don't supply PoW is ignored, and to stop a sybil attack where many nodes don't do PoW to try to make you calculate PoW for nothing you'd connect to multiple dozens of random nodes at once.
Edit: If the SMPC was given bad inputs, it would also reveal who it was that gave it the bad inputs (if it were to finish, but giving bad inputs + interupting the SMPC is just wasteful from an attacker's point of view).

And by the way, I'm one of those who wants the system to be as solid as possible in advance. Nobody deploys bad encryption algorithms and try to patch the algorithm as flaws is found. Not that I think that the other suggestions is bad, but I don't want people to get screwed over because somebody forgot to consider a simple attack that a little bit more analysis would have revealed and maybe shown how to stop.

[gmaxwell]

And by the way, I'm one of those who wants the system to be as solid as possible in advance. Nobody deploys bad encryption algorithms and try to patch the algorithm as flaws is found. Not that I think that the other suggestions is bad, but I don't want people to get screwed over because somebody forgot to consider a simple attack that a little bit more analysis would have revealed and maybe shown how to stop.

Dos attacks on systems which don't require flag day updates are categorically different from cryptographic breaks. I fear the approach you are advocating would result in us getting nothing at all. (but, I certainly would welcome it if someone wanted to actually work on it!)

[Natanael]

The risk of DoS in many of these cases could make the entire scheme unusable for as long as it's decentralized, as you can't really effectively ban the attacker. If the attacker can run 20x as many fake nodes as there are real nodes and abuse the scheme to only spend a trivial amount of computing power and bandwidth, while making the real users waste lots of it, then the system is trivially rendered unusable. Just throw a botnet at it and it's dead.

That's why I'm thinking hard on DoS prevention.

Edit: Also, regarding change addresses: You should split up your change in several parts. If everybody does that and thus generally also refers to multiple inputs for the transaction as a result, then correlation based on the BTC sums is much harder.

Edit: https://bitcointalk.org/index.php?topic=12751.msg315793#msg3157931 - So somebody else had the same basic idea over 2 years ago. Although my version (who originally was almost identical to his) now accounts for various types of possible attacks.

[genjix]

Hi,

I am claiming the bounty.

More info: https://bitcointalk.org/index.php?topic=282086

Source code: https://github.com/calafou/coinjoin

[ShadowOfHarbringer]

Hi,

I am claiming the bounty.

More info: https://bitcointalk.org/index.php?topic=282086

Source code: https://github.com/calafou/coinjoin

Wow, that was unexpectedly fast.

[maaku]

As far as I can tell, genjix's implementation is neither decentralized nor private, correct? The hard parts are still left to be done.

[TierNolan]

As far as I can tell, genjix's implementation is neither decentralized nor private, correct? The hard parts are still left to be done.

Right, the key is to make it a thing normal users do.  Central services can be shutdown.

[Peter Todd]

As far as I can tell, genjix's implementation is neither decentralized nor private, correct? The hard parts are still left to be done.

Also genjix should keep in mind this isn't a "one-time" bounty:

The bounty fund will pay out as funds are available according to the signers best judgment for completed work proposed in this thread that furthers the goal of making improved transaction privacy a practical reality for Bitcoin users.

[jtimon]

A simple scheme to enhance privacy without modifying the protocol.
I like it a lot.

By the way, there's a lot of confusion around zerocoin: http://themisescircle.org/blog/2013/08/22/the-problem-with-altcoins/
Is it a bitcoin upgrade? I doubt the overhead deserves it.
Is it a merged mined altchain with a coin fungible with btc? No way.
Will it become an altcoin? Probably.
Sorry, I don't want to move the thread to another direction, just wanted to note how less problematic this solution is.

[genjix]

Server:

• Powerless: has no real power. It's just a meeting point for participants to exchange data.
• Uninformed: has no special information except that which is public (and goes on the blockchain). There's no mapping between inputs and outputs because clients add their data in successive stages.
• Controls nothing: holds no funds. Funds and private keys are stored client side. Signing is done client side.
• Tor service. You can take down hidden services, but Silk Road and all the other services are still running around since 2+ years. Code is opensource so you can setup your own services. Users just paste the URL into the software. It's not really centralised. An analogy: BitcoinSpinner uses the BitcoinSpinner server, but in Electrum you choose your server and can setup your own.
• Extensible. Adding the p2p mechanism for exchanging data can easily be done. Replace the ServerInterface class methods in client.py with your own: https://github.com/calafou/coinjoin/blob/master/client.py Then the URL in the software becomes a shared secret. We designed the software with this in mind.

More technical info: http://sx.dyne.org/anontx

We've delivered usable software, simple for grandma (money goes in, money goes out), requires no blockchain or bitcoind, easy to install and trustless. We followed gmaxwell's instructions as our guidepoint and went further. And we delivered the product fast.

As far as I can tell, genjix's implementation is neither decentralized nor private, correct? The hard parts are still left to be done.

Right, the key is to make it a thing normal users do.  Central services can be shutdown.

You have the code. Setup your own server. It's all opensource.

FAQ:

Don't the users learn which inputs match up to which outputs?

In the simplest possible implementation where users meet up on IRC over tor or the like, yes they do. The next simplest implementation is where the users send their inputs and outputs to some meeting point server, and the server creates the transaction and asks people to sign it. The server learns the mapping, but no one else does, and the server still can't steal the coins.

note: Our implementation of the server is in stages and does not know the mapping so it's better even.

This is an extremely interesting idea.  Could you elaborate on how the Zerocoin transaction stages map to the stages of CoinJoin transaction creation?

For non-decenteralized coincoin, you simply pass around a transaction and sign it. It's a single sequence and an atomic transaction, you'd make two loops through the users, one to discover the inputs and outputs, and another to sign them. There really aren't stages to it.

...

As I said above, I generally think the non-decenteralized versions of these transactions will be implemented and commonly used first, simply because they're so much less work to do.

note: we do a 4 step process where the outputs and inputs are loaded separately, so the server doesn't know the mapping between them

I think adding a rendezvous mechanism to the P2P network makes sense. It's already a broadcast network after all. So perhaps the right design is not to try and do absolutely everything over the existing P2P network but rather allow people to announce rendezvous points (Tor hidden services?) over the broadcast channel and then allow nodes to set announcement filters like they set Bloom filters today. If you are an SPV/leaf node on the network you wouldn't hear announcements until you request them. Other nodes would relay them all.

[Natanael]

Why have servers at all? With I2P it would also be really easy to use DHT to set things up. Instead of a unique URL you could have a unique random string of any kind. Or even fully random peer selection.

[domob]

Take a look also here: https://bitcointalk.org/index.php?topic=200952.0  I think this is a similar concept, which is currently being worked on already (and I think even a test-net some-what-working version already exists).

This seemingly got lost.  Can anyone explain what the difference of the proposed scheme here is to what seems to be already implemented?

[gmaxwell]

Uh. Does someone have a bug to report for a tool from this thread?  (If you want you can report to me in pgp email anonymously.)

[Hawkix]

Hmm. Novel idea to mix coins into mining pool fee. Untraceable.

Seriously, there is a chance ASICMINER will help the poor soul(s).

[marcus_of_augustus]

Hi,

I am claiming the bounty.

More info: https://bitcointalk.org/index.php?topic=282086

Source code: https://github.com/calafou/coinjoin

Good start ... even the most massive of constructions begin with a single stake in the ground.

[CIYAM]

lol ... 200btc fees!

Shit - I thought I had the record for paying the most fees ever (due to creating a raw tx when way too tired).

I hope they can get that back (in my case I got most of it back).

[phelix]

Take a look also here: https://bitcointalk.org/index.php?topic=200952.0  I think this is a similar concept, which is currently being worked on already (and I think even a test-net some-what-working version already exists).

This seemingly got lost.  Can anyone explain what the difference of the proposed scheme here is to what seems to be already implemented?

Interesting...  would like to hear an opinion, too. (PMed Tom)

[Tom Scholl]

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.

[jdillon]

I'd like the administrators of this bounty to make clear some conditions for a large portion of the reward to be given:

• Testing - It has been rumored that the recent 200BTC fee transaction was the result of a failed CoinJoin transaction. Regardless of whether or not that is true, unittests and good coding practices should be taken into account.
• # of users - Take into account the # of potential users. Solutions applicable for a larger % of the total Bitcoin userbase are much more important than solutions not so widely applicable. Solutions that can be used 'by default' are far more valuable than ones that can-not.
  
• Licensing - Part of being widely applicable is the license of the software. I am in RMS's camp here, and while normally it makes sense to use restrictive open-source licenses in a tit-for-tat scenario, like him I too believe that sometimes getting the idea as widely used as possible is the right approach. Note that RMS has specifically said this in relation to Bitcoin's MIT license. Implementations should use licenses no more restrictive than LGPL.
  

As the largest individual contributor to date I hope my words are taken seriously.

Yes, I am writing this in response to Amir's proof-of-concept, which is nice to see happen quickly for people to play with, but to see it reported in Bitcoin Magazine already as "and today, two Bitcoin developers in Spain have come up with a solution." very much bothers me given how far it is from a complete solution.

For one thing, the code has rather frightening constructs such as:

call("sx rawscript [ %s ] [ %s ] | sx set-input txfile.tx %s > signed-tx" % (signature, pubkey, input_index))

I would not in the least bit be surprised if there is either a shell exploit already present, or there will be one in the future. In addition there is no license for the code, and it depends on sx/libbitcoin with are AGPL licensed.

tl;dr: I would be happy to see Amir and co receive a token BTC for their efforts, but they have to put a lot more work in for what they have done to be worth more than that.