Let's say have 3 inputs (alice, bob, satoshi): 0.3, 1.3, 1.6.
We can mix these inputs for example like this: 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.1, 0.1.
Or like this: 1.3, 1.3, 0.3, 0.3.
Traditionally it is mixed like this (CoinShuffle/ZeroLink/BlindCoin): 0.3, 0.3, 0.3, 1, 1.3.
There are many combinations, but there are better and worse mixes. I intuitively figured I want to anonymize the most bitcoins in the cheapest way.
First take the sum of the anonymity sets weighted by the amount of bitcoins. With the second mix example (1.3, 1.3, 0.3, 0.3) it would be:
- alice: 0.3btc -
2/1=2 anonset ->2*0.3=0.6 - bob: 1.3btc -
2/1=2 anonset ->2*1.3=2.6 - satoshi: 1.3btc -
2/1=2 anonset ->2*1.3=2.6 AND 0.3btc -2/1=2 anonset ->2*0.3=0.6
And the sum is: 0.6+2.6+2.6+0.6=6.4
Next we want the cheapest possible mix, for this we need to minimize the number of outputs, in the second example it's 4. Finally divide the number of outputs by the weighted anonset sum: 6.4/4=whatever (1.6).
We want this whatever number to be as high as possible. This is how we can anonymize the most bitcoins the cheapest way.
With the traditional mix, whatever would be 5 weighted anonset sum / 5 output number=1.
So the my ad-hoc 2nd algorithm exactly 60% more efficient.
I also wrote a little software that compared 3 different algos with 100 random inputs (results below).
The first goes like this: take always the smallest input and pair it up with the rest. This generated many outputs (as you can see it created so many outputs, that it overflow by 173% of the standard maximum Bitcoin transaction size.)
The second algo always took the second greatest input and paired it up with the greatest.
During the third algo I used middle out, so I took the middle input and paired it up with as many inputs as possible. This provided by far the best whatever value: 149.
Test code: https://github.com/nopara73/ConsoleApp14/blob/master/ConsoleApp14/Program.cs
What algorithm can lead to the most optimal mix?
