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