This issue will be delivered in at least 2 PRs:

1. Add ability to store coins to spend in an sorted way
2. Leverage the fact that coins are sorted in the selection algorithm

How to achieve pt. 1:

1. We'll use two DBs/columns:
   1. main_db - the current one
   2. index_db - the new, indexation DB
2. Use the separate DB/column to build an "reverse lookup index" which will use the RocksDB key sorting capabilities
   1. RocksDB uses lexicographical sort
   2. To maintain the ordering, the integer representing the amount will be converted to big-endian bytes
   3. Each entry will have a key USER|ASSET[^3]|AMOUNT, and value is going to be a key from the main_db
      • this will allow querying by USER|ASSET prefix, getting all coins in sorted order
      • TODO [needed, useful?]: Add ability to retrieve only coins "not greater" and/or "not less" than X
3. To solve the conflicts (for example: user has two coins with same value for the same asset ID), each coin entry will have an unique suffix (utxo_id). This suffix will also be used to quickly exclude coins.

Example DB structure:
Coins:

Messages:

Corresponding index_db:

How to achieve pt. 2:

1. We try to fulfill the request using the biggest coins available
2. If there is not enough value, return empty set
3. If there is enough value, put the coins into the set
4. If there are still free slots available (ie. user provided higher limit that the number of coins we found in the point above), fill the random amount of remaining slots with dust coins (smallest ones)
5. Observe if the added dust coins can "replace" the big coins selected in step 1 - if so, remove the "big coin".
   • this will promote spending the dust coins if applicable, but if a user wants to spend "big" coins, he can always send query with lower max

Remarks:

1. Both main coins and dust coins should respect the "excluded" filter
2. Coins selected as main coins should not be added as dust later in the process

Questions:

1. Can we specify the same asset multiple times in coins_to_spend query? - Nope - see here.
   • ⚠ The duplicate check is not included in the PoC

The PoC implementation of the above is available here: https://github.com/rafal-ch/coins_to_spend_poc

Current flow:

1. coinsToSpend() arrives at the GraphQL API
2. Coins are collected
   1. off_chain DB is queried for "owned coin ids"
      • these are taken from OwnedCoins storage
   2. coin exclusion filter is applied
   3. coins are read from on_chain DB (coins_iter())
      • these are taken from Coins storage
3. if querying for base_asset_id, the above is repeated for "messages":
   1. off_chain DB is queried for "owned message ids"
      • these are taken from OwnedMessageIds storage
   2. messages are read from on_chain DB (messages_iter())
      • these are taken from Messages storage
4. random_improve() algo is used to select coins
   • if it cannot satisfy the request, fallback to largest_first() algorithm

For coins the key bytes represent:
| owner | asset_id | retryable flag | amount bytes | utxo_id |
where retryable flag is always set to false

For messages the key bytes represent:
| owner | base_asset_id | retryable flag | amount bytes | nonce |

Also, to disambiguate between "coins with base asset id" and "message" we'll use the "value" in the DB.