Building BTC TX with an address having excessive UTXOs takes forever

[ShookLyngs]

Issue

A transaction with specific from address can take forever to build, for example:

await sendBtc({
  from: 'tb1quqtqsh5jrlr9p5wnpu3rs883lqh4avpwc766x3',
  tos: [
    {
      address: 'tb1quqtqsh5jrlr9p5wnpu3rs883lqh4avpwc766x3',
      value: 1000,
    },
  ],
  source,
});

What happens:

1. The construction process contains a loop to estimate the fee of the transaction
2. In each loop, the BtcAssetsApi.getBtcUtxos() API is called to get the latest UTXO[] list
3. Each request can take 8-15 seconds, and in each loop, more UTXOs are collected to the inputs
4. If the inputs length increased, the estimated fee is also increased, causing another round of the loop
5. The condition to break the loop takes a very long time to be satisfied (due to the INSUFFICIENT_UTXO error)
6. The loop (tested by @Dawn-githup) can take 40+ minutes to fail, which is clearly abnormal

Investigation & resolvers

• [x] Should the BtcAssetsApi to be queried once per build to avoid long waiting time of requests?
  • The UTXO[] list can be updated during the construction, should we worry about it?
• [x] There's only a 1000 satoshi output in the outputs, not a huge cost at all, so why won't the loop stop?
  • Is it because some bugs remain in the pay fee process?

[ahonn]

Should the BtcAssetsApi to be queried once per build to avoid long waiting time of requests?

Yes, we should query once per build and check the inputs UTXO after the transaction is built. The BtcAssetsApi can provide a new API /bitcoin/v1/tx/:txid/outspend/:vout to return the spending status of each UTXO. It would be faster and more efficient.

Even if assets-api#132 merged, adding a data cache may solve this case, but we should reduce query times if we can.

[ShookLyngs]

Debug report

Ran some tests today:

1. For the example mentioned above, the total loop should be 6 times.
2. In each loop, the BtcAssetsApi.getBtcUtxos() API is used for querying UTXO[].
3. In each loop, the BtcAssetsApi.getRgbppAssetsByBtcUtxo() is used for checking each input's corresponding RGBPP assets, and if the UTXO is bound with any, it's excluded from the collection process.

Step 2 takes about 8-15 seconds, and although a single request in step 3 doesn't take much time, for each UTXO, there is a request to check if it's qualified to be used as an input. The more inputs, the more requests, therefore costing more time.

Resolvers for the performance issue

1. Cache BtcAssetsApi.getBtcUtxos(): Despite the improvements that will be applied to the btc-assets-api, the SDK can cache and reuse the result of the API within the scope of a single Txbuilder.payFee() call, instead of querying the UTXO[] list multiple times in the loop.
2. Cache BtcAssetsApi.getRgbppAssetsByBtcUtxo(): We may also cache the result of this API to prevent querying the same UTXO multiple times in the loop, but for each UTXO, we MUST query at least once, so the overall time savings on this API could be small. (@ahonn suggests to use the p-limit for batch querying and speeding up, maybe 10 queries at a time)
3. Cut down the overall loop time? (no clue)

The value-cost trap

Even if all the above issues are resolved, the exmaple transaction is still not construct-able. Here's a log that shows how:

loop(1): time(16.99s) preFee(0) currentFee(13019) inputs(3)
loop(2): time(17.00s) preFee(13019) currentFee(54661) inputs(16)
loop(3): time(17.03s) preFee(54661) currentFee(185932) inputs(57)
loop(4): time(17.10s) preFee(185932) currentFee(605266) inputs(188)
loop(5): time(17.38s) preFee(605266) currentFee(1950218) inputs(608)
loop(6): time(18.87s) preFee(1950218) currentFee(6256922) inputs(1953)

You can see that in each round of the loop, the fee significantly increased. And in each loop, the transaction included more and more inputs. In the end, the transaction failed with the fee requirement of 6256922 satoshi, and it had included 1953 inputs in the transaction.

It was just a small transaction, with only a single goal: to transfer 1000 satoshi to himself. How could the transaction require 1953 inputs to be included, and it was still insufficient for paying the network fee? Simply put, it's because:

1. Each UTXO contained too few satoshi (mostly 1000 satoshi each), yet the fee rate was too high.
2. The more inputs were included in the transaction, the higher the network fee became.

This is like a trap; no matter how many UTXOs (with 1000 satoshi value) you put into the transaction, you can never satisfy the network fee requirement. Therefore, even though the transaction included 1953 inputs, it still lacked enough satoshi for paying the fee.

[ahonn]

I think a possible solution to The "the value-cost trap" problem is to start with the estimated number of sats needed, rather than continually getting new UTXOs until demand is met.

[Flouse]

It was just a small transaction, with only a single goal: to transfer 1000 satoshi to himself. How could the transaction require 1953 inputs to be included, and it was still insufficient for paying the network fee?

If this is a normal BTC transfer, maybe the BTC SDK could try to find a UTXO with larger value as input.

Coin Selection Algorithm: Some Bitcoin wallets and libraries use a coin selection algorithm to choose the UTXOs to spend in a transaction. These algorithms are designed to minimize the number of inputs required while still covering the amount being sent and the fee.