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

[Yuval Kogman <nothingmuch@woobling.org>]

[-- 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 --]