1 package mempool
2 3 import (
4 "container/list"
5 "errors"
6 "fmt"
7 "github.com/p9c/p9/pkg/amt"
8 "github.com/p9c/p9/pkg/chaincfg"
9 "github.com/p9c/p9/pkg/constant"
10 "github.com/p9c/p9/pkg/log"
11 "math"
12 "sync"
13 "sync/atomic"
14 "time"
15 16 "github.com/p9c/p9/pkg/blockchain"
17 "github.com/p9c/p9/pkg/chainhash"
18 "github.com/p9c/p9/pkg/hardfork"
19 "github.com/p9c/p9/pkg/indexers"
20 "github.com/p9c/p9/pkg/mining"
21 "github.com/p9c/p9/pkg/txscript"
22 "github.com/p9c/p9/pkg/wire"
23 24 "github.com/p9c/p9/pkg/btcjson"
25 "github.com/p9c/p9/pkg/util"
26 )
27 28 // Config is a descriptor containing the memory pool configuration.
29 type Config struct {
30 // Policy defines the various mempool configuration options related to policy.
31 Policy Policy
32 // ChainParams identifies which chain parameters the txpool is associated with.
33 ChainParams *chaincfg.Params
34 // FetchUtxoView defines the function to use to fetch unspent transaction output information.
35 FetchUtxoView func(*util.Tx) (*blockchain.UtxoViewpoint, error)
36 // BestHeight defines the function to use to access the block height of the current best chain.
37 BestHeight func() int32
38 // MedianTimePast defines the function to use in order to access the median time past calculated from the
39 // point-of-view of the current chain tip within the best chain.
40 MedianTimePast func() time.Time
41 // // CalcSequenceLock defines the function to use in order to generate the current sequence lock for the given
42 // // transaction using the passed utxo view.
43 // CalcSequenceLock func(*util.Tx, *blockchain.UtxoViewpoint) (*blockchain.SequenceLock, error)
44 // IsDeploymentActive returns true if the target deploymentID is active, and false otherwise. The mempool uses
45 // this function to gauge if transactions using new to be soft-forked rules should be allowed into the mempool
46 // or not.
47 IsDeploymentActive func(deploymentID uint32) (bool, error)
48 // SigCache defines a signature cache to use.
49 SigCache *txscript.SigCache
50 // HashCache defines the transaction hash mid-state cache to use.
51 HashCache *txscript.HashCache
52 // AddrIndex defines the optional address index instance to use for indexing the unconfirmed transactions in the
53 // memory pool. This can be nil if the address index is not enabled.
54 AddrIndex *indexers.AddrIndex
55 // FeeEstimatator provides a feeEstimator. If it is not nil, the mempool records all new transactions it
56 // observes into the feeEstimator.
57 FeeEstimator *FeeEstimator
58 // UpdateHook is a function that is called when transactions are added or
59 // removed from the mempool
60 UpdateHook func()
61 }
62 63 // Policy houses the policy (configuration parameters) that is used to control the mempool.
64 type Policy struct {
65 // MaxTxVersion is the transaction version that the mempool should accept. All transactions above this version are
66 // rejected as non-standard.
67 MaxTxVersion int32
68 // DisableRelayPriority defines whether to relay free or low-fee transactions that do not have enough priority to be
69 // relayed.
70 DisableRelayPriority bool
71 // AcceptNonStd defines whether to accept non-standard transactions. If true, non-standard transactions will be
72 // accepted into the mempool. Otherwise, all non-standard transactions will be rejected.
73 AcceptNonStd bool
74 // FreeTxRelayLimit defines the given amount in thousands of bytes per minute that transactions with no fee are rate
75 // limited to.
76 FreeTxRelayLimit float64
77 // MaxOrphanTxs is the maximum number of orphan transactions that can be queued.
78 MaxOrphanTxs int
79 // MaxOrphanTxSize is the maximum size allowed for orphan transactions. This helps prevent memory exhaustion attacks
80 // from sending a lot of of big orphans.
81 MaxOrphanTxSize int
82 // MaxSigOpCostPerTx is the cumulative maximum cost of all the signature operations in a single transaction we will
83 // relay or mine. It is a fraction of the max signature operations for a block.
84 MaxSigOpCostPerTx int
85 // MinRelayTxFee defines the minimum transaction fee in DUO/kB to be considered a non-zero fee.
86 MinRelayTxFee amt.Amount
87 }
88 89 // Tag represents an identifier to use for tagging orphan transactions. The caller may choose any scheme it desires
90 // however it is common to use peer IDs so that orphans can be identified by which peer first relayed them.
91 type Tag uint64
92 93 // TxDesc is a descriptor containing a transaction in the mempool along with additional metadata.
94 type TxDesc struct {
95 mining.TxDesc
96 // StartingPriority is the priority of the transaction when it was added to the pool.
97 StartingPriority float64
98 }
99 100 // TxPool is used as a source of transactions that need to be mined into blocks and relayed to other peers. It is safe
101 // for concurrent access from multiple peers.
102 type TxPool struct {
103 // The following variables must only be used atomically.
104 lastUpdated int64 // last time pool was updated
105 mtx sync.RWMutex
106 cfg Config
107 pool map[chainhash.Hash]*TxDesc
108 orphans map[chainhash.Hash]*orphanTx
109 orphansByPrev map[wire.OutPoint]map[chainhash.Hash]*util.Tx
110 outpoints map[wire.OutPoint]*util.Tx
111 pennyTotal float64 // exponentially decaying total for penny spends.
112 lastPennyUnix int64 // unix time of last ``penny spend''
113 // nextExpireScan is the time after which the orphan pool will be scanned in order to evict orphans. This is NOT
114 // a hard deadline as the scan will only run when an orphan is added to the pool as opposed to on an
115 // unconditional timer.
116 nextExpireScan time.Time
117 updateHook func()
118 }
119 120 // orphanTx is normal transaction that references an ancestor transaction that is not yet available. It also contains
121 // additional information related to it such as an expiration time to help prevent caching the orphan forever.
122 type orphanTx struct {
123 tx *util.Tx
124 tag Tag
125 expiration time.Time
126 }
127 128 const (
129 // orphanTTL is the maximum amount of time an orphan is allowed to stay in the orphan pool before it expires and is
130 // evicted during the next scan.
131 orphanTTL = time.Minute * 15
132 // orphanExpireScanInterval is the minimum amount of time in between
133 // scans of the orphan pool to evict expired transactions.
134 orphanExpireScanInterval = time.Minute * 5
135 )
136 137 var // Ensure the TxPool type implements the mining.TxSource interface.
138 _ mining.TxSource = (*TxPool)(nil)
139 140 // CheckSpend checks whether the passed outpoint is already spent by a transaction in the mempool. If that's the case
141 // the spending transaction will be returned, if not nil will be returned.
142 func (mp *TxPool) CheckSpend(op wire.OutPoint) *util.Tx {
143 mp.mtx.RLock()
144 txR := mp.outpoints[op]
145 mp.mtx.RUnlock()
146 return txR
147 }
148 149 // Count returns the number of transactions in the main pool. It does not include the orphan pool. This function is safe
150 // for concurrent access.
151 func (mp *TxPool) Count() int {
152 mp.mtx.RLock()
153 count := len(mp.pool)
154 mp.mtx.RUnlock()
155 return count
156 }
157 158 // FetchTransaction returns the requested transaction from the transaction pool. This only fetches from the main
159 // transaction pool and does not include orphans. This function is safe for concurrent access.
160 func (mp *TxPool) FetchTransaction(txHash *chainhash.Hash) (*util.Tx, error) {
161 // Protect concurrent access.
162 mp.mtx.RLock()
163 txDesc, exists := mp.pool[*txHash]
164 mp.mtx.RUnlock()
165 if exists {
166 return txDesc.Tx, nil
167 }
168 return nil, fmt.Errorf("transaction is not in the pool")
169 }
170 171 // HaveTransaction returns whether or not the passed transaction already exists in the main pool or in the orphan pool.
172 // This function is safe for concurrent access.
173 func (mp *TxPool) HaveTransaction(hash *chainhash.Hash) bool {
174 // Protect concurrent access.
175 mp.mtx.RLock()
176 haveTx := mp.haveTransaction(hash)
177 mp.mtx.RUnlock()
178 return haveTx
179 }
180 181 // IsOrphanInPool returns whether or not the passed transaction already exists in the orphan pool. This function is safe
182 // for concurrent access.
183 func (mp *TxPool) IsOrphanInPool(hash *chainhash.Hash) bool {
184 // Protect concurrent access.
185 mp.mtx.RLock()
186 inPool := mp.isOrphanInPool(hash)
187 mp.mtx.RUnlock()
188 return inPool
189 }
190 191 // IsTransactionInPool returns whether or not the passed transaction already exists in the main pool. This function is
192 // safe for concurrent access.
193 func (mp *TxPool) IsTransactionInPool(hash *chainhash.Hash) bool {
194 // Protect concurrent access.
195 mp.mtx.RLock()
196 inPool := mp.isTransactionInPool(hash)
197 mp.mtx.RUnlock()
198 return inPool
199 }
200 201 // LastUpdated returns the last time a transaction was added to or removed from the main pool. It does not include the
202 // orphan pool. This function is safe for concurrent access.
203 func (mp *TxPool) LastUpdated() time.Time {
204 return time.Unix(atomic.LoadInt64(&mp.lastUpdated), 0)
205 }
206 207 // MaybeAcceptTransaction is the main workhorse for handling insertion of new free-standing transactions into a memory
208 // pool. It includes functionality such as rejecting duplicate transactions, ensuring transactions follow all rules,
209 // detecting orphan transactions, and insertion into the memory pool. If the transaction is an orphan ( missing parent
210 // transactions) the transaction is NOT added to the orphan pool but each unknown referenced parent is returned. Use
211 // ProcessTransaction instead if new orphans should be added to the orphan pool. This function is safe for concurrent
212 // access.
213 func (mp *TxPool) MaybeAcceptTransaction(
214 b *blockchain.BlockChain,
215 tx *util.Tx, isNew, rateLimit bool,
216 ) (hashes []*chainhash.Hash, txD *TxDesc, e error) {
217 // Protect concurrent access.
218 mp.mtx.Lock()
219 hashes, txD, e = mp.maybeAcceptTransaction(b, tx, isNew, rateLimit, true)
220 mp.mtx.Unlock()
221 return hashes, txD, e
222 }
223 224 // MiningDescs returns a slice of mining descriptors for all the transactions in the pool. This is part of the mining.
225 // TxSource interface implementation and is safe for concurrent access as required by the interface contract.
226 func (mp *TxPool) MiningDescs() []*mining.TxDesc {
227 mp.mtx.RLock()
228 descs := make([]*mining.TxDesc, len(mp.pool))
229 i := 0
230 for _, desc := range mp.pool {
231 descs[i] = &desc.TxDesc
232 i++
233 }
234 mp.mtx.RUnlock()
235 return descs
236 }
237 238 // ProcessOrphans determines if there are any orphans which depend on the passed transaction hash (it is possible that
239 // they are no longer orphans) and potentially accepts them to the memory pool. It repeats the process for the newly
240 // accepted transactions (to detect further orphans which may no longer be orphans) until there are no more. It returns
241 // a slice of transactions added to the mempool. A nil slice means no transactions were moved from the orphan pool to
242 // the mempool. This function is safe for concurrent access.
243 func (mp *TxPool) ProcessOrphans(b *blockchain.BlockChain, acceptedTx *util.Tx) []*TxDesc {
244 mp.mtx.Lock()
245 acceptedTxns := mp.processOrphans(b, acceptedTx)
246 mp.mtx.Unlock()
247 return acceptedTxns
248 }
249 250 // ProcessTransaction is the main workhorse for handling insertion of new free-standing transactions into the memory
251 // pool. It includes functionality such as rejecting duplicate transactions, ensuring transactions follow all rules,
252 // orphan transaction handling, and insertion into the memory pool. It returns a slice of transactions added to the
253 // mempool. When the error is nil the list will include the passed transaction itself along with any additional orphan
254 // transactions that were added as a result of the passed one being accepted. This function is safe for concurrent
255 // access.
256 func (mp *TxPool) ProcessTransaction(
257 b *blockchain.BlockChain, tx *util.Tx,
258 allowOrphan, rateLimit bool, tag Tag,
259 ) ([]*TxDesc, error) {
260 D.Ln("processing transaction", tx.Hash())
261 // Protect concurrent access.
262 mp.mtx.Lock()
263 defer mp.mtx.Unlock()
264 // Potentially accept the transaction to the memory pool.
265 missingParents, txD, e := mp.maybeAcceptTransaction(
266 b, tx, true,
267 rateLimit, true,
268 )
269 if e != nil {
270 return nil, e
271 }
272 if len(missingParents) == 0 {
273 // Accept any orphan transactions that depend on this transaction ( they may no longer be orphans if all inputs
274 // are now available) and repeat for those accepted transactions until there are no more.
275 newTxs := mp.processOrphans(b, tx)
276 acceptedTxs := make([]*TxDesc, len(newTxs)+1)
277 // Add the parent transaction first so remote nodes do not add orphans.
278 acceptedTxs[0] = txD
279 copy(acceptedTxs[1:], newTxs)
280 return acceptedTxs, nil
281 }
282 // The transaction is an orphan (has inputs missing). Reject it if the flag to allow orphans is not set.
283 if !allowOrphan {
284 // Only use the first missing parent transaction in the error message. NOTE: RejectDuplicate is really not an
285 // accurate reject code here, but it matches the reference implementation and there isn't a better choice due to
286 // the limited number of reject codes. Missing inputs is assumed to mean they are already spent which is not
287 // really always the case.
288 str := fmt.Sprintf(
289 "orphan transaction %v references outputs of"+
290 " unknown or fully-spent transaction %v", tx.Hash(),
291 missingParents[0],
292 )
293 return nil, txRuleError(wire.RejectDuplicate, str)
294 }
295 // Potentially add the orphan transaction to the orphan pool.
296 e = mp.maybeAddOrphan(tx, tag)
297 return nil, e
298 }
299 300 // RawMempoolVerbose returns all of the entries in the mempool as a fully populated json result. This function is safe
301 // for concurrent access.
302 func (mp *TxPool) RawMempoolVerbose() map[string]*btcjson.GetRawMempoolVerboseResult {
303 mp.mtx.RLock()
304 defer mp.mtx.RUnlock()
305 result := make(map[string]*btcjson.GetRawMempoolVerboseResult, len(mp.pool))
306 bestHeight := mp.cfg.BestHeight()
307 for _, desc := range mp.pool {
308 // Calculate the current priority based on the inputs to the transaction. Use zero if one or more of the input
309 // transactions can't be found for some reason.
310 tx := desc.Tx
311 var currentPriority float64
312 utxos, e := mp.fetchInputUtxos(tx)
313 if e == nil {
314 currentPriority = mining.CalcPriority(
315 tx.MsgTx(), utxos,
316 bestHeight+1,
317 )
318 }
319 mpd := &btcjson.GetRawMempoolVerboseResult{
320 Size: int32(tx.MsgTx().SerializeSize()),
321 VSize: int32(GetTxVirtualSize(tx)),
322 Fee: amt.Amount(desc.Fee).ToDUO(),
323 Time: desc.Added.Unix(),
324 Height: int64(desc.Height),
325 StartingPriority: desc.StartingPriority,
326 CurrentPriority: currentPriority,
327 Depends: make([]string, 0),
328 }
329 for _, txIn := range tx.MsgTx().TxIn {
330 hash := &txIn.PreviousOutPoint.Hash
331 if mp.haveTransaction(hash) {
332 mpd.Depends = append(
333 mpd.Depends,
334 hash.String(),
335 )
336 }
337 }
338 result[tx.Hash().String()] = mpd
339 }
340 return result
341 }
342 343 // RemoveDoubleSpends removes all transactions which spend outputs spent by the passed transaction from the memory pool.
344 // Removing those transactions then leads to removing all transactions which rely on them, recursively. This is
345 // necessary when a block is connected to the main chain because the block may contain transactions which were
346 // previously unknown to the memory pool. This function is safe for concurrent access.
347 func (mp *TxPool) RemoveDoubleSpends(tx *util.Tx) {
348 // Protect concurrent access.
349 mp.mtx.Lock()
350 for _, txIn := range tx.MsgTx().TxIn {
351 if txRedeemer, ok := mp.outpoints[txIn.PreviousOutPoint]; ok {
352 if !txRedeemer.Hash().IsEqual(tx.Hash()) {
353 mp.removeTransaction(txRedeemer, true)
354 }
355 }
356 }
357 mp.mtx.Unlock()
358 }
359 360 // RemoveOrphan removes the passed orphan transaction from the orphan pool and previous orphan index. This function is
361 // safe for concurrent access.
362 func (mp *TxPool) RemoveOrphan(tx *util.Tx) {
363 mp.mtx.Lock()
364 mp.removeOrphan(tx, false)
365 mp.mtx.Unlock()
366 }
367 368 // RemoveOrphansByTag removes all orphan transactions tagged with the provided identifier. This function is safe for
369 // concurrent access.
370 func (mp *TxPool) RemoveOrphansByTag(tag Tag) uint64 {
371 var numEvicted uint64
372 mp.mtx.Lock()
373 for _, otx := range mp.orphans {
374 if otx.tag == tag {
375 mp.removeOrphan(otx.tx, true)
376 numEvicted++
377 }
378 }
379 mp.mtx.Unlock()
380 return numEvicted
381 }
382 383 // RemoveTransaction removes the passed transaction from the mempool. When the removeRedeemers flag is set any
384 // transactions that redeem outputs from the removed transaction will also be removed recursively from the mempool, as
385 // they would otherwise become orphans. This function is safe for concurrent access.
386 func (mp *TxPool) RemoveTransaction(tx *util.Tx, removeRedeemers bool) {
387 // Protect concurrent access.
388 mp.mtx.Lock()
389 mp.removeTransaction(tx, removeRedeemers)
390 mp.mtx.Unlock()
391 }
392 393 // TxDescs returns a slice of descriptors for all the transactions in the pool. The descriptors are to be treated as
394 // read only. This function is safe for concurrent access.
395 func (mp *TxPool) TxDescs() []*TxDesc {
396 mp.mtx.RLock()
397 descs := make([]*TxDesc, len(mp.pool))
398 i := 0
399 for _, desc := range mp.pool {
400 descs[i] = desc
401 i++
402 }
403 mp.mtx.RUnlock()
404 return descs
405 }
406 407 // TxHashes returns a slice of hashes for all of the transactions in the memory pool. This function is safe for
408 // concurrent access.
409 func (mp *TxPool) TxHashes() []*chainhash.Hash {
410 mp.mtx.RLock()
411 hashes := make([]*chainhash.Hash, len(mp.pool))
412 i := 0
413 for hash := range mp.pool {
414 hashCopy := hash
415 hashes[i] = &hashCopy
416 i++
417 }
418 mp.mtx.RUnlock()
419 return hashes
420 }
421 422 // addOrphan adds an orphan transaction to the orphan pool. This function MUST be called with the mempool lock held (for
423 // writes).
424 func (mp *TxPool) addOrphan(tx *util.Tx, tag Tag) {
425 // Nothing to do if no orphans are allowed.
426 if mp.cfg.Policy.MaxOrphanTxs <= 0 {
427 return
428 }
429 // Limit the number orphan transactions to prevent memory exhaustion. This will periodically remove any expired
430 // orphans and evict a random orphan if space is still needed.
431 e := mp.limitNumOrphans()
432 if e != nil {
433 W.Ln("failed to set orphan limit", e)
434 }
435 mp.orphans[*tx.Hash()] = &orphanTx{
436 tx: tx,
437 tag: tag,
438 expiration: time.Now().Add(orphanTTL),
439 }
440 for _, txIn := range tx.MsgTx().TxIn {
441 if _, exists := mp.orphansByPrev[txIn.PreviousOutPoint]; !exists {
442 mp.orphansByPrev[txIn.PreviousOutPoint] =
443 make(map[chainhash.Hash]*util.Tx)
444 }
445 mp.orphansByPrev[txIn.PreviousOutPoint][*tx.Hash()] = tx
446 }
447 D.Ln("stored orphan transaction", tx.Hash(), "(total:", len(mp.orphans), ")")
448 }
449 450 // addTransaction adds the passed transaction to the memory pool. It should not be called directly as it doesn't perform
451 // any validation. This is a helper for maybeAcceptTransaction. This function MUST be called with the mempool lock held
452 // (for writes).
453 func (mp *TxPool) addTransaction(utxoView *blockchain.UtxoViewpoint, tx *util.Tx, height int32, fee int64) *TxDesc {
454 // Add the transaction to the pool and mark the referenced outpoints as spent by the pool.
455 txD := &TxDesc{
456 TxDesc: mining.TxDesc{
457 Tx: tx,
458 Added: time.Now(),
459 Height: height,
460 Fee: fee,
461 FeePerKB: fee * 1000 / GetTxVirtualSize(tx),
462 },
463 StartingPriority: mining.CalcPriority(tx.MsgTx(), utxoView, height),
464 }
465 mp.pool[*tx.Hash()] = txD
466 for _, txIn := range tx.MsgTx().TxIn {
467 mp.outpoints[txIn.PreviousOutPoint] = tx
468 }
469 atomic.StoreInt64(&mp.lastUpdated, time.Now().Unix())
470 if mp.updateHook != nil {
471 mp.updateHook()
472 }
473 // Add unconfirmed address index entries associated with the transaction if enabled.
474 if mp.cfg.AddrIndex != nil {
475 mp.cfg.AddrIndex.AddUnconfirmedTx(tx, utxoView)
476 }
477 // Record this tx for fee estimation if enabled.
478 if mp.cfg.FeeEstimator != nil {
479 mp.cfg.FeeEstimator.ObserveTransaction(txD)
480 }
481 return txD
482 }
483 484 // checkPoolDoubleSpend checks whether or not the passed transaction is attempting to spend coins already spent by other
485 // transactions in the pool. Note it does not check for double spends against transactions already in the main chain.
486 // This function MUST be called with the mempool lock held (for reads).
487 func (mp *TxPool) checkPoolDoubleSpend(tx *util.Tx) (e error) {
488 for _, txIn := range tx.MsgTx().TxIn {
489 if txR, exists := mp.outpoints[txIn.PreviousOutPoint]; exists {
490 str := fmt.Sprintf(
491 "output %v already spent by "+
492 "transaction %v in the memory pool",
493 txIn.PreviousOutPoint, txR.Hash(),
494 )
495 return txRuleError(wire.RejectDuplicate, str)
496 }
497 }
498 return nil
499 }
500 501 // fetchInputUtxos loads utxo details about the input transactions referenced by the passed transaction. First it loads
502 // the details form the viewpoint of the main chain, then it adjusts them based upon the contents of the transaction
503 // pool. This function MUST be called with the mempool lock held (for reads).
504 func (mp *TxPool) fetchInputUtxos(tx *util.Tx) (*blockchain.UtxoViewpoint, error) {
505 utxoView, e := mp.cfg.FetchUtxoView(tx)
506 if e != nil {
507 return nil, e
508 }
509 // Attempt to populate any missing inputs from the transaction pool.
510 for _, txIn := range tx.MsgTx().TxIn {
511 prevOut := &txIn.PreviousOutPoint
512 entry := utxoView.LookupEntry(*prevOut)
513 if entry != nil && !entry.IsSpent() {
514 continue
515 }
516 if poolTxDesc, exists := mp.pool[prevOut.Hash]; exists {
517 // AddTxOut ignores out of range index values,
518 // so it is safe to call without bounds checking here.
519 utxoView.AddTxOut(
520 poolTxDesc.Tx, prevOut.Index,
521 mining.UnminedHeight,
522 )
523 }
524 }
525 return utxoView, nil
526 }
527 528 // haveTransaction returns whether or not the passed transaction already exists in the main pool or in the orphan pool.
529 // This function MUST be called with the mempool lock held (for reads).
530 func (mp *TxPool) haveTransaction(
531 hash *chainhash.Hash,
532 ) bool {
533 return mp.isTransactionInPool(hash) || mp.isOrphanInPool(hash)
534 }
535 536 // isOrphanInPool returns whether or not the passed transaction already exists in the orphan pool. This function MUST be
537 // called with the mempool lock held (for reads).
538 func (mp *TxPool) isOrphanInPool(hash *chainhash.Hash) bool {
539 if _, exists := mp.orphans[*hash]; exists {
540 return true
541 }
542 return false
543 }
544 545 // isTransactionInPool returns whether or not the passed transaction already exists in the main pool. This function MUST
546 // be called with the mempool lock held (for reads).
547 func (mp *TxPool) isTransactionInPool(hash *chainhash.Hash) bool {
548 if _, exists := mp.pool[*hash]; exists {
549 return true
550 }
551 return false
552 }
553 554 // limitNumOrphans limits the number of orphan transactions by evicting a random orphan if adding a new one would cause
555 // it to overflow the max allowed. This function MUST be called with the mempool lock held (for writes).
556 func (mp *TxPool) limitNumOrphans() (e error) {
557 // Scan through the orphan pool and remove any expired orphans when it's time. This is done for efficiency so the
558 // scan only happens periodically instead of on every orphan added to the pool.
559 if now := time.Now(); now.After(mp.nextExpireScan) {
560 origNumOrphans := len(mp.orphans)
561 for _, otx := range mp.orphans {
562 if now.After(otx.expiration) {
563 // Remove redeemers too because the missing parents are very unlikely to ever materialize since the
564 // orphan has already been around more than long enough for them to be delivered.
565 mp.removeOrphan(otx.tx, true)
566 }
567 }
568 // Set next expiration scan to occur after the scan interval.
569 mp.nextExpireScan = now.Add(orphanExpireScanInterval)
570 numOrphans := len(mp.orphans)
571 if numExpired := origNumOrphans - numOrphans; numExpired > 0 {
572 D.F(
573 "Expired %d %s (remaining: %d)",
574 numExpired, log.PickNoun(numExpired, "orphan", "orphans"),
575 numOrphans,
576 )
577 }
578 }
579 // Nothing to do if adding another orphan will not cause the pool to exceed the limit.
580 if len(mp.orphans)+1 <= mp.cfg.Policy.MaxOrphanTxs {
581 return nil
582 }
583 // Remove a random entry from the map. For most compilers, Go's range statement iterates starting at a random item
584 // although that is not 100% guaranteed by the spec. The iteration order is not important here because an adversary
585 // would have to be able to pull off preimage attacks on the hashing function in order to target eviction of
586 // specific entries anyways.
587 for _, otx := range mp.orphans {
588 // Don't remove redeemers in the case of a random eviction since it is quite possible it might be needed again
589 // shortly.
590 mp.removeOrphan(otx.tx, false)
591 break
592 }
593 return nil
594 }
595 596 // maybeAcceptTransaction is the internal function which implements the public MaybeAcceptTransaction. See the comment
597 // for MaybeAcceptTransaction for more details. This function MUST be called with the mempool lock held (for writes).
598 func (mp *TxPool) maybeAcceptTransaction(
599 b *blockchain.BlockChain, tx *util.Tx, isNew, rateLimit, rejectDupOrphans bool,
600 ) ([]*chainhash.Hash, *TxDesc, error) {
601 txHash := tx.Hash()
602 // // If a transaction has witness data, and segwit isn't active yet, If segwit isn't active yet, then we won't accept
603 // // it into the mempool as it can't be mined yet.
604 // if tx.MsgTx().HasWitness() {
605 // segwitActive, e := mp.cfg.IsDeploymentActive(chaincfg.DeploymentSegwit)
606 // if e != nil {
607 // General // return nil, nil, e
608 // }
609 // if !segwitActive {
610 // str := fmt.Sprintf("transaction %v has witness data, but segwit isn't active yet", txHash)
611 // return nil, nil, txRuleError(wire.RejectNonstandard, str)
612 // }
613 // }
614 if blockchain.ContainsBlacklisted(b, tx, hardfork.Blacklist) {
615 return nil, nil, errors.New("transaction contains blacklisted address")
616 }
617 // Don't accept the transaction if it already exists in the pool. This applies to orphan transactions as well when
618 // the reject duplicate orphans flag is set. This check is intended to be a quick check to weed out duplicates.
619 if mp.isTransactionInPool(txHash) || (rejectDupOrphans &&
620 mp.isOrphanInPool(txHash)) {
621 str := fmt.Sprintf("already have transaction %v", txHash)
622 return nil, nil, txRuleError(wire.RejectDuplicate, str)
623 }
624 // Perform preliminary sanity checks on the transaction. This makes use of blockchain which contains the invariant
625 // rules for what transactions are allowed into blocks.
626 e := blockchain.CheckTransactionSanity(tx)
627 if e != nil {
628 if cErr, ok := e.(blockchain.RuleError); ok {
629 return nil, nil, chainRuleError(cErr)
630 }
631 return nil, nil, e
632 }
633 // A standalone transaction must not be a coinbase transaction.
634 if blockchain.IsCoinBase(tx) {
635 str := fmt.Sprintf(
636 "transaction %v is an individual coinbase",
637 txHash,
638 )
639 return nil, nil, txRuleError(wire.RejectInvalid, str)
640 }
641 // Get the current height of the main chain. A standalone transaction will be mined into the next block at best, so
642 // its height is at least one more than the current height.
643 bestHeight := mp.cfg.BestHeight()
644 nextBlockHeight := bestHeight + 1
645 medianTimePast := mp.cfg.MedianTimePast()
646 // Don't allow non-standard transactions if the network parameters forbid their acceptance.
647 if !mp.cfg.Policy.AcceptNonStd {
648 e = checkTransactionStandard(
649 tx,
650 nextBlockHeight,
651 medianTimePast,
652 mp.cfg.Policy.MinRelayTxFee,
653 mp.cfg.Policy.MaxTxVersion,
654 )
655 if e != nil {
656 // Attempt to extract a reject code from the error so it can be retained. When not possible, fall back to a
657 // non standard error.
658 rejectCode, found := extractRejectCode(e)
659 if !found {
660 rejectCode = wire.RejectNonstandard
661 }
662 str := fmt.Sprintf(
663 "transaction %v is not standard: %v",
664 txHash, e,
665 )
666 return nil, nil, txRuleError(rejectCode, str)
667 }
668 }
669 // The transaction may not use any of the same outputs as other transactions already in the pool as that would
670 // ultimately result in a double spend. This check is intended to be quick and therefore only detects double spends
671 // within the transaction pool itself. The transaction could still be double spending coins from the main chain at
672 // this point. There is a more in-depth check that happens later after fetching the referenced transaction inputs
673 // from the main chain which examines the actual spend data and prevents double spends.
674 e = mp.checkPoolDoubleSpend(tx)
675 if e != nil {
676 return nil, nil, e
677 }
678 // Fetch all of the unspent transaction outputs referenced by the inputs to this transaction. This function also
679 // attempts to fetch the transaction itself to be used for detecting a duplicate transaction without needing to do a
680 // separate lookup.
681 utxoView, e := mp.fetchInputUtxos(tx)
682 if e != nil {
683 if cErr, ok := e.(blockchain.RuleError); ok {
684 return nil, nil, chainRuleError(cErr)
685 }
686 return nil, nil, e
687 }
688 // Don't allow the transaction if it exists in the main chain and is not not already fully spent.
689 prevOut := wire.OutPoint{Hash: *txHash}
690 for txOutIdx := range tx.MsgTx().TxOut {
691 prevOut.Index = uint32(txOutIdx)
692 entry := utxoView.LookupEntry(prevOut)
693 if entry != nil && !entry.IsSpent() {
694 return nil, nil, txRuleError(
695 wire.RejectDuplicate,
696 "transaction already exists",
697 )
698 }
699 utxoView.RemoveEntry(prevOut)
700 }
701 // Transaction is an orphan if any of the referenced transaction outputs don't exist or are already spent. Adding
702 // orphans to the orphan pool is not handled by this function, and the caller should use maybeAddOrphan if this
703 // behavior is desired.
704 var missingParents []*chainhash.Hash
705 for outpoint, entry := range utxoView.Entries() {
706 if entry == nil || entry.IsSpent() {
707 // Must make a copy of the hash here since the iterator is replaced and taking its address directly would
708 // result in all of the entries pointing to the same memory location and thus all be the final hash.
709 hashCopy := outpoint.Hash
710 missingParents = append(missingParents, &hashCopy)
711 }
712 }
713 if len(missingParents) > 0 {
714 return missingParents, nil, nil
715 }
716 // // Don't allow the transaction into the mempool unless its sequence lock is active, meaning that it'll be allowed
717 // // into the next block with respect to its defined relative lock times.
718 // sequenceLock, e := mp.cfg.CalcSequenceLock(tx, utxoView)
719 // if e != nil {
720 // General // if cErr, ok := err.(blockchain.RuleError); ok {
721 // return nil, nil, chainRuleError(cErr)
722 // }
723 // return nil, nil, e
724 // }
725 // if !blockchain.SequenceLockActive(
726 // sequenceLock, nextBlockHeight,
727 // medianTimePast,
728 // ) {
729 // return nil, nil, txRuleError(
730 // wire.RejectNonstandard,
731 // "transaction's sequence locks on inputs not met",
732 // )
733 // }
734 // Perform several checks on the transaction inputs using the invariant rules in blockchain for what transactions
735 // are allowed into blocks. Also returns the fees associated with the transaction which will be used later.
736 txFee, e := blockchain.CheckTransactionInputs(
737 tx, nextBlockHeight,
738 utxoView, mp.cfg.ChainParams,
739 )
740 if e != nil {
741 if cErr, ok := e.(blockchain.RuleError); ok {
742 return nil, nil, chainRuleError(cErr)
743 }
744 return nil, nil, e
745 }
746 // Don't allow transactions with non-standard inputs if the network parameters forbid their acceptance.
747 if !mp.cfg.Policy.AcceptNonStd {
748 e = checkInputsStandard(tx, utxoView)
749 if e != nil {
750 // Attempt to extract a reject code from the error so it can be retained. When not possible, fall back to a
751 // non standard error.
752 rejectCode, found := extractRejectCode(e)
753 if !found {
754 rejectCode = wire.RejectNonstandard
755 }
756 str := fmt.Sprintf(
757 "transaction %v has a non-standard "+
758 "input: %v", txHash, e,
759 )
760 return nil, nil, txRuleError(rejectCode, str)
761 }
762 }
763 // NOTE: if you modify this code to accept non-standard transactions, you should add code here to check that the
764 // transaction does a reasonable number of ECDSA signature verifications. Don't allow transactions with an excessive
765 // number of signature operations which would result in making it impossible to mine. Since the coinbase address
766 // itself can contain signature operations, the maximum allowed signature operations per transaction is less than
767 // the maximum allowed signature operations per block. TODO(roasbeef): last bool should be conditional on segwit
768 // activation
769 var sigOpCost int
770 sigOpCost, e = blockchain.GetSigOpCost(tx, false, utxoView, true)
771 if e != nil {
772 if cErr, ok := e.(blockchain.RuleError); ok {
773 return nil, nil, chainRuleError(cErr)
774 }
775 return nil, nil, e
776 }
777 if sigOpCost > mp.cfg.Policy.MaxSigOpCostPerTx {
778 str := fmt.Sprintf(
779 "transaction %v sigop cost is too high: %d > %d",
780 txHash, sigOpCost, mp.cfg.Policy.MaxSigOpCostPerTx,
781 )
782 return nil, nil, txRuleError(wire.RejectNonstandard, str)
783 }
784 // Don't allow transactions with fees too low to get into a mined block. Most miners allow a free transaction area
785 // in blocks they mine to go alongside the area used for high-priority transactions as well as transactions with
786 // fees. A transaction size of up to 1000 bytes is considered safe to go into this section. Further, the minimum fee
787 // calculated below on its own would encourage several small transactions to avoid fees rather than one single
788 // larger transaction which is more desirable. Therefore as long as the size of the transaction does not exceed 1000
789 // less than the reserved space for high-priority transactions, don't require a fee for it.
790 serializedSize := GetTxVirtualSize(tx)
791 minFee := calcMinRequiredTxRelayFee(
792 serializedSize,
793 mp.cfg.Policy.MinRelayTxFee,
794 )
795 if serializedSize >= (constant.DefaultBlockPrioritySize-1000) && txFee < minFee {
796 str := fmt.Sprintf(
797 "transaction %v has %d fees which is under the required amount of %d",
798 txHash, txFee, minFee,
799 )
800 return nil, nil, txRuleError(wire.RejectInsufficientFee, str)
801 }
802 // Require that free transactions have sufficient priority to be mined in the next block. Transactions which are
803 // being added back to the memory pool from blocks that have been disconnected during a reorg are exempted.
804 if isNew && !mp.cfg.Policy.DisableRelayPriority && txFee < minFee {
805 currentPriority := mining.CalcPriority(
806 tx.MsgTx(), utxoView,
807 nextBlockHeight,
808 )
809 if currentPriority <= mining.MinHighPriority.ToDUO() {
810 str := fmt.Sprintf(
811 "transaction %v has insufficient "+
812 "priority (%v <= %v)", txHash,
813 currentPriority, mining.MinHighPriority,
814 )
815 return nil, nil, txRuleError(wire.RejectInsufficientFee, str)
816 }
817 }
818 // Free-to-relay transactions are rate limited here to prevent penny -flooding with tiny transactions as a form of
819 // attack.
820 if rateLimit && txFee < minFee {
821 nowUnix := time.Now().Unix()
822 // Decay passed data with an exponentially decaying ~10 minute window - matches bitcoind handling.
823 mp.pennyTotal *= math.Pow(
824 1.0-1.0/600.0,
825 float64(nowUnix-mp.lastPennyUnix),
826 )
827 mp.lastPennyUnix = nowUnix
828 // Are we still over the limit?
829 if mp.pennyTotal >= mp.cfg.Policy.FreeTxRelayLimit*10*1000 {
830 str := fmt.Sprintf(
831 "transaction %v has been rejected "+
832 "by the rate limiter due to low fees", txHash,
833 )
834 return nil, nil, txRuleError(wire.RejectInsufficientFee, str)
835 }
836 oldTotal := mp.pennyTotal
837 mp.pennyTotal += float64(serializedSize)
838 T.F(
839 "rate limit: curTotal %v, nextTotal: %v, limit %v",
840 oldTotal,
841 mp.pennyTotal,
842 mp.cfg.Policy.FreeTxRelayLimit*10*1000,
843 )
844 }
845 // Verify crypto signatures for each input and reject the transaction if any don't verify.
846 e = blockchain.ValidateTransactionScripts(
847 b, tx, utxoView,
848 txscript.StandardVerifyFlags, mp.cfg.SigCache,
849 mp.cfg.HashCache,
850 )
851 if e != nil {
852 if cErr, ok := e.(blockchain.RuleError); ok {
853 return nil, nil, chainRuleError(cErr)
854 }
855 return nil, nil, e
856 }
857 // Add to transaction pool.
858 txD := mp.addTransaction(utxoView, tx, bestHeight, txFee)
859 D.F(
860 "accepted transaction %v (pool size: %v) %s",
861 txHash,
862 len(mp.pool),
863 )
864 return nil, txD, nil
865 }
866 867 // maybeAddOrphan potentially adds an orphan to the orphan pool. This function MUST be called with the mempool lock held
868 // (for writes).
869 func (mp *TxPool) maybeAddOrphan(tx *util.Tx, tag Tag) (e error) {
870 // Ignore orphan transactions that are too large. This helps avoid a memory exhaustion attack based on sending a lot
871 // of really large orphans. In the case there is a valid transaction larger than this, it will ultimately be
872 // rebroadcast after the parent transactions have been mined or otherwise received. Note that the number of orphan
873 // transactions in the orphan pool is also limited, so this equates to a maximum memory used of mp.cfg.Policy.
874 // MaxOrphanTxSize * mp.cfg.Policy.MaxOrphanTxs ( which is ~5MB using the default values at the time this comment
875 // was written).
876 serializedLen := tx.MsgTx().SerializeSize()
877 if serializedLen > mp.cfg.Policy.MaxOrphanTxSize {
878 str := fmt.Sprintf(
879 "orphan transaction size of %d bytes is larger"+
880 " than max allowed size of %d bytes",
881 serializedLen, mp.cfg.Policy.MaxOrphanTxSize,
882 )
883 return txRuleError(wire.RejectNonstandard, str)
884 }
885 // Add the orphan if the none of the above disqualified it.
886 mp.addOrphan(tx, tag)
887 return nil
888 }
889 890 // processOrphans is the internal function which implements the public ProcessOrphans. See the comment for
891 // ProcessOrphans for more details. This function MUST be called with the mempool lock held (for writes).
892 func (mp *TxPool) processOrphans(b *blockchain.BlockChain, acceptedTx *util.Tx) []*TxDesc {
893 var acceptedTxns []*TxDesc
894 // Start with processing at least the passed transaction.
895 processList := list.New()
896 processList.PushBack(acceptedTx)
897 for processList.Len() > 0 {
898 // Pop the transaction to process from the front of the list.
899 firstElement := processList.Remove(processList.Front())
900 processItem := firstElement.(*util.Tx)
901 prevOut := wire.OutPoint{Hash: *processItem.Hash()}
902 for txOutIdx := range processItem.MsgTx().TxOut {
903 // Look up all orphans that redeem the output that is now available. This will typically only be one but it
904 // could be multiple if the orphan pool contains double spends. While it may seem odd that the orphan pool
905 // would allow this since there can only possibly ultimately be a single redeemer, it's important to track
906 // it this way to prevent malicious actors from being able to purposely constructing orphans that would
907 // otherwise make outputs unspendable. Skip to the next available output if there are none.
908 prevOut.Index = uint32(txOutIdx)
909 orphans, exists := mp.orphansByPrev[prevOut]
910 if !exists {
911 continue
912 }
913 // Potentially accept an orphan into the tx pool.
914 for _, tx := range orphans {
915 missing, txD, e := mp.maybeAcceptTransaction(
916 b, tx, true, true, false,
917 )
918 if e != nil {
919 // The orphan is now invalid so there is no way any other orphans which redeem any of its outputs
920 // can be accepted. Remove them.
921 mp.removeOrphan(tx, true)
922 break
923 }
924 // Transaction is still an orphan. Try the next orphan which redeems this output.
925 if len(missing) > 0 {
926 continue
927 }
928 // Transaction was accepted into the main pool. Add it to the list of accepted transactions that are no
929 // longer orphans, remove it from the orphan pool, and add it to the list of transactions to process so
930 // any orphans that depend on it are handled too.
931 acceptedTxns = append(acceptedTxns, txD)
932 mp.removeOrphan(tx, false)
933 processList.PushBack(tx)
934 // Only one transaction for this outpoint can be accepted, so the rest are now double spends and are
935 // removed later.
936 break
937 }
938 }
939 }
940 // Recursively remove any orphans that also redeem any outputs redeemed by the accepted transactions since those are
941 // now definitive double spends.
942 mp.removeOrphanDoubleSpends(acceptedTx)
943 for _, txD := range acceptedTxns {
944 mp.removeOrphanDoubleSpends(txD.Tx)
945 }
946 return acceptedTxns
947 }
948 949 // removeOrphan is the internal function which implements the public RemoveOrphan. See the comment for RemoveOrphan for
950 // more details. This function MUST be called with the mempool lock held (for writes).
951 func (mp *TxPool) removeOrphan(tx *util.Tx, removeRedeemers bool) {
952 // Nothing to do if passed tx is not an orphan.
953 txHash := tx.Hash()
954 otx, exists := mp.orphans[*txHash]
955 if !exists {
956 return
957 }
958 // Remove the reference from the previous orphan index.
959 for _, txIn := range otx.tx.MsgTx().TxIn {
960 orphans, exists := mp.orphansByPrev[txIn.PreviousOutPoint]
961 if exists {
962 delete(orphans, *txHash)
963 // Remove the map entry altogether if there are no longer any orphans which depend on it.
964 if len(orphans) == 0 {
965 delete(mp.orphansByPrev, txIn.PreviousOutPoint)
966 }
967 }
968 }
969 // Remove any orphans that redeem outputs from this one if requested.
970 if removeRedeemers {
971 prevOut := wire.OutPoint{Hash: *txHash}
972 for txOutIdx := range tx.MsgTx().TxOut {
973 prevOut.Index = uint32(txOutIdx)
974 for _, orphan := range mp.orphansByPrev[prevOut] {
975 mp.removeOrphan(orphan, true)
976 }
977 }
978 }
979 // Remove the transaction from the orphan pool.
980 delete(mp.orphans, *txHash)
981 }
982 983 // removeOrphanDoubleSpends removes all orphans which spend outputs spent by the passed transaction from the orphan
984 // pool. Removing those orphans then leads to removing all orphans which rely on them, recursively. This is necessary
985 // when a transaction is added to the main pool because it may spend outputs orphans also spend. This function MUST be
986 // called with the mempool lock held (for writes).
987 func (mp *TxPool) removeOrphanDoubleSpends(tx *util.Tx) {
988 msgTx := tx.MsgTx()
989 for _, txIn := range msgTx.TxIn {
990 for _, orphan := range mp.orphansByPrev[txIn.PreviousOutPoint] {
991 mp.removeOrphan(orphan, true)
992 }
993 }
994 }
995 996 // removeTransaction is the internal function which implements the public RemoveTransaction. See the comment for
997 // RemoveTransaction for more details. This function MUST be called with the mempool lock held (for writes).
998 func (mp *TxPool) removeTransaction(tx *util.Tx, removeRedeemers bool) {
999 txHash := tx.Hash()
1000 if removeRedeemers {
1001 // Remove any transactions which rely on this one.
1002 for i := uint32(0); i < uint32(len(tx.MsgTx().TxOut)); i++ {
1003 prevOut := wire.OutPoint{Hash: *txHash, Index: i}
1004 if txRedeemer, exists := mp.outpoints[prevOut]; exists {
1005 mp.removeTransaction(txRedeemer, true)
1006 }
1007 }
1008 }
1009 // Remove the transaction if needed.
1010 if txDesc, exists := mp.pool[*txHash]; exists {
1011 // Remove unconfirmed address index entries associated with the transaction if enabled.
1012 if mp.cfg.AddrIndex != nil {
1013 mp.cfg.AddrIndex.RemoveUnconfirmedTx(txHash)
1014 }
1015 // Mark the referenced outpoints as unspent by the pool.
1016 for _, txIn := range txDesc.Tx.MsgTx().TxIn {
1017 delete(mp.outpoints, txIn.PreviousOutPoint)
1018 }
1019 delete(mp.pool, *txHash)
1020 atomic.StoreInt64(&mp.lastUpdated, time.Now().Unix())
1021 if mp.updateHook != nil {
1022 mp.updateHook()
1023 }
1024 }
1025 }
1026 1027 // New returns a new memory pool for validating and storing standalone transactions until they are mined into a block.
1028 func New(cfg *Config) *TxPool {
1029 return &TxPool{
1030 cfg: *cfg,
1031 pool: make(map[chainhash.Hash]*TxDesc),
1032 orphans: make(map[chainhash.Hash]*orphanTx),
1033 orphansByPrev: make(map[wire.OutPoint]map[chainhash.Hash]*util.Tx),
1034 nextExpireScan: time.Now().Add(orphanExpireScanInterval),
1035 outpoints: make(map[wire.OutPoint]*util.Tx),
1036 updateHook: cfg.UpdateHook,
1037 }
1038 }
1039