Re: [bitcoin-dev] Non-equal value CoinJoins. Opinions.
Hi, On Sun, 29 Dec 2019 at 10:23, ZmnSCPxj wrote: > > Indeed, this is a problem still of equal-valued CoinJoin. > In theory the ZeroLink protocol fixes this by strongly constraining user > behavior, but ZeroLink is not "purely" implemented in e.g. Wasabi: Wasabi > still allows spending pre- and post-mix coins in the same tx (ZeroLink > disallows this) and any mix change should be considered as still linked to > the inputs (though could be unlinked from the equal-valued output), i.e. > returned to pre-mix wallet. > Yes, although since the base denomination size is pretty large this can be very limiting, possibly forcing these change outputs to be linked to each other or, worse, with unmixed inputs which is still a serious linkage concern. This is further complicated due to variability of the denomination (which makes remixing possible due to the fee structure, but see below) also leaks some information or requires linking of mixed outputs in addition (although this resets its notion of anonymity set size, so I don't consider this unsafe or misleading, just wasteful) or in change being donated to the coordinator due to not meeting the threshold, depending on the "phase angle" between a user's past mixes and the coordinator's current denomination. > > Equal-valued CoinJoins fix this by using a Chaumian bank, which constrains > value transfers to specific fixed amounts. > Since an equal-valued CoinJoin uses a single fixed amount anyway, it is > not an additional restriction. > CashFusion cannot use the same technique without dropping into something > very much like an equal-valued CoinJoin. > I concur. I need to write a proper account of what I alluded to in my last email, but here's a summary (allowing myself to keep it in this thread as the subject was unequal amounts and opinions ;-) 1. introduce another stage between the input/output phases - at input registration you would receive chaumian reissuable/redenominatable tokens after deduction of per input fees, which you can then "spend" to create outputs (instead of the chaumian token itself being an output script) 2. replace the current notion of a mixing round into several sub-types: - "decompose" - take an arbitrary amount and produce popcount(amount-fees) outputs with popcount = 1 (anon set size assumed to be 1) - "mix" - mix popcount == 1 amounts with equal sized outputs - this is the only round type that can increase anon set size - "optimize" - convert mixed, popcount == 1 (e.g. { 2^n} <-> { 2^(n-1), 2^(n-1) } ) - it's not clear to me to what anon set size should be considered after this, probably reset to somewhere between 1 and the minimum size of the inputs, depending on degree of linkage - "combine" - spend popcount == 1 outputs to produce arbitrary amounts Note that simultaneous rounds can be merged by the server during the signing phase, such so that for example a "decompose" output may benefit from inhabiting the same CoinJoin transaction as a mixing round with the same denomination, but the coordinator would still be able to categorically distinguish between these, so this should not be thought of as a robust privacy improvement (but it does make some other adversary's job harder given only public data). In order to preserve the exact denomination size for mixing transactions, such rounds would need to have their mining fees subsidized - this can be accomplished by such merging, with the coordinator discounting or subsidizing input/output registration fees depending on the degree of mixing (a la Samourai/Whirlpool's mechanism design), or using some sort of prepaid mechanism (e.g. as part of a mixing round instead of a registered output you might elect to receive long lived - as in not per round - chaumian tokens that can be redeemed for fee-less, round denomination mixing, which can be reissued if the signing phase fails). In both cases I'm assuming the coordinator includes an input to cover the mining fees. I find the privacy aspects much easier to think about in this model, and it addresses many things of zerolink's weaknesses: 1. allows unequal amounts but retains many of the advantages of fixed denomination - the number of separate mixing pools would be at most log(2.1e13), with their sizes corresponding to actual amount distribution being used (for mining & coordination fees too, but more generally any amounts used for any Bitcoin payment) 2. it can potentially eliminate post mix change (if I want to spend some amount x = \sum{i=1..~40} a_i*2^i, and i have exactly the combination specified by the a_i's) which the server can also enforce by restricting "combine" rounds to require "optimize" rounds before them 3. increases privacy benefit of remixing while still removing Wasabi's round denomination decreases, especially over long time intervals The main issue, which I stress is significant, is the bloat - many such rounds are required, with many inputs and outputs per user per round, and many UTXOs per user on
Re: [bitcoin-dev] Non-equal value CoinJoins. Opinions.
This idea is not similar to the one in the knapsack paper because this one is based only in the computational complexity of finding partitions that match the outputs. However, and except in rare cases, there is only one valid partition (solution) for each output, it doesn't introduce any ambiguity. Knapsack, on the other hand, splits the original outputs in such a way that there are many partitions (solutions) that match the a selected group of outputs. For example, imagine 7 people decide to participate in a coinjoin transaction with an arbitrary number of inputs (no more than 7 inputs each), imagine this is not a pay to yourself cj tx but a pay to someone else cjtx instead such that there are at most 2 outputs for participants (payment output and change output) in this case, configuring the partitions search algorithm to restrict the search space to sets of 7 inputs maximum and 4 outputs maximum it found 14,599 valid transactions in 42mins 18secs https://raw.githubusercontent.com/lontivero/Knapsack/master/data/knapsack-7-participants.txt The same simulation with 8 participants under the same conditions found 35,781 valid transactions in about 4 hours. Finally, with 9 participants I let it running all the day and it didn't finished. The point is that the number of valid transactions grows so incredible fast that with 100 participants even if you find a way to find all the partitions that matches a set of outputs (something near to impossible), there are no way to know which of those are the real ones. Also, the attacks on this mechanism look so simple that generate doubts. Finally, I think the numbers in this proposal look weird because the example is using 10 inputs and the amounts are in the "neighborhood of ~0.1btc" (what the heck does that mean?) and the sum of those are around 1btc. That means that it could work in a very specific scenario. Knapsack is a general solution with good math behind and backtested against historical data extracted from the bitcoin's blockchain. In summary, in unequal inputs/outputs coinjoins knapsack is the best we have at the moment (btw, it is not as effective as equal-outputs transactions). This proposal is imo inferior and it is not supported by good math. El vie., 27 dic. 2019 a las 22:29, nopara73 via bitcoin-dev (< bitcoin-dev@lists.linuxfoundation.org>) escribió: > The CashFusion research came out of the Bitcoin Cash camp, thus this > probably went under the radar of many of you. I would like to ask your > opinions on the research's claim that, if non-equal value coinjoins can be > really relied on for privacy or not. > > (Btw, there were also similar ideas in the Knapsack paper in 2017: > https://www.comsys.rwth-aachen.de/fileadmin/papers/2017/2017-maurer-trustcom-coinjoin.pdf > ) > > > https://github.com/cashshuffle/spec/blob/master/CASHFUSION.md#avoiding-amount-linkages-through-combinatorics > > > I copy the most relevant paragraphs here: > > -BEGIN QUOTE - > > > Consider a transaction where 10 people have each brought 10 inputs of > arbitary amounts in the neighborhood of ~0.1 BCH. One input might be > 0.03771049 BCH; the next might be 0.24881232 BCH, etc. All parties have > chosen to consolidate their coins, so the transaction has 10 outputs of > around 1 BCH. So the transaction has 100 inputs, and 10 outputs. The first > output might be 0.91128495, the next could be 1.79783710, etc. > > Now, there are 100!/(10!)^10 ~= 10^92 ways to partition the inputs into a > list of 10 sets of 10 inputs, but only a tiny fraction of these partitions > will produce the precise output list. So, how many ways produce this exact > output list? We can estimate with some napkin math. First, recognize that > for each partitioning, each output will typically land in a range of ~10^8 > discrete possibilities (around 1 BCH wide, with a 0.0001 BCH > resolution). The first 9 outputs all have this range of possibilities, and > the last will be constrained by the others. So, the 10^92 possibilies will > land somewhere within a 9-dimensional grid that cointains (10^8)^9=10^72 > possible distinct sites, one site which is our actual output list. Since we > are stuffing 10^92 possibilties into a grid that contains only 10^72 sites, > then this means on average, each site will have 10^20 possibilities. > > Based on the example above, we can see that not only are there a huge > number of partitions, but that even with a fast algorithm that could find > matching partitions, it would produce around 10^20 possible valid > configurations. With 10^20 possibilities, there is essentially no linkage. > The Cash Fusion scheme actually extends this obfuscation even further. Not > only can players bring many inputs, they can also have multiple outputs. > -END QUOTE - > -- > Best, > Ádám > ___ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org >
Re: [bitcoin-dev] Non-equal value CoinJoins. Opinions.
On Sun, 29 Dec 2019, 05:31 Yuval Kogman, wrote: > n = # inputs + # indistinguishable outputs > sorry, this is really wrong (although of no consequence to my arguments) - n is the smaller of these two numbers, not their sum. ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Non-equal value CoinJoins. Opinions.
Good morning Yuval, > Additionally (though is a broader criticism of CoinJoin based privacy and not > specific to unequal amounts, and in particular refers to ZmnSCPxj's assertion > of 0 linkability) I am very worried that perspectives that focus on > linkability information revealed by a single coinjoin transaction in > isolation. This problem was alluded in the document, to but I don't see that > it was addressed. Naively the post/pre mix transaction graph would seem to > present a computationally much harder problem when looking at the > combinatorics through the same lens, but reality it can also be used to place > many constraints on valid partitions/sub-transaction assignments for a single > transaction with equal amounts. The trivial example is post mix linking of > outputs, but there are many other ways to draw inferences or eliminate > possible interpretations of a single transaction based on its wider context, > which in turn may be used to attack other transactions. Indeed, this is a problem still of equal-valued CoinJoin. In theory the ZeroLink protocol fixes this by strongly constraining user behavior, but ZeroLink is not "purely" implemented in e.g. Wasabi: Wasabi still allows spending pre- and post-mix coins in the same tx (ZeroLink disallows this) and any mix change should be considered as still linked to the inputs (though could be unlinked from the equal-valued output), i.e. returned to pre-mix wallet. > Finally, the proof as well as its applicability seems suspect to me, since > seems to involve trusting the server: > "Since the distinct list [...] [is] kept on the server and not shared with > the players" > "The server knows the linkages of the commitments but does not participate as > a verifier " > "If there is a problem [...] each component is assigned to another player at > random for verification" > these 3 statements together seems to suggest the server is trusted to not use > sybils in order the compromise privacy by participating in the verification > process? Equal-valued CoinJoins fix this by using a Chaumian bank, which constrains value transfers to specific fixed amounts. Since an equal-valued CoinJoin uses a single fixed amount anyway, it is not an additional restriction. CashFusion cannot use the same technique without dropping into something very much like an equal-valued CoinJoin. Regards, ZmnSCPxj ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev