Inside Bitcoin
Opening the selected file…
Inside Bitcoin
Opening the selected file…
The code behind the network, with room to understand it.
Release published 2026-10-28 · Snapshot fetched 2026-11-01. Latest stable release at fetch time; development branches and Git history are excluded. Only the selected code window and visible folders load here.
251while (utxo_pool[next_utxo - 1].GetSelectionAmount() == utxo_pool[next_utxo].GetSelectionAmount()) {252if (next_utxo >= utxo_pool.size() - 1) {253// Reached end of UTXO pool skipping clones: SHIFT instead254should_shift = true;255break;256}257// Skip clone: previous UTXO is equivalent and unselected258++next_utxo;259}260}261}263result.SetSelectionsEvaluated(curr_try);265if (best_selection.empty()) {266return max_tx_weight_exceeded ? ErrorMaxWeightExceeded() : util::Error();267}269for (const size_t& i : best_selection) {270result.AddInput(utxo_pool.at(i));271}273return result;274}277/*278* TL;DR: Coin Grinder is a DFS-based algorithm that deterministically searches for the minimum-weight input set to fund279* the transaction. The algorithm is similar to the Branch and Bound algorithm, but will produce a transaction _with_ a280* change output instead of a changeless transaction.281*282* Full description: CoinGrinder can be thought of as a graph walking algorithm. It explores a binary tree283* representation of the powerset of the UTXO pool. Each node in the tree represents a candidate input set. The tree’s284* root is the empty set. Each node in the tree has two children which are formed by either adding or skipping the next285* UTXO ("inclusion/omission branch"). Each level in the tree after the root corresponds to a decision about one UTXO in286* the UTXO pool.287*288* Example:289* We represent UTXOs as _alias=[effective_value/weight]_ and indicate omitted UTXOs with an underscore. Given a UTXO290* pool {A=[10/2], B=[7/1], C=[5/1], D=[4/2]} sorted by descending effective value, our search tree looks as follows:291*292* _______________________ {} ________________________293* / \294* A=[10/2] __________ {A} _________ __________ {_} _________295* / \ / \296* B=[7/1] {AB} _ {A_} _ {_B} _ {__} _297* / \ / \ / \ / \298* C=[5/1] {ABC} {AB_} {A_C} {A__} {_BC} {_B_} {__C} {___}299* / \ / \ / \ / \ / \ / \ / \ / \300* D=[4/2] {ABCD} {ABC_} {AB_D} {AB__} {A_CD} {A_C_} {A__D} {A___} {_BCD} {_BC_} {_B_D} {_B__} {__CD} {__C_} {___D} {____}301*302*303* CoinGrinder uses a depth-first search to walk this tree. It first tries inclusion branches, then omission branches. A304* naive exploration of a tree with four UTXOs requires visiting all 31 nodes:305*306* {} {A} {AB} {ABC} {ABCD} {ABC_} {AB_} {AB_D} {AB__} {A_} {A_C} {A_CD} {A_C_} {A__} {A__D} {A___} {_} {_B} {_BC}307* {_BCD} {_BC_} {_B_} {_B_D} {_B__} {__} {__C} {__CD} {__C} {___} {___D} {____}308*309* As powersets grow exponentially with the set size, walking the entire tree would quickly get computationally310* infeasible with growing UTXO pools. Thanks to traversing the tree in a deterministic order, we can keep track of the311* progress of the search solely on basis of the current selection (and the best selection so far). We visit as few312* nodes as possible by recognizing and skipping any branches that can only contain solutions worse than the best313* solution so far. This makes CoinGrinder a branch-and-bound algorithm314* (https://en.wikipedia.org/wiki/Branch_and_bound).315* CoinGrinder is searching for the input set with lowest weight that can fund a transaction, so for example we can only316* ever find a _better_ candidate input set in a node that adds a UTXO, but never in a node that skips a UTXO. After317* visiting {A} and exploring the inclusion branch {AB} and its descendants, the candidate input set in the omission318* branch {A_} is equivalent to the parent {A} in effective value and weight. While CoinGrinder does need to visit the319* descendants of the omission branch {A_}, it is unnecessary to evaluate the candidate input set in the omission branch320* itself. By skipping evaluation of all nodes on an omission branch we reduce the visited nodes to 15:321*322* {A} {AB} {ABC} {ABCD} {AB_D} {A_C} {A_CD} {A__D} {_B} {_BC} {_BCD} {_B_D} {__C} {__CD} {___D}323*324* _______________________ {} ________________________325* / \326* A=[10/2] __________ {A} _________ ___________\____________327* / \ / \328* B=[7/1] {AB} __ __\_____ {_B} __ __\_____329* / \ / \ / \ / \330* C=[5/1] {ABC} \ {A_C} \ {_BC} \ {__C} \331* / / / / / / / /332* D=[4/2] {ABCD} {AB_D} {A_CD} {A__D} {_BCD} {_B_D} {__CD} {___D}333*334*335* We refer to the move from the inclusion branch {AB} via the omission branch {A_} to its inclusion-branch child {A_C}336* as _shifting to the omission branch_ or just _SHIFT_. (The index of the ultimate element in the candidate input set337* shifts right by one: {AB} ⇒ {A_C}.)338* When we reach a leaf node in the last level of the tree, shifting to the omission branch is not possible. Instead we339* go to the omission branch of the node’s last ancestor on an inclusion branch: from {ABCD}, we go to {AB_D}. From340* {AB_D}, we go to {A_C}. We refer to this operation as a _CUT_. (The ultimate element in341* the input set is deselected, and the penultimate element is shifted right by one: {AB_D} ⇒ {A_C}.)342* If a candidate input set in a node has not selected sufficient funds to build the transaction, we continue directly343* along the next inclusion branch. We call this operation _EXPLORE_. (We go from one inclusion branch to the next344* inclusion branch: {_B} ⇒ {_BC}.)345* Further, any prefix that already has selected sufficient effective value to fund the transaction cannot be improved346* by adding more UTXOs. If for example the candidate input set in {AB} is a valid solution, all potential descendant347* solutions {ABC}, {ABCD}, and {AB_D} must have a higher weight, thus instead of exploring the descendants of {AB}, we348* can SHIFT from {AB} to {A_C}.349*350* Given the above UTXO set, using a target of 11, and following these initial observations, the basic implementation of351* CoinGrinder visits the following 10 nodes:352*353* Node [eff_val/weight] Evaluation354* ---------------------------------------------------------------355* {A} [10/2] Insufficient funds: EXPLORE356* {AB} [17/3] Solution: SHIFT to omission branch357* {A_C} [15/3] Better solution: SHIFT to omission branch358* {A__D} [14/4] Worse solution, shift impossible due to leaf node: CUT to omission branch of {A__D},359* i.e. SHIFT to omission branch of {A}360* {_B} [7/1] Insufficient funds: EXPLORE361* {_BC} [12/2] Better solution: SHIFT to omission branch362* {_B_D} [11/3] Worse solution, shift impossible due to leaf node: CUT to omission branch of {_B_D},363* i.e. SHIFT to omission branch of {_B}364* {__C} [5/1] Insufficient funds: EXPLORE365* {__CD} [9/3] Insufficient funds, leaf node: CUT366* {___D} [4/2] Insufficient funds, leaf node, cannot CUT since only one UTXO selected: done.367*368* _______________________ {} ________________________369* / \370* A=[10/2] __________ {A} _________ ___________\____________371* / \ / \372* B=[7/1] {AB} __\_____ {_B} __ __\_____373* / \ / \ / \374* C=[5/1] {A_C} \ {_BC} \ {__C} \375* / / / /376* D=[4/2] {A__D} {_B_D} {__CD} {___D}377*378*379* We implement this tree walk in the following algorithm:380* 1. Add `next_utxo`381* 2. Evaluate candidate input set382* 3. Determine `next_utxo` by deciding whether to383* a) EXPLORE: Add next inclusion branch, e.g. {_B} ⇒ {_B} + `next_uxto`: C384* b) SHIFT: Replace last selected UTXO by next higher index, e.g. {A_C} ⇒ {A__} + `next_utxo`: D385* c) CUT: deselect last selected UTXO and shift to omission branch of penultimate UTXO, e.g. {AB_D} ⇒ {A_} + `next_utxo: C386*387* The implementation then adds further optimizations by discovering further situations in which either the inclusion388* branch can be skipped, or both the inclusion and omission branch can be skipped after evaluating the candidate input389* set in the node.390*391* @param std::vector<OutputGroup>& utxo_pool The UTXOs that we are choosing from. These UTXOs will be sorted in392* descending order by effective value, with lower weight preferred as a tie-breaker. (We can think of an output393* group with multiple as a heavier UTXO with the combined amount here.)394* @param const CAmount& selection_target This is the minimum amount that we need for the transaction without considering change.395* @param const CAmount& change_target The minimum budget for creating a change output, by which we increase the selection_target.396* @param int max_selection_weight The maximum allowed weight for a selection result to be valid.397* @returns The result of this coin selection algorithm, or std::nullopt398*/399util::Result<SelectionResult> CoinGrinder(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, CAmount change_target, int max_selection_weight)400{401std::sort(utxo_pool.begin(), utxo_pool.end(), descending_effval_weight);402// The sum of UTXO amounts after this UTXO index, e.g. lookahead[5] = Σ(UTXO[6+].amount)403std::vector<CAmount> lookahead(utxo_pool.size());404// The minimum UTXO weight among the remaining UTXOs after this UTXO index, e.g. min_tail_weight[5] = min(UTXO[6+].weight)405std::vector<int> min_tail_weight(utxo_pool.size());407// Calculate lookahead values, min_tail_weights, and check that there are sufficient funds408CAmount total_available = 0;409int min_group_weight = std::numeric_limits<int>::max();410for (size_t i = 0; i < utxo_pool.size(); ++i) {411size_t index = utxo_pool.size() - 1 - i; // Loop over every element in reverse order412lookahead[index] = total_available;413min_tail_weight[index] = min_group_weight;414// UTXOs with non-positive effective value must have been filtered415Assume(utxo_pool[index].GetSelectionAmount() > 0);416total_available += utxo_pool[index].GetSelectionAmount();417min_group_weight = std::min(min_group_weight, utxo_pool[index].m_weight);418}420const CAmount total_target = selection_target + change_target;421if (total_available < total_target) {422// Insufficient funds423return util::Error();424}426// The current selection and the best input set found so far, stored as the utxo_pool indices of the UTXOs forming them427std::vector<size_t> curr_selection;428std::vector<size_t> best_selection;430// The currently selected effective amount, and the effective amount of the best selection so far431CAmount curr_amount = 0;432CAmount best_selection_amount = MAX_MONEY;434// The weight of the currently selected input set, and the weight of the best selection435int curr_weight = 0;436int best_selection_weight = max_selection_weight; // Tie is fine, because we prefer lower selection amount438// Whether the input sets generated during this search have exceeded the maximum transaction weight at any point439bool max_tx_weight_exceeded = false;441// Index of the next UTXO to consider in utxo_pool442size_t next_utxo = 0;444/*445* You can think of the current selection as a vector of booleans that has decided inclusion or exclusion of all446* UTXOs before `next_utxo`. When we consider the next UTXO, we extend this hypothetical boolean vector either with447* a true value if the UTXO is included or a false value if it is omitted. The equivalent state is stored more448* compactly as the list of indices of the included UTXOs and the `next_utxo` index.449*450* We can never find a new solution by deselecting a UTXO, because we then revisit a previously evaluated451* selection. Therefore, we only need to check whether we found a new solution _after adding_ a new UTXO.452*453* Each iteration of CoinGrinder starts by selecting the `next_utxo` and evaluating the current selection. We454* use three state transitions to progress from the current selection to the next promising selection:455*456* - EXPLORE inclusion branch: We do not have sufficient funds, yet. Add `next_utxo` to the current selection, then457* nominate the direct successor of the just selected UTXO as our `next_utxo` for the458* following iteration.459*460* Example:461* Current Selection: {0, 5, 7}462* Evaluation: EXPLORE, next_utxo: 8463* Next Selection: {0, 5, 7, 8}464*465* - SHIFT to omission branch: Adding more UTXOs to the current selection cannot produce a solution that is better466* than the current best, e.g. the current selection weight exceeds the max weight or467* the current selection amount is equal to or greater than the target.468* We designate our `next_utxo` the one after the tail of our current selection, then469* deselect the tail of our current selection.470*471* Example:472* Current Selection: {0, 5, 7}473* Evaluation: SHIFT, next_utxo: 8, omit last selected: {0, 5}474* Next Selection: {0, 5, 8}475*476* - CUT entire subtree: We have exhausted the inclusion branch for the penultimately selected UTXO, both the477* inclusion and the omission branch of the current prefix are barren. E.g. we have478* reached the end of the UTXO pool, so neither further EXPLORING nor SHIFTING can find479* any solutions. We designate our `next_utxo` the one after our penultimate selected,480* then deselect both the last and penultimate selected.481*482* Example:483* Current Selection: {0, 5, 7}484* Evaluation: CUT, next_utxo: 6, omit two last selected: {0}485* Next Selection: {0, 6}486*/487auto deselect_last = [&]() {488OutputGroup& utxo = utxo_pool[curr_selection.back()];489curr_amount -= utxo.GetSelectionAmount();490curr_weight -= utxo.m_weight;491curr_selection.pop_back();492};494SelectionResult result(selection_target, SelectionAlgorithm::CG);495bool is_done = false;496size_t curr_try = 0;497while (!is_done) {498bool should_shift{false}, should_cut{false};499// Select `next_utxo`500OutputGroup& utxo = utxo_pool[next_utxo];