Don't create change when it isn't necessary. #898

pull dooglus wants to merge 2 commits into bitcoin:master from dooglus:lesschange changing 3 files +372 −85

dooglus commented at 7:36 PM on February 25, 2012: contributor

If we have three 50BTC outputs and try to spend 100BTC, we should use only two of the outputs. Previously we were using all three. Similarly if we have outputs of 50, 50, and 0.01 and want to spend 100BTC, we shouldn't include the 0.01 in the transaction.

http://blockexplorer.com/tx/29a3efd3ef04f9153d47a990bd7b048a4b2d213daaa5fb8ed670fb85f13bdbcf shows a transaction where MtGox (edit, Feb 2014: I've no idea what caused me to think this was MtGox) was trying to consolidate ten 50k outputs into a single 500k output. The wallet had at least 11 50k outputs in it. Because of this code in wallet.cpp: if (nTotalLower >= nTargetValue + CENT) nTargetValue += CENT; the target value was increased from 500k to 500k plus a cent, which couldn't be found using just ten 50k outputs, and so an eleventh 50k output became involved, to avoid sub-cent change. There was no need for any change at all. (I notice the 50k change hasn't yet been redeemed. I hope it isn't lost!)

These transactions show other common cases where extra 0.01 coins are tacked on to both sides of transactions for no good reason:

http://blockexplorer.com/tx/a9d50d41be42beb278f5830d75aee06216b0a9c93d5eb5a62b6d30bec8c272f3 http://blockexplorer.com/tx/a2f748139f90b5063aace9ab18cb0ceb011a440a5a51888e0ec6c7b71a12aed6

(Sorry for the repeat pull request. I still don't know how to work github properly...)
gavinandresen commented at 9:49 PM on February 25, 2012: contributor

Too big/dangerous a change for 0.6, I think.

It'd be really spiffy if there were unit tests for the SelectCoins code to test all the edge cases (I know they're not trivial to write, but maybe a little refactoring of SelectCoins would help).
dooglus commented at 8:56 PM on February 26, 2012: contributor

@gavinandresen I'd be happy to write some unit tests for SelectCoins but it seems to depend on the whole blockchain which isn't available to the unit tests. Is that what you are referring to with the refactoring of SelectCoins? I'm sure with a little help I could get this done.
gavinandresen commented at 9:40 PM on February 26, 2012: contributor

@dooglus : yes, off the top of my head something like splitting it into two methods, the first of which creates an array of pointers to available outputs (or maybe tuples of (output, nConfirmations, size) or something) and the second of which runs the actual "figure out which outputs to use" algorithm. Making SelectCoins strictly a function that chooses a subset of items passed in should make it much easier to both test and modify in the future.
dooglus commented at 12:55 AM on February 27, 2012: contributor

@gavinandresen Is it acceptable to use a vector of pair<nConfirmations,pair<nSize,pair<tx,output_number> > > or is that too ugly?
sipa commented at 1:13 AM on February 27, 2012: member

Tip: use COutPoint instead of pair(tx,output_number). But as soon as there is more than one argument you want to tie to it, I'd add a smallish class.
dooglus commented at 11:54 AM on February 27, 2012: contributor

@sipa COutPoint has a hash, rather than a transaction, whereas I already have the transactions.

I used a new smallish class anyway because it makes things tidier.

Refactor SelectCoinsMinConf() and add unit tests.

AvailableCoins() makes a vector of available outputs which is then passed to SelectCoinsMinConf().  This allows unit tests to test the coin selection algorithm without having the whole blockchain available.

ec0e83664f

luke-jr commented at 6:37 PM on February 27, 2012: member
I didn't see the test for this case:
- Available outputs: 0.0005, 0.01, 1
- Desired amount: 1.0001
- Correct solution: 0.01, 1
In this case, the 0.0005 coin should never be chosen, because that would have 0.0004 BTC left over incurring a fee.
dooglus commented at 7:22 PM on February 27, 2012: contributor

@luke-jr Your "correct solution" adds up to 1.01. Subtracting the desired amount leaves 0.0099. That's sub-cent change, which we're trying to avoid.

Wouldn't it be better to chose all 3 coins, leaving 0.0104 change and no fee?

I guess you made a typo somewhere, but I can't work out what you meant.

Don't create change when it isn't necessary.

If we have three 50BTC outputs and try to spend 100BTC, we should use only two of the outputs.  Previously we were using all three.  Similarly if we have outputs of 50, 50, and 0.01 and want to spend 100BTC, we shouldn't include the 0.01 in the transaction.

Move the stochastic approximation code into a new function and call it once or twice: first for <target> and then for <target+cent> if we weren't able to find a subset of coins that sum to exactly <target>.

Updated the unit tests to no longer conditionally compile out the tests which used to fail.

7244bba3fb

dooglus commented at 7:43 PM on February 27, 2012: contributor

Changing the desired amount to 0.999 gives a situation where we should leave the smallest coin. I've added corresponding test cases, thanks.
sipa commented at 6:49 PM on June 12, 2012: member

Is this pull request superceded or not? I think we want this change for sure, while there are still implementation issues with coin selections.
luke-jr commented at 6:53 PM on June 12, 2012: member

#1416 is the latest rebased iteration of this
sipa commented at 3:20 PM on June 14, 2012: member

Merged under #1416.
sipa closed this on Jun 14, 2012
dooglus commented at 6:26 PM on June 14, 2012: contributor

I don't see this (or coin control) in #1416.
dooglus commented at 6:58 PM on August 23, 2012: contributor
This fix still isn't merged, somehow. The master branch is still doing this:
```
if (nTotalLower >= nTargetValue + CENT)
    nTargetValue += CENT;
```
and consequently adds change when it isn't needed.
gmaxwell commented at 2:25 AM on August 24, 2012: contributor

@dooglus Can you explain why the test case passes? https://github.com/bitcoin/bitcoin/blob/master/src/test/wallet_tests.cpp#L210

Can you suggest a test case that fails?

I suspect you have an unclean clone that has been merged 'nTargetValue +=' doesn't appear anywhere in the codebase as far as I can tell.
luke-jr commented at 2:29 AM on August 24, 2012: member

I also can confirm that code does not exist in master...
jwillerth commented at 2:43 AM on August 24, 2012: none

Take me off this list

Regards,

Joseph Willerth

Sent from my iPhone

On Aug 23, 2012, at 9:25 PM, Gregory Maxwell notifications@github.com wrote:

@dooglus Can you explain why the test case passes? https://github.com/bitcoin/bitcoin/blob/master/src/test/wallet_tests.cpp#L210

Can you suggest a test case that fails?

— Reply to this email directly or view it on GitHub.
luke-jr commented at 2:54 AM on August 24, 2012: member
This isn't a list, it's an issue. To remove yourself from notifications (nobody else can do it for you), do this:
- Login to GitHub if necessary
- Open #898 in your browser
- Scroll all the way to the bottom
- Where it says "Watching thread", click it and select "Mute"
dooglus commented at 8:46 PM on August 24, 2012: contributor

You're right. I was looking at a cached copy of master. Apologies.
suprnurd referenced this in commit dd5bd97561 on Dec 5, 2017
ptschip referenced this in commit 43899c009e on Jan 11, 2018
ptschip referenced this in commit b853490d13 on Jan 19, 2018
lateminer referenced this in commit 3d496cc746 on Oct 30, 2019
DrahtBot locked this on Sep 8, 2021

Contributors

Milestone
0.7.0

Linked (view graph)

#905 Refactor SelectCoinsMinConf() and add unit tests.#1017 coin control / less change / refactor coin selection