6

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?

2
  • Are you aware of comsys.rwth-aachen.de/fileadmin/papers/2017/… ? Apr 4, 2018 at 13:07
  • I wasn't, thanks. I coded it and added to my tests, but it doesn't give optimal combinations, even if you try all possible Knapsack combination and only go with the best, the middle-out algo above consistently performs better.
    – nopara73
    Apr 5, 2018 at 1:26

1 Answer 1

1

I don't have an answer to your question directly, but it's worth pointing out that anything other than 32 x 0.1btc inputs and 32 x 0.1btc outputs provides worse anonymity. Even having 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.1, 0.1 gives away some information that likely 2 of the inputs were 0.1btc above a number divisible by 0.3. Maybe there's a peak on a benefit/cost curve, but it's still a trade-off against privacy. There are other solutions outside of Bitcoin (that vastly improved on the concepts of coinjoin) like MimbeWimble which do what it sounds like you want in terms of cheap coinjoining, but with other benefits too, that Bitcoin is unable to implement because of its design

1
  • 1
    Another con I learned in the meantime that with fixed denominations perfect remixing is possible, which increases anonymity greatly. This of course not to say the pros don't outweigh the cons, it's just a more elaborate concept is needed to evaluate and research these ideas.
    – nopara73
    Dec 6, 2018 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.