Deriving multiple addresses for the receiver

[MaxHillebrand]

The big advantage of this new scheme is that it allows to send an arbitrary amount to a third party. However, for several denial of service vectors [either malicious or unintentional] a CoinJoin round fails after output registration. This means, that the coordinator and all participants have seen all addresses and associated receiving amounts. For the next attempted round, the old address should me marked as burned and not used again, and a new address should be generated for this round. For mix2self this is not an issue, as we are using HD wallets, and can thus simply derive a new unused address, which is still contained in the static backup.

The issue is how to derive a new address for the receiver?

I'm going to list a couple methods I know of, with pros and cons to it. Please continue the conversation with more techniques and trade-offs.

Just reuse the address

The transaction has never been broadcasted to the network, so ONLY coordinator and round participants know about the address reuse, not an outside observer. It might ok to trust that these participants are not-malicious, and then just ignore the problem and reuse the address.

As the CoinJoin should be trustless, this is not a solution.

Child xpub

Instead of asking for a single address, the sender can ask the receiver for a child xpub. Now the sender wallet can derive multiple addresses for the receiver, which are all in his static backup - and this is as good as we do it currently for the sender's wallet. The receiver does not be online to communicate a new address.

The big downside is that it breaks the current flow of payment request, as not a single address, but an xpub needs to be provided. Thus, only receivers who "update" their wallets and workflows to give out xpubs, a new one for every user can be part of the CoinJoin. Further, the sender wallet needs to sync the chain to find out which addresses are used / not used. This can take time.

The sender will know multiple addresses of the receiver, and thus potentially can follow a transaction history. Thus it is important for the sender to CoinJoin out of the child xpub into a different unleaked xpub. This is doable for wasabi users, but not for other wallet users.

Stealth address

Stealth addresses are static strings that the receiver generates, which then can be used by any sender in a Diffie-Hellman key exchange. The sender will add a random number to the stealth address, which generates a new public key. The receiver can generate a private key corresponding to that public key, if he gets the random number too. The receiver does not need to be online.

This might work, but it still requires adoption of a new workflow, and there is no beautiful implementation so far.

Public key tweaking [schnorr or ecdsa]

If a public key of the receiver is known by the sender, then it can be tweaked with a random number so that a new public key is generated, and when the receiver knows the random number too, he can derive the according private key. With taproot, public keys are exposed in the address, but we cannot wait for taproot to be activated and widely used. The crypto magic is also possible with ECDSA, however, current Bitcoin addresses do not expose the public key. So, the sender needs to figure out a public key of the receiver, which can be done if the sender knows a spent output of the receiver [which exposes the public key in the witness script]. The receiver does not have to be online.

This either requires a new address type, or the receiver to give out the public key directly to the sender, or some arbitrary guessing what a spent coin of the receiver is.

Pay 2 endpoint

I don't mean the mini CoinJoin, but rather, that the receiver gives out an IP address or tor hidden service, that the sender can ping and get a new unused address from.

This breaks the workflow again, as now a endpoint, not an address needs to be communicated up front. The receiver also needs to be online at the time the sender makes the CoinJoin.

[MaxHillebrand]

I think, that any serious proposal [excluding address reuse] break user flow.
Now, the question is, which of the possible options are most commonly used by multiple wallets already now?

And I think, that this is the hierarchical deterministic wallet structure - as all [?] wallets use it, and most wallets allow the function to derive a new child xpub. The more I think about it, the more I lean towards favoring it.

[MaxHillebrand]

I was thinking about my statement again, and I'm not sure my intuition is correct here.

This means, that the coordinator and all participants have seen all addresses and associated receiving amounts. For the next attempted round, the old address should me marked as burned and not used again, and a new address should be generated for this round.

Is it really a problem that the output address are reused? As long as these reused addresses cannot be linked to the input, there is not inherently a privacy problem. They do not reveal common ownership of several coins [as with "regular" onchain address reuse].

• Alice, Bob, Charlie and Mallory make a WabiSabi, input registration passes, output registration passes. Now all three have their inputs and output addresses revealed.
• Mallory refuses to sign, thus the round fails. In the blame phase, it is clear that Mallory was the bad one, and thus her input is banned [her output is not known to be hers].
• Now, the next attempt stars. If Alice, Bob, and Charlie use the same inputs, and the same output addresses, then still, there is no link between input and outputs. There seems to not be a privacy issue at all. All they know is what Mallories address was, but that is Mallories issue.

---

• There is an issue, if David is allowed to enter the second attempted round. Because now we have one [or several] new inputs, and one [or several] new outputs, that belong to David. These were not part of the previous round, and thus Alice, Bob, Charlie and Mallory can make a link between David's input and output.

---

I'm not certain on other reasons why the current CoinJoin protocol uses a new address after each failed round - I'm probably missing some important detail - please say so if this is the case.

However, I think that as long as no new peers are allowed to enter a second attempt after a DoS attack, there is no inherent issue with address reuse. If this is the case, then we do not at all need to worry about deriving addresses for the receiver, we simply use the same address over and over again, until the round succeeds.

Now, there is an issue that this reduces the anonset size for every failed attempt, and there are no new users coming in to increase the anonset size again. This might be a downside. But, I think it is a negligible trade-off if it allows us to do the sending in a mix...

[real-or-random]

I'm not certain on other reasons why the current CoinJoin protocol uses a new address after each failed round - I'm probably missing some important detail - please say so if this is the case.

However, I think that as long as no new peers are allowed to enter a second attempt after a DoS attack, there is no inherent issue with address reuse. If this is the case, then we do not at all need to worry about deriving addresses for the receiver, we simply use the same address over and over again, until the round succeeds.

The same issue appears when peers leave. Say Bob does not participate in the second round, possibly because the attacker interferes with Bob's connection or the coordinator simply denies that Bob was responding. Then Mallory get a very similar intersection attack against Bob.

This is an attack described in the CoinShuffle++ paper. I don't think there's a way around this in CoinJoin because you Mallory can always refuse to sign. In this model with the coordinator, it's even easier for a malicious coordinator: it can simply claim that Bob hasn't sent a signature in the first round and then exclude Bob.

Importantly, the concern of reusing messages is not limited to recipient addresses. You can get fresh recipient address using any of the methods mentioned above. But you cannot get fresh payment amounts. It's just not possible to re-randomize the payment amount unless you have Confidential Transaction and can re-randomize the commitment instead. This is exactly the reason why ValueShuffle supports real payments and mixing simultaneously (if you can derive fresh recipient addresses) while CoinShuffle(++) does not.

See the mentioned papers or my talk here https://www.youtube.com/watch?v=BPNs9EVxWrA&feature=youtu.be&t=5069, where I mention this problem.

[MaxHillebrand]

You are of course right @real-or-random - I completely missed that the user who fails to sign can be honest and the victim of a DoS attack. Thank you for bringing it up so clearly.

So, there is no way around it, we need to derive multiple addresses for the receiver.

Also a good point regarding the payment amounts. For self-spends, this can be presumably randomized without many issues. However, many payments require a precise amount to be send, and even slight over/under payments might be rejected. Since CT won't make it into the base layer any time soon, two questions come up...

• How high does the percentage of the value have to change so that it is non-trivial to link the two amounts? A random value within the range of +-5%?
• What percentage of payment value deviation is usually accepted by merchants?

[real-or-random]

How high does the percentage of the value have to change so that it is non-trivial to link the two amounts?

To be honest, I fear that "non-trivial" is not good enough. I don't believe you can make payments work with such tricks without sacrificing privacy.

[nothingmuch]

i don't think that a percentage change in the value is the right way of framing it, if the difference is small enough to be negligible to the payer/merchant, then it's likely small enough to be a reasonable heuristic.

i don't know how i feel about this, ot1h there seems to be a slippery slope, that of providing weak privacy assurances that create a false sense of security. otoh it also seems like a perfect-is-the-enemy-of-the-good situation: the coordinator has an incentive (reputation, fees) not to disrupt, a network level adversary has to be pretty powerful to disrupt the protocol in a targeted way, and although this is not solvable on a fundamental level, the outcome of a successful attack is more or less equivalent to the user simply making a payment with the typical transaction structure, so it could be argued that in some ways even the worst case might still be strictly an improvement from a privacy POV.

if clients are conservative in their behaviour, for example perhaps by limiting the number of attempts to log(other inputs), and not participating if the subsequent set of inputs to a reattempted isn't a proper subset, then it should be possible to fail a payment under adversarial conditions. however, in that case of failure i'm not sure what a sensible UX might be - display an error saying that the user is under a suspected de-anonymization attack? what recourse would they have at that point?

i suppose my gut feeling is that the benefits of supporting payments seem to outweigh the downsides, so mainly i'd like to hear arguments against this

[nopara73]

Another, simple idea here:

• Sender knows a public address of the receiver.
• Sender builds and sign a tx with the public address of the receiver.
• Sender sends the tx to the receiver.
• Receiver replaces the address and gives the tx back.
• Sender signs and broadcasts.

If the receiver doesn't see the sender broadcast within a timeout, the receiver broadcasts.

The sender could play it out by spending his coins, but that imposes a cost, so the sender would not be able to learn too much addresses of the receiver without paying a lot.