[Proposal] Merge pre-mixed/change inputs without change

[NicolasDorier]

I noticed that I spend a fair amount of time trying to select exactly the right amount of change coins to make 1 whole round without any change back.

Because the number of change keep growing, and you don't want any change back to protect your future privacy, I was thinking it is a good idea to have a feature which try to selection the coins to almost equal the coinjoin round price.

[nopara73]

That is how it worked for about 2-3 months ago, but then I thought I be smart and do some more sophisticated coin selection that protects your privacy better. However this is indeed creating a lot of change in the wallet and if the changes are consolidated then all the smartness is for nothing, so I give a concept ACK to your suggestion.

Another alternative is that we could have 3 coin selection algorithm, where yours is the default.

1. Maximize Privacy - current one.
2. Default - Yours.
3. Consolidating - yours extended with trying to always register a coin with 2 small change. It could be smarter to consolidate like this than in one transaction.

As an exercise, let me walk you through our current mixing coin selection algorithm:

https://github.com/zkSNACKs/WalletWasabi/blob/ca7cb6123a5456e393b0f87651853d560c107e89/WalletWasabi/Models/ChaumianCoinJoin/CcjClientState.cs#L168-L271

Confirmation has largest priority. Wasabi will always want to register confirmed coins first than unconfirmed ones, because registering unconfirmed ones can ruin the user experience of others. This won't change.

https://github.com/zkSNACKs/WalletWasabi/blob/ca7cb6123a5456e393b0f87651853d560c107e89/WalletWasabi/Models/ChaumianCoinJoin/CcjClientState.cs#L178-L186

Then it says that you cannot register unconfirmed coins if it doesn't come from a coinjoin. This won't change.

https://github.com/zkSNACKs/WalletWasabi/blob/ca7cb6123a5456e393b0f87651853d560c107e89/WalletWasabi/Models/ChaumianCoinJoin/CcjClientState.cs#L197-L205

Next it says take the coins from the waiting list. So these are those coins those are queued and not already registered to a round. This won't change.

https://github.com/zkSNACKs/WalletWasabi/blob/ca7cb6123a5456e393b0f87651853d560c107e89/WalletWasabi/Models/ChaumianCoinJoin/CcjClientState.cs#L207

This line says to take the coins those don't have a "don't select me" timeout set. This is needed, because the backend propagates the coinjoin and we don't know that a coinjoin is propagated or the round failed until it's propagated to us through nodes or a sufficient amount of time is passed. For some reason I didn't want to trust the coordinator here to tell us if a round failed or not, not sure why. This won't change.

https://github.com/zkSNACKs/WalletWasabi/blob/ca7cb6123a5456e393b0f87651853d560c107e89/WalletWasabi/Models/ChaumianCoinJoin/CcjClientState.cs#L208

Next I have a for cycle from 1 to 7. I prefer to register the smallest number of coins, so if I find a good combination with 1, I break, I don't want to merge. I don't know if it should change.

https://github.com/zkSNACKs/WalletWasabi/blob/ca7cb6123a5456e393b0f87651853d560c107e89/WalletWasabi/Models/ChaumianCoinJoin/CcjClientState.cs#L215

Next I just collect coinGroups, which are lists of smartcoin lists. These are all the possible permutations a wallet can register coins in. If the computation gets too expensive, then perfectMode is turned off and just gives back one coin group, which is the largest one.

https://github.com/zkSNACKs/WalletWasabi/blob/ca7cb6123a5456e393b0f87651853d560c107e89/WalletWasabi/Models/ChaumianCoinJoin/CcjClientState.cs#L217-L241

From here on comes the interesting part. Precedence going from back to the forth. I'm doing ordering on these groups and then choose the first one. So the most important thing is to confirmation:

https://github.com/zkSNACKs/WalletWasabi/blob/ca7cb6123a5456e393b0f87651853d560c107e89/WalletWasabi/Models/ChaumianCoinJoin/CcjClientState.cs#L260

If only one coin is to be registered:

1. Prefer the one with the smallest anonset.
2. Among these prefer the largest one.

For example if you received 0.1BTC and 4BTC, then prefer registering 4BTC: then you'll provide others more anonymity, since you'll provide after 0.1, 0.2, 0.4, 0.8, 1.6 and 3.2 mixing levels instead of just 0.1 with a small coin.)

https://github.com/zkSNACKs/WalletWasabi/blob/ca7cb6123a5456e393b0f87651853d560c107e89/WalletWasabi/Models/ChaumianCoinJoin/CcjClientState.cs#L243-L250

If more then one coin is to be registered, coin merging will happen:

1. Try to register the largest anonymity set, so red and green coins input merging should be less likely.
2. Prefer the lowest amount sum, so perfect mix should be more likely.

https://github.com/zkSNACKs/WalletWasabi/blob/ca7cb6123a5456e393b0f87651853d560c107e89/WalletWasabi/Models/ChaumianCoinJoin/CcjClientState.cs#L251-L258

Thoughts on what to change?

[NicolasDorier]

@nopara73 I am not thinking of making automatic coin selection.
More like a one time button: Merge coins in a round without having a change.
I think automatic coin selection is very tricky, and personally I always end up picking manually what I want to mix.

[NicolasDorier]

Ah can I ask you what happen if I register one coin of X then the price of coinjoin raise above X because of the number of participants?

[NicolasDorier]

Ah also what is the minimum change output that wasabi is using? (where, if any value below this, the money is given to the coordinator or miners)

[nopara73]

Ah can I ask you what happen if I register one coin of X then the price of coinjoin raise above X because of the number of participants?

The smallest coin registration never pays any fee and those who don't have enough to pay the CJ fee will only pay as much as they have.

[nopara73]

Ah also what is the minimum change output that wasabi is using? (where, if any value below this, the money is given to the coordinator or miners)

Money minimumOutputAmount = Money.Coins(0.0001m); // If the change would be less than about $1 then add it to the coordinator.
Money somePercentOfDenomination = newDenomination.Percentage(0.7m); // If the change is less than about 0.7% of the newDenomination then add it to the coordinator fee.
Money minimumChangeAmount = Math.Max(minimumOutputAmount, somePercentOfDenomination);

Where newDenomination is always the base denomination.

[nopara73]

More like a one time button: Merge coins in a round without having a change.

We cannot clutter the UI, rather we should make it simpler: #1369

[Kortik7]

to make it simpler is there a way to highlight change utxo in some color that will make a user pay attention and when you point your mouse over that utxo it will warn not to mix change with high annon utxo's. Lots of users do not understand and do exactly what I said. therefore it affects other users when we coinjoin. Correct me if I am wrong?

[nopara73]

Fixes? #1652

[nopara73]

@Kortik7 Do you mean red change UTXO? There's nothing that helps the user make the decision except that it's red and other ones are green :/

[Kortik7]

I talked to Aviv and David about this at SF2019 conference.
I was asking about zero link change utxos it is already red and when you point mouse on it it shown anon set.
What I meant

is for users to have some kind of educated reminder. that when you point your mouse to that zero link change utxo it should say "please do not mix change with already mixed coins". Do you understand what I am suggesting? maybe it is not necessary but according to my reading on telegram lots of people mix zero link change with already high anonn set mixed coins.

[nopara73]

@NicolasDorier Actually what you want is to find the closest subset sum to the denomination. Maybe this should be the first algorithm? And if the closest isn't close enough fall back to my algorithm.

https://www.geeksforgeeks.org/subarray-whose-sum-is-closest-to-k/

[nopara73]

@Kortik7 That's a great idea and easy to implement. I opened an issue: #1653

[NicolasDorier]

@nopara73 then I have an idea I think. A selection algorithm that always select UTXOs to minimize the fees.
This eventually reach the same result.

[NicolasDorier]

Basically calling the two selection algorithm:

• Maximize Privacy
• Make it cheap

It would not select red coins if those make a change.
It would not select already fully mixed coin (checked state)

[NicolasDorier]

Where should be the settings for that? In the settings windows?

[Kortik7]

@NicolasDorier it possible to ingrate that by default without even needing a setting option, should be automatic without users knowing it.

[NicolasDorier]

@Kortik7 well, the user wants probably to configure by themselves wether they want cheap coinjoin or maximum privacy one.

[nopara73]

Yeah, trying to find closest subset sum before my algo may be the smartest thing to do. It may result in unnecessary coin merging, but rather merge now in a cj than later in a noncj.
The algo should also pay attention as Nicolas said to not accidentally end up in the 0.7pc upper range.

[nopara73]

@Kortik7 well, the user wants probably to configure by themselves wether they want cheap coinjoin or maximum privacy one.

The user will ruin his privacy by consolidating the change in a much worse way.

[nopara73]

Hmm, thinking about it, maybe Nicolas is right. If this algo would mix red with non-red coins that's instant deanonymization, so it's not a good idea, other than adding an option, so the fee algo try to find the cheapest combo.

[NicolasDorier]

I have a better idea actually, very easy to explain in the UX: A parameter in settings called never produce a change.

Then the user would just queue all his coins, and when wasabi detect a round where it can queue without producing change, it register it automatically.

[MaxHillebrand]

I like the idea, but what when the user selects an amount MUCH larger than the round?
Will it then never register that coin, because it would always generate change?

It seems that your idea is only useful for a very narrow range of denomination?

[NicolasDorier]

@MaxHillebrand it would works as most of the time large amount can be remixed by multiple of 0.1

[NicolasDorier]

Or maybe "Avoid change for small denominations"

[MaxHillebrand]

A wild idea - how about some form of DBC for small change?
The change goes into the wallet of zkSnacks, and the user gets the eCash token, which at a later point in time, he can register for coin join and then get larger as another input.

I know - huge change to the protocol, and it would make zkSnacks somewhat of a custodian [depending how you view DBC servers...] so this is most likely out of the question for the short term, rather something to think about.

[MaxHillebrand]

2.0 change avoidance is a brilliant to solution to exactly this problem.

really well done guys!