docs: add doc comment for SRD selection algorithm

yancyribbens commented at 1:05 pm on October 14, 2025: contributor

The params documentation is missing change_fee and the description is lacking recent changes.

DrahtBot added the label Docs on Oct 14, 2025

DrahtBot commented at 1:06 pm on October 14, 2025: contributor

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Code Coverage & Benchmarks

For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/33622.

Reviews

See the guideline for information on the review process.

Type	Reviewers
Concept ACK	murchandamus

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

LLM Linter (✨ experimental)

Possible typos and grammar issues:

*outputs until the target is satisfied. If the maximum weight is exceeded, the OutputGroups -> *output groups until the target is satisfied. If the maximum weight is exceeded, the OutputGroups [“outputs” is unclear here; “output groups” matches the term used elsewhere and improves clarity. Also remove double space after sentence break.]
- with the lowest effective value are removed from the selection until weight is acceptable. -> *with the lowest effective value are removed from the selection until the selection weight is acceptable. [adds “the selection” to make the noun explicit and the phrase grammatically complete]
- By removing the lowest effective value, the average effective value per weight of the selection is increased and thus reducing the average selection size. -> *By removing the OutputGroups with the lowest effective value, the average effective value per weight of the selection is increased, thus reducing the average selection size. [specifies what is removed and fixes the verb phrasing/structure]

drahtbot_id_5_m

fanquake requested review from murchandamus on Oct 14, 2025

yancyribbens commented at 4:52 pm on October 14, 2025: contributor

cc @furszy as related to https://github.com/bitcoin/bitcoin/issues/33168

in src/wallet/coinselection.cpp:538 in e6c439dcb2

532@@ -533,6 +533,21 @@ class MinOutputGroupComparator
533     }
534 };
535 
536+/* Randomized Single Round Selection Algorithm.
537+*
538+* Full Description: This algorithm works by selecting inputs randomly until the target amount is

brunoerg commented at 6:46 pm on October 14, 2025:

e6c439dcb23e1a0d03261734fd89412a15b1932a: I don’t this it needs this “Full Description:”. It seems obvious that is the description of the algorithm.

0This algorithm works by selecting inputs randomly until the target amount is

yancyribbens commented at 8:20 pm on October 14, 2025:

Some of the other algorithms use that wording, for example see coin-grinder: https://github.com/bitcoin/bitcoin/pull/33622/files#diff-d473ed8396f9451afb848923cfcfaa630c9811a78e07f3ae1ffd3a65da218accR208. Therefore just copying a pattern that already exists. Do you not like that wording in coin-grinder also?

brunoerg commented at 8:42 pm on October 14, 2025:

I think coin grinder explanation is more complex, so that makes sense. But anyway, feel free to ignore it.

yancyribbens commented at 11:25 pm on October 14, 2025:

No worries I can remove it then.

in src/wallet/coinselection.cpp:544 in e6c439dcb2

539+* reached or exceeded.  If the maximum weight is exceeded, then the least valuable inputs are
540+* removed from the selection.  In so doing, minimize the number of UTXOs included in the result
541+* by preferring UTXOs with higher value.  Note that this selection algorithm should always produce
542+* a non-dust change output.
543+*
544+* @param std::vector<OutputGroup>& utxo_pool The UTXOs that we are choosing from.

brunoerg commented at 7:04 pm on October 14, 2025:

Aren’t there already documentation about the parameters in coinselection.h? If so, we should just add the description there instead.

yancyribbens commented at 8:25 pm on October 14, 2025:

There’s not much presidence for this when looking at how the other algorithms are documented. coin-grinder seems to have it documented in both the headers file and the cpp file.

yancyribbens commented at 8:26 pm on October 14, 2025:

I don’t care much either way where the doc comments are, just that it exists someplace that is findable.

brunoerg commented at 8:43 pm on October 14, 2025:

I think it’s weird to have a documentation about the paratemers in coinselection.h and another documentation about the same parameters but with different wording/explanation in coinselection.cpp.

yancyribbens commented at 11:35 pm on October 14, 2025:

Hmm it’s probably silly to have it both places. BnB for example does not have it’s params defined in .h at all, nor its description for that matter. And the params in .h for SRD are missing change_fee :face_palm:.

Honestly, all these comments should be in the header file, right? It would be really hard to get people to review that kind of a change though.

yancyribbens force-pushed on Oct 14, 2025

yancyribbens commented at 11:59 pm on October 14, 2025: contributor

@brunoerg thanks for reviewing. Instead of adding new docs I improved the comments in .h instead. If only the other selection algorithms did that as well..

yancyribbens force-pushed on Oct 15, 2025

doc: add missing param description to SRD d18a88a203

yancyribbens force-pushed on Oct 15, 2025

in src/wallet/coinselection.h:454 in d18a88a203 outdated

450@@ -451,6 +451,7 @@ util::Result<SelectionResult> CoinGrinder(std::vector<OutputGroup>& utxo_pool, c
451  *
452  * @param[in]  utxo_pool    The positive effective value OutputGroups eligible for selection
453  * @param[in]  target_value The target value to select for
454+ * @param[in]  change_fee The amount added to CHANGE_LOWER which ensures a non-dust change output will be created.

murchandamus commented at 1:19 pm on November 3, 2025:

This comment is unhelpful. It provides the information that is already available from the code, but does not correctly explain the abstract context.

0 * [@param](/bitcoin-bitcoin/contributor/param/)[in]  change_fee The cost of adding the change output to the transaction at the transaction’s feerate. Budgeting separately ensures that the change’s amount will be at least CHANGE_LOWER.

yancyribbens commented at 5:16 pm on November 3, 2025:

This edit is a tautology. No matter what the change budgeting is, the change amount will be at least CHANGE_LOWER since this value is added to CHANGE_LOWER. Maybe it’s not the place to explain to users of the API why it matters that CHANGE_LOWER may not be enough of a change budget, although I would have no idea why without reading the commit that added this parameter.

yancyribbens commented at 11:16 am on November 9, 2025:

I think I see now what you are getting on when you say “Budgeting separately”. You’re saying that by budgeting separately you are providing a value to be used for change_fee and any value used for change fee will be at least CHANGE_LOWER. If there is no other discussion on this i’ll accept it and move on, but this is pretty confusing imo. It also doesn’t make clear that you can just not “budget separately” and the change_fee will be equal to CHANGE_LOWER.

yancyribbens commented at 11:26 am on November 9, 2025:

I think ideally a default parameter value is used here: CAmount change_fee = CHANGE_LOWER. That way it’s made more clear that either you budget separately for the change_fee or it will default to CHANGE_LOWER. In most cases CHANGE_LOWER should be plenty for a change_fee.

in src/wallet/coinselection.h:453 in bbdfe22902 outdated

446@@ -447,7 +447,10 @@ util::Result<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool
447 util::Result<SelectionResult> CoinGrinder(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, CAmount change_target, int max_selection_weight);
448 
449 /** Select coins by Single Random Draw. OutputGroups are selected randomly from the eligible
450- * outputs until the target is satisfied
451+ * outputs until the target is satisfied.  If the maximum weight is exceeded, then the least
452+ * valuable outputs are removed from the selection.  In so doing, minimize the number of UTXOs
453+ * included in the result by preferring UTXOs with higher value.  Note that this selection
454+ * algorithm should always produce a non-dust change output.

murchandamus commented at 1:35 pm on November 3, 2025:

SRD does NOT minimize the number of UTXOs included in the result. It only ensures that the selection adheres to the weight limit. Minimizing would imply that the selection is further pruned beyond adhering to the weight limit. The last sentence should also be amended to clarify that SRD does not always return a result, but when it does, the selection will always create a change output:

0 * outputs until the target is satisfied.  If the maximum weight is exceeded, the OutputGroups with the lowest
1 * effective value are removed from the selection until weight is acceptable. If a solution is found, the resulting
2 * selection will produce a change output with an amount of at least CHANGE_LOWER.

yancyribbens commented at 5:02 pm on November 3, 2025:

SRD does NOT minimize the number of UTXOs included in the result. It only ensures that the selection adheres to the weight limit. Minimizing would imply that the selection is further pruned beyond adhering to the weight limit.

Your edit’s make sense, thanks for the clarification. However, I thought it would be helpful to note why the OutputGroups with the lowest effective_value are removed when the weight is exceeded. This seems at first counter-intuitive since it’s not removing OutputGroups according to weight when the weight is exceeded.

Removing UTXO’s with the lowest effective_value minimizes the number of UTXOS included in the result when the maximum weight is exceeded. That is, by removing the lowest effective_value utxos leaves only large value utxos which means there are less required to reach a target.

murchandamus commented at 1:41 am on November 6, 2025:

Removing UTXO’s with the lowest effective_value minimizes the number of UTXOS included in the result when the maximum weight is exceeded.

Maybe we have diverging understandings of what the verb “minimize” means. I understand it to mean “reduce to a minimum”. Are you using it as a synonym for “reduce”? Or do you think that removing a single OutputGroup always reduces the selection to the minimum necessary selection?

Because, per my understanding of the verb, this algorithm does not minimize the selection when the weight is overshot. To give a counterexample, if the addition of a tenth OutputGroup causes the weight to be exceeded, maybe removing a single OutputGroup is sufficient to drop the selection below the weigh limit, leaving nine OutputGroups selected even if the single tenth OutputGroup among the selected were to be sufficient to fund the whole transaction. I would understand “minimizing” here as all other nine OGs being removed once the limit is exceeded, and that’s not what we do.

why the OutputGroups with the lowest effective_value are removed

When the maximum weight is exceeded, this implies that the current selection has an insufficient amount of value per weight. Most wallets only have one UTXO per OutputGroup, and many only one type of UTXOs. In that case, their weight would not differ in the first place. Removing the OutputGroup with the lowest effective_value is a simple algorithm that increases the average effective_value per weight of the selection. Especially if there are OutputGroups with multiple UTXOs or UTXOs with different weights, this simple heuristic is insufficient to guarantee that a solution will be found even when one exists, but in most cases, it will get the job done. To guarantee that an existing solution is found, a more complex approach such as CoinGrinder would be necessary.

yancyribbens commented at 12:47 pm on November 6, 2025:

Are you using it as a synonym for “reduce”?

Yes, that is correct. I was using it in terms of a minimization function, that is, it is a step in the direction of a more minimal solution. Agree to remove that wording though if your don’t like it; I can see why it’s confusing.

Removing the OutputGroup with the lowest effective_value is a simple algorithm that increases the average effective_value per weight of the selection.

Said another way, the selection density is biased towards a higher density selection when max weight is exceeded?

this simple heuristic is insufficient to guarantee that a solution will be found even when one exists, but in most cases, it will get the job done. To guarantee that an existing solution is found, a more complex approach such as CoinGrinder would be necessary.

Agree

yancyribbens commented at 11:57 am on November 9, 2025:

I updated the documentation per out discussion here to read:

If the maximum weight is exceeded, the OutputGroups with the lowest effective value are removed from the selection until weight is acceptable. By removing the lowest effective value, the average effective value per weight of the selection is increased and thus reducing the average selection size. If a solution is found, the resulting selection will produce a change output with an amount of at least CHANGE_LOWER.

murchandamus commented at 1:39 pm on November 3, 2025: contributor

Concept ACK on improving the documentation, but there is room for improvement on the specific phrasing.

yancyribbens force-pushed on Nov 9, 2025

DrahtBot added the label CI failed on Nov 9, 2025

Update src/wallet/coinselection.h

Co-authored-by: Mark "Murch" Erhardt <murch@murch.one>

ea8d9953be

doc: improve description for SRD selection algorithm

Description is missing recent changes to the selection process.

c2d05bf0be

yancyribbens force-pushed on Nov 9, 2025

DrahtBot removed the label CI failed on Nov 9, 2025

docs: add doc comment for SRD selection algorithm #33622

Code Coverage & Benchmarks

Reviews

LLM Linter (✨ experimental)