This is a quick sketch of several modifications to zerolink. This document tries to articulate an as of yet unproven intuition is that combined together they can allow unequal input amounts as well as relaxation of the post-mix no linking restriction, while retaining the same conservative assumptions about mixed output indistinguishability.
Disallowing post-mix linking is arguably bad for fungibility, since users are likely to bypass this restriction by transferring to other wallets. Therefore, if I am able to justify this change this seems like a much more substantial contribution to usability and fungibility. That said even if it can't be shown to be reasonable to do so, some of these ideas still have merit on their own, so not all would be lost.
- Enable additional fixed denomination mixing rounds based on preferred value series: i.e. instead of just rounds of 0.1 as is the case today with wasabi, there would be multiple independent rounds for e.g. using the 1-2-5 series, the round denominations could be
{ 1, 2, 5 } * 10^n
for all non-dust values ofn
(unpopular denominations would simply take longer to mix). Even with increased adoption this would likely reduce the size of anonymity set in given wallclock time interval, but not in discrete time measured mixing rounds.
Instead of input registration submitting multiple inputs, a change output and a blinded mix output, input registration mints chaumian tokens corresponding to the input amount minus the per-input fees, at a rate corresponding to the mixing fees.
These tokens can then be unblinded and "spent", deducting the per output fee, to register outputs that are not linked to the inputs before the final coinjoin signing phase. The server could still enforce the restriction of only 1 mixed output per participant if inputs must be registered together, with a single "mix" token being issued for the round denomination, and the remaining amount issued as "change" tokens (thus limiting the number of mixed outputs that can be made from one or more inputs to at most one). This restriction could also be relaxed, to allow tumbling that preserves the fixed denomination (allowing mixing fees to be paid by seemingly unrelated inputs).
Token denominations and colours would be specified by a set of per-round keys, and are thus only valid for the duration of the round. To allow O(1) verification of tokens, the amount should also be specified when spending: (amount, serial, signature)
(see also brands credentials, anonymous credentials light for how to encode amount information with blind signatures).
This revised protocol would allow the following changes:
-
Implement group send proposal as a new round type (non mixing round). If post-mix linking is allowed, then values over 0.1 would be spendable by using multiple mixed txos. Assuming preferred value series denominations are used, payments should generally be possible without requiring a change output given enough values (e.g. 0.321 = 0.2 + 0.1 + 0.02 + 0.001).
-
Implement dual of group send, i.e. non mixing rounds for breaking arbitrary sized inputs into fixed size, mixable denominations.
-
When rounds of any kind coincide, be they splitting to fixed denominations, mixing rounds, or group sends, they can be merged by the server into a single coinjoin transaction (merged rounds end by signing the same transaction). The server should still enforce rules for different round types, i.e. unequal amounts only get broken up, normal mixing rounds take fixed denomination inputs and outputs, and group sends of unequal output values are are only constructed from mixed inputs.
-
Inputs with good anonymity set sizes can be given a negative fees, covering the output creation amount (limited to the first registered output from a previous mixing transaction). This would incentivize "switching network" mixing topologies, allowing already mixed coins to contribute more to the anonymity sets of newly mixed coins.
TBD. Work is ongoing to provide an improved set of anonymity set estimation metrics, to analyze the feasibiltity of removing the post-mix linking restriction, and to address some of the computational complexity of Boltzmann.
See previous revisions of this document for early notes (mostly incorrect and incoherent)
- https://github.com/Samourai-Wallet/boltzmann
- Bitcoin Transactions & Privacy (part 1) : https://gist.github.com/LaurentMT/e758767ca4038ac40aaf
- Bitcoin Transactions & Privacy (part 2) : https://gist.github.com/LaurentMT/d361bca6dc52868573a2
- Bitcoin Transactions & Privacy (part 3) : https://gist.github.com/LaurentMT/e8644d5bc903f02613c6
- https://www.comsys.rwth-aachen.de/fileadmin/papers/2017/2017-maurer-trustcom-coinjoin.pdf
- https://github.com/AdamISZ/JMPrivacyAnalysis/blob/master/tumbler_privacy.md
- nopara73/ZeroLink#74 - unqeual input mixing
- https://github.com/zkSNACKs/WalletWasabi/issues/728 - improved anonymity set calculation
- https://github.com/zkSNACKs/WalletWasabi/issues/760 - group send proposal
- zkSNACKs/WalletWasabi#414 - schnorr blinding
I think the main difference is the UX, i.e. does each fixed denomination has a separate participant counter? (i think that's simplest, at least conceptually). What happens when a round has enough participants but another denomination is close to completion? (i think a small delay which would allow a different denomination round to complete, thus combining the two rounds is simplest)
The way the CJJ API works, participants register inputs along with a blinded output and a cleartext change output, and when the round is full, all participants submit unblinded outputs within some time window, after which the unsigned transaction is ready for everyone to sign. there's no technical limitation preventing multiple inputs and outputs by a single entity. to have {x1, x2, x3} as inputs and one output of amount x1+x2+x3 is not possible in the current API since all outputs in a round are assumed to have the same denomination, but the last proposed change would allow that (input registration would issue per-round tokens that can be spent to register blinded outputs)
If you mean in one round, then yes, this reduces the anonimity set for everyone, and currently is not allowed (though technically nothing prevents a single entity from splitting up coins into smaller inputs and participating multiple times, it's just not what the wallet software does without modified). If you mean over multiple rounds, then that's what's done now, and such outputs indistinguishable participating multiple times is fine, so long as mixed outputs are not linked.
This is also problematic if the post-mix no linking restriction isn't observed (for example by sending from the post-mix wallet to a wallet which doesn't follow the zerolink spec). For example, suppose you want to mix a large amount, and you participate in a round and then send your change to the next round, and so on. If a payment of this magnitude is later paid out of the transactions that mixed this amount, bin packing analysis can be made on the aggregate input amount, the actual anonymity set is substantially reduced. It's still plausible that some other user consolidated such an amount. Note that in that particular transaction some of the mixed outputs have been linked and identified as such by oxt.me. This observed behaviour is the main motivation for this writeup.
The logic I've been trying to formalize for this recursive calculation is that if the set of all inputs is increased, that becomes less of a problem. however, in the current approach this set's size is linear in the number of rounds. with additional mixing rounds the anonymity set for a given can grow quite large if taking into account all of its sister transactions, and this can compound (see remark about Clos/switching networks in the coinjoin bitcointalk post, several transactions forming a clos network is the ideal form, is essnetially equivalent to one large coinjoin transaction). This increase
isshould be estimated conservatively (under estimated), and entropy reduction of linking is also estimated conservatively (over estimated), in other words the recursive formula should pessimistically esitmate the per output entropy coming out of a Clos network transaction topology as though those transactions were one giant coinjoin.Both right now and with what i'm proposing that's allowed, entropy is created by introducing indistinguishability among the outputs. Boltzmann's intrinsic entropy and linkability matrix metrics account for all plausible combinations, and zerolink's notion only counts fully indistinguishable inputs.
I think this should remain unchanged, but if the post-mix linking restriction is lifted, the pre-mix entropy can be taken into account as well, in order to justify doing that (and the goal of the recursive formula is to quantify whether or not the pre-mix entropy is sufficient to cover the entropy lost by post-mix linking).
The main reason to use a preferred value series is to reduce the number of possible denominations over the entire range of plausible values, to avoid needing complex coordination for unpopular denominations (DoS protection also adds complexity there). This does create additional chain bloat and UTXO set bloat, and therefore increased the miner fees. The mixing fees scale with the amount mixed, not the data size to dissuate sybil attacks, so those fees should be unaffected.
If the ecash style tokens for output registration thing is implemented, this actually adds another possibility - users can pay extra fees, similar to the join market taker fee, incentivizing others to join a round. But this too adds some complexity to the protocol, and I haven't really thought through the implications