[WIP] Implement bitcoin coin selection algorithm

[chris124567]

Mostly implements the algorithm described at https://bitcoin.stackexchange.com/questions/1077/what-is-the-coin-selection-algorithm. Still need to add tests.

[lukechampine]

I noticed someone complaining in the StackOverflow thread that this algorithm optimizes for minimal change, rather than minimal fees. Looking at the bitcoin master branch, it seems like they have switched to a new algorithm based on this master's thesis paper: https://murch.one/wp-content/uploads/2016/11/erhardt2016coinselection.pdf

Here's the code: https://github.com/bitcoin/bitcoin/blob/f37bd15d472fdc7dd3d40cafaba9e8dfddd6b530/src/wallet/coinselection.cpp

Implementing this for Sia might be overkill, but in any case I recommend checking out the paper. It seems pretty readable and provides a good overview of various approaches.

[lukechampine]

Actually, that paper concludes with this recommendation:

Single Random Draw (Cent) is a bit cheaper and should exhibit better privacy than FIFO, so it is recommended as a simple coin selection policy for newly created wallets.

The "Single Random Draw (Cent)" algorithm is described in section 5.2, and is pretty much what you'd expect: just draw randomly from your UTXOs until the sum exceeds target. The "Cent" part comes from the fact that your target is actually target + estimated fee + 0.01; this means that the transaction will always produce a change output worth at least 0.01 BTC.

I think we can do a bit better than hard-coding 0.01 (or whatever the equivalent would be for SC). The paper also mentions using target instead of 0.01, thus (ideally) producing a change output equal to the one you just spent; you can also keep track of the wallet's average target value, and use that. In other words, if the user is making lots of transactions that spend 5 BTC, the coin selection algorithm will try to create change outputs worth 5 BTC. We probably want to do something like this to facilitate contract formation.

Regardless, it seems like the original approach of drawing randomly actually performs pretty well -- in fact, better than the fancy 1000-round bitcoin algorithm in some cases. 😅

[lukechampine]

Honestly, maybe we should write some simulation code, like the author of that paper did. Then we can gather real data on what works and what doesn't.

[chris124567]

Honestly, maybe we should write some simulation code, like the author of that paper did. Then we can gather real data on what works and what doesn't.

On it. I guess we would want to compare 1) the "naive" original algorithm 2) the bitcoin algorithm 3) single random draw.

[chris124567]

Which do we want?

    hotwallet_test.go:454: Testing with coin selection:  Random
    hotwallet_test.go:588: All wallets averaged: {"UtxoRemaining":4.55,"UtxoMean":2.3793333333333333,"UtxoReceived":4.55,"UtxoSpent":2.87,"Change":1.99,"ChangeMinimum":"323125296467909866278473","ChangeMean":"31312529646790986627847334","ChangeMaximum":"3231252964679098662784","Fees":"0","UtxoInputMinimum":0,"UtxoInputMean":1.2861666666666665,"UtxoInputMaximum":1.53,"Transactions":0}
    hotwallet_test.go:454: Testing with coin selection:  Bitcoin
    hotwallet_test.go:588: All wallets averaged: {"UtxoRemaining":4.62,"UtxoMean":2.401333333333333,"UtxoReceived":4.62,"UtxoSpent":2.55,"Change":1.99,"ChangeMinimum":"224824194460453934660284","ChangeMean":"21482419446045393466028421","ChangeMaximum":"2248241944604539346602","Fees":"0","UtxoInputMinimum":0,"UtxoInputMean":1.1641666666666668,"UtxoInputMaximum":1.28,"Transactions":0}
    hotwallet_test.go:454: Testing with coin selection:  SingleRandomDraw
    hotwallet_test.go:588: All wallets averaged: {"UtxoRemaining":4.28,"UtxoMean":2.2811666666666666,"UtxoReceived":4.28,"UtxoSpent":3.4,"Change":2.01,"ChangeMinimum":"446124331625566893424036","ChangeMean":"43612433162556689342403665","ChangeMaximum":"4461243316255668934240","Fees":"0","UtxoInputMinimum":0,"UtxoInputMean":1.5826666666666669,"UtxoInputMaximum":2.09,"Transactions":0}

[chris124567]

OK, I'm currently leaning towards just keeping the random coin selection algorithm and removing the others. The bitcoin algorithm is marginally better but substantially more complicated. Interested to hear what anyone else thinks.

    hotwallet_test.go:592: Random: {"UtxoRemaining":4.42,"UtxoMean":2.4238333333333335,"UtxoReceived":4.42,"UtxoSpent":2.68,"Change":1.91,"ChangeMinimum":"281934596350886033425716","ChangeMean":"27193459635088603342571630","ChangeMaximum":"2819345963508860334257","Fees":"266510000000000000000000","UtxoInputMinimum":0,"UtxoInputMean":1.2689999999999997,"UtxoInputMaximum":1.47,"Transactions":0}
    hotwallet_test.go:592: Bitcoin: {"UtxoRemaining":4.6,"UtxoMean":2.4816666666666665,"UtxoReceived":4.6,"UtxoSpent":2.31,"Change":1.91,"ChangeMinimum":"239753742331191735953641","ChangeMean":"22975374233119173595364108","ChangeMaximum":"2397537423311917359536","Fees":"266510000000000000000000","UtxoInputMinimum":0,"UtxoInputMean":1.1108333333333333,"UtxoInputMaximum":1.16,"Transactions":0}
    hotwallet_test.go:592: SingleRandomDraw: {"UtxoRemaining":4.14,"UtxoMean":2.3215,"UtxoReceived":4.14,"UtxoSpent":3.33,"Change":1.92,"ChangeMinimum":"441857454053887869080613","ChangeMean":"43185745405388786908061326","ChangeMaximum":"4418574540538878690806","Fees":"266510000000000000000000","UtxoInputMinimum":0,"UtxoInputMean":1.6263333333333332,"UtxoInputMaximum":2.14,"Transactions":0}