[bitcoin-dev] Non-equal value CoinJoins. Opinions.

[bitcoin-dev] Non-equal value CoinJoins. Opinions.

[nopara73]

[-- Attachment #1: Type: text/plain, Size: 2434 bytes --]

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 ---------
-- 
Best,
Ádám

[-- Attachment #2: Type: text/html, Size: 3716 bytes --]

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

[Ethan Heilman]

I'm only going to talk about cashfusion and not the knapsack paper.

The language they use to describe the cashfusion protocol is very
broad and could describe many things. Because it is hard so vague I
don't want to dismiss the cashfusion approach out of hand. For
instance they say: "inputs of arbitary amounts in the neighborhood of
~0.1 BCH" what exactly does this mean?

Attack 1:
If we assume arbitrary means any precision then a trivial attack is
possible. Consider the case where one of the inputs has more precision
than any other input. This allows an attacker to trivially break the
privacy of that input:

Lets look at a toy example that takes 12 inputs and creates 3 outputs
inputs:
0.1525
0.1225
0.1145
0.1443
0.1144111
0.1001
0.1124
0.1093
0.1113
0.1134
0.1029
0.1206

Outputs:
0.4648111
0.5185
0.4349

Clearly output output 0.4648111 contains input 0.1144111.

Attack 2:
Let's say you attempt to address this problem this by limiting the
precision of inputs to two decimal places i.e. 0.1X where 0<=X<=9.
Consider the case of 10 users where each user is always joining sets
of 10 inputs to create 1 output. Thus in total you would have 100
inputs and 10 outputs in the coinjoin. If one of those outputs is 2
then you know its inputs must all be 0.2. Using this method you can
start eliminate input output pairs far faster brute force. How much
faster is hard to say without adding additional assumptions for
instance are these inputs amounts drawn from a uniform distribution?

I want to be clear. I'm not saying cashfusion is broken or that this
more inputs than outputs technique is a dead end. However the
description given is vague and could be interpreted to describe a
broken protocol. Is this actively being used?

On Fri, Dec 27, 2019 at 8:29 PM nopara73 via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
>
> 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 ---------
> --
> Best,
> Ádám
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

[ZmnSCPxj]

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

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

[Yuval Kogman]

[-- Attachment #1: Type: text/plain, Size: 7603 bytes --]

Hi,

On Sat, 28 Dec 2019 at 01:29, nopara73 via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

I haven't read the whole thing in detail (and fwiw, I don't think I will by
this point), but I do want to respond to section about the combinatorics as
well as the proof, since both the premises and the implications don't seem
very solid to me, especially in light of the other replies in this thread.

It appears to be a step up from the Knapsack paper in terms of the
specificity of a concrete mixing protocol (which again, I did not
scrutinize, but see below), but a regression in terms of privacy (see other
replies), which even in the Knapsack paper's approach raises some concerns:

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.
>
In the equal amount case, the search space of possible interpretations with
n = # inputs + # indistinguishable outputs is proportional to the nth Bell
number, i.e. it's exponential in the size of the transaction, which is an
inviting intuition. But this is an *upper* bound on the difficulty of
deanonymization, given no additional information.

This quantitative framing is potentially misleading because:

1. attributing inputs/outputs (sub-transactions in the Knapsack paper's
terminology) is arguably not a search problem, but an optimization problem,
since approximate results are still partly useful to the adversary
2. there are many computational strategies, heuristics, etc that in
practice can make this more efficient than brute force[1], so framing it
that as a security parameter doesn't sit right with me
3. as individual sub-transactions are identified (for example using out of
band information), the computational challenge also *drops* exponentially
fast

Additionally (though is a broader criticism of CoinJoin based privacy and
not specific to unequal amounts, and in particular refers to ZmnSCPxj's
assertion of 0 linkability) I am very worried that perspectives that focus
on linkability information revealed by a single coinjoin transaction in
isolation. This problem was alluded in the document, to but I don't see
that it was addressed. Naively the post/pre mix transaction graph would
seem to present a computationally much harder problem when looking at the
combinatorics through the same lens, but reality it can also be used to
place many constraints on valid partitions/sub-transaction assignments for
a single transaction with equal amounts. The trivial example is post mix
linking of outputs, but there are many other ways to draw inferences or
eliminate possible interpretations of a single transaction based on its
wider context, which in turn may be used to attack other transactions.


> 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.
>
This is a better framing, but still doesn't address my third bullet, since
"Attacks always get better; they never get worse." In other words
"essentially no linkage" due to multiple possible interpretation is still
strictly more meaningful if you can add constraints out of band.

To be fair in equal amount CoinJoins this is also the case, but it's a much
simpler model to consider in the context of other privacy leak vectors
(e.g. transaction graph connectivity beyond a single coinjoin, wallet
fingerprinting, temporal patterns, network privacy leaks, etc etc), since
analyzing your level of exposure is *also* complicated by unequal amounts,
in other words higher chance of privacy leaks due to misuse, or ignorance
of some of the implications under intended use. Thinking through these
implications is much easier when the information content in the amounts is
minimized.

The Cash Fusion scheme actually extends this obfuscation even further. Not
> only can players bring many inputs, they can also have multiple outputs
>
And, quoting another section:

Unfortunately, the production of equal-amount coins is impractical for
> various reasons. Foremost, it has a "toxic waste"
>

I'm still cautiously optimistic about the potential of multiple
inputs/outputs per user (c.f. 3-phase chaumian CoinJoin ideas we've
previously discussed in the context of Wasabi, though I don't recall any
public discussion I can link to, sorry list), but with the additional
assumption of amounts with small popcounts/Hamming weights (e.g. only
amounts that are 2^n sat in size, or based on 1-2-5 series, and for a
rationale see Ethan's reply).

Unfortunately this trades off that "toxic waste" problem for a very large
on chain footprint (e.g. if the popcount of the amount of a wallet is
limited to 1, the number of inputs and change outputs required in the worst
case is proportional to log of the payment amount) and significant UTXO
bloat (several mixed outputs per magnitude for transaction size to scale as
the popcount(payment amount) instead of the log(payment amount))

However, with OP_CHECKTEMPLATEVERIFY and Taproot, this overhead could
potentially be mitigated (something more like TumbleBit's privacy model,
but with an on chain footprint similar to multiparty payment channels as
described in the OP_CTV BIP draft) since the safety guaranteed by
CoinJoins' atomicity can be preserved without requiring atomicity of the
mixing itself, which can extend over multiple transactions and long time
intervals, while still providing the liquidity and finality and unilateral
exit option of payment channels. By moving such low hamming weight amount
outputs off chain, and allowing them to be mixed (with equal amounts),
split and merged off chain. The simpler analysis of equal amount outputs
could still be assumed which makes analysis easier and assumptions about
adversary weaker, and furthermore this approach would better align the
incentives for batching and privacy, which is why I think it's very
promising.

Finally, the proof as well as its applicability seems suspect to me, since
seems to involve trusting the server:
"Since the distinct list [...] [is] kept on the server and not shared with
the players"
"The server knows the linkages of the commitments but does not participate
as a verifier "
"If there is a problem [...] each component is assigned to another player
at random for verification"
these 3 statements together seems to suggest the server is trusted to not
use sybils in order the compromise privacy by participating in the
verification process?

(also, and although this is nitpicking, also does not seem to be
demonstrating "soundness" in any sense that I am familiar with - wouldn't
break in soundness only imply DoS vector?)

[1] btw, although I still owe you (nopara73) some consistently working
linear programming code to attribute change outputs in Wasabi (sorry! i
suck...), but anecdotally, in the special cases I did manage to solve even
transactions with tens of inputs do not present a challenge even to
supposedly slow/inefficient solvers compared to the state of the art. Even
though it's just anecdotal and in the context of the easier problem of
attributing change, which can still be ambiguous in Wasabi transactions, i
still think this puts into question the privacy of mixing based on a
dubious hardness assumption and a computationally bounded adversary, as
opposed to something which (in the scope of a single mixing transaction) is
perfectly hiding.

[-- Attachment #2: Type: text/html, Size: 10039 bytes --]

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

[Yuval Kogman]

[-- Attachment #1: Type: text/plain, Size: 253 bytes --]

On Sun, 29 Dec 2019, 05:31 Yuval Kogman, <nothingmuch@woobling.org> wrote:

> n = # inputs + # indistinguishable outputs
>

sorry, this is really wrong (although of no consequence to my arguments) -
n is the smaller of these two numbers, not their sum.

[-- Attachment #2: Type: text/html, Size: 689 bytes --]

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

[ZmnSCPxj]

Good morning Yuval,


> Additionally (though is a broader criticism of CoinJoin based privacy and not specific to unequal amounts, and in particular refers to ZmnSCPxj's assertion of 0 linkability) I am very worried that perspectives that focus on linkability information revealed by a single coinjoin transaction in isolation. This problem was alluded in the document, to but I don't see that it was addressed. Naively the post/pre mix transaction graph would seem to present a computationally much harder problem when looking at the combinatorics through the same lens, but reality it can also be used to place many constraints on valid partitions/sub-transaction assignments for a single transaction with equal amounts. The trivial example is post mix linking of outputs, but there are many other ways to draw inferences or eliminate possible interpretations of a single transaction based on its wider context, which in turn may be used to attack other transactions.

Indeed, this is a problem still of equal-valued CoinJoin.
In theory the ZeroLink protocol fixes this by strongly constraining user behavior, but ZeroLink is not "purely" implemented in e.g. Wasabi: Wasabi still allows spending pre- and post-mix coins in the same tx (ZeroLink disallows this) and any mix change should be considered as still linked to the inputs (though could be unlinked from the equal-valued output), i.e. returned to pre-mix wallet.

> Finally, the proof as well as its applicability seems suspect to me, since seems to involve trusting the server:
> "Since the distinct list [...] [is] kept on the server and not shared with the players"
> "The server knows the linkages of the commitments but does not participate as a verifier "
> "If there is a problem [...] each component is assigned to another player at random for verification"
> these 3 statements together seems to suggest the server is trusted to not use sybils in order the compromise privacy by participating in the verification process?

Equal-valued CoinJoins fix this by using a Chaumian bank, which constrains value transfers to specific fixed amounts.
Since an equal-valued CoinJoin uses a single fixed amount anyway, it is not an additional restriction.
CashFusion cannot use the same technique without dropping into something very much like an equal-valued CoinJoin.

Regards,
ZmnSCPxj

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

[Yuval Kogman]

[-- Attachment #1: Type: text/plain, Size: 6613 bytes --]

Hi,

On Sun, 29 Dec 2019 at 10:23, ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:

>
> Indeed, this is a problem still of equal-valued CoinJoin.
> In theory the ZeroLink protocol fixes this by strongly constraining user
> behavior, but ZeroLink is not "purely" implemented in e.g. Wasabi: Wasabi
> still allows spending pre- and post-mix coins in the same tx (ZeroLink
> disallows this) and any mix change should be considered as still linked to
> the inputs (though could be unlinked from the equal-valued output), i.e.
> returned to pre-mix wallet.
>

Yes, although since the base denomination size is pretty large this can be
very limiting, possibly forcing these change outputs to be linked to each
other or, worse, with unmixed inputs which is still a serious linkage
concern. This is further complicated due to variability of the denomination
(which makes remixing possible due to the fee structure, but see below)
also leaks some information or requires linking of mixed outputs in
addition (although this resets its notion of anonymity set size, so I don't
consider this unsafe or misleading, just wasteful) or in change being
donated to the coordinator due to not meeting the threshold, depending on
the "phase angle" between a user's past mixes and the coordinator's current
denomination.

>
> Equal-valued CoinJoins fix this by using a Chaumian bank, which constrains
> value transfers to specific fixed amounts.
> Since an equal-valued CoinJoin uses a single fixed amount anyway, it is
> not an additional restriction.
> CashFusion cannot use the same technique without dropping into something
> very much like an equal-valued CoinJoin.
>

I concur.

I need to write a proper account of what I alluded to in my last email, but
here's a summary (allowing myself to keep it in this thread as the subject
was unequal amounts and opinions ;-)

1. introduce another stage between the input/output phases - at input
registration you would receive chaumian reissuable/redenominatable tokens
after deduction of per input fees, which you can then "spend" to create
outputs (instead of the chaumian token itself being an output script)

2. replace the current notion of a mixing round into several sub-types:
  - "decompose" - take an arbitrary amount and produce
popcount(amount-fees) outputs with popcount = 1 (anon set size assumed to
be 1)
  - "mix" - mix popcount == 1 amounts with equal sized outputs - this is
the only round type that can increase anon set size
  - "optimize" - convert mixed, popcount == 1 (e.g. { 2^n} <-> { 2^(n-1),
2^(n-1) } ) - it's not clear to me to what anon set size should be
considered after this, probably reset to somewhere between 1 and the
minimum size of the inputs, depending on degree of linkage
  - "combine" - spend popcount == 1 outputs to produce arbitrary amounts

Note that simultaneous rounds can be merged by the server during the
signing phase, such so that for example a "decompose" output may benefit
from inhabiting the same CoinJoin transaction as a mixing round with the
same denomination, but the coordinator would still be able to categorically
distinguish between these, so this should not be thought of as a robust
privacy improvement (but it does make some other adversary's job harder
given only public data).

In order to preserve the exact denomination size for mixing transactions,
such rounds would need to have their mining fees subsidized - this can be
accomplished by such merging, with the coordinator discounting or
subsidizing input/output registration fees depending on the degree of
mixing (a la Samourai/Whirlpool's mechanism design), or using some sort of
prepaid mechanism (e.g. as part of a mixing round instead of a registered
output you might elect to receive long lived - as in not per round -
chaumian tokens that can be redeemed for fee-less, round denomination
mixing, which can be reissued if the signing phase fails). In both cases
I'm assuming the coordinator includes an input to cover the mining fees.

I find the privacy aspects much easier to think about in this model, and it
addresses many things of zerolink's weaknesses:

1. allows unequal amounts but retains many of the advantages of fixed
denomination - the number of separate mixing pools would be at most
log(2.1e13), with their sizes corresponding to actual amount distribution
being used (for mining & coordination fees too, but more generally any
amounts used for any Bitcoin payment)

2. it can potentially eliminate post mix change (if I want to spend some
amount x = \sum{i=1..~40} a_i*2^i, and i have exactly the combination
specified by the a_i's) which the server can also enforce by restricting
"combine" rounds to require "optimize" rounds before them

3. increases privacy benefit of remixing while still removing Wasabi's
round denomination decreases, especially over long time intervals

The main issue, which I stress is significant, is the bloat - many such
rounds are required, with many inputs and outputs per user per round, and
many UTXOs per user on average. This can be alleviated to a certain degree
by batching. Although this leaks information about payment linkage post mix
which can be attacked by partitioning, the risk is still mitigated since
the amounts themselves are low hamming weight and since consolidations
still happen in mixing rounds. Since the intra-round tokens are reissuable,
they are transferable as well, so this effectively makes everything into a
payment hub protocol (e.g. if Alice wants to pay Bob and Carol, registers
an input receiving tokens, splits those as necessary to accommodate the
payment & change amounts, and transfers some subsets to Bob and Carol, who
are free to register their own output(s). Payment is finalized if the
mixing succeeds and the transaction is mined). That in turn led to thinking
of how payment channels or multiparty payment might be used in a Chaumian
CoinJoin protocol (see also our private correspondence of some months ago),
but naively this approach makes many tradeoffs like a slight departure from
CoinJoin's notion of trustless mixing or requiring interaction between
participants post-mix (which introduces new privacy concerns, or at least
significant complexity). Since covenants were re-raised, and specifically
OP_STB/CTV's approach to congestion control and multiparty payment channels
in the context of Taproot & SIGHASH_NOINPUT/ANYPREVOUT etc. I believe that
this approach can actually made to be size efficient by just keeping the
low hamming weight outputs virtual, but I still haven't worked this out in
detail (still overwhelmed by the size of this design space).

[-- Attachment #2: Type: text/html, Size: 7643 bytes --]

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

[Lucas Ontivero]

[-- Attachment #1: Type: text/plain, Size: 5103 bytes --]

This idea is not similar to the one in the knapsack paper because this one
is based only in the computational complexity of finding partitions that
match the outputs. However, and except in rare cases, there is only one
valid partition (solution) for each output, it doesn't introduce any
ambiguity. Knapsack, on the other hand, splits the original outputs in such
a way that there are many partitions (solutions) that match the a selected
group of outputs. For example, imagine 7 people decide to participate in a
coinjoin transaction with an arbitrary number of inputs (no more than 7
inputs each), imagine this is not a pay to yourself cj tx but a pay to
someone else cjtx instead such that there are at most 2 outputs for
participants (payment output and change output) in this case, configuring
the partitions search algorithm to restrict the search space to sets of 7
inputs maximum and 4 outputs maximum it found 14,599 valid transactions in
42mins 18secs
https://raw.githubusercontent.com/lontivero/Knapsack/master/data/knapsack-7-participants.txt

The same simulation with 8 participants under the same conditions found
35,781 valid transactions in about 4 hours. Finally, with 9 participants I
let it running all the day and it didn't finished. The point is that the
number of valid transactions grows so incredible fast that with 100
participants even if you find a way to find all the partitions that matches
a set of outputs (something near to impossible), there are no way to know
which of those are the real ones.

Also, the attacks on this mechanism look so simple that generate doubts.
Finally, I think the numbers in this proposal look weird because the
example is using 10 inputs and the amounts are in the "neighborhood of
~0.1btc" (what the heck does that mean?) and the sum of those are around
1btc. That means that it could work in a very specific scenario. Knapsack
is a general solution with good math behind and backtested against
historical data extracted from the bitcoin's blockchain.

In summary, in unequal inputs/outputs coinjoins knapsack is the best we
have at the moment (btw, it is not as effective as equal-outputs
transactions). This proposal is imo inferior and it is not supported by
good math.


El vie., 27 dic. 2019 a las 22:29, nopara73 via bitcoin-dev (<
bitcoin-dev@lists.linuxfoundation.org>) escribió:

> 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 ---------
> --
> Best,
> Ádám
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 6940 bytes --]

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

[nopara73]

[-- Attachment #1: Type: text/plain, Size: 6127 bytes --]

>  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 <ZmnSCPxj@protonmail.com> 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

[-- Attachment #2: Type: text/html, Size: 7304 bytes --]