1
// Copyright © 2017-2020 Trust Wallet.
2
//
3
// This file is part of Trust. The full Trust copyright notice, including
4
// terms governing use, modification, and redistribution, is contained in the
5
// file LICENSE at the root of the source code distribution tree.
6

7
#include "UnspentSelector.h"
8

9
#include <algorithm>
10
#include <cassert>
11

12
using namespace TW;
13
using namespace TW::Bitcoin;
14

15
const int64_t UnspentSelector::dustThreshold = 3 * 182;
16

17
/// A selection of unspent transactions.
18
struct Selection {
19
    std::vector<Proto::UnspentTransaction> utxos;
20
    int64_t total;
21
};
22

23
// Filters utxos that are dust
24
template <typename T>
25
std::vector<Proto::UnspentTransaction>
26 1
UnspentSelector::filterDustInput(const T& selectedUtxos, int64_t byteFee) {
27 1
    auto inputFeeLimit = feeCalculator.calculateSingleInput(byteFee);
28 1
    std::vector<Proto::UnspentTransaction> filteredUtxos;
29 1
    for (auto utxo: selectedUtxos) {
30 1
        if (utxo.amount() > inputFeeLimit) {
31 1
            filteredUtxos.push_back(utxo);
32
        }
33
    }
34 1
    return filteredUtxos;
35
}
36

37
// Slice Array
38
// [0,1,2,3,4,5,6,7,8,9].eachSlices(3)
39
// >
40
// [[0, 1, 2], [1, 2, 3], [2, 3, 4], [3, 4, 5], [4, 5, 6], [5, 6, 7], [6, 7, 8],
41
// [7, 8, 9]]
42
template <typename T>
43 1
static inline auto slice(const T& elements, size_t sliceSize) {
44 1
    std::vector<std::vector<Proto::UnspentTransaction>> slices;
45 1
    for (auto i = 0; i <= elements.size() - sliceSize; i += 1) {
46 1
        slices.emplace_back();
47 1
        slices[i].reserve(sliceSize);
48 1
        for (auto j = i; j < i + sliceSize; j += 1) {
49 1
            slices[i].push_back(elements[j]);
50
        }
51
    }
52 1
    return slices;
53
}
54

55
template <typename T>
56
std::vector<Proto::UnspentTransaction>
57 1
UnspentSelector::select(const T& utxos, int64_t targetValue, int64_t byteFee, int64_t numOutputs) {
58
    // if target value is zero, no UTXOs are needed
59 1
    if (targetValue == 0) {
60 1
        return {};
61
    }
62

63
    // total values of utxos should be greater than targetValue
64 1
    if (utxos.empty() || sum(utxos) < targetValue) {
65 1
        return {};
66
    }
67 1
    assert(utxos.size() >= 1);
68

69
    // definitions for the following caluculation
70 1
    const auto doubleTargetValue = targetValue * 2;
71

72
    // Get all possible utxo selections up to a maximum size, sort by total
73
    // amount
74 1
    auto sortedUtxos = utxos;
75 1
    std::sort(sortedUtxos.begin(), sortedUtxos.end(),
76 1
              [](const Proto::UnspentTransaction& lhs, const Proto::UnspentTransaction& rhs) {
77 1
                  return lhs.amount() < rhs.amount();
78
              });
79

80
    // difference from 2x targetValue
81 1
    auto distFrom2x = [doubleTargetValue](int64_t val) -> int64_t {
82 1
        if (val > doubleTargetValue)
83 1
            return val - doubleTargetValue;
84
        else
85 1
            return doubleTargetValue - val;
86 1
    };
87

88
    // 1. Find a combination of the fewest inputs that is
89
    //    (1) bigger than what we need
90
    //    (2) closer to 2x the amount,
91
    //    (3) and does not produce dust change.
92 1
    for (int64_t numInputs = 1; numInputs <= sortedUtxos.size(); numInputs += 1) {
93 1
        const auto fee = feeCalculator.calculate(numInputs, numOutputs, byteFee);
94 1
        const auto targetWithFeeAndDust = targetValue + fee + dustThreshold;
95 1
        auto slices = slice(sortedUtxos, static_cast<size_t>(numInputs));
96 1
        slices.erase(std::remove_if(slices.begin(), slices.end(),
97 1
                                    [targetWithFeeAndDust](
98
                                        const std::vector<Proto::UnspentTransaction>& slice) {
99 1
                                        return sum(slice) < targetWithFeeAndDust;
100
                                    }),
101 1
                     slices.end());
102 1
        if (!slices.empty()) {
103 1
            std::sort(slices.begin(), slices.end(),
104 1
                      [distFrom2x](const std::vector<Proto::UnspentTransaction>& lhs,
105
                                   const std::vector<Proto::UnspentTransaction>& rhs) {
106 1
                          return distFrom2x(sum(lhs)) < distFrom2x(sum(rhs));
107
                      });
108 1
            return filterDustInput(slices.front(), byteFee);
109
        }
110
    }
111

112
    // 2. If not, find a valid combination of outputs even if they produce dust change.
113 1
    for (int64_t numInputs = 1; numInputs <= sortedUtxos.size(); numInputs += 1) {
114 1
        const auto fee = feeCalculator.calculate(numInputs, numOutputs, byteFee);
115 1
        const auto targetWithFee = targetValue + fee;
116 1
        auto slices = slice(sortedUtxos, static_cast<size_t>(numInputs));
117 1
        slices.erase(
118 1
            std::remove_if(slices.begin(), slices.end(),
119 1
                           [targetWithFee](const std::vector<Proto::UnspentTransaction>& slice) {
120 1
                               return sum(slice) < targetWithFee;
121
                           }),
122 1
            slices.end());
123 1
        if (!slices.empty()) {
124 1
            return filterDustInput(slices.front(), byteFee);
125
        }
126
    }
127

128 1
    return {};
129
}
130

131
template <typename T>
132
std::vector<Proto::UnspentTransaction>
133 1
UnspentSelector::selectMaxAmount(const T& utxos, int64_t byteFee) {
134 1
    return filterDustInput(utxos, byteFee);
135
}
136

137
template std::vector<Proto::UnspentTransaction> UnspentSelector::select(const ::google::protobuf::RepeatedPtrField<Proto::UnspentTransaction>& utxos, int64_t targetValue, int64_t byteFee, int64_t numOutputs);
138
template std::vector<Proto::UnspentTransaction> UnspentSelector::select(const std::vector<Proto::UnspentTransaction>& utxos, int64_t targetValue, int64_t byteFee, int64_t numOutputs);
139
template std::vector<Proto::UnspentTransaction> UnspentSelector::selectMaxAmount(const ::google::protobuf::RepeatedPtrField<Proto::UnspentTransaction>& utxos, int64_t byteFee);
140
template std::vector<Proto::UnspentTransaction> UnspentSelector::selectMaxAmount(const std::vector<Proto::UnspentTransaction>& utxos, int64_t byteFee);

Read our documentation on viewing source code .

Loading