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

pull glozow wants to merge 4 commits into bitcoin:master from glozow:2022-03-minchange changing 8 files +157 −92
  1. glozow commented at 2:52 pm on March 7, 2022: member

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

  2. glozow added the label Privacy on Mar 7, 2022
  3. glozow added the label Wallet on Mar 7, 2022
  4. glozow force-pushed on Mar 7, 2022
  5. DrahtBot commented at 0:20 am on March 8, 2022: contributor

    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.

  6. in src/wallet/spend.cpp:397 in 6d803e5161 outdated 
    396     }
397 
398-    // We include the minimum final change for SRD as we do want to avoid making really small change.
399-    // KnapsackSolver does not need this because it includes MIN_CHANGE internally.
400-    const CAmount srd_target = nTargetValue + coin_selection_params.m_change_fee + MIN_FINAL_CHANGE;
401+    const CAmount srd_target = nTargetValue + coin_selection_params.m_change_fee + coin_selection_params.m_change_target;
    S3RK commented at 8:14 am on March 8, 2022:

    I think we should rather keep CHANGE_LOWER here.

    SRD doesn’t optimise to match the target so it couldn’t be exploited for fingerprinting. On the other hand raising lower bound for change will reduce amount of solutions found by SRD.

    glozow commented at 11:36 am on March 9, 2022:
    Ah that’s a good point.
  7. glozow force-pushed on Mar 8, 2022
  8. glozow commented at 1:55 pm on March 8, 2022: member
    Ok fixed the wallet_bumpfee.py break.
  9. glozow marked this as ready for review on Mar 8, 2022
  10. glozow requested review from achow101 on Mar 8, 2022
  11. glozow commented at 1:55 pm on March 8, 2022: member
    cc @Xekyo
  12. in test/functional/wallet_bumpfee.py:446 in a653b8438f outdated 
    441@@ -442,7 +442,8 @@ def test_watchonly_psbt(self, peer_node, rbf_node, dest_address):
442     self.generate(peer_node, 1)
443 
444     # Create single-input PSBT for transaction to be bumped
445-    psbt = watcher.walletcreatefundedpsbt([], {dest_address: 0.0005}, 0, {"fee_rate": 1}, True)['psbt']
446+    # Ensure the payment amount + change can be fully funded using one of the 0.001BTC inputs.
447+    psbt = watcher.walletcreatefundedpsbt([], {dest_address: 0.0003}, 0, {"fee_rate": 1}, True)['psbt']
    achow101 commented at 3:39 pm on March 8, 2022:

    In a653b8438f5784362c061d96128419268c65c7dc “[wallet] randomly generate change target, remove MIN_CHANGE”

    If we only want one input, I would strongly prefer that we just specify one input to use rather than hoping that coin selection chooses only one input. It is okay to do that on this line as this is just setting up for the test a few lines later.

    0    psbt = watcher.walletcreatefundedpsbt([watcher.listunspent()[0]], {dest_address: 0.0005}, 0, {"fee_rate": 1, "add_inputs": False}, True)['psbt']
    glozow commented at 4:02 pm on March 8, 2022:
    Ah that’s much cleaner! Done
  13. glozow force-pushed on Mar 8, 2022
  14. S3RK commented at 8:55 am on March 9, 2022: contributor

    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?

  15. glozow commented at 11:35 am on March 9, 2022: member

    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.

  16. in src/wallet/coinselection.cpp:405 in 6490a74eeb outdated 
    399@@ -384,6 +400,19 @@ CAmount GetSelectionWaste(const std::set<CInputCoin>& inputs, CAmount change_cos
400     return waste;
401 }
402 
403+CAmount GenerateChangeTarget(CAmount payment_value)
404+{
405+    FastRandomContext rng;
    MarcoFalke commented at 12:34 pm on March 9, 2022:
    Might be good to use only one rng for coin selection to make mocking and testing easier. Obviously not in this pull, but for now you can at least pass it in to this function?
    glozow commented at 1:44 pm on March 9, 2022:
    Nice. good first issue?
    MarcoFalke commented at 2:29 pm on March 14, 2022:
    #24560 :sweat_smile:
  17. glozow force-pushed on Mar 9, 2022
  18. glozow commented at 2:11 pm on March 9, 2022: member
    Set SRD change target to CHANGE_LOWER and added rng as a parameter to GenerateChangeTarget()
  19. in src/qt/coincontroldialog.cpp:489 in 3173930d74 outdated 
    484@@ -486,7 +485,7 @@ void CoinControlDialog::updateLabels(CCoinControl& m_coin_control, WalletModel *
485                 nChange -= nPayFee;
486 
487             // Never create dust outputs; if we would, just add the dust to the fee.
488-            if (nChange > 0 && nChange < MIN_CHANGE)
    promag commented at 10:20 pm on March 9, 2022:

    3173930d74a2e8ed74884e95ccb66ce0f9f38b4f

    nit, could make this change on a separate commit since it is unrelated to the randomized change target.

    glozow commented at 12:40 pm on March 10, 2022:
    Done
  20. in src/wallet/coinselection.h:229 in 3173930d74 outdated 
    201@@ -200,6 +202,15 @@ struct OutputGroup
202  */
203 [[nodiscard]] CAmount GetSelectionWaste(const std::set<CInputCoin>& inputs, CAmount change_cost, CAmount target, bool use_effective_value = true);
204 
205+
206+/** Chooose a random change target for each transaction to make it harder to fingerprint the Core
    promag commented at 10:52 pm on March 9, 2022:

    3173930d74a2e8ed74884e95ccb66ce0f9f38b4f

    nit, typo “Chooose”.

    Do you mind explaining how you got to this approach?

    MarcoFalke commented at 7:42 am on March 10, 2022:
    See discussion in #24458
    glozow commented at 12:40 pm on March 10, 2022:
    Elaborated on the reasoning in the doxygen comment.
    promag commented at 1:26 pm on March 10, 2022:
    Maybe just add a reference to the issue?
    MarcoFalke commented at 1:29 pm on March 10, 2022:
    I don’t think it is beneficial to devs to have to follow a link in the browser, leave the source code, and then read a discussion thread to understand the code. A code comment seems preferable.
  21. in src/wallet/test/coinselector_tests.cpp:169 in 3173930d74 outdated 
    164@@ -165,7 +165,9 @@ inline std::vector<OutputGroup>& GroupCoins(const std::vector<COutput>& coins)
165 inline std::vector<OutputGroup>& KnapsackGroupOutputs(const std::vector<COutput>& coins, CWallet& wallet, const CoinEligibilityFilter& filter)
166 {
167     CoinSelectionParams coin_selection_params(/* change_output_size= */ 0,
168-                                              /* change_spend_size= */ 0, /* effective_feerate= */ CFeeRate(0),
169+                                              /* change_spend_size= */ 0,
170+                                              /*change_target=*/ CENT,
    promag commented at 10:53 pm on March 9, 2022:

    3173930d74a2e8ed74884e95ccb66ce0f9f38b4f

    nit, spaces? below too.

    glozow commented at 9:23 am on March 10, 2022:

    I’ve been trying to format for clang-tidy since seeing #23545 :sweat_smile:

    I’m not super attached to it though, and I understand that the formatting would be inconsistent here. Happy to add spaces if you feel like it’s better

    promag commented at 1:24 pm on March 10, 2022:
    nah don’t bother
  22. promag commented at 11:05 pm on March 9, 2022: member
    Concept ACK.
  23. glozow force-pushed on Mar 10, 2022
  24. glozow commented at 12:45 pm on March 10, 2022: member
    Added release notes, docs for GenerateChangeTarget, and separate commit for removing MIN_CHANGE
  25. in doc/release-notes-24494.md:5 in 53a30b5466 outdated 
    0@@ -0,0 +1,8 @@
1+
2+To help prevent fingerprinting transactions created by the Bitcoin Core wallet, the default change
3+target (MIN\_CHANGE or 1,000,000sat) has been removed. When creating a transaction, if a change
4+output is to be created, the wallet now picks a random amount to target within a range based on the
5+average payment value:
    MarcoFalke commented at 1:14 pm on March 10, 2022:
    I think users that are interested in the exact algorithm can read the source code. Otherwise this will just bloat the release notes.
    glozow commented at 1:30 pm on March 10, 2022:
    i guess the intention was to specify the bounds. I’ll remove
  26. achow101 commented at 1:14 pm on March 10, 2022: member
    The code changes look fine but I would like to run a simulation first to see how it affects our coin selection strategies.
  27. glozow force-pushed on Mar 10, 2022
  28. achow101 requested review from murchandamus on Mar 11, 2022
  29. murchandamus commented at 2:38 pm on March 15, 2022: contributor
    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.
  30. in src/wallet/coinselection.cpp:196 in 0a25b209b2 outdated 
    188@@ -189,11 +189,23 @@ std::optional<SelectionResult> SelectCoinsSRD(const std::vector<OutputGroup>& ut
189     return std::nullopt;
190 }
191 
192+/** Find a subset of the OutputGroups that is at least as large as, but as close as possible to, the
193+ * target amount; solve subset sum.
194+ * param@[in]   groups          OutputGroups to choose from, sorted by value in descending order.
195+ * param@[in]   nTotalLower     Total (effective) value of the UTXOs in groups.
196+ * param@[in]   nTargetValue    Subset sum target.
    murchandamus commented at 6:11 pm on March 15, 2022:
    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.
    glozow commented at 1:15 pm on March 23, 2022:
    Done
  31. in src/wallet/coinselection.cpp:407 in 7e8186c234 outdated 
    399@@ -400,6 +400,18 @@ CAmount GetSelectionWaste(const std::set<CInputCoin>& inputs, CAmount change_cos
400     return waste;
401 }
402 
403+CAmount GenerateChangeTarget(CAmount payment_value, FastRandomContext& rng)
404+{
405+    if (payment_value < CHANGE_LOWER / 2) {
406+        // random value between payment_value and 50ksat
407+        return rng.randrange(CHANGE_LOWER - payment_value) + payment_value;
    murchandamus commented at 8:37 pm on March 15, 2022:

    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.

    glozow commented at 1:15 pm on March 23, 2022:
    Changed to CHANGE_LOWER when the payment amount is less than 25k
  32. in src/wallet/coinselection.cpp:401 in 7e8186c234 outdated 
    399@@ -400,6 +400,18 @@ CAmount GetSelectionWaste(const std::set<CInputCoin>& inputs, CAmount change_cos
400     return waste;
401 }
402 
403+CAmount GenerateChangeTarget(CAmount payment_value, FastRandomContext& rng)
    murchandamus commented at 8:40 pm on March 15, 2022:
    How would this function be used for transactions enacting multiple payments at once? Perhaps we should keep track of the smallest and largest recipient here? – Never mind, I learned below that you thought of that already and propose to use the average of the payment amounts.
    glozow commented at 1:16 pm on March 23, 2022:
    Yeah, I think average payment makes the most sense so I used that
  33. in src/wallet/coinselection.h:113 in 7e8186c234 outdated 
    109@@ -100,10 +110,11 @@ struct CoinSelectionParams
110      * reuse. Dust outputs are not eligible to be added to output groups and thus not considered. */
111     bool m_avoid_partial_spends = false;
112 
113-    CoinSelectionParams(size_t change_output_size, size_t change_spend_size, CFeeRate effective_feerate,
114+    CoinSelectionParams(size_t change_output_size, size_t change_spend_size, CAmount change_target, CFeeRate effective_feerate,
    murchandamus commented at 9:07 pm on March 15, 2022:
    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.
    glozow commented at 1:16 pm on March 23, 2022:
    Changed to min_change_target everywhere. The comment above the member should hopefully be pretty clear.
  34. in src/qt/coincontroldialog.cpp:487 in 45ac3b1d85 outdated 
    484@@ -486,7 +485,7 @@ void CoinControlDialog::updateLabels(CCoinControl& m_coin_control, WalletModel *
485                 nChange -= nPayFee;
486 
487             // Never create dust outputs; if we would, just add the dust to the fee.
    murchandamus commented at 9:25 pm on March 15, 2022:
    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?
  35. murchandamus commented at 10:02 pm on March 15, 2022: contributor
    Looks very good, thanks for taking this up so quickly.
  36. achow101 commented at 10:32 pm on March 15, 2022: member

    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
  37. murchandamus commented at 3:11 pm on March 21, 2022: contributor
    As mentioned in person, I think it would be interesting to see the simulation repeated multiple times, given that it’s partially driven by random behavior. @achow101 and I have also been collaborating on some improvements to the simulation, given an investigation of the results and some concerns about its representability for actual wallet situations.
  38. murchandamus commented at 5:45 pm on March 21, 2022: contributor

    Here’s a result of ten runs of master and ten runs of #24494:

    Random min change
    Scenario File 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
    sim_data.csv 15.51711248 124.125512167 54 4065 11174 7893 1 7162 731 4.039E-05 274.97911422 13.4243308484 39.4756675519 0.44573085 5.64716647662E-05 -3.672E-05 0.44569413 1 92 1.41568478399 2.23559017584 731 1586 5576 731 0 0
    sim_data.csv 15.53285769 112.780500042 61 4065 11135 7893 3 7130 763 1.814E-05 256.54571999 12.3689351608 39.4568243737 0.44477681 5.63507931078E-05 -4.148E-05 0.44473533 1 122 1.41074369695 2.45415049552 763 1598 5532 763 0 0
    sim_data.csv 15.5166763 119.792457563 47 4065 11185 7893 8 7166 727 4.209E-05 274.81338985 15.9946753063 45.4619717938 0.44616703 5.65269263905E-05 -3.196E-05 0.44613507 1 79 1.41707842392 2.14304051154 726 1601 5566 726 0 1
    sim_data.csv 15.53290023 115.786520612 36 4065 11186 7893 2 7156 737 4.565E-05 275.00812031 12.7406297702 40.0372419661 0.44473427 5.63454035221E-05 -2.448E-05 0.44470979 1 100 1.41720511846 2.44957104825 736 1603 5554 736 0 1
    sim_data.csv 15.53399549 117.093820554 49 4065 11136 7893 2 7119 774 2.863E-05 256.54571999 12.6081304563 37.4846184589 0.44363901 5.62066400608E-05 -3.332E-05 0.44360569 1 101 1.41087039149 2.34608697415 773 1529 5591 773 0 1
    sim_data.csv 15.53567698 117.222175767 38 4065 11161 7893 0 7133 760 2.493E-05 389.61052145 15.4484914805 43.3340961965 0.44195752 5.59936044596E-05 -2.584E-05 0.44193168 1 100 1.41403775497 2.41471153691 759 1505 5629 759 0 1
    sim_data.csv 15.53292613 116.022911615 38 4065 11147 7893 0 7119 774 3.709E-05 270.2899162 12.1733817628 41.5118773018 0.44470837 5.63421221335E-05 -2.584E-05 0.44468253 1 96 1.41226403142 2.16010493382 774 1778 5341 774 0 0
    sim_data.csv 15.53261885 118.037544945 39 4065 11150 7893 0 7123 770 1.874E-05 256.54571999 12.8142199682 39.982547796 0.44501565 5.63810528316E-05 -2.652E-05 0.44498913 1 102 1.41264411504 2.26704888755 770 1539 5584 770 0 0
    sim_data.csv 15.51531364 110.048666276 30 4065 11205 7893 5 7169 724 4.979E-05 274.97688826 10.8623395526 36.8756392858 0.44752969 5.66995679716E-05 -2.04E-05 0.44750929 1 100 1.41961231471 2.2142652517 724 1895 5274 724 0 0
    sim_data.csv 15.53285732 122.16924492 57 4065 11160 7893 1 7151 742 3.966E-05 236.25291481 13.1360351135 37.8831307331 0.44477718 5.63508399848E-05 -3.876E-05 0.44473842 1 100 1.41391106043 2.34106427223 742 1408 5743 742 0 0
    Average 15.528293511 117.3079354461 44.9 4065 11163.9 7893 2.2 7142.8 750.2 3.4511E-05 276.556802507 13.15711694196 40.15036154576 0.444903638 5.636686152285E-05 -3.0532E-05 0.444873106 1 99.2 1.414405169138 2.302563408751 749.8 1604.2 5539 749.8 0 0.4
    MASTER
    Scenario File 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
    sim_data.csv 15.53400826 132.677815871 66 4065 11161 7893 2 7161 732 7.026E-05 256.54571999 14.5121417883 42.0967686404 0.44362624 5.62050221715E-05 -4.488E-05 0.44358136 1 96 1.41403775497 2.25735618498 732 1806 5355 732 0 0
    sim_data.csv 15.51592855 118.283635755 26 4065 11236 7893 0 7196 697 1.148E-05 273.3206638 15.4558271243 43.5390959423 0.44691478 5.66216622324E-05 -1.768E-05 0.4468971 1 100 1.42353984543 2.27391570594 697 1809 5387 697 0 0
    sim_data.csv 15.53294166 126.235554812 73 4065 11167 7893 3 7174 719 8.942E-05 265.79855963 17.5077775295 44.5299095347 0.44469284 5.63401545673E-05 -4.964E-05 0.4446432 1 102 1.41479792221 2.26024590617 719 1716 5458 719 0 0
    sim_data.csv 15.53330097 120.750898905 26 4065 11217 7893 2 7177 716 7.585E-05 274.85415613 17.0800836478 45.0173828483 0.44433353 5.62946319524E-05 -1.768E-05 0.44431585 1 100 1.42113264918 2.40427887368 715 1825 5353 715 0 1
    sim_data.csv 15.51545201 126.814282131 38 4065 11233 7893 3 7205 688 2.396E-05 273.32009803 17.2787685832 45.7371541282 0.44739132 5.66820372482E-05 -2.584E-05 0.44736548 1 101 1.42315976181 2.39864609544 688 1853 5352 688 0 0
    sim_data.csv 15.51633457 119.979011623 63 4065 11198 7893 6 7195 698 1.153E-05 275.00459992 16.6380544625 45.1544445389 0.44650876 5.65702217154E-05 -4.284E-05 0.44646592 1 90 1.41872545293 2.21612050976 698 1772 5423 698 0 0
    sim_data.csv 15.5346199 133.958692198 51 4065 11154 7893 1 7139 754 5.462E-05 273.54581866 14.3841888847 42.1005536847 0.4430146 5.61275307234E-05 -3.468E-05 0.44297992 1 100 1.4131508932 2.33116447132 754 1814 5325 754 0 0
    sim_data.csv 15.5344172 128.32987708 56 4065 11151 7893 1 7141 752 3.009E-05 271.5924155 17.3977889218 46.811431865 0.4432173 5.61532117066E-05 -3.808E-05 0.44317922 1 101 1.41277080958 2.35682767359 751 1775 5367 751 0 1
    sim_data.csv 15.51801192 125.234635003 40 4065 11207 7893 3 7181 712 1.153E-05 273.44079115 14.155185078 38.8092770407 0.44483141 5.63577106297E-05 -2.72E-05 0.44480421 1 107 1.41986570379 2.38948758516 712 2004 5177 712 0 0
    sim_data.csv 15.51698267 132.335145079 25 4065 11190 7893 3 7149 744 2.153E-05 274.07103179 18.2783060038 46.0450921958 0.44586066 5.64881109844E-05 -1.7E-05 0.44584366 1 101 1.41771189662 2.27716478483 743 1734 5416 743 0 1
    Average 15.525199771 126.4599548457 46.4 4065 11191.4 7893 2.4 7171.8 721.2 4.0027E-05 271.14938546 16.26881220239 43.9841110419 0.445039144 5.638402939313E-05 -3.1552E-05 0.445007592 1 99.8 1.417889268972 2.316520779087 720.9 1810.8 5361.3 720.9 0 0.3

    Data by @achow101

  39. murchandamus commented at 5:50 pm on March 21, 2022: contributor

    Result is that #24494 has smaller average UTXO pool, 3.8% more changeless transactions, negligible decrease in total cost… but also more Knapsack uses (probably due to lowest_larger being used more often, because the change is now smaller).

    Given that the main motivation was a privacy improvement, and the other metrics also are benign or improved, this is an overall improvement in the coin selection behavior.

  40. MarcoFalke commented at 8:12 am on March 22, 2022: member
    I don’t expect a lot to change, but maybe the benchmarks should be run (again) after #24494 (review) is addressed?
  41. glozow force-pushed on Mar 23, 2022
  42. glozow commented at 1:19 pm on March 23, 2022: member
    Thanks, addressed @Xekyo’s review comments.
  43. in src/wallet/coinselection.cpp:405 in 57c035b4b1 outdated 
    399@@ -384,6 +400,17 @@ CAmount GetSelectionWaste(const std::set<CInputCoin>& inputs, CAmount change_cos
400     return waste;
401 }
402 
403+CAmount GenerateChangeTarget(CAmount payment_value, FastRandomContext& rng)
404+{
405+    if (payment_value < CHANGE_LOWER / 2) {
    MarcoFalke commented at 2:07 pm on March 23, 2022:

    :rotating_light:

    This crashes the node

    0    if (payment_value <= CHANGE_LOWER / 2) {

    0bitcoin-qt: ./random.h:204: uint64_t FastRandomContext::randrange(uint64_t): Assertion `range' failed.
1Aborted (core dumped)
    glozow commented at 2:23 pm on March 23, 2022:
    Oops, fixed.
  44. glozow force-pushed on Mar 23, 2022
  45. in src/qt/coincontroldialog.cpp:488 in 762f0540ed outdated 
    483@@ -485,11 +484,11 @@ void CoinControlDialog::updateLabels(CCoinControl& m_coin_control, WalletModel *
484             if (!CoinControlDialog::fSubtractFeeFromAmount)
485                 nChange -= nPayFee;
486 
487-            // Never create dust outputs; if we would, just add the dust to the fee.
488-            if (nChange > 0 && nChange < MIN_CHANGE)
489+            if (nChange > 0)
490             {
    MarcoFalke commented at 2:27 pm on March 23, 2022:
    nit in commit 762f0540ed009e5597a923ead557e17941d5e351: You can remove the newline after the if. (Only if you need to touch this branch again for other reasons).
    glozow commented at 12:14 pm on March 24, 2022:
    Done
  46. MarcoFalke approved
  47. DrahtBot added the label Needs rebase on Mar 23, 2022
  48. in src/wallet/spend.cpp:666 in 3e779e7de3 outdated 
    661@@ -662,6 +662,8 @@ static bool CreateTransactionInternal(
662             coin_selection_params.m_subtract_fee_outputs = true;
663         }
664     }
665+    FastRandomContext rng;
666+    coin_selection_params.m_change_target = GenerateChangeTarget(std::floor(recipients_sum / vecSend.size()), rng);
    MarcoFalke commented at 8:23 am on March 24, 2022:

    nit: (After rebase)

    0
1    coin_selection_params.m_change_target = GenerateChangeTarget(std::floor(recipients_sum / vecSend.size()), rng_fast);
    glozow commented at 12:13 pm on March 24, 2022:
    Done, thanks for the reminder
  49. glozow force-pushed on Mar 24, 2022
  50. glozow force-pushed on Mar 24, 2022
  51. glozow commented at 12:14 pm on March 24, 2022: member
    Rebased + addressed @MarcoFalke’s comments
  52. DrahtBot removed the label Needs rebase on Mar 24, 2022
  53. murchandamus approved
  54. murchandamus commented at 8:56 pm on March 24, 2022: contributor
    ACK e75c8dd14d0988c1bf4594105de905c2c444b530
  55. DrahtBot added the label Needs rebase on Mar 24, 2022
  56. refactor coin selection for parameterizable change target 
    no behavior changes, since the target is always MIN_CHANGE
    1e52e6bd0a
  57. [wallet] randomly generate change targets 
    If the wallet always chooses 1 million sats as its change target, it is
easier to fingerprint transactions created by the Core wallet.
    a44236addd
  58. [wallet] remove MIN_CHANGE 46f2fed6c5
  59. [doc] release notes for random change target 9053f64fcb
  60. glozow force-pushed on Mar 25, 2022
  61. DrahtBot removed the label Needs rebase on Mar 25, 2022
  62. glozow commented at 1:47 pm on March 25, 2022: member
    Rebased for #24091. The CI failure is the “AssertionError: Fee of 0.00003160 BTC too high!” error from wallet_send.py, unrelated
  63. achow101 commented at 3:35 pm on March 25, 2022: member
    ACK 9053f64fcbd26d87c26ae6b982d17756a6ea0896
  64. murchandamus approved
  65. murchandamus commented at 5:12 pm on March 25, 2022: contributor
    reACK 9053f64fcbd26d87c26ae6b982d17756a6ea0896
  66. fanquake merged this on Mar 25, 2022
  67. fanquake closed this on Mar 25, 2022
  68. glozow deleted the branch on Mar 30, 2022
  69. bitcoin deleted a comment on Aug 12, 2022
  70. MarcoFalke commented at 6:20 am on August 12, 2022: member
    The pull request description is outdated/wrong. The correct description can be found in the docstring of GenerateChangeTarget
  71. glozow commented at 9:43 am on August 12, 2022: member

    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.

  72. t-bast referenced this in commit 3510ee58c7 on Jul 13, 2023
  73. bitcoin locked this on Aug 12, 2023


glozow DrahtBot S3RK achow101 MarcoFalke promag murchandamus

Labels
Wallet Privacy

github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin/bitcoin. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2024-11-21 09:12 UTC
This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me