[refactor] Make TransactionWithinChainLimit more flexible #12634

kallewoof · 2018-03-07T16:07:22Z

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.~~

promag

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

I believe "1" means "no ancestors/descendants in mempool".

promag · 2018-03-07T18:20:42Z

src/txmempool.cpp

Snake case is for variables.

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

bitcoin/src/cuckoocache.h

Line 92 in a34ac6a

inline void bit_set(uint32_t s)

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

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).

Wow, okay. I totally missed that, thanks!

promag · 2018-03-07T18:25:20Z

src/txmempool.h

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.

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

@NicolasDorier have you checked these?

bitcoin/src/txmempool.cpp

Line 30 in a34ac6a

nCountWithDescendants = 1;

bitcoin/src/txmempool.cpp

Line 36 in a34ac6a

nCountWithAncestors = 1;

bitcoin/src/txmempool.cpp

Line 317 in a34ac6a

assert(int64_t(nCountWithDescendants) > 0);

bitcoin/src/txmempool.cpp

Line 326 in a34ac6a

assert(int64_t(nCountWithAncestors) > 0);

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

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

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!

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.

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.

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.

NicolasDorier · 2018-03-08T18:33:08Z

utACK b0928df

promag · 2018-05-15T13:32:07Z

utACK 8154223.

jimpo · 2018-05-18T22:29:35Z

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 · 2018-05-19T01:44:47Z

@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 · 2018-05-19T17:42:33Z

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.

kallewoof · 2018-05-21T00:43:11Z

@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 · 2018-05-21T02:02:10Z

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 · 2018-05-21T02:08:15Z

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 · 2018-05-21T04:06:23Z

@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?

Empact · 2018-05-21T07:43:36Z

src/txmempool.cpp

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

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

jimpo

Definitely a big step in the right direction.

jimpo · 2018-05-21T15:51:51Z

src/wallet/wallet.cpp

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.

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.

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.)

jimpo · 2018-05-21T15:54:29Z

src/txmempool.cpp

+    for (;;) {
+        const setEntries& parents = GetMemPoolParents(top);
+        if (parents.size() == 0) break;
+        top = *parents.begin();


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.

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

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.

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 · 2018-05-22T19:34:06Z

src/wallet/wallet.cpp

This underflows if nMaxChainLength is 0.

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

jimpo · 2018-05-22T19:38:07Z

src/wallet/wallet.cpp

This underflows if max_ancestors or max_descendants is 0.

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

jimpo · 2018-05-22T19:42:01Z

src/txmempool.cpp

+    for (;;) {
+        const setEntries& parents = GetMemPoolParents(top);
+        if (parents.size() == 0) break;
+        top = *parents.begin();


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.

ryanofsky · 2018-05-23T18:05:15Z

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 · 2018-05-30T19:05:52Z

ACK e39efa8c9da85737393ca93bcda711774115702c

kallewoof · 2018-05-31T04:33:59Z

Squashed fix-commits into 5ad55d2.

Empact · 2018-06-11T10:01:23Z

src/test/mempool_tests.cpp

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.

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.

…mit checking

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

Empact · 2018-06-11T10:05:47Z

src/txmempool.cpp

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

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

Empact · 2018-06-11T10:32:01Z

src/txmempool.cpp

-bool CTxMemPool::TransactionWithinChainLimit(const uint256& txid, size_t chainLimit) const {
+uint64_t CTxMemPool::CalculateDescendantMaximum(txiter entry) const {
+    // find parent with highest descendant count
+    std::vector<txiter> candidates;


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

nit,

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

and remove push_back below.

Empact · 2018-06-11T10:37:12Z

utACK f77e1d3

promag

utACK f77e1d3.

promag · 2018-06-11T10:42:28Z

src/txmempool.cpp

-bool CTxMemPool::TransactionWithinChainLimit(const uint256& txid, size_t chainLimit) const {
+uint64_t CTxMemPool::CalculateDescendantMaximum(txiter entry) const {
+    // find parent with highest descendant count
+    std::vector<txiter> candidates;


nit,

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

and remove push_back below.

promag · 2018-06-11T10:55:02Z

src/txmempool.cpp

 }

-bool CTxMemPool::TransactionWithinChainLimit(const uint256& txid, size_t chainLimit) const {
+uint64_t CTxMemPool::CalculateDescendantMaximum(txiter entry) const {


nit const txiter& entry.

laanwj · 2018-06-11T14:25:40Z

utACK f77e1d3

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

f77e1d3 test: Add MempoolAncestryTests (Karl-Johan Alm) a08d76b mempool: Calculate descendant maximum thoroughly (Karl-Johan Alm) 6d35683 wallet: Switch to using ancestor/descendant limits (Karl-Johan Alm) 6888195 wallet: Strictly greater than for ancestor caps (Karl-Johan Alm) 322b12a Remove deprecated TransactionWithinChainLimit (Karl-Johan Alm) 4784751 Switch to GetTransactionAncestry() in OutputEligibleForSpending (Karl-Johan Alm) 475a385 Add GetTransactionAncestry to CTxMemPool for general purpose chain limit checking (Karl-Johan Alm) 46847d6 mempool: Fix max descendants check (Karl-Johan Alm) b9ef21d mempool: Add explicit max_descendants (Karl-Johan Alm) Pull request description: 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.~~ Tree-SHA512: aa59c849360542362b3126c0e29d44d3d58f11898e277d38c034dc4b86a5b4500f77ac61767599ce878c876b5c446fec9c02699797eb2fa41e530ec863a00cf9

sdaftuar · 2018-06-11T15:01:55Z

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 · 2018-06-11T16:03:47Z

@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.

… flexible f77e1d3 test: Add MempoolAncestryTests (Karl-Johan Alm) a08d76b mempool: Calculate descendant maximum thoroughly (Karl-Johan Alm) 6d35683 wallet: Switch to using ancestor/descendant limits (Karl-Johan Alm) 6888195 wallet: Strictly greater than for ancestor caps (Karl-Johan Alm) 322b12a Remove deprecated TransactionWithinChainLimit (Karl-Johan Alm) 4784751 Switch to GetTransactionAncestry() in OutputEligibleForSpending (Karl-Johan Alm) 475a385 Add GetTransactionAncestry to CTxMemPool for general purpose chain limit checking (Karl-Johan Alm) 46847d6 mempool: Fix max descendants check (Karl-Johan Alm) b9ef21d mempool: Add explicit max_descendants (Karl-Johan Alm) Pull request description: 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. bitcoin#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 bitcoin#12257.~~ Tree-SHA512: aa59c849360542362b3126c0e29d44d3d58f11898e277d38c034dc4b86a5b4500f77ac61767599ce878c876b5c446fec9c02699797eb2fa41e530ec863a00cf9

fanquake added the Refactoring label Mar 7, 2018

kallewoof mentioned this pull request Mar 7, 2018

[wallet] Use destination groups instead of coins in coin select #12257

Merged

promag reviewed Mar 7, 2018

View reviewed changes

kallewoof force-pushed the txmempool-chain-limit-value branch 3 times, most recently from 667592e to b0928df Compare March 8, 2018 17:16

kallewoof force-pushed the txmempool-chain-limit-value branch from b0928df to 8a32f56 Compare March 15, 2018 10:20

kallewoof force-pushed the txmempool-chain-limit-value branch 2 times, most recently from 38fd625 to 06a937a Compare April 4, 2018 08:15

kallewoof force-pushed the txmempool-chain-limit-value branch from 06a937a to 8154223 Compare May 9, 2018 08:20

kallewoof force-pushed the txmempool-chain-limit-value branch from 8154223 to d120f0d Compare May 21, 2018 04:03

kallewoof force-pushed the txmempool-chain-limit-value branch from d120f0d to d8864ab Compare May 21, 2018 04:17

Empact reviewed May 21, 2018

View reviewed changes

jimpo reviewed May 21, 2018

View reviewed changes

kallewoof force-pushed the txmempool-chain-limit-value branch 4 times, most recently from d1a2f21 to d9b765b Compare May 22, 2018 02:22

jimpo reviewed May 22, 2018

View reviewed changes

kallewoof force-pushed the txmempool-chain-limit-value branch from d9b765b to cde1022 Compare May 22, 2018 23:45

kallewoof force-pushed the txmempool-chain-limit-value branch from e39efa8 to 5ad55d2 Compare May 31, 2018 04:33

Empact reviewed Jun 11, 2018

View reviewed changes

src/test/mempool_tests.cpp Outdated

Copy link

Contributor

Empact Jun 11, 2018

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

nit: ++i

kallewoof reacted with thumbs up emoji

kallewoof added 7 commits June 11, 2018 19:04

mempool: Add explicit max_descendants

b9ef21d

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.

Add GetTransactionAncestry to CTxMemPool for general purpose chain li…

475a385

…mit checking

Switch to GetTransactionAncestry() in OutputEligibleForSpending

4784751

Remove deprecated TransactionWithinChainLimit

322b12a

wallet: Strictly greater than for ancestor caps

6888195

wallet: Switch to using ancestor/descendant limits

6d35683

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

Empact reviewed Jun 11, 2018

View reviewed changes

kallewoof force-pushed the txmempool-chain-limit-value branch from 5ad55d2 to 6c47fb2 Compare June 11, 2018 10:06

kallewoof added 2 commits June 11, 2018 19:09

mempool: Calculate descendant maximum thoroughly

a08d76b

test: Add MempoolAncestryTests

f77e1d3

kallewoof force-pushed the txmempool-chain-limit-value branch from 6c47fb2 to f77e1d3 Compare June 11, 2018 10:16

Empact reviewed Jun 11, 2018

View reviewed changes

promag reviewed Jun 11, 2018

View reviewed changes

laanwj merged commit f77e1d3 into bitcoin:master Jun 11, 2018

kallewoof deleted the txmempool-chain-limit-value branch June 11, 2018 16:02

Bushstar mentioned this pull request Jun 12, 2018

commits from bitcoin/master FeatherCoin/Feathercoin#343

Merged

ryanofsky mentioned this pull request Jun 26, 2018

Refactor: separate wallet from node #10973

Merged

bitcoin locked as resolved and limited conversation to collaborators Sep 8, 2021

[refactor] Make TransactionWithinChainLimit more flexible #12634

[refactor] Make TransactionWithinChainLimit more flexible #12634

Uh oh!

Conversation

kallewoof commented Mar 7, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

promag left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

promag Mar 7, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

NicolasDorier commented Mar 8, 2018

Uh oh!

promag commented May 15, 2018

Uh oh!

jimpo commented May 18, 2018

Uh oh!

kallewoof commented May 19, 2018

Uh oh!

jimpo commented May 19, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

kallewoof commented May 21, 2018

Uh oh!

kallewoof commented May 21, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

kallewoof commented May 21, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

kallewoof commented May 21, 2018

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

jimpo left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

kallewoof commented Mar 7, 2018 •

edited

Loading

promag Mar 7, 2018 •

edited

Loading

jimpo commented May 19, 2018 •

edited

Loading

kallewoof commented May 21, 2018 •

edited

Loading

kallewoof commented May 21, 2018 •

edited

Loading

jimpo left a comment •

edited

Loading