wallet: Make IsTrusted scan parents recursively

JeremyRubin commented at 7:45 pm on August 30, 2019: contributor

This slightly modifies the behavior of IsTrusted to recursively check the parents of a transaction. Otherwise, it’s possible that a parent is not IsTrusted but a child is. If a parent is not trusted, then a child should not be either.

This recursive scan can be a little expensive, so ~~it might be beneficial to have a way of caching IsTrusted state, but this is a little complex because various conditions can change between calls to IsTrusted (e.g., re-org).~~ I added a cache which works per call/across calls, but does not store the results semi-permanently. Which reduces DoS risk of this change. There is no risk of untrusted parents causing a resource exploitation, as we immediately return once that is detected.

This is a change that came up as a bug-fix esque change while working on OP_SECURETHEBAG. You can see the branch where this change is important here: https://github.com/bitcoin/bitcoin/compare/master...JeremyRubin:stb-with-rpc?expand=1. Essentially, without this change, we can be tricked into accepting an OP_SECURETHEBAG output because we don’t properly check the parents. As this was a change which, on its own, was not dependent on OP_SECURETHEBAG, I broke it out as I felt the change stands on its own by fixing a long standing wallet bug.

The test wallet_balance.py has been corrected to meet the new behavior. The below comment, reproduced, explains what the issue is and the edge cases that can arise before this change.

    # Before `test_balance()`, we have had two nodes with a balance of 50
    # each and then we:
    #
    # 1) Sent 40 from node A to node B with fee 0.01
    # 2) Sent 60 from node B to node A with fee 0.01
    #
    # Then we check the balances:
    #
    # 1) As is
    # 2) With transaction 2 from above with 2x the fee
    #
    # Prior to [#16766](/bitcoin-bitcoin/16766/), in this situation, the node would immediately report
    # a balance of 30 on node B as unconfirmed and trusted.
    #
    # After [#16766](/bitcoin-bitcoin/16766/), we show that balance as unconfirmed.
    #
    # The balance is indeed "trusted" and "confirmed" insofar as removing
    # the mempool transactions would return at least that much money. But
    # the algorithm after [#16766](/bitcoin-bitcoin/16766/) marks it as unconfirmed because the 'taint'
    # tracking of transaction trust for summing balances doesn't consider
    # which inputs belong to a user. In this case, the change output in
    # question could be "destroyed" by replace the 1st transaction above.
    #
    # The post [#16766](/bitcoin-bitcoin/16766/) behavior is correct; we shouldn't be treating those
    # funds as confirmed. If you want to rely on that specific UTXO existing
    # which has given you that balance, you cannot, as a third party
    # spending the other input would destroy that unconfirmed.
    #
    # For example, if the test transactions were:
    #
    # 1) Sent 40 from node A to node B with fee 0.01
    # 2) Sent 10 from node B to node A with fee 0.01
    #
    # Then our node would report a confirmed balance of 40 + 50 - 10 = 80
    # BTC, which is more than would be available if transaction 1 were
    # replaced.

The release notes have been updated to note the new behavior.

DrahtBot added the label Wallet on Aug 30, 2019

JeremyRubin commented at 8:37 pm on August 30, 2019: contributor

I added a cache which works per call/across calls, but does not store the results semi-permanently.

This should reduce DoS risk of this change.

There is no risk of untrusted parents causing a resource exploitation, as we immediately return once that is detected.

DrahtBot commented at 10:33 pm on August 30, 2019: member

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#15931 (Remove GetDepthInMainChain dependency on locked chain interface by ariard)
#15729 (rpc: Raise error in getbalance if minconf is not zero by promag)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

MarcoFalke renamed this:
~~Make IsTrusted scan parents recursively~~
wallet: Make IsTrusted scan parents recursively
on Sep 3, 2019

MarcoFalke commented at 3:48 pm on September 3, 2019: member

If a parent is not trusted, then a child should not be either.

Would be nice to have a test for this or update the wallet_balance.py script in case it is already tested there. (wallet_balance.py is failing)

JeremyRubin commented at 5:42 pm on September 3, 2019: contributor

I updated the tests to pass.

In the test, we have two nodes with a balance of 50 each and then:

Send 40 from node A to node B. Send 60 from node B to node A.

Then we would check the balances.

Previously, we would immediately report a balance of 30 on node B as unconfirmed and trusted.

Now, we show that balance as unconfirmed.

The balance is indeed “trusted” and “confirmed” insofar as removing the mempool transactions would return at least that much money. But the current software marks it as unconfirmed because the ’taint’ tracking of transaction trust for summing balances doesn’t consider which inputs belong to a user.

I think the new behavior is correct; we shouldn’t be treating those funds as confirmed. If you want to rely on that specific UTXO existing which has given you that balance, you cannot, as a third party spending the other input would destroy that unconfirmed.

Overall I think that this points to a general concept worth exploring as a revision to the categories “unconfirmed” and “confirmed”, to have “free cash”, “locked”, and “unconfirmed”. Free cash can be spent at will, locked funds are balances that are guaranteed to exist but we don’t have a confirmed UTXO for yet, and unconfirmed are funds we may or may not receive. I think this is out of scope of this PR though, but is worth further thought.

in test/functional/wallet_balance.py:115 in bee1dc9f8a outdated

111@@ -112,10 +112,10 @@ def run_test(self):
112         def test_balances(*, fee_node_1=0):
113             # getbalance without any arguments includes unconfirmed transactions, but not untrusted transactions
114             assert_equal(self.nodes[0].getbalance(), Decimal('9.99'))  # change from node 0's send
115-            assert_equal(self.nodes[1].getbalance(), Decimal('30') - fee_node_1)  # change from node 1's send
116+            assert_equal(self.nodes[1].getbalance(), Decimal('0'))  # change from node 1's send

MarcoFalke commented at 7:16 pm on September 3, 2019:

0            assert_equal(self.nodes[1].getbalance(), Decimal('0'))  # node 1's send had an unsafe input

MarcoFalke commented at 7:17 pm on September 3, 2019: member

Concept ACK

JeremyRubin commented at 6:47 pm on September 5, 2019: contributor

Test failure unrelated it seems? In assumevalid

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

jonatack commented at 8:05 pm on September 5, 2019: member

Concept ACK.

Test failure unrelated it seems? In assumevalid

Yup, just built and all tests are green.

in src/wallet/wallet.cpp:2428 in 07858cc41a outdated

2420@@ -2407,10 +2421,11 @@ CWallet::Balance CWallet::GetBalance(const int min_depth, bool avoid_reuse) cons
2421     {
2422         auto locked_chain = chain().lock();
2423         LOCK(cs_wallet);
2424+        std::set<uint256> trustedParents;
2425         for (const auto& entry : mapWallet)
2426         {
2427             const CWalletTx& wtx = entry.second;
2428-            const bool is_trusted{wtx.IsTrusted(*locked_chain)};
2429+            const bool is_trusted{wtx.IsTrusted(*locked_chain, trustedParents)};

promag commented at 11:47 pm on September 5, 2019:

With the overloaded IsTrusted this could be reverted? Same below.

JeremyRubin commented at 2:52 am on September 6, 2019:

Nope – because I’m caching the trust across the entire wallet (outside the loop) rather than just a single call.

promag commented at 4:50 pm on September 6, 2019:

Right, missed this is in a loop 🤦‍♂

in src/wallet/wallet.cpp:2334 in 07858cc41a outdated

2325@@ -2320,8 +2326,16 @@ bool CWalletTx::IsTrusted(interfaces::Chain::Lock& locked_chain) const
2326         if (parent == nullptr)
2327             return false;
2328         const CTxOut& parentOut = parent->tx->vout[txin.prevout.n];
2329+        // Check that this specific input being spent is trusted
2330         if (pwallet->IsMine(parentOut) != ISMINE_SPENDABLE)
2331             return false;
2332+        // If we've already trusted this parent, continue
2333+        if (trustedParents.count(parent->GetHash()))
2334+            continue;

promag commented at 11:51 pm on September 5, 2019:

nit, join with line above - to follow correct format.

JeremyRubin commented at 2:52 am on September 6, 2019:

Not sure what you mean

JeremyRubin commented at 4:25 pm on September 6, 2019:

got it; went ahead and did this in the entire function (rather than leave it half-styled)

promag commented at 4:51 pm on September 6, 2019:

Yup, that was the idea.

in src/wallet/wallet.cpp:2303 in 07858cc41a outdated

2294@@ -2295,6 +2295,12 @@ bool CWalletTx::InMempool() const
2295 }
2296 
2297 bool CWalletTx::IsTrusted(interfaces::Chain::Lock& locked_chain) const
2298+{
2299+    std::set<uint256> s;
2300+    return IsTrusted(locked_chain, s);
2301+}
2302+
2303+bool CWalletTx::IsTrusted(interfaces::Chain::Lock& locked_chain, std::set<uint256>& trustedParents) const

promag commented at 11:51 pm on September 5, 2019:

nit, snake case - header too.

JeremyRubin commented at 2:53 am on September 6, 2019:

Did we change styles?

sipa commented at 3:15 am on September 6, 2019:

We settled on a variable naming style in 2017: 47d84414662

promag commented at 4:52 pm on September 6, 2019: member

Do you expect a performance penalty for big wallets?

JeremyRubin commented at 5:26 pm on September 6, 2019: contributor

Yes and No.

Yes: A properly constructed wallet, which has long-chains of unconfirmed transactions, will take longer to analyze. However, given the use of the set cache it should still be linear in the number of long-chain inputs (this could be large if there are a ton of fully independent unconfirmeds being spent).

No: A normal wallet, and normal wallet transactions (who is confirmed or whose parents are all confirmed) won’t have much impact. Note we also abort as soon as we find an offending tx. It might be better to do this via BFS than DFS, but DFS is simpler to implement.

Note that a third party can’t force a long-chain lookup on you without your participation, because you’re checking IsMine at each level. So an unconfirmed spend to you will look back only until it’s a transaction with another participant that’s unconfirmed.

It’s also possible to use an unordered_set here – but perhaps that’s better done as something across the module (std::set/map is used extensively)

in src/wallet/wallet.cpp:2306 in 58cb227cc0 outdated

2305     // Quick answer in most cases
2306-    if (!locked_chain.checkFinalTx(*tx)) {
2307-        return false;
2308-    }
2309+    if (!locked_chain.checkFinalTx(*tx)) return false;
2310     int nDepth = GetDepthInMainChain(locked_chain);

promag commented at 11:42 am on September 13, 2019:

Maybe I’m missing something but I think you could avoid calling GetDepthInMainChain for parents if nDepth >= 1?

JeremyRubin commented at 6:18 am on September 14, 2019:

You’re right, but we already don’t recurse on trusted parents right?

promag commented at 6:21 am on September 14, 2019:

Doh!

in src/wallet/wallet.h:619 in 58cb227cc0 outdated

575@@ -576,6 +576,7 @@ class CWalletTx
576 
577     bool InMempool() const;
578     bool IsTrusted(interfaces::Chain::Lock& locked_chain) const;
579+    bool IsTrusted(interfaces::Chain::Lock& locked_chain, std::set<uint256>& trusted_parents) const;

promag commented at 11:44 am on September 13, 2019:

nit, should be private?

JeremyRubin commented at 6:02 pm on September 19, 2019:

Actually I’d rather just get rid of the other function as usually you’d want to share the cache across IsTrusted calls…

Slightly more agressive change but maybe it’s ok

in src/wallet/wallet.cpp:2325 in 58cb227cc0 outdated

2336-        if (pwallet->IsMine(parentOut) != ISMINE_SPENDABLE)
2337-            return false;
2338+        // Check that this specific input being spent is trusted
2339+        if (pwallet->IsMine(parentOut) != ISMINE_SPENDABLE) return false;
2340+        // If we've already trusted this parent, continue
2341+        if (trusted_parents.count(parent->GetHash())) continue;

promag commented at 11:51 am on September 13, 2019:

You could .insert() here, and use the result value .second to know whether it was missing and then call parent->IsTrusted.

JeremyRubin commented at 6:16 am on September 14, 2019:

I’m a little uncomfortable with that design because we then need to remove ourselves from the set if the recursion returns false.

It’s also a bit weird because we add ourselves to the trusted set before recursion so technically there are elements not known to be trusted in the set. This is safe because the element is a child, but it’s odd.

promag commented at 11:51 am on September 13, 2019: member

@JeremyRubin thanks for the detailed response! Some comments follow.

luke-jr commented at 9:41 pm on September 20, 2019: member

I think the new behavior is correct; we shouldn’t be treating those funds as confirmed. If you want to rely on that specific UTXO existing which has given you that balance, you cannot, as a third party spending the other input would destroy that unconfirmed.

But your balance isn’t specific UTXOs. Users don’t care about UTXOs, just total bitcoins.

30 BTC should show as confirmed and trusted…

JeremyRubin commented at 8:16 am on September 21, 2019: contributor

Then it’s a mistake to compute balance from summing IsTrusted, but we shouldn’t rely on broken IsTrusted behavior to compute Balance.

Bear in mind for the specific situation you’re thinking of, there are also edge cases where we over report correct balance.

fjahr commented at 8:40 am on October 1, 2019: member

Otherwise, it’s possible that a parent is not IsTrusted but a child is.

Was the test you changed a good example of how this can happen or did you have other examples in mind? Would it be worth to have an explicit test for that?

in src/wallet/wallet.cpp:2418 in 58cb227cc0 outdated

2411@@ -2407,10 +2412,11 @@ CWallet::Balance CWallet::GetBalance(const int min_depth, bool avoid_reuse) cons
2412     {
2413         auto locked_chain = chain().lock();
2414         LOCK(cs_wallet);
2415+        std::set<uint256> trusted_parents;
2416         for (const auto& entry : mapWallet)
2417         {
2418             const CWalletTx& wtx = entry.second;
2419-            const bool is_trusted{wtx.IsTrusted(*locked_chain)};
2420+            const bool is_trusted{wtx.IsTrusted(*locked_chain, trusted_parents)};

fjahr commented at 8:43 am on October 1, 2019:

nit: I would prefer to keep using the old interface here and in 2488, 3784 until the trusted_parents are actually used/shared.

JeremyRubin commented at 3:30 pm on October 1, 2019:

What do you mean by “actually used/shared”?

fjahr commented at 3:42 pm on October 1, 2019:

I mean for now, you could leave this line unchanged since trusted_parents is not used outside of IsTrusted. I know you eventually want to share the parents for optimization but I would not change this line until that is the case.

JeremyRubin commented at 4:15 pm on October 1, 2019:

I’m not sure what the “eventually” or “actually” part is… this is what is done by the code already. Note that trusted_parents lives outside the for loop so is shared across calls.

And it’s less so optimization and more so anti-DoS.

fjahr commented at 4:36 pm on October 1, 2019:

I see, I misunderstood at which level the caching is happening, thanks!

in test/functional/wallet_balance.py:150 in bee1dc9f8a outdated

111@@ -112,10 +112,10 @@ def run_test(self):
112         def test_balances(*, fee_node_1=0):

ryanofsky commented at 6:56 pm on October 21, 2019:

In commit “Update wallet_balance.py test to reflect new behavior” (bee1dc9f8a5182f03979fa066dc7937fc945bf29)

You also have a really nice description of the test setup in #16766 (comment) that could be nice to incorporate as a comment or link in the test_balances function.

ryanofsky approved

ryanofsky commented at 7:03 pm on October 21, 2019: member

Code review ACK 58cb227cc07f7f00ce91ec2fa903c343769f5524. This seems right. It doesn’t seem good to trust a child transaction if the parents aren’t trusted. But I don’t understand what originally motivated this change. Is there a prototypical example of a case where this would be an obvious improvement? The test example in #16766 (comment) seems more like arguably correct behavior with not a great outcome. I wouldn’t mind seeing:

The PR description updated with more motivation, and maybe a motivating example
A release note to warn users and avoid surprises from balances being computed differently than before

I like the proposed free/locked/unconfirmed idea, too. I hope future changes could allow figuring out a free+locked value, which has seemed to me like a useful thing to have before #15010 (comment).

JeremyRubin commented at 8:11 pm on October 21, 2019: contributor

Hi @ryanofsky, thanks for the review!

This is a change that came up as a bug-fix esque change while working on OP_SECURETHEBAG. You can see the branch where this change is important here: https://github.com/bitcoin/bitcoin/compare/master...JeremyRubin:stb-with-rpc?expand=1. Essentially, without this change, we can be tricked into accepting an OP_SECURETHEBAG output because we don’t properly check the parents.

As this was a change which, on its own, was not dependent on OP_SECURETHEBAG, I broke it out as I felt the change stands on its own.

I’ll add to the release notes and to the tests comments.

Make IsTrusted scan parents recursively dce032ce29

Cache tx Trust per-call to avoid DoS 595f09d6de

Reuse trustedParents in looped calls to IsTrusted 5dd7da4ccd

Update wallet_balance.py test to reflect new behavior a550c58267

Update comment in test/functional/wallet_balance.py

Co-Authored-By: MarcoFalke <falke.marco@gmail.com>

5ffe0d1449

update variable naming conventions for IsTrusted b49dcbedf7

Systematize style of IsTrusted single line if 8f174ef112

Update release notes to mention changes to IsTrusted and impact on wallet 91f3073f08

Expand on wallet_balance.py comment from https://github.com/bitcoin/bitcoin/pull/16766\#issuecomment-527563982 4671fc3d9e

JeremyRubin force-pushed on Oct 21, 2019

JeremyRubin commented at 8:51 pm on October 21, 2019: contributor

I had to rebase to clear out the release notes; code hasn’t changed except the comment in wallet_balances.py. I have also updated the PR message.

re-ack when you have a moment @ryanofsky!

ryanofsky approved

ryanofsky commented at 5:31 pm on October 22, 2019: member

Code review ACK 4671fc3d9e669da8b8781f0cbefee43cb9acd527. Changes since last review: 2 new commits adding suggested release note and python test comment, also a clean rebase with no changes to the earlier commits. The PR description is more comprehensive now, too. Looks good!

in src/wallet/wallet.cpp:2298 in 595f09d6de outdated

2293@@ -2294,6 +2294,12 @@ bool CWalletTx::InMempool() const
2294 }
2295 
2296 bool CWalletTx::IsTrusted(interfaces::Chain::Lock& locked_chain) const
2297+{
2298+    std::set<uint256> s;

ariard commented at 9:00 pm on October 24, 2019:

Hmm I don’t know about the need of DoS protection, can’t we rely on mempool DEFAULT_ANCESTOR_LIMIT there ? A transaction to be trusted has to be in-mempool (among other standards), so their unconfirmed parent too, at first parent hit which is not we should return. What’s th worst complexity for a graph of 25 parents?

JeremyRubin commented at 11:19 pm on October 24, 2019:

Even so, you can imagine a case where we have a single input single output chain of 25 taking:

sum n = 0 to N n = n * (n-1) /2 = O(N^2).

Which for 25 = 625 iterations.

Imagine what this would be for a tree with no descendants limit!

The caching guarantees that it is O(N*log(N)) worst case (could be improved possibly by switching to unordered_set… but it’s worth benchmarking since we will usually have a very small set)

sipa commented at 11:26 pm on October 24, 2019:

I believe the worst case is O(a^n), where a is the number of inputs/output per transaction, and n is the ancestor limit. Simply build a tx graph where every transaction spends a outputs of the previous layer, in a different inputs.

ariard commented at 5:15 pm on October 25, 2019:

Okay assuming complexity O(a^n), standard txn are limited by MAX_STANDARD_TX_WEIGHT and 148-bytes input, that gives you 548 inputs/outputs on every tx layer so something like 13700 iterations… Would be interesting to know how IsTrusted behaves on such computation order, but the fees burn for a DoS attacker seems pretty high.

Imagine what this would be for a tree with no descendants limit!

Not sure why descendants limit matters there?

Anyway, DoS protection is simple enough to get it for peace of mind.

in src/wallet/wallet.cpp:2423 in 5dd7da4ccd outdated

2419@@ -2420,10 +2420,11 @@ CWallet::Balance CWallet::GetBalance(const int min_depth, bool avoid_reuse) cons
2420     {
2421         auto locked_chain = chain().lock();
2422         LOCK(cs_wallet);
2423+        std::set<uint256> trustedParents;

ariard commented at 9:02 pm on October 24, 2019:

If you go with DoS protection, can’t you go further and reuse the cached set of trusted parents between WalletTxToJSON call in listtransactions and listsinceblock, they are all after chain locks so shouldn’t be an issue ?

JeremyRubin commented at 11:20 pm on October 24, 2019:

Possibly, but because it’s through the interfaced call I didn’t want to scope creep to include that. But it’s maybe worth a follow up PR?

ariard commented at 5:16 pm on October 25, 2019:

Really IMO but if DoS protection is worth it, it should take precedence on creeping into interfaced call.

in doc/release-notes.md:88 in 91f3073f08 outdated

84@@ -85,6 +85,7 @@ Wallet
85 ------
86 
87 - The wallet now by default uses bech32 addresses when using RPC, and creates native segwit change outputs.
88+- The way that output trust was computed has been fixed in #16766, which impacts confirmed/unconfirmed balance status and coin selection.

ariard commented at 9:07 pm on October 24, 2019:

nit: maybe precise how the trust computation has been changed “to evaluate trustiness of outpoint spent by parent and so recursively”

JeremyRubin commented at 11:22 pm on October 24, 2019:

I’m not sure what level of detail is best for the release note; will leave up to maintainer discretion. Since it can be nuanced, if someone is relying on this it’s best that they read the PR.

ariard commented at 9:22 pm on October 24, 2019: member

Concept ACK, this was previously a non-tested bug. Don’t know about the DoS protection, see comment.

Overall I think that this points to a general concept worth exploring as a revision to the categories “unconfirmed” and “confirmed”, to have “free cash”, “locked”, and “unconfirmed”. Free cash can be spent at will, locked funds are balances that are guaranteed to exist but we don’t have a confirmed UTXO for yet, and unconfirmed are funds we may or may not receive. I think this is out of scope of this PR though, but is worth further thought

Agree, UTXO state management is pretty unclear currently, I was thinking about this on the spending-side to rework abandontransaction to something like abandonutxo with the given nomenclature, committed UTXO included in one or more tx, spent UTXO include in a confirm tx, where user should be able to unlock committed UTXO if they are his. Conflicts tracking should stay at the transaction-level. On the receiving-side, not sure about the difference between locked and unconfirmed

ariard commented at 5:17 pm on October 25, 2019: member

Code Review ACK 4671fc3, maybe extend DoS protection in a follow-up PR.

fjahr commented at 9:24 pm on October 30, 2019: member

Code review ACK 4671fc3d9e669da8b8781f0cbefee43cb9acd527

Thanks for adding the extended description in the test. Good idea @ryanofsky !

promag commented at 2:21 am on November 4, 2019: member

Code review ACK 4671fc3d9e669da8b8781f0cbefee43cb9acd527.

b49dcbedf79613f0e0f61bfd742ed265213ed280 could be avoided (by fixing the respective commits in the first place) and 8f174ef112199aa4e98d756039855cc561687c2e could be discarded since it’s kind of unrelated. I guess it’s not a big deal considering the existing ACK.

Looking into IsTrusted, couldn’t we change it to not require cs_main (just cs_wallet)?

meshcollider referenced this in commit bdda137878 on Nov 5, 2019

meshcollider merged this on Nov 5, 2019

meshcollider closed this on Nov 5, 2019

meshcollider commented at 8:59 am on November 5, 2019: contributor

Concept ACK, this looks ready with 4 review ACKs

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

ryanofsky commented at 6:20 pm on November 5, 2019: member

re: #16766#pullrequestreview-310861505 from @promag

Looking into IsTrusted, couldn’t we change it to not require cs_main (just cs_wallet)?

It’s not trivial because of the GetDepthInMainChain and checkFinalTx calls, but #16426 does this

sidhujag referenced this in commit 75841000fe on Nov 7, 2019

HashUnlimited referenced this in commit 8410c1f790 on Apr 17, 2020

deadalnix referenced this in commit acadeec0ee on Oct 1, 2020

sidhujag referenced this in commit 814520cf59 on Nov 10, 2020

MarcoFalke locked this on Dec 16, 2021

wallet: Make IsTrusted scan parents recursively #16766

Conflicts