Quote from: Cryddit on February 09, 2014, 04:21:31 PM

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.

I've thought through this some more. I could implement this, and it wouldn't be terribly difficult. In fact, I think I can even implement it without changing my current communication API (see my data store requirements in a previous post). My main problem with it is that it only solves one thing that i can't solve by simply encrypting every message published to the Director and a DCN doesn't solve a larger issue.

With using TomP2P and adding message encryption, the Director can still connect IP addresses to Inputs/Outputs but the Participants cannot. A DCN will solve this. But an outside observer would most likely still be able to connect IP addresses with the resulting published transaction just by watching the Coinmux network and watching the Bitcoin network. While the observer cannot directly correlate an IP to a specific Bitcoin output address, just knowing the transaction and the IP addresses involved is still a pretty big leaked piece of information.

If I use an anonymity network (i.e. Freenet), it would solve both issues. Neither the participants nor the director would be able to associate an IP address to a specific input/output, and an observer would not be able to associate a transaction to any IP addresses.