mempool.go

package mempool

import (
	"container/list"
	"errors"
	"fmt"
	"github.com/p9c/duod/pkg/amt"
	"github.com/p9c/duod/pkg/chaincfg"
	"github.com/p9c/duod/pkg/constant"
	"github.com/p9c/log"
	"math"
	"sync"
	"sync/atomic"
	"time"
	
	"github.com/p9c/duod/pkg/blockchain"
	"github.com/p9c/duod/pkg/chainhash"
	"github.com/p9c/duod/pkg/hardfork"
	"github.com/p9c/duod/pkg/indexers"
	"github.com/p9c/duod/pkg/mining"
	"github.com/p9c/duod/pkg/txscript"
	"github.com/p9c/duod/pkg/wire"
	
	"github.com/p9c/duod/pkg/btcjson"
	"github.com/p9c/duod/pkg/util"
)

// Config is a descriptor containing the memory pool configuration.
type Config struct {
	// Policy defines the various mempool configuration options related to policy.
	Policy Policy
	// ChainParams identifies which chain parameters the txpool is associated with.
	ChainParams *chaincfg.Params
	// FetchUtxoView defines the function to use to fetch unspent transaction output information.
	FetchUtxoView func(*util.Tx) (*blockchain.UtxoViewpoint, error)
	// BestHeight defines the function to use to access the block height of the current best chain.
	BestHeight func() int32
	// MedianTimePast defines the function to use in order to access the median time past calculated from the
	// point-of-view of the current chain tip within the best chain.
	MedianTimePast func() time.Time
	// // CalcSequenceLock defines the function to use in order to generate the current sequence lock for the given
	// // transaction using the passed utxo view.
	// CalcSequenceLock func(*util.Tx, *blockchain.UtxoViewpoint) (*blockchain.SequenceLock, error)
	// IsDeploymentActive returns true if the target deploymentID is active, and false otherwise. The mempool uses
	// this function to gauge if transactions using new to be soft-forked rules should be allowed into the mempool
	// or not.
	IsDeploymentActive func(deploymentID uint32) (bool, error)
	// SigCache defines a signature cache to use.
	SigCache *txscript.SigCache
	// HashCache defines the transaction hash mid-state cache to use.
	HashCache *txscript.HashCache
	// AddrIndex defines the optional address index instance to use for indexing the unconfirmed transactions in the
	// memory pool. This can be nil if the address index is not enabled.
	AddrIndex *indexers.AddrIndex
	// FeeEstimatator provides a feeEstimator. If it is not nil, the mempool records all new transactions it
	// observes into the feeEstimator.
	FeeEstimator *FeeEstimator
	// UpdateHook is a function that is called when transactions are added or
	// removed from the mempool
	UpdateHook func()
}

// Policy houses the policy (configuration parameters) that is used to control the mempool.
type Policy struct {
	// MaxTxVersion is the transaction version that the mempool should accept. All transactions above this version are
	// rejected as non-standard.
	MaxTxVersion int32
	// DisableRelayPriority defines whether to relay free or low-fee transactions that do not have enough priority to be
	// relayed.
	DisableRelayPriority bool
	// AcceptNonStd defines whether to accept non-standard transactions. If true, non-standard transactions will be
	// accepted into the mempool. Otherwise, all non-standard transactions will be rejected.
	AcceptNonStd bool
	// FreeTxRelayLimit defines the given amount in thousands of bytes per minute that transactions with no fee are rate
	// limited to.
	FreeTxRelayLimit float64
	// MaxOrphanTxs is the maximum number of orphan transactions that can be queued.
	MaxOrphanTxs int
	// MaxOrphanTxSize is the maximum size allowed for orphan transactions. This helps prevent memory exhaustion attacks
	// from sending a lot of of big orphans.
	MaxOrphanTxSize int
	// MaxSigOpCostPerTx is the cumulative maximum cost of all the signature operations in a single transaction we will
	// relay or mine. It is a fraction of the max signature operations for a block.
	MaxSigOpCostPerTx int
	// MinRelayTxFee defines the minimum transaction fee in DUO/kB to be considered a non-zero fee.
	MinRelayTxFee amt.Amount
}

// Tag represents an identifier to use for tagging orphan transactions. The caller may choose any scheme it desires
// however it is common to use peer IDs so that orphans can be identified by which peer first relayed them.
type Tag uint64

// TxDesc is a descriptor containing a transaction in the mempool along with additional metadata.
type TxDesc struct {
	mining.TxDesc
	// StartingPriority is the priority of the transaction when it was added to the pool.
	StartingPriority float64
}

// TxPool is used as a source of transactions that need to be mined into blocks and relayed to other peers. It is safe
// for concurrent access from multiple peers.
type TxPool struct {
	// The following variables must only be used atomically.
	lastUpdated   int64 // last time pool was updated
	mtx           sync.RWMutex
	cfg           Config
	pool          map[chainhash.Hash]*TxDesc
	orphans       map[chainhash.Hash]*orphanTx
	orphansByPrev map[wire.OutPoint]map[chainhash.Hash]*util.Tx
	outpoints     map[wire.OutPoint]*util.Tx
	pennyTotal    float64 // exponentially decaying total for penny spends.
	lastPennyUnix int64   // unix time of last ``penny spend''
	// nextExpireScan is the time after which the orphan pool will be scanned in order to evict orphans. This is NOT
	// a hard deadline as the scan will only run when an orphan is added to the pool as opposed to on an
	// unconditional timer.
	nextExpireScan time.Time
	updateHook     func()
}

// orphanTx is normal transaction that references an ancestor transaction that is not yet available. It also contains
// additional information related to it such as an expiration time to help prevent caching the orphan forever.
type orphanTx struct {
	tx         *util.Tx
	tag        Tag
	expiration time.Time
}

const (
	// orphanTTL is the maximum amount of time an orphan is allowed to stay in the orphan pool before it expires and is
	// evicted during the next scan.
	orphanTTL = time.Minute * 15
	// orphanExpireScanInterval is the minimum amount of time in between
	// scans of the orphan pool to evict expired transactions.
	orphanExpireScanInterval = time.Minute * 5
)

var // Ensure the TxPool type implements the mining.TxSource interface.
	_ mining.TxSource = (*TxPool)(nil)

// CheckSpend checks whether the passed outpoint is already spent by a transaction in the mempool. If that's the case
// the spending transaction will be returned, if not nil will be returned.
func (mp *TxPool) CheckSpend(op wire.OutPoint) *util.Tx {
	mp.mtx.RLock()
	txR := mp.outpoints[op]
	mp.mtx.RUnlock()
	return txR
}

// Count returns the number of transactions in the main pool. It does not include the orphan pool. This function is safe
// for concurrent access.
func (mp *TxPool) Count() int {
	mp.mtx.RLock()
	count := len(mp.pool)
	mp.mtx.RUnlock()
	return count
}

// FetchTransaction returns the requested transaction from the transaction pool. This only fetches from the main
// transaction pool and does not include orphans. This function is safe for concurrent access.
func (mp *TxPool) FetchTransaction(txHash *chainhash.Hash) (*util.Tx, error) {
	// Protect concurrent access.
	mp.mtx.RLock()
	txDesc, exists := mp.pool[*txHash]
	mp.mtx.RUnlock()
	if exists {
		return txDesc.Tx, nil
	}
	return nil, fmt.Errorf("transaction is not in the pool")
}

// HaveTransaction returns whether or not the passed transaction already exists in the main pool or in the orphan pool.
// This function is safe for concurrent access.
func (mp *TxPool) HaveTransaction(hash *chainhash.Hash) bool {
	// Protect concurrent access.
	mp.mtx.RLock()
	haveTx := mp.haveTransaction(hash)
	mp.mtx.RUnlock()
	return haveTx
}

// IsOrphanInPool returns whether or not the passed transaction already exists in the orphan pool. This function is safe
// for concurrent access.
func (mp *TxPool) IsOrphanInPool(hash *chainhash.Hash) bool {
	// Protect concurrent access.
	mp.mtx.RLock()
	inPool := mp.isOrphanInPool(hash)
	mp.mtx.RUnlock()
	return inPool
}

// IsTransactionInPool returns whether or not the passed transaction already exists in the main pool. This function is
// safe for concurrent access.
func (mp *TxPool) IsTransactionInPool(hash *chainhash.Hash) bool {
	// Protect concurrent access.
	mp.mtx.RLock()
	inPool := mp.isTransactionInPool(hash)
	mp.mtx.RUnlock()
	return inPool
}

// LastUpdated returns the last time a transaction was added to or removed from the main pool. It does not include the
// orphan pool. This function is safe for concurrent access.
func (mp *TxPool) LastUpdated() time.Time {
	return time.Unix(atomic.LoadInt64(&mp.lastUpdated), 0)
}

// MaybeAcceptTransaction is the main workhorse for handling insertion of new free-standing transactions into a memory
// pool. It includes functionality such as rejecting duplicate transactions, ensuring transactions follow all rules,
// detecting orphan transactions, and insertion into the memory pool. If the transaction is an orphan ( missing parent
// transactions) the transaction is NOT added to the orphan pool but each unknown referenced parent is returned. Use
// ProcessTransaction instead if new orphans should be added to the orphan pool. This function is safe for concurrent
// access.
func (mp *TxPool) MaybeAcceptTransaction(
	b *blockchain.BlockChain,
	tx *util.Tx, isNew, rateLimit bool,
) (hashes []*chainhash.Hash, txD *TxDesc, e error) {
	// Protect concurrent access.
	mp.mtx.Lock()
	hashes, txD, e = mp.maybeAcceptTransaction(b, tx, isNew, rateLimit, true)
	mp.mtx.Unlock()
	return hashes, txD, e
}

// MiningDescs returns a slice of mining descriptors for all the transactions in the pool. This is part of the mining.
// TxSource interface implementation and is safe for concurrent access as required by the interface contract.
func (mp *TxPool) MiningDescs() []*mining.TxDesc {
	mp.mtx.RLock()
	descs := make([]*mining.TxDesc, len(mp.pool))
	i := 0
	for _, desc := range mp.pool {
		descs[i] = &desc.TxDesc
		i++
	}
	mp.mtx.RUnlock()
	return descs
}

// ProcessOrphans determines if there are any orphans which depend on the passed transaction hash (it is possible that
// they are no longer orphans) and potentially accepts them to the memory pool. It repeats the process for the newly
// accepted transactions (to detect further orphans which may no longer be orphans) until there are no more. It returns
// a slice of transactions added to the mempool. A nil slice means no transactions were moved from the orphan pool to
// the mempool. This function is safe for concurrent access.
func (mp *TxPool) ProcessOrphans(b *blockchain.BlockChain, acceptedTx *util.Tx) []*TxDesc {
	mp.mtx.Lock()
	acceptedTxns := mp.processOrphans(b, acceptedTx)
	mp.mtx.Unlock()
	return acceptedTxns
}

// ProcessTransaction is the main workhorse for handling insertion of new free-standing transactions into the memory
// pool. It includes functionality such as rejecting duplicate transactions, ensuring transactions follow all rules,
// orphan transaction handling, and insertion into the memory pool. It returns a slice of transactions added to the
// mempool. When the error is nil the list will include the passed transaction itself along with any additional orphan
// transactions that were added as a result of the passed one being accepted. This function is safe for concurrent
// access.
func (mp *TxPool) ProcessTransaction(
	b *blockchain.BlockChain, tx *util.Tx,
	allowOrphan, rateLimit bool, tag Tag,
) ([]*TxDesc, error) {
	D.Ln("processing transaction", tx.Hash())
	// Protect concurrent access.
	mp.mtx.Lock()
	defer mp.mtx.Unlock()
	// Potentially accept the transaction to the memory pool.
	missingParents, txD, e := mp.maybeAcceptTransaction(
		b, tx, true,
		rateLimit, true,
	)
	if e != nil {
		return nil, e
	}
	if len(missingParents) == 0 {
		// Accept any orphan transactions that depend on this transaction ( they may no longer be orphans if all inputs
		// are now available) and repeat for those accepted transactions until there are no more.
		newTxs := mp.processOrphans(b, tx)
		acceptedTxs := make([]*TxDesc, len(newTxs)+1)
		// Add the parent transaction first so remote nodes do not add orphans.
		acceptedTxs[0] = txD
		copy(acceptedTxs[1:], newTxs)
		return acceptedTxs, nil
	}
	// The transaction is an orphan (has inputs missing). Reject it if the flag to allow orphans is not set.
	if !allowOrphan {
		// Only use the first missing parent transaction in the error message. NOTE: RejectDuplicate is really not an
		// accurate reject code here, but it matches the reference implementation and there isn't a better choice due to
		// the limited number of reject codes. Missing inputs is assumed to mean they are already spent which is not
		// really always the case.
		str := fmt.Sprintf(
			"orphan transaction %v references outputs of"+
				" unknown or fully-spent transaction %v", tx.Hash(),
			missingParents[0],
		)
		return nil, txRuleError(wire.RejectDuplicate, str)
	}
	// Potentially add the orphan transaction to the orphan pool.
	e = mp.maybeAddOrphan(tx, tag)
	return nil, e
}

// RawMempoolVerbose returns all of the entries in the mempool as a fully populated json result. This function is safe
// for concurrent access.
func (mp *TxPool) RawMempoolVerbose() map[string]*btcjson.GetRawMempoolVerboseResult {
	mp.mtx.RLock()
	defer mp.mtx.RUnlock()
	result := make(map[string]*btcjson.GetRawMempoolVerboseResult, len(mp.pool))
	bestHeight := mp.cfg.BestHeight()
	for _, desc := range mp.pool {
		// Calculate the current priority based on the inputs to the transaction. Use zero if one or more of the input
		// transactions can't be found for some reason.
		tx := desc.Tx
		var currentPriority float64
		utxos, e := mp.fetchInputUtxos(tx)
		if e == nil {
			currentPriority = mining.CalcPriority(
				tx.MsgTx(), utxos,
				bestHeight+1,
			)
		}
		mpd := &btcjson.GetRawMempoolVerboseResult{
			Size:             int32(tx.MsgTx().SerializeSize()),
			VSize:            int32(GetTxVirtualSize(tx)),
			Fee:              amt.Amount(desc.Fee).ToDUO(),
			Time:             desc.Added.Unix(),
			Height:           int64(desc.Height),
			StartingPriority: desc.StartingPriority,
			CurrentPriority:  currentPriority,
			Depends:          make([]string, 0),
		}
		for _, txIn := range tx.MsgTx().TxIn {
			hash := &txIn.PreviousOutPoint.Hash
			if mp.haveTransaction(hash) {
				mpd.Depends = append(
					mpd.Depends,
					hash.String(),
				)
			}
		}
		result[tx.Hash().String()] = mpd
	}
	return result
}

// RemoveDoubleSpends removes all transactions which spend outputs spent by the passed transaction from the memory pool.
// Removing those transactions then leads to removing all transactions which rely on them, recursively. This is
// necessary when a block is connected to the main chain because the block may contain transactions which were
// previously unknown to the memory pool. This function is safe for concurrent access.
func (mp *TxPool) RemoveDoubleSpends(tx *util.Tx) {
	// Protect concurrent access.
	mp.mtx.Lock()
	for _, txIn := range tx.MsgTx().TxIn {
		if txRedeemer, ok := mp.outpoints[txIn.PreviousOutPoint]; ok {
			if !txRedeemer.Hash().IsEqual(tx.Hash()) {
				mp.removeTransaction(txRedeemer, true)
			}
		}
	}
	mp.mtx.Unlock()
}

// RemoveOrphan removes the passed orphan transaction from the orphan pool and previous orphan index. This function is
// safe for concurrent access.
func (mp *TxPool) RemoveOrphan(tx *util.Tx) {
	mp.mtx.Lock()
	mp.removeOrphan(tx, false)
	mp.mtx.Unlock()
}

// RemoveOrphansByTag removes all orphan transactions tagged with the provided identifier. This function is safe for
// concurrent access.
func (mp *TxPool) RemoveOrphansByTag(tag Tag) uint64 {
	var numEvicted uint64
	mp.mtx.Lock()
	for _, otx := range mp.orphans {
		if otx.tag == tag {
			mp.removeOrphan(otx.tx, true)
			numEvicted++
		}
	}
	mp.mtx.Unlock()
	return numEvicted
}

// RemoveTransaction removes the passed transaction from the mempool. When the removeRedeemers flag is set any
// transactions that redeem outputs from the removed transaction will also be removed recursively from the mempool, as
// they would otherwise become orphans. This function is safe for concurrent access.
func (mp *TxPool) RemoveTransaction(tx *util.Tx, removeRedeemers bool) {
	// Protect concurrent access.
	mp.mtx.Lock()
	mp.removeTransaction(tx, removeRedeemers)
	mp.mtx.Unlock()
}

// TxDescs returns a slice of descriptors for all the transactions in the pool. The descriptors are to be treated as
// read only. This function is safe for concurrent access.
func (mp *TxPool) TxDescs() []*TxDesc {
	mp.mtx.RLock()
	descs := make([]*TxDesc, len(mp.pool))
	i := 0
	for _, desc := range mp.pool {
		descs[i] = desc
		i++
	}
	mp.mtx.RUnlock()
	return descs
}

// TxHashes returns a slice of hashes for all of the transactions in the memory pool. This function is safe for
// concurrent access.
func (mp *TxPool) TxHashes() []*chainhash.Hash {
	mp.mtx.RLock()
	hashes := make([]*chainhash.Hash, len(mp.pool))
	i := 0
	for hash := range mp.pool {
		hashCopy := hash
		hashes[i] = &hashCopy
		i++
	}
	mp.mtx.RUnlock()
	return hashes
}

// addOrphan adds an orphan transaction to the orphan pool. This function MUST be called with the mempool lock held (for
// writes).
func (mp *TxPool) addOrphan(tx *util.Tx, tag Tag) {
	// Nothing to do if no orphans are allowed.
	if mp.cfg.Policy.MaxOrphanTxs <= 0 {
		return
	}
	// Limit the number orphan transactions to prevent memory exhaustion. This will periodically remove any expired
	// orphans and evict a random orphan if space is still needed.
	e := mp.limitNumOrphans()
	if e != nil {
		W.Ln("failed to set orphan limit", e)
	}
	mp.orphans[*tx.Hash()] = &orphanTx{
		tx:         tx,
		tag:        tag,
		expiration: time.Now().Add(orphanTTL),
	}
	for _, txIn := range tx.MsgTx().TxIn {
		if _, exists := mp.orphansByPrev[txIn.PreviousOutPoint]; !exists {
			mp.orphansByPrev[txIn.PreviousOutPoint] =
				make(map[chainhash.Hash]*util.Tx)
		}
		mp.orphansByPrev[txIn.PreviousOutPoint][*tx.Hash()] = tx
	}
	D.Ln("stored orphan transaction", tx.Hash(), "(total:", len(mp.orphans), ")")
}

// addTransaction adds the passed transaction to the memory pool. It should not be called directly as it doesn't perform
// any validation. This is a helper for maybeAcceptTransaction. This function MUST be called with the mempool lock held
// (for writes).
func (mp *TxPool) addTransaction(utxoView *blockchain.UtxoViewpoint, tx *util.Tx, height int32, fee int64) *TxDesc {
	// Add the transaction to the pool and mark the referenced outpoints as spent by the pool.
	txD := &TxDesc{
		TxDesc: mining.TxDesc{
			Tx:       tx,
			Added:    time.Now(),
			Height:   height,
			Fee:      fee,
			FeePerKB: fee * 1000 / GetTxVirtualSize(tx),
		},
		StartingPriority: mining.CalcPriority(tx.MsgTx(), utxoView, height),
	}
	mp.pool[*tx.Hash()] = txD
	for _, txIn := range tx.MsgTx().TxIn {
		mp.outpoints[txIn.PreviousOutPoint] = tx
	}
	atomic.StoreInt64(&mp.lastUpdated, time.Now().Unix())
	if mp.updateHook != nil {
		mp.updateHook()
	}
	// Add unconfirmed address index entries associated with the transaction if enabled.
	if mp.cfg.AddrIndex != nil {
		mp.cfg.AddrIndex.AddUnconfirmedTx(tx, utxoView)
	}
	// Record this tx for fee estimation if enabled.
	if mp.cfg.FeeEstimator != nil {
		mp.cfg.FeeEstimator.ObserveTransaction(txD)
	}
	return txD
}

// checkPoolDoubleSpend checks whether or not the passed transaction is attempting to spend coins already spent by other
// transactions in the pool. Note it does not check for double spends against transactions already in the main chain.
// This function MUST be called with the mempool lock held (for reads).
func (mp *TxPool) checkPoolDoubleSpend(tx *util.Tx) (e error) {
	for _, txIn := range tx.MsgTx().TxIn {
		if txR, exists := mp.outpoints[txIn.PreviousOutPoint]; exists {
			str := fmt.Sprintf(
				"output %v already spent by "+
					"transaction %v in the memory pool",
				txIn.PreviousOutPoint, txR.Hash(),
			)
			return txRuleError(wire.RejectDuplicate, str)
		}
	}
	return nil
}

// fetchInputUtxos loads utxo details about the input transactions referenced by the passed transaction. First it loads
// the details form the viewpoint of the main chain, then it adjusts them based upon the contents of the transaction
// pool. This function MUST be called with the mempool lock held (for reads).
func (mp *TxPool) fetchInputUtxos(tx *util.Tx) (*blockchain.UtxoViewpoint, error) {
	utxoView, e := mp.cfg.FetchUtxoView(tx)
	if e != nil {
		return nil, e
	}
	// Attempt to populate any missing inputs from the transaction pool.
	for _, txIn := range tx.MsgTx().TxIn {
		prevOut := &txIn.PreviousOutPoint
		entry := utxoView.LookupEntry(*prevOut)
		if entry != nil && !entry.IsSpent() {
			continue
		}
		if poolTxDesc, exists := mp.pool[prevOut.Hash]; exists {
			// AddTxOut ignores out of range index values,
			// so it is safe to call without bounds checking here.
			utxoView.AddTxOut(
				poolTxDesc.Tx, prevOut.Index,
				mining.UnminedHeight,
			)
		}
	}
	return utxoView, nil
}

// haveTransaction returns whether or not the passed transaction already exists in the main pool or in the orphan pool.
// This function MUST be called with the mempool lock held (for reads).
func (mp *TxPool) haveTransaction(
	hash *chainhash.Hash,
) bool {
	return mp.isTransactionInPool(hash) || mp.isOrphanInPool(hash)
}

// isOrphanInPool returns whether or not the passed transaction already exists in the orphan pool. This function MUST be
// called with the mempool lock held (for reads).
func (mp *TxPool) isOrphanInPool(hash *chainhash.Hash) bool {
	if _, exists := mp.orphans[*hash]; exists {
		return true
	}
	return false
}

// isTransactionInPool returns whether or not the passed transaction already exists in the main pool. This function MUST
// be called with the mempool lock held (for reads).
func (mp *TxPool) isTransactionInPool(hash *chainhash.Hash) bool {
	if _, exists := mp.pool[*hash]; exists {
		return true
	}
	return false
}

// limitNumOrphans limits the number of orphan transactions by evicting a random orphan if adding a new one would cause
// it to overflow the max allowed. This function MUST be called with the mempool lock held (for writes).
func (mp *TxPool) limitNumOrphans() (e error) {
	// Scan through the orphan pool and remove any expired orphans when it's time. This is done for efficiency so the
	// scan only happens periodically instead of on every orphan added to the pool.
	if now := time.Now(); now.After(mp.nextExpireScan) {
		origNumOrphans := len(mp.orphans)
		for _, otx := range mp.orphans {
			if now.After(otx.expiration) {
				// Remove redeemers too because the missing parents are very unlikely to ever materialize since the
				// orphan has already been around more than long enough for them to be delivered.
				mp.removeOrphan(otx.tx, true)
			}
		}
		// Set next expiration scan to occur after the scan interval.
		mp.nextExpireScan = now.Add(orphanExpireScanInterval)
		numOrphans := len(mp.orphans)
		if numExpired := origNumOrphans - numOrphans; numExpired > 0 {
			D.F(
				"Expired %d %s (remaining: %d)",
				numExpired, log.PickNoun(numExpired, "orphan", "orphans"),
				numOrphans,
			)
		}
	}
	// Nothing to do if adding another orphan will not cause the pool to exceed the limit.
	if len(mp.orphans)+1 <= mp.cfg.Policy.MaxOrphanTxs {
		return nil
	}
	// Remove a random entry from the map. For most compilers, Go's range statement iterates starting at a random item
	// although that is not 100% guaranteed by the spec. The iteration order is not important here because an adversary
	// would have to be able to pull off preimage attacks on the hashing function in order to target eviction of
	// specific entries anyways.
	for _, otx := range mp.orphans {
		// Don't remove redeemers in the case of a random eviction since it is quite possible it might be needed again
		// shortly.
		mp.removeOrphan(otx.tx, false)
		break
	}
	return nil
}

// maybeAcceptTransaction is the internal function which implements the public MaybeAcceptTransaction. See the comment
// for MaybeAcceptTransaction for more details. This function MUST be called with the mempool lock held (for writes).
func (mp *TxPool) maybeAcceptTransaction(
	b *blockchain.BlockChain, tx *util.Tx, isNew, rateLimit, rejectDupOrphans bool,
) ([]*chainhash.Hash, *TxDesc, error) {
	txHash := tx.Hash()
	// // If a transaction has witness data, and segwit isn't active yet, If segwit isn't active yet, then we won't accept
	// // it into the mempool as it can't be mined yet.
	// if tx.MsgTx().HasWitness() {
	// 	segwitActive, e := mp.cfg.IsDeploymentActive(chaincfg.DeploymentSegwit)
	// 	if e != nil  {
	// 		General	// 		return nil, nil, e
	// 	}
	// 	if !segwitActive {
	// 		str := fmt.Sprintf("transaction %v has witness data, but segwit isn't active yet", txHash)
	// 		return nil, nil, txRuleError(wire.RejectNonstandard, str)
	// 	}
	// }
	if blockchain.ContainsBlacklisted(b, tx, hardfork.Blacklist) {
		return nil, nil, errors.New("transaction contains blacklisted address")
	}
	// Don't accept the transaction if it already exists in the pool. This applies to orphan transactions as well when
	// the reject duplicate orphans flag is set. This check is intended to be a quick check to weed out duplicates.
	if mp.isTransactionInPool(txHash) || (rejectDupOrphans &&
		mp.isOrphanInPool(txHash)) {
		str := fmt.Sprintf("already have transaction %v", txHash)
		return nil, nil, txRuleError(wire.RejectDuplicate, str)
	}
	// Perform preliminary sanity checks on the transaction. This makes use of blockchain which contains the invariant
	// rules for what transactions are allowed into blocks.
	e := blockchain.CheckTransactionSanity(tx)
	if e != nil {
		if cErr, ok := e.(blockchain.RuleError); ok {
			return nil, nil, chainRuleError(cErr)
		}
		return nil, nil, e
	}
	// A standalone transaction must not be a coinbase transaction.
	if blockchain.IsCoinBase(tx) {
		str := fmt.Sprintf(
			"transaction %v is an individual coinbase",
			txHash,
		)
		return nil, nil, txRuleError(wire.RejectInvalid, str)
	}
	// Get the current height of the main chain. A standalone transaction will be mined into the next block at best, so
	// its height is at least one more than the current height.
	bestHeight := mp.cfg.BestHeight()
	nextBlockHeight := bestHeight + 1
	medianTimePast := mp.cfg.MedianTimePast()
	// Don't allow non-standard transactions if the network parameters forbid their acceptance.
	if !mp.cfg.Policy.AcceptNonStd {
		e = checkTransactionStandard(
			tx,
			nextBlockHeight,
			medianTimePast,
			mp.cfg.Policy.MinRelayTxFee,
			mp.cfg.Policy.MaxTxVersion,
		)
		if e != nil {
			// Attempt to extract a reject code from the error so it can be retained. When not possible, fall back to a
			// non standard error.
			rejectCode, found := extractRejectCode(e)
			if !found {
				rejectCode = wire.RejectNonstandard
			}
			str := fmt.Sprintf(
				"transaction %v is not standard: %v",
				txHash, e,
			)
			return nil, nil, txRuleError(rejectCode, str)
		}
	}
	// The transaction may not use any of the same outputs as other transactions already in the pool as that would
	// ultimately result in a double spend. This check is intended to be quick and therefore only detects double spends
	// within the transaction pool itself. The transaction could still be double spending coins from the main chain at
	// this point. There is a more in-depth check that happens later after fetching the referenced transaction inputs
	// from the main chain which examines the actual spend data and prevents double spends.
	e = mp.checkPoolDoubleSpend(tx)
	if e != nil {
		return nil, nil, e
	}
	// Fetch all of the unspent transaction outputs referenced by the inputs to this transaction. This function also
	// attempts to fetch the transaction itself to be used for detecting a duplicate transaction without needing to do a
	// separate lookup.
	utxoView, e := mp.fetchInputUtxos(tx)
	if e != nil {
		if cErr, ok := e.(blockchain.RuleError); ok {
			return nil, nil, chainRuleError(cErr)
		}
		return nil, nil, e
	}
	// Don't allow the transaction if it exists in the main chain and is not not already fully spent.
	prevOut := wire.OutPoint{Hash: *txHash}
	for txOutIdx := range tx.MsgTx().TxOut {
		prevOut.Index = uint32(txOutIdx)
		entry := utxoView.LookupEntry(prevOut)
		if entry != nil && !entry.IsSpent() {
			return nil, nil, txRuleError(
				wire.RejectDuplicate,
				"transaction already exists",
			)
		}
		utxoView.RemoveEntry(prevOut)
	}
	// Transaction is an orphan if any of the referenced transaction outputs don't exist or are already spent. Adding
	// orphans to the orphan pool is not handled by this function, and the caller should use maybeAddOrphan if this
	// behavior is desired.
	var missingParents []*chainhash.Hash
	for outpoint, entry := range utxoView.Entries() {
		if entry == nil || entry.IsSpent() {
			// Must make a copy of the hash here since the iterator is replaced and taking its address directly would
			// result in all of the entries pointing to the same memory location and thus all be the final hash.
			hashCopy := outpoint.Hash
			missingParents = append(missingParents, &hashCopy)
		}
	}
	if len(missingParents) > 0 {
		return missingParents, nil, nil
	}
	// // Don't allow the transaction into the mempool unless its sequence lock is active, meaning that it'll be allowed
	// // into the next block with respect to its defined relative lock times.
	// sequenceLock, e := mp.cfg.CalcSequenceLock(tx, utxoView)
	// if e != nil  {
	// 	General	// 	if cErr, ok := err.(blockchain.RuleError); ok {
	// 		return nil, nil, chainRuleError(cErr)
	// 	}
	// 	return nil, nil, e
	// }
	// if !blockchain.SequenceLockActive(
	// 	sequenceLock, nextBlockHeight,
	// 	medianTimePast,
	// ) {
	// 	return nil, nil, txRuleError(
	// 		wire.RejectNonstandard,
	// 		"transaction's sequence locks on inputs not met",
	// 	)
	// }
	// Perform several checks on the transaction inputs using the invariant rules in blockchain for what transactions
	// are allowed into blocks. Also returns the fees associated with the transaction which will be used later.
	txFee, e := blockchain.CheckTransactionInputs(
		tx, nextBlockHeight,
		utxoView, mp.cfg.ChainParams,
	)
	if e != nil {
		if cErr, ok := e.(blockchain.RuleError); ok {
			return nil, nil, chainRuleError(cErr)
		}
		return nil, nil, e
	}
	// Don't allow transactions with non-standard inputs if the network parameters forbid their acceptance.
	if !mp.cfg.Policy.AcceptNonStd {
		e = checkInputsStandard(tx, utxoView)
		if e != nil {
			// Attempt to extract a reject code from the error so it can be retained. When not possible, fall back to a
			// non standard error.
			rejectCode, found := extractRejectCode(e)
			if !found {
				rejectCode = wire.RejectNonstandard
			}
			str := fmt.Sprintf(
				"transaction %v has a non-standard "+
					"input: %v", txHash, e,
			)
			return nil, nil, txRuleError(rejectCode, str)
		}
	}
	// NOTE: if you modify this code to accept non-standard transactions, you should add code here to check that the
	// transaction does a reasonable number of ECDSA signature verifications. Don't allow transactions with an excessive
	// number of signature operations which would result in making it impossible to mine. Since the coinbase address
	// itself can contain signature operations, the maximum allowed signature operations per transaction is less than
	// the maximum allowed signature operations per block. TODO(roasbeef): last bool should be conditional on segwit
	// activation
	var sigOpCost int
	sigOpCost, e = blockchain.GetSigOpCost(tx, false, utxoView, true)
	if e != nil {
		if cErr, ok := e.(blockchain.RuleError); ok {
			return nil, nil, chainRuleError(cErr)
		}
		return nil, nil, e
	}
	if sigOpCost > mp.cfg.Policy.MaxSigOpCostPerTx {
		str := fmt.Sprintf(
			"transaction %v sigop cost is too high: %d > %d",
			txHash, sigOpCost, mp.cfg.Policy.MaxSigOpCostPerTx,
		)
		return nil, nil, txRuleError(wire.RejectNonstandard, str)
	}
	// Don't allow transactions with fees too low to get into a mined block. Most miners allow a free transaction area
	// in blocks they mine to go alongside the area used for high-priority transactions as well as transactions with
	// fees. A transaction size of up to 1000 bytes is considered safe to go into this section. Further, the minimum fee
	// calculated below on its own would encourage several small transactions to avoid fees rather than one single
	// larger transaction which is more desirable. Therefore as long as the size of the transaction does not exceed 1000
	// less than the reserved space for high-priority transactions, don't require a fee for it.
	serializedSize := GetTxVirtualSize(tx)
	minFee := calcMinRequiredTxRelayFee(
		serializedSize,
		mp.cfg.Policy.MinRelayTxFee,
	)
	if serializedSize >= (constant.DefaultBlockPrioritySize-1000) && txFee < minFee {
		str := fmt.Sprintf(
			"transaction %v has %d fees which is under the required amount of %d",
			txHash, txFee, minFee,
		)
		return nil, nil, txRuleError(wire.RejectInsufficientFee, str)
	}
	// Require that free transactions have sufficient priority to be mined in the next block. Transactions which are
	// being added back to the memory pool from blocks that have been disconnected during a reorg are exempted.
	if isNew && !mp.cfg.Policy.DisableRelayPriority && txFee < minFee {
		currentPriority := mining.CalcPriority(
			tx.MsgTx(), utxoView,
			nextBlockHeight,
		)
		if currentPriority <= mining.MinHighPriority.ToDUO() {
			str := fmt.Sprintf(
				"transaction %v has insufficient "+
					"priority (%v <= %v)", txHash,
				currentPriority, mining.MinHighPriority,
			)
			return nil, nil, txRuleError(wire.RejectInsufficientFee, str)
		}
	}
	// Free-to-relay transactions are rate limited here to prevent penny -flooding with tiny transactions as a form of
	// attack.
	if rateLimit && txFee < minFee {
		nowUnix := time.Now().Unix()
		// Decay passed data with an exponentially decaying ~10 minute window - matches bitcoind handling.
		mp.pennyTotal *= math.Pow(
			1.0-1.0/600.0,
			float64(nowUnix-mp.lastPennyUnix),
		)
		mp.lastPennyUnix = nowUnix
		// Are we still over the limit?
		if mp.pennyTotal >= mp.cfg.Policy.FreeTxRelayLimit*10*1000 {
			str := fmt.Sprintf(
				"transaction %v has been rejected "+
					"by the rate limiter due to low fees", txHash,
			)
			return nil, nil, txRuleError(wire.RejectInsufficientFee, str)
		}
		oldTotal := mp.pennyTotal
		mp.pennyTotal += float64(serializedSize)
		T.F(
			"rate limit: curTotal %v, nextTotal: %v, limit %v",
			oldTotal,
			mp.pennyTotal,
			mp.cfg.Policy.FreeTxRelayLimit*10*1000,
		)
	}
	// Verify crypto signatures for each input and reject the transaction if any don't verify.
	e = blockchain.ValidateTransactionScripts(
		b, tx, utxoView,
		txscript.StandardVerifyFlags, mp.cfg.SigCache,
		mp.cfg.HashCache,
	)
	if e != nil {
		if cErr, ok := e.(blockchain.RuleError); ok {
			return nil, nil, chainRuleError(cErr)
		}
		return nil, nil, e
	}
	// Add to transaction pool.
	txD := mp.addTransaction(utxoView, tx, bestHeight, txFee)
	D.F(
		"accepted transaction %v (pool size: %v) %s",
		txHash,
		len(mp.pool),
	)
	return nil, txD, nil
}

// maybeAddOrphan potentially adds an orphan to the orphan pool. This function MUST be called with the mempool lock held
// (for writes).
func (mp *TxPool) maybeAddOrphan(tx *util.Tx, tag Tag) (e error) {
	// Ignore orphan transactions that are too large. This helps avoid a memory exhaustion attack based on sending a lot
	// of really large orphans. In the case there is a valid transaction larger than this, it will ultimately be
	// rebroadcast after the parent transactions have been mined or otherwise received. Note that the number of orphan
	// transactions in the orphan pool is also limited, so this equates to a maximum memory used of mp.cfg.Policy.
	// MaxOrphanTxSize * mp.cfg.Policy.MaxOrphanTxs ( which is ~5MB using the default values at the time this comment
	// was written).
	serializedLen := tx.MsgTx().SerializeSize()
	if serializedLen > mp.cfg.Policy.MaxOrphanTxSize {
		str := fmt.Sprintf(
			"orphan transaction size of %d bytes is larger"+
				" than max allowed size of %d bytes",
			serializedLen, mp.cfg.Policy.MaxOrphanTxSize,
		)
		return txRuleError(wire.RejectNonstandard, str)
	}
	// Add the orphan if the none of the above disqualified it.
	mp.addOrphan(tx, tag)
	return nil
}

// processOrphans is the internal function which implements the public ProcessOrphans. See the comment for
// ProcessOrphans for more details. This function MUST be called with the mempool lock held (for writes).
func (mp *TxPool) processOrphans(b *blockchain.BlockChain, acceptedTx *util.Tx) []*TxDesc {
	var acceptedTxns []*TxDesc
	// Start with processing at least the passed transaction.
	processList := list.New()
	processList.PushBack(acceptedTx)
	for processList.Len() > 0 {
		// Pop the transaction to process from the front of the list.
		firstElement := processList.Remove(processList.Front())
		processItem := firstElement.(*util.Tx)
		prevOut := wire.OutPoint{Hash: *processItem.Hash()}
		for txOutIdx := range processItem.MsgTx().TxOut {
			// Look up all orphans that redeem the output that is now available. This will typically only be one but it
			// could be multiple if the orphan pool contains double spends. While it may seem odd that the orphan pool
			// would allow this since there can only possibly ultimately be a single redeemer, it's important to track
			// it this way to prevent malicious actors from being able to purposely constructing orphans that would
			// otherwise make outputs unspendable. Skip to the next available output if there are none.
			prevOut.Index = uint32(txOutIdx)
			orphans, exists := mp.orphansByPrev[prevOut]
			if !exists {
				continue
			}
			// Potentially accept an orphan into the tx pool.
			for _, tx := range orphans {
				missing, txD, e := mp.maybeAcceptTransaction(
					b, tx, true, true, false,
				)
				if e != nil {
					// The orphan is now invalid so there is no way any other orphans which redeem any of its outputs
					// can be accepted. Remove them.
					mp.removeOrphan(tx, true)
					break
				}
				// Transaction is still an orphan. Try the next orphan which redeems this output.
				if len(missing) > 0 {
					continue
				}
				// Transaction was accepted into the main pool. Add it to the list of accepted transactions that are no
				// longer orphans, remove it from the orphan pool, and add it to the list of transactions to process so
				// any orphans that depend on it are handled too.
				acceptedTxns = append(acceptedTxns, txD)
				mp.removeOrphan(tx, false)
				processList.PushBack(tx)
				// Only one transaction for this outpoint can be accepted, so the rest are now double spends and are
				// removed later.
				break
			}
		}
	}
	// Recursively remove any orphans that also redeem any outputs redeemed by the accepted transactions since those are
	// now definitive double spends.
	mp.removeOrphanDoubleSpends(acceptedTx)
	for _, txD := range acceptedTxns {
		mp.removeOrphanDoubleSpends(txD.Tx)
	}
	return acceptedTxns
}

// removeOrphan is the internal function which implements the public RemoveOrphan. See the comment for RemoveOrphan for
// more details. This function MUST be called with the mempool lock held (for writes).
func (mp *TxPool) removeOrphan(tx *util.Tx, removeRedeemers bool) {
	// Nothing to do if passed tx is not an orphan.
	txHash := tx.Hash()
	otx, exists := mp.orphans[*txHash]
	if !exists {
		return
	}
	// Remove the reference from the previous orphan index.
	for _, txIn := range otx.tx.MsgTx().TxIn {
		orphans, exists := mp.orphansByPrev[txIn.PreviousOutPoint]
		if exists {
			delete(orphans, *txHash)
			// Remove the map entry altogether if there are no longer any orphans which depend on it.
			if len(orphans) == 0 {
				delete(mp.orphansByPrev, txIn.PreviousOutPoint)
			}
		}
	}
	// Remove any orphans that redeem outputs from this one if requested.
	if removeRedeemers {
		prevOut := wire.OutPoint{Hash: *txHash}
		for txOutIdx := range tx.MsgTx().TxOut {
			prevOut.Index = uint32(txOutIdx)
			for _, orphan := range mp.orphansByPrev[prevOut] {
				mp.removeOrphan(orphan, true)
			}
		}
	}
	// Remove the transaction from the orphan pool.
	delete(mp.orphans, *txHash)
}

// removeOrphanDoubleSpends removes all orphans which spend outputs spent by the passed transaction from the orphan
// pool. Removing those orphans then leads to removing all orphans which rely on them, recursively. This is necessary
// when a transaction is added to the main pool because it may spend outputs orphans also spend. This function MUST be
// called with the mempool lock held (for writes).
func (mp *TxPool) removeOrphanDoubleSpends(tx *util.Tx) {
	msgTx := tx.MsgTx()
	for _, txIn := range msgTx.TxIn {
		for _, orphan := range mp.orphansByPrev[txIn.PreviousOutPoint] {
			mp.removeOrphan(orphan, true)
		}
	}
}

// removeTransaction is the internal function which implements the public RemoveTransaction. See the comment for
// RemoveTransaction for more details. This function MUST be called with the mempool lock held (for writes).
func (mp *TxPool) removeTransaction(tx *util.Tx, removeRedeemers bool) {
	txHash := tx.Hash()
	if removeRedeemers {
		// Remove any transactions which rely on this one.
		for i := uint32(0); i < uint32(len(tx.MsgTx().TxOut)); i++ {
			prevOut := wire.OutPoint{Hash: *txHash, Index: i}
			if txRedeemer, exists := mp.outpoints[prevOut]; exists {
				mp.removeTransaction(txRedeemer, true)
			}
		}
	}
	// Remove the transaction if needed.
	if txDesc, exists := mp.pool[*txHash]; exists {
		// Remove unconfirmed address index entries associated with the transaction if enabled.
		if mp.cfg.AddrIndex != nil {
			mp.cfg.AddrIndex.RemoveUnconfirmedTx(txHash)
		}
		// Mark the referenced outpoints as unspent by the pool.
		for _, txIn := range txDesc.Tx.MsgTx().TxIn {
			delete(mp.outpoints, txIn.PreviousOutPoint)
		}
		delete(mp.pool, *txHash)
		atomic.StoreInt64(&mp.lastUpdated, time.Now().Unix())
		if mp.updateHook != nil {
			mp.updateHook()
		}
	}
}

// New returns a new memory pool for validating and storing standalone transactions until they are mined into a block.
func New(cfg *Config) *TxPool {
	return &TxPool{
		cfg:            *cfg,
		pool:           make(map[chainhash.Hash]*TxDesc),
		orphans:        make(map[chainhash.Hash]*orphanTx),
		orphansByPrev:  make(map[wire.OutPoint]map[chainhash.Hash]*util.Tx),
		nextExpireScan: time.Now().Add(orphanExpireScanInterval),
		outpoints:      make(map[wire.OutPoint]*util.Tx),
		updateHook:     cfg.UpdateHook,
	}
}