test: cover GenerateChangeTarget range and distribution #36732

To protect privacy, the wallet picks a random target for the change output (#24494), inside a set range that is fixed for very small payments, otherwise random between CHANGE_LOWER and min(2 × payment, CHANGE_UPPER). This function has no unit test at all. You could widen the range, or make it not random anymore, and every test would still pass. This PR adds a unit test to the function GenerateChangeTarget

<details> <summary>Mutations tested against the added unit test</summary>

• Boundary change
• Dropped change fee
• Wrong randrange
• Skewed distribution
• Halved upper cap

</details>

<!--e57a25ab6845829454e8d69fc972939a-->

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

<!--006a51241073e994b41acfe9ec718e94-->

External sites

• Code coverage & benchmarks: https://corecheck.dev/bitcoin/bitcoin/pulls/36732
• Ralph review <img src=https://review.fish.foo/assets/bitcoin/bitcoin/36732.png alt="Ralph review status"> https://git.fish.foo/bitcoin/bitcoin/pulls/36732#author-ralph

<!--021abf342d371248e50ceaed478a90ca-->

Reviews

See the guideline and AI policy for information on the review process. A summary of reviews will appear here.

<!--5faf32d7da4f0f540f40219e4f7537a3-->

Can you please share the git diff of the mutants? It would facilitate the review.

Can you please share the git diff of the mutants? It would facilitate the review.

Definitely

After the unit test with the original function <img width="1914" height="356" alt="image" src="https://github.com/user-attachments/assets/fe4ab44c-1229-4976-9945-94b155cb6e12" />

Boundary change

diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp
index 51c5064787..3a11309495 100644
--- a/src/wallet/coinselection.cpp
+++ b/src/wallet/coinselection.cpp
@@ -882,7 +882,7 @@ void OutputGroupTypeMap::Push(const OutputGroup& group, OutputType type, bool in
 
 CAmount GenerateChangeTarget(const CAmount payment_value, const CAmount change_fee, FastRandomContext& rng)
 {
-    if (payment_value <= CHANGE_LOWER / 2) {
+    if (payment_value < CHANGE_LOWER / 2) {
         return change_fee + CHANGE_LOWER;
     } else {
         // random value between 50ksat and min (payment_value * 2, 1milsat)

<details> <summary>Result</summary> <img width="1914" height="396" alt="image" src="https://github.com/user-attachments/assets/83717f48-2c44-4975-b997-327adefdaaed" /> </details>

Dropped change fee

diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp
index 51c5064787..daac915b9f 100644
--- a/src/wallet/coinselection.cpp
+++ b/src/wallet/coinselection.cpp
@@ -887,7 +887,7 @@ CAmount GenerateChangeTarget(const CAmount payment_value, const CAmount change_f
     } else {
         // random value between 50ksat and min (payment_value * 2, 1milsat)
         const auto upper_bound = std::min(payment_value * 2, CHANGE_UPPER);
-        return change_fee + rng.randrange(upper_bound - CHANGE_LOWER) + CHANGE_LOWER;
+        return rng.randrange(upper_bound - CHANGE_LOWER) + CHANGE_LOWER;
     }
 }

<details> <summary>Result</summary> <img width="1928" height="596" alt="image" src="https://github.com/user-attachments/assets/ed8c6ffb-953c-41a9-bafa-40d2a86429ec" /> </details>

Wrong randrange

diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp
index 51c5064787..c19e2d4512 100644
--- a/src/wallet/coinselection.cpp
+++ b/src/wallet/coinselection.cpp
@@ -887,7 +887,7 @@ CAmount GenerateChangeTarget(const CAmount payment_value, const CAmount change_f
     } else {
         // random value between 50ksat and min (payment_value * 2, 1milsat)
         const auto upper_bound = std::min(payment_value * 2, CHANGE_UPPER);
-        return change_fee + rng.randrange(upper_bound - CHANGE_LOWER) + CHANGE_LOWER;
+        return change_fee + rng.randrange(upper_bound) + CHANGE_LOWER;
     }
 }

<details> <summary>Result</summary> <img width="1908" height="756" alt="image" src="https://github.com/user-attachments/assets/b749a8ac-85d2-43dd-9716-c78177127352" /> </details>

Skewed distribution

diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp
index 51c5064787..9e8ad0e76c 100644
--- a/src/wallet/coinselection.cpp
+++ b/src/wallet/coinselection.cpp
@@ -887,7 +887,8 @@ CAmount GenerateChangeTarget(const CAmount payment_value, const CAmount change_f
     } else {
         // random value between 50ksat and min (payment_value * 2, 1milsat)
         const auto upper_bound = std::min(payment_value * 2, CHANGE_UPPER);
-        return change_fee + rng.randrange(upper_bound - CHANGE_LOWER) + CHANGE_LOWER;
+        const auto range = upper_bound - CHANGE_LOWER;
+        return change_fee + std::min(rng.randrange(range), rng.randrange(range)) + CHANGE_LOWER;
     }
 }

<details> <summary>Result</summary> <img width="1928" height="596" alt="image" src="https://github.com/user-attachments/assets/ed8c6ffb-953c-41a9-bafa-40d2a86429ec" /> </details>

Halved upper cap

diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp
index 51c5064787..68aaa78f2c 100644
--- a/src/wallet/coinselection.cpp
+++ b/src/wallet/coinselection.cpp
@@ -886,7 +886,7 @@ CAmount GenerateChangeTarget(const CAmount payment_value, const CAmount change_f
         return change_fee + CHANGE_LOWER;
     } else {
         // random value between 50ksat and min (payment_value * 2, 1milsat)
-        const auto upper_bound = std::min(payment_value * 2, CHANGE_UPPER);
+        const auto upper_bound = std::min(payment_value * 2, CHANGE_UPPER / 2);
         return change_fee + rng.randrange(upper_bound - CHANGE_LOWER) + CHANGE_LOWER;
     }
 }

<details> <summary>Result</summary> <img width="1932" height="526" alt="image" src="https://github.com/user-attachments/assets/28e87429-11e3-4e98-bf3a-b4b61514982a" /> </details>

I have enumerated all the changes I made to the GenerateChangeTarget as requested by @brunoerg

Image? Really?

Apologies, I have edited accordingly