From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from fraxinus.osuosl.org (smtp4.osuosl.org [140.211.166.137]) by lists.linuxfoundation.org (Postfix) with ESMTP id 7BCF0C077D for ; Sun, 29 Dec 2019 18:14:44 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by fraxinus.osuosl.org (Postfix) with ESMTP id 65A708445A for ; Sun, 29 Dec 2019 18:14:44 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from fraxinus.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id eEecVcAEIs2p for ; Sun, 29 Dec 2019 18:14:41 +0000 (UTC) X-Greylist: delayed 00:18:22 by SQLgrey-1.7.6 Received: from mail-pg1-f193.google.com (mail-pg1-f193.google.com [209.85.215.193]) by fraxinus.osuosl.org (Postfix) with ESMTPS id 836128414F for ; Sun, 29 Dec 2019 18:14:41 +0000 (UTC) Received: by mail-pg1-f193.google.com with SMTP id s64so16971144pgb.9 for ; Sun, 29 Dec 2019 10:14:41 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=woobling.org; s=google; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=Fl5gYDjDcp/FF/Y2EF+KHjlaHmp6wY1AxI9zWPEw7ME=; b=mPI8bDCswUVTb9D6TvfSKgR62twupeK1XdUVNCUf2zy7OoGTnw0MagabVvVLKIEXPj meZj6+dBOBvqoZw9E6IM61JXzTUFC/H1tJKVfQ9U+cJZ4CSlE9BoULtxZ7KulTv44Uzv siF9avNYslvPrYWF95PJd4QOXselPdBQ4aWK8= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=Fl5gYDjDcp/FF/Y2EF+KHjlaHmp6wY1AxI9zWPEw7ME=; b=BRv7Rtol/vR+wyS+YYpPa82VSML2mxmN2j9sO9JvlzI8G6VSrPIvt77NRK10KFL70N nDetNMO3eFp+qIlKlE/sCYksQ1I8q6UnaEEtwz+ivbBUE+XTvMzvWoFnXzGcTn66UpeZ LfSZBGyI26QKjSFTWaccwrhxuWCylLGtDFivpDD24VM1lIIurP6RdIVjDt9lKpx2bne8 Ijx9nskS2zzkd5CLEVGRWxNpd0RtpI2rw/uDd7eio52JAFD7RI4jERnsYgKdF7FWz1yG 3wAAAOayfht6S3In4bftX1kH4WNaEjpsrh2004Txi8/n+uKZkbyYVI+j/IsXsbVENZZk 435A== X-Gm-Message-State: APjAAAVIDLNRKYCjUg/fbv10E8z8FmsGsDsNXpPHpk/sqPS3mjqF0avc g3an/OF0aJfCIrYoUuKRsOAdAve7BJ1TvtvRgQ7SGJRnAcY= X-Google-Smtp-Source: APXvYqx7Nxrsz++QahfnhI+tFynHbs/nb7NfuaV8EG6H2kL9pjHy69jjI5NE3yStGRx0T85y/ixo1WPLUjGBQ4UcAQw= X-Received: by 2002:aa7:9e82:: with SMTP id p2mr59651331pfq.54.1577641730677; Sun, 29 Dec 2019 09:48:50 -0800 (PST) MIME-Version: 1.0 References: In-Reply-To: From: Yuval Kogman Date: Sun, 29 Dec 2019 17:48:38 +0000 Message-ID: To: ZmnSCPxj Content-Type: multipart/alternative; boundary="000000000000f0b2bb059adb5661" X-Mailman-Approved-At: Mon, 30 Dec 2019 01:32:28 +0000 Cc: Bitcoin Protocol Discussion Subject: Re: [bitcoin-dev] Non-equal value CoinJoins. Opinions. X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 29 Dec 2019 18:14:44 -0000 --000000000000f0b2bb059adb5661 Content-Type: text/plain; charset="UTF-8" Hi, On Sun, 29 Dec 2019 at 10:23, ZmnSCPxj 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
Hi,

On Sun, 29 Dec 2019 at 10:23, ZmnSCPxj <ZmnSCPxj@protonmail.com> wr= ote:
=C2=A0
Indeed, this is a problem still of equal-valued CoinJoin.
In theory the ZeroLink protocol fixes this by strongly constraining user be= havior, but ZeroLink is not "purely" 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.

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'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 "phase angle"= ; between a user's past mixes and the coordinator's current denomin= ation.
=C2=A0
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 ve= ry 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 subj= ect was unequal amounts and opinions ;-)

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 "spend" to create outp= uts (instead of the chaumian token itself being an output script)

2. replace the current notion of a mixing round into severa= l sub-types:
=C2=A0 - "decompose" - take an arbitrary a= mount and produce popcount(amount-fees) outputs with popcount =3D 1 (anon s= et size assumed to be 1)
=C2=A0 - "mix" - mix popco= unt =3D=3D 1 amounts with equal sized outputs - this is the only round type= that can increase anon set size
=C2=A0 - "optimize"= ; - convert mixed, popcount =3D=3D 1 (e.g. { 2^n} <-> { 2^(n-1), 2^(n= -1) } ) - it'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
=C2=A0 - "c= ombine" - spend popcount =3D=3D 1 outputs to produce arbitrary amounts=

Note that simultaneous rounds can be merged by th= e server during the signing phase, such so that for example a "decompo= se" 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'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 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'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.

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

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 & coor= dination fees too, but more generally any amounts used for any Bitcoin paym= ent)

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's) which the server can= also enforce by restricting "combine" rounds to require "op= timize" rounds before them

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

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 & = 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'= 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'= s approach to congestion control and multiparty payment channels in the con= text of Taproot & 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't worked this out in deta= il (still overwhelmed by the size of this design space).
--000000000000f0b2bb059adb5661--