Mixing Unequal Inputs [Optimal Heuristic]

[nopara73]

Related Issues: #73, #74, #75
Related Question: https://bitcoin.stackexchange.com/questions/73431/mixing-unequal-inputs
Non-entropist Approach Measuring Anonymity: https://www.freehaven.net/anonbib/cache/entropist.pdf
Knapsack Algorithm: https://www.comsys.rwth-aachen.de/fileadmin/papers/2017/2017-maurer-trustcom-coinjoin.pdf

Intuition

[nopara73]

Jeremy Mandelkern

As your goal appears to be the "optimization" of the average of some sort of weighted sum, the way in which your weighted terms are generated will be key. It may be possible that optimization techniques from Multivariate Calculus would be applicable, I.E. Lagrange Multipliers.

[nopara73]

Advantages of unequal input mixing, compared to the fixed denomination mixing. I will use the following notation here:

UIM - Unequal Input Mixing
FDM - Fixed Denomination Mixing

1. UIM's main goal is to optimize the cost/anonymity set.
2. In FDM those who don't have enough money to mix, will not be able to mix. In UIM it is not an issue anymore.
3. In FDM peers often join together their utxos in order to reach the denomination. This exposes common ownership. There is no such an issue in UIM. Because of this, joining utxos together after the mix is not as big of a deal anymore.
4. In UIM mixing can be done over and over again until the desired anonymity set is reached. In FDM mixing cannot be repeated, because the mixed output of the mix will never reach the sufficient input level of the next mix (due to network fees.) In FDM if the user would decide to participate with an already mixed coin, then he would have to add another input in order to suffice the mix requirements, which exposes common ownership.
5. People with lot of money would got matched together and would not have to wait weeks/months to mix everything out.

[nopara73]

Combining Groupsend with UIM: Unequal Amount Mixing for ZeroLink using Preferred Value Series Fixed Denominations

https://gist.github.com/nothingmuch/544cdd47dd18ef8fe923b54e0d5ee141