public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: Yuval Kogman <nothingmuch@woobling.org>
To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Non-equal value CoinJoins. Opinions.
Date: Sun, 29 Dec 2019 17:48:38 +0000	[thread overview]
Message-ID: <CAAQdECCCPL1jezCpFEbj=9r5=ho33dfvd=AQCzGpczKKrD8omw@mail.gmail.com> (raw)
In-Reply-To: <Ucl9pe26g2ECz-SRmXPV3WLxVR8PBOf0dnMR_aD8NwTqBNmq6e3a9hKJtwkYPJz7v_QUCxT_Y5X0w1VkvbiQZ6H3QJVcOtpUhNYTQ29rwFA=@protonmail.com>

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

  reply	other threads:[~2019-12-29 18:14 UTC|newest]

Thread overview: 9+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-12-27 18:03 [bitcoin-dev] Non-equal value CoinJoins. Opinions nopara73
2019-12-28 17:38 ` Ethan Heilman
2019-12-28 23:25 ` ZmnSCPxj
2020-02-22 18:01   ` nopara73
2019-12-29  3:31 ` Yuval Kogman
2019-12-29  9:57   ` Yuval Kogman
2019-12-29 10:23   ` ZmnSCPxj
2019-12-29 17:48     ` Yuval Kogman [this message]
2019-12-30  1:14 ` Lucas Ontivero

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to='CAAQdECCCPL1jezCpFEbj=9r5=ho33dfvd=AQCzGpczKKrD8omw@mail.gmail.com' \
    --to=nothingmuch@woobling.org \
    --cc=ZmnSCPxj@protonmail.com \
    --cc=bitcoin-dev@lists.linuxfoundation.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox