Here is my proposed path forward after some in-person discussion.
- Merge #10637 which simply adds a preliminary attempt to find an exact match using Branch and Bound and then falls back to the existing Core algo.
Then we’ll replace the fallback to an improved algo:
- Remove Core’s exact match finding. (If BnB doesn’t find exact match, just resign yourself to creating change)
- Use effective value for adding inputs.
- Aim for a target which is actual target + some minimum reasonable change.
- Consider inputs lower than the target value separately from inputs > than target value.
- If we can achieve target with lower value inputs, randomly add them until we are above the target and return.
- If we can’t achieve target with lower value inputs, randomly select one of the higher value inputs and return.
- Handle edge cases where we can’t create a reasonable size change, but do have enough balance.
The change from the existing Core fallback here will be that we are no longer spending uneconomic inputs, but we will still by default be highly consolidating as we are always combining lower value inputs to meet our target when possible. When fees are lower, more inputs will automatically be available for inclusion. Also when it’s not possible to find a solution from lower value inputs, we won’t always use the smallest high valued output.
In the future we can reconsider this 100% bias towards always using lower value inputsand consider other factors such as current feerate and size of transaction required in deciding whether to consolidate or use just one higher value input. It may also be the case that Branch and Bound performance in finding exact matches improves when we more often use larger inputs and don’t always get rid of our small ones.
