diff options
| author | German Luna <german@diviproject.org> | 2020-04-24 07:42:12 -0600 |
|---|---|---|
| committer | bitcoindev <bitcoindev@gnusha.org> | 2020-04-24 13:42:26 +0000 |
| commit | be107ad734dfbc136c716ee0100a84d947a99dee (patch) | |
| tree | 462ede788b16d1d51d438e47b10e9309392f6930 /28 | |
| parent | fef4142dda2df4b52e0694bb14f39004d4a91bd8 (diff) | |
| download | pi-bitcoindev-be107ad734dfbc136c716ee0100a84d947a99dee.tar.gz pi-bitcoindev-be107ad734dfbc136c716ee0100a84d947a99dee.zip | |
Re: [bitcoin-dev] Fwd: (Semi)Traceless 2-party coinjoin off-chain protocol using schnorr signatures
Diffstat (limited to '28')
| -rw-r--r-- | 28/8d68a89323ea68349a778e4c4bc3d0192ff281 | 216 |
1 files changed, 216 insertions, 0 deletions
diff --git a/28/8d68a89323ea68349a778e4c4bc3d0192ff281 b/28/8d68a89323ea68349a778e4c4bc3d0192ff281 new file mode 100644 index 000000000..9e75cede9 --- /dev/null +++ b/28/8d68a89323ea68349a778e4c4bc3d0192ff281 @@ -0,0 +1,216 @@ +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'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'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'd have to make that conjecture fo= +r 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.</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 "practical limit on the numb= +er of UTXOs".<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'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-- + |