251     * it could be economical to create a change output. */
252    CFeeRate m_long_term_feerate{0};
253    /** Indicate that we are subtracting the fee from outputs.
254     * When true, the value that is used for coin selection is the UTXO's real value rather than effective value */
255    bool m_subtract_fee_outputs{false};
256    /** Total weight of the UTXOs in this group. */
257    int m_weight{0};
258
259    OutputGroup() = default;
260    OutputGroup(const CoinSelectionParams& params) :
261        m_long_term_feerate(params.m_long_term_feerate),
262        m_subtract_fee_outputs(params.m_subtract_fee_outputs)
263    {}
264
265    void Insert(const std::shared_ptr<COutput>& output, size_t ancestors, size_t cluster_count);
266    bool EligibleForSpending(const CoinEligibilityFilter& eligibility_filter) const;
267    CAmount GetSelectionAmount() const;
268};
269
270struct Groups {
271    // Stores 'OutputGroup' containing only positive UTXOs (value > 0).
272    std::vector<OutputGroup> positive_group;
273    // Stores 'OutputGroup' which may contain both positive and negative UTXOs.
274    std::vector<OutputGroup> mixed_group;
275};
276
277/** Stores several 'Groups' whose were mapped by output type. */
278struct OutputGroupTypeMap
279{
280    // Maps output type to output groups.
281    std::map<OutputType, Groups> groups_by_type;
282    // All inserted groups, no type distinction.
283    Groups all_groups;
284
285    // Based on the insert flag; appends group to the 'mixed_group' and, if value > 0, to the 'positive_group'.
286    // This affects both; the groups filtered by type and the overall groups container.
287    void Push(const OutputGroup& group, OutputType type, bool insert_positive, bool insert_mixed);
288    // Different output types count
289    size_t TypesCount() { return groups_by_type.size(); }
290};
291
292typedef std::map<CoinEligibilityFilter, OutputGroupTypeMap> FilteredOutputGroups;
293
294/** Choose a random change target for each transaction to make it harder to fingerprint the Core
295 * wallet based on the change output values of transactions it creates.
296 * Change target covers at least change fees and adds a random value on top of it.
297 * The random value is between 50ksat and min(2 * payment_value, 1milsat)
298 * When payment_value <= 25ksat, the value is just 50ksat.
299 *
300 * Making change amounts similar to the payment value may help disguise which output(s) are payments
301 * are which ones are change. Using double the payment value may increase the number of inputs
302 * needed (and thus be more expensive in fees), but breaks analysis techniques which assume the
303 * coins selected are just sufficient to cover the payment amount ("unnecessary input" heuristic).
304 *
305 * @param[in]   payment_value   Average payment value of the transaction output(s).
306 * @param[in]   change_fee      Fee for creating a change output.
307 */
308[[nodiscard]] CAmount GenerateChangeTarget(CAmount payment_value, CAmount change_fee, FastRandomContext& rng);
309
310enum class SelectionAlgorithm : uint8_t
311{
312    BNB = 0,
313    KNAPSACK = 1,
314    SRD = 2,
315    CG = 3,
316    MANUAL = 4,
317};
318
319std::string GetAlgorithmName(SelectionAlgorithm algo);
320
321struct OutputPtrComparator {
322    bool operator()(const std::shared_ptr<COutput>& a, const std::shared_ptr<COutput>& b) const {
323        return *a < *b;
324    }
325};
326using OutputSet = std::set<std::shared_ptr<COutput>, OutputPtrComparator>;
327
328struct SelectionResult
329{
330private:
331    /** Set of inputs selected by the algorithm to use in the transaction */
332    OutputSet m_selected_inputs;
333    /** The target the algorithm selected for. Equal to the recipient amount plus non-input fees */
334    CAmount m_target;
335    /** The algorithm used to produce this result */
336    SelectionAlgorithm m_algo;
337    /** Whether the input values for calculations should be the effective value (true) or normal value (false) */
338    bool m_use_effective{false};
339    /** The computed waste */
340    std::optional<CAmount> m_waste;
341    /** False if algorithm was cut short by hitting limit of attempts and solution is non-optimal */
342    bool m_algo_completed{true};
343    /** The count of selections that were evaluated by this coin selection attempt */
344    size_t m_selections_evaluated;
345    /** Total weight of the selected inputs */
346    int m_weight{0};
347    /** How much individual inputs overestimated the bump fees for the shared ancestry */
348    CAmount bump_fee_group_discount{0};
349
350    template<typename T>
351    void InsertInputs(const T& inputs)
352    {
353        // Store sum of combined input sets to check that the results have no shared UTXOs
354        const size_t expected_count = m_selected_inputs.size() + inputs.size();
355        util::insert(m_selected_inputs, inputs);
356        if (m_selected_inputs.size() != expected_count) {
357            throw std::runtime_error(STR_INTERNAL_BUG("Shared UTXOs among selection results"));
358        }
359    }
360
361public:
362    explicit SelectionResult(const CAmount target, SelectionAlgorithm algo)
363        : m_target(target), m_algo(algo) {}
364
365    SelectionResult() = delete;
366
367    /** Get the sum of the input values */
368    [[nodiscard]] CAmount GetSelectedValue() const;
369
370    [[nodiscard]] CAmount GetSelectedEffectiveValue() const;
371
372    [[nodiscard]] CAmount GetTotalBumpFees() const;
373
374    void Clear();
375
376    void AddInput(const OutputGroup& group);
377    void AddInputs(const OutputSet& inputs, bool subtract_fee_outputs);
378
379    /** How much individual inputs overestimated the bump fees for shared ancestries */
380    void SetBumpFeeDiscount(CAmount discount);
381
382    /** Calculates and stores the waste for this result given the cost of change
383     * and the opportunity cost of spending these inputs now vs in the future.
384     * If change exists, waste = change_cost + inputs * (effective_feerate - long_term_feerate) - bump_fee_group_discount
385     * If no change, waste = excess + inputs * (effective_feerate - long_term_feerate) - bump_fee_group_discount
386     * where excess = selected_effective_value - target
387     * change_cost = effective_feerate * change_output_size + long_term_feerate * change_spend_size
388     *
389     * @param[in] min_viable_change The minimum amount necessary to make a change output economic
390     * @param[in] change_cost       The cost of creating a change output and spending it in the future. Only
391     *                              used if there is change, in which case it must be non-negative.
392     * @param[in] change_fee        The fee for creating a change output
393     */
394    void RecalculateWaste(CAmount min_viable_change, CAmount change_cost, CAmount change_fee);
395    [[nodiscard]] CAmount GetWaste() const;
396
397    /** Tracks that algorithm was able to exhaustively search the entire combination space before hitting limit of tries */
398    void SetAlgoCompleted(bool algo_completed);
399
400    /** Get m_algo_completed */
401    bool GetAlgoCompleted() const;
402
403    /** Record the number of selections that were evaluated */
404    void SetSelectionsEvaluated(size_t attempts);
405
406    /** Get selections_evaluated */
407    size_t GetSelectionsEvaluated() const ;
408
409    /**
410     * Combines the @param[in] other selection result into 'this' selection result.
411     *
412     * Important note:
413     * There must be no shared 'COutput' among the two selection results being combined.
414     */
415    void Merge(const SelectionResult& other);
416
417    /** Get m_selected_inputs */
418    const OutputSet& GetInputSet() const;
419    /** Get the vector of COutputs that will be used to fill in a CTransaction's vin */
420    std::vector<std::shared_ptr<COutput>> GetShuffledInputVector() const;
421
422    bool operator<(SelectionResult other) const;
423
424    /** Get the amount for the change output after paying needed fees.
425     *
426     * The change amount is not 100% precise due to discrepancies in fee calculation.
427     * The final change amount (if any) should be corrected after calculating the final tx fees.
428     * When there is a discrepancy, most of the time the final change would be slightly bigger than estimated.
429     *
430     * Following are the possible factors of discrepancy:
431     *  + non-input fees always include segwit flags
432     *  + input fee estimation always include segwit stack size
433     *  + input fees are rounded individually and not collectively, which leads to small rounding errors
434     *  - input counter size is always assumed to be 1vbyte
435     *
436     * @param[in]  min_viable_change  Minimum amount for change output, if change would be less then we forgo change
437     * @param[in]  change_fee         Fees to include change output in the tx
438     * @returns Amount for change output, 0 when there is no change.
439     *
440     */
441    CAmount GetChange(CAmount min_viable_change, CAmount change_fee) const;
442
443    CAmount GetTarget() const { return m_target; }
444
445    SelectionAlgorithm GetAlgo() const { return m_algo; }
446
447    int GetWeight() const { return m_weight; }
448};
449
450util::Result<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change,
451                                             int max_selection_weight);
452
453util::Result<SelectionResult> CoinGrinder(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, CAmount change_target, int max_selection_weight);
454
455/** Select coins by Single Random Draw (SRD). SRD selects eligible OutputGroups from a shuffled
456 * ordering until the effective value of the input set suffices to create the recipient outputs and a
457 * change output with an amount of at least CHANGE_LOWER. While the maximum selection
458 * weight is exceeded during selection, the OutputGroup with the lowest effective value is dropped
459 * from the selection before additional OutputGroups are selected. Due to this greedy approach,
460 * SRD can fail to discover possible solutions in pathological cases.
461 *
462 * @param[in]  utxo_pool    The positive effective value OutputGroups eligible for selection
463 * @param[in]  target_value The target value to select for
464 * @param[in]  change_fee The cost of adding the change output to the transaction at the transaction’s feerate.
465 * @param[in]  rng The randomness source to shuffle coins
466 * @param[in]  max_selection_weight The maximum allowed weight for a selection result to be valid
467 * @returns If successful, a valid SelectionResult, otherwise, util::Error
468 */
469util::Result<SelectionResult> SelectCoinsSRD(const std::vector<OutputGroup>& utxo_pool, CAmount target_value, CAmount change_fee, FastRandomContext& rng,
470                                             int max_selection_weight);
471
472// Original coin selection algorithm as a fallback
473util::Result<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, const CAmount& nTargetValue,
474                                             CAmount change_target, FastRandomContext& rng, int max_selection_weight);
475} // namespace wallet
476
477#endif // BITCOIN_WALLET_COINSELECTION_H
478