Skip split when exact change is already available for undelegation

[plaidfinch]

Currently, we unconditionally perform a spend to ourselves prior to an undelegation, in order to prevent locking up change in quarantine. However, if we already have exact change, this split transaction wastes an unnecessary fee and takes longer to execute, having to wait for two consecutive transactions.

We should query to find out whether it is possible to make exact change for the undelegation before attempting to perform the split. This is more general than "find exactly one note of the right value"; it means finding any set of notes that exactly add up to the right value. This is, unfortunately, equivalent to the NP-complete positive subset sum problem. However, for most users, the number of distinct delegation tokens for a given validator will be small, which means it is likely tractable in reality. By ordering the search to proceed simultaneously "down" and "up" from the extremes of "undelegate everything" and "undelegate nothing", we can ensure that the simplest solutions, likely to be the consequence of actual user choices, are encountered first. We can also just give up if the search exceeds a time threshold without being exhaustive.

[hdevalence]

Hmm, wouldn't this potentially reveal information about the user's delegation? If we did this, and someone saw an undelegation where there's an empty block preceding it, someone could learn that the delegation was an exact amount. I'm not sure this is a big problem, but it seems possibly easier and safer to do nothing here?

[plaidfinch]

You're right that it would reveal that information in that circumstance, though I'm struggling to find any real world way that this information could be exploited. It seems potentially worth optimizing this mostly because I anticipate that "undelegate everything" and "undelegate exactly the amount I last delegated" are likely to be common kinds of action, so it seems nice to avoid charging unnecessary fees. But if fees remain low, then this ends up not being a problem in reality, so maybe it's not worth it. Someone who is doing a lot of undelegation for some reason can write their own bot that does this logic, after all.

[plaidfinch]

This is obviated by the tokenized unbonding mechanism we now have, which doesn't require making exact change prior to undelegation.