Repository: Chia-Network/chia-blockchain
Pull request: Ms.fix coin selection
Two bugs :
1. `test_smallest_coin_over_amount` did not work properly when all coins where smaller than the amount.
2. In the cases where knapsack found a solution but it was too large, we fell back to selecting the "largest coin over the amount" as in issue 1, but instead we should be adding up the largest coins that are < the target amount first, because we might not have any large coins.

It also fixes a performance issue with knapsack, where it keeps searching even if we are selecting more coins than we can actually select.
Old performance with 200k coins:  60 seconds. New: 0.78 seconds.

A bunch of tests are added to test all the functionality.

Problem statement:
[Bug] Repeated timeout when trying to send XCH 
### What happened?

Attempting to send ~2 XCH from one wallet to another on Win10 Chia 1.4 and getting repeated timeouts on the Tx. 
EDIT: Amount accuracy 

Never had trouble with this on past versions. Any suggestions? Thanks.

### Version

1.4

### What platform are you using?

Windows

### What ui mode are you using?

GUI

### Relevant log output or stacktrace

```shell
2022-07-02T16:xxxxxx wallet chia.rpc.rpc_server        : WARNING  Error while handling message: Traceback (most recent call last):
  File "chia\rpc\rpc_server.py", line 229, in safe_handle
  File "chia\rpc\rpc_server.py", line 220, in ws_api
  File "chia\rpc\wallet_rpc_api.py", line 838, in send_transaction
  File "chia\wallet\wallet.py", line 432, in generate_signed_transaction
  File "chia\wallet\wallet.py", line 315, in _generate_unsigned_transaction
  File "chia\wallet\wallet.py", line 267, in select_coins
  File "chia\wallet\coin_selection.py", line 90, in select_coins
  File "chia\wallet\coin_selection.py", line 119, in select_smallest_coin_over_target
ValueError: Unable to select coins for this transaction. Try sending a smaller amount
```

Hints from issue discussion:
Reduced the amount to 1 XCH and same result. The spendable balance in the wallet is more than these amounts. 
I reduced the amount even further and it gave the same error (Timeout after 600 seconds), but the Tx actually went through. 
I confirm that I am also experiencing crashes of the wallet daemon when trying to send more than 1 XCH since upgrading to 1.4.0. When sending 1 XCH it has a success rate of about 50/50.
If you have many (thousands probably) of small coins that can add up to the total you need,  the knapsack algorithm may select this list of small coins, however, if that list of small coins is too many coins (more than 500) you can get this error even though you may have a set of coins that would work better - we are working on some fixes. This can happen if all your coins are smaller than the amount you are sending and some are fairly big (say 0.25 rewards) and many many are really small .
Being fixed by: https://github.com/Chia-Network/chia-blockchain/pull/12242
https://trello.com/c/6LyH2mDm/1563-coin-selection-bug-fix

Commit message: Add another test

Patch to review:
diff --git a/chia/wallet/coin_selection.py b/chia/wallet/coin_selection.py
index 92d950acc7c5..ea313e0f6e92 100644
--- a/chia/wallet/coin_selection.py
+++ b/chia/wallet/coin_selection.py
@@ -78,28 +78,33 @@ async def select_coins(
         log.debug(f"Selected all smaller coins because they equate to an exact match of the target.: {smaller_coins}")
         return set(smaller_coins)
     elif smaller_coin_sum < amount:
-        smallest_coin = select_smallest_coin_over_target(len(smaller_coins), valid_spendable_coins)
+        smallest_coin: Optional[Coin] = select_smallest_coin_over_target(amount, valid_spendable_coins)
+        assert smallest_coin is not None  # Since we know we have enough, there must be a larger coin
         log.debug(f"Selected closest greater coin: {smallest_coin.name()}")
         return {smallest_coin}
     elif smaller_coin_sum > amount:
-        coin_set = knapsack_coin_algorithm(smaller_coins, amount, max_coin_amount)
+        coin_set: Optional[Set[Coin]] = knapsack_coin_algorithm(smaller_coins, amount, max_coin_amount)
         log.debug(f"Selected coins from knapsack algorithm: {coin_set}")
         if coin_set is None:
             raise ValueError("Knapsack algorithm failed to find a solution.")
         if len(coin_set) > max_num_coins:
-            coin = select_smallest_coin_over_target(len(smaller_coins), valid_spendable_coins)
-            if coin is None or coin.amount < amount:
-                raise ValueError(
-                    f"Transaction of {amount} mojo would use more than "
-                    f"{max_num_coins} coins. Try sending a smaller amount"
-                )
-            coin_set = {coin}
+            coin_set = sum_largest_coins(amount, smaller_coins)
+            if coin_set is None or len(coin_set) > max_num_coins:
+                greater_coin = select_smallest_coin_over_target(amount, valid_spendable_coins)
+                if greater_coin is None:
+                    raise ValueError(
+                        f"Transaction of {amount} mojo would use more than "
+                        f"{max_num_coins} coins. Try sending a smaller amount"
+                    )
+                coin_set = {greater_coin}
         return coin_set
     else:
         # if smaller_coin_sum == amount and len(smaller_coins) >= max_num_coins.
-        coin = select_smallest_coin_over_target(len(smaller_coins), valid_spendable_coins)
-        log.debug(f"Resorted to selecting smallest coin over target due to dust.: {coin}")
-        return {coin}
+        potential_large_coin: Optional[Coin] = select_smallest_coin_over_target(amount, valid_spendable_coins)
+        if potential_large_coin is None:
+            raise ValueError("Too many coins are required to make this transaction")
+        log.debug(f"Resorted to selecting smallest coin over target due to dust.: {potential_large_coin}")
+        return {potential_large_coin}
 
 
 # These algorithms were based off of the algorithms in:
@@ -113,16 +118,15 @@ def check_for_exact_match(coin_list: List[Coin], target: uint64) -> Optional[Coi
     return None
 
 
-# amount of coins smaller than target, followed by a list of all valid spendable coins sorted in descending order.
-def select_smallest_coin_over_target(smaller_coin_amount: int, valid_spendable_coin_list: List[Coin]) -> Coin:
-    if smaller_coin_amount >= len(valid_spendable_coin_list):
-        raise ValueError("Unable to select coins for this transaction. Try sending a smaller amount")
-    if smaller_coin_amount > 0:  # in case we only have bigger coins.
-        greater_coins = valid_spendable_coin_list[:-smaller_coin_amount]
-    else:
-        greater_coins = valid_spendable_coin_list
-    coin = greater_coins[len(greater_coins) - 1]  # select the coin with the least value.
-    return coin
+# amount of coins smaller than target, followed by a list of all valid spendable coins.
+def select_smallest_coin_over_target(target: uint128, coin_list: List[Coin]) -> Optional[Coin]:
+    sorted_coin_list: List[Coin] = list(sorted(coin_list, key=lambda c: c.amount))
+    if sorted_coin_list[-1].amount < target:
+        return None
+    for coin in sorted_coin_list:
+        if coin.amount >= target:
+            return coin
+    assert False  # Should never reach here
 
 
 # we use this to find the set of coins which have total value closest to the target, but at least the target.
@@ -155,3 +159,17 @@ def knapsack_coin_algorithm(smaller_coins: List[Coin], target: uint128, max_coin
                             selected_coins.remove(coin)
             n_pass += 1
     return best_set_of_coins
+
+
+# Adds up the largest coins in the list, resulting in the minimum number of selected coins. A solution
+# is guaranteed if and only if the sum(coins) >= target.
+def sum_largest_coins(target: uint128, coins: List[Coin]) -> Optional[Set[Coin]]:
+    sorted_coins: List[Coin] = list(reversed(sorted(coins, key=lambda c: c.amount)))
+    total_value = 0
+    selected_coins: Set[Coin] = set()
+    for coin in sorted_coins:
+        total_value += coin.amount
+        selected_coins.add(coin)
+        if total_value >= target:
+            return selected_coins
+    return None
diff --git a/tests/wallet/test_coin_selection.py b/tests/wallet/test_coin_selection.py
index 71815ba25257..2f8a9f538457 100644
--- a/tests/wallet/test_coin_selection.py
+++ b/tests/wallet/test_coin_selection.py
@@ -9,7 +9,13 @@
 from chia.types.blockchain_format.sized_bytes import bytes32
 from chia.util.hash import std_hash
 from chia.util.ints import uint32, uint64, uint128
-from chia.wallet.coin_selection import check_for_exact_match, knapsack_coin_algorithm, select_coins
+from chia.wallet.coin_selection import (
+    check_for_exact_match,
+    knapsack_coin_algorithm,
+    select_coins,
+    select_smallest_coin_over_target,
+    sum_largest_coins,
+)
 from chia.wallet.util.wallet_types import WalletType
 from chia.wallet.wallet_coin_record import WalletCoinRecord
 
@@ -98,6 +104,7 @@ async def test_coin_selection_with_dust(self, a_hash: bytes32) -> None:
             )
         # make sure coins are not identical.
         for target_amount in [10000, 9999]:
+            print("Target amount: ", target_amount)
             result: Set[Coin] = await select_coins(
                 spendable_amount,
                 DEFAULT_CONSTANTS.MAX_COIN_AMOUNT,
@@ -132,6 +139,66 @@ async def test_coin_selection_with_dust(self, a_hash: bytes32) -> None:
                 assert coin.amount > 1
             assert len(dusty_result) <= 500
 
+        # test when we have multiple coins under target, and a lot of dust coins.
+        spendable_amount = uint128(25000 + 10000)
+        new_coin_list: List[WalletCoinRecord] = []
+        for i in range(5):
+            new_coin_list.append(
+                WalletCoinRecord(
+                    Coin(a_hash, std_hash(i), uint64(5000)), uint32(1), uint32(1), False, True, WalletType(0), 1
+                )
+            )
+
+        for i in range(10000):
+            new_coin_list.append(
+                WalletCoinRecord(
+                    Coin(a_hash, std_hash(i), uint64(1)), uint32(1), uint32(1), False, True, WalletType(0), 1
+                )
+            )
+        for target_amount in [20000, 15000, 10000, 5000]:  # select the first 100 values
+            dusty_below_target: Set[Coin] = await select_coins(
+                spendable_amount,
+                DEFAULT_CONSTANTS.MAX_COIN_AMOUNT,
+                new_coin_list,
+                {},
+                logging.getLogger("test"),
+                uint128(target_amount),
+            )
+            assert dusty_below_target is not None
+            assert sum([coin.amount for coin in dusty_below_target]) >= target_amount
+            for coin in dusty_below_target:
+                assert coin.amount == 5000
+            assert len(dusty_below_target) <= 500
+
+    @pytest.mark.asyncio
+    async def test_dust_and_one_large_coin(self, a_hash: bytes32) -> None:
+        # test when we have a lot of dust and 1 large coin
+        spendable_amount = uint128(50000 + 10000)
+        new_coin_list: List[WalletCoinRecord] = [
+            WalletCoinRecord(
+                Coin(a_hash, std_hash(b"123"), uint64(50000)), uint32(1), uint32(1), False, True, WalletType(0), 1
+            )
+        ]
+
+        for i in range(10000):
+            new_coin_list.append(
+                WalletCoinRecord(
+                    Coin(a_hash, std_hash(i), uint64(1)), uint32(1), uint32(1), False, True, WalletType(0), 1
+                )
+            )
+        for target_amount in [50000, 10001, 10000, 9999]:
+            dusty_below_target: Set[Coin] = await select_coins(
+                spendable_amount,
+                DEFAULT_CONSTANTS.MAX_COIN_AMOUNT,
+                new_coin_list,
+                {},
+                logging.getLogger("test"),
+                uint128(target_amount),
+            )
+            assert dusty_below_target is not None
+            assert sum([coin.amount for coin in dusty_below_target]) >= target_amount
+            assert len(dusty_below_target) <= 500
+
     @pytest.mark.asyncio
     async def test_coin_selection_failure(self, a_hash: bytes32) -> None:
         spendable_amount = uint128(10000)
@@ -288,3 +355,52 @@ async def test_coin_selection(self, a_hash: bytes32) -> None:
         assert sum([coin.amount for coin in multiple_greater_result]) > target_amount
         assert sum([coin.amount for coin in multiple_greater_result]) == 90000
         assert len(multiple_greater_result) == 1
+
+    @pytest.mark.asyncio
+    async def test_coin_selection_difficult(self, a_hash: bytes32) -> None:
+        num_coins = 40
+        spendable_amount = uint128(num_coins * 1000)
+        coin_list: List[WalletCoinRecord] = [
+            WalletCoinRecord(
+                Coin(a_hash, std_hash(i.to_bytes(4, "big")), uint64(1000)),
+                uint32(1),
+                uint32(1),
+                False,
+                True,
+                WalletType(0),
+                1,
+            )
+            for i in range(num_coins)
+        ]
+        target_amount = (num_coins) * 1000 - 1
+        result: Set[Coin] = await select_coins(
+            spendable_amount,
+            DEFAULT_CONSTANTS.MAX_COIN_AMOUNT,
+            coin_list,
+            {},
+            logging.getLogger("test"),
+            uint128(target_amount),
+        )
+        assert result is not None
+        print(result)
+        print(sum([c.amount for c in result]))
+        assert sum([coin.amount for coin in result]) >= target_amount
+
+    @pytest.mark.asyncio
+    async def test_smallest_coin_over_amount(self, a_hash: bytes32) -> None:
+        coin_list: List[Coin] = [
+            Coin(a_hash, std_hash(i.to_bytes(4, "big")), uint64((39 - i) * 1000)) for i in range(40)
+        ]
+        assert select_smallest_coin_over_target(uint128(100), coin_list) == coin_list[39 - 1]
+        assert select_smallest_coin_over_target(uint128(1000), coin_list) == coin_list[39 - 1]
+        assert select_smallest_coin_over_target(uint128(1001), coin_list) == coin_list[39 - 2]
+        assert select_smallest_coin_over_target(uint128(37000), coin_list) == coin_list[39 - 37]
+        assert select_smallest_coin_over_target(uint128(39000), coin_list) == coin_list[39 - 39]
+        assert select_smallest_coin_over_target(uint128(39001), coin_list) is None
+
+    @pytest.mark.asyncio
+    async def test_sum_largest_coins(self, a_hash: bytes32) -> None:
+        coin_list: List[Coin] = [Coin(a_hash, std_hash(i.to_bytes(4, "big")), uint64(i)) for i in range(41)]
+        assert sum_largest_coins(uint128(40), coin_list) == {coin_list[40]}
+        assert sum_largest_coins(uint128(79), coin_list) == {coin_list[40], coin_list[39]}
+        assert sum_largest_coins(uint128(40000), coin_list) is None


Code review comments:
diff_hunk: @@ -288,3 +355,52 @@ async def test_coin_selection(self, a_hash: bytes32) -> None:
         assert sum([coin.amount for coin in multiple_greater_result]) > target_amount
         assert sum([coin.amount for coin in multiple_greater_result]) == 90000
         assert len(multiple_greater_result) == 1
+
+    @pytest.mark.asyncio
+    async def test_coin_selection_difficult(self, a_hash: bytes32) -> None:
+        num_coins = 40
+        spendable_amount = uint128(num_coins * 1000)
+        coin_list: List[WalletCoinRecord] = [
+            WalletCoinRecord(
+                Coin(a_hash, std_hash(i.to_bytes(4, "big")), uint64(1000)),
+                uint32(1),
+                uint32(1),
+                False,
+                True,
+                WalletType(0),
+                1,
+            )
+            for i in range(num_coins)
+        ]
+        target_amount = (num_coins) * 1000 - 1
path: tests/wallet/test_coin_selection.py
text: @user1:
could this just be `target_amount = spendable_amount -1`?