There is concern that the current coin selection algorithm is too biased towards creating small inputs. We should try to look at some data after the change for 0.12 and see if that is actually the case and regardless work at improving the coin selection algorithm to avoid that concern before the 0.13 release.
See #7657 and #4906 for back story.
Tag with 0.13 milestone please
Agree with @morcos. Something we might want to work towards is a flexible/modular Coinselection. Coinselection somehow depends on the use cases and could be modular therefore.
We could allow different coin selection classes (some OO magic / interfacing) and allow to select them in fundrawtransaction or over a global state only adjustable on startup -coinselection=*class*.
Bitcoinj has a similar approach.
In my experience the biggest impediment to doing anything with coin selection is the current testing approach that simply fail if anything changes at all. So when you intend to change it you just get a pile of failures and nothing that tells you if the change is behaving sanely.
I don’t see any problem to having a selection, but I’m somewhat doubtful of the utility. Having a selection doesn’t replace having a good default– and right now we don’t even have a good default; and most of the time the user actually doesn’t really much useful information here (nothing the user would call a “use case” probably directly translates into the right strategy)– keep in mind that most users have no idea about the underlying “coins” behavior in the system.
Perhaps the primary strategy distinguisher would be the importance of privacy– e.g. should sweeping be kept to “do no privacy harm” levels, or more aggressive– but the user is often poorly equipt to weigh the privacy considerations (e.g. don’t what their future risks are, and may not know how powerful transaction analysis is), nor are they usually able to weigh the privacy impacts on their counterparties or the ecosystem as a whole.
Another thing to keep in mind is that implementation of GROUPCHECKSIGVERIFY would make strategies that try to spend many inputs at once much more attractive. (beyond the argument I’ve made before that you generally want to pay fees sooner rather than later, since fees tend to go up over time)
One untested idea that I haven’t seen suggested before (quite possibly because I’m overlooking something): try minimize the value of the change output. If it’s less than the dust-threshold, it can be safely omitted and donated to miners.
It should help keep the unspent set in check, while generating outputs that are actually useful for the next transaction(s). It also has the actively trying to avoid sourcing pointlessly large inputs (which are best saved for another transaction, especially if the user is sending multiple transactions before the next block confirms), and will also help create outputs which are useful for sending exact-change.
The biggest disadvantage I can see, is it’ll tend to make the change very distinguishable from the destination, but that’s a problem that already exists.
@RHavar technically thats what Bitcoin has always done. The subset sum tries to minimize the change (which generally minimizes the input set), and tiny amounts of change are just turned to fees. This has a bad behavior though of often resulting in small change (though above the threshold), which is not very useful for spending in the future; so big coins get spent and ground down to near-dust.
See ApproximateBestSubset in wallet.cpp.
which generally minimizes the input set
I doubt this is true. The algorithm will generally start by selecting some appropriately sized large coins (vValues is sorted) and then “fill up the gaps” with small coins such that it either hits the target value or overshoots the target value + MIN_CHANGE by the smallest amount possible. (see e.g. the issue @laanwj linked to)
One parameter you could add without introducing a huge amount of complexity would be an “ideal” amount of outputs in your wallet, lets call it N. Having a low N would mean you can easily/cheaply sweep your wallet (at the expense of linking your coins more heavily, and big transaction chains). Having a high N would give you the option of more coins to select from, hopefully resulting in an more ideal match.
N could be a configuration option, and when the amount of outputs is less than N it could actively try to increase it (spending from the largest coins first is a good way), and when the outputs is greater than N it could actively try to decrease it (sourcing extraneous inputs is a good way).
Would it perhaps make sense to increase the limit of what gets converted to fees? It would seem to me that this could reduce the number of tiny UTXO being created.
E.g. If the change is a magnitude smaller than the fee and a small portion of the total value of the transaction, add it to the fee:
0if(change < 0.1* fee && change < 0.001 * target):
1 fee = fee + change
That way, it would only apply to transactions where the change is only a tiny portion of the total value transacted, but still never donate more than transaction fee amounts. I.e. that way really large transactions wouldn’t suddenly donate significant money, and micro transactions wouldn’t lose a significant portion of the transacted value.
I haven’t tested whether it would have significant impact, and these numbers are just from the top of my head as well.
@gmaxwell Re “technically thats what Bitcoin has always done. The subset sum tries to minimize the change (which generally minimizes the input set), and tiny amounts of change are just turned to fees” I don’t think that’s true. From CWallet::SelectCoinsMinConf():
0ApproximateBestSubset(vValue, nTotalLower, nTargetValue, vfBest, nBest);
1if (nBest != nTargetValue && nTotalLower >= nTargetValue + MIN_CHANGE)
2 ApproximateBestSubset(vValue, nTotalLower, nTargetValue + MIN_CHANGE, vfBest, nBest);
The code is trying to make exactly the nTargetValue, and if it is unable to make that exact amount it instead tries to make nTargetValue + MIN_CHANGE instead.
So most transactions end up with a change amount of 0.010xxxxx and you end up with a wallet full of these individual bitcents which are expensive to spend. See this tx for an example of a high fee caused by this 0.01* pollution.
[Edit: this one is even crazier]
In the tx linked above, notice that the change output is 0.01000109 BTC, while two of the inputs are 0.01000112 BTC. So by donating just three satoshis to the miner we could have avoided the change output completely in this example. I suspect (based on how change outputs are very often less than a thousand satoshis over 0.01 BTC) that the majority of change outputs could be eliminated if the coin selection code was changed to donate up to 1000 satoshis to the miner if it allows change to be avoided.
@gmaxwell “and turn it into change” .. you mean turn it into fee, right? We’re talking about avoiding creating change in this instance.
How are we to determine the current feerate? Do we just use CWallet::GetMinimumFee() for some fixed nTxBytes size? Using a hardcoded ‘3600 base units’ seems like the wrong way to go about it.
Fee yes. :)
The size should depend on the kind of keys being used for change and reflect the marginal size increase from adding the input e.g. it would be ~ 32+4+1+73+34 bytes for a regular p2pkh change address. Effectively coin worth less than the fee for that size could currently costs more to spend than its worth– so we really shouldn’t be making outputs smaller than that, and preferably not smaller than 100 times that value, since presumably people would like to keep their fees as small percentage of the funds moved. :)
we really shouldn’t be making outputs smaller than that, and preferably not smaller than 100 times that value, since presumably people would like to keep their fees as small percentage of the funds moved. :)
I’m not sure this logic is sound. We’re looking for the threshold at which we decide to just include the ‘change’ in the miner fee instead of making a new output. That is effectively giving 100% of the change to the miner.
Suppose the cost (in fees) of spending an output is 0.0001 and the value of the output is 0.0010. We are choosing between:
A) create a change output; spending it will involve a 10% fee, but the user will still get a 0.0009 value from spending it B) don’t create a change output, just immediately give it all in extra fees.
While A) involves a 10% fee when the output is spent, B) involves an immediate 100% fee. Neither choice lets the user keep their fee as a small percentage. Best for the user would be if we simply never created a change output worth less than the expected cost of spending it.
I don’t see how bitcent change is “expensive to spend”.
Well, even if you only have 10 BTC, and that gets churned into 1000 outputs over time (as they currently do in 0.12 depending on your spend:receive habits), it’s pretty painful to spend from, regardless if your normal spend amount is 0.01 btc. For instance, even though I normally send tiny transactions, I’m in a position where trying to sweep 50% of my wallet results in “transaction too large” error. And when I lower that amount so I can actually make a transaction, it costs $8 (?) in transaction fees or something.
I really do think that if it was just tiny bit more aggressive in create change-less transactions, most of the problems would go away (and privacy improve).
I’ve finished my thesis on coin selection on Monday.
I’ve described an algorithm on pages 46-49 for coin selection which I call “Branch’n’Bound” in the document. (I only came up with it after Scaling Bitcoin, so it wasn’t included in my presentation there.)
It is a two step scheme.
Simulating with the dataset provided by RHavar in the other thread and compared to Bitcoin Core’s current strategy it:
This algorithm could be basis for a new coin selection algorithm of Bitcoin Core and I would like to invite questions and commentary. (If this thread is perhaps not the best medium for such a discussion, I’d be open to another format, e.g. the mailing list?)
@Xekyo Very interesting work! So that algorithm does coin selection better (at least on that dataset) and implementing it would unentangle the current coin selection code mess and is also less computationally intensive. Sounds great to me. Looking forward to it.
To avoid having a pull request wither forever I think we should get some people to commit to testing it. Also at least one large site that uses bitcoin core for wallet.
To avoid having a pull request wither forever I think we should get some people to commit to testing it. Also at least one large site that uses bitcoin core for wallet.
I’d be happy to test a PR on a production site after it’s reasonably stable. My site has made 2583 outgoing transactions in the last 7 days, (and received 4774 in the same time period) so it’s probably a reasonable stress test. (if someone could just ping or mention me on it, if there’s a PR so I don’t miss it)
I just saw the proposed changes in #9404, sorry I didn’t get my proposal done for 0.14. :(
The proposed fix is much better than the previous behavior (#4082), also especially for computational effort, because unnecessary repetitions are forestalled.
However, the issue is due to the order that a transaction is created: Since the fee is being estimated before the inputs are selected, when the number of selected inputs deviates from the initial estimate, the fee estimate is off. This problem stems from the effective target of the selection increasing with each collected input, because the effective target is increased by the cost of one input for every input we select.
Instead we should estimate the fee rate first, before the inputs are selected, and deduct the cost of spending an input from each input’s value upon selection.
effectiveValue = utxo.value - feePerByte × bytesPerInput
We’d measure the “effective contribution” of the input toward the fixed cost of target + transaction overhead + output costs. That way, we always get the fee right.