wallet: Strictly match tx change type to improve privacy #23789

maflcko · 2021-12-15T20:16:45Z

Currently the change type will only match a destination by accident, making it easier to determine the change.

Fix that by strictly matching one of the destinations.

maflcko · 2021-12-15T20:17:15Z

Obviously this will fail tests and need docs fixed up. I'll do that unless there are NACKs.

kristapsk · 2021-12-15T20:28:38Z

Concept ACK

src/wallet/wallet.cpp

ghost · 2021-12-15T22:33:58Z

Concept ACK

naumenkogs · 2021-12-16T09:10:02Z

Concept ACK

rajarshimaitra

Concept + tACK faf4958

This mixes change with destination better than previous logic.
Below are just some small nits.

test/functional/wallet_address_types.py

rajarshimaitra · 2021-12-17T06:25:55Z

test/functional/wallet_address_types.py

@@ -348,9 +348,9 @@ def run_test(self):
        if self.options.descriptors:


It seems now the change type behavior for both type of wallets is same. So this can be removed?

I think the whole test needs to be re-written from scratch, but I want to keep the changes minimal here.

maflcko · 2021-12-17T07:02:04Z

Force pushed to fix test logs

S3RK · 2021-12-17T07:23:10Z

Concept & Approach ACK fada6c6. Also did light code review .

ghost · 2021-12-17T10:12:21Z

Tested with some transactions on testnet by using different types of address:

maflcko · 2021-12-17T10:24:16Z

Excellent. Thank you for testing. If you want to match P2TR, you need a descriptor wallet with a tr descriptor (created by default for new descriptor wallets).

ghost · 2021-12-17T11:11:53Z

Yes that works for P2TR: 64d300442ad4ccb726146b292658876040a1e230af0fd0236e5e83a5aaa33c8d

maflcko · 2021-12-17T11:44:30Z

and for completeness: P2WSH is impossible to match, since the wallet doesn't support it

ghost

tACK fada6c6

Thanks for improving privacy. Will have to add this PR and author in my blog.

kristapsk · 2021-12-17T14:33:53Z

and for completeness: P2WSH is impossible to match, since the wallet doesn't support it

And it's useless even to try to match as it will likely differ on spend.

maflcko · 2021-12-17T14:58:59Z

WSH is a corner case anyway (less than 5%) according to https://transactionfee.info/charts/output-type-distribution-count/

ghost · 2021-12-17T15:49:48Z

I was assuming its used for multisig because of this note mentioned in caravan:

achow101 · 2021-12-17T18:09:20Z

and for completeness: P2WSH is impossible to match, since the wallet doesn't support it

Not necessarily. A descriptor wallet can have an active wsh(...) descriptor, and it would be assigned to OutputType::BECH32 (because P2WSH is bech32).

achow101 · 2021-12-17T18:31:02Z

ACK fada6c6

w0xlt

tACK fada6c6

Tested on signet with legacy, p2sh-segwit, bech32, and bech32m address types.

maflcko · 2021-12-18T08:25:17Z

Not necessarily. A descriptor wallet can have an active wsh(...) descriptor, and it would be assigned to OutputType::BECH32 (because P2WSH is bech32).

Interesting. Could the wallet also spend the created wsh change output?

maflcko · 2021-12-20T09:34:30Z

@achow101 Ready for merge?

JeremyRubin · 2021-12-20T20:48:03Z

This feels like an incredibly fast merge for a privacy related feature that requires careful consideration.

I need to review the code specifically, but if I understand it correctly this will majorly slow the adoption of Taproot because you'll have transitive slowness to upgrade (e.g., I made a segwit change to be compatible with a old segwit destination I was paying to, now my change is segwit, now future users will make segwit change to pay me, etc).

Please revert and make a mailing list post.

JeremyRubin · 2021-12-20T20:53:57Z

I gues maybe part of what I'm missing is that only outputs are analyzed, not inputs, so it's not as bad as I thought it might be in terms of transitivity.

I still think this could slow Tr adoption quite a bit, and I think that's worth getting a better idea of before deploying this.

achow101 · 2021-12-20T21:33:50Z

now my change is segwit, now future users will make segwit change to pay me, etc).

No, inputs are not considered.

Please revert and make a mailing list post.

This is a local wallet policy, it does not need to be discussed on the mailing list.

I still think this could slow Tr adoption quite a bit, and I think that's worth getting a better idea of before deploying this.

I see that it could slow adoption a bit, but it is overall an improvement to how we determine change addresses IMO. We have plenty of time until 23.0 to change it, and changing the order of preferences would not be particularly difficult.

ghost · 2021-12-20T21:53:44Z

I still think this could slow Tr adoption quite a bit, and I think that's worth getting a better idea of before deploying this.

Privacy > TR adoption
IIUC change will be P2TR if sending to P2TR: wallet: Strictly match tx change type to improve privacy #23789 (comment) so I don't see issues with adoption if more people want to use P2TR they will eventually because of usecases.

Making it difficult to identify change in a transaction is a great improvement.

JeremyRubin · 2021-12-20T22:04:09Z

Well it still does worsen privacy since then my wallet will be spending a mix out output types rather than just all taproot.

And the observability of this pattern (change matching) is also... pretty observable, especially if bitcoin core (and only upgraded wallets) are the ones doing it.

This becomes worse the slower taproot uptake is.

Further, when you do a subsequent spend, unless our coin selection algorithm is primed to only spend like-kind togehter (not sure it is?) we end up re-correlating the legacy output with the new format, linking the idea that that output was likely one from our wallet as it's with the upgraded type. In order to safely get taproot outputs you'd have to double-tap your old style outputs into a all taproot self-pay payout txn, or find an opportunity to do so nautrally as a payment. If you were to take your old outputs and pay to a new txn and make a Tr change, you also get screwed because then it's known that your wallet did really have Tr enabled and was faking. I think it's really hard to avoid these cases.

The main benefit here is decorrelation of change / payment at time of flight of txn. But privacy is a property that we also have to weigh the costs and benefits for future behaviors as well, and I think it's worth tightly considering this PR under that lens.

I agree that privacy > all else, but this change should have IMO a pretty negative effect on the herd benefit. And privacy only can be created within the walls of an anonymity set. The only thing worse than no privacy is a false sense of one.

I think the best path to build the anonymity set is to just go all-in taproot change.

… privacy

achow101 · 2021-12-20T22:17:24Z

we end up re-correlating the legacy output with the new format, linking the idea that that output was likely one from our wallet as it's with the upgraded type.

I don't see how this is any worse than a normal spend which is likely to correlate change to your wallet anyways. The purpose is to make it harder to determine which is change while the UTXOs are unspent. Hiding which outputs are change is already tenuous at best.

In order to safely get taproot outputs you'd have to double-tap your old style outputs into a all taproot self-pay payout txn, or find an opportunity to do so nautrally as a payment.

Or just set -addresstype=bech32m and -changetype=bech32m? Those startup options, and any change address option given to transaction creation, will always take precedence over this automatic behavior.

The behavior implemented here also is fairly similar to what we did for segwit. The default address type was p2sh-segwit, and we would only use bech32 if a p2wpkh or p2wsh recipient was observed.

JeremyRubin · 2021-12-20T22:23:43Z

we end up re-correlating the legacy output with the new format, linking the idea that that output was likely one from our wallet as it's with the upgraded type.

I don't see how this is any worse than a normal spend which is likely to correlate change to your wallet anyways. The purpose is to make it harder to determine which is change while the UTXOs are unspent. Hiding which outputs are change is already tenuous at best.

It's worse because the subsequent spend mixing inputs shows that our wallet did in fact support (other type) and is therefore likely to be the change address because it's unlikely we requested to be paid in (old type).

Or just set -addresstype=bech32m and -changetype=bech32m? Those startup options, and any change address option given to transaction creation will always take precedence over this automatic behavior.

I'm analyzing the impact for a user who uses the default configuration, not what someone can do. If the default configuration isn't a good idea, it shouldn't be default.

The behavior implemented here also is fairly similar to what we did for segwit. The default address type was p2sh-segwit, and we would only use bech32 if a p2wpkh or p2wsh recipient was observed.

I don't think that results from segwit v0 apply here since there was an entirely different mood around adoption which necessitated the segwit have 2 address types for p2sh wrapping and there was real risk of refusing to integrate.

Noting also the negative scaling impact this has on a CISA future, for example, if a lot of the change outputs created are to be long lived.

ghost · 2021-12-20T22:31:10Z

And the observability of this pattern (change matching) is also... pretty observable, especially if bitcoin core (and only upgraded wallets) are the ones doing it.

There are few other wallets that do the same thing.

Further, when you do a subsequent spend, unless our coin selection algorithm is primed to only spend like-kind togehter (not sure it is?) we end up re-correlating the legacy output with the new format, linking the idea that that output was likely one from our wallet as it's with the upgraded type.

Good point. Will have to test this. I think this can be improved but it would be out of scope for this PR.

JeremyRubin · 2021-12-20T22:36:49Z

the best case we could do would probably be to draw output types from some distribution matching the chain data over the last 2 weeks and encode a small bias towards the newer type. The herd would move in unison towards new types, and you would actually not be able to learn more information than the bias amount.

note: this would have to apply to address creation too

achow101 · 2021-12-20T22:54:50Z

It's worse because the subsequent spend mixing inputs shows that our wallet did in fact support (other type) and is therefore likely to be the change address because it's unlikely we requested to be paid in (old type).

Not true. The default output type is still bech32 - users using the current defaults will still give out bech32 addresses, and so they will be requesting payments to bech32 addresses. However, their wallet may have tr descriptors, in which case they support Taproot. So they would be giving out p2wpkh addresses, and potentially receiving change as p2tr if the recipient gives them a p2tr address.

Additionally, this is all about address type and not script type. Future witness versions (are expected to) use bech32m as well, so in the future, unless the recipient was asked to be paid in (really old type), the change is likely to be (future witness version) even if the recipient asked for (older witness version).

I'm analyzing the impact for a user who uses the default configuration, not what someone can do. If the default configuration isn't a good idea, it shouldn't be default.

You gave a scenario where the user is trying to use all taproot. If a user knows enough about address types and wants to only use a specific type, I think they can figure out how to set the option. We can also add a GUI setting for it too.

maflcko · 2021-12-21T08:54:40Z

@JeremyRubin For reference I implemented what you suggest first in #23731, but then decided to abandon it.

re: process. I think that a pull request is ready to be merged if it was reviewed. Surely, a behaviour changing pull request should be open for a few days to let more eyes take a look at it. I think 11 days is more than enough for that, since it will never be possible to get everyone's eye on it. And this is "just" the master branch. If for some reason all reviewers messed up and did the wrong thing, there is still plenty of time to revisit before a release.

re: content:
Surely, using bech32m unconditionally for change is going to speed up tr adoption on chain. However, it also makes it trivial to spot the change output immediately (at broadcast time of the tx). Especially if the "real" tr usage is low.

With this patch, there should still be a bias toward "promoting" tr, since any tr output will lead to tr change.

Also, I am not sure if it makes sense to consider input-bundling here. If the analysis firm uses input-bundling as a heuristic, then it can determine the wallet inputs regardless of their type already. If they don't, since it might be a coinjoin, then it shouldn't matter.

maflcko · 2021-12-22T10:14:03Z

The -changetype doc wasn't updated. Fixed in #23840

…pes` during coin selection 71d1d13 test: add unit test for AvailableCoins (josibake) da03cb4 test: functional test for new coin selection logic (josibake) 438e048 wallet: run coin selection by `OutputType` (josibake) 77b0707 refactor: use CoinsResult struct in SelectCoins (josibake) 2e67291 refactor: store by OutputType in CoinsResult (josibake) Pull request description: # Concept Following bitcoin/bitcoin#23789, Bitcoin Core wallet will now generate a change address that matches the payment address type. This improves privacy by not revealing which of the outputs is the change at the time of the transaction in scenarios where the input address types differ from the payment address type. However, information about the change can be leaked in a later transaction. This proposal attempts to address that concern. ## Leaking information in a later transaction Consider the following scenario: ![mix input types(1)](https://user-images.githubusercontent.com/7444140/158597086-788339b0-c698-4b60-bd45-9ede4cd3a483.png) 1. Alice has a wallet with bech32 type UTXOs and pays Bob, who gives her a P2SH address 2. Alice's wallet generates a P2SH change output, preserving her privacy in `txid: a` 3. Alice then pays Carol, who gives her a bech32 address 4. Alice's wallet combines the P2SH UTXO with a bech32 UTXO and `txid: b` has two bech32 outputs From a chain analysis perspective, it is reasonable to infer that the P2SH input in `txid: b` was the change from `txid: a`. To avoid leaking information in this scenario, Alice's wallet should avoid picking the P2SH output and instead fund the transaction with only bech32 Outputs. If the payment to Carol can be funded with just the P2SH output, it should be preferred over the bech32 outputs as this will convert the P2SH UTXO to bech32 UTXOs via the payment and change outputs of the new transaction. **TLDR;** Avoid mixing output types, spend non-default `OutputTypes` when it is economical to do so. # Approach `AvailableCoins` now populates a struct, which makes it easier to access coins by `OutputType`. Coin selection tries to find a funding solution by each output type and chooses the most economical by waste metric. If a solution can't be found without mixing, coin selection runs over the entire wallet, allowing mixing, which is the same as the current behavior. I've also added a functional test (`test/functional/wallet_avoid_mixing_output_types.py`) and unit test (`src/wallet/test/availablecoins_tests.cpp`. ACKs for top commit: achow101: re-ACK 71d1d13 aureleoules: ACK 71d1d13. Xekyo: reACK 71d1d13 via `git range-diff master 6530d19 71d1d13` LarryRuane: ACK 71d1d13 Tree-SHA512: 2e0716efdae5adf5479446fabc731ae81d595131d3b8bade98b64ba323d0e0c6d964a67f8c14c89c428998bda47993fa924f3cfca1529e2bd49eaa4e31b7e426

maflcko added Wallet Privacy labels Dec 15, 2021

maflcko mentioned this pull request Dec 15, 2021

[RFC] wallet: Always prefer bech32(m) change by default #23731

Closed

maflcko changed the title ~~wallet: Strictly match in TransactionChangeType to improve privacy [skip ci] [ci skip]~~ wallet: Strictly match tx change type to improve privacy [skip ci] [ci skip] Dec 15, 2021

maflcko force-pushed the 2112-walletChangeChange branch 2 times, most recently from cb66fbf to 26682d5 Compare December 15, 2021 20:21

achow101 reviewed Dec 15, 2021

View reviewed changes

src/wallet/wallet.cpp Show resolved Hide resolved

maflcko changed the title ~~wallet: Strictly match tx change type to improve privacy [skip ci] [ci skip]~~ wallet: Strictly match tx change type to improve privacy Dec 16, 2021

maflcko force-pushed the 2112-walletChangeChange branch from 26682d5 to faf4958 Compare December 16, 2021 18:11

rajarshimaitra reviewed Dec 17, 2021

View reviewed changes

wallet: Strictly match tx change type to improve privacy

fada6c6

maflcko force-pushed the 2112-walletChangeChange branch from faf4958 to fada6c6 Compare December 17, 2021 07:00

ghost approved these changes Dec 17, 2021

View reviewed changes

w0xlt approved these changes Dec 18, 2021

View reviewed changes

achow101 merged commit 3ac3805 into bitcoin:master Dec 20, 2021

sidhujag pushed a commit to syscoin/syscoin that referenced this pull request Dec 20, 2021

Merge bitcoin#23789: wallet: Strictly match tx change type to improve…

d7f67b2

… privacy

maflcko deleted the 2112-walletChangeChange branch December 21, 2021 08:33

josibake mentioned this pull request Mar 16, 2022

wallet: avoid mixing different OutputTypes during coin selection #24584

Merged

ghost mentioned this pull request Aug 5, 2022

wallet: Do not match legacy addresses for change type #24362

Closed

bitcoin locked and limited conversation to collaborators Dec 22, 2022

		@@ -348,9 +348,9 @@ def run_test(self):
		if self.options.descriptors:

wallet: Strictly match tx change type to improve privacy #23789

wallet: Strictly match tx change type to improve privacy #23789

Conversation

maflcko commented Dec 15, 2021

Uh oh!

maflcko commented Dec 15, 2021

Uh oh!

kristapsk commented Dec 15, 2021

Uh oh!

Uh oh!

ghost commented Dec 15, 2021

Uh oh!

naumenkogs commented Dec 16, 2021

Uh oh!

rajarshimaitra left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

rajarshimaitra Dec 17, 2021

Choose a reason for hiding this comment

Uh oh!

maflcko Dec 17, 2021

Choose a reason for hiding this comment

Uh oh!

maflcko commented Dec 17, 2021

Uh oh!

S3RK commented Dec 17, 2021

Uh oh!

ghost commented Dec 17, 2021 • edited by ghost Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

maflcko commented Dec 17, 2021

Uh oh!

ghost commented Dec 17, 2021

Uh oh!

maflcko commented Dec 17, 2021

Uh oh!

ghost left a comment

Choose a reason for hiding this comment

Uh oh!

kristapsk commented Dec 17, 2021

Uh oh!

maflcko commented Dec 17, 2021

Uh oh!

ghost commented Dec 17, 2021

Uh oh!

achow101 commented Dec 17, 2021

Uh oh!

achow101 commented Dec 17, 2021

Uh oh!

w0xlt left a comment

Choose a reason for hiding this comment

Uh oh!

maflcko commented Dec 18, 2021

Uh oh!

maflcko commented Dec 20, 2021

Uh oh!

JeremyRubin commented Dec 20, 2021

Uh oh!

JeremyRubin commented Dec 20, 2021

Uh oh!

achow101 commented Dec 20, 2021

Uh oh!

ghost commented Dec 20, 2021

Uh oh!

JeremyRubin commented Dec 20, 2021

Uh oh!

achow101 commented Dec 20, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

JeremyRubin commented Dec 20, 2021

Uh oh!

ghost commented Dec 20, 2021

Uh oh!

JeremyRubin commented Dec 20, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

achow101 commented Dec 20, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

ghost commented Dec 17, 2021 •

edited by ghost

Loading

achow101 commented Dec 20, 2021 •

edited

Loading

JeremyRubin commented Dec 20, 2021 •

edited

Loading

achow101 commented Dec 20, 2021 •

edited

Loading