Avoid re-use of change address if unused in a shuffle

[imaginaryusername]

After #68 , there will always be one shuffler in a round that has no change address. The guy will nevertheless "leak" the change address to other shufflers - ordinarily this is not a big deal since change is trivially linked to input anyway. But if it's not used, the shuffler then goes on to re-use the address in another shuffle. This undesirably results in leaking linkage to other shufflers in the current pool unnecessarily, about an unrelated future shuffle whether for shuffle output or change output.

Potential solutions:

1) Do nothing. Might not be a big deal, but curious for inputs from other people. Information leak is limited - you'll have to isolate victim into reliably being the minimum party. But information leak is information leak, and can be harmful on a large scale surveillance basis...

2) Freeze an address if unused. Might be draconian, and can result in gap limit complications if too many are skipped, but straightforward to implement. Alternatively some scheme like reserving certain addresses for change (odd numbers?) might also work, but each has downsides.

3) Exchange change addresses later, and don't supply a change address if found yourself to be minimum (peers should ignore checking for change address from the minimum peer). Probably the most robust, but may involve more change in code, which can be undesirable.

What do you guys think?

[cculianu]

It's subtle but it is a tiny bit of weaksauce. That change that everybody saw can be used later as shuffled output. Note this issue is new because now both change and shuffled end up on the same derivation path (change) so the wallet can pick up either/or of the two and mix them up in subsequent rounds.

Not sure what the best approach is. I'm nervous to mess with the fragile protocol internals authored by Yura. The code already doesn't like to be changed much. :)

One possible hack is to just always give even-numbered address positions to shuffled and odd-numbered to "change". This way at least it's not like an address you told everybody about in a previous round as belonging to "change" ends up with a shuffled output on it. It's not perfect either but it's a slight improvement.

[imaginaryusername]

If the change in code is minimal, I'll endorse the odd-even idea as a weaker version of (2) that doesn't generate complications in gap limit (no wallets have gap limit = 1, hopefully!). It doesn't address the problem completely unlike (3), but does alleviate greatly.

[cculianu]

Hey @imaginaryusername so I thought about this today and it's a small detail that needed fixing. Latest commit takes care of it.

Basically the wallet "remembers" the set of change addresses it has published to the network and only uses those for change outputs to a shuffle (and not for shuffled address outputs). This change should address this issue fully, I hope.

[markblundeberg]

Interesting point, good catch @imaginaryusername .

[cculianu]

Yeah of note is I also had to prohibit those change addr's from being used in the "Send" tab as well! (After all they are "known" to the world). They are only good for shuffled change outputs once they've been prostituted that way.. :P

[imaginaryusername]

I can't wait for #72 so we can make all these super easy =]

[markblundeberg]

Another brain twister: if you assign an address for the shuffled output but then the shuffle fails at the last step, it would be a privacy problem if that address were again used in another shuffle, since the people from the last shuffle would have some correlative info about that address already.

[cculianu]

Eh. You are right. And we have to balance that against creating huge gaps in the address book... Good thing I made that "beyond the gap" scanner.. 👍