Subject: Re: [bitcoin-dev] Non-equal value CoinJoins. Opinions.

From: nopara73 <[email-masked]>
Date: Sat, 22 Feb 2020 19:01:14 +0100

>  It seems to me that most users will not have nearly the same output of
"around 1 BTC"

While that would be true out of context, it depends on how you interpret it
and they interpret it really broadly: " One input might be 0.03771049 BCH;
the next might be 0.24881232 BCH, etc. "

> anyway if you deploy this on a real live mainnet, and if your math
requires that you have "around 1 BTC" outputs per user. you might as well
just use equal-valued CoinJoins, where the equal-valued outputs at least
are completely unlinked from the inputs.
>  e.g. if you have a CashFusion transaction with outputs 1.0, 1.1, 0.99,
you could transform that to a CoinJoin with 0.99, 0.99, 0.99, 0.01, 0.11
outputs.

Equal valued coinjoins (1) waste more blockspace as your example
illustrates and (2) prevent arbitrary amounts, so you cannot send in
coinjoins.

> Indeed, the change outputs of an equal-valued CoinJoin would have similar
analyses to CashFusion, since the same analysis "around 1 BTC" can be
performed with the CoinJoin change outputs "around 0 BTC".

I've been wondering about this too. I think it cannot be applied to
existing CoinJoin schemes, as coin selection heuristics are quite a help
and that could be a reason why the changes can be deanonymized (I assume.)
For example if I want to analyze a Wasabi CJ, then I assume every input
that have > 0.1 BTC value to be THE valid input partition and I will only
look for the valid matching partition on the output side. I won't try to
find all the partitions and look at all the possible subset sums. (
https://github.com/nopara73/Notes/blob/master/BellNumber.md,
https://github.com/nopara73/Notes/blob/master/SubSetSum.md)

At the very least coin selection for equal value coinjoins can be relaxed
to remove such assumptions and make the above math applicable for the
change. (If works.)

On Sun, Dec 29, 2019 at 12:25 AM ZmnSCPxj <[email-masked]> wrote:

> Good morning Adam,
>
> > The CashFusion research came out of the Bitcoin Cash camp, thus this
> probably went under the radar of many of you. I would like to ask your
> opinions on the research's claim that, if non-equal value coinjoins can be
> really relied on for privacy or not.
> >
> > (Btw, there were also similar ideas in the Knapsack paper in 2017:
> https://www.comsys.rwth-aachen.de/fileadmin/papers/2017/2017-maurer-trustcom-coinjoin.pdf
>  )
> >
> >
> https://github.com/cashshuffle/spec/blob/master/CASHFUSION.md#avoiding-amount-linkages-through-combinatorics
>
> >
> > I copy the most relevant paragraphs here:
> >
> >   ---------BEGIN QUOTE ---------
> >
> >
> > Consider a transaction where 10 people have each brought 10 inputs of
> arbitary amounts in the neighborhood of ~0.1 BCH. One input might be
> 0.03771049 BCH; the next might be 0.24881232 BCH, etc. All parties have
> chosen to consolidate their coins, so the transaction has 10 outputs of
> around 1 BCH. So the transaction has 100 inputs, and 10 outputs. The first
> output might be 0.91128495, the next could be 1.79783710, etc.
> >
> > Now, there are 100!/(10!)^10 ~= 10^92 ways to partition the inputs into
> a list of 10 sets of 10 inputs, but only a tiny fraction of these
> partitions will produce the precise output list. So, how many ways produce
> this exact output list? We can estimate with some napkin math. First,
> recognize that for each partitioning, each output will typically land in a
> range of ~10^8 discrete possibilities (around 1 BCH wide, with a 0.00000001
> BCH resolution). The first 9 outputs all have this range of possibilities,
> and the last will be constrained by the others. So, the 10^92 possibilies
> will land somewhere within a 9-dimensional grid that cointains
> (10^8)^9=10^72 possible distinct sites, one site which is our actual output
> list. Since we are stuffing 10^92 possibilties into a grid that contains
> only 10^72 sites, then this means on average, each site will have 10^20
> possibilities.
> >
> > Based on the example above, we can see that not only are there a huge
> number of partitions, but that even with a fast algorithm that could find
> matching partitions, it would produce around 10^20 possible valid
> configurations. With 10^20 possibilities, there is essentially no linkage.
> The Cash Fusion scheme actually extends this obfuscation even further. Not
> only can players bring many inputs, they can also have multiple outputs.
> >
> > ---------END QUOTE ---------
> > --
>
>
> It seems to me that most users will not have nearly the same output of
> "around 1 BTC" anyway if you deploy this on a real live mainnet, and if
> your math requires that you have "around 1 BTC" outputs per user. you might
> as well just use equal-valued CoinJoins, where the equal-valued outputs at
> least are completely unlinked from the inputs.
>
> Indeed, the change outputs of an equal-valued CoinJoin would have similar
> analyses to CashFusion, since the same analysis "around 1 BTC" can be
> performed with the CoinJoin change outputs "around 0 BTC".
>
> * You can always transform a CashFusion transaction whose outputs are
> "around 1 BTC" to a CoinJoin transaction with equal-valued outputs and some
> change outputs, with the equal-valued outputs having equal value to the
> smallest CashFusion output.
>  * e.g. if you have a CashFusion transaction with outputs 1.0, 1.1, 0.99,
> you could transform that to a CoinJoin with 0.99, 0.99, 0.99, 0.01, 0.11
> outputs.
> * Conversely, you can transform an equal-valued CoinJoin transaction to a
> CashFusion transaction using the same technique.
> * That implies that the change outputs of an equal-valued CoinJoin have
> the same linkability as the outputs of the equivalent CashFusion
> transaction.
> * At least with equal-valued CoinJoin, the equal-valued outputs have 0
> linkability with inputs (at least with only that transaction in isolation).
>   The same cannot be said of CashFusion, because the value involved is
> just in a single UTXO.
>
> Regards,
> ZmnSCPxj
>

-- 
Best,
Ádám