forked from decred/dcrdex
-
Notifications
You must be signed in to change notification settings - Fork 0
/
coin_selection.go
200 lines (182 loc) · 6.8 KB
/
coin_selection.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
// This code is available on the terms of the project LICENSE.md file,
// also available online at https://blueoakcouncil.org/license/1.0.0.
package dcr
import (
"math/rand"
"sort"
"decred.org/dcrdex/dex/calc"
dexdcr "decred.org/dcrdex/dex/networks/dcr"
)
// sendEnough generates a function that can be used as the enough argument to
// the fund method when creating transactions to send funds. If fees are to be
// subtracted from the inputs, set subtract so that the required amount excludes
// the transaction fee. If change from the transaction should be considered
// immediately available (not mixing), set reportChange to indicate this and the
// returned enough func will return a non-zero excess value. Otherwise, the
// enough func will always return 0, leaving only unselected UTXOs to cover any
// required reserves.
func sendEnough(amt, feeRate uint64, subtract bool, baseTxSize uint32, reportChange bool) func(sum uint64, inputSize uint32, unspent *compositeUTXO) (bool, uint64) {
return func(sum uint64, inputSize uint32, unspent *compositeUTXO) (bool, uint64) {
total := sum + toAtoms(unspent.rpc.Amount)
txFee := uint64(baseTxSize+inputSize+unspent.input.Size()) * feeRate
req := amt
if !subtract { // add the fee to required
req += txFee
}
if total < req {
return false, 0
}
excess := total - req
if subtract && excess > txFee {
excess -= txFee // total - (req + txFee), without underflow
}
if !reportChange || dexdcr.IsDustVal(dexdcr.P2PKHOutputSize, excess, feeRate) {
excess = 0
}
return true, excess
}
}
// orderEnough generates a function that can be used as the enough argument to
// the fund method. If change from a split transaction will be created AND
// immediately available (not mixing), set reportChange to indicate this and the
// returned enough func will return a non-zero excess value reflecting this
// potential spit tx change. Otherwise, the enough func will always return 0,
// leaving only unselected UTXOs to cover any required reserves.
func orderEnough(val, lots, feeRate uint64, reportChange bool) func(sum uint64, size uint32, unspent *compositeUTXO) (bool, uint64) {
return func(sum uint64, size uint32, unspent *compositeUTXO) (bool, uint64) {
reqFunds := calc.RequiredOrderFundsAlt(val, uint64(size+unspent.input.Size()), lots,
dexdcr.InitTxSizeBase, dexdcr.InitTxSize, feeRate)
total := sum + toAtoms(unspent.rpc.Amount) // all selected utxos
if total >= reqFunds { // that'll do it
// change = total - (val + swapTxnsFee)
excess := total - reqFunds // reqFunds = val + swapTxnsFee
if !reportChange || dexdcr.IsDustVal(dexdcr.P2PKHOutputSize, excess, feeRate) {
excess = 0
}
return true, excess
}
return false, 0
}
}
func sumUTXOs(set []*compositeUTXO) (tot uint64) {
for _, utxo := range set {
tot += toAtoms(utxo.rpc.Amount)
}
return tot
}
// subsetWithLeastSumGreaterThan attempts to select the subset of UTXOs with
// the smallest total value greater than amt. It does this by making
// 1000 random selections and returning the best one. Each selection
// involves two passes over the UTXOs. The first pass randomly selects
// each UTXO with 50% probability. Then, the second pass selects any
// unused UTXOs until the total value is greater than or equal to amt.
func subsetWithLeastSumGreaterThan(amt uint64, utxos []*compositeUTXO) []*compositeUTXO {
best := uint64(1 << 62)
var bestIncluded *[]bool
bestNumIncluded := 0
iterations := 1000
for nRep := 0; nRep < iterations; nRep++ {
included := make([]bool, len(utxos))
var found bool
var nTotal uint64
var numIncluded int
for nPass := 0; nPass < 2 && !found; nPass++ {
for i := 0; i < len(utxos); i++ {
var use bool
if nPass == 0 {
use = rand.Uint32()&1 == 1
} else {
use = !included[i]
}
if use {
included[i] = true
numIncluded++
nTotal += toAtoms(utxos[i].rpc.Amount)
if nTotal >= amt {
if nTotal < best || (nTotal == best && numIncluded < bestNumIncluded) {
best = nTotal
bestIncluded = &included
bestNumIncluded = numIncluded
found = true
}
break
}
}
}
}
}
if bestIncluded == nil {
return nil
}
set := make([]*compositeUTXO, 0, len(utxos))
for i, inc := range *bestIncluded {
if inc {
set = append(set, utxos[i])
}
}
return set
}
// leastOverFund attempts to pick a subset of the provided UTXOs to reach the
// required amount with the objective of minimizing the total amount of the
// selected UTXOs. This is different from the objective used when funding
// orders, which is to minimize the number of UTXOs (to minimize fees).
//
// The UTXOs MUST be sorted in ascending order (smallest first, largest last)!
//
// This begins by partitioning the slice before the smallest single UTXO that is
// large enough to fully fund the requested amount, if it exists. If the smaller
// set is insufficient, the single largest UTXO is returned. If instead the set
// of smaller UTXOs has enough total value, it will search for a subset that
// reaches the amount with least over-funding (see subsetWithLeastSumGreaterThan).
// If that subset has less combined value than the single
// sufficiently-large UTXO (if it exists), the subset will be returned,
// otherwise the single UTXO will be returned.
//
// If the provided UTXO set has less combined value than the requested amount a
// nil slice is returned.
func leastOverFund(amt uint64, utxos []*compositeUTXO) []*compositeUTXO {
if amt == 0 || sumUTXOs(utxos) < amt {
return nil
}
// Partition - smallest UTXO that is large enough to fully fund, and the set
// of smaller ones.
idx := sort.Search(len(utxos), func(i int) bool {
return toAtoms(utxos[i].rpc.Amount) >= amt
})
var small []*compositeUTXO
var single *compositeUTXO // only return this if smaller ones would use more
if idx == len(utxos) { // no one is enough
small = utxos
} else {
small = utxos[:idx]
single = utxos[idx]
}
// Find a subset of the small UTXO set with smallest combined amount.
var set []*compositeUTXO
if sumUTXOs(small) >= amt {
set = subsetWithLeastSumGreaterThan(amt, small)
} else if single != nil {
return []*compositeUTXO{single}
}
// Return the small UTXO subset if it is less than the single big UTXO.
if single != nil && toAtoms(single.rpc.Amount) < sumUTXOs(set) {
return []*compositeUTXO{single}
}
return set
}
// utxoSetDiff performs the setdiff(set,sub) of two UTXO sets. That is, any
// UTXOs that are both sets are removed from the first. The comparison is done
// *by pointer*, with no regard to the values of the compositeUTXO elements.
func utxoSetDiff(set, sub []*compositeUTXO) []*compositeUTXO {
var availUTXOs []*compositeUTXO
avail:
for _, utxo := range set {
for _, kept := range sub {
if utxo == kept { // by pointer
continue avail
}
}
availUTXOs = append(availUTXOs, utxo)
}
return availUTXOs
}