[WIP] wallet: standardize change output detection process #25979

furszy · 2022-09-01T20:40:07Z

Depends on #27601, please go there first.

This work aims to define, and implement a base standard mechanism to
detect individual change outputs.

Context

Currently, the wallet detects whether an output is change or not based
on data stored in the address book.

There is no notion of “change outputs”, the wallet detects change scripts.

Connoting that any address book record modification has implications
on all the historical outputs related to that particular destination. Meaning
that all those outputs can either be change or not. There is no middle-ground
granular distinction.

How Change Detection Currently Works?

The wallet walks-through the transaction outputs, extracts the script
destination and verify the following two points:

If the destination doesn't exist in the address book, then the script
is a "change address".
If the destination exists in the address book, but it doesn't have a
label, then the script is a "change address".

Motivation

There are a good number of problems in the current approach:

We make the wallet dependent on an external structure, with separate storage.
Which has to be updated and maintained along with the wallet state.
It cannot be maintained nor recovered across different wallet instances.
Cannot re-create the, possibly custom, address book data only by importing
the wallet descriptor string.
As the address book is an structure that the user can freely modify, the change
detection process might differ through different wallets.
The current rudimentary assumptions of "no address book entry" or "no label set for the address book entry"
to denote that certain script destination is change or not can easily be broken:
E.g. derive an address from one of the wallet’s external paths manually. Then send coins to it.
As the receive destination wasn't created inside the wallet, the wallet has no associated address book entry.
So, the reception is invalidly detected as change (added a test case for it).
The wallet can't detect change outputs on more complex scripts such as multi-sig change outputs.
The wallet is not able to detect change outputs going to an internal address if the internal address has a label.
(E.g. the user can manually set a label for the internal address and, doing that, make that all the change
outputs, in the wallet history, that were sent to the destination are no longer detected as change).
There isn’t a way to distinguish the external reception of coins into an internal address. Coins reception on any
internal address are always detected as change.

New Change Detection Mechanism Goals

Aiming to:

Define a base mechanism to align different wallet implementations. Preventing each piece of software
from diverging on the basic change outputs distinction.
Detect change outputs on-demand without requiring to maintain an external data structure synced with the
latest wallet state.
Independently, and accurately, detect change outputs regardless data stored in structures that the user
can freely modify.
Granular distinction between change vs non-change outputs that were sent to the same internal address.
E.g. the reception of coins, from an external source, on internal addresses will not longer be detected
as change anymore.
Expand the change detection to more complex scripts such as a multi-sig protected addresses. (While they
are added into the wallet on an internal spkm)

Change Output Detection Rules

A transaction output is change if it fulfills the following points:

At least one of the parent transaction inputs is from the wallet. (If none of them are, then the wallet is receiving coins
on an internal address).
The script extracted destination is from the wallet and is located in one of the internal script pub key manager.
(e.g. derived from an internal derivation path)

What about legacy wallets?

If the legacy wallet is HD post-split, we have an internal derivation path, so we can follow the same process as
descriptors wallet. Unless the destination is on the pre-split key pool, in which case, we fallback to the follow-up
case.

If the legacy wallet is pre-split, we continue using the address book as we either have an HD wallet with keys
derived only on the external path, or we are using raw keypool.

———————————————————————

Extra Note

This PR, in about 85% at least, is about expanding the current test coverage for the change output detection area.

TO DO (still WIP):

Save “internal” flag on non-active descriptors so the wallet can use them on the change detection process.
(which will fix the currently failing test cases).
Re-organize commits so tests always pass.
Verify backwards compatibility.

DrahtBot · 2022-09-01T21:23:24Z

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

Code Coverage & Benchmarks

For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/25979.

Reviews

See the guideline for information on the review process.

Type	Reviewers
Concept ACK	ghost

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#29936 (fuzz: wallet: add target for CreateTransaction by brunoerg)
#29136 (wallet: addhdkey RPC to add just keys to wallets via new void(KEY) descriptor by achow101)
#28710 (Remove the legacy wallet and BDB dependency by achow101)

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.

ghost · 2022-09-02T02:31:37Z

Interesting pull request although I haven't tested it yet.

Does this also fix #20935 and #20795 ?

How Change Detection Currently Works?
The wallet walks-through the transaction outputs, extracts the script
destination and verify the following two points:

If the destination doesn't exist in the address book, then the script
is a "change address".

If the destination exists in the address book, but it doesn't have a
label, then the script is a "change address".

I was assuming change address had different derivation path. Is that false?

furszy · 2022-09-02T16:09:34Z

Does this also fix #20935 and #20795 ?

Yes for the change outputs detection part. It will allow us to properly detect each individual output as change or not, independently on what is stored in the address book entry (making the process deterministic across instances, and not dependent on a data structure that the user can freely modify).

As an edge case example; with this, users could even receive coins on an internal address and the new mechanism will properly detect it as an external reception, not a change output (the transaction inputs aren't from the wallet, so no coins are returning to it). Still, this behavior is obviously not encouraged, nor should be easy to do in the wallet, as it breaks the whole idea of internal/external derivation paths.

Plus, would recommend you to check #25685 as well. The first commit there fixes a misleading wallet behavior where even if you set add_inputs=false (telling the wallet to disallow automatic coin selection), the wallet will still fetch coins internally and use them in the Coin Selection process (if you don't pre-set inputs manually).

How Change Detection Currently Works?
The wallet walks-through the transaction outputs, extracts the script
destination and verify the following two points:

If the destination doesn't exist in the address book, then the script
is a "change address".

If the destination exists in the address book, but it doesn't have a
label, then the script is a "change address".

I was assuming change address had different derivation path. Is that false?

Not entirely, the assumption is most of the time correct. It breaks on pre-split legacy wallets, where we don't have an internal derivation path. In those wallet versions we (1) only use an external path to derive public and change addresses, or if we go further back in time, (2) we use a raw pool of keys with no derivation paths at all. (Thus why the initial change detection process was implemented using the address book).

ghost · 2022-09-03T05:41:36Z

Concept ACK

achow101 · 2022-10-31T19:53:29Z

While I like the idea this is going for, I don't think it is sufficient. It relies on m_internal_spk_managers which only contains the currently active SPKMs. If a user were to remove a SPKM from being active, all of the addresses that were produced by that would no longer be detected as change. This is especially problematic with #25907 which rotates all of the currently active descriptors.

In general, I'm not sure that we can determine which output is change without storing additional metadata. What has been suggested before is to explicitly store an "IsChange" value in address book entries, with a "smart" fallback like what this PR does.

furszy · 2023-01-11T19:07:01Z

finally here. Thanks for the input achow101

While I like the idea this is going for, I don't think it is sufficient. It relies on m_internal_spk_managers which only contains the currently active SPKMs. If a user were to remove a SPKM from being active, all of the addresses that were produced by that would no longer be detected as change. This is especially problematic with #25907 which rotates all of the currently active descriptors.

I'm probably missing some context but.. wouldn't that be solvable by adding an internal field to the WalletDescriptor class? (32a990a). So we can keep track of non-active internal descriptors too.
It should work fine while we don't have any descriptor removal functionality (which would also mean to remove txs from the wallet etc) and require to keep historical records.

In general, I'm not sure that we can determine which output is change without storing additional metadata. What has been suggested before is to explicitly store an "IsChange" value in address book entries, with a "smart" fallback like what this PR does.

I think that we should have a more granular distinction and move from "change addresses" to "change outputs". Storing any extra metadata, if needed, inside the wallet transaction class.

A good use case for this is the reception of coins from an external source on internal addresses, which shouldn't be detected as change as it could be a simple reception or part of a dust attack.
if the tx has no inputs belonging to the wallet, then no output should be labeled as change.

General concept: Create transactions using the local wallet to different destinations provided by an external wallet. Verifying that the local wallet can detect the change output prior and post the tx is added to the wallet. The following cases are covered for a descriptor wallet: * 1) Create tx that sends to a legacy p2pkh addr and verify change detection. * 2) Create tx that sends to a p2wpkh addr and verify change detection. * 3) Create tx that sends to a wrapped p2wpkh addr and verify change detection. * 4) Create tx that sends to a taproot addr and verify change detection. And the following ones for a legacy-only wallet: * 1) Create tx that sends to a legacy p2pkh addr and verify change detection. * 2) Create tx that sends to a p2wpkh addr and verify change detection. * 3) Create tx that sends to a wrapped p2wpkh addr and verify change detection.

…allet The current change detection process assumption can easily be broken by creating an address manually, from an external derivation path, and send coins to it. As the address was not created by the wallet, it will not be in the addressbook, there by will be treated as change when it's clearly not. The wallet will properly detect it once the transaction gets added to the wallet and the address (and all the previous unused address) are derived and stored in the address book.

1) The change output goes to an address in one of the wallet external path. 2) The change goes back to the source. As the source is an external destination, and we are currently detecting change through it output script, the change will be marked as external (not change). 3) The user setting an address book label to a destination created from an internal key.

Currently, the wallet detects whether an output is change or not based on data stored in the address book. There is no notion of “change outputs”, the wallet detects change scripts. Meaning that any address book data modification has implications on all the historical outputs related to a particular destination as all of them can either be change or not. There is no middle-ground. The wallet walks-through the transaction outputs, extracts the script destination and verify the following two points: 1) If the destination doesn't exist in the address book, then the script is a "change address". 2) If the destination exists in the address book, but it doesn't have a label, then the script is a "change address". There are a good number of problems in the current approach: - We make the wallet dependent on an external structure, with separate storage. Which has to be updated and maintained along with the wallet state. - It cannot be maintained nor recovered across different wallet instances. Cannot re-create the address book data only by importing the wallet descriptor string. - As the address book is an structure that the user can freely modify, the change detection process might differ through different wallets. - The current rudimentary assumptions of "no address book entry" or "no label set for the address book entry" to denote that certain script destination is change or not can easily be broken: E.g. derive an address from one of the wallet’s external paths manually. Then send coins to it. As the receive destination wasn't created inside the wallet, the wallet has no associated address book entry. So, the reception is invalidly detected as change (added a test case for it). - The wallet can't detect change outputs on more complex scripts such as multi-sig change outputs. - The wallet is not able to detect any change output going to an internal address if the internal address has a label. (E.g. the user can manually set a label for the internal address and, doing that, make that all the change outputs, in the wallet history, that were sent to the destination are no longer detected as change). - There isn’t a way to distinguish the external reception of coins into an internal address. Coins reception on any internal address are always detected as change. Aiming to: * Define a base mechanism to align different wallet implementations. Preventing each piece of software from diverging on the basic change outputs distinction. * Detect change outputs on-demand without requiring to maintain an external data structure synced with the latest wallet state. * Independently, and accurately, detect change outputs regardless data stored in structures that the user can freely modify. * Granular distinction between change vs non-change outputs that were sent to the same internal address. E.g. the reception of coins, from an external source, on internal addresses will not longer be detected as change anymore. * Expand the change detection to more complex scripts such as a multi-sig protected addresses. (While they are added into the wallet on an internal spkm) A transaction output is change if it fulfills the following points: 1) At least one of the parent transaction inputs is from the wallet. (If none of them are, then the wallet is receiving coins on an internal address). 2) The script extracted destination is from the wallet and is located in one of the internal script pub key manager. (e.g. derived from an internal derivation path) If the legacy wallet is HD post-split, we have an internal derivation path, so we can follow the same process as descriptors wallet. Unless the destination is on the pre-split key pool, in which case, we fallback to the follow-up case. If the legacy wallet is pre-split, we continue using the address book as we either have an HD wallet with keys derived only on the external path, or we are using raw keypool.

As the wallet is receiving those coins from outside, them should not be detected as change. E.g. the user manually obtained and shared one of the internal addresses and received coins there.

…t to the same internal address A transaction output is change if it fulfills the following rules: 1) At least one of the transaction inputs is from the wallet. (If none of them are, then the wallet is receiving coins on an internal address). 2) The script extracted destination is from the wallet and is located in one of the internal script pub key manager. (e.g. derived from an internal derivation path)

Keep behavior consistent

To detect whether active and non-active descriptors are internal or not.

DrahtBot · 2024-10-25T09:23:43Z

🐙 This pull request conflicts with the target branch and needs rebase.

murchandamus · 2024-11-04T20:45:28Z

Hey @furszy, is this ready for review?

DrahtBot · 2025-02-01T01:07:54Z

⌛ There hasn't been much activity lately and the patch still needs rebase. What is the status here?

Is it still relevant? ➡️ Please solve the conflicts to make it ready for review and to ensure the CI passes.
Is it no longer relevant? ➡️ Please close.
Did the author lose interest or time to work on this? ➡️ Please close it and mark it 'Up for grabs' with the label, so that it can be picked up in the future.

DrahtBot · 2025-05-01T00:33:21Z

⌛ There hasn't been much activity lately and the patch still needs rebase. What is the status here?

Is it still relevant? ➡️ Please solve the conflicts to make it ready for review and to ensure the CI passes.
Is it no longer relevant? ➡️ Please close.
Did the author lose interest or time to work on this? ➡️ Please close it and mark it 'Up for grabs' with the label, so that it can be picked up in the future.

maflcko · 2025-05-04T17:20:23Z

The dependency was closed more than a year ago: #27601 (comment)

furszy · 2025-05-04T22:53:14Z

The dependency was closed more than a year ago: #27601 (comment)

Time flies. Closing for now as it is not in my priorities.

DrahtBot added the Wallet label Sep 1, 2022

furszy changed the title ~~wallet: standardize change output detection process~~ [WIP] wallet: standardize change output detection process Sep 1, 2022

This was referenced Sep 1, 2022

wallet: coverage for receiving txes with same id but different witness data #25909

Closed

wallet: Introduce AddressBookManager #25620

Closed

DrahtBot mentioned this pull request Sep 2, 2022

rpc: Return fee and prevout (utxos) to getrawtransaction #23319

Merged

ghost mentioned this pull request Sep 3, 2022

privacy: add_inputs argument for replacements to avoid adding unnecessary inputs #25776

Closed

DrahtBot mentioned this pull request Sep 3, 2022

Wallet: Add foreign_outputs metadata to support CoinJoin transactions #25991

Closed

DrahtBot mentioned this pull request Sep 13, 2022

New outputs argument for bumpfee/psbtbumpfee #25344

Merged

This was referenced Oct 3, 2022

clang-tidy: fixup named argument comments #26238

Merged

wallet, rpc: add label to listsinceblock #25934

Merged

ghost mentioned this pull request Oct 27, 2022

bumpfee behavior with custom change address #11233

Closed

DrahtBot mentioned this pull request Nov 9, 2022

bumpfee: Allow the user to choose which output is change #26467

Merged

DrahtBot mentioned this pull request Nov 29, 2022

wallet: simplify ListCoins implementation #25659

Merged

DrahtBot added the Needs rebase label Dec 6, 2022

furszy mentioned this pull request Jan 5, 2023

listreceivedbyaddress is empty for descriptor (but not legacy) wallets #26813

Open

furszy force-pushed the 2022_wallet_change_detection branch from d627345 to 2459339 Compare January 10, 2023 14:06

DrahtBot removed the Needs rebase label Jan 10, 2023

This was referenced Jan 12, 2023

refactor: importpubkey, importprivkey, importaddress, importmulti, and importdescriptors rpc #26840

Closed

refactor: wallet, remove global 'ArgsManager' dependency #26889

Merged

DrahtBot mentioned this pull request Apr 22, 2024

fuzz: wallet: add target for CreateTransaction #29936

Merged

DrahtBot mentioned this pull request May 23, 2024

rpc: avoid copying into UniValue #30115

Merged

DrahtBot added the Needs rebase label May 23, 2024

furszy force-pushed the 2022_wallet_change_detection branch from 95b2d8d to 00534c4 Compare August 20, 2024 20:40

DrahtBot removed CI failed Needs rebase labels Aug 20, 2024

DrahtBot added the Needs rebase label Aug 28, 2024

furszy added 13 commits October 12, 2024 12:56

wallet: remove old ScriptIsChange function

25fd5fe

wallet: coverage for coins reception into an internal address

12723da

As the wallet is receiving those coins from outside, them should not be detected as change. E.g. the user manually obtained and shared one of the internal addresses and received coins there.

RPC: add 'include_change' arg to 'listtransactions' and 'gettransaction'

df638b8

[fixup] tests, internal address with addrbook label detected as change

59de009

wallet: move OutputIsChange(txout) to IsOutputChange(tx, pos)

dae621e

Keep behavior consistent

wallet: add 'internal' field to WalletDescriptor

ea33406

To detect whether active and non-active descriptors are internal or not.

wallet: GetAllScriptPubKeyMans, return non-active internal descriptors

fb59e1c

test: coverage for change detection on inactive internal descriptors

679c918

furszy force-pushed the 2022_wallet_change_detection branch from 00534c4 to 679c918 Compare October 12, 2024 16:09

DrahtBot removed the Needs rebase label Oct 12, 2024

DrahtBot added the Needs rebase label Oct 25, 2024

furszy closed this May 4, 2025

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

[WIP] wallet: standardize change output detection process #25979

[WIP] wallet: standardize change output detection process #25979

Uh oh!

furszy commented Sep 1, 2022 •

edited

Loading

Uh oh!

DrahtBot commented Sep 1, 2022 •

edited

Loading

Uh oh!

ghost commented Sep 2, 2022

Uh oh!

furszy commented Sep 2, 2022 •

edited

Loading

Uh oh!

ghost commented Sep 3, 2022

Uh oh!

achow101 commented Oct 31, 2022

Uh oh!

furszy commented Jan 11, 2023 •

edited

Loading

Uh oh!

DrahtBot commented Oct 25, 2024

Uh oh!

murchandamus commented Nov 4, 2024

Uh oh!

DrahtBot commented Feb 1, 2025

Uh oh!

DrahtBot commented May 1, 2025

Uh oh!

maflcko commented May 4, 2025

Uh oh!

furszy commented May 4, 2025

Uh oh!

Uh oh!

[WIP] wallet: standardize change output detection process #25979

[WIP] wallet: standardize change output detection process #25979

Uh oh!

Conversation

furszy commented Sep 1, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Context

How Change Detection Currently Works?

Motivation

New Change Detection Mechanism Goals

Change Output Detection Rules

What about legacy wallets?

Extra Note

TO DO (still WIP):

Uh oh!

DrahtBot commented Sep 1, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Code Coverage & Benchmarks

Reviews

Conflicts

Uh oh!

ghost commented Sep 2, 2022

Uh oh!

furszy commented Sep 2, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

ghost commented Sep 3, 2022

Uh oh!

achow101 commented Oct 31, 2022

Uh oh!

furszy commented Jan 11, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

DrahtBot commented Oct 25, 2024

Uh oh!

murchandamus commented Nov 4, 2024

Uh oh!

DrahtBot commented Feb 1, 2025

Uh oh!

DrahtBot commented May 1, 2025

Uh oh!

maflcko commented May 4, 2025

Uh oh!

furszy commented May 4, 2025

Uh oh!

Uh oh!

furszy commented Sep 1, 2022 •

edited

Loading

DrahtBot commented Sep 1, 2022 •

edited

Loading

furszy commented Sep 2, 2022 •

edited

Loading

furszy commented Jan 11, 2023 •

edited

Loading