📅 Original date posted:2020-04-24
📝 Original message: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 sum
> 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, they
> may know of other issues (or solutions to the above problems).
>
Thank you for your input and suggestions! I will reach out to them.
--
Germán
Mathematician
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20200424/dfd618b8/attachment.html>;
German Luna [ARCHIVE] /
npub1pz…x2ld8
2023-06-07 18:24:05
in reply to nevent1q…verr
Author Public Key
npub1pzahhguklemv3yzw3rszdkgy56999h235a9rfx5naxp63dwd6pns7x2ld8Published at
2023-06-07 18:24:05Event JSON
{
"id": "6ea8abfb08462a4e68997cf897ba1c255772f6f8f10e242149df6310cc9be050",
"pubkey": "08bb7ba396fe76c8904e88e026d904a68a52dd51a74a349a93e983a8b5cdd067",
"created_at": 1686162245,
"kind": 1,
"tags": [
[
"e",
"34656e8e3a21e9e36bd639a933809cb38662e425b24ae92fc2e74925768908b3",
"",
"root"
],
[
"e",
"f308bb8a7eeebdee1f21acea9a71c65a18038541d6eea252898fbe3e879fc3be",
"",
"reply"
],
[
"p",
"4505072744a9d3e490af9262bfe38e6ee5338a77177b565b6b37730b63a7b861"
]
],
"content": "📅 Original date posted:2020-04-24\n📝 Original message:Good morning ZmnSCPxj,\n\nThe issues you point out are indeed important to note. Thank you for your\nwonderful feedback!\n\n* There is a practical limit to the number of UTXOs you would be willing to\n\u003e receive in the swap.\n\u003e * Every UTXO you receive increases the potential fee you have to pay to\n\u003e spend them, meaning you would strongly dislike receiving 100 UTXOs that sum\n\u003e up to 1mBTC.\n\u003e\nAbsolutely agree. It wouldn't be particularly nice to have to manage that.\n\n * Thus, a practical blockchain analyst can bound the size of the sets\n\u003e involved, and the problem becomes less than NP in practice.\n\u003e\nDefinitely, though they first have to consider all subsets of a fixed size\nwith values bounded above by the value of the unknown sum. So the analyst\nhas to search through all fixed size sets (up to the practical bound) whose\nelements are less than a maximum sum. This is a number of choices that is\n(in a crude estimation) exponential (in the size of the UTXO set), and\npolynomial in the number UTXOs below that maximum sum value on-chain which\ncan be pretty big at sufficiently large value-transfers.\n\n* If you have a single UTXO and split it, then swap, anyone looking at the\n\u003e history can conjecture that the split involved is part of a CoinSwap.\n\u003e * The split is now a hint on how the subset sums can be tried.\n\u003e\nYou're right that anybody could conjecture that it is involved in a\nCoinSwap, however in my proposed protocol the swap would like a (schnorr)\nP2PKH to the chain so you'd have to make that conjecture for every UTXO, so\nit's not much of a hint. Especially so noting that one, both or none of the\noutputs could be part of a swap.\n\n* If after the CoinSwap you spend the UTXOs you received in a single\n\u003e transaction, then you just published the solution to the subset sum for\n\u003e your adversary.\n\u003e * This ties in even further to the \"practical limit on the number of\n\u003e UTXOs\".\n\u003e * Because it is not safe to spend the UTXOs from a single CoinSwap\n\u003e together, you want to have fewer, larger UTXOs for more flexibility in\n\u003e spending later.\n\u003e\nYes, this is definitely a weakness and some over-the-top UTXO management\ntechniques (e.g. try to avoid combining different UTXOs in a known set into\nthe same transaction by default, where possible) would be needed or like\nyou say fewer larger UTXOs.\n\nIt's interesting to note one can pick some subset of recent UTXOs and add\nup their output values, and select that as the amount of value transfer to\nexchange in a given operation. Resulting in a bit of added obfuscation as\nthere are now seemingly (at least) 3 utxo sets that add up to similar or\nidentical values, but only two of which are really participating in the\nswap.\n\nI believe belcher and waxwing and nopara73 have been working far longer on\n\u003e privacy tech, and you should try to get in contact with them as well, they\n\u003e may know of other issues (or solutions to the above problems).\n\u003e\nThank you for your input and suggestions! I will reach out to them.\n\n-- \nGermán\nMathematician\n-------------- next part --------------\nAn HTML attachment was scrubbed...\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20200424/dfd618b8/attachment.html\u003e",
"sig": "39226c5e234263d0e58d58fe3cb474cfef278e414f96eeaa1ee42906a4c33ffd8a93ebdf66856bb5f3eb566fbd4e942448558ddc1e94c8087b31bbee8ccc8d96"
}