CoinJoin: Bitcoin privacy for the real world

[Crowex]

maaku's solution does not seem to work as it requires communication between the participants

No, the server can include this signed information in the message it sends to participants.

The solution is simple: each participants sign what outputs they want to see on the chain.

Are they signing a set of all outputs randomly mixed up? This wouldn't solve the problem.
Or are they signing their individual outputs? There is no anonymity now.

No participant signs the transaction unless they receive invoices separately signed by every single input which cumulatively add up to the transaction.

I can't see how this helps to solve the problem.

Cryptographic blinding is used to make sure that users can specify hidden outputs not subject to this check.

I'm not really sure what you're saying here. If you're talking about a blind signature protocol can you be more specific about how it can work in this case.

the example was a donation address, it would be difficult to imagine this changing for each donation

Google "bitcoin stealth address"

I didn't say that it wasn't possible to change the address for each donation. This could be done without stealth addresses. I just think that most people asking for donations will just put up an address and ask people to send coins to it.

[maaku]

They sign a list of their outputs, some of which are explicit, some of which are blinded. The blind signed outputs are separately checked (the server blind signed them without knowing what they were, so couldn't later skim them without detection). So each participant has a list of non-mixed outputs signed by their owners, and a list of blinded outputs signed by the server before it had a chance to do any funny business. Together these should add up to the entire transaction (modulo facilitator and miner fees).

[Murphant]

I am looking to compare different implementations of CoinJoin, but I don't feel like going through 20 pages. Would someone be considerate enough to list them here, or maybe in the original post?

[ajsubtronic]

where can i find a comparison of coinjoin? is there a website? 

[Amitabh S]

Is the bounty still open? I can see the funds are still there.

How do I cite CoinJoin?

[gaston909]

This is a great idea!

[themgp]

Hey all,

I've spent the last two/three months working on a CoinJoin implementation that I call Coinmux.  It is open source and mostly P2P / decentralized.

The source is in Ruby (JRuby) and on Github: https://github.com/michaelgpearce/coinmux.  The project home page has quite a bit of information so its worth reading through.

Here is an example transaction created with Coinmux for 3 participants: http://test.webbtc.com/tx/963d6a87c2f0c3e715d0550539ffa3fed0731abd4b3b081d52f29891592f400d.  (You'll notice some change address re-use due to this making my testing easier.)  The commands used were:

bin/coinmux --participants 3 --amount 0.0625 --output-address muTpTtZSGyEbH2xt47SS3J45XG4Dx5F9DE --change-address mwU8DyTw2fBQmyCDJNRyHBDXk7KUDJ7vEA
bin/coinmux -p 3 -a 0.0625 -o mynWtUyX3UmEfvbU6oESCuXWJXA2vjbJw8 -c mjfCi3t1jBsizt9MKtNDxpn3qdd73CRyhQ --data-store p2p?port=14142
bin/coinmux -p 3 -a 0.0625 -o mpexwCiUhDVNYEMWqzoLn8C4UkMdDdZCQo -c mjfCi3t1jBsizt9MKtNDxpn3qdd73CRyhQ --data-store p2p?port=14143

Its setup to use Testnet (i have not tried it on mainnet as its alpha software!).  It can be easily configured to use either a local filesystem to communicate or P2P over the Internet.  The filesystem communication is fairly robust while the P2P Internet mode works reasonably well, but will require a lot more testing and work to prevent bad actors.

There is a protocol specification: https://github.com/michaelgpearce/coinmux/blob/master/docs/spec.md
The peers communicate using JSON messages.  None of the connected peers can associate input with output ownership from the messages themselves, only by IP addresses.  This is a pretty big privacy leak, but can be solved by integrating Tor or Freenet to communicate the messages.

I've only implemented a command line interface for now, but the CLI is event driven and built with a GUI in mind.  I don't want non-developers trying it yet so a CLI seems like a good place to start.

The easiest way to try it out locally is to use "--data-store filesystem" and invoke the command from a couple of different terminal sessions on your computer.  Again, its setup to use Testnet, so you need a Testnet wallet / private keys.

[themgp]

... and of course, you can generate an address from bitaddress.org and get some Testnet coins from TP's faucet.

https://www.bitaddress.org/bitaddress.org-v2.6.5-SHA1-fa763c2bbc97e1b37bc6d3945647aed869ec8c18.html?testnet=true
http://tpfaucet.appspot.com/

[themgp]

Hey all, i just released v0.1.0 of Coinmux (followed quickly by 0.1.1 to fix a couple of minor UI issues) which is my milestone for having things functional on Testnet.  I'm ready to move on to building a GUI to sit on top of the code already there and make it easier to use.

But before I do that, I want to try it out on the Bitcoin MAINNET and with some STRANGERS on the Internet!  I've never done either!

I'm hoping a couple of you are brave enough to try it with me.  I want to do a small CoinJoin transaction, 0.001 BTC (a little less than 1USD) .  To get a suitable wallet, I simply went to bitaddress.org, created a new wallet for the CoinJoin input, and then sent 0.0015 BTC to it from my main wallet (a little extra for miner fees).  Any address with a balance > 0.0015 will work, but I would not recommend using your primary wallet.  There shouldn't be any issues, but better to be safe than sorry.

If you are interested, there is a link to download the latest Java client here: https://github.com/michaelgpearce/coinmux.  To use the Mainnet Bitcoin network instead of Testnet, you'll simply need to set an environment variable COINMUX_ENV=production.  On a Unixy OS, you should be able to just type this command in the terminal/console where you run the Java command.  On Windows, i believe you use the SET command, but its been years since i've used Windows.

I'm on Freenode IRC at #coinmux via webchat: https://webchat.freenode.net.  Hopefully one or two people will come find me.

Thanks!!

[themgp]

Hey all.  Short update, here is the first transaction that Coinmux has created on the main Bitcoin network and a transcript of the output as shown on the console from one of the peers.

https://blockchain.info/tx/b5b8c60836d22964138d05c0bd42f9f06ccef81cd3150641a9436f6173ded6c0

(Its kinda cool that it confuses Blockchain.info's "Estimated BTC Transacted" for the transaction!)

Code:

~/Downloads $ COINMUX_ENV=production java -jar coinmux-latest.jar -p 2 -a 0.001 -o 1GQypfLSim1xndF5jupFrNoJi9U9LFLLzp -c 1Jd7Hiv43MeHMkPKU4bbSJqvQeZxqLj5iu
Enter your private key:
***************************************************
Starting...
[Participant]: Finding coin join message
[Participant]: No available coin join
   [Director]: Inserting coin join message
   [Director]: Inserting status message
   [Director]: Waiting for inputs
[Participant]: Finding coin join message
[Participant]: Inserting input
[Participant]: Waiting for other inputs
   [Director]: Inserting message verification message
   [Director]: Waiting for outputs
[Participant]: Inserting output
[Participant]: Waiting for other outputs
   [Director]: Inserting transaction message
   [Director]: Waiting for signatures
[Participant]: Inserting transaction signatures
[Participant]: Waiting for completed
   [Director]: Publishing transaction
   [Director]: Completed
[Participant]: Completed - Transaction ID: b5b8c60836d22964138d05c0bd42f9f06ccef81cd3150641a9436f6173ded6c0
CoinJoin successfully created!

[Rassah]

How does Coinmux find other users? And if it doesn't, can it implement a Bitmessage chan?

[themgp]

How does Coinmux find other users? And if it doesn't, can it implement a Bitmessage chan?

It uses a java p2p library http://tomp2p.net/ to create DHT of users.

Yep. It uses TomP2P. My initial implementation was going to use Freenet, but I didn't want to require needing any external applications running.

In Coinmux, I call the communication layer a Data store in the code. There is an implementation using TomP2P, the file system and one that uses only memory for testing purposes. It's straight forward to implement these and I did also consider Bitmessage. Unfortunately, the Bitmessage JSON API looked to be very heavily tied to a specific user in the UI with no way to create a new user via API or send messages as a specific user. This lead me to stop investigating it further.

[piotr_n]

Good stuff - I hope it will explode

[themgp]

Good stuff - I hope it will explode

Thanks! There's a bit of a trust issue with any new Bitcoin software project (especially with one that asks you to enter your private key!), so i'm having a hard time finding people to try it out. Hopefully time will be the solution to that.  I'm planning on giving a presentation at the SF Bitcoin Meetup to increase CoinJoin and Coinmux awareness.

[themgp]

Good stuff - I hope it will explode

Thanks! There's a bit of a trust issue with any new Bitcoin software project (especially with one that asks you to enter your private key!), so i'm having a hard time finding people to try it out. Hopefully time will be the solution to that.  I'm planning on giving a presentation at the SF Bitcoin Meetup to increase CoinJoin and Coinmux awareness.

I think this is a great start, your protocol needs a little work and I am writing something off of it.

Feel free to share your thoughts.  I haven't gotten any feedback on the protocol yet.

[Cryddit]

Good stuff - I hope it will explode

Thanks! There's a bit of a trust issue with any new Bitcoin software project (especially with one that asks you to enter your private key!), so i'm having a hard time finding people to try it out. Hopefully time will be the solution to that.

Testnet is the proper solution to that.  Let people test it using testnet coins and the problem about the bitcoin private key risk goes away.

[themgp]

Good stuff - I hope it will explode

Thanks! There's a bit of a trust issue with any new Bitcoin software project (especially with one that asks you to enter your private key!), so i'm having a hard time finding people to try it out. Hopefully time will be the solution to that.

Testnet is the proper solution to that.  Let people test it using testnet coins and the problem about the bitcoin private key risk goes away.

I totally agree. It is set up right now to work off testnet by default (the user needs to set an environment variable to connect to Mainnet). Unfortunately, the testnet knowledgeable audience is a lot smaller, and CoinJoining needs multiple people running it at the same time.  Hopefully in time, this will resolve itself.

And i'm not sure i really made this clear in my original posting, but the only thing needed to run Coinmux is Java and the Jar file available from http://github.com/michaelgpearce/coinmux.  You don't need to have BitcoinQT installed and it does not require downloading the blockchain to your computer.  I'm trying to make something that an average Bitcoin user will be able to understand and use.

[Cryddit]

After reviewing your coinmux code, I can identify a problem.  And a solution.

The good: no evidence appears in the blockchain about whose inputs are associated with which output.  That's part 1 of the solution.  

The bad:  Someone eavesdropping on the protocol messages, including a nonparticipant, can associate both inputs and outputs with IP addresses.  Fixing this is completely necessary before coinmux is viable, especially since the primary attack on network privacy is via traffic analysis.

The solution:  Implement a Dining Cryptographers Network among the participants, and you are immune to traffic analysis.  Here's a wikipedia article about the Dining Cryptographers' problem which it's based on.  

http://en.wikipedia.org/wiki/Dining_cryptographers_problem

In a DCN, topologically the participants are arranged in a circle, where Alice is next to Zebulon and Bob, Bob is next to Alice and Carol, Carol is next to Bob and Estelle, etc.  

Each adjacent *pair* of participants generates a shared key stream - which can be as simple as repeatedly incrementing a nonce and encrypting it to get each new block of the key stream.  You can use Diffie-Hellman key agreement to create a shared secret to key the stream.

Then each participant publishes XOR of the keystreams he shares with his two adjacent participants and the message he wishes to broadcast.  When all of these published messages are XOR'd together, the broadcast message magically appears because each keystream has been XOR'd with it twice thereby cancelling out the keystreams.  Different participants can write on different parts of the block, creating different messages.  And the participants can iteratively publish the block with updates, if they use a different hunk of their shared keystreams each time.  I'm thinking that the obvious implementation here has the 'block' that's getting updated include the image of a transaction.  The participants would each add their inputs and their outputs, then signatures (not valid if anybody changes outputs) in a later round.

The benefit is that nobody monitoring the protocol messages can tell where the messages (or the parts of messages, IE inputs and outputs) originated, even if they saw every last message and every published XOR.  Not even the participants can tell anything about the origins of any part of the message written by someone else.

It has some limitations;  For example if two people both try to write on the same blob of bits at the same time, then the 'message' that appears in that blob is binary garbage.  So there are conventions about 'reserving' blocks in previous rounds, where you agree that whoever reserved the block can write things in it and others shouldn't, and ways to detect which participant has broken the convention so that they can be cut out of subsequent rounds, etc.  Also, it requires O(n^2) overhead where n is the number of participants, so it doesn't scale well past a few dozen people per mux. It's kinda clunky.  

But it does work, and it's completely trustless in that NOBODY can de-anonymize, or even distinguish, the participants.  

[themgp]

The cryptographer in me says I should do this, while the engineer in me thinks this may be (too) difficult to implement.  (And I'm a much stronger engineer than cryptographer!)  I still haven't totally wrapped my head around it from an engineering perspective, I'll do that once I get the GUI for Coinmux working.  But I am a believer in keeping Coinmux simple.  Bitcoin has some warts, but its really pretty simple as far as crypto goes.  I'd like to keep that same philosophy for Coinmux.

One of the easiest things I can do to limit who sees the the IP address of published messages is to encrypt them.  Both the Director and Participants have a public key as part of their first message broadcast.  Other than the Director's first announcement message and the Director's subsequent status updates, all other messages can be encrypted so only the involved parties can decrypt the messages.  The IP address would still be leaked, but only those in the mix can make sense of what's going on.  While not a cryptographically perfect solution, this would make traffic analysis more difficult and less useful. This may make put Coinmux in the "good enough to be useful" category. This wouldn't be great, but as an engineer, I realize everything has tradeoffs.

The Coinmux protocol itself was not designed to hide IP addresses/participants, only to facilitate communication.  As i first imagined what the protocol would look like, I had always considered using Freenet for message communication and to provide anonymity at the "network layer." Coinmux was designed with a Freenet like system in mind with the following properties: untraceable message insertion, immutable messages, ability to post multiple messages to a known location/key, and all messages publicly retrievable from a known key.  TomP2P allows for all of these except the untraceable message insertion.  TomP2P was really only selected due to it being available as a Java library and ready to be embedded in an application.  Well, that and it's faster than Freenet.

I'd rather try to solve this at the network layer than the protocol layer.  This allows for the network layer to be easily changed (I have 3 implementations now - TomP2P, the filesystem, and a memory implementation used for testing).  I am still actively considering switching to using Freenet as originally planned. Bitmessage is another option, though i believe their API is inadequate.  Maybe there is a way to use Tor.  Or maybe some new Altcoin becomes a viable option in the future. Or maybe i can push harder on TomP2P: is it possible to shuffle messages around the TomP2P peer network before inserting them to provide anonymity?  The protocol doesn't care who inserted the message, only that it gets inserted.  As it is right now, none of the options outside of TomP2P meet the requirement of "easy to use" as they require an additional application running.

Anyway, there are lots of different options and all of them have tradeoffs, but I am pretty open to anything that will work.  I'll need to let what you wrote settle on my brain a little more.

[randomguy7]

Maybe you can use i2p (https://geti2p.net) for the network layer (comes with nice java bindings ).