CreateTransaction can include much too high a fee

gavinandresen commented at 5:29 pm on April 22, 2014: contributor

I ran into this writing a regression test for the smart ’estimate fees’ code.

CreateTransaction does not deal well with wallets that have lots of small-value inputs and just a couple of high-value inputs.

In pseudo-code, with default settings CreateTransaction does this:

0loop:
1  Select enough inputs to pay (amount+0 fees).
2  Maybe add a change output.
3  Create and sign transaction.
4  IF transaction is small and high priority: DONE.
5  IF enough fees are paid: DONE
6  ELSE:
7     go back to top of loop, re-selecting inputs to pay (amount+fees needed)

The bug is that if you have a lot of small-value inputs, you get a ‘ratchet’ effect where (say) 10 inputs are selected, they don’t add up to enough to pay fees, so 11 inputs are selected, but adding another input makes the fees even higher so 12 inputs are needed. That continues until SelectCoins either runs out of inputs OR it randomly decides to select a large coin.

The bug bothering me is when it eventually selects a large coin it will create a very small transaction that pays a much-larger-than-necessary fee-per-kilobyte.

Here is debug.log output from the smartfee CreateTransaction code (instrumented with extra LogPrint statements):

 02014-04-22 16:59:56 Estimated fee rate: 0.09375 BTC/kB; size 374, need 3506250 satoshis
 12014-04-22 16:59:56 Estimated fee rate: 0.09375 BTC/kB; size 962, need 9018750 satoshis
 22014-04-22 16:59:56 Estimated fee rate: 0.09375 BTC/kB; size 1700, need 15937500 satoshis
 32014-04-22 16:59:56 Estimated fee rate: 0.09375 BTC/kB; size 2586, need 24243750 satoshis
 42014-04-22 16:59:56 Estimated fee rate: 0.09375 BTC/kB; size 3615, need 33890625 satoshis
 52014-04-22 16:59:56 Estimated fee rate: 0.09375 BTC/kB; size 4942, need 46331250 satoshis
 62014-04-22 16:59:56 Estimated fee rate: 0.09375 BTC/kB; size 6568, need 61575000 satoshis
 72014-04-22 16:59:56 CommitTransaction:
 8CTransaction(hash=10c367c2c1, ver=1, vin.size=1, vout.size=2, nLockTime=0)
 9    CTxIn(COutPoint(036acfae76, 1), scriptSig=304402207b0c1bdadc92c9b7)
10    CTxOut(nValue=2.48612500, scriptPubKey=OP_DUP OP_HASH160 c808df63821d)
11    CTxOut(nValue=0.01000000, scriptPubKey=OP_DUP OP_HASH160 05fe160591a6)

So CreateTransaction ends up creating a ~250-byte transaction that pays as much as a 6,500 byte transaction: about 25 times as much as necessary (and that had me pulling my hair out, trying to figure out why my regression test sanity-check code was randomly failing).

We don’t see this as much in our existing code, because the wallet code rounds up transaction sizes to the next 1,000-byte multiple. That is really just hiding the problem, though.

I’m still thinking about how to test and fix this.

gavinandresen commented at 6:03 pm on April 22, 2014: contributor

Brain dump on how to fix:

After transaction is created, if fee-per-kb is larger than fee needed, move value from fee to change (assuming there is a change output: maybe always compute fee needed assuming that there WILL BE a change output).

CreateTransaction can loop a bunch of times right now, and it signs inputs every time it loops (which is an expensive operation). Signing inputs once would be much more efficient; a CTransaction::maxSignedSize() method that operates on a transaction with empty scriptSigs would be useful for both coin control and CreateTransaction.

It would be nice if CreateTransaction either always succeeded or always failed given a set of unspent inputs to select from. That might not be true right now; I think you could have a wallet with a few moderate-size and (say) thousands of small inputs, where SelectCoinsMinConf/ApproximateBestSubset would sometimes select just the moderate-sized inputs to create an under-100K-and-pays-enough-fees transaction but would sometimes fail.

So maybe CreateTransaction should be changed to “three strikes and you’re out”:

Create a zero-fee transaction. If it is high enough priority: spiffy, done.
Do one-pass of what we do today (maybe with fix to move fees to change, if it pays too much in fees). If it succeeds: spiffy, done.
Last-ditch best effort: run a greedy-select on the UTXO, adding largest-value inputs one by one until either we get a transaction that has enough value-in to pay fees needed OR we run into the 100K transaction size limit OR we run out of inputs.

The annoying task will be creating regression tests with wallets crafted to trigger CreateTransaction edge cases.

gmaxwell commented at 1:18 am on April 23, 2014: contributor

I started to write all the stuff you wrote here about signing being in the loop, so obviously I agree. I also I agree with the second pass approach, elsewhere I’d written before:

“Any of the greedy processes can be improved by a fix-up pass on the final result. Take the result.. Is there a change output? If not, can we add one and take non-dust change while remaining in fee policy? If (or now that) there is one: Can some of the fee be moved to change? Are there any more tiny already-linked inputs that could be added with out adversely effecting the fee (or running us over the size limits)? Iterate.”

I’m not a super big fan of the greedy select largest inputs approach because I think it will tend to grind wallets down to unspendable dust even worse than the current coin selection behavior does. If you have one or more inputs that is larger than your typical spending amount you’ll keep using it over and over again grinding out change that this selection procedure won’t use. One thing we could do to improve this, I think is do the top down greedy solution and if we’re successful try eliminating the largest coin and continuing to add inputs. Stop if you hit the size limit, or if your largest input is on the order of half the size of what your paying, and take the last best (largest) solution.

WRT createtransaction always being successful or always failing. We could derandomize the heuristic solver by using all the input txids as the source of randomness for the search. or just by using a constant seed— I’d worry about the privacy leakage from the constant seed, but since we make basically no efforts here to improve privacy currently perhaps it shouldn’t be the biggest concern. The non-deterministic approach does have an advantage that it may be successful on a second try. Still greedy, but it should have the same success rate as the first approach and will tend to garbage collect the wallet.

Generally, for privacy, we ought to move the first level selection to be scriptPubKey based, so that if it spends one coin to a given pubkey it spends them all.

Another post-processing pass that would both improve privacy and wallet fragmentation would be if the change is greater than twice the value being spent minus epsilon and the change is also greater than (say) 10000x dust, create two change outputs instead of one, and at random split the change 50/50 or set one equal to the payment and put the remainder in the other. This will help break out of the case where the user gets a single large payment and is constantly spending their change.

laanwj added the label Wallet on May 3, 2014

laanwj added the label Priority Medium on May 3, 2014

laanwj added the label TX fees on May 9, 2014

MarcoFalke removed the label Priority Medium on Dec 30, 2016

MarcoFalke added the label Priority High on Jan 6, 2017

MarcoFalke added this to the milestone 0.14.0 on Jan 6, 2017

morcos commented at 3:27 pm on January 13, 2017: member

I think this is solved now by #9404 It can at least be removed from 0.14 milestone and probably be closed.

MarcoFalke removed this from the milestone 0.14.0 on Jan 14, 2017

laanwj closed this on Apr 25, 2017

DrahtBot locked this on Sep 8, 2021

CreateTransaction can include much too high a fee #4082