One thing to be aware of is the potential lack of security even using Tor right now, so one should be using Tor 2.4 or later even though it is alpha. See below.  Once CoinJoin is live, one should be aware of Tor versions for best practices in privacy.

http://arstechnica.com/security/2013/09/majority-of-tor-crypto-keys-could-be-broken-by-nsa-researcher-says/

Very true.  Unfortunately Tor (et al) are not yet to the point that many would like.  :-)

I propose a specification of the CoinJoin protocol. It is not yet implemented, but if you find the work-flow sound it would not be hard to make an IRC bot with the sx command line utilities as a proof-of-concept.

The idea is a P2P network where a thread is relaying all transactions. Another thread is in charge of the mixing.

A first, simple implementation would be an IRC bot which sends and listens to encoded transactions. Of course this approach would not be P2P, but a public channel in a hidden IRC server provides several advantages:

   -Easy implementation: IRC servers already exist. Bots enter to the channel #coinjoin (for example) and speak there.
   -Soft trust system:
      - If we trust the IRC server (for large values of 'trust') and only registered nicks are allowed to talk in the channel, a Sybil attack will be difficult.
      - We can chat (privately or publicly) with some users and thus allow them to prove their identity (by signing a given message, telling you a private joke, etc.)

The concept is composed by two parts (threads):

   1) Communications thread: In the case of the IRC server architecture, it has the method "sendTransaction" and "listenToTransaction". The first one "chats" in the channel and the latter listens to transactions and stores them in memory.

   2) The actual mixing part: Its work-flow is showed in the link [1]. It has been designed with yEd (http://www.yworks.com/en/products_yed_download.html) and the file (if you want to edit it) is [2] . The main points are:

      - It handles "change" addresses. If you want to mix 47 BTC, it will be a pain (really!) to make 47 inputs of 1 BTC and mix the separately. This approach allows you to send the 47 BTC as input, recover 1 BTC (for example) mixed and your 46 BTC back (of course, not mixed! In order to avoid confusion, this change address is the same as the input address). Fees are deduced from the change address, and thus you can serialize this method trivially as many times as you want.

      - Random decisions to avoid an attacker that listens how the transaction is constructed to map inputs with outputs. Each time transactions are composed in a different order.

      - If something goes wrong (bad signature, peer not responding, etc.) the output is discarded and the process restarted.


Q: What means checkTransaction?

A:
1) Are inputs confirmed (at least 1 confirmation)? OR, Are all unconfirmed previous transactions valid (for the Bitcoin network) and with enough fee?
AND
2) Signatures match?
AND
3) Is there enough transaction fee?
AND
4) Are all outputs equal AND sum(outputs) < sum(inputs)?


[1] http://i41.tinypic.com/5p3k02.jpg

[2] http://www18.zippyshare.com/v/26446175/file.html

No it is not. Take a look at the flowchart. The way the transaction is constructed does not leak information about which input goes with which output.

For example (fees excluded for clarity)

Inputs:
1) 50 BTC from 1addr1
2) 100 BTC from 1addr2

Outputs:
1) 1 BTC to 1addrX
2) 1 BTC to 1addrY
3) 49 BTC to 1addr1
4) 99 BTC to 1addr2


The change is sent to the same address in order to avoid confuse the user (it was 1addr1 the mixed, or was it 1addrY?).

Anyway, if you *really* want to specify a different one, it is trivial to do that.

I agree that it might not be ideal, but it does not compromise the anonymization. It is not intended to be pretty, but useful, and to decrease the chance of the user making mistakes.

I will answer the two questions:

1) Why is there a change address?
Because more often than not the user has more coins than the standard amount to mix (for example, 1 BTC).

2) Why is the same as the input address?
Because it makes clear that these funds are NOT mixed. Not only slightly mixed (in my previous example, the output with 49 BTC is obvious where it came from). There is no such thing as "little unsure". Funds are completely anonymous*, or they are identifiable. And I chose to make it clear in the protocol.

I would like feedback in the protocol itself. For example, how can a transaction be re-identified, or under which circumstances the program may be stuck. If you still believe that reusing the change address would compromise anonymity, please give a concrete example of how.

If it is OK, developing the program is quite straightforward. All the tools exist already (it can be even a bash script with the sx tools).


*Under certain assumptions, like for example excluding the other party (this is why the process is repeated several times)

Here is something that would help.

Standardize some coin denominations, call 'minted coin'.  Random other denominations call 'bullion', for 'bulk metal.' 

Let a standard minted coin be anything that starts with 1, 25, or 5, and the rest of whose digits are zero. 

phase 1.  Merchants start splitting input into minted coin into own wallets, giving back minted coin as change.   Trigger phase 2 when 90% transactions last 100 blocks done exclusively with minted coin input & output. 

phase 2.  Now make 'normal' transaction be transaction exclusively in minted coin.  Other transactions still legal, just not 'normal' anymore (or maybe not 'normal' unless accompanied by bigger tx fee for miner). 

phase 3.  Clients concerned with privacy may start participate exclusively in tx have exactly same number, denomination, for input & output, and at least 2 inputs largest size coin used.  Other clients, not care, may allow tx where take maybe some number coin at same address , but if so let make another standard size coin. 

Easy for someone to figure out what's going on when there's an input that's 3.88 BTC, an output that's 3 BTC, and an output that's .88 BTC. 

Much less easy when there are 3 inputs of 1 BTC, 3 inputs of .25 BTC, 2 inputs of .05 BTC, and 3 inputs of 0.1 BTC, and output is exactly the same number and size of coins.  No way to know which is change going back to buyer.  No way to know which inputs & outputs represent buyer, which seller.  Maybe seller has inputs too, and is making change  Not even a way to know if the thing somebody bought cost 0.5 BTC or 3 BTC or 3.5 BTC, etc. Every address used have one coin, every address paid to have one coin. 

Trades in 'bullion' (arbitrary N-digit denominations) still possible, maybe not 'standard', or may require small 'minting fee'.  But also possible exchange 'bullion' for 'minted coin'  of standard denominations, down to level of negligible dust award for miners.   Not even possible when watching to tell difference between someone changing own 'bullion' for goods with merchant take 'minted coin' and getting 'minted coin' change, from someone just changing own bullion for minted coin.

Makes 'coinjoin' privacy by default.  Money go through a few ordinary trades under new rules, specially trades with or by privacy enforcing clients, no longer possible tell who own which. Is soft fork only; all tx legal under new rules also legal under old.  Takes no 'mixing' as such or 'mixers.'  Requires trust no extra party.  Implementation simple and easy make secure.

Edward.

That's a neat idea (mixing large transactions) but unfortunately I cannot see how it could be implemented. When signing an input we sign a hash of the outputs, and thus adding new outputs will require to re-sign the transaction (as you already stated).

So, the transaction must go back and fort (in order to resign it each time an output is added) and the miner becomes essentially the rendez-vous server.

Interesting.  I had not thought about the privacy implications of the jagged numbers, just the bloaty change part.