Merge bitcoin/bitcoin#26631: test: add coverage for dust mempool policy (`-dustrelayfee` setting)

d6fc1d6a3393c571a1691a6bda60433216643616 test: add coverage for dust mempool policy (`-dustrelayfee` setting) (Sebastian Falbesoner)
8a5dbe28793d2e2ad85242f2191a6e1956b980dc test: add `CScript` method for checking for witness program (Sebastian Falbesoner)

Pull request description:

  This PR adds missing test coverage for the `-dustrelayfee` setting, which specifies the fee-rate used to define dust. Output scripts for all common types that are treated as standard by default (P2PK, P2(W)PKH, P2(W)SH, P2TR, bare multisig, null data, unknown witness versions v2+) are created and then checked for dust-mempool-policy each via the `testmempoolaccept` RPC: a tx with an output's nValue equal to the dust threshold should be accepted, one with an nValue of just one 1 satoshi below that should be rejected with reason `dust`. This is repeatedly done for a fixed (but obviously somewhat arbitrary) list of different `-dustrelayfee` settings on a single node, including the default and zero (i.e. no dust limit) settings.

  Note that the first commit introduces a necessary `CScript` helper method `IsWitnessProgram` (using PascalCase in Python is likely controversial; in this case the style for the already existing method `GetSigOpCount` was followed, which also refers to a method in the core `CScript` class).

  Some historical information about dust, contributed by pablomartin4btc:
  "The concept of dust was first introduced in https://github.com/bitcoin/bitcoin/pull/2577. This [commit](https://github.com/bitcoin/bitcoin/pull/9380/commits/eb30d1a5b215c6dd3763d7f7948f2dd8cb61f6bf) from https://github.com/bitcoin/bitcoin/pull/9380 introduced the -dustrelayfee option. Previous to that PR, the dust feerate was whatever -minrelaytxfee was set to."

ACKs for top commit:
  LarryRuane:
    ACK d6fc1d6a3393c571a1691a6bda60433216643616
  glozow:
    ACK d6fc1d6a3393c571a1691a6bda60433216643616
  kouloumos:
    ACK d6fc1d6a3393c571a1691a6bda60433216643616

Tree-SHA512: 35ea2b2497dfb466395af5665bb217f7250aa7cab9dc43539a5658ab69a454e3623ff58fce7489fcc1105b37f8cb4840a93cec658c5df1de611732bc6439ccad

3 files changed, 124 insertions, 0 deletions

diff --git a/test/functional/mempool_dust.py b/test/functional/mempool_dust.py
new file mode 100755
index 0000000000..2153f59a55
--- /dev/null
+++ b/test/functional/mempool_dust.py
@@ -0,0 +1,116 @@
+#!/usr/bin/env python3
+# Copyright (c) 2022 The Bitcoin Core developers
+# Distributed under the MIT software license, see the accompanying
+# file COPYING or http://www.opensource.org/licenses/mit-license.php.
+"""Test dust limit mempool policy (`-dustrelayfee` parameter)"""
+from decimal import Decimal
+
+from test_framework.key import ECKey
+from test_framework.messages import (
+    COIN,
+    CTxOut,
+)
+from test_framework.script import (
+    CScript,
+    OP_RETURN,
+    OP_TRUE,
+)
+from test_framework.script_util import (
+    key_to_p2pk_script,
+    key_to_p2pkh_script,
+    key_to_p2wpkh_script,
+    keys_to_multisig_script,
+    output_key_to_p2tr_script,
+    program_to_witness_script,
+    script_to_p2sh_script,
+    script_to_p2wsh_script,
+)
+from test_framework.test_framework import BitcoinTestFramework
+from test_framework.test_node import TestNode
+from test_framework.util import (
+    assert_equal,
+    get_fee,
+)
+from test_framework.wallet import MiniWallet
+
+
+DUST_RELAY_TX_FEE = 3000  # default setting [sat/kvB]
+
+
+class DustRelayFeeTest(BitcoinTestFramework):
+    def set_test_params(self):
+        self.num_nodes = 1
+
+    def test_dust_output(self, node: TestNode, dust_relay_fee: Decimal,
+                         output_script: CScript, type_desc: str) -> None:
+        # determine dust threshold (see `GetDustThreshold`)
+        if output_script[0] == OP_RETURN:
+            dust_threshold = 0
+        else:
+            tx_size = len(CTxOut(nValue=0, scriptPubKey=output_script).serialize())
+            tx_size += 67 if output_script.IsWitnessProgram() else 148
+            dust_threshold = int(get_fee(tx_size, dust_relay_fee) * COIN)
+        self.log.info(f"-> Test {type_desc} output (size {len(output_script)}, limit {dust_threshold})")
+
+        # amount right on the dust threshold should pass
+        tx = self.wallet.create_self_transfer()["tx"]
+        tx.vout.append(CTxOut(nValue=dust_threshold, scriptPubKey=output_script))
+        tx.vout[0].nValue -= dust_threshold  # keep total output value constant
+        tx_good_hex = tx.serialize().hex()
+        res = node.testmempoolaccept([tx_good_hex])[0]
+        assert_equal(res['allowed'], True)
+
+        # amount just below the dust threshold should fail
+        if dust_threshold > 0:
+            tx.vout[1].nValue -= 1
+            res = node.testmempoolaccept([tx.serialize().hex()])[0]
+            assert_equal(res['allowed'], False)
+            assert_equal(res['reject-reason'], 'dust')
+
+        # finally send the transaction to avoid running out of MiniWallet UTXOs
+        self.wallet.sendrawtransaction(from_node=node, tx_hex=tx_good_hex)
+
+    def run_test(self):
+        self.wallet = MiniWallet(self.nodes[0])
+        self.wallet.rescan_utxos()
+
+        # prepare output scripts of each standard type
+        key = ECKey()
+        key.generate(compressed=False)
+        uncompressed_pubkey = key.get_pubkey().get_bytes()
+        key.generate(compressed=True)
+        pubkey = key.get_pubkey().get_bytes()
+
+        output_scripts = (
+            (key_to_p2pk_script(uncompressed_pubkey),          "P2PK (uncompressed)"),
+            (key_to_p2pk_script(pubkey),                       "P2PK (compressed)"),
+            (key_to_p2pkh_script(pubkey),                      "P2PKH"),
+            (script_to_p2sh_script(CScript([OP_TRUE])),        "P2SH"),
+            (key_to_p2wpkh_script(pubkey),                     "P2WPKH"),
+            (script_to_p2wsh_script(CScript([OP_TRUE])),       "P2WSH"),
+            (output_key_to_p2tr_script(pubkey[1:]),            "P2TR"),
+            # witness programs for segwitv2+ can be between 2 and 40 bytes
+            (program_to_witness_script(2,  b'\x66' * 2),       "P2?? (future witness version 2)"),
+            (program_to_witness_script(16, b'\x77' * 40),      "P2?? (future witness version 16)"),
+            # largest possible output script considered standard
+            (keys_to_multisig_script([uncompressed_pubkey]*3), "bare multisig (m-of-3)"),
+            (CScript([OP_RETURN, b'superimportanthash']),      "null data (OP_RETURN)"),
+        )
+
+        # test default (no parameter), disabled (=0) and a bunch of arbitrary dust fee rates [sat/kvB]
+        for dustfee_sat_kvb in (DUST_RELAY_TX_FEE, 0, 1, 66, 500, 1337, 12345, 21212, 333333):
+            dustfee_btc_kvb = dustfee_sat_kvb / Decimal(COIN)
+            if dustfee_sat_kvb == DUST_RELAY_TX_FEE:
+                self.log.info(f"Test default dust limit setting ({dustfee_sat_kvb} sat/kvB)...")
+            else:
+                dust_parameter = f"-dustrelayfee={dustfee_btc_kvb:.8f}"
+                self.log.info(f"Test dust limit setting {dust_parameter} ({dustfee_sat_kvb} sat/kvB)...")
+                self.restart_node(0, extra_args=[dust_parameter])
+
+            for output_script, description in output_scripts:
+                self.test_dust_output(self.nodes[0], dustfee_btc_kvb, output_script, description)
+            self.generate(self.nodes[0], 1)
+
+
+if __name__ == '__main__':
+    DustRelayFeeTest().main()
diff --git a/test/functional/test_framework/script.py b/test/functional/test_framework/script.py
index f345bf02db..443cae86a1 100644
--- a/test/functional/test_framework/script.py
+++ b/test/functional/test_framework/script.py
@@ -597,6 +597,13 @@ class CScript(bytes):
             lastOpcode = opcode
         return n
 
+    def IsWitnessProgram(self):
+        """A witness program is any valid CScript that consists of a 1-byte
+           push opcode followed by a data push between 2 and 40 bytes."""
+        return ((4 <= len(self) <= 42) and
+                (self[0] == OP_0 or (OP_1 <= self[0] <= OP_16)) and
+                (self[1] + 2 == len(self)))
+
 
 SIGHASH_DEFAULT = 0 # Taproot-only default, semantics same as SIGHASH_ALL
 SIGHASH_ALL = 1
diff --git a/test/functional/test_runner.py b/test/functional/test_runner.py
index 86a9e4cd9a..4b9bf11d0e 100755
--- a/test/functional/test_runner.py
+++ b/test/functional/test_runner.py
@@ -318,6 +318,7 @@ BASE_SCRIPTS = [
     'mempool_unbroadcast.py',
     'mempool_compatibility.py',
     'mempool_accept_wtxid.py',
+    'mempool_dust.py',
     'rpc_deriveaddresses.py',
     'rpc_deriveaddresses.py --usecli',
     'p2p_ping.py',