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