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