path: root/28/8d68a89323ea68349a778e4c4bc3d0192ff281

Return-Path: <german@diviproject.org>
Received: from fraxinus.osuosl.org (smtp4.osuosl.org [140.211.166.137])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 8A8B0C0175
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 24 Apr 2020 13:42:26 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by fraxinus.osuosl.org (Postfix) with ESMTP id 7E7C6860F0
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 24 Apr 2020 13:42:26 +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 IfaKa277Qz6p
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 24 Apr 2020 13:42:25 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.6
Received: from mail-wr1-f52.google.com (mail-wr1-f52.google.com
 [209.85.221.52])
 by fraxinus.osuosl.org (Postfix) with ESMTPS id E782F85FAE
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 24 Apr 2020 13:42:24 +0000 (UTC)
Received: by mail-wr1-f52.google.com with SMTP id i10so10855286wrv.10
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 24 Apr 2020 06:42:24 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=diviproject-org.20150623.gappssmtp.com; s=20150623;
 h=mime-version:references:in-reply-to:from:date:message-id:subject:to
 :cc; bh=L/JHsyk5JNmc1ap/61gWHJpIyRb2o8dclwV+yCtvQUw=;
 b=oVblsY3ZtQ0QvTQ9twjNCXwW6HR0trq8+2jUVLFpBOq3g4wZfgnzCG+7XmhSJVsNLd
 l8biRgWaCAGcBI0nm244zApyT6haR7gEWshgZdx1WSw69/b3WNAQsNGqB5/HY9JpaIEz
 lYFse6yocqNMfNezm9LMVYbtv456xBZ+P+epBg8DbuLW9d75qSuKbb/6i9PDDxn3Nsyx
 wQuz0Yjc+tjq+6/uo3ZE0dunhkBHnif4tsmdSLWGCIZUeF1hbzjpaoOPjfM7w//n8AVj
 PCQudvUQM/6q7VtGuBRKF4z2ZqU8ChRW2cmR/v/LYjH8M6wLBSKPPvwbgiPrDC9+2GQ6
 rN6Q==
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=L/JHsyk5JNmc1ap/61gWHJpIyRb2o8dclwV+yCtvQUw=;
 b=d7sa0sZtUO2NMUz7BVW48eDKaiJB3TPU8kdsaDsOxBnoHUSDsZb2sTPRA7caZBVhK3
 5xbjNPG41e6KO/IzVGK++uSqMJng9AZFDswE0j7zVyt+ULWn287rsX3MuZfXgM8Q6cQA
 HG7S1/y5gB4PWYigMqNSL/sAl9XXW6N9fGtiCdW03ORJJ4lnKiwpkxr1vTE06tThlYLK
 lNgYjlN9LRPqE7hbiXSa5FiiO1NdsA/Wgp7tSO8TKCvOvis2G9oGn3QO+pxpoIdQCWW2
 BAJFm1xQGFbvXCSKp3USFcEv+E0v/o3+S/m0CRbVWZKfcnKB3JDpXW6r6SlL62zk7gOA
 QfVA==
X-Gm-Message-State: AGi0PuYGY4+DIoDFlBGGmiJkWWTykYgi3B5ZK7lO6R9/K3++ablf2krj
 2G/eYxf6jKjZfrM/3IIDxZIbJq+jgVFaq2w+lpTLTQ==
X-Google-Smtp-Source: APiQypLxrgtsd+PFNVCpb0zVMtNOOgwv7Mjz8D8tG34xjUCH1Om+aWClOfWc0bqq/WTjhmKBgkUxdASgPjFVBFe+/QI=
X-Received: by 2002:adf:cc8d:: with SMTP id p13mr11698308wrj.114.1587735743226; 
 Fri, 24 Apr 2020 06:42:23 -0700 (PDT)
MIME-Version: 1.0
References: <CALmj_sWCA6S_4bnmLetvLuzNhv=PfQvLnX3zVEZwsRtgzA=yqw@mail.gmail.com>
 <CALmj_sVwLG82_pCEnc-mdT-Cf+cPitpL59AruBbvyYLjaYoZ2Q@mail.gmail.com>
 <mRCFEsXTvivO-I7sBdoTbqV0RsnX9vdGGORqzJBGYWXd1Xqis-oBNtEFaCEWIt3g9ARrvNeqH3l6sWSH4uQdcj5ps5WAmaEbEUvb9Znk9Rw=@protonmail.com>
 <CALmj_sUuw8JkodDemnq4qkapWD28vpojKD3bmkiVYm3Cp76+NQ@mail.gmail.com>
 <-_xRcjb8H_0Bck71k4VkeukEBgHT-03ikLTIdyTG2P0rt0T_mvN4b4FejmWobwnAUCGNaDpFQlPc3TMwlml1gjnZ1lwSumeEYQpXSyijND0=@protonmail.com>
In-Reply-To: <-_xRcjb8H_0Bck71k4VkeukEBgHT-03ikLTIdyTG2P0rt0T_mvN4b4FejmWobwnAUCGNaDpFQlPc3TMwlml1gjnZ1lwSumeEYQpXSyijND0=@protonmail.com>
From: German Luna <german@diviproject.org>
Date: Fri, 24 Apr 2020 07:42:12 -0600
Message-ID: <CALmj_sVnBK2jqhdsmRNcS3YVOF2XsOQdJ8wzPy2Zbx0dfU3K4A@mail.gmail.com>
To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Content-Type: multipart/alternative; boundary="000000000000f8f3e005a40988d8"
X-Mailman-Approved-At: Fri, 24 Apr 2020 13:46:12 +0000
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Fwd: (Semi)Traceless 2-party coinjoin off-chain
 protocol using schnorr signatures
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Fri, 24 Apr 2020 13:42:26 -0000

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

Good morning ZmnSCPxj,

The issues you point out are indeed important to note. Thank you for your
wonderful feedback!

* There is a practical limit to the number of UTXOs you would be willing to
> receive in the swap.
>   * Every UTXO you receive increases the potential fee you have to pay to
> spend them, meaning you would strongly dislike receiving 100 UTXOs that s=
um
> up to 1mBTC.
>
Absolutely agree. It wouldn't be particularly nice to have to manage that.

  * Thus, a practical blockchain analyst can bound the size of the sets
> involved, and the problem becomes less than NP in practice.
>
Definitely, though they first have to consider all subsets of a fixed size
with values bounded above by the value of the unknown sum. So the analyst
has to search through all fixed size sets (up to the practical bound) whose
elements are less than a maximum sum. This is a number of choices that is
(in a crude estimation) exponential (in the size of the UTXO set), and
polynomial in the number UTXOs below that maximum sum value on-chain which
can be pretty big at sufficiently large value-transfers.

* If you have a single UTXO and split it, then swap, anyone looking at the
> history can conjecture that the split involved is part of a CoinSwap.
>   * The split is now a hint on how the subset sums can be tried.
>
You're right that anybody could conjecture that it is involved in a
CoinSwap, however in my proposed protocol the swap would like a (schnorr)
P2PKH to the chain so you'd have to make that conjecture for every UTXO, so
it's not much of a hint. Especially so noting that one, both or none of the
outputs could be part of a swap.

* If after the CoinSwap you spend the UTXOs you received in a single
> transaction, then you just published the solution to the subset sum for
> your adversary.
>   * This ties in even further to the "practical limit on the number of
> UTXOs".
>     * Because it is not safe to spend the UTXOs from a single CoinSwap
> together, you want to have fewer, larger UTXOs for more flexibility in
> spending later.
>
Yes, this is definitely a weakness and some over-the-top UTXO management
techniques (e.g. try to avoid combining different UTXOs in a known set into
the same transaction by default, where possible) would be needed or like
you say fewer larger UTXOs.

It's interesting to note one can pick some subset of recent UTXOs and add
up their output values, and select that as the amount of value transfer to
exchange in a given operation. Resulting in a bit of added obfuscation as
there are now seemingly (at least) 3 utxo sets that add up to similar or
identical values, but only two of which are really participating in the
swap.

I believe belcher and waxwing and nopara73 have been working far longer on
> privacy tech, and you should try to get in contact with them as well, the=
y
> may know of other issues (or solutions to the above problems).
>
Thank you for your input and suggestions! I will reach out to them.

--=20
Germ=C3=A1n
Mathematician

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

<div dir=3D"ltr"><div dir=3D"ltr">Good morning ZmnSCPxj,<div><br></div><div=
>The issues you point out are indeed important to note. Thank=C2=A0you for =
your wonderful feedback!</div><div><br></div></div><div class=3D"gmail_quot=
e"><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;bord=
er-left:1px solid rgb(204,204,204);padding-left:1ex">* There is a practical=
 limit to the number of UTXOs you would be willing to receive in the swap.<=
br>
=C2=A0 * Every UTXO you receive increases the potential fee you have to pay=
 to spend them, meaning you would strongly dislike receiving 100 UTXOs that=
 sum up to 1mBTC.<br></blockquote><div>Absolutely agree. It wouldn&#39;t be=
 particularly nice to have to manage that.</div><div><br></div><blockquote =
class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px sol=
id rgb(204,204,204);padding-left:1ex">
=C2=A0 * Thus, a practical blockchain analyst can bound the size of the set=
s involved, and the problem becomes less than NP in practice.<br></blockquo=
te><div>Definitely, though they first have to consider all subsets of a fix=
ed size with values bounded above by the value of the unknown sum. So the a=
nalyst has to search through all fixed size sets (up to the practical bound=
) whose elements are less than a maximum sum. This is a number of choices t=
hat is (in a crude estimation) exponential (in the size of the UTXO set), a=
nd polynomial in the number UTXOs below that maximum sum value on-chain whi=
ch can be pretty big at sufficiently large value-transfers.</div><div><br><=
/div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;bo=
rder-left:1px solid rgb(204,204,204);padding-left:1ex">
* If you have a single UTXO and split it, then swap, anyone looking at the =
history can conjecture that the split involved is part of a CoinSwap.<br>
=C2=A0 * The split is now a hint on how the subset sums can be tried.<br></=
blockquote><div>You&#39;re right that anybody could conjecture that it is i=
nvolved in a CoinSwap, however in my proposed protocol the swap would like =
a (schnorr) P2PKH to the chain so you&#39;d have to make that conjecture fo=
r every UTXO, so it&#39;s not much of a hint. Especially so noting that one=
, both or none of the outputs could be part of a swap.</div><div><br></div>=
<blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-=
left:1px solid rgb(204,204,204);padding-left:1ex">
* If after the CoinSwap you spend the UTXOs you received in a single transa=
ction, then you just published the solution to the subset sum for your adve=
rsary.<br>
=C2=A0 * This ties in even further to the &quot;practical limit on the numb=
er of UTXOs&quot;.<br>
=C2=A0 =C2=A0 * Because it is not safe to spend the UTXOs from a single Coi=
nSwap together, you want to have fewer, larger UTXOs for more flexibility i=
n spending later.<br></blockquote><div>Yes, this is definitely a weakness a=
nd some over-the-top UTXO management techniques (e.g. try to avoid combinin=
g different=C2=A0UTXOs in a known set into the same transaction by default,=
 where possible) would be needed or like you say fewer larger UTXOs.</div><=
div><br></div><div>It&#39;s interesting to note one can pick some subset of=
 recent UTXOs and add up their output values, and select that as the amount=
 of value transfer to exchange in a given operation. Resulting in a bit of =
added obfuscation as there are now seemingly (at least) 3 utxo sets that ad=
d up to similar or identical values, but only two of which are really parti=
cipating in the swap.</div><div><br></div><blockquote class=3D"gmail_quote"=
 style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);p=
adding-left:1ex">
I believe belcher and waxwing and nopara73 have been working far longer on =
privacy tech, and you should try to get in contact with them as well, they =
may know of other issues (or solutions to the above problems).<br></blockqu=
ote><div>Thank you for your input and suggestions! I will reach out to them=
.</div><div>=C2=A0</div></div>-- <br><div dir=3D"ltr"><div dir=3D"ltr">Germ=
=C3=A1n<div>Mathematician</div></div></div></div>

--000000000000f8f3e005a40988d8--