Decompose change to standard denominations with anonset

[MaxHillebrand]

Currently the taker coordinates a round with his chosen parameters of the single equal denomination and count of makers. He knows the input clustering of all makers, and calculates sum inputs - equal denomination + fees = change value, allocating the entire change value in a single output. With a high likelyhood, there is no other output with the same sats value, the change as anonset 1. The maker only gets two outputs, [disregarding batched payments] one equal coin with anonset, and one change, this requires relatively little blockspace. This change output might reveal the input cluster of the corresponding maker.

The ambiguity of the change outputs might be improved by increasing the number of outputs created. The taker still requires every maker to be part in the denomination of his choice. But the taker and maker can create more "change" outputs in such a way, that at least some of them have anonset too. Since the taker knows all input clusters, he can coordinate the distribution of sats for each maker prefering that equal amount outputs are created. As more outputs are created, more blockspace is required and more fees have to be paid. However, the "quality" of the created coins improve. The effectiveness of this strategy depends on the nuances.

There can be a set of "global standard denominations", which takers prefer to use in their change amount organization. They can be low Hamming weight values. In Wasabi Wallet research, we figured a somewhat optimal set with powers of 2, powers of 3, powers of 10, 2x powers of 2, 2x powers of 3, 1-2-5 series. We did remove from the set some denominations which were close to each other, especially for higher values. [WalletWasabi/WalletWasabi/pull/7549] In our simulations this lead to an "efficient" decomposition of any input value to a handful of outputs. But maybe there is a different optimum in joinmarkets design.

Wasabi users don't know the input clusters, so users need to "guess" which denominations other users will choose, which we do with a frequency table analysis. Our approach works better with more inputs. However, this is not a problem in joinmarkets case, and thus the taker could probably decompose even more efficiently, creating more anonset in fewer outputs.

Prefering to create these standard denominations on the output side, has the cool benefit that when these coins remix, there is a chance that other users have the exact same amount, thus there is anonset on the input side too, a big improvement in subset ambiguity.

There is even a slight ambiguity increase for standard denomination coins which are the only output with this value. Because they can still be decomposed into numerous other standard denominations. I'm not sure how to correctly quantify or qualify this property though...

There will be nuances of how that Wasabi research can be applied to the design of joinmarket. I would guess that similarely with more inputs, the change amount ambiguity increases, so maybe adapt the strategy in rounds with low maker count.

Both the maker and the taker could now create more outputs, and the question is how to fairly pay for these. I am not sure how exactly the blockspace fee is handled currently, and how this proposal would change it.

If users makes batched payments in the coinjoin, those outputs likely don't have a standard denomination [well, there is the 1-2-5 series in the set, which handles rounded sat amounts nicely]. But still, non standard anonset 1 coins are likely payment outputs. This fingerprint does not exist in the current one change output design. However, it can be built in a way that the standard denominations are only prefered up to a certain point, and a non standard change output is still created. This might decrease blockspace usage, decrease anonset per coin, but increase the ambiguity if any output is a payment output.

Here an example of a testnet Wasabi coinjoin with these standard denominations. Notice this was with an outdated amount organizer and coin selector, current master has some improvements.

[openoms]

Currently all the miner (and coinjoin) fees are paid by the Taker.
The option for Makers to contribute miner fees from their part of coinjoin fees is deprecated (defaults to 0 now).

The benefit of creating more equal amount outputs (cj-outs) is clear, but with the trade-off of blowing up the number of coins in the wallets further.

Running a Maker small change is created often already so when considering this I would like to avoid (or be able to configure) the lowest denomination a wallet would get from this new strategy.
For example WW2 on testnet goes down to 5000 sats. I think a sane default for joinmarket could start at 100k sats (which is default minsize for coinjoin already (+/- 10 % randomization))

[kristapsk]

Related - #994

[openoms]

Given that #994 only needs to update the Taker script the change to that is much more viable (only the Taker needs to update / opt-in) also it does not generate additional outputs for the Makers.

The downside compared to this proposal is that there would be no cases where the inputs would be the same size (or multiples of each other).

In the case when the Taker is sending a sweep (with no change created) decomposing the Maker's change would give some additional privacy benefit for the Makers - and maybe help with with having uniform inputs in later transactions.

[MaxHillebrand]

Since this improves the privacy of the maker, I would argue that he has more reason to pay for the blockspace, and not the taker.

So some maker fee contribution would have to be reintroduced, which will probably be complex.

I'd be very curious to learn more about how efficient a taker can decompose with high anonset count, given that he knows the input cluster. The extra blockspace for this might be surprisingly low...

Arguably there is more ambiguity when consolidating standard denomination inputs, rather than unique ones. Not sure about this claim. At least the taker will know the exact input clustering anyhow, but it might mislead a passive blockchain observer.

[kristapsk]

@MaxHillebrand Thanks for bringing up this topic!

I think we should look more at #994 and do review on that one, it's pretty simple and elegant.

[AdamISZ]

I realise the discussion is quite old now, but is it reasonable to close this in favour of #994 on the basis that people in the discussion seem to prefer that model?

[MaxHillebrand]

Yes, it'll be here for future reference.