đź“… Original date posted:2020-04-28
đź“ť Original message:On 24/04/2020 02:34, ZmnSCPxj via bitcoin-dev wrote:
> 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
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
Hello list,
A couple of thoughts on multi-transaction coinswaps:
* Users should never split up a single UTXO before doing a coinswap,
instead they should send the one UTXO to a coinswap address and get back
multiple UTXOs.
For example, this 1-to-3 TXO coinswap (The symbol ----> means bitcoin
transaction).
AliceA (10 BTC) ----> CoinSwap AddressA ----> BobA (10 BTC)
BobB (3 BTC) ----> CoinSwap AddressB ----> AliceB (6 BTC)
BobC (2 BTC) ----> CoinSwap AddressC ----> AliceC (3 BTC)
BobD (5 BTC) ----> CoinSwap AddressD ----> AliceD (1 BTC)
Note that the Bob-to-Alice set of transactions add up to 10 BTC, the
entire CoinSwap is swapping the same amount.
Or written another way:
Alice TXO (10 BTC) ----> Coinswap Protocol ----> Alice TXO1 (6 BTC)
----> Alice TXO2 (3 BTC)
----> Alice TXO3 (1 BTC)
This kind of thing could also be used for consolidation of many UTXOs
without necessarily leaking information that the same person owns them.
For example, if Alice owns 5 UTXOs:
Alice TXO1 ----> Coinswap Protocol ----> Alice TXO
Alice TXO2 ---->
Alice TXO3 ---->
Alice TXO4 ---->
Alice TXO5 ---->
* It's helpful if any CoinSwap app is actually used for spending rather
than just mixing back to yourself. That will help avoid the problem of
users inadvertently co-spending all their coinswap outputs in the same
transaction.
An example of Alice paying for a VPN anonymously:
Alice TXO (10 BTC) ---> Coinswap Protocol ---> VPN Payment (0.1 BTC)
---> Change1 (6 BTC)
---> Change2 (3 BTC)
---> Change3 (0.9 BTC)
In this case Alice will never accidentally merge all her TXOs together,
because the VPN Payment TXO doesn't belong to her. Also this could
improve privacy because unlike in normal transaction the VPN provider
might not be able to figure out the lower bound of Alice's balance (10
BTC in this case).
* Multi-transaction CoinSwaps aren't truly an example of a subset-sum
problem, but "sparse subset sum", a related and easier problem.
The way its normally formulated, subset sum is about finding a subset
that adds up to a target value. But in multi-transaction coinswap
there'd only be three or four CoinSwap outputs, so the problem is
finding just three or four integers in a big set that add up to the target.
You could think of it mathematically that the n-choose-k function is
near-polynomial when k is near 0 or near n, and the function is
exponential when k is near n/2.
A more promising way to build privacy is to create a situation where an
adversary would find a huge amount of false positives which are very
close the amount being sent. So even if the adversary has enough
computational power to iterate all the amounts it won't help them much
due to the huge number of false positives.
Regards
CB
Chris Belcher [ARCHIVE] /
npub1ek…lnm2u
2023-06-07 18:24:05
in reply to nevent1q…azwt
Author Public Key
npub1ekvnqhww3aagwuj9t55dgj5y29u8cxdjllfv3vgppt8vc0zljhrs6lnm2uPublished at
2023-06-07 18:24:05Event JSON
{
"id": "ccc4595694397a1a4036adef95a57981795b5975a222304e860071e5b0713cc1",
"pubkey": "cd99305dce8f7a8772455d28d44a8451787c19b2ffd2c8b1010acecc3c5f95c7",
"created_at": 1686162245,
"kind": 1,
"tags": [
[
"e",
"34656e8e3a21e9e36bd639a933809cb38662e425b24ae92fc2e74925768908b3",
"",
"root"
],
[
"e",
"6ea8abfb08462a4e68997cf897ba1c255772f6f8f10e242149df6310cc9be050",
"",
"reply"
],
[
"p",
"08bb7ba396fe76c8904e88e026d904a68a52dd51a74a349a93e983a8b5cdd067"
]
],
"content": "📅 Original date posted:2020-04-28\n📝 Original message:On 24/04/2020 02:34, ZmnSCPxj via bitcoin-dev wrote:\n\u003e Good morning Germán,\n\u003e \n\u003e \n\u003e\u003e 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 )? \n\u003e\u003e 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.\n\u003e \n\u003e There are a number of issues to simply modeling this to the subset-sum problem.\n\u003e \n\u003e * There is a practical limit to the number of UTXOs you would be willing to receive in the swap.\n\u003e * 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.\n\u003e * Thus, a practical blockchain analyst can bound the size of the sets involved, and the problem becomes less than NP in practice.\n\u003e * 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.\n\u003e * The split is now a hint on how the subset sums can be tried.\n\u003e * 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.\n\u003e * This ties in even further to the \"practical limit on the number of UTXOs\".\n\u003e * 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.\n\u003e \n\u003e 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).\n\u003e \n\u003e Regards,\n\u003e ZmnSCPxj\n\u003e _______________________________________________\n\u003e bitcoin-dev mailing list\n\u003e bitcoin-dev at lists.linuxfoundation.org\n\u003e https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev\n\u003e \n\nHello list,\n\nA couple of thoughts on multi-transaction coinswaps:\n\n* Users should never split up a single UTXO before doing a coinswap,\ninstead they should send the one UTXO to a coinswap address and get back\nmultiple UTXOs.\n\nFor example, this 1-to-3 TXO coinswap (The symbol ----\u003e means bitcoin\ntransaction).\n\n AliceA (10 BTC) ----\u003e CoinSwap AddressA ----\u003e BobA (10 BTC)\n\n BobB (3 BTC) ----\u003e CoinSwap AddressB ----\u003e AliceB (6 BTC)\n BobC (2 BTC) ----\u003e CoinSwap AddressC ----\u003e AliceC (3 BTC)\n BobD (5 BTC) ----\u003e CoinSwap AddressD ----\u003e AliceD (1 BTC)\n\n\nNote that the Bob-to-Alice set of transactions add up to 10 BTC, the\nentire CoinSwap is swapping the same amount.\n\nOr written another way:\n\n Alice TXO (10 BTC) ----\u003e Coinswap Protocol ----\u003e Alice TXO1 (6 BTC)\n ----\u003e Alice TXO2 (3 BTC)\n ----\u003e Alice TXO3 (1 BTC)\n\nThis kind of thing could also be used for consolidation of many UTXOs\nwithout necessarily leaking information that the same person owns them.\nFor example, if Alice owns 5 UTXOs:\n\n Alice TXO1 ----\u003e Coinswap Protocol ----\u003e Alice TXO\n Alice TXO2 ----\u003e\n Alice TXO3 ----\u003e\n Alice TXO4 ----\u003e\n Alice TXO5 ----\u003e\n\n\n* It's helpful if any CoinSwap app is actually used for spending rather\nthan just mixing back to yourself. That will help avoid the problem of\nusers inadvertently co-spending all their coinswap outputs in the same\ntransaction.\nAn example of Alice paying for a VPN anonymously:\n\n Alice TXO (10 BTC) ---\u003e Coinswap Protocol ---\u003e VPN Payment (0.1 BTC)\n ---\u003e Change1 (6 BTC)\n ---\u003e Change2 (3 BTC)\n ---\u003e Change3 (0.9 BTC)\n\nIn this case Alice will never accidentally merge all her TXOs together,\nbecause the VPN Payment TXO doesn't belong to her. Also this could\nimprove privacy because unlike in normal transaction the VPN provider\nmight not be able to figure out the lower bound of Alice's balance (10\nBTC in this case).\n\n\n* Multi-transaction CoinSwaps aren't truly an example of a subset-sum\nproblem, but \"sparse subset sum\", a related and easier problem.\n\nThe way its normally formulated, subset sum is about finding a subset\nthat adds up to a target value. But in multi-transaction coinswap\nthere'd only be three or four CoinSwap outputs, so the problem is\nfinding just three or four integers in a big set that add up to the target.\n\nYou could think of it mathematically that the n-choose-k function is\nnear-polynomial when k is near 0 or near n, and the function is\nexponential when k is near n/2.\n\nA more promising way to build privacy is to create a situation where an\nadversary would find a huge amount of false positives which are very\nclose the amount being sent. So even if the adversary has enough\ncomputational power to iterate all the amounts it won't help them much\ndue to the huge number of false positives.\n\n\nRegards\nCB",
"sig": "f7e5d5c09ab2895f92b1d2b87e06da675ec0a12cb4f498b8b7654177a355809101d91cebd1bc80c3993329de32ab9db4bbb592ee8b0d4a254088b8945be2f113"
}