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

theStack · 2021-10-27T16:01:04Z

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

bitcoin/test/functional/test_framework/wallet.py

Lines 173 to 174 in ab25ef8

    
           self._utxos = sorted(self._utxos, key=lambda k: k['value']) 
        
           utxo_to_spend = utxo_to_spend or self._utxos.pop()  # Pick the largest utxo (if none provided) and hope it covers the fee

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 (comment) (PR #23371).

…s (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.

brunoerg · 2021-10-27T19:33:02Z

Concept ACK

going to test soon..

maflcko · 2021-10-28T12:56:50Z

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 · 2021-10-28T14:09:02Z

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:

-------------------
--- BEFORE SORT ---
-------------------
{..., 'value': Decimal('50.00000000'), 'height': 1}
{..., 'value': Decimal('50.00000000'), 'height': 2}
.....
{..., 'value': Decimal('50.00000000'), 'height': 149}
{..., 'value': Decimal('25.00000000'), 'height': 150}
{..., 'value': Decimal('25.00000000'), 'height': 151}
.....
{..., 'value': Decimal('25.00000000'), 'height': 206}

------------------
--- AFTER SORT ---
------------------
{..., 'value': Decimal('25.00000000'), 'height': 150}
{..., 'value': Decimal('25.00000000'), 'height': 151}
.....
{..., 'value': Decimal('25.00000000'), 'height': 206}
{..., 'value': Decimal('50.00000000'), 'height': 1}          <--- we want to pick this one (oldest)
{..., 'value': Decimal('50.00000000'), 'height': 2}
.....
{..., '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

ACK d2c4904

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.

mjdietzx

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?

mjdietzx · 2021-10-28T15:44:36Z

test/functional/test_framework/wallet.py

        for out in tx['vout']:
            if out['scriptPubKey']['hex'] == self._scriptPubKey.hex():
-                self._utxos.append({'txid': tx['txid'], 'vout': out['n'], 'value': out['value']})
+                self._utxos.append({'txid': tx['txid'], 'vout': out['n'], 'value': out['value'], 'height': 0})


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?

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).

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

mjdietzx · 2021-10-28T15:45:10Z

test/functional/test_framework/wallet.py

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


Genius 👀

maflcko · 2021-10-29T10:55:28Z

review ACK d2c4904

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 😅

…ion for coinbase UTXOs (oldest first) d2c4904 test: MiniWallet: more deterministic coin selection for coinbase UTXOs (oldest first) (Sebastian Falbesoner) Pull request description: 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 bitcoin#23371 (comment) (PR bitcoin#23371). ACKs for top commit: MarcoFalke: review ACK d2c4904 shaavan: ACK d2c4904 Tree-SHA512: 15d67b42fb8b77fd53022ea2ab8a6ed2b615567f3ce73bab16c06bfcb687c1a04dcb0360d0c2287c526b604cd3ac5eef7b14ce46fc31e23047ce1a3290027306

theStack mentioned this pull request Oct 27, 2021

test: MiniWallet: add P2TR support and use it per default #23371

Closed

DrahtBot added the Tests label Oct 27, 2021

shaavan approved these changes Oct 28, 2021

View reviewed changes

mjdietzx reviewed Oct 28, 2021

View reviewed changes

maflcko merged commit 8bac3b1 into bitcoin:master Oct 29, 2021

theStack deleted the 202110-test-MiniWallet-deterministic_coin_selection_oldest_first branch October 29, 2021 11:30

bitcoin locked and limited conversation to collaborators Oct 30, 2022

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

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

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

Uh oh!

theStack commented Oct 27, 2021

Uh oh!

brunoerg commented Oct 27, 2021

Uh oh!

maflcko commented Oct 28, 2021

Uh oh!

theStack commented Oct 28, 2021 •

edited

Loading

Uh oh!

shaavan left a comment

Uh oh!

mjdietzx left a comment

Uh oh!

mjdietzx Oct 28, 2021

Uh oh!

theStack Oct 28, 2021

Uh oh!

brunoerg Oct 29, 2021

Uh oh!

mjdietzx Oct 28, 2021

Uh oh!

maflcko commented Oct 29, 2021

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

	self._utxos = sorted(self._utxos, key=lambda k: k['value'])
	utxo_to_spend = utxo_to_spend or self._utxos.pop() # Pick the largest utxo (if none provided) and hope it covers the fee

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

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

Uh oh!

Conversation

theStack commented Oct 27, 2021

Uh oh!

brunoerg commented Oct 27, 2021

Uh oh!

maflcko commented Oct 28, 2021

Uh oh!

theStack commented Oct 28, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

shaavan left a comment

Choose a reason for hiding this comment

Uh oh!

mjdietzx left a comment

Choose a reason for hiding this comment

Uh oh!

mjdietzx Oct 28, 2021

Choose a reason for hiding this comment

Uh oh!

theStack Oct 28, 2021

Choose a reason for hiding this comment

Uh oh!

brunoerg Oct 29, 2021

Choose a reason for hiding this comment

Uh oh!

mjdietzx Oct 28, 2021

Choose a reason for hiding this comment

Uh oh!

maflcko commented Oct 29, 2021

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

theStack commented Oct 28, 2021 •

edited

Loading