mempool_fee_histogram.py raw
1 #!/usr/bin/env python3
2 # Copyright (c) 2023 The Limenka 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 mempool fee histogram."""
6
7 from decimal import Decimal
8
9 from test_framework.blocktools import COINBASE_MATURITY
10 from test_framework.messages import (
11 COIN,
12 )
13 from test_framework.test_framework import LimenkaTestFramework
14 from test_framework.util import (
15 assert_equal,
16 assert_greater_than,
17 assert_greater_than_or_equal,
18 )
19
20 def get_actual_fee_rate(fee_in_satoshis, vsize):
21 # NOTE: Must round down, unlike ceildiv/get_fee
22 fee_rate = fee_in_satoshis // vsize
23 return str(fee_rate)
24
25 def get_tx_details(node, txid):
26 info = node.gettransaction(txid=txid)
27 info.update(node.getrawtransaction(txid=txid, verbose=True))
28 info['fee'] = int(-info['fee'] * COIN) # convert to satoshis
29 info['feerate'] = get_actual_fee_rate(info['fee'], info['vsize'])
30 return info
31
32 class MempoolFeeHistogramTest(LimenkaTestFramework):
33 def add_options(self, parser):
34 self.add_wallet_options(parser)
35
36 def set_test_params(self):
37 self.setup_clean_chain = True
38 self.num_nodes = 1
39
40 def skip_test_if_missing_module(self):
41 self.skip_if_no_wallet()
42
43 def run_test(self):
44 node = self.nodes[0]
45 self.generate(self.nodes[0], COINBASE_MATURITY + 2, sync_fun=self.no_op)
46
47 # We have two UTXOs (utxo_1 and utxo_2) and we create three changeless transactions:
48 # - tx1 (5 sat/vB): spending utxo_1
49 # - tx2 (14 sat/vB): spending output from tx1
50 # - tx3 (6 sat/vB): spending utxo_2 and the output from tx2
51
52 self.log.info("Test getmempoolinfo does not return fee histogram by default")
53 assert ("fee_histogram" not in node.getmempoolinfo())
54
55 self.log.info("Test getmempoolinfo returns empty fee histogram when mempool is empty")
56 info = node.getmempoolinfo([1, 2, 3])
57
58 (non_empty_groups, empty_groups, total_fees) = self.histogram_stats(info['fee_histogram'])
59 assert_equal(0, non_empty_groups)
60 assert_equal(3, empty_groups)
61 assert_equal(0, total_fees)
62
63 for i in ['1', '2', '3']:
64 assert_equal(0, info['fee_histogram'][i]['sizes'])
65 assert_equal(0, info['fee_histogram'][i]['count'])
66 assert_equal(0, info['fee_histogram'][i]['fees'])
67 assert_equal(int(i), info['fee_histogram'][i]['from_feerate'])
68
69 self.log.info("Test that we have two spendable UTXOs and lock the second one")
70 utxos = node.listunspent()
71 assert_equal(2, len(utxos))
72 node.lockunspent(False, [{"txid": utxos[1]["txid"], "vout": utxos[1]["vout"]}])
73
74 self.log.info("Send tx1 transaction with 5 sat/vB fee rate")
75 tx1_txid = node.sendtoaddress(address=node.getnewaddress(), amount=Decimal("50.0"), fee_rate=5, subtractfeefromamount=True)
76 tx1_info = get_tx_details(node, tx1_txid)
77
78 self.log.info(f"Test fee rate histogram when mempool contains 1 transaction (tx1: {tx1_info['feerate']} sat/vB)")
79 info = node.getmempoolinfo([1, 3, 5, 10])
80 (non_empty_groups, empty_groups, total_fees) = self.histogram_stats(info['fee_histogram'])
81 assert_equal(1, non_empty_groups)
82 assert_equal(3, empty_groups)
83 assert_equal(1, info['fee_histogram'][tx1_info['feerate']]['count'])
84 assert_equal(total_fees, info['fee_histogram']['total_fees'])
85
86 assert_equal(0, info['fee_histogram']['1']['sizes'])
87 assert_equal(0, info['fee_histogram']['1']['count'])
88 assert_equal(0, info['fee_histogram']['1']['fees'])
89 assert_equal(1, info['fee_histogram']['1']['from_feerate'])
90
91 assert_equal(0, info['fee_histogram']['3']['sizes'])
92 assert_equal(0, info['fee_histogram']['3']['count'])
93 assert_equal(0, info['fee_histogram']['3']['fees'])
94 assert_equal(3, info['fee_histogram']['3']['from_feerate'])
95
96 assert_equal(tx1_info['vsize'], info['fee_histogram']['5']['sizes'])
97 assert_equal(1, info['fee_histogram']['5']['count'])
98 assert_equal(tx1_info['fee'], info['fee_histogram']['5']['fees'])
99 assert_equal(5, info['fee_histogram']['5']['from_feerate'])
100
101 assert_equal(0, info['fee_histogram']['10']['sizes'])
102 assert_equal(0, info['fee_histogram']['10']['count'])
103 assert_equal(0, info['fee_histogram']['10']['fees'])
104 assert_equal(10, info['fee_histogram']['10']['from_feerate'])
105
106 self.log.info("Send tx2 transaction with 14 sat/vB fee rate (spends tx1 UTXO)")
107 tx2_txid = node.sendtoaddress(address=node.getnewaddress(), amount=Decimal("25.0"), fee_rate=14, subtractfeefromamount=True)
108 tx2_info = get_tx_details(node, tx2_txid)
109
110 self.log.info(f"Test fee rate histogram when mempool contains 2 transactions (tx1: {tx1_info['feerate']} sat/vB, tx2: {tx2_info['feerate']} sat/vB)")
111 info = node.getmempoolinfo([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15])
112
113 # Verify that both tx1 and tx2 are reported in 8 sat/vB fee rate group
114 (non_empty_groups, empty_groups, total_fees) = self.histogram_stats(info['fee_histogram'])
115 tx1p2_feerate = get_actual_fee_rate(tx1_info['fee'] + tx2_info['fee'], tx1_info['vsize'] + tx2_info['vsize'])
116 assert_equal(1, non_empty_groups)
117 assert_equal(14, empty_groups)
118 assert_equal(2, info['fee_histogram'][tx1p2_feerate]['count'])
119 assert_equal(total_fees, info['fee_histogram']['total_fees'])
120
121 # Unlock the second UTXO which we locked
122 node.lockunspent(True, [{"txid": utxos[1]["txid"], "vout": utxos[1]["vout"]}])
123
124 self.log.info("Send tx3 transaction with 6 sat/vB fee rate (spends all available UTXOs)")
125 tx3_txid = node.sendtoaddress(address=node.getnewaddress(), amount=Decimal("99.9"), fee_rate=6, subtractfeefromamount=True)
126 tx3_info = get_tx_details(node, tx3_txid)
127
128 self.log.info(f"Test fee rate histogram when mempool contains 3 transactions (tx1: {tx1_info['feerate']} sat/vB, tx2: {tx2_info['feerate']} sat/vB, tx3: {tx3_info['feerate']} sat/vB)")
129 info = node.getmempoolinfo([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15])
130
131 # Verify that each of 6, 8 and 9 sat/vB fee rate groups contain one transaction
132 # tx1 should be grouped with tx2 + tx3 (descendants)
133 # tx2 should be grouped with tx1 (ancestors only)
134 # tx3 should be alone
135 expected_histogram = dict(
136 tuple(
137 (str(n), {
138 'from_feerate': n,
139 'to_feerate': n + 1,
140 'count': 0,
141 'fees': 0,
142 'sizes': 0,
143 }) for n in range(1, 16)
144 ) + (
145 ('total_fees', tx1_info['fee'] + tx2_info['fee'] + tx3_info['fee']),
146 )
147 )
148 expected_frg = expected_histogram
149 expected_frg['15']['to_feerate'] = 9223372036854775807
150 tx1p2p3_feerate = get_actual_fee_rate(expected_histogram['total_fees'], tx1_info['vsize'] + tx2_info['vsize'] + tx3_info['vsize'])
151 def inc_expected(feerate, txinfo):
152 this_frg = expected_frg[feerate]
153 this_frg['count'] += 1
154 this_frg['fees'] += txinfo['fee']
155 this_frg['sizes'] += txinfo['vsize']
156 inc_expected(tx1p2p3_feerate, tx1_info)
157 inc_expected(tx1p2_feerate, tx2_info)
158 inc_expected(tx3_info['feerate'], tx3_info)
159
160 assert_equal(expected_histogram, info['fee_histogram'])
161
162 self.log.info("Test fee rate histogram with default groups")
163 info = node.getmempoolinfo(with_fee_histogram=True)
164
165 # Verify that the 6 sat/vB fee rate group has one transaction, and the 8-9 sat/vB fee rate group has two
166 for collapse_n in (9, 11, 13, 15):
167 for field in ('count', 'sizes', 'fees'):
168 expected_frg[str(collapse_n - 1)][field] += expected_frg[str(collapse_n)][field]
169 expected_frg[str(collapse_n - 1)]['to_feerate'] += 1
170 del expected_frg[str(collapse_n)]
171 expected_frg['14']['to_feerate'] += 1 # 16 is also skipped
172
173 for new_n in (17, 20, 25) + tuple(range(30, 90, 10)) + (100, 120, 140, 170, 200, 250) + tuple(range(300, 900, 100)) + (1000, 1200, 1400, 1700, 2000, 2500) + tuple(range(3000, 9000, 1000)) + (10000,):
174 frinfo = info['fee_histogram'][str(new_n)]
175 assert frinfo['to_feerate'] > frinfo['from_feerate']
176 del frinfo['to_feerate']
177 assert_equal(frinfo, {
178 'from_feerate': new_n,
179 'count': 0,
180 'fees': 0,
181 'sizes': 0,
182 })
183 del info['fee_histogram'][str(new_n)]
184 assert_equal(expected_histogram, info['fee_histogram'])
185
186 self.log.info("Test getmempoolinfo(with_fee_histogram=False) does not return fee histogram")
187 assert('fee_histogram' not in node.getmempoolinfo(with_fee_histogram=False))
188
189 def histogram_stats(self, histogram):
190 total_fees = 0
191 empty_count = 0
192 non_empty_count = 0
193
194 for key, bin in histogram.items():
195 if key == 'total_fees':
196 continue
197 assert_equal(int(key), bin['from_feerate'])
198 if bin['fees'] > 0:
199 assert_greater_than(bin['count'], 0)
200 else:
201 assert_equal(bin['count'], 0)
202 assert_greater_than_or_equal(bin['fees'], 0)
203 assert_greater_than_or_equal(bin['sizes'], 0)
204 if bin['to_feerate'] is not None:
205 assert_greater_than_or_equal(bin['to_feerate'], bin['from_feerate'])
206 for next_key in sorted((*(int(a) for a in histogram.keys() if a != 'total_fees'), 0x7fffffffffffffff)):
207 if int(next_key) <= int(key):
208 continue
209 assert_equal(bin['to_feerate'], int(next_key))
210 break
211 total_fees += bin['fees']
212
213 if bin['count'] == 0:
214 empty_count += 1
215 else:
216 non_empty_count += 1
217
218 return (non_empty_count, empty_count, total_fees)
219
220 if __name__ == '__main__':
221 MempoolFeeHistogramTest(__file__).main()
222