wallet: generate random change target for each tx for better privacy #24494

glozow · 2022-03-07T14:52:12Z

Closes #24458 - Knapsack always chooses 1 million sats as its change target, making it easier to fingerprint transactions created by the Core wallet. Instead of using a fixed value, choose one randomly each time (within a range).

GenerateChangeTarget works as follows:

If the payment value > 25ksat, it is randomly chosen between 50ksat and min(2 * payment_value, 1milsat)
If the payment_value <= 25ksat, the value is just 50ksat.

The SRD target is 50ksat, not randomized, since the selection does not aim for a specific target anyway.

(Note the random change target was mistakenly not used yet in this PR, see #25825).

DrahtBot · 2022-03-08T00:20:41Z

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

Conflicts

Reviewers, this pull request conflicts with the following ones:

#24644 (wallet: add tracepoints and algorithm information to coin selection by achow101)
#24091 (wallet: Consolidate CInputCoin and COutput by achow101)
#23076 (Pass CFeeRate and CTxMemPool in-params by reference to const by jonatack)

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.

glozow · 2022-03-08T13:55:05Z

Ok fixed the wallet_bumpfee.py break.

glozow · 2022-03-08T13:55:28Z

cc @xekyo

test/functional/wallet_bumpfee.py

S3RK

Concept ACK.

I'm somewhat concerned though that testing coin selection behavior becomes more difficult because one can't predictably explore edge cases now. We can either rely on a more complex stochastic testing or add a way to fix the change traget (though I'm not a fan of adding functionality just for the tests). How should we think about the trade off between increasing test complexity vs increasing code complexity for testability?

src/wallet/spend.cpp

glozow · 2022-03-09T11:35:52Z

I'm somewhat concerned though that testing coin selection behavior becomes more difficult because one can't predictably explore edge cases now. We can either rely on a more complex stochastic testing or add a way to fix the change traget

I'd argue that if we're testing coin selection specifically (i.e. calling something like SelectCoins(), or AttemptSelection(), not CreateTransaction()), we can still manually control the change target through CoinSelectionParams. In less granular tests, the concern might be that we accidentally run out of coins to cover the change, but since our upper bound is equal to MIN_CHANGE, that shouldn't happen in existing tests, and future tests should make room for a change output up to 1milsats.

src/wallet/coinselection.cpp

glozow · 2022-03-09T14:11:10Z

Set SRD change target to CHANGE_LOWER and added rng as a parameter to GenerateChangeTarget()

promag

Concept ACK.

src/qt/coincontroldialog.cpp

src/wallet/coinselection.h

src/wallet/test/coinselector_tests.cpp

glozow · 2022-03-10T12:45:52Z

Added release notes, docs for GenerateChangeTarget, and separate commit for removing MIN_CHANGE

doc/release-notes-24494.md

achow101 · 2022-03-10T13:14:36Z

The code changes look fine but I would like to run a simulation first to see how it affects our coin selection strategies.

murchandamus · 2022-03-15T14:38:51Z

Concept ACK, but I'm wondering how making the minChange different for SRD and Knapsack affects the outcome. My first impression is that it would favor SRD, because SRD needs to raise less funds than Knapsack. This could in turn increase the frequency of single input selections which may lead to larger UTXO pools in the Bitcoin Core wallet. In turn that might make Branch and Bound find more solutions, too.

@achow101: Very curious for your simulation results, and it might be interesting to also run a variant where SRD and Knapsack use the same minChange per selection.

murchandamus

Looks very good, thanks for taking this up so quickly.

murchandamus · 2022-03-15T18:11:52Z

src/wallet/coinselection.cpp

0a25b209b2fab44d639b93f9699e1364f270527e: Perhaps mention here how the nTargetValue is composed, it would be nice to get a reminder here whether it already includes min_change or does not.

murchandamus · 2022-03-15T20:37:56Z

src/wallet/coinselection.cpp

It's not clear to me what we are trying to achieve in the context of smaller payments here. The proposed range for the change amount would cause the payment to always be smaller than the change which clearly identifies their roles (if one of the outputs is below 25,000, the smaller is the payment). It may be better to avoid making a tiny change output here, if there is no privacy benefit. Perhaps it would be better to drop the special case and then just go with CHANGE_LOWER?

Alternatively, we should perhaps make the lower bound for change always smaller than the payment to ensure that the roles are unclear.

Changed to CHANGE_LOWER when the payment amount is less than 25k

src/wallet/coinselection.cpp

murchandamus · 2022-03-15T21:07:55Z

src/wallet/coinselection.h

I'm a bit worried that "change_target" may be understood here as us actually trying to produce change with exactly that amount, while that would just reflect the behavior of the Knapsack algorithm. Perhaps it would be clearer to identify the "target change" as a form of minimum change here. To a lesser degree this concern also applies to the comments on the static boundaries in lines 20 and 22.

Changed to min_change_target everywhere. The comment above the member should hopefully be pretty clear.

murchandamus · 2022-03-15T21:25:08Z

src/qt/coincontroldialog.cpp

Not your fault obviously, but this comment is kinda confusing where it's at and would fit much better around line 493. Since you're touching this section already, could you perhaps move it down?

achow101 · 2022-03-15T22:32:12Z

Simulation results:

Method	Current Balance	Mean #UTXO	Current #UTXO	#Deposits	#Inputs Spent	#Withdraws	#Uneconomical outputs spent	#Change Created	#Changeless	Min Change Value	Max Change Value	Mean Change Value	Std. Dev. of Change Value	Total Fees	Mean Fees per Withdraw	Cost to Empty	Total Cost	Min Input Size	Max Input Size	Mean Input Size	Std. Dev. of Input Size	BnB Usage	SRD Usage	Knapsack Usage	#BnB no change	#SRD no change	#Knapsack no change
Master (7d1cef26)	16.55857290	128.469688101	58	4065	11182	7893	2	7175	718	0.00002240	274.32706193	17.5661542098	47.1756762651	0.44316889	0.0000561470784239	-0.0000394400000	0.443129450000	1	102	1.41669834030	2.50732528322	716	1936	5241	716	0	2
Master (7d1cef26) + 24494 (dee71867)	16.55374714	111.582991889	45	4065	11191	7893	3	7171	722	0.00001160	256.54571999	11.2871949815	38.4625842089	0.44799465	0.0000567584758647	-0.0000306000000	0.447964050000	1	100	1.41783859116	2.20978931572	722	1866	5305	722	0	0

glozow · 2022-03-24T12:14:17Z

Rebased + addressed @MarcoFalke's comments

murchandamus

ACK e75c8dd14d0988c1bf4594105de905c2c444b530

no behavior changes, since the target is always MIN_CHANGE

If the wallet always chooses 1 million sats as its change target, it is easier to fingerprint transactions created by the Core wallet.

glozow · 2022-03-25T13:47:27Z

Rebased for #24091. The CI failure is the "AssertionError: Fee of 0.00003160 BTC too high!" error from wallet_send.py, unrelated

achow101 · 2022-03-25T15:35:27Z

ACK 9053f64

murchandamus

reACK 9053f64

maflcko · 2022-08-12T06:20:51Z

The pull request description is outdated/wrong. The correct description can be found in the docstring of GenerateChangeTarget

glozow · 2022-08-12T09:43:31Z

The pull request description is outdated/wrong. The correct description can be found in the docstring of GenerateChangeTarget

Updated.

In the spirit of keeping pull documentation correct, tbh this pull didn't really randomize change targets. I accidentally created 2 separate change target params instead of renaming when updating from dee7186 to 57c035b. Thanks @S3RK for catching this and pointing it out to me, it's since been fixed in #25825.

A new feature was added to bitcoind 24.1+ that tries to make the change output indistinguishable from the payment output. This is a great for privacy, but it adds randomness to coin selection and uses a non-minimal set of inputs sometimes. We work around this by updating the amount of the output we want bitcoind to use to make sure it's sufficient to pay for both the channel funding and the change output. This shouldn't be too much of an issue for normal operation, where we'll sometimes use two inputs instead of one, which costs more fees, but increases privacy. See bitcoin/bitcoin#24494 for details.

glozow added Privacy Wallet labels Mar 7, 2022

glozow force-pushed the 2022-03-minchange branch from f4a6fe0 to 6d803e5 Compare March 7, 2022 15:02

glozow force-pushed the 2022-03-minchange branch from 6d803e5 to a653b84 Compare March 8, 2022 12:50

glozow marked this pull request as ready for review March 8, 2022 13:55

glozow requested a review from achow101 March 8, 2022 13:55

DrahtBot mentioned this pull request Mar 8, 2022

wallet: Consolidate CInputCoin and COutput #24091

Merged

achow101 reviewed Mar 8, 2022

View reviewed changes

test/functional/wallet_bumpfee.py Outdated Show resolved Hide resolved

glozow force-pushed the 2022-03-minchange branch from a653b84 to 6490a74 Compare March 8, 2022 16:02

DrahtBot mentioned this pull request Mar 9, 2022

refactor: pass CTxMemPool and CFeeRate in-param objects by const reference #23076

Closed

S3RK reviewed Mar 9, 2022

View reviewed changes

src/wallet/spend.cpp Outdated Show resolved Hide resolved

maflcko reviewed Mar 9, 2022

View reviewed changes

src/wallet/coinselection.cpp Outdated Show resolved Hide resolved

glozow force-pushed the 2022-03-minchange branch from 6490a74 to 3173930 Compare March 9, 2022 14:10

promag reviewed Mar 9, 2022

View reviewed changes

src/qt/coincontroldialog.cpp Outdated Show resolved Hide resolved

src/wallet/coinselection.h Outdated Show resolved Hide resolved

src/wallet/test/coinselector_tests.cpp Outdated Show resolved Hide resolved

glozow force-pushed the 2022-03-minchange branch from 3173930 to 53a30b5 Compare March 10, 2022 11:21

maflcko reviewed Mar 10, 2022

View reviewed changes

doc/release-notes-24494.md Outdated Show resolved Hide resolved

glozow force-pushed the 2022-03-minchange branch from 53a30b5 to dee7186 Compare March 10, 2022 13:33

achow101 requested a review from murchandamus March 11, 2022 15:02

This was referenced Mar 11, 2022

wallet: add config to prioritize a solution that doesn't create change in coin selection #23475

Closed

wallet: Use single FastRandomContext when creating a wallet tx #24560

Merged

murchandamus reviewed Mar 15, 2022

View reviewed changes

glozow force-pushed the 2022-03-minchange branch 2 times, most recently from 5988dd1 to e75c8dd Compare March 24, 2022 12:13

DrahtBot removed the Needs rebase label Mar 24, 2022

DrahtBot mentioned this pull request Mar 24, 2022

wallet: add tracepoints and algorithm information to coin selection #24644

Merged

murchandamus approved these changes Mar 24, 2022

View reviewed changes

DrahtBot added the Needs rebase label Mar 24, 2022

glozow added 4 commits March 25, 2022 11:56

refactor coin selection for parameterizable change target

1e52e6b

no behavior changes, since the target is always MIN_CHANGE

[wallet] randomly generate change targets

a44236a

If the wallet always chooses 1 million sats as its change target, it is easier to fingerprint transactions created by the Core wallet.

[wallet] remove MIN_CHANGE

46f2fed

[doc] release notes for random change target

9053f64

glozow force-pushed the 2022-03-minchange branch from e75c8dd to 9053f64 Compare March 25, 2022 12:05

DrahtBot removed the Needs rebase label Mar 25, 2022

murchandamus approved these changes Mar 25, 2022

View reviewed changes

fanquake merged commit 6d5771b into bitcoin:master Mar 25, 2022

mzumsande mentioned this pull request Mar 27, 2022

fuzz: add target for coinselection algorithms #24602

Merged

S3RK mentioned this pull request Mar 29, 2022

test: coinselection edge cases #24580

Closed

glozow deleted the 2022-03-minchange branch March 30, 2022 20:31

murchandamus mentioned this pull request Aug 10, 2022

Use change amount as tiebreaker for SelectionResults #25742

Closed

bitcoin deleted a comment from nina1234 Aug 12, 2022

maflcko mentioned this pull request Aug 12, 2022

Improve change amount privacy #6569

Closed

sime mentioned this pull request Dec 19, 2022

Generate random change target for each TX to increase privacy trezor/trezor-suite#7245

Closed

notmandatory mentioned this pull request Mar 31, 2023

Improve bdk::Wallet API bitcoindevkit/bdk#918

Closed

4 tasks

t-bast mentioned this pull request Jul 13, 2023

Update to bitcoind 24.1 ACINQ/eclair#2711

Merged

bitcoin locked and limited conversation to collaborators Aug 12, 2023

wallet: generate random change target for each tx for better privacy #24494

wallet: generate random change target for each tx for better privacy #24494

Uh oh!

Conversation

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

Uh oh!

Uh oh!

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

Uh oh!

Conflicts

Uh oh!

glozow commented Mar 8, 2022

Uh oh!

glozow commented Mar 8, 2022

Uh oh!

Uh oh!

S3RK left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

glozow commented Mar 9, 2022

Uh oh!

Uh oh!

glozow commented Mar 9, 2022

Uh oh!

promag left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

glozow commented Mar 10, 2022

Uh oh!

Uh oh!

achow101 commented Mar 10, 2022

Uh oh!

murchandamus commented Mar 15, 2022

Uh oh!

murchandamus left a comment

Choose a reason for hiding this comment

Uh oh!

murchandamus Mar 15, 2022

Choose a reason for hiding this comment

Uh oh!

glozow Mar 23, 2022

Choose a reason for hiding this comment

Uh oh!

murchandamus Mar 15, 2022

Choose a reason for hiding this comment

Uh oh!

glozow Mar 23, 2022

Choose a reason for hiding this comment

Uh oh!

Uh oh!

murchandamus Mar 15, 2022

Choose a reason for hiding this comment

Uh oh!

glozow Mar 23, 2022

Choose a reason for hiding this comment

Uh oh!

murchandamus Mar 15, 2022

Choose a reason for hiding this comment

Uh oh!

achow101 commented Mar 15, 2022

Uh oh!

glozow commented Mar 24, 2022

Uh oh!

murchandamus left a comment

Choose a reason for hiding this comment

Uh oh!

glozow commented Mar 25, 2022

Uh oh!

achow101 commented Mar 25, 2022

Uh oh!

murchandamus left a comment

Choose a reason for hiding this comment

Uh oh!

maflcko commented Aug 12, 2022

Uh oh!

glozow commented Aug 12, 2022

glozow commented Mar 7, 2022 •

edited

Loading

DrahtBot commented Mar 8, 2022 •

edited

Loading