[refactor] Make TransactionWithinChainLimit more flexible

kallewoof commented at 4:07 pm on March 7, 2018: member

Currently, TransactionWithinChainLimit is restricted to single-output use, and needs to be called every time for different limits. If it is replaced with a chain limit value calculator, that can be called once and reused, and is generally more flexible (see e.g. #12257).

Update: this PR now corrects usage of max ancestors / max descendants, including calculating the correct max descendant value, as advertised for the two limits.

This change also makes nMaxAncestors signed, as the replacement method will return -1 for “not in the mempool”, which is different from “0”, which means “no ancestors/descendants in mempool”.

~~This is a subset of #12257.~~

fanquake added the label Refactoring on Mar 7, 2018

in src/txmempool.cpp:1058 in 667592e1b6 outdated

1054@@ -1055,11 +1055,10 @@ void CTxMemPool::TrimToSize(size_t sizelimit, std::vector<COutPoint>* pvNoSpends
1055     }
1056 }
1057 
1058-bool CTxMemPool::TransactionWithinChainLimit(const uint256& txid, size_t chainLimit) const {
1059+int64_t CTxMemPool::chain_limit_value(const uint256& txid) const {

promag commented at 6:20 pm on March 7, 2018:

Snake case is for variables.

kallewoof commented at 6:35 pm on March 7, 2018:

It seems like we are moving to snake case, e.g. for new code like

https://github.com/bitcoin/bitcoin/blob/a34ac6ae0788b50e12dd2c8ac59dbda2a03a3c2e/src/cuckoocache.h#L92

Maybe I’m mistaken on that one. Will check recent merges.

promag commented at 7:25 pm on March 7, 2018:

From the developer notes:

Variable and namespace names are all lowercase, and may use _ to separate words (snake_case).
Class names, function names and method names are UpperCamelCase (PascalCase).

kallewoof commented at 3:42 pm on March 8, 2018:

Wow, okay. I totally missed that, thanks!

kallewoof commented at 4:37 pm on March 8, 2018:

Fixed.

in src/txmempool.h:623 in 667592e1b6 outdated

618@@ -619,8 +619,10 @@ class CTxMemPool
619     /** Expire all transaction (and their dependencies) in the mempool older than time. Return the number of removed transactions. */
620     int Expire(int64_t time);
621 
622-    /** Returns false if the transaction is in the mempool and not within the chain limit specified. */
623-    bool TransactionWithinChainLimit(const uint256& txid, size_t chainLimit) const;
624+    /** Get the maximum of the chain limit value in the mempool of the given transaction.
625+      * If the transaction is not in the mempool, -1 is returned.

promag commented at 6:25 pm on March 7, 2018:

If not in the mempool could return 0 since GetCountWithAncestors and GetCountWithDescendants are always > 0 (self is counted). In that case you can revert s/uint64_t/int64_t.

NicolasDorier commented at 7:33 pm on March 7, 2018:

I looked in the code and it seems to me they can be both 0 and that self is not counted.

promag commented at 7:52 pm on March 7, 2018:

@NicolasDorier have you checked these? https://github.com/bitcoin/bitcoin/blob/a34ac6ae0788b50e12dd2c8ac59dbda2a03a3c2e/src/txmempool.cpp#L30 https://github.com/bitcoin/bitcoin/blob/a34ac6ae0788b50e12dd2c8ac59dbda2a03a3c2e/src/txmempool.cpp#L36 https://github.com/bitcoin/bitcoin/blob/a34ac6ae0788b50e12dd2c8ac59dbda2a03a3c2e/src/txmempool.cpp#L317 https://github.com/bitcoin/bitcoin/blob/a34ac6ae0788b50e12dd2c8ac59dbda2a03a3c2e/src/txmempool.cpp#L326

NicolasDorier commented at 9:07 pm on March 7, 2018:

woops, completely missed that indeed. I failed to notice how the clients were forcing this invariant though.

NicolasDorier commented at 9:11 pm on March 7, 2018:

Got confused when I saw that which seemed to me it could be 0.

kallewoof commented at 3:43 pm on March 8, 2018:

I made the change for a reason but that reason may have been flawed. I’ll try it with uint64_t and 0 again. Thanks!

kallewoof commented at 5:08 pm on March 8, 2018:

The thing is, the check in SelectCoinsMinConf checks if the chain limit value >= nMaxAncestors, which is 0 for no chained ancestors in the code. With the old method, this would be true, but with a 0 returned, it would be false.

I could change the 0 to a 1 to fix it, which may be a better solution here, and is probably what I will end up doing.

kallewoof commented at 5:14 pm on March 8, 2018:

If I do that, the semantics becomes misleading. It says ‘max ancestors’ so 1 makes it sound like it allows 1 ancestor or descendant, when in reality it only counts itself. I’m gonna keep the change to signed, for now.

NicolasDorier commented at 6:32 pm on March 8, 2018:

Indeed, now:

with @promag suggestion, if nMaxAncestors==0 and the tx is not in mempool then mempool.ChainLimitValue(pcoin->GetHash()) >= nMaxAncestors evaluate to true.

While before !mempool.TransactionWithinChainLimit(pcoin->GetHash(), nMaxAncestors) evaluate to false.

promag commented at 6:28 pm on March 7, 2018: member

which is different from “0”, which means “no ancestors/descendants in mempool”.

I believe “1” means “no ancestors/descendants in mempool”.

kallewoof force-pushed on Mar 8, 2018

NicolasDorier commented at 6:33 pm on March 8, 2018: contributor

utACK b0928df

kallewoof force-pushed on Mar 15, 2018

kallewoof force-pushed on Apr 3, 2018

kallewoof force-pushed on Apr 4, 2018

kallewoof force-pushed on May 9, 2018

fanquake added this to the "Blockers" column in a project

promag commented at 1:32 pm on May 15, 2018: member

utACK 8154223.

jimpo commented at 10:29 pm on May 18, 2018: contributor

I find this whole thing unnecessarily confusing. Not your change in particular, more how the code works today.

There are two separate config limits, -limitancestorcount and -limitdescendantcount, which are treated as the same and merged into a single limit nMaxChainLength. Then that value is compared against both the ancestor count and descendant count of the transaction containing the candidate output. So first, it seems like there should be a separate max_descendants field on EligibilityFilter.

But further, the descendants check isn’t even right: the documentation says “Do not accept transactions if any ancestor would have or more in-mempool descendants”. So the descendants check really needs to check the descendants count on all ancestors, not just the direct parent.

Regardless of all that, even just looking at the ancestors limit, which is easier to check, I think it should not be a strict equality check, whereas it is currently in the code. If trying to spend an output from a transaction with 3 ancestors, the spending transaction would have 4 ancestors. Say the ancestor limit is 3. The code currently would call that spend ineligible because GetCountWithAncestors returns 3, and there is a strict < check, whereas the spend should be allowed because the ancestor count is not above the limit. So that is to say TransactionLimitValue can return 0 on the case where the tx is not in the mempool.

kallewoof commented at 1:44 am on May 19, 2018: member

@jimpo Yeah it’s not entirely straightforward that’s for sure, and I think further consideration should be given. I don’t think this PR makes the situation worse, though.

jimpo commented at 5:42 pm on May 19, 2018: contributor

Well, I think it does make things worse because it formalizes the concept of a chain_limit_value, which is a broken concept. If such a value were useful, it should really be two things, the count of ancestors and the max count of descendants of any ancestor. But furthermore, to calculate them (especially the latter), it’s helpful to have an explicit limit on the depth of recursive searching, which is why they are passed into the mempool function rather than returned from it. To see what I mean, see CalculateMemPoolAncestors, which implements this sort of checking.

fanquake removed this from the "Blockers" column in a project

kallewoof commented at 0:43 am on May 21, 2018: member

@jimpo Thanks for spelling it out. To summarize:

The max ancestors and max descendants stuff is needlessly complex and can be simplified.
It is also broken.
It can be replaced with a single value (e.g. max descendants) that checks the descendant count of the top parent in the mempool.

Does that seem accurate?

kallewoof commented at 2:02 am on May 21, 2018: member

Delving into this a bit further, the ascendant vs descendant thing is quite different. There’s usually only one ascendant per transaction except if several transactions were merged together, while there can be a tree of transactions as descendants.

I’m wondering if this should instead be “max unconfirmed group size”, and default to the sum of the default values for max descendants/ascendants.

kallewoof commented at 2:08 am on May 21, 2018: member

Actually, I think the more straightforward fix here is to fix ~~the description of max descendants~~ the max descendants check, and to add it to the eligibility filter.

This PR can then be rewritten to take both max ancestors and max descendants. That would address your concerns, right?

kallewoof force-pushed on May 21, 2018

kallewoof commented at 4:06 am on May 21, 2018: member

@jimpo

2d8748b adds a max_descendants to the eligibility class and uses it in the eligibility method in coin selection
4e742ba addresses the max descendants check to iterate over parents and using the top parent’s descendant count. This is not exact, because a tx with multiple parents in the mempool will pick one of them and only use its values, but it’s better than what we are doing right now.

Would you mind checking that out and seeing if it looks okay to you?

kallewoof force-pushed on May 21, 2018

in src/txmempool.cpp:1075 in d8864ab573 outdated

1073-    return it == mapTx.end() || (it->GetCountWithAncestors() < chainLimit &&
1074-       it->GetCountWithDescendants() < chainLimit);
1075+    ancestors = descendants = -1;
1076+    if (it != mapTx.end()) {
1077+        ancestors = it->GetCountWithAncestors();
1078+        descendants = (int64_t)CalculateDescendantMaximum(it);

Empact commented at 7:43 am on May 21, 2018:

Maybe add some bounds-checking asserts here ala assert(int64_t(nCountWithDescendants) > 0);

kallewoof commented at 11:36 pm on May 21, 2018:

I’m going to switch back to unsigned, so no need.

in src/wallet/wallet.cpp:2472 in 33eca3e0ea outdated

2466@@ -2467,8 +2467,11 @@ bool CWallet::OutputEligibleForSpending(const COutput& output, const CoinEligibi
2467     if (output.nDepth < (output.tx->IsFromMe(ISMINE_ALL) ? eligibility_filter.conf_mine : eligibility_filter.conf_theirs))
2468         return false;
2469 
2470-    if (!mempool.TransactionWithinChainLimit(output.tx->GetHash(), eligibility_filter.max_ancestors, eligibility_filter.max_descendants))
2471+    int64_t ancestors, descendants;
2472+    mempool.GetTransactionAncestry(output.tx->GetHash(), ancestors, descendants);
2473+    if (ancestors >= eligibility_filter.max_ancestors || descendants >= eligibility_filter.max_descendants) {

jimpo commented at 3:51 pm on May 21, 2018:

commit: Switch to GetTransactionAncestry() in OutputEligibleForSpending

I think these should be strict > checks, in which case you don’t need to switch to signed results. This makes sense logically because ancestors and descendants counts includes the transaction queried, so if the count is at the maximum allowable, it is still valid to create one more in the chain.

kallewoof commented at 11:35 pm on May 21, 2018:

It means having to change the parameter for all the calls (bump by 1), but I think you’re right. The -1 hack is bad. Fixing.

kallewoof commented at 2:15 am on May 22, 2018:

I had to do one minor tweak, but otherwise the current values worked even with the change. I also switched from nMaxChainLength to using max_ancestors and max_descendants with their corresponding defaults. (See 6ab847bce76224ff46552dd647b542fa70350a91.)

in src/txmempool.cpp:1064 in 4e742baf11 outdated

1059+    // find top parent
1060+    txiter top = entry;
1061+    for (;;) {
1062+        const setEntries& parents = GetMemPoolParents(top);
1063+        if (parents.size() == 0) break;
1064+        top = *parents.begin();

jimpo commented at 3:54 pm on May 21, 2018:

commit: mempool: Fix max descendants check

You actually need to recurse down all parents and take the max GetCountWithDescendants of all ancestors. A transaction can have multiple chains of ancestry with different descendants counts. This is also why it kind of makes sense to take the descendants limit as a parameter to this method rather than (or in addition to) returning it – because it can limit the recursion.

kallewoof commented at 11:35 pm on May 21, 2018:

I was afraid that would be too resource intensive and potential for DoS. Doing a ‘depth first optimistic pass’ seemed like a good estimate.

jimpo commented at 7:42 pm on May 22, 2018:

Hmm, I understand the concern, but this doesn’t match the advertised behavior of the flag. Also, the ancestor limit can be used to limit the depth of recursion. I’d like some more opinions on this.

kallewoof commented at 0:14 am on May 23, 2018:

After thinking about it for a bit, I am not convinced it’s particularly DoS vulnerable. I pushed a commit (to squash) that calculates it the way it is advertised.

jimpo commented at 3:55 pm on May 21, 2018: contributor

Definitely a big step in the right direction.

kallewoof force-pushed on May 22, 2018

in src/wallet/wallet.cpp:2595 in 2e5606f198 outdated

2591@@ -2592,7 +2592,7 @@ bool CWallet::SelectCoins(const std::vector<COutput>& vAvailableCoins, const CAm
2592         (m_spend_zero_conf_change && SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, CoinEligibilityFilter(0, 1, 2), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) ||
2593         (m_spend_zero_conf_change && SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, CoinEligibilityFilter(0, 1, std::min((size_t)4, nMaxChainLength/3)), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) ||
2594         (m_spend_zero_conf_change && SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, CoinEligibilityFilter(0, 1, nMaxChainLength/2), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) ||
2595-        (m_spend_zero_conf_change && SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, CoinEligibilityFilter(0, 1, nMaxChainLength), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) ||
2596+        (m_spend_zero_conf_change && SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, CoinEligibilityFilter(0, 1, nMaxChainLength-1), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) ||

jimpo commented at 7:34 pm on May 22, 2018:

This underflows if nMaxChainLength is 0.

kallewoof commented at 11:38 pm on May 22, 2018:

Fixed (I set nMaxChainLength to std::max(1, ...)).

in src/wallet/wallet.cpp:2598 in d9b765b2b0 outdated

2595-        (m_spend_zero_conf_change && SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, CoinEligibilityFilter(0, 1, std::min((size_t)4, nMaxChainLength/3)), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) ||
2596-        (m_spend_zero_conf_change && SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, CoinEligibilityFilter(0, 1, nMaxChainLength/2), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) ||
2597-        (m_spend_zero_conf_change && SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, CoinEligibilityFilter(0, 1, nMaxChainLength-1), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) ||
2598+        (m_spend_zero_conf_change && SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, CoinEligibilityFilter(0, 1, std::min((size_t)4, max_ancestors/3), std::min((size_t)4, max_descendants/3)), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) ||
2599+        (m_spend_zero_conf_change && SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, CoinEligibilityFilter(0, 1, max_ancestors/2, max_descendants/2), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) ||
2600+        (m_spend_zero_conf_change && SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, CoinEligibilityFilter(0, 1, max_ancestors-1, max_descendants-1), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) ||

jimpo commented at 7:38 pm on May 22, 2018:

This underflows if max_ancestors or max_descendants is 0.

kallewoof commented at 11:38 pm on May 22, 2018:

Fixed (set both to std::max(1, ...)).

kallewoof force-pushed on May 22, 2018

ryanofsky commented at 6:05 pm on May 23, 2018: member

From https://botbot.me/freenode/bitcoin-core-dev/msg/100337736/ on motivation for this change:

<kallewoof> When doing coin selection on groups rather than individual outputs, the ancestor/descendant stuff becomes rather messy if you don’t unify them to their corresponding maximums. In order to do that, you need the values, since they are tested against multiple limits.

jimpo commented at 6:03 am on May 24, 2018: contributor

utACK 6e56fef. Would be nice to have a unit test for CTxMemPool::GetTransactionAncestry though. :-)

kallewoof commented at 9:52 am on May 24, 2018: member

@jimpo I added tests in fcf1ed7 – it would be great if you could check that the expected values matches what you would expect (checking the very last test is probably quickest, as each test simply builds on the previous one).

sdaftuar commented at 12:50 pm on May 24, 2018: member

@kallewoof Sorry I missed you on IRC, but thanks for responding.

When doing coin selection on groups rather than individual outputs, the ancestor/descendant stuff becomes rather messy if you don’t unify them to their corresponding maximums. In order to do that, you need the values, since they are tested against multiple limits.

I guess I don’t understand how this relates because at first thought, I would have assumed that the only time we’re spending unconfirmed outputs in the coin selection logic is if we are spending our own unconfirmed change, where address re-use (and therefore the grouping logic being introduced in #12257) should not be an issue at all. Is there a case I’m overlooking?

kallewoof commented at 4:04 am on May 25, 2018: member

@sdaftuar Yes, I think most of the time the unspent trusted outputs will be your own and will probably not do address reuse, but I don’t think it’s guaranteed to always be that way.

Either way, once the coin selection is done per-group rather than per-output, it has to either iterate over all the outputs and check the limits each time, or it can cache it by storing the ancestry in the group struct itself. The latter seems like a more efficient solution and is enabled by this PR.

laanwj added this to the "Blockers" column in a project

jimpo commented at 7:05 pm on May 30, 2018: contributor

ACK e39efa8c9da85737393ca93bcda711774115702c

kallewoof force-pushed on May 31, 2018

kallewoof commented at 4:33 am on May 31, 2018: member

Squashed fix-commits into 5ad55d2.

mempool: Add explicit max_descendants

TransactionWithinChainLimits would take a 'limit' and check it against ascendants and descendants. This is changed to take an explicit
max ancestors and max descendants value, and to test the corresponding value against its corresponding max.

b9ef21dd72

mempool: Fix max descendants check

The chain limits check for max descendants would check the descendants of the transaction itself even though the description for -limitdescendantcount says 'any ancestor'. This commit corrects the descendant count check by finding the top parent transaction in the mempool and comparing against that.

46847d69d2

Add GetTransactionAncestry to CTxMemPool for general purpose chain limit checking 475a385a80

Switch to GetTransactionAncestry() in OutputEligibleForSpending 4784751547

Remove deprecated TransactionWithinChainLimit 322b12ac4e

wallet: Strictly greater than for ancestor caps 6888195b06

wallet: Switch to using ancestor/descendant limits

Instead of combining the -limitancestorcount and -limitdescendantcount into a nMaxChainLength, this commit uses each one separately in the coin eligibility filters.

6d3568371e

in src/test/mempool_tests.cpp:583 in 5ad55d23d6 outdated

578+    tx.vout.resize(output_values.size());
579+    for (size_t i = 0; i < inputs.size(); ++i) {
580+        tx.vin[i].prevout.hash = inputs[i]->GetHash();
581+        tx.vin[i].prevout.n = input_indices.size() > i ? input_indices[i] : 0;
582+    }
583+    for (size_t i = 0; i < output_values.size(); i++) {

Empact commented at 10:01 am on June 11, 2018:

nit: ++i

in src/txmempool.cpp:1068 in 5ad55d23d6 outdated

1064+    uint64_t maximum = 0;
1065+    while (candidates.size()) {
1066+        txiter candidate = candidates.back();
1067+        candidates.pop_back();
1068+        if (counted.find(candidate) != counted.end()) continue;
1069+        counted.insert(candidate);

Empact commented at 10:05 am on June 11, 2018:

nit: should be faster if you read the return value from the insertion, rather than find & insert.

kallewoof commented at 10:08 am on June 11, 2018:

Didn’t realize set::insert told you if the insertion happened. Nice!

kallewoof force-pushed on Jun 11, 2018

mempool: Calculate descendant maximum thoroughly a08d76bcfe

test: Add MempoolAncestryTests f77e1d34fd

kallewoof force-pushed on Jun 11, 2018

in src/txmempool.cpp:1060 in f77e1d34fd

1054@@ -1055,11 +1055,36 @@ void CTxMemPool::TrimToSize(size_t sizelimit, std::vector<COutPoint>* pvNoSpends
1055     }
1056 }
1057 
1058-bool CTxMemPool::TransactionWithinChainLimit(const uint256& txid, size_t chainLimit) const {
1059+uint64_t CTxMemPool::CalculateDescendantMaximum(txiter entry) const {
1060+    // find parent with highest descendant count
1061+    std::vector<txiter> candidates;

Empact commented at 10:32 am on June 11, 2018:

nit: more true to form to use a std::stack here, although I see they’re not used otherwise in the codebase fwiw.

promag commented at 10:42 am on June 11, 2018:

nit,

0std::vector<txiter> candidates = {entry};

and remove push_back below.

Empact commented at 10:37 am on June 11, 2018: member

utACK f77e1d3

in src/txmempool.cpp:1058 in f77e1d34fd

1054@@ -1055,11 +1055,36 @@ void CTxMemPool::TrimToSize(size_t sizelimit, std::vector<COutPoint>* pvNoSpends
1055     }
1056 }
1057 
1058-bool CTxMemPool::TransactionWithinChainLimit(const uint256& txid, size_t chainLimit) const {
1059+uint64_t CTxMemPool::CalculateDescendantMaximum(txiter entry) const {

promag commented at 10:55 am on June 11, 2018:

nit const txiter& entry.

promag commented at 10:55 am on June 11, 2018: member

utACK f77e1d3.

laanwj commented at 2:25 pm on June 11, 2018: member

utACK f77e1d34fd5f17304ce319b5f962b8005592501a

I’m going to ignore last-minute nits here, sorry. This has too many reviews to hold it up on nits.

laanwj merged this on Jun 11, 2018

laanwj closed this on Jun 11, 2018

laanwj referenced this in commit 43ae5ee9e4 on Jun 11, 2018

MarcoFalke removed this from the "Blockers" column in a project

sdaftuar commented at 3:01 pm on June 11, 2018: member

Sorry I haven’t dug into this change myself, but might this have a material performance impact on wallets with many unconfirmed coins, if the mempool is full?

kallewoof deleted the branch on Jun 11, 2018

kallewoof commented at 4:03 pm on June 11, 2018: member

@sdaftuar I honestly doubt it, unless they have a TON of ancestors in the mempool. I was initially hesitant to make the ancestor check “thorough” but couldn’t come up with a reason why it would ever be the case that you have enough transactions in the mempool to make the ancestor check bog down your system significantly.

PastaPastaPasta referenced this in commit 688b0736b5 on Feb 2, 2021

PastaPastaPasta referenced this in commit a8863dc3b5 on Feb 4, 2021

MarcoFalke locked this on Sep 8, 2021

[refactor] Make TransactionWithinChainLimit more flexible #12634