A coinjoin is a collaborative bitcoin transaction, where multiple users own different inputs to the same transaction.
There is a consensus problem: every user needs to sign the exactly same transaction, if one input fails to sign, it is an invalid transaction and will never confirm.
An easy solution to consensus problems is to have a central coordinator to propose the transaction to be signed. Every coinjoin implementation so far uses centralized coordination, because deventralized consensus is bloody difficult.
In order to preserve privacy, nobody, including the coordinator, should learn that multiple inputs or outputs belong to the same user. Clients can create a new Tor identity for each input and output registration with the coordinator.
However, if the coordinator would allow any anonymous Tor identity to register outputs, then any troll can keep on registering unfunded outputs. The coordinator needs to ensure that a user can only register an output, if they registered an input with enough sats earlier.
This access right system can be designed in a privacy preserving way by using the cryptography that enabled anonymous eCash, Chaumian blind signatures. The client creates a random serial number, blinds it, and sends the cyphertext to the coordinator during input registration. If the input is valid, the coordinator signs the cyphertext with his privat key and returns the signature. Depending on the amount of sats in the input the coordinator uses a different private key. The non-standard change amount output has to be registered already now non-anonymously. Later during output registration, the client unblinds the signed cyphertext, and sends the unblinded signed serial number to the coordinator together with the output address. If the signature is valid, and the serial number is new, then the coordinator allows the output address registration with the sats value depending on from which key the signature is. If multiple users register the same amount, then there is an anonymity set for that private key. The coordinator cannot find out from which input registration this signature is. However, because users register arbitrary input amounts, there will always be a change output where the blind signature cryptography does not work, thus the coordinator learns the linkage between inputs and change output.
However, with the use of more fancy cryptography, this access right system can be greatly improved, this is Wabisabi: Keyed verified anonymous credentials have similar blinding attributes as blind signatures, however one credential can have multiple independent and flexible attributes. One of the attributes is the serial number, the other is a homomorphic encrypted value of the amount of sats. During input registration the client creates the serial number and adds the sats amount of his input minus fees to the credential. The coordinator verified the input and the amount of the credential, then signs it. The coordinator also signs credentials with a zero amount of sats. Next, the client can "reissue" credentials to himself, he presents to the coordinator two unblinded credentials, and two new blinded credentials. The coordinator does not know the values of any of the credentials, however he knows that the sum of the two old credentials is exactly equal to the value of the two new ones. This uses Peterson commitments and bullet proofs, like liquid or monero. This way the user can change the value of his credentials to whatever he likes, consolidating multiple small credentials into one big 2+2=4+0, or splitting up one big credential into multiple smaller 4+0=3+1. Later during output registration, the client unblinds the credential serial number and amount, and presents this with a fresh bitcoin address to the coordinator, who verifies his signature and approved the output. The anonymity set of the credential does not depend on the amount anymore, it is now the set of all users of this round. There is no non-private change output, each output registration is done with a new Tor identity and new anonymous credential.
After output registration, all clients construct the final unsigned transaction, verify that their inputs and outputs are represented, sign it, and send the signature to the coordinator. If all inputs sign the transaction, the coordinator broadcasts it to the Bitcoin network.
To sum up, a coinjoin coordinator is a centralized bulletin board that collects inputs, outputs, and signatures of multiple bitcoin users. The coordinator creates ecash tokens for a registered input, and only accepts outputs when that token is redeemed. Using Tor, blind signatures, and homomorphic value encryption ensures that not even the coordinator learns which inputs or outputs belong to the same user. The key innovation of Wabisabi is to make the value of the access right token anonymous to allow for arbitrary input and output values.
