MIME-Version: 1.0
References: <CAEPKjgdtgDbyLoj6FV+cjY1Djca_FBtd9Kt_eB4zWU+at=wfYQ@mail.gmail.com>
 <CAAQdECBqFKxAoZXCkWynN4wj5g8C9vzdhuEWk9b-BYqDW=us6g@mail.gmail.com>
 <Ucl9pe26g2ECz-SRmXPV3WLxVR8PBOf0dnMR_aD8NwTqBNmq6e3a9hKJtwkYPJz7v_QUCxT_Y5X0w1VkvbiQZ6H3QJVcOtpUhNYTQ29rwFA=@protonmail.com>
In-Reply-To: <Ucl9pe26g2ECz-SRmXPV3WLxVR8PBOf0dnMR_aD8NwTqBNmq6e3a9hKJtwkYPJz7v_QUCxT_Y5X0w1VkvbiQZ6H3QJVcOtpUhNYTQ29rwFA=@protonmail.com>
From: Yuval Kogman <nothingmuch@woobling.org>
Date: Sun, 29 Dec 2019 17:48:38 +0000
Message-ID: <CAAQdECCCPL1jezCpFEbj=9r5=ho33dfvd=AQCzGpczKKrD8omw@mail.gmail.com>
To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Content-Type: multipart/alternative; boundary="000000000000f0b2bb059adb5661"
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Non-equal value CoinJoins. Opinions.
Precedence: list

--000000000000f0b2bb059adb5661
Content-Type: text/plain; charset="UTF-8"

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).

--000000000000f0b2bb059adb5661
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div>Hi,<br></div><br><div class=3D"gmail_quote"><div dir=
=3D"ltr" class=3D"gmail_attr">On Sun, 29 Dec 2019 at 10:23, ZmnSCPxj &lt;<a=
 href=3D"mailto:ZmnSCPxj@protonmail.com">ZmnSCPxj@protonmail.com</a>&gt; wr=
ote:<br></div>=C2=A0<blockquote class=3D"gmail_quote" style=3D"margin:0px 0=
px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
Indeed, this is a problem still of equal-valued CoinJoin.<br>
In theory the ZeroLink protocol fixes this by strongly constraining user be=
havior, but ZeroLink is not &quot;purely&quot; implemented in e.g. Wasabi: =
Wasabi still allows spending pre- and post-mix coins in the same tx (ZeroLi=
nk 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.<br></blockquote><div><br></div><div>Yes, altho=
ugh since the base denomination size is pretty large this can be very limit=
ing, possibly forcing these change outputs to be linked to each other or, w=
orse, with unmixed inputs which is still a serious linkage concern. This is=
 further complicated due to variability of the denomination (which makes re=
mixing possible due to the fee structure, but see below) also leaks some in=
formation or requires linking of mixed outputs in addition (although this r=
esets its notion of anonymity set size, so I don&#39;t consider this unsafe=
 or misleading, just wasteful) or in change being donated to the coordinato=
r due to not meeting the threshold, depending on the &quot;phase angle&quot=
; between a user&#39;s past mixes and the coordinator&#39;s current denomin=
ation.</div>=C2=A0<blockquote class=3D"gmail_quote" style=3D"margin:0px 0px=
 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
Equal-valued CoinJoins fix this by using a Chaumian bank, which constrains =
value transfers to specific fixed amounts.<br>
Since an equal-valued CoinJoin uses a single fixed amount anyway, it is not=
 an additional restriction.<br>
CashFusion cannot use the same technique without dropping into something ve=
ry much like an equal-valued CoinJoin. <br></blockquote><div><br></div><div=
>I concur. <br></div></div><div class=3D"gmail_quote"><div><br></div><div>I=
 need to write a proper account of what I alluded to in my last email, but =
here&#39;s a summary (allowing myself to keep it in this thread as the subj=
ect was unequal amounts and opinions ;-)<br></div><div><br></div><div>1. in=
troduce another stage between the input/output phases - at input registrati=
on you would receive chaumian reissuable/redenominatable tokens after deduc=
tion of per input fees, which you can then &quot;spend&quot; to create outp=
uts (instead of the chaumian token itself being an output script)</div><div=
><br></div><div>2. replace the current notion of a mixing round into severa=
l sub-types:</div><div>=C2=A0 - &quot;decompose&quot; - take an arbitrary a=
mount and produce popcount(amount-fees) outputs with popcount =3D 1 (anon s=
et size assumed to be 1)<br></div><div>=C2=A0 - &quot;mix&quot; - mix popco=
unt =3D=3D 1 amounts with equal sized outputs - this is the only round type=
 that can increase anon set size<br></div><div>=C2=A0 - &quot;optimize&quot=
; - convert mixed, popcount =3D=3D 1 (e.g. { 2^n} &lt;-&gt; { 2^(n-1), 2^(n=
-1) } ) - it&#39;s not clear to me to what anon set size should be consider=
ed after this, probably reset to somewhere between 1 and the minimum size o=
f the inputs, depending on degree of linkage<br></div><div>=C2=A0 - &quot;c=
ombine&quot; - spend popcount =3D=3D 1 outputs to produce arbitrary amounts=
</div><div><br></div><div>Note that simultaneous rounds can be merged by th=
e server during the signing phase, such so that for example a &quot;decompo=
se&quot; output may benefit from inhabiting the same CoinJoin transaction a=
s a mixing round with the same denomination, but the coordinator would stil=
l 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 ad=
versary&#39;s job harder given only public data).</div><div><br></div><div =
class=3D"gmail_quote">In order to preserve the exact denomination size for =
mixing transactions, such rounds would need to have their mining fees subsi=
dized - this can be accomplished by such merging, with the coordinator disc=
ounting or subsidizing input/output registration fees depending on the degr=
ee of mixing (a la Samourai/Whirlpool&#39;s mechanism design), or using som=
e sort of prepaid mechanism (e.g. as part of a mixing round instead of a re=
gistered output you might elect to receive long lived - as in not per round=
 - chaumian tokens that can be redeemed for fee-less, round denomination mi=
xing, which can be reissued if the signing phase fails). In both cases I=
9;m assuming the coordinator includes an input to cover the mining fees. </=
div><div class=3D"gmail_quote"><br></div></div><div>I find the privacy aspe=
cts much easier to think about in this model, and it addresses many things =
of zerolink&#39;s weaknesses:</div><div><br></div><div>1. allows unequal am=
ounts 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 co=
rresponding to actual amount distribution being used (for mining &amp; coor=
dination fees too, but more generally any amounts used for any Bitcoin paym=
ent)</div><div><br></div><div>2. it can potentially eliminate post mix chan=
ge (if I want to spend some amount x =3D \sum{i=3D1..~40} a_i*2^i, and i ha=
ve exactly the combination specified by the a_i&#39;s) which the server can=
 also enforce by restricting &quot;combine&quot; rounds to require &quot;op=
timize&quot; rounds before them</div><div><br></div><div>3. increases priva=
cy benefit of remixing while still removing Wasabi&#39;s round denomination=
 decreases, especially over long time intervals</div><div><br></div><div>Th=
e main issue, which I stress is significant, is the bloat - many such round=
s are required, with many inputs and outputs per user per round, and many U=
TXOs per user on average. This can be alleviated to a certain degree by bat=
ching. Although this leaks information about payment linkage post mix which=
 can be attacked by partitioning, the risk is still mitigated since the amo=
unts themselves are low hamming weight and since consolidations still happe=
n in mixing rounds. Since the intra-round tokens are reissuable, they are t=
ransferable as well, so this effectively makes everything into a payment hu=
b protocol (e.g. if Alice wants to pay Bob and Carol, registers an input re=
ceiving tokens, splits those as necessary to accommodate the payment &amp; =
change amounts, and transfers some subsets to Bob and Carol, who are free t=
o 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 protoc=
ol (see also our private correspondence of some months ago), but naively th=
is approach makes many tradeoffs like a slight departure from CoinJoin&#39;=
s notion of trustless mixing or requiring interaction between participants =
post-mix (which introduces new privacy concerns, or at least significant co=
mplexity). Since covenants were re-raised, and specifically OP_STB/CTV&#39;=
s approach to congestion control and multiparty payment channels in the con=
text of Taproot &amp; SIGHASH_NOINPUT/ANYPREVOUT etc. I believe that this a=
pproach can actually made to be size efficient by just keeping the low hamm=
ing weight outputs virtual, but I still haven&#39;t worked this out in deta=
il (still overwhelmed by the size of this design space).<br></div></div>

--000000000000f0b2bb059adb5661--