vendor/github.com/btcsuite/btcd/mempool/mempool_test.go

   1 // Copyright (c) 2016 The btcsuite developers
   2 // Use of this source code is governed by an ISC
   3 // license that can be found in the LICENSE file.
   4
   5 package mempool
   6
   7 import (
   8         "encoding/hex"
   9         "reflect"
  10         "runtime"
  11         "sync"
  12         "testing"
  13         "time"
  14
  15         "github.com/btcsuite/btcd/blockchain"
  16         "github.com/btcsuite/btcd/btcec"
  17         "github.com/btcsuite/btcd/chaincfg"
  18         "github.com/btcsuite/btcd/chaincfg/chainhash"
  19         "github.com/btcsuite/btcd/txscript"
  20         "github.com/btcsuite/btcd/wire"
  21         "github.com/btcsuite/btcutil"
  22 )
  23
  24 // fakeChain is used by the pool harness to provide generated test utxos and
  25 // a current faked chain height to the pool callbacks.  This, in turn, allows
  26 // transations to be appear as though they are spending completely valid utxos.
  27 type fakeChain struct {
  28         sync.RWMutex
  29         utxos          *blockchain.UtxoViewpoint
  30         currentHeight  int32
  31         medianTimePast time.Time
  32 }
  33
  34 // FetchUtxoView loads utxo details about the input transactions referenced by
  35 // the passed transaction from the point of view of the fake chain.
  36 // It also attempts to fetch the utxo details for the transaction itself so the
  37 // returned view can be examined for duplicate unspent transaction outputs.
  38 //
  39 // This function is safe for concurrent access however the returned view is NOT.
  40 func (s *fakeChain) FetchUtxoView(tx *btcutil.Tx) (*blockchain.UtxoViewpoint, error) {
  41         s.RLock()
  42         defer s.RUnlock()
  43
  44         // All entries are cloned to ensure modifications to the returned view
  45         // do not affect the fake chain's view.
  46
  47         // Add an entry for the tx itself to the new view.
  48         viewpoint := blockchain.NewUtxoViewpoint()
  49         entry := s.utxos.LookupEntry(tx.Hash())
  50         viewpoint.Entries()[*tx.Hash()] = entry.Clone()
  51
  52         // Add entries for all of the inputs to the tx to the new view.
  53         for _, txIn := range tx.MsgTx().TxIn {
  54                 originHash := &txIn.PreviousOutPoint.Hash
  55                 entry := s.utxos.LookupEntry(originHash)
  56                 viewpoint.Entries()[*originHash] = entry.Clone()
  57         }
  58
  59         return viewpoint, nil
  60 }
  61
  62 // BestHeight returns the current height associated with the fake chain
  63 // instance.
  64 func (s *fakeChain) BestHeight() int32 {
  65         s.RLock()
  66         height := s.currentHeight
  67         s.RUnlock()
  68         return height
  69 }
  70
  71 // SetHeight sets the current height associated with the fake chain instance.
  72 func (s *fakeChain) SetHeight(height int32) {
  73         s.Lock()
  74         s.currentHeight = height
  75         s.Unlock()
  76 }
  77
  78 // MedianTimePast returns the current median time past associated with the fake
  79 // chain instance.
  80 func (s *fakeChain) MedianTimePast() time.Time {
  81         s.RLock()
  82         mtp := s.medianTimePast
  83         s.RUnlock()
  84         return mtp
  85 }
  86
  87 // SetMedianTimePast sets the current median time past associated with the fake
  88 // chain instance.
  89 func (s *fakeChain) SetMedianTimePast(mtp time.Time) {
  90         s.Lock()
  91         s.medianTimePast = mtp
  92         s.Unlock()
  93 }
  94
  95 // CalcSequenceLock returns the current sequence lock for the passed
  96 // transaction associated with the fake chain instance.
  97 func (s *fakeChain) CalcSequenceLock(tx *btcutil.Tx,
  98         view *blockchain.UtxoViewpoint) (*blockchain.SequenceLock, error) {
  99
 100         return &blockchain.SequenceLock{
 101                 Seconds:     -1,
 102                 BlockHeight: -1,
 103         }, nil
 104 }
 105
 106 // spendableOutput is a convenience type that houses a particular utxo and the
 107 // amount associated with it.
 108 type spendableOutput struct {
 109         outPoint wire.OutPoint
 110         amount   btcutil.Amount
 111 }
 112
 113 // txOutToSpendableOut returns a spendable output given a transaction and index
 114 // of the output to use.  This is useful as a convenience when creating test
 115 // transactions.
 116 func txOutToSpendableOut(tx *btcutil.Tx, outputNum uint32) spendableOutput {
 117         return spendableOutput{
 118                 outPoint: wire.OutPoint{Hash: *tx.Hash(), Index: outputNum},
 119                 amount:   btcutil.Amount(tx.MsgTx().TxOut[outputNum].Value),
 120         }
 121 }
 122
 123 // poolHarness provides a harness that includes functionality for creating and
 124 // signing transactions as well as a fake chain that provides utxos for use in
 125 // generating valid transactions.
 126 type poolHarness struct {
 127         // signKey is the signing key used for creating transactions throughout
 128         // the tests.
 129         //
 130         // payAddr is the p2sh address for the signing key and is used for the
 131         // payment address throughout the tests.
 132         signKey     *btcec.PrivateKey
 133         payAddr     btcutil.Address
 134         payScript   []byte
 135         chainParams *chaincfg.Params
 136
 137         chain  *fakeChain
 138         txPool *TxPool
 139 }
 140
 141 // CreateCoinbaseTx returns a coinbase transaction with the requested number of
 142 // outputs paying an appropriate subsidy based on the passed block height to the
 143 // address associated with the harness.  It automatically uses a standard
 144 // signature script that starts with the block height that is required by
 145 // version 2 blocks.
 146 func (p *poolHarness) CreateCoinbaseTx(blockHeight int32, numOutputs uint32) (*btcutil.Tx, error) {
 147         // Create standard coinbase script.
 148         extraNonce := int64(0)
 149         coinbaseScript, err := txscript.NewScriptBuilder().
 150                 AddInt64(int64(blockHeight)).AddInt64(extraNonce).Script()
 151         if err != nil {
 152                 return nil, err
 153         }
 154
 155         tx := wire.NewMsgTx(wire.TxVersion)
 156         tx.AddTxIn(&wire.TxIn{
 157                 // Coinbase transactions have no inputs, so previous outpoint is
 158                 // zero hash and max index.
 159                 PreviousOutPoint: *wire.NewOutPoint(&chainhash.Hash{},
 160                         wire.MaxPrevOutIndex),
 161                 SignatureScript: coinbaseScript,
 162                 Sequence:        wire.MaxTxInSequenceNum,
 163         })
 164         totalInput := blockchain.CalcBlockSubsidy(blockHeight, p.chainParams)
 165         amountPerOutput := totalInput / int64(numOutputs)
 166         remainder := totalInput - amountPerOutput*int64(numOutputs)
 167         for i := uint32(0); i < numOutputs; i++ {
 168                 // Ensure the final output accounts for any remainder that might
 169                 // be left from splitting the input amount.
 170                 amount := amountPerOutput
 171                 if i == numOutputs-1 {
 172                         amount = amountPerOutput + remainder
 173                 }
 174                 tx.AddTxOut(&wire.TxOut{
 175                         PkScript: p.payScript,
 176                         Value:    amount,
 177                 })
 178         }
 179
 180         return btcutil.NewTx(tx), nil
 181 }
 182
 183 // CreateSignedTx creates a new signed transaction that consumes the provided
 184 // inputs and generates the provided number of outputs by evenly splitting the
 185 // total input amount.  All outputs will be to the payment script associated
 186 // with the harness and all inputs are assumed to do the same.
 187 func (p *poolHarness) CreateSignedTx(inputs []spendableOutput, numOutputs uint32) (*btcutil.Tx, error) {
 188         // Calculate the total input amount and split it amongst the requested
 189         // number of outputs.
 190         var totalInput btcutil.Amount
 191         for _, input := range inputs {
 192                 totalInput += input.amount
 193         }
 194         amountPerOutput := int64(totalInput) / int64(numOutputs)
 195         remainder := int64(totalInput) - amountPerOutput*int64(numOutputs)
 196
 197         tx := wire.NewMsgTx(wire.TxVersion)
 198         for _, input := range inputs {
 199                 tx.AddTxIn(&wire.TxIn{
 200                         PreviousOutPoint: input.outPoint,
 201                         SignatureScript:  nil,
 202                         Sequence:         wire.MaxTxInSequenceNum,
 203                 })
 204         }
 205         for i := uint32(0); i < numOutputs; i++ {
 206                 // Ensure the final output accounts for any remainder that might
 207                 // be left from splitting the input amount.
 208                 amount := amountPerOutput
 209                 if i == numOutputs-1 {
 210                         amount = amountPerOutput + remainder
 211                 }
 212                 tx.AddTxOut(&wire.TxOut{
 213                         PkScript: p.payScript,
 214                         Value:    amount,
 215                 })
 216         }
 217
 218         // Sign the new transaction.
 219         for i := range tx.TxIn {
 220                 sigScript, err := txscript.SignatureScript(tx, i, p.payScript,
 221                         txscript.SigHashAll, p.signKey, true)
 222                 if err != nil {
 223                         return nil, err
 224                 }
 225                 tx.TxIn[i].SignatureScript = sigScript
 226         }
 227
 228         return btcutil.NewTx(tx), nil
 229 }
 230
 231 // CreateTxChain creates a chain of zero-fee transactions (each subsequent
 232 // transaction spends the entire amount from the previous one) with the first
 233 // one spending the provided outpoint.  Each transaction spends the entire
 234 // amount of the previous one and as such does not include any fees.
 235 func (p *poolHarness) CreateTxChain(firstOutput spendableOutput, numTxns uint32) ([]*btcutil.Tx, error) {
 236         txChain := make([]*btcutil.Tx, 0, numTxns)
 237         prevOutPoint := firstOutput.outPoint
 238         spendableAmount := firstOutput.amount
 239         for i := uint32(0); i < numTxns; i++ {
 240                 // Create the transaction using the previous transaction output
 241                 // and paying the full amount to the payment address associated
 242                 // with the harness.
 243                 tx := wire.NewMsgTx(wire.TxVersion)
 244                 tx.AddTxIn(&wire.TxIn{
 245                         PreviousOutPoint: prevOutPoint,
 246                         SignatureScript:  nil,
 247                         Sequence:         wire.MaxTxInSequenceNum,
 248                 })
 249                 tx.AddTxOut(&wire.TxOut{
 250                         PkScript: p.payScript,
 251                         Value:    int64(spendableAmount),
 252                 })
 253
 254                 // Sign the new transaction.
 255                 sigScript, err := txscript.SignatureScript(tx, 0, p.payScript,
 256                         txscript.SigHashAll, p.signKey, true)
 257                 if err != nil {
 258                         return nil, err
 259                 }
 260                 tx.TxIn[0].SignatureScript = sigScript
 261
 262                 txChain = append(txChain, btcutil.NewTx(tx))
 263
 264                 // Next transaction uses outputs from this one.
 265                 prevOutPoint = wire.OutPoint{Hash: tx.TxHash(), Index: 0}
 266         }
 267
 268         return txChain, nil
 269 }
 270
 271 // newPoolHarness returns a new instance of a pool harness initialized with a
 272 // fake chain and a TxPool bound to it that is configured with a policy suitable
 273 // for testing.  Also, the fake chain is populated with the returned spendable
 274 // outputs so the caller can easily create new valid transactions which build
 275 // off of it.
 276 func newPoolHarness(chainParams *chaincfg.Params) (*poolHarness, []spendableOutput, error) {
 277         // Use a hard coded key pair for deterministic results.
 278         keyBytes, err := hex.DecodeString("700868df1838811ffbdf918fb482c1f7e" +
 279                 "ad62db4b97bd7012c23e726485e577d")
 280         if err != nil {
 281                 return nil, nil, err
 282         }
 283         signKey, signPub := btcec.PrivKeyFromBytes(btcec.S256(), keyBytes)
 284
 285         // Generate associated pay-to-script-hash address and resulting payment
 286         // script.
 287         pubKeyBytes := signPub.SerializeCompressed()
 288         payPubKeyAddr, err := btcutil.NewAddressPubKey(pubKeyBytes, chainParams)
 289         if err != nil {
 290                 return nil, nil, err
 291         }
 292         payAddr := payPubKeyAddr.AddressPubKeyHash()
 293         pkScript, err := txscript.PayToAddrScript(payAddr)
 294         if err != nil {
 295                 return nil, nil, err
 296         }
 297
 298         // Create a new fake chain and harness bound to it.
 299         chain := &fakeChain{utxos: blockchain.NewUtxoViewpoint()}
 300         harness := poolHarness{
 301                 signKey:     signKey,
 302                 payAddr:     payAddr,
 303                 payScript:   pkScript,
 304                 chainParams: chainParams,
 305
 306                 chain: chain,
 307                 txPool: New(&Config{
 308                         Policy: Policy{
 309                                 DisableRelayPriority: true,
 310                                 FreeTxRelayLimit:     15.0,
 311                                 MaxOrphanTxs:         5,
 312                                 MaxOrphanTxSize:      1000,
 313                                 MaxSigOpCostPerTx:    blockchain.MaxBlockSigOpsCost / 4,
 314                                 MinRelayTxFee:        1000, // 1 Satoshi per byte
 315                                 MaxTxVersion:         1,
 316                         },
 317                         ChainParams:      chainParams,
 318                         FetchUtxoView:    chain.FetchUtxoView,
 319                         BestHeight:       chain.BestHeight,
 320                         MedianTimePast:   chain.MedianTimePast,
 321                         CalcSequenceLock: chain.CalcSequenceLock,
 322                         SigCache:         nil,
 323                         AddrIndex:        nil,
 324                 }),
 325         }
 326
 327         // Create a single coinbase transaction and add it to the harness
 328         // chain's utxo set and set the harness chain height such that the
 329         // coinbase will mature in the next block.  This ensures the txpool
 330         // accepts transactions which spend immature coinbases that will become
 331         // mature in the next block.
 332         numOutputs := uint32(1)
 333         outputs := make([]spendableOutput, 0, numOutputs)
 334         curHeight := harness.chain.BestHeight()
 335         coinbase, err := harness.CreateCoinbaseTx(curHeight+1, numOutputs)
 336         if err != nil {
 337                 return nil, nil, err
 338         }
 339         harness.chain.utxos.AddTxOuts(coinbase, curHeight+1)
 340         for i := uint32(0); i < numOutputs; i++ {
 341                 outputs = append(outputs, txOutToSpendableOut(coinbase, i))
 342         }
 343         harness.chain.SetHeight(int32(chainParams.CoinbaseMaturity) + curHeight)
 344         harness.chain.SetMedianTimePast(time.Now())
 345
 346         return &harness, outputs, nil
 347 }
 348
 349 // testContext houses a test-related state that is useful to pass to helper
 350 // functions as a single argument.
 351 type testContext struct {
 352         t       *testing.T
 353         harness *poolHarness
 354 }
 355
 356 // testPoolMembership tests the transaction pool associated with the provided
 357 // test context to determine if the passed transaction matches the provided
 358 // orphan pool and transaction pool status.  It also further determines if it
 359 // should be reported as available by the HaveTransaction function based upon
 360 // the two flags and tests that condition as well.
 361 func testPoolMembership(tc *testContext, tx *btcutil.Tx, inOrphanPool, inTxPool bool) {
 362         txHash := tx.Hash()
 363         gotOrphanPool := tc.harness.txPool.IsOrphanInPool(txHash)
 364         if inOrphanPool != gotOrphanPool {
 365                 _, file, line, _ := runtime.Caller(1)
 366                 tc.t.Fatalf("%s:%d -- IsOrphanInPool: want %v, got %v", file,
 367                         line, inOrphanPool, gotOrphanPool)
 368         }
 369
 370         gotTxPool := tc.harness.txPool.IsTransactionInPool(txHash)
 371         if inTxPool != gotTxPool {
 372                 _, file, line, _ := runtime.Caller(1)
 373                 tc.t.Fatalf("%s:%d -- IsTransactionInPool: want %v, got %v",
 374                         file, line, inTxPool, gotTxPool)
 375         }
 376
 377         gotHaveTx := tc.harness.txPool.HaveTransaction(txHash)
 378         wantHaveTx := inOrphanPool || inTxPool
 379         if wantHaveTx != gotHaveTx {
 380                 _, file, line, _ := runtime.Caller(1)
 381                 tc.t.Fatalf("%s:%d -- HaveTransaction: want %v, got %v", file,
 382                         line, wantHaveTx, gotHaveTx)
 383         }
 384 }
 385
 386 // TestSimpleOrphanChain ensures that a simple chain of orphans is handled
 387 // properly.  In particular, it generates a chain of single input, single output
 388 // transactions and inserts them while skipping the first linking transaction so
 389 // they are all orphans.  Finally, it adds the linking transaction and ensures
 390 // the entire orphan chain is moved to the transaction pool.
 391 func TestSimpleOrphanChain(t *testing.T) {
 392         t.Parallel()
 393
 394         harness, spendableOuts, err := newPoolHarness(&chaincfg.MainNetParams)
 395         if err != nil {
 396                 t.Fatalf("unable to create test pool: %v", err)
 397         }
 398         tc := &testContext{t, harness}
 399
 400         // Create a chain of transactions rooted with the first spendable output
 401         // provided by the harness.
 402         maxOrphans := uint32(harness.txPool.cfg.Policy.MaxOrphanTxs)
 403         chainedTxns, err := harness.CreateTxChain(spendableOuts[0], maxOrphans+1)
 404         if err != nil {
 405                 t.Fatalf("unable to create transaction chain: %v", err)
 406         }
 407
 408         // Ensure the orphans are accepted (only up to the maximum allowed so
 409         // none are evicted).
 410         for _, tx := range chainedTxns[1 : maxOrphans+1] {
 411                 acceptedTxns, err := harness.txPool.ProcessTransaction(tx, true,
 412                         false, 0)
 413                 if err != nil {
 414                         t.Fatalf("ProcessTransaction: failed to accept valid "+
 415                                 "orphan %v", err)
 416                 }
 417
 418                 // Ensure no transactions were reported as accepted.
 419                 if len(acceptedTxns) != 0 {
 420                         t.Fatalf("ProcessTransaction: reported %d accepted "+
 421                                 "transactions from what should be an orphan",
 422                                 len(acceptedTxns))
 423                 }
 424
 425                 // Ensure the transaction is in the orphan pool, is not in the
 426                 // transaction pool, and is reported as available.
 427                 testPoolMembership(tc, tx, true, false)
 428         }
 429
 430         // Add the transaction which completes the orphan chain and ensure they
 431         // all get accepted.  Notice the accept orphans flag is also false here
 432         // to ensure it has no bearing on whether or not already existing
 433         // orphans in the pool are linked.
 434         acceptedTxns, err := harness.txPool.ProcessTransaction(chainedTxns[0],
 435                 false, false, 0)
 436         if err != nil {
 437                 t.Fatalf("ProcessTransaction: failed to accept valid "+
 438                         "orphan %v", err)
 439         }
 440         if len(acceptedTxns) != len(chainedTxns) {
 441                 t.Fatalf("ProcessTransaction: reported accepted transactions "+
 442                         "length does not match expected -- got %d, want %d",
 443                         len(acceptedTxns), len(chainedTxns))
 444         }
 445         for _, txD := range acceptedTxns {
 446                 // Ensure the transaction is no longer in the orphan pool, is
 447                 // now in the transaction pool, and is reported as available.
 448                 testPoolMembership(tc, txD.Tx, false, true)
 449         }
 450 }
 451
 452 // TestOrphanReject ensures that orphans are properly rejected when the allow
 453 // orphans flag is not set on ProcessTransaction.
 454 func TestOrphanReject(t *testing.T) {
 455         t.Parallel()
 456
 457         harness, outputs, err := newPoolHarness(&chaincfg.MainNetParams)
 458         if err != nil {
 459                 t.Fatalf("unable to create test pool: %v", err)
 460         }
 461         tc := &testContext{t, harness}
 462
 463         // Create a chain of transactions rooted with the first spendable output
 464         // provided by the harness.
 465         maxOrphans := uint32(harness.txPool.cfg.Policy.MaxOrphanTxs)
 466         chainedTxns, err := harness.CreateTxChain(outputs[0], maxOrphans+1)
 467         if err != nil {
 468                 t.Fatalf("unable to create transaction chain: %v", err)
 469         }
 470
 471         // Ensure orphans are rejected when the allow orphans flag is not set.
 472         for _, tx := range chainedTxns[1:] {
 473                 acceptedTxns, err := harness.txPool.ProcessTransaction(tx, false,
 474                         false, 0)
 475                 if err == nil {
 476                         t.Fatalf("ProcessTransaction: did not fail on orphan "+
 477                                 "%v when allow orphans flag is false", tx.Hash())
 478                 }
 479                 expectedErr := RuleError{}
 480                 if reflect.TypeOf(err) != reflect.TypeOf(expectedErr) {
 481                         t.Fatalf("ProcessTransaction: wrong error got: <%T> %v, "+
 482                                 "want: <%T>", err, err, expectedErr)
 483                 }
 484                 code, extracted := extractRejectCode(err)
 485                 if !extracted {
 486                         t.Fatalf("ProcessTransaction: failed to extract reject "+
 487                                 "code from error %q", err)
 488                 }
 489                 if code != wire.RejectDuplicate {
 490                         t.Fatalf("ProcessTransaction: unexpected reject code "+
 491                                 "-- got %v, want %v", code, wire.RejectDuplicate)
 492                 }
 493
 494                 // Ensure no transactions were reported as accepted.
 495                 if len(acceptedTxns) != 0 {
 496                         t.Fatal("ProcessTransaction: reported %d accepted "+
 497                                 "transactions from failed orphan attempt",
 498                                 len(acceptedTxns))
 499                 }
 500
 501                 // Ensure the transaction is not in the orphan pool, not in the
 502                 // transaction pool, and not reported as available
 503                 testPoolMembership(tc, tx, false, false)
 504         }
 505 }
 506
 507 // TestOrphanEviction ensures that exceeding the maximum number of orphans
 508 // evicts entries to make room for the new ones.
 509 func TestOrphanEviction(t *testing.T) {
 510         t.Parallel()
 511
 512         harness, outputs, err := newPoolHarness(&chaincfg.MainNetParams)
 513         if err != nil {
 514                 t.Fatalf("unable to create test pool: %v", err)
 515         }
 516         tc := &testContext{t, harness}
 517
 518         // Create a chain of transactions rooted with the first spendable output
 519         // provided by the harness that is long enough to be able to force
 520         // several orphan evictions.
 521         maxOrphans := uint32(harness.txPool.cfg.Policy.MaxOrphanTxs)
 522         chainedTxns, err := harness.CreateTxChain(outputs[0], maxOrphans+5)
 523         if err != nil {
 524                 t.Fatalf("unable to create transaction chain: %v", err)
 525         }
 526
 527         // Add enough orphans to exceed the max allowed while ensuring they are
 528         // all accepted.  This will cause an eviction.
 529         for _, tx := range chainedTxns[1:] {
 530                 acceptedTxns, err := harness.txPool.ProcessTransaction(tx, true,
 531                         false, 0)
 532                 if err != nil {
 533                         t.Fatalf("ProcessTransaction: failed to accept valid "+
 534                                 "orphan %v", err)
 535                 }
 536
 537                 // Ensure no transactions were reported as accepted.
 538                 if len(acceptedTxns) != 0 {
 539                         t.Fatalf("ProcessTransaction: reported %d accepted "+
 540                                 "transactions from what should be an orphan",
 541                                 len(acceptedTxns))
 542                 }
 543
 544                 // Ensure the transaction is in the orphan pool, is not in the
 545                 // transaction pool, and is reported as available.
 546                 testPoolMembership(tc, tx, true, false)
 547         }
 548
 549         // Figure out which transactions were evicted and make sure the number
 550         // evicted matches the expected number.
 551         var evictedTxns []*btcutil.Tx
 552         for _, tx := range chainedTxns[1:] {
 553                 if !harness.txPool.IsOrphanInPool(tx.Hash()) {
 554                         evictedTxns = append(evictedTxns, tx)
 555                 }
 556         }
 557         expectedEvictions := len(chainedTxns) - 1 - int(maxOrphans)
 558         if len(evictedTxns) != expectedEvictions {
 559                 t.Fatalf("unexpected number of evictions -- got %d, want %d",
 560                         len(evictedTxns), expectedEvictions)
 561         }
 562
 563         // Ensure none of the evicted transactions ended up in the transaction
 564         // pool.
 565         for _, tx := range evictedTxns {
 566                 testPoolMembership(tc, tx, false, false)
 567         }
 568 }
 569
 570 // TestBasicOrphanRemoval ensure that orphan removal works as expected when an
 571 // orphan that doesn't exist is removed  both when there is another orphan that
 572 // redeems it and when there is not.
 573 func TestBasicOrphanRemoval(t *testing.T) {
 574         t.Parallel()
 575
 576         const maxOrphans = 4
 577         harness, spendableOuts, err := newPoolHarness(&chaincfg.MainNetParams)
 578         if err != nil {
 579                 t.Fatalf("unable to create test pool: %v", err)
 580         }
 581         harness.txPool.cfg.Policy.MaxOrphanTxs = maxOrphans
 582         tc := &testContext{t, harness}
 583
 584         // Create a chain of transactions rooted with the first spendable output
 585         // provided by the harness.
 586         chainedTxns, err := harness.CreateTxChain(spendableOuts[0], maxOrphans+1)
 587         if err != nil {
 588                 t.Fatalf("unable to create transaction chain: %v", err)
 589         }
 590
 591         // Ensure the orphans are accepted (only up to the maximum allowed so
 592         // none are evicted).
 593         for _, tx := range chainedTxns[1 : maxOrphans+1] {
 594                 acceptedTxns, err := harness.txPool.ProcessTransaction(tx, true,
 595                         false, 0)
 596                 if err != nil {
 597                         t.Fatalf("ProcessTransaction: failed to accept valid "+
 598                                 "orphan %v", err)
 599                 }
 600
 601                 // Ensure no transactions were reported as accepted.
 602                 if len(acceptedTxns) != 0 {
 603                         t.Fatalf("ProcessTransaction: reported %d accepted "+
 604                                 "transactions from what should be an orphan",
 605                                 len(acceptedTxns))
 606                 }
 607
 608                 // Ensure the transaction is in the orphan pool, not in the
 609                 // transaction pool, and reported as available.
 610                 testPoolMembership(tc, tx, true, false)
 611         }
 612
 613         // Attempt to remove an orphan that has no redeemers and is not present,
 614         // and ensure the state of all other orphans are unaffected.
 615         nonChainedOrphanTx, err := harness.CreateSignedTx([]spendableOutput{{
 616                 amount:   btcutil.Amount(5000000000),
 617                 outPoint: wire.OutPoint{Hash: chainhash.Hash{}, Index: 0},
 618         }}, 1)
 619         if err != nil {
 620                 t.Fatalf("unable to create signed tx: %v", err)
 621         }
 622
 623         harness.txPool.RemoveOrphan(nonChainedOrphanTx)
 624         testPoolMembership(tc, nonChainedOrphanTx, false, false)
 625         for _, tx := range chainedTxns[1 : maxOrphans+1] {
 626                 testPoolMembership(tc, tx, true, false)
 627         }
 628
 629         // Attempt to remove an orphan that has a existing redeemer but itself
 630         // is not present and ensure the state of all other orphans (including
 631         // the one that redeems it) are unaffected.
 632         harness.txPool.RemoveOrphan(chainedTxns[0])
 633         testPoolMembership(tc, chainedTxns[0], false, false)
 634         for _, tx := range chainedTxns[1 : maxOrphans+1] {
 635                 testPoolMembership(tc, tx, true, false)
 636         }
 637
 638         // Remove each orphan one-by-one and ensure they are removed as
 639         // expected.
 640         for _, tx := range chainedTxns[1 : maxOrphans+1] {
 641                 harness.txPool.RemoveOrphan(tx)
 642                 testPoolMembership(tc, tx, false, false)
 643         }
 644 }
 645
 646 // TestOrphanChainRemoval ensure that orphan chains (orphans that spend outputs
 647 // from other orphans) are removed as expected.
 648 func TestOrphanChainRemoval(t *testing.T) {
 649         t.Parallel()
 650
 651         const maxOrphans = 10
 652         harness, spendableOuts, err := newPoolHarness(&chaincfg.MainNetParams)
 653         if err != nil {
 654                 t.Fatalf("unable to create test pool: %v", err)
 655         }
 656         harness.txPool.cfg.Policy.MaxOrphanTxs = maxOrphans
 657         tc := &testContext{t, harness}
 658
 659         // Create a chain of transactions rooted with the first spendable output
 660         // provided by the harness.
 661         chainedTxns, err := harness.CreateTxChain(spendableOuts[0], maxOrphans+1)
 662         if err != nil {
 663                 t.Fatalf("unable to create transaction chain: %v", err)
 664         }
 665
 666         // Ensure the orphans are accepted (only up to the maximum allowed so
 667         // none are evicted).
 668         for _, tx := range chainedTxns[1 : maxOrphans+1] {
 669                 acceptedTxns, err := harness.txPool.ProcessTransaction(tx, true,
 670                         false, 0)
 671                 if err != nil {
 672                         t.Fatalf("ProcessTransaction: failed to accept valid "+
 673                                 "orphan %v", err)
 674                 }
 675
 676                 // Ensure no transactions were reported as accepted.
 677                 if len(acceptedTxns) != 0 {
 678                         t.Fatalf("ProcessTransaction: reported %d accepted "+
 679                                 "transactions from what should be an orphan",
 680                                 len(acceptedTxns))
 681                 }
 682
 683                 // Ensure the transaction is in the orphan pool, not in the
 684                 // transaction pool, and reported as available.
 685                 testPoolMembership(tc, tx, true, false)
 686         }
 687
 688         // Remove the first orphan that starts the orphan chain without the
 689         // remove redeemer flag set and ensure that only the first orphan was
 690         // removed.
 691         harness.txPool.mtx.Lock()
 692         harness.txPool.removeOrphan(chainedTxns[1], false)
 693         harness.txPool.mtx.Unlock()
 694         testPoolMembership(tc, chainedTxns[1], false, false)
 695         for _, tx := range chainedTxns[2 : maxOrphans+1] {
 696                 testPoolMembership(tc, tx, true, false)
 697         }
 698
 699         // Remove the first remaining orphan that starts the orphan chain with
 700         // the remove redeemer flag set and ensure they are all removed.
 701         harness.txPool.mtx.Lock()
 702         harness.txPool.removeOrphan(chainedTxns[2], true)
 703         harness.txPool.mtx.Unlock()
 704         for _, tx := range chainedTxns[2 : maxOrphans+1] {
 705                 testPoolMembership(tc, tx, false, false)
 706         }
 707 }
 708
 709 // TestMultiInputOrphanDoubleSpend ensures that orphans that spend from an
 710 // output that is spend by another transaction entering the pool are removed.
 711 func TestMultiInputOrphanDoubleSpend(t *testing.T) {
 712         t.Parallel()
 713
 714         const maxOrphans = 4
 715         harness, outputs, err := newPoolHarness(&chaincfg.MainNetParams)
 716         if err != nil {
 717                 t.Fatalf("unable to create test pool: %v", err)
 718         }
 719         harness.txPool.cfg.Policy.MaxOrphanTxs = maxOrphans
 720         tc := &testContext{t, harness}
 721
 722         // Create a chain of transactions rooted with the first spendable output
 723         // provided by the harness.
 724         chainedTxns, err := harness.CreateTxChain(outputs[0], maxOrphans+1)
 725         if err != nil {
 726                 t.Fatalf("unable to create transaction chain: %v", err)
 727         }
 728
 729         // Start by adding the orphan transactions from the generated chain
 730         // except the final one.
 731         for _, tx := range chainedTxns[1:maxOrphans] {
 732                 acceptedTxns, err := harness.txPool.ProcessTransaction(tx, true,
 733                         false, 0)
 734                 if err != nil {
 735                         t.Fatalf("ProcessTransaction: failed to accept valid "+
 736                                 "orphan %v", err)
 737                 }
 738                 if len(acceptedTxns) != 0 {
 739                         t.Fatalf("ProcessTransaction: reported %d accepted transactions "+
 740                                 "from what should be an orphan", len(acceptedTxns))
 741                 }
 742                 testPoolMembership(tc, tx, true, false)
 743         }
 744
 745         // Ensure a transaction that contains a double spend of the same output
 746         // as the second orphan that was just added as well as a valid spend
 747         // from that last orphan in the chain generated above (and is not in the
 748         // orphan pool) is accepted to the orphan pool.  This must be allowed
 749         // since it would otherwise be possible for a malicious actor to disrupt
 750         // tx chains.
 751         doubleSpendTx, err := harness.CreateSignedTx([]spendableOutput{
 752                 txOutToSpendableOut(chainedTxns[1], 0),
 753                 txOutToSpendableOut(chainedTxns[maxOrphans], 0),
 754         }, 1)
 755         if err != nil {
 756                 t.Fatalf("unable to create signed tx: %v", err)
 757         }
 758         acceptedTxns, err := harness.txPool.ProcessTransaction(doubleSpendTx,
 759                 true, false, 0)
 760         if err != nil {
 761                 t.Fatalf("ProcessTransaction: failed to accept valid orphan %v",
 762                         err)
 763         }
 764         if len(acceptedTxns) != 0 {
 765                 t.Fatalf("ProcessTransaction: reported %d accepted transactions "+
 766                         "from what should be an orphan", len(acceptedTxns))
 767         }
 768         testPoolMembership(tc, doubleSpendTx, true, false)
 769
 770         // Add the transaction which completes the orphan chain and ensure the
 771         // chain gets accepted.  Notice the accept orphans flag is also false
 772         // here to ensure it has no bearing on whether or not already existing
 773         // orphans in the pool are linked.
 774         //
 775         // This will cause the shared output to become a concrete spend which
 776         // will in turn must cause the double spending orphan to be removed.
 777         acceptedTxns, err = harness.txPool.ProcessTransaction(chainedTxns[0],
 778                 false, false, 0)
 779         if err != nil {
 780                 t.Fatalf("ProcessTransaction: failed to accept valid tx %v", err)
 781         }
 782         if len(acceptedTxns) != maxOrphans {
 783                 t.Fatalf("ProcessTransaction: reported accepted transactions "+
 784                         "length does not match expected -- got %d, want %d",
 785                         len(acceptedTxns), maxOrphans)
 786         }
 787         for _, txD := range acceptedTxns {
 788                 // Ensure the transaction is no longer in the orphan pool, is
 789                 // in the transaction pool, and is reported as available.
 790                 testPoolMembership(tc, txD.Tx, false, true)
 791         }
 792
 793         // Ensure the double spending orphan is no longer in the orphan pool and
 794         // was not moved to the transaction pool.
 795         testPoolMembership(tc, doubleSpendTx, false, false)
 796 }