This PR is splitting off some of the improvements made in #28985 and starts addressing the issues raised in #27754.
I aim to completely replace coinselector_tests with coinselection_tests. The goal is to generally use coins created per a nominal effective value so we can get away from testing with CoinSelectionParams that are non-representative and effectuate counterintuitive behavior such as feerate = 0 or cost_of_change = 0
<!--e57a25ab6845829454e8d69fc972939a-->
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
<!--006a51241073e994b41acfe9ec718e94-->
For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/29532.
<!--021abf342d371248e50ceaed478a90ca-->
See the guideline for information on the review process.
| Type | Reviewers |
|---|---|
| ACK | achow101, monlovesmango, w0xlt |
| Concept ACK | jasonribble, ismaelsadeeq, yancyribbens |
If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.
<!--174a7506f384e20aa4161008e828411d-->
No conflicts as of last run.
<!--5faf32d7da4f0f540f40219e4f7537a3-->
64 | +} 65 | + 66 | +/** Make multiple coins with given effective values */ 67 | +static void AddCoins(std::vector<COutput>& utxo_pool, std::vector<CAmount> coins, CFeeRate feerate = default_cs_params.m_effective_feerate) 68 | +{ 69 | + for (int c : coins) {
In 3dff8f0490b4b92c4adf229a828063dfda6d3a80 "[test] Create coinselection_tests"
The elements in coins are CAmount, not int.
Thanks, fixed
73 | + 74 | +/** Group available coins into OutputGroups */ 75 | +inline std::vector<OutputGroup>& GroupCoins(const std::vector<COutput>& available_coins, const CoinSelectionParams& cs_params = default_cs_params, bool subtract_fee_outputs = false) 76 | +{ 77 | + static std::vector<OutputGroup> static_groups; 78 | + static_groups.clear();
In 3dff8f0490b4b92c4adf229a828063dfda6d3a80 "[test] Create coinselection_tests"
There doesn't seem to be a purpose for having a static variable here. We basically treat it as temporary since it's cleared every time.
Removed the static keyword and the clear as suggested.
70 | + utxo_pool.push_back(MakeCoin(c, true, 0, feerate)); 71 | + } 72 | +} 73 | + 74 | +/** Group available coins into OutputGroups */ 75 | +inline std::vector<OutputGroup>& GroupCoins(const std::vector<COutput>& available_coins, const CoinSelectionParams& cs_params = default_cs_params, bool subtract_fee_outputs = false)
In 3dff8f0490b4b92c4adf229a828063dfda6d3a80 "[test] Create coinselection_tests"
Since the expected pattern is to always GroupCoins(utxo_pool), it might make sense to make utxo_pool a std::vector<OutputGroup> and combine this function with AddCoins.
Amended all the functions to directly create OutputGroups instead.
103 | @@ -104,5 +104,40 @@ static bool EquivalentResult(const SelectionResult& a, const SelectionResult& b) 104 | return ret.first == a_amts.end() && ret.second == b_amts.end(); 105 | } 106 | 107 | +static void TestBnBSuccess(std::string test_title, std::vector<COutput>& utxo_pool, const CAmount& selection_target, const std::vector<CAmount>& expected_input_amounts, const CFeeRate& feerate = default_cs_params.m_effective_feerate) 108 | +{ 109 | + SelectionResult expected_result(CAmount(0), SelectionAlgorithm::BNB); 110 | + CAmount expected_amount = 0; 111 | + for (int input_amount : expected_input_amounts) {
In e286c6470bbaa1358fecb7c5a7e109583d158780 "[test] Recreate simple BnB success tests"
The elements of expected_input_amounts are CAmount not int.
Thanks, fixed
115 | + group.Insert(std::make_shared<COutput>(coin), /*ancestors=*/ 0, /*descendants=*/ 0); 116 | + expected_result.AddInput(group); 117 | + } 118 | + 119 | + const auto result = SelectCoinsBnB(GroupCoins(utxo_pool), selection_target, /*cost_of_change=*/ default_cs_params.m_cost_of_change, /*max_weight=*/MAX_STANDARD_TX_WEIGHT); 120 | + BOOST_CHECK_MESSAGE(result, "BnB-Success: " + test_title);
In e286c6470bbaa1358fecb7c5a7e109583d158780 "[test] Recreate simple BnB success tests"
The *_MESSAGE functions print out the message on failure, not on success. So the message should be something that better indicates what the failure was, not something that might suggest something was successful.
Made all tests output messages indicate what went wrong in the success case.
51 | +} 52 | + 53 | +static const CoinSelectionParams default_cs_params = init_default_params(); 54 | + 55 | +/** Make one coin that either has a given effective value (default) or a given amount (`is_eff_value = false`). */ 56 | +static COutput MakeCoin(const CAmount& amount, bool is_eff_value = true, int nInput = 0, CFeeRate feerate = default_cs_params.m_effective_feerate, int custom_spending_vsize = 68)
I have removed nInput from the function parameters of MakeCoin(…).
And then actually also removed it as a variable in the function by assuming that there generally is only one output.
18 | +#include <wallet/test/wallet_test_fixture.h> 19 | +#include <wallet/wallet.h> 20 | + 21 | +#include <algorithm> 22 | +#include <boost/test/unit_test.hpp> 23 | +#include <random>
In https://github.com/bitcoin/bitcoin/commit/3dff8f0490b4b92c4adf229a828063dfda6d3a80:
I don't think we need all this includes. For instance, no wallet is used and <wallet/wallet.h> is included, no fee function is used and wallet/fees.h is included, <random.h> and <random> are included.
Maybe run IOWY to clean this up.
I was able to remove all except for
#include <consensus/amount.h>
#include <wallet/coinselection.h>
#include <wallet/test/wallet_test_fixture.h>
#include <boost/test/unit_test.hpp>
I’m not familiar with IOWY and could not turn up anything with a websearch, what is that?
I’m not familiar with IOWY and could not turn up anything with a websearch, what is that?
Upps, the acronym is IWYU from include-what-you-use. I wrote it fast as IOWY "include only what you use". Should stop using acronyms..
I see, thanks for clarifying. I think I cleared out everything that I don’t use.
118 | + 119 | + const auto result = SelectCoinsBnB(GroupCoins(utxo_pool), selection_target, /*cost_of_change=*/ default_cs_params.m_cost_of_change, /*max_weight=*/MAX_STANDARD_TX_WEIGHT); 120 | + BOOST_CHECK_MESSAGE(result, "BnB-Success: " + test_title); 121 | + BOOST_CHECK(EquivalentResult(expected_result, *result)); 122 | + BOOST_CHECK_EQUAL(result->GetSelectedValue(), expected_amount); 123 | + expected_result.Clear();
In e286c6470b:
No need to clear expected_result. It's created within this function.
Thanks, fixed
I'm not completely sure about 584e524eb57444d7192df1049cafde9ccc480406. The commit description says
Originally these tests verified that at a SelectCoins level that a solution with fewer inputs gets preferred at high feerates, and a solution with more inputs gets preferred at low feerates. This outcome relies on the behavior of BnB, so we move these tests under the umbrella of BnB tests.
It is true that the outcome relies only on the BnB behavior currently but that might not be true in the future. There could be other algorithm clashing with it.
9 | +#include <boost/test/unit_test.hpp> 10 | + 11 | +namespace wallet { 12 | +BOOST_FIXTURE_TEST_SUITE(coinselection_tests, WalletTestingSetup) 13 | + 14 | +static int nextLockTime = 0;
Should be snake_case.
40 | + 41 | +/** Make one coin that either has a given effective value (default) or a given amount (`is_eff_value = false`). */ 42 | +static OutputGroup MakeCoin(const CAmount& amount, bool is_eff_value = true, CoinSelectionParams cs_params = default_cs_params, int custom_spending_vsize = 68) 43 | +{ 44 | + // Always assume that we only have one input 45 | + const int nInput = 0;
nInput is unused, let’s remove it.
47 | + tx.vout.resize(nInput + 1); 48 | + CAmount fees = cs_params.m_effective_feerate.GetFee(custom_spending_vsize); 49 | + tx.vout[nInput].nValue = amount + int(is_eff_value) * fees; 50 | + tx.nLockTime = nextLockTime++; // so all transactions get different hashes 51 | + OutputGroup group(cs_params); 52 | + group.Insert(std::make_shared<COutput>(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/ 1, /*input_bytes=*/ custom_spending_vsize, /*spendable=*/ true, /*solvable=*/ true, /*safe=*/ true, /*time=*/ 0, /*from_me=*/ false, /*fees=*/ fees), /*ancestors=*/0, /*descendants=*/0);
Remove spaces after comments describing params.
51 | + OutputGroup group(cs_params); 52 | + group.Insert(std::make_shared<COutput>(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/ 1, /*input_bytes=*/ custom_spending_vsize, /*spendable=*/ true, /*solvable=*/ true, /*safe=*/ true, /*time=*/ 0, /*from_me=*/ false, /*fees=*/ fees), /*ancestors=*/0, /*descendants=*/0); 53 | + return group; 54 | +} 55 | + 56 | +/** Make multiple coins with given effective values */
Outdated comment, it’s an OutputGroup not coin now.
80 | @@ -80,5 +81,37 @@ static bool EquivalentResult(const SelectionResult& a, const SelectionResult& b) 81 | return ret.first == a_amts.end() && ret.second == b_amts.end(); 82 | } 83 | 84 | +static void TestBnBSuccess(std::string test_title, std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const std::vector<CAmount>& expected_input_amounts, const CoinSelectionParams cs_params = default_cs_params)
Should be a reference.
static void TestBnBSuccess(std::string test_title, std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const std::vector<CAmount>& expected_input_amounts, const CoinSelectionParams& cs_params = default_cs_params)
89 | + OutputGroup group = MakeCoin(input_amount, true, cs_params); 90 | + expected_amount += group.m_value; 91 | + expected_result.AddInput(group); 92 | + } 93 | + 94 | + const auto result = SelectCoinsBnB(utxo_pool, selection_target, /*cost_of_change=*/ default_cs_params.m_cost_of_change, /*max_weight=*/MAX_STANDARD_TX_WEIGHT);
const auto result = SelectCoinsBnB(utxo_pool, selection_target, /*cost_of_change=*/default_cs_params.m_cost_of_change, /*max_weight=*/MAX_STANDARD_TX_WEIGHT);
101 | +{ 102 | + std::vector<OutputGroup> utxo_pool; 103 | + AddCoins(utxo_pool, {1 * CENT, 3 * CENT, 5 * CENT}); 104 | + 105 | + // Simple success cases 106 | + TestBnBSuccess("Select smallest UTXO", utxo_pool, /*selection_target=*/ 1 * CENT, /*expected_input_amounts=*/ {1 * CENT});
Remove spaces after param comments
108 | + TestBnBSuccess("Select biggest UTXO", utxo_pool, /*selection_target=*/ 5 * CENT, /*expected_input_amounts=*/ {5 * CENT}); 109 | + TestBnBSuccess("Select two UTXOs", utxo_pool, /*selection_target=*/ 4 * CENT, /*expected_input_amounts=*/ {1 * CENT, 3 * CENT}); 110 | + TestBnBSuccess("Select all UTXOs", utxo_pool, /*selection_target=*/ 9 * CENT, /*expected_input_amounts=*/ {1 * CENT, 3 * CENT, 5 * CENT}); 111 | + 112 | + // BnB finds changeless solution while overshooting by up to cost_of_change 113 | + TestBnBSuccess("Select upper bound", utxo_pool, /*selection_target=*/ 9 * CENT - default_cs_params.m_cost_of_change, /*expected_input_amounts=*/ {1 * CENT, 3 * CENT, 5 * CENT});
Should not overselect, so we could do this with 4×CENT
TestBnBSuccess("Select upper bound", utxo_pool, /*selection_target=*/ 4 * CENT - default_cs_params.m_cost_of_change, /*expected_input_amounts=*/ {1 * CENT, 3 * CENT});
120 | + AddCoins(low_feerate_pool, {2 * CENT, 3 * CENT, 5 * CENT, 10 * CENT}); 121 | + TestBnBSuccess("Select many inputs at low feerates", low_feerate_pool, /*selection_target=*/ 10 * CENT, /*expected_input_amounts=*/ {2 * CENT, 3 * CENT, 5 * CENT}); 122 | + 123 | + std::vector<OutputGroup> high_feerate_pool; // 25 sat/vB (greater than long_term_feerate of 10 sat/vB) 124 | + CoinSelectionParams high_feerate_params = init_default_params(); 125 | + high_feerate_params.m_effective_feerate = CFeeRate{25'000};
CoinSelectionParams high_feerate_params = init_default_params();
high_feerate_params.m_effective_feerate = CFeeRate{25'000};
std::vector<OutputGroup> high_feerate_pool; // 25 sat/vB (greater than long_term_feerate of 10 sat/vB)
103 | @@ -104,9 +104,18 @@ static void TestBnBSuccess(std::string test_title, std::vector<OutputGroup>& utx 104 | BOOST_CHECK_MESSAGE(result->GetSelectedValue() == expected_amount, "Selected amount mismatch in BnB-Success: " + test_title); 105 | } 106 | 107 | +static void TestBnBFail(std::string test_title, std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target) 108 | +{ 109 | + BOOST_CHECK_MESSAGE(!SelectCoinsBnB(utxo_pool, selection_target, /*cost_of_change=*/ default_cs_params.m_cost_of_change, /*max_weight=*/MAX_STANDARD_TX_WEIGHT), "BnB-Fail: " + test_title);
remove spaces
127 | @@ -119,6 +128,14 @@ BOOST_AUTO_TEST_CASE(bnb_test) 128 | // BnB finds changeless solution while overshooting by up to cost_of_change 129 | TestBnBSuccess("Select upper bound", utxo_pool, /*selection_target=*/ 9 * CENT - default_cs_params.m_cost_of_change, /*expected_input_amounts=*/ {1 * CENT, 3 * CENT, 5 * CENT}); 130 | 131 | + // BnB fails to find changeless solution when overshooting by cost_of_change + 1 sat 132 | + TestBnBFail("Overshoot upper bound", utxo_pool, /*selection_target=*/ 9 * CENT - default_cs_params.m_cost_of_change - 1);
TestBnBFail("Overshoot upper bound", utxo_pool, /*selection_target=*/4 * CENT - default_cs_params.m_cost_of_change - 1);
112 | BOOST_AUTO_TEST_CASE(bnb_test)
113 | {
114 | std::vector<OutputGroup> utxo_pool;
115 | +
116 | + // Fail for empty UTXO pool
117 | + TestBnBFail("Empty UTXO pool", utxo_pool, /*selection_target=*/ 1 * CENT);
Space
Alright, should hopefully be ready to review.
I'm not completely sure about 584e524. The commit description says
Originally these tests verified that at a SelectCoins level that a solution with fewer inputs gets preferred at high feerates, and a solution with more inputs gets preferred at low feerates. This outcome relies on the behavior of BnB, so we move these tests under the umbrella of BnB tests.
It is true that the outcome relies only on the BnB behavior currently but that might not be true in the future. There could be other algorithm clashing with it.
Yeah, so the old tests assumed that because BnB behaved a certain way, we would get a specific overall outcome. The new tests just check that BnB behaves a certain way. We might still want tests that test the overall outcome as a result from the interaction of multiple coin selection tests, but this one seemed clearly to be testing BnB behavior, and it seemed strange to me to be testing that at the level where the results are combined rather than checking that BnB assumptions are fulfilled by BnB.
<!--85328a0da195eb286784d51f73fa0af9-->
🚧 At least one of the CI tasks failed. <sub>Debug: https://github.com/bitcoin/bitcoin/runs/29957535397</sub>
<details><summary>Hints</summary>
Make sure to run all tests locally, according to the documentation.
The failure may happen due to a number of reasons, for example:
Possibly due to a silent merge conflict (the changes in this pull request being incompatible with the current code in the target branch). If so, make sure to rebase on the latest commit of the target branch.
A sanitizer issue, which can only be found by compiling with the sanitizer and running the affected test.
An intermittent issue.
Leave a comment here, if you need help tracking down a confusing failure.
</details>
7 | +#include <wallet/test/wallet_test_fixture.h> 8 | + 9 | +#include <boost/test/unit_test.hpp> 10 | + 11 | +namespace wallet { 12 | +BOOST_FIXTURE_TEST_SUITE(coinselection_tests, WalletTestingSetup)
nit: As far as I can see, no test case in this file uses the WalletTestingSetup wallet. So we could save some initialization time on each test case by changing it to TestingSetup. And if any future test requires a wallet, it could be specified in-place.
Thanks, great, taken!
nit: I have read the test and I don't have any code related comment yet, but I have noticed that some of the commits are structured with some not written conventions and beside the actual comments about commit message quality in the CONTRIBUTIONS.md file, there are some other conventions used by other contributors too, in a similar fashion to conventional commits with (wallet:, ci:, rpc:). In that spirit, wouldn't be a good idea to, in case there needs to be a change in some of the commits, to change from [test] to test: or coinselection: to scope the commits a little bit more and move towards a common format? Also, do you think is worth to add these conventions to the CONTRIBUTIONS.md file?
160 | + TestBnBSuccess("Combine smallest 8 of 17 unique UTXOs", doppelganger_pool, /*selection_target=*/8 * CENT, /*expected_input_amounts=*/expected_inputs); 161 | + 162 | + // Starting with 18 unique UTXOs of similar effective value we will not find the solution 163 | + AddCoins(doppelganger_pool, {1 * CENT + default_cs_params.m_cost_of_change + 17}); 164 | + TestBnBFail("Exhaust looking for smallest 8 of 18 unique UTXOs", doppelganger_pool, /*selection_target=*/8 * CENT); 165 | +}
nit: perhaps the comment on line 144 can be more descriptive for this part. (or the comments in general can be improved). It's the strangest test in the group.
maybe you can rename the "18" value as a BnB threshold
I added a longer explanation to this test. Luckily 18 is not generally the limit, it’s just the limit in this artificially crafted case where all of our UTXOs have very similar amounts and we have to pick eight of them to meet the target. Please let me know if the test makes sense now! :)
51 | + OutputGroup group(cs_params); 52 | + group.Insert(std::make_shared<COutput>(COutPoint(tx.GetHash(), 0), tx.vout.at(0), /*depth=*/1, /*input_bytes=*/custom_spending_vsize, /*spendable=*/true, /*solvable=*/true, /*safe=*/true, /*time=*/0, /*from_me=*/false, /*fees=*/fees), /*ancestors=*/0, /*descendants=*/0); 53 | + return group; 54 | +} 55 | + 56 | +/** Make multiple OutpuGroups with the given values as their effective value */
minor spelling: OutputGroups
30 | + /*tx_noinputs_size=*/11 + 31, //static header size + output size 31 | + /*avoid_partial=*/false, 32 | + }; 33 | + dcsp.m_change_fee = /*155 sats=*/dcsp.m_effective_feerate.GetFee(dcsp.change_output_size); 34 | + dcsp.m_cost_of_change = /*204 + 155 sats=*/dcsp.m_discard_feerate.GetFee(dcsp.change_spend_size) + dcsp.m_change_fee; 35 | + dcsp.min_viable_change = /*204 sats=*/dcsp.m_discard_feerate.GetFee(dcsp.change_spend_size);
Can we eliminate a call to GetFee via reordering assignment?
dcsp.m_change_fee = /*155 sats=*/dcsp.m_effective_feerate.GetFee(dcsp.change_output_size);
dcsp.min_viable_change = /*204 sats=*/dcsp.m_discard_feerate.GetFee(dcsp.change_spend_size);
dcsp.m_cost_of_change = /*204 + 155 sats=*/dcsp.min_viable_change + dcsp.m_change_fee;
Thanks, great suggestion. I’ve adopted that change.
8 | @@ -9,6 +9,7 @@ target_sources(test_bitcoin 9 | init_test_fixture.cpp 10 | wallet_test_fixture.cpp 11 | coinselector_tests.cpp 12 | + coinselection_tests.cpp
Is this name going to set this portion of tests apart enough to be meaningful? It seems only some of the BnB tests that were present in coinselector_tests have been refactored
disregard this comment. I skipped your intent in the description
Yeah, as explained, the intention is to rewrite all coinselection tests with transactions that could be encountered in the wild rather than the artificial zero-fee transactions the old tests are using.
159 | + // Among up to 17 unique UTXOs of similar effective value we will find a solution composed of the eight smallest 160 | + TestBnBSuccess("Combine smallest 8 of 17 unique UTXOs", doppelganger_pool, /*selection_target=*/8 * CENT, /*expected_input_amounts=*/expected_inputs); 161 | + 162 | + // Starting with 18 unique UTXOs of similar effective value we will not find the solution 163 | + AddCoins(doppelganger_pool, {1 * CENT + default_cs_params.m_cost_of_change + 17}); 164 | + TestBnBFail("Exhaust looking for smallest 8 of 18 unique UTXOs", doppelganger_pool, /*selection_target=*/8 * CENT);
This segment of code appears to me to be intended to refactor the make_hard_case exhaustion tests, but with differing amounts (17,18 vs. 14,17) and construction (amount = iterative CENT + i vs. bitshifting?). Isn't there double the coins being created in the make_hard_case? I appreciate that this format is more readable, though it's unclear to me why one should exhaust based on the given coin sizes and quantity. Is this related to src/wallet/coinselection.cpp setting TOTAL_TRIES to 100,000 constraining the useful effective traversal depth?
Yes, this tests that BnB will fail to find the best solution when the attempts exceed the TOTAL_TRIES limit of 100,000. This test follows the same approach but is slightly different than the one in the original tests. I wanted to replace the old test because I found it too difficult to parse, but I came up with my own way of testing it. I have expanded the explanation of what is going on here, and how I created this artificial example that manages to exhaust the limit with only 18 UTXOs.—To be clear, usually we would be able to handle much bigger UTXO pools and still find solutions, this UTXO pool is specifically crafted to cause all possible combinations to be explored.
133 | - add_coin(CAmount{1} << (utxos+i), 2*i, utxo_pool); 134 | - add_coin((CAmount{1} << (utxos+i)) + (CAmount{1} << (utxos-1-i)), 2*i + 1, utxo_pool); 135 | - } 136 | - return target; 137 | -} 138 | -
Worth noting that src/bench/coin_selection.cpp makes a copy of the make_hard_case function (commenting as such), so removal here may lead to confusion unless that benchmark is also updated.
Thanks, I’ll make a note to update the benchmark as well.
I spent a lot of time figuring out how make_hard works. Thanks for replacing it with a version that actually explains itself instead of making it a mensa test.
Thanks @furszy, @nymius, @jasonribble, and @vicariousdrama for the review! I updated the commit message names as suggested, adopted all of your proposed changes as indicated, and added more explanation to the test covering the attempt limit.
Also, do you think is worth to add these conventions to the
CONTRIBUTIONS.mdfile?
I don’t know! It would be a good thing to ask in the IRC channel or at the weekly meeting. :)
So C++ noob question. Not sure if this is an appropriate place to ask.
I'm noticing that you're calling CFeeRate with an int:
https://github.com/bitcoin/bitcoin/blob/280e65d3a7993ea38ba49ae00133a7ba709c193e/src/wallet/test/coinselection_tests.cpp#L20-L38
Okay that's cool, clearly it compiles and runs...but how?
src/policy/feerate.h has the class definition. I don't see how it's able to only take an int
This is my best bet of how it works
it's using std::integral, maybe doing some weird magic I didn't know we had. But, I don't see #include <concepts>.
Btw, this curiosity all started because my editor highlighted this error
no instance of constructor "CFeeRate::CFeeRate" matches the argument listC/C++(289)
Then in src/policy/feerate.h it the IDE says
namespace "std" has no member "integral"C/C++(135)
I see that it does compile but where does CFeeRate get constructed with only an int?
@jasonribble template<std::integral I> is the same as template<typename I>, with the added restriction that I must be a type that satisfies the std::integral concept. Since int does satisfy that concept, I can be instantiated as int.
@jasonribble
template<std::integral I>is the same astemplate<typename I>, with the added restriction thatImust be a type that satisfies thestd::integralconcept. Sinceintdoes satisfy that concept,Ican be instantiated asint.
Magical. Thank you 🙏
But, I don't see #include <concepts>.
If you check the IWYU logs in the "tidy" CI job you will see that it is indeed missing:
[19:28:01.280] /ci_container_base/src/policy/feerate.h should add these lines:
[19:28:01.280] #include <concepts> // for integral
This report is generated on each CI run, but the missing includes are not enforced. This can be confusing, so best to always check the CI output.
it is indeed missing
Oh interesting! Well, I guess not in this important for this PR, but perhaps it should be explicit. Especially so people don't get those evil red lines
ACK
I went through each of the commits. It is an improvement of the branch and bound selection tests.
Concept ACK
97 | +} 98 | + 99 | +BOOST_AUTO_TEST_CASE(bnb_test) 100 | +{ 101 | + std::vector<OutputGroup> utxo_pool; 102 | + AddCoins(utxo_pool, {1 * CENT, 3 * CENT, 5 * CENT});
In f3b0593b8: Can you explain why did you remove the other coins (2 and 4) that were here before? Guess they will be selected and break something if we re-add them because of the algo predilection for unifying utxos?
I just felt that it wasn’t necessary to have four UTXOs to replicate the same coverage. Rather I wanted to be explicit about the cases that are being tested and show that they all work, but I felt that three UTXOs were sufficient to achieve that.
91 | + } 92 | + 93 | + const auto result = SelectCoinsBnB(utxo_pool, selection_target, /*cost_of_change=*/default_cs_params.m_cost_of_change, /*max_selection_weight=*/MAX_STANDARD_TX_WEIGHT); 94 | + BOOST_CHECK_MESSAGE(result, "Falsy result in BnB-Success: " + test_title); 95 | + BOOST_CHECK_MESSAGE(EquivalentResult(expected_result, *result), "Result mismatch in BnB-Success: " + test_title); 96 | + BOOST_CHECK_MESSAGE(result->GetSelectedValue() == expected_amount, "Selected amount mismatch in BnB-Success: " + test_title);
In https://github.com/bitcoin/bitcoin/commit/f3b0593b8bd67bc919b21cd636a01813fc5538c8:
This could output a bit more detailed error message:
BOOST_CHECK_MESSAGE(EquivalentResult(expected_result, *result), strprintf("Result mismatch in BnB-Success: %s. Expected %s vs %s", test_title, InputsToString(expected_result), InputsToString(*result)));
BOOST_CHECK_MESSAGE(result->GetSelectedValue() == expected_amount, strprintf("Selected amount mismatch in BnB-Success: %s. Expected %d vs %d", test_title, expected_amount, result->GetSelectedValue()));
But you would need something like this too:
static std::string InputsToString(const SelectionResult& selection)
{
std::string res = "[";
for (const auto& input : selection.GetInputSet()) {
res += util::ToString(input->txout.nValue);
}
return res + "]";
}
Thanks, great suggestion.
18 | + * parameters when a diverging value is relevant in the context of a test. */ 19 | +static CoinSelectionParams init_default_params() 20 | +{ 21 | + CoinSelectionParams dcsp{ 22 | + /*rng_fast*/default_rand, 23 | + /*change_output_size=*/31,
In a8bf940ae20ed5a03a1cc328212fcac3c3462b43
A comment explaining why you selected these magic numbers would be helpful.
similar to tx_noinputs_size or an indication if they are just random.
i.e values when initializing default CSP, and some defaults in MakeCoin
I wanted to use representative values, but also avoid using values whose multiples overlap. So, I used the vsize of P2WPKH inputs and outputs.
I added to the description that the change weights are taken from the P2WPKH output type.
could also use a const for these magic numbers.
P2WPKH_VB_SIZE = 31
19 | +static CoinSelectionParams init_default_params() 20 | +{ 21 | + CoinSelectionParams dcsp{ 22 | + /*rng_fast*/default_rand, 23 | + /*change_output_size=*/31, 24 | + /*change_spend_size=*/68,
After this PR, we will have two coin selection test files. Is there a reason why?
Wouldn't it be better to add a commit that renames coinselector_tests to coinselection_tests and modify the test name to coinselection_tests?
As mentioned in the opening comment, I’m looking to completely change the approach. Instead of using absolute values and feerates of zero, transactions in the new tests use real feerates, and spend UTXOs whose effective values are round amounts. Since there are a ton of tests, I expected that it would be too much to get reviewed in a single PR, and migrating from the old test suite to the new test suite would make it obvious which ones had been updated already.
It could have also been done by renaming first and then updating in place, but this seemed easier to understand, especially because it was going to use a different framework in parallel. Having even more "MakeCoin" and "AddCoin" etc. functions in the same test suite would have been pretty confusing.
60 | + } 61 | +} 62 | + 63 | +/** Check if SelectionResult a is equivalent to SelectionResult b. 64 | + * Equivalent means same input values, but maybe different inputs (i.e. same value, different prevout) */ 65 | +static bool EquivalentResult(const SelectionResult& a, const SelectionResult& b)
Since we are checking for Value equivalence, this can just be
CheckValueEquivalence for clarity
Okay, I renamed it to "HaveEquivalentValues"
73 | + b_amts.push_back(coin->txout.nValue); 74 | + } 75 | + std::sort(a_amts.begin(), a_amts.end()); 76 | + std::sort(b_amts.begin(), b_amts.end()); 77 | + 78 | + std::pair<std::vector<CAmount>::iterator, std::vector<CAmount>::iterator> ret = std::mismatch(a_amts.begin(), a_amts.end(), b_amts.begin());
auto ret = std::mismatch(a_amts.begin(), a_amts.end(), b_amts.begin());
108 | + } 109 | + 110 | + const auto result = SelectCoinsBnB(utxo_pool, selection_target, /*cost_of_change=*/default_cs_params.m_cost_of_change, /*max_selection_weight=*/MAX_STANDARD_TX_WEIGHT); 111 | + BOOST_CHECK_MESSAGE(result, "Falsy result in BnB-Success: " + test_title); 112 | + BOOST_CHECK_MESSAGE(HaveEquivalentValues(expected_result, *result), strprintf("Result mismatch in BnB-Success: %s. Expected %s, but got %s", test_title, InputsToString(expected_result), InputsToString(*result))); 113 | +BOOST_CHECK_MESSAGE(result->GetSelectedValue() == expected_amount, strprintf("Selected amount mismatch in BnB-Success: %s. Expected %d, but got %d", test_title, expected_amount, result->GetSelectedValue()));
nit - this should be indented. Right now it's mis-aligned.
100 | +static void TestBnBSuccess(std::string test_title, std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const std::vector<CAmount>& expected_input_amounts, const CoinSelectionParams& cs_params = default_cs_params) 101 | +{ 102 | + SelectionResult expected_result(CAmount(0), SelectionAlgorithm::BNB); 103 | + CAmount expected_amount = 0; 104 | + for (CAmount input_amount : expected_input_amounts) { 105 | + OutputGroup group = MakeCoin(input_amount, true, cs_params);
nit - you can simplify this line slightly by using the default arguments instead of passing them explicitly.
OutputGroup group = MakeCoin(input_amount);
nit - you can simplify this line slightly by using the default arguments instead of passing them explicitly.
No, the way this method is written, it is possible to pass in a custom CoinSelectionParams object and it will be passed through to MakeCoin. If I adopted the change you propose, the MakeCoin call here would be limited to the default parameters.
Ah I see, even though that wouldn't cause any test failures, that would limit the functions behavior in the future. My mistake.
Concept ACK to refactor the tests. TestBnBSuccess and TestBnBFail are much better and easier to read. Thanks!
non-representative and effectuate counterintuitive behavior such as feerate = 0 or cost_of_change = 0
I'm still trying to sus out what the tests are doing now that's better than before. Most of the current tests use a cost_of_change = 0.5 * COIN, for example. I personally added a test five years ago to test cost_of_change. Also, there are some that do test with varying feerates here that you replaced. Although I do agree that every test should have feerate above zero and existing tests have feerate of zero which means that effective_value == value which is never the case in practice.
Concept ACK to refactor the tests.
TestBnBSuccessandTestBnBFailare much better and easier to read. Thanks!
I’m glad to read that.
non-representative and effectuate counterintuitive behavior such as feerate = 0 or cost_of_change = 0
I'm still trying to sus out what the tests are doing now that's better than before.
For example, our waste calculation used to assume that cost_of_change being zero indicated that the transaction is changeless and any excess should be dropped to fees even when there were enough funds left to create a change output. This can lead to unexpected outcomes when we are comparing two selections with change. We would expect at low feerates the input set with more inputs to be preferred, but instead the selection with the smaller change budget is preferred.
My motivation for this PR was that I was debugging issues several times and lost hours due to expecting other outcomes than the ones exhibited in the tests, because setting values to zero that should never be zero leads to all sorts of quirky outcomes. Using values that can actually appear in production makes these tests much easier to follow.
Most of the current tests use a cost_of_change = 0.5 * COIN, for example.
These new tests do not exhibit the behavior you point out. Which commit is this that you are linking to? As mentioned, this is just the first PR of an attempt to completely replace the old tests, to be followed by more refactors if/when this ever gets merged.
Also, there are some that do test with varying feerates here that you replaced.
Yes, I believe that these tests have been replaced with new tests that introduce equivalent coverage. Please see the commit "test: Move BnB feerate sensitivity tests" and the commit message of the commit.
Which commit is this that you are linking to?
This is master from only a few days ago when I submitted the review feedback.
127 | @@ -121,6 +128,12 @@ BOOST_AUTO_TEST_CASE(bnb_test) 128 | 129 | // BnB finds changeless solution while overshooting by up to cost_of_change 130 | TestBnBSuccess("Select upper bound", utxo_pool, /*selection_target=*/4 * CENT - default_cs_params.m_cost_of_change, /*expected_input_amounts=*/{1 * CENT, 3 * CENT}); 131 | + 132 | + // Test skipping of equivalent input sets 133 | + std::vector<OutputGroup> clone_pool; 134 | + AddCoins(clone_pool, {2 * CENT, 7 * CENT, 7 * CENT});
Good idea to simplify this by reducing the size of the set. Two sevens here with a reduced target amount serves the same purpose as five sevens.
122 | BOOST_AUTO_TEST_CASE(bnb_test)
123 | {
124 | std::vector<OutputGroup> utxo_pool;
125 | +
126 | + // Fail for empty UTXO pool
127 | + TestBnBFail("Empty UTXO pool", utxo_pool, /*selection_target=*/1 * CENT);
This is really minor nit, although I find the /*selection_target=* comments to be more distracting than helpful personally.
150 | @@ -151,6 +151,41 @@ BOOST_AUTO_TEST_CASE(bnb_test) 151 | AddCoins(clone_pool, {2 * CENT, 7 * CENT, 7 * CENT}); 152 | AddDuplicateCoins(clone_pool, 50'000, 5 * CENT); 153 | TestBnBSuccess("Skip equivalent input sets", clone_pool, /*selection_target=*/16 * CENT, /*expected_input_amounts=*/{2 * CENT, 7 * CENT, 7 * CENT}); 154 | + 155 | + /* Test BnB attempt limit (`TOTAL_TRIES`)
It would be nice if BnB returned the total_tries, like coin_grinder. I recently added that to the rust implementation since I think it's useful for regression testing. If BnB was ever refactored or had changes it would come in handy imo.
That seems like a good idea, but that’s out of scope for this PR. I have had a refactor of BnB on my todo list for a long time, and it would be part of that, probably.
We would expect at low feerates the input set with more inputs to be preferred, but instead the selection with the smaller change budget is preferred.
I'm familiar with change_budget as it exists in coin-grinder. Beyond that, I'm not sure how that ties in to BnB and SRD.
Please see the commit "test: Move BnB feerate sensitivity tests" and the commit message of the commit.
I reviewed the commits, and it appears that the test coverage is equivalent. It might be helpful to document a baseline of what we want to be sure is tested for each algorithm at some point, understanding that extended coverage is handled by fuzz testing/mutation testing/property testing.
189 | +} 190 | + 191 | +BOOST_AUTO_TEST_CASE(bnb_feerate_sensitivity_test) 192 | +{ 193 | + // Create sets of UTXOs with the same effective amounts at different feerates (but different absolute amounts) 194 | + std::vector<OutputGroup> low_feerate_pool; // 5 sat/vB (default, and lower than long_term_feerate of 10 sat/vB)
This file has some strange formatting that does not show up in Github. My editor (Vim) just shows a character that seems like a translation error.
5 sat
I opened the file with xxd and the translation is 35e2 80af 7361 742f. 35 is the hex for 5 in ascii, and 73 is the hex for s. It looks like 80 is extended hex for the euro sign and e2 and af also have extended hex meanings. There are more of these weird encodings thought the file.
0xe280af is the UTF-8 encoding for a narrow no-break space: https://www.fileformat.info/info/unicode/char/202f/index.htm
Thanks. It's sort of interesting that this sort of thing doesn't even appear in the Github review. This implies that if one only reviews by Github diff, there is hidden characters that can go in un-noticed. Presumably in this case, there is some editors that can translated this UTF-8 encoding.
<!--85328a0da195eb286784d51f73fa0af9-->
🚧 At least one of the CI tasks failed. <sub>Debug: https://github.com/bitcoin/bitcoin/runs/39320450081</sub>
<details><summary>Hints</summary>
Try to run the tests locally, according to the documentation. However, a CI failure may still happen due to a number of reasons, for example:
Possibly due to a silent merge conflict (the changes in this pull request being incompatible with the current code in the target branch). If so, make sure to rebase on the latest commit of the target branch.
A sanitizer issue, which can only be found by compiling with the sanitizer and running the affected test.
An intermittent issue.
Leave a comment here, if you need help tracking down a confusing failure.
</details>
157 | + * Generally, on a diverse UTXO pool BnB will quickly pass over UTXOs bigger than the target and then start 158 | + * combining small counts of UTXOs that in sum remain under the selection_target+cost_of_change. When there are 159 | + * multiple UTXOs that have matching amount and cost, combinations with equivalent input sets are skipped. The UTXO 160 | + * pool for this test is specifically crafted to create as much branching as possible. The selection target is 161 | + * 8 CENT while all UTXOs are slightly bigger than 1 CENT. The smallest eight are 100,000…100,007 sats, while the larger 162 | + * ten are 100,009,…,100,018 sats plus cost_of_change.
* nine are 100,008,…,100,016 sats plus cost_of_change.
As discussed during Bitcoin Core Review Club, at least one test with 0 fee rate should probably be added to avoid test coverage regression.
Thanks for hosting Murch!
9 | @@ -10,6 +10,7 @@ target_sources(test_bitcoin 10 | wallet_test_fixture.cpp 11 | db_tests.cpp 12 | coinselector_tests.cpp 13 | + coinselection_tests.cpp
nit: Since coinselection_tests.cpp is introduced in the first commit, this change may be there as well.
I had forgotten why I did it that way, but when I tried that, testing the first commit results in warnings that the helper functions are unused.
86 | + 87 | + auto ret = std::mismatch(a_amts.begin(), a_amts.end(), b_amts.begin()); 88 | + return ret.first == a_amts.end() && ret.second == b_amts.end(); 89 | +} 90 | + 91 | +static std::string InputsToString(const SelectionResult& selection)
nit: Just for clarity
static std::string InputAmountsToString(const SelectionResult& selection)
Taken, thanks
96 | + res += " "; 97 | + } 98 | + return res + "]"; 99 | +} 100 | + 101 | +static void TestBnBSuccess(std::string test_title, std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const std::vector<CAmount>& expected_input_amounts, const CoinSelectionParams& cs_params = default_cs_params, int custom_spending_vsize = 68)
nit: This function is added in the commit https://github.com/bitcoin/bitcoin/pull/29532/commits/66200b3ffa21605fc3234ccbda7b424381f3319a and then modified in the commit https://github.com/bitcoin/bitcoin/pull/29532/commits/afd4b807ff1300e4f74ceab6a683f3ff1376369d. It can be added directly as it is in the latest commit.
I did that on purpose to illustrate that the function now needs the custom weight for the new test
nit: Perhaps the commit descriptions ("BnB rate sensitivity tests", "simple BnB failure tests", and "BnB iteration exhaustion test", for example) could become functions for clarity (not necessarily new test cases).
nit: Some commits can be squashed to avoid warnings like "unused function".
nit: Perhaps the commit descriptions ("BnB rate sensitivity tests", "simple BnB failure tests", and "BnB iteration exhaustion test", for example) could become functions for clarity (not necessarily new test cases).
I’m not sure I understand what you mean. Do you mean that I introduce helper functions like "TestBnBSuccess" for the new tests instead of making them their own test cases?
nit: Some commits can be squashed to avoid warnings like "unused function". @w0xlt: I ran each commit, and I did not receive this warning. Could you let me know which commit resulted in that warning for you?
As discussed during Bitcoin Core Review Club, at least one test with 0 fee rate should probably be added to avoid test coverage regression. @monlovesmango: I added another commit to run the simple tests at various feerates, including the feerates 0 sat/kvB, 1 sat/kvB, and 1,500,000 sat/kvB.
Rebased due to strange CI failures
Edit: It seems to me that
wallet_backwards_compatibility.py got addressed via #32369p2p_i2p_ports.py. Anyone have an idea?86 | + std::string res = "[ "; 87 | + for (const auto& input : selection.GetInputSet()) { 88 | + res += util::ToString(input->txout.nValue); 89 | + res += " "; 90 | + } 91 | + return res + "]";
In 30479487c26dec47ac609009838d82b53cce4a3c "test: Recreate simple BnB success tests"
This is essentially a reimplementation of util::Join. This could be a one-liner of:
return "[" + util::Join(selection.GetInputSet(), " ", [](const auto& input){ return util::ToString(input->txout.nValue);}) + "]";
Thanks, I used your suggestion.
161 | + * 8 CENT while all UTXOs are slightly bigger than 1 CENT. The smallest eight are 100,000…100,007 sats, while the larger 162 | + * nine are 100,368…100,375 (i.e., 100,008…100,016 sats plus cost_of_change (359 sats)). 163 | + * 164 | + * Because BnB will only select input sets that fall between selection_target and selection_target + cost_of_change, 165 | + * and the search traverses the UTXO pool from large to small amounts, the search will visit every single 166 | + * combination of eight inputs. All except the last combination will overshoot by more than cost_of_change on the eighth input, because the larger nine inputs each exceed 1 CENT by more than cost_of_change.
In 1c1087132eb88c1e4e5a3ded89c8712ac8a54638 "test: Recreate BnB iteration exhaustion test"
nit: This line is double the length of all the other ones, it could use as linebreak somewhere.
I think the first 2 commits could be combined. The first commit is harder to review since it introduces a bunch of helpers that are completely unused. In fact, the file is introduced but not to the build system, so we can't even check if it compiles.
ACK https://github.com/bitcoin/bitcoin/pull/29532/commits/dbf1f2663b1afbe03d6b1855f83db604bc79979e
I ran each commit, and I did not receive this warning. Could you let me know which commit resulted in that warning for you?
It was caused by the coinselection_tests.cpp as you mentioned here: #29532 (review)
Do you mean that I introduce helper functions like "TestBnBSuccess" for the new tests instead of making them their own test cases?
I was referring to something like the code below (which encapsulates the latest commit changes), but it was just a suggestion. The current code looks good to me too.
void iteration_exhaustion_test(...){
std::vector<OutputGroup> doppelganger_pool;
std::vector<CAmount> doppelgangers;
std::vector<CAmount> expected_inputs;
for (int i = 0; i < 17; ++i) {
// ...
}
AddCoins(doppelganger_pool, doppelgangers);
// Among up to 17 unique UTXOs of similar effective value we will find a solution composed of the eight smallest UTXOs
TestBnBSuccess("Combine smallest 8 of 17 unique UTXOs", doppelganger_pool, /*selection_target=*/8 * CENT, /*expected_input_amounts=*/expected_inputs);
// Starting with 18 unique UTXOs of similar effective value we will not find the solution due to exceeding the attempt limit
AddCoins(doppelganger_pool, {1 * CENT + default_cs_params.m_cost_of_change + 17});
TestBnBFail("Exhaust looking for smallest 8 of 18 unique UTXOs", doppelganger_pool, /*selection_target=*/8 * CENT);
}
BOOST_AUTO_TEST_CASE(bnb_test) {
// ...
iteration_exhaustion_test(...);
}
Recreates the tests in a new test suite coinselection_tests.cpp that is
based on UTXOs being created per their effective values rather than
nominal values and uses transactions with non-zero feerates.
Originally these tests verified that at a SelectCoins level that a
solution with fewer inputs gets preferred at high feerates, and a
solution with more inputs gets preferred at low feerates. This outcome
relies on the behavior of BnB, so we move these tests under the umbrella
of BnB tests.
Originally these tests relied on SFFO to work.
We do not need to repeat the same test multiple times because BnB is
deterministic and will therefore always have the same outcome.
Additionally, this test was redundant because it repeats the "Smallest
combination too big" test.
108 | + expected_result.AddInput(group); 109 | + } 110 | + 111 | + const auto result = SelectCoinsBnB(utxo_pool, selection_target, /*cost_of_change=*/default_cs_params.m_cost_of_change, /*max_selection_weight=*/MAX_STANDARD_TX_WEIGHT); 112 | + BOOST_CHECK_MESSAGE(result, "Falsy result in BnB-Success: " + test_title); 113 | + BOOST_CHECK_MESSAGE(HaveEquivalentValues(expected_result, *result), strprintf("Result mismatch in BnB-Success: %s. Expected %s, but got %s", test_title, InputAmountsToString(expected_result), InputAmountsToString(*result)));
Nit: this seems to be checking for a match, not a mismatch
BOOST_CHECK_MESSAGE(HaveEquivalentValues(expected_result, *result), strprintf("Result match in BnB-Success: %s. Expected %s, and got %s", test_title, InputAmountsToString(expected_result), InputAmountsToString(*result)));
Right, it checks whether the expected result and the selected input set match, but the message here is printed in the case of a failure!
Ok I see! I understand now. Sorry was running with --log_level=all and was misinterpreting these as success messages. Please disregard..
Thanks for taking such a thorough look!
109 | + } 110 | + 111 | + const auto result = SelectCoinsBnB(utxo_pool, selection_target, /*cost_of_change=*/default_cs_params.m_cost_of_change, /*max_selection_weight=*/MAX_STANDARD_TX_WEIGHT); 112 | + BOOST_CHECK_MESSAGE(result, "Falsy result in BnB-Success: " + test_title); 113 | + BOOST_CHECK_MESSAGE(HaveEquivalentValues(expected_result, *result), strprintf("Result mismatch in BnB-Success: %s. Expected %s, but got %s", test_title, InputAmountsToString(expected_result), InputAmountsToString(*result))); 114 | + BOOST_CHECK_MESSAGE(result->GetSelectedValue() == expected_amount, strprintf("Selected amount mismatch in BnB-Success: %s. Expected %d, but got %d", test_title, expected_amount, result->GetSelectedValue()));
Nit: this also seems to be checking for a match
BOOST_CHECK_MESSAGE(result->GetSelectedValue() == expected_amount, strprintf("Selected amount match in BnB-Success: %s. Expected %d, and got %d", test_title, expected_amount, result->GetSelectedValue()));
Disregard, misunderstood when message would be displayed.
ACK dbf1f2663b1afbe03d6b1855f83db604bc79979e
I like how it now covers a variety of fee rates.
I was referring to something like the code below (which encapsulates the latest commit changes), but it was just a suggestion. The current code looks good to me too.
I see, thanks. I guess it could be nice to be able to run the test suite in smaller portions especially if some of the tests took a long time, but it overall runs extremely quickly, so I’m not sure it is necessary to further structure the tests at this time.
I intend to work on porting the other algorithms’ tests in the same manner, and I can pick this up in a follow-up commit, if we decide that’s the way to go then.
Should be ready to review, again.
ACK 85368aafa0d1772626d5f615e272b1c1a580b42f
ACK 85368aafa0d1772626d5f615e272b1c1a580b42f
39 | +} 40 | + 41 | +static const CoinSelectionParams default_cs_params = init_default_params(); 42 | + 43 | +/** Make one OutputGroup with a single UTXO that either has a given effective value (default) or a given amount (`is_eff_value = false`). */ 44 | +static OutputGroup MakeCoin(const CAmount& amount, bool is_eff_value = true, CoinSelectionParams cs_params = default_cs_params, int custom_spending_vsize = 68)
As the is_eff_value arg is always true for all the tests. What about removing it?.
Also, you are expecting group.GetSelectionAmount() to be equal to tx.vout[0].nValue with this parameter right?. I'm unsure that will always be the case.
As a test, could try adding an assertion at the end of this function. I have a hunch it will crash.
I believe the plan is to rewrite all of the tests into this style over the course of a couple PRs. So this parameter is here to allow for the future testing of SFFO behavior.
Also, you are expecting group.GetSelectionAmount() to be equal to tx.vout[0].nValue with this parameter right?
Only when it is false. The purpose is to have group.GetSelectionAmount() be eqaul to amount, so nValue is increased by the amount in fees so that they match after fees are deducted.