1#!/usr/bin/env python3
2# Copyright (c) 2014-2020 The Bitcoin Core developers
3# Distributed under the MIT software license, see the accompanying
4# file COPYING or http://www.opensource.org/licenses/mit-license.php.
5"""Test fee estimation code."""
6from decimal import Decimal
7import random
8
9from test_framework.messages import CTransaction, CTxIn, CTxOut, COutPoint, ToHex, COIN
10from test_framework.script import CScript, OP_1, OP_DROP, OP_2, OP_HASH160, OP_EQUAL, hash160, OP_TRUE
11from test_framework.test_framework import BitcoinTestFramework
12from test_framework.util import (
13    assert_equal,
14    assert_greater_than,
15    assert_greater_than_or_equal,
16    satoshi_round,
17)
18
19# Construct 2 trivial P2SH's and the ScriptSigs that spend them
20# So we can create many transactions without needing to spend
21# time signing.
22REDEEM_SCRIPT_1 = CScript([OP_1, OP_DROP])
23REDEEM_SCRIPT_2 = CScript([OP_2, OP_DROP])
24P2SH_1 = CScript([OP_HASH160, hash160(REDEEM_SCRIPT_1), OP_EQUAL])
25P2SH_2 = CScript([OP_HASH160, hash160(REDEEM_SCRIPT_2), OP_EQUAL])
26
27# Associated ScriptSig's to spend satisfy P2SH_1 and P2SH_2
28SCRIPT_SIG = [CScript([OP_TRUE, REDEEM_SCRIPT_1]), CScript([OP_TRUE, REDEEM_SCRIPT_2])]
29
30
31def small_txpuzzle_randfee(from_node, conflist, unconflist, amount, min_fee, fee_increment):
32    """Create and send a transaction with a random fee.
33
34    The transaction pays to a trivial P2SH script, and assumes that its inputs
35    are of the same form.
36    The function takes a list of confirmed outputs and unconfirmed outputs
37    and attempts to use the confirmed list first for its inputs.
38    It adds the newly created outputs to the unconfirmed list.
39    Returns (raw transaction, fee)."""
40
41    # It's best to exponentially distribute our random fees
42    # because the buckets are exponentially spaced.
43    # Exponentially distributed from 1-128 * fee_increment
44    rand_fee = float(fee_increment) * (1.1892 ** random.randint(0, 28))
45    # Total fee ranges from min_fee to min_fee + 127*fee_increment
46    fee = min_fee - fee_increment + satoshi_round(rand_fee)
47    tx = CTransaction()
48    total_in = Decimal("0.00000000")
49    while total_in <= (amount + fee) and len(conflist) > 0:
50        t = conflist.pop(0)
51        total_in += t["amount"]
52        tx.vin.append(CTxIn(COutPoint(int(t["txid"], 16), t["vout"]), b""))
53    if total_in <= amount + fee:
54        while total_in <= (amount + fee) and len(unconflist) > 0:
55            t = unconflist.pop(0)
56            total_in += t["amount"]
57            tx.vin.append(CTxIn(COutPoint(int(t["txid"], 16), t["vout"]), b""))
58        if total_in <= amount + fee:
59            raise RuntimeError("Insufficient funds: need %d, have %d" % (amount + fee, total_in))
60    tx.vout.append(CTxOut(int((total_in - amount - fee) * COIN), P2SH_1))
61    tx.vout.append(CTxOut(int(amount * COIN), P2SH_2))
62    # These transactions don't need to be signed, but we still have to insert
63    # the ScriptSig that will satisfy the ScriptPubKey.
64    for inp in tx.vin:
65        inp.scriptSig = SCRIPT_SIG[inp.prevout.n]
66    txid = from_node.sendrawtransaction(hexstring=ToHex(tx), maxfeerate=0)
67    unconflist.append({"txid": txid, "vout": 0, "amount": total_in - amount - fee})
68    unconflist.append({"txid": txid, "vout": 1, "amount": amount})
69
70    return (ToHex(tx), fee)
71
72
73def split_inputs(from_node, txins, txouts, initial_split=False):
74    """Generate a lot of inputs so we can generate a ton of transactions.
75
76    This function takes an input from txins, and creates and sends a transaction
77    which splits the value into 2 outputs which are appended to txouts.
78    Previously this was designed to be small inputs so they wouldn't have
79    a high coin age when the notion of priority still existed."""
80
81    prevtxout = txins.pop()
82    tx = CTransaction()
83    tx.vin.append(CTxIn(COutPoint(int(prevtxout["txid"], 16), prevtxout["vout"]), b""))
84
85    half_change = satoshi_round(prevtxout["amount"] / 2)
86    rem_change = prevtxout["amount"] - half_change - Decimal("0.00001000")
87    tx.vout.append(CTxOut(int(half_change * COIN), P2SH_1))
88    tx.vout.append(CTxOut(int(rem_change * COIN), P2SH_2))
89
90    # If this is the initial split we actually need to sign the transaction
91    # Otherwise we just need to insert the proper ScriptSig
92    if (initial_split):
93        completetx = from_node.signrawtransactionwithwallet(ToHex(tx))["hex"]
94    else:
95        tx.vin[0].scriptSig = SCRIPT_SIG[prevtxout["vout"]]
96        completetx = ToHex(tx)
97    txid = from_node.sendrawtransaction(hexstring=completetx, maxfeerate=0)
98    txouts.append({"txid": txid, "vout": 0, "amount": half_change})
99    txouts.append({"txid": txid, "vout": 1, "amount": rem_change})
100
101def check_raw_estimates(node, fees_seen):
102    """Call estimaterawfee and verify that the estimates meet certain invariants."""
103
104    delta = 1.0e-6  # account for rounding error
105    for i in range(1, 26):
106        for _, e in node.estimaterawfee(i).items():
107            feerate = float(e["feerate"])
108            assert_greater_than(feerate, 0)
109
110            if feerate + delta < min(fees_seen) or feerate - delta > max(fees_seen):
111                raise AssertionError("Estimated fee (%f) out of range (%f,%f)"
112                                     % (feerate, min(fees_seen), max(fees_seen)))
113
114def check_smart_estimates(node, fees_seen):
115    """Call estimatesmartfee and verify that the estimates meet certain invariants."""
116
117    delta = 1.0e-6  # account for rounding error
118    last_feerate = float(max(fees_seen))
119    all_smart_estimates = [node.estimatesmartfee(i) for i in range(1, 26)]
120    for i, e in enumerate(all_smart_estimates):  # estimate is for i+1
121        feerate = float(e["feerate"])
122        assert_greater_than(feerate, 0)
123
124        if feerate + delta < min(fees_seen) or feerate - delta > max(fees_seen):
125            raise AssertionError("Estimated fee (%f) out of range (%f,%f)"
126                                 % (feerate, min(fees_seen), max(fees_seen)))
127        if feerate - delta > last_feerate:
128            raise AssertionError("Estimated fee (%f) larger than last fee (%f) for lower number of confirms"
129                                 % (feerate, last_feerate))
130        last_feerate = feerate
131
132        if i == 0:
133            assert_equal(e["blocks"], 2)
134        else:
135            assert_greater_than_or_equal(i + 1, e["blocks"])
136
137def check_estimates(node, fees_seen):
138    check_raw_estimates(node, fees_seen)
139    check_smart_estimates(node, fees_seen)
140
141class EstimateFeeTest(BitcoinTestFramework):
142    def set_test_params(self):
143        self.num_nodes = 3
144        # mine non-standard txs (e.g. txs with "dust" outputs)
145        # Force fSendTrickle to true (via whitelist.noban)
146        self.extra_args = [
147            ["-acceptnonstdtxn", "-whitelist=noban@127.0.0.1"],
148            ["-acceptnonstdtxn", "-whitelist=noban@127.0.0.1", "-blockmaxweight=68000"],
149            ["-acceptnonstdtxn", "-whitelist=noban@127.0.0.1", "-blockmaxweight=32000"],
150        ]
151
152    def skip_test_if_missing_module(self):
153        self.skip_if_no_wallet()
154
155    def setup_network(self):
156        """
157        We'll setup the network to have 3 nodes that all mine with different parameters.
158        But first we need to use one node to create a lot of outputs
159        which we will use to generate our transactions.
160        """
161        self.add_nodes(3, extra_args=self.extra_args)
162        # Use node0 to mine blocks for input splitting
163        # Node1 mines small blocks but that are bigger than the expected transaction rate.
164        # NOTE: the CreateNewBlock code starts counting block weight at 4,000 weight,
165        # (68k weight is room enough for 120 or so transactions)
166        # Node2 is a stingy miner, that
167        # produces too small blocks (room for only 55 or so transactions)
168        self.start_nodes()
169        self.import_deterministic_coinbase_privkeys()
170        self.stop_nodes()
171
172    def transact_and_mine(self, numblocks, mining_node):
173        min_fee = Decimal("0.00001")
174        # We will now mine numblocks blocks generating on average 100 transactions between each block
175        # We shuffle our confirmed txout set before each set of transactions
176        # small_txpuzzle_randfee will use the transactions that have inputs already in the chain when possible
177        # resorting to tx's that depend on the mempool when those run out
178        for _ in range(numblocks):
179            random.shuffle(self.confutxo)
180            for _ in range(random.randrange(100 - 50, 100 + 50)):
181                from_index = random.randint(1, 2)
182                (txhex, fee) = small_txpuzzle_randfee(self.nodes[from_index], self.confutxo,
183                                                      self.memutxo, Decimal("0.005"), min_fee, min_fee)
184                tx_kbytes = (len(txhex) // 2) / 1000.0
185                self.fees_per_kb.append(float(fee) / tx_kbytes)
186            self.sync_mempools(wait=.1)
187            mined = mining_node.getblock(mining_node.generate(1)[0], True)["tx"]
188            self.sync_blocks(wait=.1)
189            # update which txouts are confirmed
190            newmem = []
191            for utx in self.memutxo:
192                if utx["txid"] in mined:
193                    self.confutxo.append(utx)
194                else:
195                    newmem.append(utx)
196            self.memutxo = newmem
197
198    def run_test(self):
199        self.log.info("This test is time consuming, please be patient")
200        self.log.info("Splitting inputs so we can generate tx's")
201
202        # Start node0
203        self.start_node(0)
204        self.txouts = []
205        self.txouts2 = []
206        # Split a coinbase into two transaction puzzle outputs
207        split_inputs(self.nodes[0], self.nodes[0].listunspent(0), self.txouts, True)
208
209        # Mine
210        while len(self.nodes[0].getrawmempool()) > 0:
211            self.nodes[0].generate(1)
212
213        # Repeatedly split those 2 outputs, doubling twice for each rep
214        # Use txouts to monitor the available utxo, since these won't be tracked in wallet
215        reps = 0
216        while reps < 5:
217            # Double txouts to txouts2
218            while len(self.txouts) > 0:
219                split_inputs(self.nodes[0], self.txouts, self.txouts2)
220            while len(self.nodes[0].getrawmempool()) > 0:
221                self.nodes[0].generate(1)
222            # Double txouts2 to txouts
223            while len(self.txouts2) > 0:
224                split_inputs(self.nodes[0], self.txouts2, self.txouts)
225            while len(self.nodes[0].getrawmempool()) > 0:
226                self.nodes[0].generate(1)
227            reps += 1
228        self.log.info("Finished splitting")
229
230        # Now we can connect the other nodes, didn't want to connect them earlier
231        # so the estimates would not be affected by the splitting transactions
232        self.start_node(1)
233        self.start_node(2)
234        self.connect_nodes(1, 0)
235        self.connect_nodes(0, 2)
236        self.connect_nodes(2, 1)
237
238        self.sync_all()
239
240        self.fees_per_kb = []
241        self.memutxo = []
242        self.confutxo = self.txouts  # Start with the set of confirmed txouts after splitting
243        self.log.info("Will output estimates for 1/2/3/6/15/25 blocks")
244
245        for _ in range(2):
246            self.log.info("Creating transactions and mining them with a block size that can't keep up")
247            # Create transactions and mine 10 small blocks with node 2, but create txs faster than we can mine
248            self.transact_and_mine(10, self.nodes[2])
249            check_estimates(self.nodes[1], self.fees_per_kb)
250
251            self.log.info("Creating transactions and mining them at a block size that is just big enough")
252            # Generate transactions while mining 10 more blocks, this time with node1
253            # which mines blocks with capacity just above the rate that transactions are being created
254            self.transact_and_mine(10, self.nodes[1])
255            check_estimates(self.nodes[1], self.fees_per_kb)
256
257        # Finish by mining a normal-sized block:
258        while len(self.nodes[1].getrawmempool()) > 0:
259            self.nodes[1].generate(1)
260
261        self.sync_blocks(self.nodes[0:3], wait=.1)
262        self.log.info("Final estimates after emptying mempools")
263        check_estimates(self.nodes[1], self.fees_per_kb)
264
265
266if __name__ == '__main__':
267    EstimateFeeTest().main()
268