bitcoin 0.12's coinselection

RHavar commented at 5:05 am on March 9, 2016: contributor

After switching to bitcoin 0.12, I’m seeing a rather concerning amount of unspent transactions:

0$ bitcoin-cli listunspent | grep amount | wc -l
1734

Which make it very painful (and expensive!) to sweep the wallet. Previously it used to hover around 10-20 unspent or so.

Full dump of bitcoin-cli listunspent | grep amount on bitcoin 0.12

If it helps, during the time period I have received about 2.6x as many transactions as I have sent. The average receive amount was 0.11 BTC, and average send 0.26 BTC.

From the looks of it, it’s as if it’s trying to perpetually create change of 0.01 BTC, and never really inclined to spend from it.

gmaxwell commented at 7:51 am on March 9, 2016: contributor

What are you switching from?

Nothing in coinselection should have changed. There are unit tests which should detect it if it did.

MarcoFalke commented at 9:27 am on March 9, 2016: member

There was a really minor change to the coin selection #4906 but this should only trigger in really rare edge cases. A quick look at the sorted list of amounts does not imply #4906 had any impact on this.

MarcoFalke commented at 9:34 am on March 9, 2016: member

If it helps, during the time period I have received about 2.6x as many transactions as I have sent. The average receive amount was 0.11 BTC, and average send 0.26 BTC.

Wouldn’t it make sense if you receive a lot of “small” inputs and only send a few “large” outputs, that the number of outputs in your wallet increases? (Coin selection does not select a set of coins such that the utxo is reduced but rather a set of coins that “fits best” to the output value)

jonasschnelli added the label Wallet on Mar 9, 2016

RHavar commented at 4:27 pm on March 9, 2016: contributor

What are you switching from?

Switching from 11.2

There was a really minor change to the coin selection #4906 but this should only trigger in really rare edge cases.

Looking at #4906 it might actually be the reason for the observed difference. If before it was using lots of extraneous inputs, it would’ve kept the unspent set in check.

Right now, since last night the set has continued to grow:

$ bitcoin-cli listunspent | grep amount | wc -l 786

Which gives me the impression that it is almost trying to converge on 100*$amountOfBitcoins outputs, which is clearly extremely unideal.

Doing a quick skim of the code, it seems the situation could be improved a lot by making bitcoin aggressively attempt to make transactions without a change output, remembering that there are potentially three extra costs associated with creating a change output: a) The cost associated with the extra transaction size b) The cost associated with how in the future, that output will need to be spent c) Privacy (normally change addresses are super easy to determine, which then get spent-linked with the rest of your wallet)

And lets say you figure the extra associated cost of a change output to be ~80.00 bits, a side benefit of forgoing that change output to save 79.00 bits, would be that extra money is going to mining fees, and might help confirm faster.

I’m also not convinced that trying to make change outputs at least 0.01 BTC is particularly useful once you factor into the cost of creating change outputs For instance some extra dust outputs is actually essential in helping sourcing the exact amount of inputs required.

MarcoFalke commented at 4:45 pm on March 9, 2016: member

Doing a quick skim of the code, it seems the situation could be improved a lot by making bitcoin aggressively attempt to make transactions without a change output

This would require you to always have appropriately sized coins in your wallet or just “donate” the change via the fee and the try to minimize the additional fee/change.

a) The cost associated with the extra transaction size

True, but right now the wallet code is not “aware” of the transaction size and does not optimize in this direction. Related: #5782

c) Privacy (normally change addresses are super easy to determine, which then get spent-linked with the rest of your wallet)

I agree it is trivial to determine the change output on random transactions that are not yours. There was some discussion in #6569

I’m also not convinced that trying to make change outputs at least 0.01 BTC is particularly useful once you factor into the cost of creating change outputs For instance some extra dust outputs is actually essential in helping sourcing the exact amount of inputs required.

Please check #7615 which makes it 0.001 BTC

RHavar commented at 4:58 pm on March 9, 2016: contributor

This would require you to always have appropriately sized coins in your wallet or just “donate” the change via the fee and the try to minimize the additional fee/change.

Yeah. My thoughts were that the code should run coin selection twice. Once for a transaction with no change output (trying to minimize for the extraneous mining fee), and once for a transaction with a change output.

Then you can compare the mining fee of the two transactions (but applying a X penalty to the one with a change output) and pick the one with a smaller mining fee.

(I think X will be around ~50 bits, but you can more scientifically calculate it by figuring out the extra fee increase transaction by increase a transaction size of +1 output and +1 transaction input)

gmaxwell commented at 9:35 pm on March 9, 2016: contributor

@MarcoFalke ah, darn, I missed that that was merged. That change amplifying dust was a concern I raised with it.

Doing a quick skim of the code, it seems the situation could be improved a lot by making bitcoin aggressively attempt to make transactions without a change output,

It really does try to avoid a change output; it could be more aggressive– but I think few would be happy with it throwing out $4 in BTC in fees to avoid it. :)

More importantly, if it cannot avoid change it should probably use the opportunity to sweep up many (if not all) of the other coins that are already linked.

RHavar commented at 10:16 pm on March 9, 2016: contributor

$ bitcoin-cli listunspent | grep amount | wc -l 806

It’s still growing, despite the value of the wallet actually having decreased 10 BTC since yesterday. It’s quite a huge difference compared to 11.2, where it was always quite a small unspent set (like under 20). But perhaps it’s not such a big deal, because the transaction I did make probably had less fees (so it’s sort of just pushing the problem off), and I’m guessing as it keeps growing, the coin selection is going to become less and less efficient which will force it into cleaning up after itself to some degree.

It really does try to avoid a change output; it could be more aggressive– but I think few would be happy with it throwing out $4 in BTC in fees to avoid it. :)

$4, no. But if it was $0.02 (50 bits) more in fees to avoid an extra output, it would likely be worth it.

MarcoFalke commented at 10:52 pm on March 9, 2016: member

It is really hard for me to believe that #4906 has such a huge impact. @RHavar Could you try to create a list of transaction sizes using listtransactions "*" $hugeNumber 0|grep txid and then feeding those lines into getrawtransaction and finally into python -c 'print len(bytearray.fromhex("'$raw_tx'"))?

gmaxwell commented at 10:59 pm on March 9, 2016: contributor

@MarcoFalke Did you see the simulation results in #4906? under some usage patterns it resulted in double the number of UTXO.

$4, no. But if it was $0.02 (50 bits) more in fees to avoid an extra output, it would likely be worth it.

Already the strategy of bitcoin core is to try to construct a changeless output, if at all possible. The only way to directly reduce the amount of change created from the current state is to burn change as fees more often. Less directly, the wallet could try to create change amounts which are more likely to be useful without change in the future; though the potential for that is fairly modest in most cases.

If indeed #4906’s change is the cause of what you’re seeing and not something else, then it’s likely that issue isn’t that it’s creating more change, the issue is that it’s avoiding sweeping up outputs that it otherwise would sweep up.

RHavar commented at 11:02 pm on March 9, 2016: contributor

@MarcoFalke I can share it with you privately if you like, but I do not want to publish it openly. My email address is in my profile

MarcoFalke commented at 11:15 pm on March 9, 2016: member

@gmaxwell It’s not clear to me that the simulation results also cover the patch that was finally merged. Also, I have not reviewed the simulation code itself. (Note: It appears that the simulation code would create small non-standard dust outputs, which makes transferring the results to Bitcoin questionable)

RHavar commented at 0:09 am on March 10, 2016: contributor

Already the strategy of bitcoin core is to try to construct a changeless output, if at all possible.

I sent the full data to Marco, but in the last 30 days I’ve made 4485 sends of which only 11 don’t have a change ouput. Surely it can do better than that.

gmaxwell commented at 0:14 am on March 10, 2016: contributor

For there to be no change the inputs must match the output value pretty much exactly. This turns out to be pretty rare. @MarcoFalke I think you might underestimate the effect: Consider, adding just one extra input to a transaction counteracts the UTXO-count impact of the transaction creating change. It also means that the average value of utxo in your wallet would strictly increase. If extra inputs aren’t added, we would expect the average value of UTXO in your wallet to decrease over time. Low value UTXO are not as likely to be selected in the future, because the selection algorithm generally tries to minimize the number of inputs used.

MarcoFalke commented at 0:18 am on March 14, 2016: member

I couldn’t find anything meaningful in the data. It’s probably best to run 0.11 and 0.12 on a predefined set of transactions and compare the result.

RHavar commented at 0:52 am on March 14, 2016: contributor

I downgraded to 0.11 and it cleaned it up pretty fast, so it probably is a 0.12 regression (at least for my specific use-case). I’m guessing if I sent more often than I received the problem wouldn’t really exist.

That said, I’m not sure how bad the problem is. If it’s just #7664 it would means that I’m paying the fees later instead of right away, which isn’t so terrible. The real problem is that it’s generating so many outputs of 0.01 BTC, which is totally useless. Having a lot of dust outputs would in fact be more useful (e.g. for when i need to send dust, a common case :P)

Also, is it just my imagination or does 0.11 have better estimatefee logic too? I’ve never once on bitcoin 0.12 see bitcoin-cli estimatefee 1 return anything but -1, and it seems to give significantly more expensive estimates than before.

MarcoFalke commented at 1:10 am on March 14, 2016: member

does 0.11 have better estimatefee logic too?

I think #6134 (e92377f) changed the threshold to .95 as well as making estimatefee return -1 when estimates can not be given.

laanwj commented at 9:47 am on March 14, 2016: member

Closing in favor of #7664, to have this discussion in one place

laanwj closed this on Mar 14, 2016

laanwj referenced this in commit cc452d073c on Jul 1, 2016

laanwj referenced this in commit 20f3cd75f6 on Jul 1, 2016

lateminer referenced this in commit 77ea5eb519 on Jan 7, 2018

MarcoFalke locked this on Sep 8, 2021

bitcoin 0.12’s coinselection #7657