8000 client/dcr: Improved UTXO selection algorithm by martonp · Pull Request #2169 · decred/dcrdex · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

client/dcr: Improved UTXO selection algorithm #2169

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 3 commits into from
Feb 28, 2023
Merged

client/dcr: Improved UTXO selection algorithm #2169

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
3 commits
Select commit Hold shift + click to select a range
4f73efc
client/dcr: Improved UTXO selection algorithm
martonp Feb 24, 2023
7a08ec4
Chappjc fixes
martonp Feb 25, 2023
2a72c2b
Use shuffle
martonp Feb 26, 2023
File filter

Filter by extension

Filter by extension
Conversations
F 8000 ailed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
134 changes: 72 additions & 62 deletions client/asset/dcr/coin_selection.go
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -4,7 +4,9 @@
package dcr

import (
"math/rand"
"sort"
"time"

"decred.org/dcrdex/dex/calc"
dexdcr "decred.org/dcrdex/dex/networks/dcr"
Expand Down Expand Up @@ -71,69 +73,81 @@ func sumUTXOs(set []*compositeUTXO) (tot uint64) {
return tot
}

// In the following utxo selection functions, the compositeUTXO slice MUST be
// sorted in ascending order (smallest first, largest last).

// subsetLargeBias begins by summing from the largest UTXO down until the sum is
// just below the requested amount. Then it picks the (one) final UTXO that
// reaches the amount with the least excess. Each utxo in the input must be
// smaller than amt - use via leastOverFund only!
func subsetLargeBias(amt uint64, utxos []*compositeUTXO) []*compositeUTXO {
// Add from largest down until sum is *just under*. Resulting sum will be
// less, and index will be the next (smaller) element that would hit amt.
var sum uint64
var i int
for i = len(utxos) - 1; i >= 0; i-- {
this := toAtoms(utxos[i].rpc.Amount) // must not be >= amt
if sum+this >= amt {
break
}
sum += this
}

if i == -1 { // full set used
// if sum >= amt { return utxos } // would have been i>=0 after break above
return nil
}
// if i == len(utxos)-1 { return utxos[i:] } // shouldn't happen if each in set are < amt

// Find the last one to meet amt, as small as possible.
rem, set := utxos[:i+1], utxos[i+1:]
idx := sort.Search(len(rem), func(i int) bool {
return sum+toAtoms(rem[i].rpc.Amount) >= amt
// 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

rnd := rand.New(rand.NewSource(time.Now().Unix()))

shuffledUTXOs := make([]*compositeUTXO, len(utxos))
copy(shuffledUTXOs, utxos)
rnd.Shuffle(len(shuffledUTXOs), func(i, j int) {
shuffledUTXOs[i], shuffledUTXOs[j] = shuffledUTXOs[j], shuffledUTXOs[i]
})

return append([]*compositeUTXO{rem[idx]}, set...)
}

// subsetSmallBias begins by summing from the smallest UTXO up until the sum is
// at least the requested amount. Then it drops the smallest ones it had
// selected if they are not required to reach the amount.
func subsetSmallBias(amt uint64, utxos []*compositeUTXO) []*compositeUTXO {
// Add from smallest up until sum is enough.
var sum uint64
var idx int
for i, utxo := range utxos {
sum += toAtoms(utxo.rpc.Amount)
if sum >= amt {
idx = i
break
included := make([]bool, len(utxos))
const iterations = 1000

searchLoop:
for nRep := 0; nRep < iterations; nRep++ {
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Only other thing from the cpp that might make sense is to break nreps (this outermost loop) if we happen to hit nTotal == amt.

var nTotal uint64
var numIncluded int

for nPass := 0; nPass < 2; nPass++ {
for i := 0; i < len(shuffledUTXOs); i++ {
var use bool
if nPass == 0 {
use = rnd.Int63()&1 == 1
} else {
use = !included[i]
}
if use {
included[i] = true
numIncluded++
nTotal += toAtoms(shuffledUTXOs[i].rpc.Amount)
if nTotal >= amt {
if nTotal < best || (nTotal == best && numIncluded < bestNumIncluded) {
best = nTotal
if bestIncluded == nil {
bestIncluded = make([]bool, len(shuffledUTXOs))
}
copy(bestIncluded, included)
bestNumIncluded = numIncluded
}
if nTotal == amt {
break searchLoop
}
included[i] = false
nTotal -= toAtoms(shuffledUTXOs[i].rpc.Amount)
numIncluded--
}
}
}
}
for i := 0; i < len(included); i++ {
included[i] = false
}
}
if sum < amt {

if bestIncluded == nil {
return nil
}
set := utxos[:idx+1]

// Now drop excess small ones.
for i, utxo := range set {
sum -= toAtoms(utxo.rpc.Amount)
if sum < amt {
idx = i // needed this one
break

set := make([]*compositeUTXO, 0, len(shuffledUTXOs))
for i, inc := range bestIncluded {
if inc {
set = append(set, shuffledUTXOs[i])
}
}
return set[idx:]

return set
}

// leastOverFund attempts to pick a subset of the provided UTXOs to reach the
Expand All @@ -147,8 +161,8 @@ func subsetSmallBias(amt uint64, utxos []*compositeUTXO) []*compositeUTXO {
// 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 subsetSmallBias and
// subsetLargeBias). If that subset has less combined value than the single
// 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.
//
Expand Down Expand Up @@ -176,11 +190,7 @@ func leastOverFund(amt uint64, utxos []*compositeUTXO) []*compositeUTXO {
// Find a subset of the small UTXO set with smallest combined amount.
var set []*compositeUTXO
if sumUTXOs(small) >= amt {
set = subsetLargeBias(amt, small)
setX := subsetSmallBias(amt, small)
if sumUTXOs(setX) < sumUTXOs(set) {
set = setX
}
set = subsetWithLeastSumGreaterThan(amt, small)
} else if single != nil {
return []*compositeUTXO{single}
}
Expand Down
166 changes: 46 additions & 120 deletions client/asset/dcr/coin_selection_test.go
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -3,115 +3,13 @@ package dcr
import (
"math/rand"
"reflect"
"sort"
"testing"
"time"

walletjson "decred.org/dcrwallet/v2/rpc/jsonrpc/types"
)

func Test_subsetLargeBias(t *testing.T) {
amt := uint64(10e8)
newU := func(amt float64) *compositeUTXO {
return &compositeUTXO{
rpc: &walletjson.ListUnspentResult{Amount: amt},
}
}
tests := []struct {
name string
utxos []*compositeUTXO
want []*compositeUTXO
}{
{
"1,3 exact",
[]*compositeUTXO{ne 8000 wU(1), newU(8), newU(9)},
[]*compositeUTXO{newU(1), newU(9)},
},
{
"subset large bias",
[]*compositeUTXO{newU(1), newU(3), newU(6), newU(7)},
[]*compositeUTXO{newU(3), newU(7)},
},
{
"subset large bias",
[]*compositeUTXO{newU(1), newU(3), newU(5), newU(7), newU(8)},
[]*compositeUTXO{newU(3), newU(8)},
},
{
"insufficient",
[]*compositeUTXO{newU(1), newU(8)},
nil,
},
{
"all exact",
[]*compositeUTXO{newU(1), newU(9)},
[]*compositeUTXO{newU(1), newU(9)},
},
}
for _, tt := range tests {
t.Run(tt.name, func(t *testing.T) {
if got := subsetLargeBias(amt, tt.utxos); !reflect.DeepEqual(got, tt.want) {
t.Errorf("subset() = %v, want %v", got, tt.want)
}
})
}
}

func Test_subsetSmallBias(t *testing.T) {
amt := uint64(10e8)
newU := func(amt float64) *compositeUTXO {
return &compositeUTXO{
rpc: &walletjson.ListUnspentResult{Amount: amt},
}
}
tests := []struct {
name string
utxos []*compositeUTXO
want []*compositeUTXO
}{
{
"1,3",
[]*compositeUTXO{newU(1), newU(8), newU(9)},
[]*compositeUTXO{newU(8), newU(9)},
},
{
"subset",
[]*compositeUTXO{newU(1), newU(9), newU(11)},
[]*compositeUTXO{newU(1), newU(9)},
},
{
"subset small bias",
[]*compositeUTXO{newU(1), newU(3), newU(6), newU(7)},
[]*compositeUTXO{newU(1), newU(3), newU(6)},
},
{
"subset small bias",
[]*compositeUTXO{newU(1), newU(3), newU(5), newU(7), newU(8)},
[]*compositeUTXO{newU(5), newU(7)},
},
{
"ok nil",
[]*compositeUTXO{newU(1), newU(8)},
nil,
},
{
"two, over",
[]*compositeUTXO{newU(5), newU(7), newU(11)},
[]*compositeUTXO{newU(5), newU(7)},
},
{
"insufficient",
[]*compositeUTXO{newU(1), newU(8)},
nil,
},
}
for _, tt := range tests {
t.Run(tt.name, func(t *testing.T) {
if got := subsetSmallBias(amt, tt.utxos); !reflect.DeepEqual(got, tt.want) {
t.Errorf("subset() = %v, want %v", got, tt.want)
}
})
}
}

func Test_leastOverFund(t *testing.T) {
amt := uint64(10e8)
newU := func(amt float64) *compositeUTXO {
Copy link
Member

Choose a reason for hiding this c AE8F omment

The reason will be displayed to describe this comment to others. Learn more.

Thanks for this!

I guess the test cases for the dumber leastOverFund were too easy? We chatted a bit about replacing the algo and it sounded like the new one got better results ~1/2 the time. Would it require much larger sets to test a case where it's a better result?

Copy link
Collaborator Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The better results ~1/2 the time was with the dynamic programming solution which only worked with very small amounts of UTXOs. When I tested this one with large amounts of UTXOs and compared it with the old solution, it got better results every single time.

The two solutions (this vs small and large bias subset) are equivalent, but the old one tries 2 random possibilities and this one tries 1000.

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Tests well. ~16ms for a set of 4000 UTXOs between 0 and 2 DCR in search of a subset totaling 10DCR

func Test_subsetFund(t *testing.T) {
	amt := uint64(10e8)
	s := make([]*compositeUTXO, 4000)
	newU := func(amt float64) *compositeUTXO {
		return &compositeUTXO{
			rpc: &walletjson.ListUnspentResult{Amount: amt},
		}
	}
	for i := range s {
		v := rand.Float64() + float64(rand.Int63n(2))
		v = math.Round(v*1e8) / 1e8
		fmt.Println(v)
		s[i] = newU(v)
	}
	sort.Slice(s, func(i, j int) bool {
		return s[i].rpc.Amount < s[i].rpc.Amount
	})
	r := subsetWithLeastSumGreaterThan(amt, s)
	fmt.Println(len(r), sumUTXOs(r))
}

Expand Down Expand Up @@ -156,7 +54,7 @@ func Test_leastOverFund(t *testing.T) {
},
{
"subset small bias",
[]*compositeUTXO{newU(1), newU(3), newU(6), newU(7)},
[]*compositeUTXO{newU(3), newU(6), newU(7)},
[]*compositeUTXO{newU(3), newU(7)},
},
{
Expand All @@ -182,30 +80,32 @@ func Test_leastOverFund(t *testing.T) {
}
for _, tt := range tests {
t.Run(tt.name, func(t *testing.T) {
if got := leastOverFund(amt, tt.utxos); !reflect.DeepEqual(got, tt.want) {
got := leastOverFund(amt, tt.utxos)
sort.Slice(got, func(i int, j int) bool {
return got[i].rpc.Amount < got[j].rpc.Amount
})
if !reflect.DeepEqual(got, tt.want) {
t.Errorf("subset() = %v, want %v", got, tt.want)
}
})
}
}

func Fuzz_leastOverFund(f *testing.F) {
seeds := []struct {
type seed struct {
amt uint64
n int
}{{
amt: 200,
n: 2,
}, {
amt: 20,
n: 1,
}, {
amt: 20,
n: 20,
}, {
amt: 2,
n: 40,
}}
}

rnd := rand.New(rand.NewSource(1))

seeds := make([]seed, 0, 40)
for i := 0; i < 10; i++ {
seeds = append(seeds, seed{
amt: uint64(rnd.Intn(40)),
n: rnd.Intn(20000),
})
}

for _, seed := range seeds {
f.Add(seed.amt, seed.n)
Expand All @@ -217,6 +117,9 @@ func Fuzz_leastOverFund(f *testing.F) {
}
}

var totalDuration time.Duration
var totalUTXO int64

f.Fuzz(func(t *testing.T, amt uint64, n int) {
if n < 1 || n > 65535 || amt == 0 || amt > 21e6 {
t.Skip()
Expand All @@ -236,8 +139,31 @@ func Fuzz_leastOverFund(f *testing.F) {
}
utxos[i] = newU(v)
}
startTime := time.Now()
leastOverFund(amt*1e8, utxos)
totalDuration += time.Since(startTime)
totalUTXO += int64(n)
})

f.Logf("leastOverFund: average duration: %v, with average number of UTXOs: %v\n", totalDuration/100, totalUTXO/100)
}

func BenchmarkLeastOverFund(b *testing.B) {
// Same amounts every time.
rnd := rand.New(rand.NewSource(1))
utxos := make([]*compositeUTXO, 2_000)
for i := range utxos {
utxo := &compositeUTXO{
rpc: &walletjson.ListUnspentResult{
Amount: float64(1+rnd.Int31n(100)) / float64(1e8),
},
}
utxos[i] = utxo
}
b.ResetTimer()
for n := 0; n < b.N; n++ {
leastOverFund(10_000, utxos)
}
}

func Test_utxoSetDiff(t *testing.T) {
Expand Down
0