The point of mixing is so you can't tell who owns what coins afterwards. If you have a tx like this:

47 BTC -> 50 BTC

50 BTC -> 47 BTC

you don't have to be a genius to assume that the 47 BTC input maps to the 47 BTC output. The mix has failed.

There isn't an easy way to fix this if the disparities between parties are huge. But if they aren't, as above, we can do:

47 BTC -> 10 BTC

50 BTC -> 10 BTC

-> 10 BTC

-> 10 BTC

-> 1 BTC

-> 1 BTC

-> 5 BTC

-> 5 BTC

-> 5 BTC

-> 20 BTC

-> 20 BTC

and now it's not really clear which output is owned by whom. There are several combinations that work.

Let a represent the minimum of the inputs,

Let b represent the GCD of the inputs.

For each input, the output is to be as many blocks of

*a* as possible, followed by enough

*b* to complete it.

This method works decently:

IN OUT

8 BTC -> 8 BTC

10 BTC -> 8 BTC

-> 2 BTC

IN OUT

3.5 BTC -> 3.5 BTC

6.5 BTC -> 3.5 BTC

9.0 BTC -> 3.5 BTC

-> 3.5 BTC

-> 0.5 BTC

-> 0.5 BTC

-> 0.5 BTC

-> 0.5 BTC

-> 0.5 BTC

-> 0.5 BTC

-> 0.5 BTC

-> 0.5 BTC

-> 0.5 BTC

-> 0.5 BTC

That method is unfortunately not perfectly secure. For example, none of the 0.5 BTC outputs belong to the first party (the one supplying 3.5 BTC).

The last one could be done better and shorter:

3.5 BTC -> 3.0 BTC

-> 0.5 BTC

6.5 BTC -> 3.0 BTC

-> 3.0 BTC

-> 0.5 BTC

9.0 BTC -> 3.0 BTC

-> 3.0 BTC

-> 0.5 BTC

-> 0.5 BTC

-> 0.5 BTC

-> 0.5 BTC

-> 0.5 BTC

-> 0.5 BTC

13 outputs, instead of 14. Also, looking at the transaction, you cannot figure out any information

**with 100% certainty** about the identity of any one of the outputs.

So we must translate this

For each input, the output is to be as many blocks of a as possible, followed by enough b to complete it.

Into

For each input, the output must be composed of blocks no greater than a. Each input must correspond to at least one output of each size block.

Which is only a bound, not a function.

Since all of the inputs are in a single transaction, there is no way to map an input to an output. I can find no way to further shorten the above example.

This example:

IN OUT

8 BTC -> 8 BTC

10 BTC -> 8 BTC

-> 2 BTC

Fails in a very bad way: the 2 BTC output obviously belongs to the owner of the 10 BTC input.

There is also the unfortunate aspect of probability: looking at the example with 3.5, 6.5, and 9 as inputs, each 0.5 output has a 75% chance of belonging to the owner of the 9 input.

Here is the optimal solution.

Several parties can get together and mix like this:

3.5 BTC 3.5 BTC

6.5 BTC -> 3.5 BTC

9.0 BTC 3.5 BTC

3.0 BTC

5.5 BTC

Of course, the 3.0 and 5.5 BTC outputs are identifiable. They do another transaction*

3.0 BTC -> 3.0 BTC

5.5 BTC -> 3.0 BTC

-> 2.5 BTC

The final 2.5 BTC is impossible to mix satisfactorily with the other parties.

* this can all be done in one transaction, actually

Doing an analysis on this transaction yields:

- Each of the 3.5 BTC outputs have a 33% chance of belonging to any given party. 1/3 is obviously the maximum anonymization which can be achieved with 3 parties.

- Each of the 3.0 BTC outputs have a 50% chance of belonging to B or C, and do not belong to A. 1/2 is the maximum anonymization which can be achieved with 2 parties, and trying to mix these coins with party A ruins the perfect anonymization of the 3.5 BTC outputs (see below).

- The 2.5 BTC output belongs to C

Mathematically, any good permutation is equivalent. For example, given 38 0.5 outputs, each output has a 7/38 chance of belonging to party A, a 13/38 chance of belonging to party B, and a 18/38 chance of belonging to party C.

Now that I've shown perfect anonymization to be impossible with unequal inputs, here's my idea of a practical implementation:

- Each node which wants to mix sets two values, Min and Max. Min being the lowest value it wishes to deal with (this is a tradeoff -- a lower value means higher anonymity, but a higher value saves money on tx fees and blockchain size etc), and Max being the amount of money it wishes to supply to the input of the transaction (setting this to the maximum amount of money in the wallet risks disclosing how much money you own and could theoretically allow identification of addresses, but it lets all of your money be anonymized later on.)

- Each node also has a MaxParties or MaxTxSize constant to avoid some global mixing which crashes every computer and begins the apocalypse.

- The node broadcasts these through some channel (p2p or centralized) and connects to peers such that A

_{max} >= B

_{min} and B

_{max} >= A

_{min} for all peers A and B.

- After MaxParties is reached or some time limit is expired, they begin constructing a transaction as in the iterative example above.

Populate associative array A with inputs from each party (each party supplies Max as broadcasted as a Tx input) and an array of output addresses per input.

While array A is not empty

{

find the minimum value in A

add an output of this minimum size to the first address in each outputaddress array to the transaction

remove the minimum key-array pair from A

remove the first address from each array in A

}

Verify that the transaction spends the total of your input addresses to your output addresses

Sign the transaction

Once signed by everyone, broadcast it.

I would notate array A as something like {3.2: [1abc, 1def], 5.0: [1ghi, 1jkl]...}

In order to find how many output addresses to supply, take Max from each party and run the above code, but keeping a tally of outputaddresses rather than adding outputs pointing to them.

Once this is done, each party can help populate array A by adding their Max and list of addresses, and signing that with the address which is to supply the input.