Date: Fri, 24 Apr 2020 01:34:51 +0000
To: German Luna <german@diviproject.org>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <-_xRcjb8H_0Bck71k4VkeukEBgHT-03ikLTIdyTG2P0rt0T_mvN4b4FejmWobwnAUCGNaDpFQlPc3TMwlml1gjnZ1lwSumeEYQpXSyijND0=@protonmail.com>
In-Reply-To: <CALmj_sUuw8JkodDemnq4qkapWD28vpojKD3bmkiVYm3Cp76+NQ@mail.gmail.com>
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>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
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
Precedence: list

Good morning Germ=C3=A1n,


> With regards to trying to tackle the problem of value-based correlations,=
 wouldn't it be possible to try to model the solution after the equal-sum-s=
ubset problem (np complete problem)( https://www.cs.mcgill.ca/~lyepre/pdf/a=
ssignment2-solutions/subsetSumNPCompleteness.pdf=C2=A0 )?=C2=A0
> That is, a pair of individuals with a set of UTXOs that both add up to si=
milar if not equal value perform a swap of similar-(total)value sets. In th=
is way the values of the UTXOs can be broken up essentially at random (foll=
owing some nominal distribution so that it doesn't stand out; e.g.=C2=A0htt=
ps://en.wikipedia.org/wiki/Benford%27s_law), but swapped=C2=A0in conjunctio=
n and decorrelated by using different keys=C2=A0+ randomized locktimes.

There are a number of issues to simply modeling this to the subset-sum prob=
lem.

* 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 s=
pend them, meaning you would strongly dislike receiving 100 UTXOs that sum =
up to 1mBTC.
  * Thus, a practical blockchain analyst can bound the size of the sets inv=
olved, and the problem becomes less than NP in practice.
* 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.
* 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.
  * This ties in even further to the "practical limit on the number of UTXO=
s".
    * Because it is not safe to spend the UTXOs from a single CoinSwap toge=
ther, you want to have fewer, larger UTXOs for more flexibility in spending=
 later.

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

Regards,
ZmnSCPxj