feature_fee_estimation.py
1 #!/usr/bin/env python3 2 # Copyright (c) 2014-present 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.""" 6 from copy import deepcopy 7 from decimal import Decimal, ROUND_DOWN 8 import os 9 import random 10 import time 11 12 from test_framework.messages import ( 13 COIN, 14 ) 15 from test_framework.test_framework import BitcoinTestFramework 16 from test_framework.util import ( 17 assert_not_equal, 18 assert_equal, 19 assert_greater_than, 20 assert_greater_than_or_equal, 21 assert_raises_rpc_error, 22 satoshi_round, 23 ) 24 from test_framework.wallet import MiniWallet 25 26 MAX_FILE_AGE = 60 27 SECONDS_PER_HOUR = 60 * 60 28 MIN_BUCKET_FEERATE = Decimal(100) / Decimal(COIN) 29 TXS_COUNT = 24 30 31 def small_txpuzzle_randfee( 32 wallet, from_node, conflist, unconflist, amount, min_fee, fee_increment, batch_reqs 33 ): 34 """Create and send a transaction with a random fee using MiniWallet. 35 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, rounding=ROUND_DOWN) 47 utxos_to_spend = [] 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["value"] 52 utxos_to_spend.append(t) 53 while total_in <= (amount + fee) and len(unconflist) > 0: 54 t = unconflist.pop(0) 55 total_in += t["value"] 56 utxos_to_spend.append(t) 57 if total_in <= amount + fee: 58 raise RuntimeError(f"Insufficient funds: need {amount + fee}, have {total_in}") 59 tx = wallet.create_self_transfer_multi( 60 utxos_to_spend=utxos_to_spend, 61 fee_per_output=0, 62 )["tx"] 63 tx.vout[0].nValue = int((total_in - amount - fee) * COIN) 64 tx.vout.append(deepcopy(tx.vout[0])) 65 tx.vout[1].nValue = int(amount * COIN) 66 txid = tx.txid_hex 67 tx_hex = tx.serialize().hex() 68 69 batch_reqs.append(from_node.sendrawtransaction.get_request(hexstring=tx_hex, maxfeerate=0)) 70 unconflist.append({"txid": txid, "vout": 0, "value": total_in - amount - fee}) 71 unconflist.append({"txid": txid, "vout": 1, "value": amount}) 72 73 return (tx.get_vsize(), fee) 74 75 76 def check_raw_estimates(node, fees_seen): 77 """Call estimaterawfee and verify that the estimates meet certain invariants.""" 78 79 delta = 1.0e-6 # account for rounding error 80 for i in range(1, 26): 81 for _, e in node.estimaterawfee(i).items(): 82 feerate = float(e["feerate"]) 83 assert_greater_than(feerate, 0) 84 85 if feerate + delta < min(fees_seen) or feerate - delta > max(fees_seen): 86 raise AssertionError( 87 f"Estimated fee ({feerate}) out of range ({min(fees_seen)},{max(fees_seen)})" 88 ) 89 90 91 def check_smart_estimates(node, fees_seen): 92 """Call estimatesmartfee and verify that the estimates meet certain invariants.""" 93 94 delta = 1.0e-6 # account for rounding error 95 all_smart_estimates = [node.estimatesmartfee(i) for i in range(1, 26)] 96 mempoolMinFee = node.getmempoolinfo()["mempoolminfee"] 97 minRelaytxFee = node.getmempoolinfo()["minrelaytxfee"] 98 feerate_ceiling = max(max(fees_seen), float(mempoolMinFee), float(minRelaytxFee)) 99 last_feerate = feerate_ceiling 100 for i, e in enumerate(all_smart_estimates): # estimate is for i+1 101 feerate = float(e["feerate"]) 102 assert_greater_than(feerate, 0) 103 assert_greater_than_or_equal(feerate, float(mempoolMinFee)) 104 assert_greater_than_or_equal(feerate, float(minRelaytxFee)) 105 106 if feerate + delta < min(fees_seen) or feerate - delta > feerate_ceiling: 107 raise AssertionError( 108 f"Estimated fee ({feerate}) out of range ({min(fees_seen)},{feerate_ceiling})" 109 ) 110 if feerate - delta > last_feerate: 111 raise AssertionError( 112 f"Estimated fee ({feerate}) larger than last fee ({last_feerate}) for lower number of confirms" 113 ) 114 last_feerate = feerate 115 116 if i == 0: 117 assert_equal(e["blocks"], 2) 118 else: 119 assert_greater_than_or_equal(i + 1, e["blocks"]) 120 121 122 def check_estimates(node, fees_seen): 123 check_raw_estimates(node, fees_seen) 124 check_smart_estimates(node, fees_seen) 125 126 127 def make_tx(wallet, utxo, feerate): 128 """Create a 1in-1out transaction with a specific input and feerate (sat/vb).""" 129 return wallet.create_self_transfer( 130 utxo_to_spend=utxo, 131 fee_rate=Decimal(feerate * 1000) / COIN, 132 ) 133 134 def check_fee_estimates_btw_modes(node, expected_conservative, expected_economical): 135 fee_est_conservative = node.estimatesmartfee(1, estimate_mode="conservative")['feerate'] 136 fee_est_economical = node.estimatesmartfee(1, estimate_mode="economical")['feerate'] 137 fee_est_default = node.estimatesmartfee(1)['feerate'] 138 assert_equal(fee_est_conservative, expected_conservative) 139 assert_equal(fee_est_economical, expected_economical) 140 assert_equal(fee_est_default, expected_economical) 141 142 143 class EstimateFeeTest(BitcoinTestFramework): 144 def set_test_params(self): 145 self.num_nodes = 3 146 # whitelist peers to speed up tx relay / mempool sync 147 self.noban_tx_relay = True 148 self.extra_args = [ 149 [], 150 ["-blockmaxweight=72000"], 151 ["-blockmaxweight=36000"], 152 ] 153 154 def setup_network(self): 155 """ 156 We'll setup the network to have 3 nodes that all mine with different parameters. 157 But first we need to use one node to create a lot of outputs 158 which we will use to generate our transactions. 159 """ 160 self.add_nodes(3, extra_args=self.extra_args) 161 # Use node0 to mine blocks for input splitting 162 # Node1 mines small blocks but that are bigger than the expected transaction rate. 163 # NOTE: the CreateNewBlock code starts counting block weight at 4,000 weight, 164 # (68k weight is room enough for 120 or so transactions) 165 # Node2 is a stingy miner, that 166 # produces too small blocks (room for only 55 or so transactions) 167 168 def update_utxo(self, mined): 169 # update which txouts are confirmed 170 newmem = [] 171 for utx in self.memutxo: 172 if utx["txid"] in mined: 173 self.confutxo.append(utx) 174 else: 175 newmem.append(utx) 176 self.memutxo = newmem 177 178 def transact_and_mine(self, numblocks, mining_node): 179 min_fee = MIN_BUCKET_FEERATE 180 # We will now mine numblocks blocks generating on average 100 transactions between each block 181 # We shuffle our confirmed txout set before each set of transactions 182 # small_txpuzzle_randfee will use the transactions that have inputs already in the chain when possible 183 # resorting to tx's that depend on the mempool when those run out 184 for _ in range(numblocks): 185 random.shuffle(self.confutxo) 186 batch_sendtx_reqs = [] 187 for _ in range(random.randrange(100 - 50, 100 + 50)): 188 from_index = random.randint(1, 2) 189 (tx_bytes, fee) = small_txpuzzle_randfee( 190 self.wallet, 191 self.nodes[from_index], 192 self.confutxo, 193 self.memutxo, 194 Decimal("0.005"), 195 min_fee, 196 min_fee, 197 batch_sendtx_reqs, 198 ) 199 tx_kbytes = tx_bytes / 1000.0 200 self.fees_per_kb.append(float(fee) / tx_kbytes) 201 for node in self.nodes: 202 node.batch(batch_sendtx_reqs) 203 self.sync_mempools(wait=0.1) 204 mined = mining_node.getblock(self.generate(mining_node, 1)[0], True)["tx"] 205 self.update_utxo(mined) 206 207 def initial_split(self, node): 208 """Split two coinbase UTxOs into many small coins""" 209 self.confutxo = self.wallet.send_self_transfer_multi( 210 from_node=node, 211 utxos_to_spend=[self.wallet.get_utxo() for _ in range(2)], 212 num_outputs=2048)['new_utxos'] 213 while len(node.getrawmempool()) > 0: 214 self.generate(node, 1, sync_fun=self.no_op) 215 216 def sanity_check_estimates_range(self): 217 """Populate estimation buckets, assert estimates are in a sane range and 218 are strictly increasing as the target decreases.""" 219 self.fees_per_kb = [] 220 self.memutxo = [] 221 self.log.info("Will output estimates for 1/2/3/6/15/25 blocks") 222 223 for _ in range(2): 224 self.log.info( 225 "Creating transactions and mining them with a block size that can't keep up" 226 ) 227 # Create transactions and mine 10 small blocks with node 2, but create txs faster than we can mine 228 self.transact_and_mine(10, self.nodes[2]) 229 check_estimates(self.nodes[1], self.fees_per_kb) 230 231 self.log.info( 232 "Creating transactions and mining them at a block size that is just big enough" 233 ) 234 # Generate transactions while mining 10 more blocks, this time with node1 235 # which mines blocks with capacity just above the rate that transactions are being created 236 self.transact_and_mine(10, self.nodes[1]) 237 check_estimates(self.nodes[1], self.fees_per_kb) 238 239 # Finish by mining a normal-sized block: 240 while len(self.nodes[1].getrawmempool()) > 0: 241 self.generate(self.nodes[1], 1) 242 243 self.log.info("Final estimates after emptying mempools") 244 check_estimates(self.nodes[1], self.fees_per_kb) 245 246 def test_estimates_with_highminrelaytxfee(self): 247 high_val = 3 * self.nodes[1].estimatesmartfee(2)["feerate"] 248 self.restart_node(1, extra_args=[f"-minrelaytxfee={high_val}"]) 249 check_smart_estimates(self.nodes[1], self.fees_per_kb) 250 self.restart_node(1) 251 252 def sanity_check_rbf_estimates(self): 253 """During 5 blocks, broadcast low fee transactions. Only 10% of them get 254 confirmed and the remaining ones get RBF'd with a high fee transaction at 255 the next block. 256 The block policy estimator should return the high feerate. 257 """ 258 # The broadcaster and block producer 259 node = self.nodes[0] 260 miner = self.nodes[1] 261 # In sat/vb 262 low_feerate = 1 263 high_feerate = 10 264 # Cache the utxos of which to replace the spender after it failed to get 265 # confirmed 266 utxos_to_respend = [] 267 txids_to_replace = [] 268 269 assert_greater_than_or_equal(len(self.confutxo), 250) 270 for _ in range(5): 271 # Broadcast 45 low fee transactions that will need to be RBF'd 272 txs = [] 273 for _ in range(45): 274 u = self.confutxo.pop(0) 275 tx = make_tx(self.wallet, u, low_feerate) 276 utxos_to_respend.append(u) 277 txids_to_replace.append(tx["txid"]) 278 txs.append(tx) 279 # Broadcast 5 low fee transaction which don't need to 280 for _ in range(5): 281 tx = make_tx(self.wallet, self.confutxo.pop(0), low_feerate) 282 self.memutxo.append(tx["new_utxo"]) 283 txs.append(tx) 284 batch_send_tx = [node.sendrawtransaction.get_request(tx["hex"]) for tx in txs] 285 for n in self.nodes: 286 n.batch(batch_send_tx) 287 # Mine the transactions on another node 288 self.sync_mempools(wait=0.1, nodes=[node, miner]) 289 for txid in txids_to_replace: 290 miner.prioritisetransaction(txid=txid, fee_delta=-COIN) 291 mined = miner.getblock(self.generate(miner, 1)[0], True)["tx"] 292 self.update_utxo(mined) 293 # RBF the low-fee transactions 294 while len(utxos_to_respend) > 0: 295 u = utxos_to_respend.pop(0) 296 tx = make_tx(self.wallet, u, high_feerate) 297 self.memutxo.append(tx["new_utxo"]) 298 node.sendrawtransaction(tx["hex"]) 299 txs.append(tx) 300 dec_txs = [res["result"] for res in node.batch([node.decoderawtransaction.get_request(tx["hex"]) for tx in txs])] 301 self.wallet.scan_txs(dec_txs) 302 303 304 # Mine the last replacement txs 305 self.sync_mempools(wait=0.1, nodes=[node, miner]) 306 mined = miner.getblock(self.generate(miner, 1)[0], True)["tx"] 307 self.update_utxo(mined) 308 309 # Only 10% of the transactions were really confirmed with a low feerate, 310 # the rest needed to be RBF'd. We must return the 90% conf rate feerate. 311 high_feerate_kvb = Decimal(high_feerate) / COIN * 10 ** 3 312 est_feerate = node.estimatesmartfee(2)["feerate"] 313 assert_equal(est_feerate, high_feerate_kvb) 314 315 def test_old_fee_estimate_file(self): 316 # Get the initial fee rate while node is running 317 fee_rate = self.nodes[0].estimatesmartfee(1)["feerate"] 318 319 # Restart node to ensure fee_estimate.dat file is read 320 self.restart_node(0) 321 assert_equal(self.nodes[0].estimatesmartfee(1)["feerate"], fee_rate) 322 323 fee_dat = self.nodes[0].chain_path / "fee_estimates.dat" 324 325 # Stop the node and backdate the fee_estimates.dat file more than MAX_FILE_AGE 326 self.stop_node(0) 327 last_modified_time = time.time() - (MAX_FILE_AGE + 1) * SECONDS_PER_HOUR 328 os.utime(fee_dat, (last_modified_time, last_modified_time)) 329 330 # Start node and ensure the fee_estimates.dat file was not read 331 self.start_node(0) 332 assert_equal(self.nodes[0].estimatesmartfee(1)["errors"], ["Insufficient data or no feerate found"]) 333 334 335 def test_estimate_dat_is_flushed_periodically(self): 336 fee_dat = self.nodes[0].chain_path / "fee_estimates.dat" 337 os.remove(fee_dat) if os.path.exists(fee_dat) else None 338 339 # Verify that fee_estimates.dat does not exist 340 assert_equal(os.path.isfile(fee_dat), False) 341 342 # Verify if the string "Flushed fee estimates to fee_estimates.dat." is present in the debug log file. 343 # If present, it indicates that fee estimates have been successfully flushed to disk. 344 expected_messages = [f"Flushed fee estimates to {fee_dat}."] 345 with self.nodes[0].assert_debug_log(expected_msgs=expected_messages, timeout=1): 346 # Mock the scheduler for an hour to flush fee estimates to fee_estimates.dat 347 self.nodes[0].mockscheduler(SECONDS_PER_HOUR) 348 349 # Verify that fee estimates were flushed and fee_estimates.dat file is created 350 assert_equal(os.path.isfile(fee_dat), True) 351 352 # Verify that the estimates remain the same if there are no blocks in the flush interval 353 block_hash_before = self.nodes[0].getbestblockhash() 354 fee_dat_initial_content = open(fee_dat, "rb").read() 355 with self.nodes[0].assert_debug_log(expected_msgs=expected_messages, timeout=1): 356 # Mock the scheduler for an hour to flush fee estimates to fee_estimates.dat 357 self.nodes[0].mockscheduler(SECONDS_PER_HOUR) 358 359 # Verify that there were no blocks in between the flush interval 360 assert_equal(block_hash_before, self.nodes[0].getbestblockhash()) 361 362 fee_dat_current_content = open(fee_dat, "rb").read() 363 assert_equal(fee_dat_current_content, fee_dat_initial_content) 364 365 # Verify that the estimates remain the same after shutdown with no blocks before shutdown 366 self.restart_node(0) 367 fee_dat_current_content = open(fee_dat, "rb").read() 368 assert_equal(fee_dat_current_content, fee_dat_initial_content) 369 370 # Verify that the estimates are not the same if new blocks were produced in the flush interval 371 with self.nodes[0].assert_debug_log(expected_msgs=expected_messages, timeout=1): 372 # Mock the scheduler for an hour to flush fee estimates to fee_estimates.dat 373 self.generate(self.nodes[0], 5, sync_fun=self.no_op) 374 self.nodes[0].mockscheduler(SECONDS_PER_HOUR) 375 376 fee_dat_current_content = open(fee_dat, "rb").read() 377 assert_not_equal(fee_dat_current_content, fee_dat_initial_content) 378 379 fee_dat_initial_content = fee_dat_current_content 380 381 # Generate blocks before shutdown and verify that the fee estimates are not the same 382 self.generate(self.nodes[0], 5, sync_fun=self.no_op) 383 self.restart_node(0) 384 fee_dat_current_content = open(fee_dat, "rb").read() 385 assert_not_equal(fee_dat_current_content, fee_dat_initial_content) 386 387 388 def test_acceptstalefeeestimates_option(self): 389 # Get the initial fee rate while node is running 390 fee_rate = self.nodes[0].estimatesmartfee(1)["feerate"] 391 392 self.stop_node(0) 393 394 fee_dat = self.nodes[0].chain_path / "fee_estimates.dat" 395 396 # Stop the node and backdate the fee_estimates.dat file more than MAX_FILE_AGE 397 last_modified_time = time.time() - (MAX_FILE_AGE + 1) * SECONDS_PER_HOUR 398 os.utime(fee_dat, (last_modified_time, last_modified_time)) 399 400 # Restart node with -acceptstalefeeestimates option to ensure fee_estimate.dat file is read 401 self.start_node(0,extra_args=["-acceptstalefeeestimates"]) 402 assert_equal(self.nodes[0].estimatesmartfee(1)["feerate"], fee_rate) 403 404 def clear_estimates(self): 405 self.log.info("Restarting node with fresh estimation") 406 self.stop_node(0) 407 fee_dat = self.nodes[0].chain_path / "fee_estimates.dat" 408 os.remove(fee_dat) 409 self.start_node(0) 410 self.connect_nodes(0, 1) 411 self.connect_nodes(0, 2) 412 self.sync_blocks() 413 assert_equal(self.nodes[0].estimatesmartfee(1)["errors"], ["Insufficient data or no feerate found"]) 414 415 def broadcast_many(self, broadcaster, feerate, count, miner=None): 416 """Broadcast and maybe mine some number of transactions with a specified fee rate.""" 417 for _ in range(count): 418 tx = self.wallet.send_self_transfer(from_node=broadcaster, fee_rate=feerate, confirmed_only=True, utxo_to_spend=self.confutxo.pop(0)) 419 self.memutxo.append(tx["new_utxo"]) 420 self.sync_mempools(wait=0.1, nodes=[self.nodes[0], self.nodes[1], self.nodes[2]]) 421 if miner: 422 mined = miner.getblock(self.generate(miner, 1)[0], True)["tx"] 423 self.update_utxo(mined) 424 425 def test_estimation_modes(self): 426 low_feerate = Decimal("0.001") 427 high_feerate = Decimal("0.005") 428 # Broadcast and mine high fee transactions for the first 12 blocks. 429 for _ in range(12): 430 self.broadcast_many(self.nodes[1], high_feerate, TXS_COUNT, self.nodes[2]) 431 check_fee_estimates_btw_modes(self.nodes[0], high_feerate, high_feerate) 432 433 # We now track 12 blocks; short horizon stats will start decaying. 434 # Broadcast and mine low fee transactions for the next 4 blocks. 435 for _ in range(4): 436 self.broadcast_many(self.nodes[1], low_feerate, TXS_COUNT, self.nodes[2]) 437 # conservative mode will consider longer time horizons while economical mode does not 438 # Check the fee estimates for both modes after mining low fee transactions. 439 check_fee_estimates_btw_modes(self.nodes[0], high_feerate, low_feerate) 440 441 def test_sub_1s_per_vb_estimates(self): 442 feerate_0_5_s_per_vb = MIN_BUCKET_FEERATE * 5 443 feerate_1_s_per_vb = Decimal(1000) / Decimal(COIN) 444 for i in range(6): 445 self.broadcast_many(self.nodes[1], feerate_0_5_s_per_vb, TXS_COUNT) 446 self.broadcast_many(self.nodes[1], feerate_1_s_per_vb, TXS_COUNT, self.nodes[2]) 447 assert_equal(feerate_0_5_s_per_vb, self.nodes[0].estimatesmartfee(1)["feerate"]) 448 449 450 def run_test(self): 451 self.log.info("This test is time consuming, please be patient") 452 self.log.info("Splitting inputs so we can generate tx's") 453 454 # Split two coinbases into many small utxos 455 self.start_node(0) 456 self.wallet = MiniWallet(self.nodes[0]) 457 self.initial_split(self.nodes[0]) 458 self.log.info("Finished splitting") 459 460 # Now we can connect the other nodes, didn't want to connect them earlier 461 # so the estimates would not be affected by the splitting transactions 462 self.start_node(1) 463 self.start_node(2) 464 self.connect_nodes(1, 0) 465 self.connect_nodes(0, 2) 466 self.connect_nodes(2, 1) 467 self.sync_all() 468 469 self.log.info("Testing estimates with single transactions.") 470 self.sanity_check_estimates_range() 471 472 self.log.info("Test fee_estimates.dat is flushed periodically") 473 self.test_estimate_dat_is_flushed_periodically() 474 475 # check that estimatesmartfee feerate is greater than or equal to maximum of mempoolminfee and minrelaytxfee 476 self.log.info( 477 "Test fee rate estimation after restarting node with high minrelaytxfee" 478 ) 479 self.test_estimates_with_highminrelaytxfee() 480 481 self.log.info("Test acceptstalefeeestimates option") 482 self.test_acceptstalefeeestimates_option() 483 484 self.log.info("Test reading old fee_estimates.dat") 485 self.test_old_fee_estimate_file() 486 487 self.clear_estimates() 488 489 self.log.info("Testing estimates with RBF.") 490 self.sanity_check_rbf_estimates() 491 492 self.clear_estimates() 493 self.log.info("Test estimatesmartfee modes") 494 self.test_estimation_modes() 495 496 self.clear_estimates() 497 self.log.info("Test that estimatesmartfee returns a sub 1s/vb fee rate estimate") 498 self.test_sub_1s_per_vb_estimates() 499 500 self.log.info("Testing that fee estimation is disabled in blocksonly.") 501 self.restart_node(0, ["-blocksonly"]) 502 assert_raises_rpc_error( 503 -32603, "Fee estimation disabled", self.nodes[0].estimatesmartfee, 2 504 ) 505 506 507 if __name__ == "__main__": 508 EstimateFeeTest(__file__).main()