Refactor SelectCoinsMinConf() and add unit tests. #905

1. 
   dooglus commented at 11:49 AM on February 27, 2012: contributor

   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.

   This change was suggested in the comments of pull #898.

2. 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
3. 
   sipa commented at 2:09 PM on February 28, 2012: member

   ACK; I really like having unit tests for the coin selection algorithm.

4. in src/wallet.cpp:None in ec0e83664f outdated

    887 |      {
    888 | -       vector<const CWalletTx*> vCoins;
    889 | -       vCoins.reserve(mapWallet.size());
    890 | -       for (map<uint256, CWalletTx>::const_iterator it = mapWallet.begin(); it != mapWallet.end(); ++it)
    891 | -           vCoins.push_back(&(*it).second);
    892 | -       random_shuffle(vCoins.begin(), vCoins.end(), GetRandInt);
   

   ---

   ---

   

   gavinandresen commented at 3:24 PM on April 6, 2012:

   The random_shuffle was deleted here, but I don't see any calls to randomize the coins selected. A random_shuffle of the result of AvailableCoins should probably be done so coin selection is unpredictable.

   A unit test to test randomness that calls SelectCoins two times to get (say) 5 out of 100 coins, all of the same value/age, and fails if exactly the same coins are selected would also be nifty.

5. 
   dooglus commented at 4:11 PM on April 7, 2012: contributor

   @gavinandresen I noticed that the shuffle was missing some time ago. It has been added back in in #1017 which is my current branch for these changes, and includes the coincontrol and lesschange changes too.

   I'll also add a new unit test for randomness too.

   Do you need this pull request with just the refactoring updated too? I merged these related changes all together to make them easier to keep up to date.

6. 
   dooglus commented at 5:28 PM on April 7, 2012: contributor

   Notice that the coins are sorted into order before running the stochastic approximation:

   // Solve subset sum by stochastic approximation
   sort(vValue.rbegin(), vValue.rend());
   

   and so the shuffle's work will be undone in the case you propose. The only times the shuffle has any effect is if:

   1. there are multiple coins with the exact value requested (e.g. have 1,1,1 and request 1), or
   2. there is no coin with the exact value requested, and the sum of coins smaller than the sum requested is less than the sum requested, and there are a multiple coins of the same value all representing the smallest value that is larger than the sum requested (e.g. have 1,1,1,5,5,6 and request 4; sum of smaller coins = 3 < requested 4; smallest value larger than requested 4 is 5; there are multiple 5 coins). I'll add tests for both these cases to make sure the shuffle is happening.

   I added your suggested "4-from-100 identical" test to check that different random coins were being selected each time. It ran the test 100 times. And every time it failed on iterations 49 and 51. It turns out that this is because rand() is being used in the stochastic approximation code:

   if (nPass == 0 ? rand() % 2 : !vfIncluded[i])
   

   and rand() isn't being seeded, so returns the same sequence each time bitcoin is run. See new bug #1057.

   If I use GetRandInt(2) instead of rand()%2 then the tests fail occasionally, but randomly. It turns out that selecting 4 coins from a sorted list of 100 often picks the same 4. So I'll pick 50 from 100 instead to minimise the chance of a random identical selection.

7. Move the random_shuffle call back into SelectCoinsMinConf() so we can unit test it. 97fc916d2a
8. Test that the coin selection code is suitably random, and add tests re. sub-cent change. 88f537e90b
9. 
   dooglus commented at 6:48 PM on April 7, 2012: contributor

   I've merged my latest changes to the unit tests from lesschange-v0.6.0 (#1017) back onto this branch. There are also tests for sub-cent change suggested by Luke here: #898 (comment) which didn't get into this branch before.

10. Preserve the shuffled order of coins with equal value to give more randomized coin selection. 7895e3c2b3
11. 
    sipa commented at 6:49 PM on June 12, 2012: member

    Is this superceded or not?

12. 
    gavinandresen commented at 1:42 AM on June 14, 2012: contributor

    Closing; I pulled 1416 which was an updated version.

13. gavinandresen closed this on Jun 14, 2012

    ---

14. suprnurd referenced this in commit dd539c3d69 on Dec 5, 2017
15. ptschip referenced this in commit b0f7a10540 on Jan 25, 2018
16. DrahtBot locked this on Sep 8, 2021

Milestone
0.7.0