Author: Chris Belcher 2020-04-28 13:03:36
Published on: 2020-04-28T13:03:36+00:00
The email exchange on the bitcoin-dev mailing list discusses the issues with modeling a solution to tackle the problem of value-based correlations after the equal-sum-subset problem. According to ZmnSCPxj, there is a practical limit to the number of UTXOs one would be willing to receive in the swap as every UTXO received increases the potential fee that one has to pay to spend them. Therefore, a practical blockchain analyst can bound the size of the sets involved and the problem becomes less than NP in practice. Additionally, if one has a single UTXO and splits it before swapping, anyone looking at the history can conjecture that the split involved is part of a CoinSwap which is now a hint to how the subset sums can be tried. The email further suggests that 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. Multi-transaction CoinSwaps aren't truly an example of a subset-sum problem, but "sparse subset sum", a related and easier problem. The way it's 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. Moreover, the email suggests that the best way to build privacy is to create a situation where an adversary would find a huge amount of false positives which are very close to 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. Finally, the email recommends getting in touch with belcher, waxwing, and nopara73 who have been working far longer on privacy tech as they may know of other issues or solutions to the above problems.
Updated on: 2023-06-14T00:53:29.117852+00:00