Chaumain CoinJoin

In 2013, Gregory Maxwell presented the idea of CoinJoin, and suggested a couple of ways to implement it.
https://bitcointalk.org/index.php?topic=279249.0
One of his suggestion was the following:
"Using chaum blind signatures: The users connect and provide inputs (and change addresses) and a cryptographically-blinded version of the address they want their private coins to go to; the server signs the tokens and returns them. The users anonymously reconnect, unblind their output addresses, and return them to the server. The server can see that all the outputs were signed by it and so all the outputs had to come from valid participants. Later people reconnect and sign."
While the idea was great, it never got traction, because the discussion went into two different direction.

(1) How to decentralize the server?

	To which his comments were the following:
	"Does the totally private version need to have a server at all? What if it gets shut down?
	No. The same privacy can be achieved in a decentralized manner where all users act as blind-signing servers. This ends up needing n^2 signatures, and distributed systems are generally a lot harder to create.  I don't know if there is, or ever would be, a reason to bother with a fully distributed version with full privacy, but it's certainly possible."

	As a followup CoinShuffle and CoinShuffle++ emerged and later an implementation was attempted by Mycelium, called ShufflePuff. The works on ShufflePuff was abandoned, since.
	http://crypsys.mmci.uni-saarland.de/projects/CoinShuffle/coinshuffle.pdf
	https://crypsys.mmci.uni-saarland.de/projects/FastDC/draft-paper.pdf
	https://github.com/DanielKrawisz/Shufflepuff

	Decentralized systems are hard to get right, require various tradeoffs and open the door for various attacks. Updating/upgrading them are also not an easy job.
	Furthermore, because Chaumain CoinJoin does not has the risk of coin stealing, nor the risk of privacy breaching, distributing the server might not be fully justified from a practical point of view.

(2) In order to successfully execute a privacy preserving CoinJoin everyone needs to send the same amount, how to overcome this?
	JoinMarket took the lead and introduced the maker-taker concept, where market makers are waiting until a taker wants to execute a CJ transaction and asks market-makers to provide liquidity  for his CoinJoin for a small fee.
	https://github.com/JoinMarket-Org/joinmarket
	This approach in the ever growing Bitcoin fee environment is getting costy.

To my knowledge Chaumain CoinJoin has never seen any implementation, nor detailed specification.

TumbleBit's Classic Tumbler mode has the same "common denomination" issue as CoinJoin.
https://eprint.iacr.org/2016/575.pdf
In NTumbleBit we solve it by starting a tumbling process, that runs until all the coins are tumbled.
For example if the user has 8.3 bitcoins and the denomination is 1 bitcoin, then we do 8 rounds of tumbling in a row, and 0.3 bitcoin will not be tumbled. We leave the job of not joining tumbled outputs together to the output wallet to handle.
https://github.com/NTumbleBit/NTumbleBit
This results in paying 8 times transaction fees. Since every round consists of 4 transactions, this is 8x4 times normal transaction fees.
A tumbling round will also take from 2 hours to 1 day.

Maxwell's Chaumain CoinJoin idea could be used the same way, however it will take instead of 8x4 txfees, only 8x txfees and instead of measuring a round in hours and days, we would measure the round in minutes, maybe seconds.
In TumbleBit we could potentially achieve thousands of anonimity set, however
(1) you get the users for that
(2) the tumbler must hold thousands of coins in order to cover the escrow, supposing 1btc denomination.
In Chaumain CoinJoin only the first issue stands, but it is easier to achieve, because of the drastically faster speed and cheaper fees.

In CoinJoin the limit of the anonimity set is the maximum standard transaction size, which is 100k byte.
Because the most common transactions we are concerned with are 1 input, 2 outputs and the second most common are be 2 input 2 output transactions.
The sizes of these transactions are about 220 byte and 360 byte, therefore the maximum achievable anonimity set would go from 270 to 450 (100k/360=270, 100k/220=450).
I don't know if Segregated Witness would elevate the signature size out of the calculation, by that resulting +30% anonimity set, or not, but when Schnorr signatures will be introduced they will definitely do that.

It is also worth to note if Confidential Transactions are intorduced, there would not be a need to do rounds, since it hides the amounts in the transactions. Altough CT would result in higher transaction sizes, which will be later an issue to consider.

The only disadvantage of Chaumain CoinJoin is that if someone doesn't sign the final transaction, which likely can be handled by simple input banning.

How does Chaumain CoinJoin work in a nutshell?
	First we must define Alice and Bob as the same client, but the server does not know about that. For example they are on different Tor circuits.

	1. Many Alices register their utxo (as the input of the CoinJoin), desired change address, and a blinded output address to the server.
		Alices also prove that they own control the private key of the registered utxo.
	Alice                              Server                              Bob
	blind(outputAddr)=A'
	----utxo, changeAddr, A', proof--->

	2. The server checks if the utxo is indeed unspent, has enough money, and Alice indeed control it, then sign the blinded output address.
	Alice                              Server                              Bob
	                                   check(utxo)
	                                   check(proof)
	                                   sign(A')=signedA'
	<-----------signedA'---------------
	3. Alices unblind the output address, they change their identity to Bob and register their signed output addresses to the server.
	Alice                              Server                              Bob
	unblind(signedA')=signedA
	-----------------------------signedA----------------------------------->
	                                       <-----------signedA--------------

	4. The server constructs the transaction, gives it out to Alices for signing.
	Alice                              Server                              Bob
	                                   buildTx->tx
	<-----------tx----------------------
	sign(tx)

	5. Alices send back their signatures, the server combines them and propagate the transaction.
	Alice                              Server                              Bob
	------signature--------------------->
	                                   combineSignatures
	                                   broadcastTx

	As noted before if an Alice refuses to sign, her input can be banned and restart the round.