test: MiniWallet: more deterministic coin selection for coinbase UTXOs (oldest first)

theStack commented at 4:01 pm on October 27, 2021: member

The coin selection strategy for MiniWallet is quite straight-forward: simply pick a single UTXO with the largest value:

https://github.com/bitcoin/bitcoin/blob/ab25ef8c7f767258d5fe44f53b35ad8bd51ed5cd/test/functional/test_framework/wallet.py#L173-L174

If there are several candidates with the same value, however, it is not clear which one is taken. This can be particularly problematic for coinbase outputs with fixed block subsidy, since spending could lead to a bad-txns-premature-spend-of-coinbase reject if an UTXO from a too-recent block is picked. Introduce block height as second criteria (saved in self._utxos in the methods generate(...) and rescan_utxos(...)), in order to avoid potential issues with coinbases that are not matured yet. If there is a tie between coinbase UTXOs and non-coinbase UTXOs (the latter are added via scan_tx(...)), prefer the non-coinbase UTXOs, since those don’t need to mature.

The issue came up while refactoring the test rpc_blockchain.py, see #23371 (review) (PR #23371).

test: MiniWallet: more deterministic coin selection for coinbase UTXOs (oldest first)

The coin selection strategy for MiniWallet is quite straight-forward: simply
pick a single UTXO with the largest value:

self._utxos = sorted(self._utxos, key=lambda k: k['value'])
utxo_to_spend = utxo_to_spend or self._utxos.pop()

If there are several candidates with the same value, however, it is not clear
which one is taken.  This can be particularly problematic for coinbase outputs
with fixed block subsidy, since spending could lead to a
'bad-txns-premature-spend-of-coinbase' reject if an UTXO from a too-recent
block is picked.  Introduce block height as second criteria (saved in
self._utxos in the methods generate(...) and rescan_utxos(...)), in order to
avoid potential issues with coinbases that are not matured yet.

d2c4904ef7

DrahtBot added the label Tests on Oct 27, 2021

brunoerg commented at 7:33 pm on October 27, 2021: member

Concept ACK

going to test soon..

MarcoFalke commented at 12:56 pm on October 28, 2021: member

Interesting. I assumed that generate will add the coinbases in the “right” order (oldest first) and I assumed sorted() in python to be a stable sort (not changing the order for equal elements).

I guess it can’t hurt to be explicit.

theStack commented at 2:09 pm on October 28, 2021: member

Interesting. I assumed that generate will add the coinbases in the “right” order (oldest first) and I assumed sorted() in python to be a stable sort (not changing the order for equal elements).

Your assumptions regarding generate and sorted() being stable sort seem to be right (https://stackoverflow.com/questions/1915376/is-pythons-sorted-function-guaranteed-to-be-stable). Still we have problems for two reasons:

due to ascending sort order and popping off the last element, we take the UTXO with the highest block number, not the lowest; example from rpc_blockchain.py before and after sorting:

 0-------------------
 1--- BEFORE SORT ---
 2-------------------
 3{..., 'value': Decimal('50.00000000'), 'height': 1}
 4{..., 'value': Decimal('50.00000000'), 'height': 2}
 5.....
 6{..., 'value': Decimal('50.00000000'), 'height': 149}
 7{..., 'value': Decimal('25.00000000'), 'height': 150}
 8{..., 'value': Decimal('25.00000000'), 'height': 151}
 9.....
10{..., 'value': Decimal('25.00000000'), 'height': 206}
11
12------------------
13--- AFTER SORT ---
14------------------
15{..., 'value': Decimal('25.00000000'), 'height': 150}
16{..., 'value': Decimal('25.00000000'), 'height': 151}
17.....
18{..., 'value': Decimal('25.00000000'), 'height': 206}
19{..., 'value': Decimal('50.00000000'), 'height': 1}          <--- we want to pick this one (oldest)
20{..., 'value': Decimal('50.00000000'), 'height': 2}
21.....
22{..., 'value': Decimal('50.00000000'), 'height': 149}        <--- that one is actually picked (newest)

the scantxoutset RPC doesn’t return its result res['unspents'] ordered by block height, i.e. one would need to sort this first before appending to self._utxos.

Those two problems could be solved on their own (sort in descending order and pop off the first element works I guess?), but rather than always taking care to append to the UTXOs in the right order (which is i.e. impossible if generate would be called before rescan_utxos), I think the most clean solution is to simply save the block height and use it as second sort criteria.

shaavan approved

shaavan commented at 2:29 pm on October 28, 2021: contributor

ACK d2c4904ef707e2023ceb8dfbfe61a92c4060e100

This change allows considering the height of utxo while sorting the utxos (based on values). This addition is especially helpful in case two utxos have the same value. This addition also prevents “premature spend of coinbase” error when a non-coinbase transaction of equal value is available.

in test/functional/test_framework/wallet.py:97 in d2c4904ef7

94     def scan_tx(self, tx):
95         """Scan the tx for self._scriptPubKey outputs and add them to self._utxos"""
96         for out in tx['vout']:
97             if out['scriptPubKey']['hex'] == self._scriptPubKey.hex():
98-                self._utxos.append({'txid': tx['txid'], 'vout': out['n'], 'value': out['value']})
99+                self._utxos.append({'txid': tx['txid'], 'vout': out['n'], 'value': out['value'], 'height': 0})

mjdietzx commented at 3:44 pm on October 28, 2021:

If this tx is in a block, don’t you need to set utxo.height accordingly? ie will height always be 0 as is hardcoded here?

theStack commented at 4:10 pm on October 28, 2021:

Right now scan_tx is used only immediately after broadcasting a transaction (internally in MiniWallet.sendrawtransaction(), and in one instance in wallet_bumpfee.py), i.e. on unconfirmed txs. I don’t think it makes much sense to ever call it for confirmed transactions (though I could miss something) – setting the ‘height’ field is particularly important for coinbase UTXOs, and those seem to be all tackled by MiniWallet.generate (explicitely generate block to MiniWallet address) and MiniWallet.rescan_utxo (scan in pre-mined chain for MiniWallet address).

brunoerg commented at 10:44 am on October 29, 2021:

@theStack thanks for the explanation, I was in doubt about it but now it is clear for me.

in test/functional/test_framework/wallet.py:174 in d2c4904ef7

170@@ -170,7 +171,7 @@ def send_to(self, *, from_node, scriptPubKey, amount, fee=1000):
171 
172     def create_self_transfer(self, *, fee_rate=Decimal("0.003"), from_node, utxo_to_spend=None, mempool_valid=True, locktime=0, sequence=0):
173         """Create and return a tx with the specified fee_rate. Fee may be exact or at most one satoshi higher than needed."""
174-        self._utxos = sorted(self._utxos, key=lambda k: k['value'])
175+        self._utxos = sorted(self._utxos, key=lambda k: (k['value'], -k['height']))

mjdietzx commented at 3:45 pm on October 28, 2021:

Genius 👀

mjdietzx commented at 3:46 pm on October 28, 2021: contributor

I agree this should be done. Thinking more about your approach here, but seems nice and simple.

What about unconfirmed utxos though? If we have an unconfirmed utxo is our utxo set, what should its height be?

MarcoFalke commented at 10:55 am on October 29, 2021: member

review ACK d2c4904ef707e2023ceb8dfbfe61a92c4060e100

Nice change. Previously it picked the last-mined largest value, which is wrong. It should pick the first-mined largest value. I added this bug :sweat_smile:

MarcoFalke merged this on Oct 29, 2021

MarcoFalke closed this on Oct 29, 2021

theStack deleted the branch on Oct 29, 2021

sidhujag referenced this in commit 3624bcd739 on Oct 29, 2021

DrahtBot locked this on Oct 30, 2022

test: MiniWallet: more deterministic coin selection for coinbase UTXOs (oldest first) #23375