estimatefee_test.go raw
1 package mempool
2
3 import (
4 "bytes"
5 "github.com/p9c/p9/pkg/amt"
6 block2 "github.com/p9c/p9/pkg/block"
7 "math/rand"
8 "testing"
9
10 "github.com/p9c/p9/pkg/chainhash"
11 "github.com/p9c/p9/pkg/mining"
12 "github.com/p9c/p9/pkg/util"
13 "github.com/p9c/p9/pkg/wire"
14 )
15
16 // estimateFeeTester interacts with the FeeEstimator to keep track of its expected state.
17 type estimateFeeTester struct {
18 ef *FeeEstimator
19 t *testing.T
20 version int32
21 height int32
22 last *lastBlock
23 }
24
25 // lastBlock is a linked list of the block hashes which have been processed by the test FeeEstimator.
26 type lastBlock struct {
27 hash *chainhash.Hash
28 prev *lastBlock
29 }
30
31 func (eft *estimateFeeTester) checkSaveAndRestore(
32 previousEstimates [estimateFeeDepth]DUOPerKilobyte,
33 ) {
34 // Get the save state.
35 save := eft.ef.Save()
36 // Save and restore database.
37 var e error
38 eft.ef, e = RestoreFeeEstimator(save)
39 if e != nil {
40 eft.t.Fatalf("Could not restore database: %s", e)
41 }
42 // Save again and check that it matches the previous one.
43 redo := eft.ef.Save()
44 if !bytes.Equal(save, redo) {
45 eft.t.Fatalf("Restored states do not match: %v %v", save, redo)
46 }
47 // Chk that the results match.
48 newEstimates := eft.estimates()
49 for i, prev := range previousEstimates {
50 if prev != newEstimates[i] {
51 eft.t.Error(
52 "Mismatch in estimate ", i, " after restore; got ",
53 newEstimates[i], " but expected ", prev,
54 )
55 }
56 }
57 }
58
59 func (eft *estimateFeeTester) estimates() [estimateFeeDepth]DUOPerKilobyte {
60 // Generate estimates
61 var estimates [estimateFeeDepth]DUOPerKilobyte
62 for i := 0; i < estimateFeeDepth; i++ {
63 estimates[i], _ = eft.ef.EstimateFee(uint32(i + 1))
64 }
65 // Chk that all estimated fee results go in descending order.
66 for i := 1; i < estimateFeeDepth; i++ {
67 if estimates[i] > estimates[i-1] {
68 eft.t.Error(
69 "Estimates not in descending order; got ",
70 estimates[i], " for estimate ", i, " and ", estimates[i-1],
71 " for ", i-1,
72 )
73 panic("invalid state.")
74 }
75 }
76 return estimates
77 }
78
79 func (eft *estimateFeeTester) newBlock(txs []*wire.MsgTx) {
80 eft.height++
81 block := block2.NewBlock(&wire.Block{Transactions: txs})
82 block.SetHeight(eft.height)
83 eft.last = &lastBlock{block.Hash(), eft.last}
84 e := eft.ef.RegisterBlock(block)
85 if e != nil {
86 W.Ln("failed to register block:", e)
87 }
88 }
89
90 func (eft *estimateFeeTester) rollback() {
91 if eft.last == nil {
92 return
93 }
94 e := eft.ef.Rollback(eft.last.hash)
95 if e != nil {
96 eft.t.Errorf("Could not rollback: %v", e)
97 }
98 eft.height--
99 eft.last = eft.last.prev
100 }
101
102 func (eft *estimateFeeTester) round(
103 txHistory [][]*TxDesc,
104 estimateHistory [][estimateFeeDepth]DUOPerKilobyte, txPerRound,
105 txPerBlock uint32,
106 ) ([][]*TxDesc, [][estimateFeeDepth]DUOPerKilobyte) {
107 // generate new txs.
108 var newTxs []*TxDesc
109 for i := uint32(0); i < txPerRound; i++ {
110 newTx := eft.testTx(amt.Amount(rand.Intn(1000000)))
111 eft.ef.ObserveTransaction(newTx)
112 newTxs = append(newTxs, newTx)
113 }
114 // Generate mempool.
115 mempool := make(map[*observedTransaction]*TxDesc)
116 for _, h := range txHistory {
117 for _, t := range h {
118 if o, exists := eft.ef.observed[*t.Tx.Hash()]; exists && o.
119 mined == mining.UnminedHeight {
120 mempool[o] = t
121 }
122 }
123 }
124 // generate new block, with no duplicates.
125 i := uint32(0)
126 newBlockList := make([]*wire.MsgTx, 0, txPerBlock)
127 for _, t := range mempool {
128 newBlockList = append(newBlockList, t.TxDesc.Tx.MsgTx())
129 i++
130 if i == txPerBlock {
131 break
132 }
133 }
134 // Register a new block.
135 eft.newBlock(newBlockList)
136 // return results.
137 estimates := eft.estimates()
138 // Return results
139 return append(txHistory, newTxs), append(estimateHistory, estimates)
140 }
141
142 func (
143 eft *estimateFeeTester,
144 ) testTx(
145 fee amt.Amount,
146 ) *TxDesc {
147 eft.version++
148 return &TxDesc{
149 TxDesc: mining.TxDesc{
150 Tx: util.NewTx(
151 &wire.MsgTx{
152 Version: eft.version,
153 },
154 ),
155 Height: eft.height,
156 Fee: int64(fee),
157 },
158 StartingPriority: 0,
159 }
160 }
161
162 // TestSave tests saving and restoring to a []byte.
163 func TestDatabase(t *testing.T) {
164 txPerRound := uint32(7)
165 txPerBlock := uint32(5)
166 binSize := uint32(6)
167 maxReplacements := uint32(4)
168 rounds := 8
169 eft := estimateFeeTester{ef: newTestFeeEstimator(binSize, maxReplacements, uint32(rounds)+1), t: t}
170 var txHistory [][]*TxDesc
171 estimateHistory := [][estimateFeeDepth]DUOPerKilobyte{eft.estimates()}
172 for round := 0; round < rounds; round++ {
173 eft.checkSaveAndRestore(estimateHistory[len(estimateHistory)-1])
174 // Go forward one step.
175 txHistory, estimateHistory =
176 eft.round(txHistory, estimateHistory, txPerRound, txPerBlock)
177 }
178 // Reverse the process and try again.
179 for round := 1; round <= rounds; round++ {
180 eft.rollback()
181 eft.checkSaveAndRestore(estimateHistory[len(estimateHistory)-round-1])
182 }
183 }
184
185 // TestEstimateFee tests basic functionality in the FeeEstimator.
186 func TestEstimateFee(t *testing.T) {
187 ef := newTestFeeEstimator(5, 3, 1)
188 eft := estimateFeeTester{ef: ef, t: t}
189 // Try with no txs and get zero for all queries.
190 expected := DUOPerKilobyte(0.0)
191 for i := uint32(1); i <= estimateFeeDepth; i++ {
192 estimated, _ := ef.EstimateFee(i)
193 if estimated != expected {
194 t.Errorf(
195 "Estimate fee error: expected %f when estimator is"+
196 " empty; got %f", expected, estimated,
197 )
198 }
199 }
200 // Now insert a tx.
201 tx := eft.testTx(1000000)
202 ef.ObserveTransaction(tx)
203 // Expected should still be zero because this is still in the mempool.
204 expected = DUOPerKilobyte(0.0)
205 for i := uint32(1); i <= estimateFeeDepth; i++ {
206 estimated, _ := ef.EstimateFee(i)
207 if estimated != expected {
208 t.Errorf(
209 "Estimate fee error: expected %f when estimator has one"+
210 " tx in mempool; got %f", expected, estimated,
211 )
212 }
213 }
214 // Change minRegisteredBlocks to make sure that works. Error return value expected.
215 ef.minRegisteredBlocks = 1
216 expected = DUOPerKilobyte(-1.0)
217 for i := uint32(1); i <= estimateFeeDepth; i++ {
218 estimated, _ := ef.EstimateFee(i)
219 if estimated != expected {
220 t.Errorf(
221 "Estimate fee error: expected %f before any blocks have"+
222 " been registered; got %f", expected, estimated,
223 )
224 }
225 }
226 // Record a block with the new tx.
227 eft.newBlock([]*wire.MsgTx{tx.Tx.MsgTx()})
228 expected = expectedFeePerKilobyte(tx)
229 for i := uint32(1); i <= estimateFeeDepth; i++ {
230 estimated, _ := ef.EstimateFee(i)
231 if estimated != expected {
232 t.Errorf(
233 "Estimate fee error: expected %f when one tx is binned"+
234 "; got %f", expected, estimated,
235 )
236 }
237 }
238 // Roll back the last block; this was an orphan block.
239 ef.minRegisteredBlocks = 0
240 eft.rollback()
241 expected = DUOPerKilobyte(0.0)
242 for i := uint32(1); i <= estimateFeeDepth; i++ {
243 estimated, _ := ef.EstimateFee(i)
244 if estimated != expected {
245 t.Errorf(
246 "Estimate fee error: expected %f after rolling back"+
247 " block; got %f", expected, estimated,
248 )
249 }
250 }
251 // Record an empty block and then a block with the new tx. This test was made because of a bug that only appeared
252 // when there were no transactions in the first bin.
253 eft.newBlock([]*wire.MsgTx{})
254 eft.newBlock([]*wire.MsgTx{tx.Tx.MsgTx()})
255 expected = expectedFeePerKilobyte(tx)
256 for i := uint32(1); i <= estimateFeeDepth; i++ {
257 estimated, _ := ef.EstimateFee(i)
258 if estimated != expected {
259 t.Errorf(
260 "Estimate fee error: expected %f when one tx is binned"+
261 "; got %f", expected, estimated,
262 )
263 }
264 }
265 // Create some more transactions.
266 txA := eft.testTx(500000)
267 txB := eft.testTx(2000000)
268 txC := eft.testTx(4000000)
269 ef.ObserveTransaction(txA)
270 ef.ObserveTransaction(txB)
271 ef.ObserveTransaction(txC)
272 // Record 7 empty blocks.
273 for i := 0; i < 7; i++ {
274 eft.newBlock([]*wire.MsgTx{})
275 }
276 // Mine the first tx.
277 eft.newBlock([]*wire.MsgTx{txA.Tx.MsgTx()})
278 // Now the estimated amount should depend on the value of the argument to estimate fee.
279 for i := uint32(1); i <= estimateFeeDepth; i++ {
280 estimated, _ := ef.EstimateFee(i)
281 if i > 2 {
282 expected = expectedFeePerKilobyte(txA)
283 } else {
284 expected = expectedFeePerKilobyte(tx)
285 }
286 if estimated != expected {
287 t.Errorf(
288 "Estimate fee error: expected %f on round %d; got %f",
289 expected, i, estimated,
290 )
291 }
292 }
293 // Record 5 more empty blocks.
294 for i := 0; i < 5; i++ {
295 eft.newBlock([]*wire.MsgTx{})
296 }
297 // Mine the next tx.
298 eft.newBlock([]*wire.MsgTx{txB.Tx.MsgTx()})
299 // Now the estimated amount should depend on the value of the argument to estimate fee.
300 for i := uint32(1); i <= estimateFeeDepth; i++ {
301 estimated, _ := ef.EstimateFee(i)
302 switch {
303 case i <= 2:
304 expected = expectedFeePerKilobyte(txB)
305 case i <= 8:
306 expected = expectedFeePerKilobyte(tx)
307 default:
308 expected = expectedFeePerKilobyte(txA)
309 }
310 if estimated != expected {
311 t.Errorf(
312 "Estimate fee error: expected %f on round %d; got %f",
313 expected, i, estimated,
314 )
315 }
316 }
317 // Record 9 more empty blocks.
318 for i := 0; i < 10; i++ {
319 eft.newBlock([]*wire.MsgTx{})
320 }
321 // Mine txC.
322 eft.newBlock([]*wire.MsgTx{txC.Tx.MsgTx()})
323 // This should have no effect on the outcome because too many blocks have been mined for txC to be recorded.
324 for i := uint32(1); i <= estimateFeeDepth; i++ {
325 estimated, _ := ef.EstimateFee(i)
326 switch {
327 case i <= 2:
328 expected = expectedFeePerKilobyte(txC)
329 case i <= 8:
330 expected = expectedFeePerKilobyte(txB)
331 case i <= 8+6:
332 expected = expectedFeePerKilobyte(tx)
333 default:
334 expected = expectedFeePerKilobyte(txA)
335 }
336 if estimated != expected {
337 t.Errorf("Estimate fee error: expected %f on round %d; got %f", expected, i, estimated)
338 }
339 }
340 }
341
342 // TestEstimateFeeRollback tests the rollback function, which undoes the effect of a adding a new block.
343 func TestEstimateFeeRollback(t *testing.T) {
344 txPerRound := uint32(7)
345 txPerBlock := uint32(5)
346 binSize := uint32(6)
347 maxReplacements := uint32(4)
348 stepsBack := 2
349 rounds := 30
350 eft := estimateFeeTester{
351 ef: newTestFeeEstimator(
352 binSize,
353 maxReplacements, uint32(stepsBack),
354 ), t: t,
355 }
356 var txHistory [][]*TxDesc
357 estimateHistory := [][estimateFeeDepth]DUOPerKilobyte{eft.estimates()}
358 for round := 0; round < rounds; round++ {
359 // Go forward a few rounds.
360 for step := 0; step <= stepsBack; step++ {
361 txHistory, estimateHistory =
362 eft.round(txHistory, estimateHistory, txPerRound, txPerBlock)
363 }
364 // Now go back.
365 for step := 0; step < stepsBack; step++ {
366 eft.rollback()
367 // After rolling back we should have the same estimated fees as before.
368 expected := estimateHistory[len(estimateHistory)-step-2]
369 estimates := eft.estimates()
370 // Ensure that these are both the same.
371 for i := 0; i < estimateFeeDepth; i++ {
372 if expected[i] != estimates[i] {
373 t.Errorf(
374 "Rollback value mismatch. Expected %f, got %f. ",
375 expected[i], estimates[i],
376 )
377 return
378 }
379 }
380 }
381 // Erase history.
382 txHistory = txHistory[0 : len(txHistory)-stepsBack]
383 estimateHistory = estimateHistory[0 : len(estimateHistory)-stepsBack]
384 }
385 }
386 func expectedFeePerKilobyte(t *TxDesc) DUOPerKilobyte {
387 size := float64(t.TxDesc.Tx.MsgTx().SerializeSize())
388 fee := float64(t.TxDesc.Fee)
389 return SatoshiPerByte(fee / size).ToBtcPerKb()
390 }
391
392 // newTestFeeEstimator creates a feeEstimator with some different parameters for testing purposes.
393 func newTestFeeEstimator(binSize, maxReplacements, maxRollback uint32) *FeeEstimator {
394 return &FeeEstimator{
395 maxRollback: maxRollback,
396 lastKnownHeight: 0,
397 binSize: int32(binSize),
398 minRegisteredBlocks: 0,
399 maxReplacements: int32(maxReplacements),
400 observed: make(map[chainhash.Hash]*observedTransaction),
401 dropped: make([]*registeredBlock, 0, maxRollback),
402 }
403 }
404