From: ZmnSCPxj <ZmnSCPxj@protonmail•com>
To: German Luna <german@diviproject•org>
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
Date: Fri, 24 Apr 2020 01:34:51 +0000 [thread overview]
Message-ID: <-_xRcjb8H_0Bck71k4VkeukEBgHT-03ikLTIdyTG2P0rt0T_mvN4b4FejmWobwnAUCGNaDpFQlPc3TMwlml1gjnZ1lwSumeEYQpXSyijND0=@protonmail.com> (raw)
In-Reply-To: <CALmj_sUuw8JkodDemnq4qkapWD28vpojKD3bmkiVYm3Cp76+NQ@mail.gmail.com>
Good morning Germán,
> 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-subset problem (np complete problem)( https://www.cs.mcgill.ca/~lyepre/pdf/assignment2-solutions/subsetSumNPCompleteness.pdf )?
> That is, a pair of individuals with a set of UTXOs that both add up to similar if not equal value perform a swap of similar-(total)value sets. In this way the values of the UTXOs can be broken up essentially at random (following some nominal distribution so that it doesn't stand out; e.g. https://en.wikipedia.org/wiki/Benford%27s_law), but swapped in conjunction and decorrelated by using different keys + randomized locktimes.
There are a number of issues to simply modeling this to the subset-sum problem.
* 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 sum up to 1mBTC.
* Thus, a practical blockchain analyst can bound the size of the sets involved, 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 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.
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
next prev parent reply other threads:[~2020-04-24 1:34 UTC|newest]
Thread overview: 13+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <CALmj_sWCA6S_4bnmLetvLuzNhv=PfQvLnX3zVEZwsRtgzA=yqw@mail.gmail.com>
2020-04-22 18:42 ` German Luna
2020-04-23 17:56 ` ZmnSCPxj
2020-04-23 18:40 ` German Luna
2020-04-24 1:34 ` ZmnSCPxj [this message]
2020-04-24 13:42 ` German Luna
2020-04-28 13:03 ` Chris Belcher
2020-04-29 7:56 ` ZmnSCPxj
2020-04-29 15:06 ` Chris Belcher
2020-04-30 8:54 ` ZmnSCPxj
2020-04-30 17:18 ` Chris Belcher
2020-05-01 7:17 ` ZmnSCPxj
2020-05-03 19:28 ` Chris Belcher
2020-05-04 8:28 ` ZmnSCPxj
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='-_xRcjb8H_0Bck71k4VkeukEBgHT-03ikLTIdyTG2P0rt0T_mvN4b4FejmWobwnAUCGNaDpFQlPc3TMwlml1gjnZ1lwSumeEYQpXSyijND0=@protonmail.com' \
--to=zmnscpxj@protonmail$(echo .)com \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
--cc=german@diviproject$(echo .)org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox