Inside Bitcoin

501
502        // if we add more small coins:
503        add_coin(available_coins, *wallet, CENT * 6 / 10);
504        add_coin(available_coins, *wallet, CENT * 7 / 10);
505
506        // and try again to make 1.0 * CENT
507        const auto result18 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), 1 * CENT, CENT);
508        BOOST_CHECK(result18);
509        BOOST_CHECK_EQUAL(result18->GetSelectedValue(), 1 * CENT); // we should get the exact amount
510
511        // run the 'mtgox' test (see https://blockexplorer.com/tx/29a3efd3ef04f9153d47a990bd7b048a4b2d213daaa5fb8ed670fb85f13bdbcf)
512        // they tried to consolidate 10 50k coins into one 500k coin, and ended up with 50k in change
513        available_coins = {};
514        for (int j = 0; j < 20; j++)
515            add_coin(available_coins, *wallet, 50000 * COIN);
516
517        const auto result19 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), 500000 * COIN, CENT);
518        BOOST_CHECK(result19);
519        BOOST_CHECK_EQUAL(result19->GetSelectedValue(), 500000 * COIN); // we should get the exact amount
520        BOOST_CHECK_EQUAL(result19->GetInputSet().size(), 10U); // in ten coins
521
522        // if there's not enough in the smaller coins to make at least 1 * CENT change (0.5+0.6+0.7 < 1.0+1.0),
523        // we need to try finding an exact subset anyway
524
525        // sometimes it will fail, and so we use the next biggest coin:
526        available_coins = {};
527        add_coin(available_coins, *wallet, CENT * 5 / 10);
528        add_coin(available_coins, *wallet, CENT * 6 / 10);
529        add_coin(available_coins, *wallet, CENT * 7 / 10);
530        add_coin(available_coins, *wallet, 1111 * CENT);
531        const auto result20 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), 1 * CENT, CENT);
532        BOOST_CHECK(result20);
533        BOOST_CHECK_EQUAL(result20->GetSelectedValue(), 1111 * CENT); // we get the bigger coin
534        BOOST_CHECK_EQUAL(result20->GetInputSet().size(), 1U);
535
536        // but sometimes it's possible, and we use an exact subset (0.4 + 0.6 = 1.0)
537        available_coins = {};
538        add_coin(available_coins, *wallet, CENT * 4 / 10);
539        add_coin(available_coins, *wallet, CENT * 6 / 10);
540        add_coin(available_coins, *wallet, CENT * 8 / 10);
541        add_coin(available_coins, *wallet, 1111 * CENT);
542        const auto result21 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), CENT, CENT);
543        BOOST_CHECK(result21);
544        BOOST_CHECK_EQUAL(result21->GetSelectedValue(), CENT);   // we should get the exact amount
545        BOOST_CHECK_EQUAL(result21->GetInputSet().size(), 2U); // in two coins 0.4+0.6
546
547        // test avoiding small change
548        available_coins = {};
549        add_coin(available_coins, *wallet, CENT * 5 / 100);
550        add_coin(available_coins, *wallet, CENT * 1);
551        add_coin(available_coins, *wallet, CENT * 100);
552
553        // trying to make 100.01 from these three coins
554        const auto result22 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), CENT * 10001 / 100, CENT);
555        BOOST_CHECK(result22);
556        BOOST_CHECK_EQUAL(result22->GetSelectedValue(), CENT * 10105 / 100); // we should get all coins
557        BOOST_CHECK_EQUAL(result22->GetInputSet().size(), 3U);
558
559        // but if we try to make 99.9, we should take the bigger of the two small coins to avoid small change
560        const auto result23 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), CENT * 9990 / 100, CENT);
561        BOOST_CHECK(result23);
562        BOOST_CHECK_EQUAL(result23->GetSelectedValue(), 101 * CENT);
563        BOOST_CHECK_EQUAL(result23->GetInputSet().size(), 2U);
564    }
565
566    // test with many inputs
567    for (CAmount amt=1500; amt < COIN; amt*=10) {
568        available_coins = {};
569        // Create 676 inputs (=  (old MAX_STANDARD_TX_SIZE == 100000)  / 148 bytes per input)
570        for (uint16_t j = 0; j < 676; j++)
571            add_coin(available_coins, *wallet, amt);
572
573        // We only create the wallet once to save time, but we still run the coin selection RUN_TESTS times.
574        for (int i = 0; i < RUN_TESTS; i++) {
575            const auto result24 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), 2000, CENT);
576            BOOST_CHECK(result24);
577
578            if (amt - 2000 < CENT) {
579                // needs more than one input:
580                uint16_t returnSize = std::ceil((2000.0 + CENT)/amt);
581                CAmount returnValue = amt * returnSize;
582                BOOST_CHECK_EQUAL(result24->GetSelectedValue(), returnValue);
583                BOOST_CHECK_EQUAL(result24->GetInputSet().size(), returnSize);
584            } else {
585                // one input is sufficient:
586                BOOST_CHECK_EQUAL(result24->GetSelectedValue(), amt);
587                BOOST_CHECK_EQUAL(result24->GetInputSet().size(), 1U);
588            }
589        }
590    }
591
592    // test randomness
593    {
594        available_coins = {};
595        for (int i2 = 0; i2 < 100; i2++)
596            add_coin(available_coins, *wallet, COIN);
597
598        // Again, we only create the wallet once to save time, but we still run the coin selection RUN_TESTS times.
599        for (int i = 0; i < RUN_TESTS; i++) {
600            // picking 50 from 100 coins doesn't depend on the shuffle,
601            // but does depend on randomness in the stochastic approximation code
602            const auto result25 = KnapsackSolver(GroupCoins(available_coins.All()), 50 * COIN, CENT);
603            BOOST_CHECK(result25);
604            const auto result26 = KnapsackSolver(GroupCoins(available_coins.All()), 50 * COIN, CENT);
605            BOOST_CHECK(result26);
606            BOOST_CHECK(!EqualResult(*result25, *result26));
607
608            int fails = 0;
609            for (int j = 0; j < RANDOM_REPEATS; j++)
610            {
611                // Test that the KnapsackSolver selects randomly from equivalent coins (same value and same input size).
612                // When choosing 1 from 100 identical coins, 1% of the time, this test will choose the same coin twice
613                // which will cause it to fail.
614                // To avoid that issue, run the test RANDOM_REPEATS times and only complain if all of them fail
615                const auto result27 = KnapsackSolver(GroupCoins(available_coins.All()), COIN, CENT);
616                BOOST_CHECK(result27);
617                const auto result28 = KnapsackSolver(GroupCoins(available_coins.All()), COIN, CENT);
618                BOOST_CHECK(result28);
619                if (EqualResult(*result27, *result28))
620                    fails++;
621            }
622            BOOST_CHECK_NE(fails, RANDOM_REPEATS);
623        }
624
625        // add 75 cents in small change.  not enough to make 90 cents,
626        // then try making 90 cents.  there are multiple competing "smallest bigger" coins,
627        // one of which should be picked at random
628        add_coin(available_coins, *wallet, 5 * CENT);
629        add_coin(available_coins, *wallet, 10 * CENT);
630        add_coin(available_coins, *wallet, 15 * CENT);
631        add_coin(available_coins, *wallet, 20 * CENT);
632        add_coin(available_coins, *wallet, 25 * CENT);
633
634        for (int i = 0; i < RUN_TESTS; i++) {
635            int fails = 0;
636            for (int j = 0; j < RANDOM_REPEATS; j++)
637            {
638                const auto result29 = KnapsackSolver(GroupCoins(available_coins.All()), 90 * CENT, CENT);
639                BOOST_CHECK(result29);
640                const auto result30 = KnapsackSolver(GroupCoins(available_coins.All()), 90 * CENT, CENT);
641                BOOST_CHECK(result30);
642                if (EqualResult(*result29, *result30))
643                    fails++;
644            }
645            BOOST_CHECK_NE(fails, RANDOM_REPEATS);
646        }
647    }
648}
649
650BOOST_AUTO_TEST_CASE(ApproximateBestSubset)
651{
652    FastRandomContext rand{};
653    std::unique_ptr<CWallet> wallet = NewWallet(m_node);
654
655    CoinsResult available_coins;
656
657    // Test vValue sort order
658    for (int i = 0; i < 1000; i++)
659        add_coin(available_coins, *wallet, 1000 * COIN);
660    add_coin(available_coins, *wallet, 3 * COIN);
661
662    const auto result = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_standard), 1003 * COIN, CENT, rand);
663    BOOST_CHECK(result);
664    BOOST_CHECK_EQUAL(result->GetSelectedValue(), 1003 * COIN);
665    BOOST_CHECK_EQUAL(result->GetInputSet().size(), 2U);
666}
667
668// Tests that with the ideal conditions, the coin selector will always be able to find a solution that can pay the target value
669BOOST_AUTO_TEST_CASE(SelectCoins_test)
670{
671    std::unique_ptr<CWallet> wallet = NewWallet(m_node);
672    LOCK(wallet->cs_wallet); // Every 'SelectCoins' call requires it
673
674    // Random generator stuff
675    std::default_random_engine generator;
676    std::exponential_distribution<double> distribution (100);
677    FastRandomContext rand;
678
679    // Run this test 100 times
680    for (int i = 0; i < 100; ++i)
681    {
682        CoinsResult available_coins;
683        CAmount balance{0};
684
685        // Make a wallet with 1000 exponentially distributed random inputs
686        for (int j = 0; j < 1000; ++j)
687        {
688            CAmount val = distribution(generator)*10000000;
689            add_coin(available_coins, *wallet, val);
690            balance += val;
691        }
692
693        // Generate a random fee rate in the range of 100 - 400
694        CFeeRate rate(rand.randrange(300) + 100);
695
696        // Generate a random target value between 1000 and wallet balance
697        CAmount target = rand.randrange(balance - 1000) + 1000;
698
699        // Perform selection
700        CoinSelectionParams cs_params{
701            rand,
702            /*change_output_size=*/ 34,
703            /*change_spend_size=*/ 148,
704            /*min_change_target=*/ CENT,
705            /*effective_feerate=*/ CFeeRate(0),
706            /*long_term_feerate=*/ CFeeRate(0),
707            /*discard_feerate=*/ CFeeRate(0),
708            /*tx_noinputs_size=*/ 0,
709            /*avoid_partial=*/ false,
710        };
711        cs_params.m_cost_of_change = 1;
712        cs_params.min_viable_change = 1;
713        CCoinControl cc;
714        const auto result = SelectCoins(*wallet, available_coins, /*pre_set_inputs=*/{}, target, cc, cs_params);
715        BOOST_CHECK(result);
716        BOOST_CHECK_GE(result->GetSelectedValue(), target);
717    }
718}
719
720BOOST_AUTO_TEST_CASE(waste_test)
721{
722    const CAmount fee{100};
723    const CAmount min_viable_change{300};
724    const CAmount change_cost{125};
725    const CAmount change_fee{30};
726    const CAmount fee_diff{40};
727    const CAmount in_amt{3 * COIN};
728    const CAmount target{2 * COIN};
729    const CAmount excess{80};
730    const CAmount exact_target{in_amt - fee * 2}; // Maximum spendable amount after fees: no change, no excess
731
732    // In the following, we test that the waste is calculated correctly in various scenarios.
733    // Usually, RecalculateWaste would compute change_fee and change_cost on basis of the
734    // change output type, current feerate, and discard_feerate, but we use fixed values
735    // across this test to make the test easier to understand.
736    {
737        // Waste with change is the change cost and difference between fee and long term fee
738        SelectionResult selection1{target, SelectionAlgorithm::MANUAL};
739        add_coin(1 * COIN, 1, selection1, /*fee=*/fee, /*long_term_fee=*/fee - fee_diff);
740        add_coin(2 * COIN, 2, selection1, fee, fee - fee_diff);
741        selection1.RecalculateWaste(min_viable_change, change_cost, change_fee);
742        BOOST_CHECK_EQUAL(fee_diff * 2 + change_cost, selection1.GetWaste());
743
744        // Waste will be greater when fee is greater, but long term fee is the same
745        SelectionResult selection2{target, SelectionAlgorithm::MANUAL};
746        add_coin(1 * COIN, 1, selection2, fee * 2, fee - fee_diff);
747        add_coin(2 * COIN, 2, selection2, fee * 2, fee - fee_diff);
748        selection2.RecalculateWaste(min_viable_change, change_cost, change_fee);
749        BOOST_CHECK_GT(selection2.GetWaste(), selection1.GetWaste());
750