Source: mempool/mempool.js

  1. /*!
  2. * mempool.js - mempool for bcoin
  3. * Copyright (c) 2014-2017, Christopher Jeffrey (MIT License).
  4. * https://github.com/bcoin-org/bcoin
  5. */
  6. 'use strict';
  7. const assert = require('bsert');
  8. const path = require('path');
  9. const EventEmitter = require('events');
  10. const bdb = require('bdb');
  11. const {RollingFilter} = require('bfilter');
  12. const Heap = require('bheep');
  13. const {BufferMap, BufferSet} = require('buffer-map');
  14. const common = require('../blockchain/common');
  15. const consensus = require('../protocol/consensus');
  16. const policy = require('../protocol/policy');
  17. const util = require('../utils/util');
  18. const random = require('bcrypto/lib/random');
  19. const {VerifyError} = require('../protocol/errors');
  20. const Script = require('../script/script');
  21. const Outpoint = require('../primitives/outpoint');
  22. const TX = require('../primitives/tx');
  23. const Coin = require('../primitives/coin');
  24. const TXMeta = require('../primitives/txmeta');
  25. const MempoolEntry = require('./mempoolentry');
  26. const Network = require('../protocol/network');
  27. const layout = require('./layout');
  28. const AddrIndexer = require('./addrindexer');
  29. const Fees = require('./fees');
  30. const CoinView = require('../coins/coinview');
  31. /**
  32. * Mempool
  33. * Represents a mempool.
  34. * @extends EventEmitter
  35. * @alias module:mempool.Mempool
  36. */
  37. class Mempool extends EventEmitter {
  38. /**
  39. * Create a mempool.
  40. * @constructor
  41. * @param {Object} options
  42. */
  43. constructor(options) {
  44. super();
  45. this.opened = false;
  46. this.options = new MempoolOptions(options);
  47. this.network = this.options.network;
  48. this.logger = this.options.logger.context('mempool');
  49. this.workers = this.options.workers;
  50. this.chain = this.options.chain;
  51. this.fees = this.options.fees;
  52. this.locker = this.chain.locker;
  53. this.cache = new MempoolCache(this.options);
  54. this.size = 0;
  55. this.freeCount = 0;
  56. this.lastTime = 0;
  57. this.lastFlush = 0;
  58. this.tip = this.network.genesis.hash;
  59. this.waiting = new BufferMap();
  60. this.orphans = new BufferMap();
  61. this.map = new BufferMap();
  62. this.spents = new BufferMap();
  63. this.rejects = new RollingFilter(120000, 0.000001);
  64. this.addrindex = new AddrIndexer(this.network);
  65. }
  66. /**
  67. * Open the chain, wait for the database to load.
  68. * @returns {Promise}
  69. */
  70. async open() {
  71. assert(!this.opened, 'Mempool is already open.');
  72. this.opened = true;
  73. await this.cache.open();
  74. if (this.options.persistent) {
  75. const entries = await this.cache.getEntries();
  76. for (const entry of entries)
  77. this.trackEntry(entry);
  78. for (const entry of entries) {
  79. this.updateAncestors(entry, addFee);
  80. if (this.options.indexAddress) {
  81. const view = await this.getCoinView(entry.tx);
  82. this.indexEntry(entry, view);
  83. }
  84. }
  85. this.logger.info(
  86. 'Loaded mempool from disk (%d entries).',
  87. entries.length);
  88. if (this.fees) {
  89. const fees = await this.cache.getFees();
  90. if (fees) {
  91. this.fees.inject(fees);
  92. this.logger.info(
  93. 'Loaded mempool fee data (rate=%d).',
  94. this.fees.estimateFee());
  95. }
  96. }
  97. }
  98. this.tip = this.chain.tip.hash;
  99. const size = (this.options.maxSize / 1024).toFixed(2);
  100. this.logger.info('Mempool loaded (maxsize=%dkb).', size);
  101. }
  102. /**
  103. * Close the chain, wait for the database to close.
  104. * @returns {Promise}
  105. */
  106. async close() {
  107. assert(this.opened, 'Mempool is not open.');
  108. this.opened = false;
  109. return this.cache.close();
  110. }
  111. /**
  112. * Notify the mempool that a new block has come
  113. * in (removes all transactions contained in the
  114. * block from the mempool).
  115. * @method
  116. * @param {ChainEntry} block
  117. * @param {TX[]} txs
  118. * @returns {Promise}
  119. */
  120. async addBlock(block, txs) {
  121. const unlock = await this.locker.lock();
  122. try {
  123. return await this._addBlock(block, txs);
  124. } finally {
  125. unlock();
  126. }
  127. }
  128. /**
  129. * Notify the mempool that a new block
  130. * has come without a lock.
  131. * @private
  132. * @param {ChainEntry} block
  133. * @param {TX[]} txs
  134. * @returns {Promise}
  135. */
  136. async _addBlock(block, txs) {
  137. if (this.map.size === 0) {
  138. this.tip = block.hash;
  139. return;
  140. }
  141. const entries = [];
  142. for (let i = txs.length - 1; i >= 1; i--) {
  143. const tx = txs[i];
  144. const hash = tx.hash();
  145. const entry = this.getEntry(hash);
  146. if (!entry) {
  147. this.removeOrphan(hash);
  148. this.removeDoubleSpends(tx);
  149. if (this.waiting.has(hash))
  150. await this.handleOrphans(tx);
  151. continue;
  152. }
  153. this.removeEntry(entry);
  154. this.emit('confirmed', tx, block);
  155. entries.push(entry);
  156. }
  157. // We need to reset the rejects filter periodically.
  158. // There may be a locktime in a TX that is now valid.
  159. this.rejects.reset();
  160. if (this.fees) {
  161. this.fees.processBlock(block.height, entries, this.chain.synced);
  162. this.cache.writeFees(this.fees);
  163. }
  164. this.cache.sync(block.hash);
  165. await this.cache.flush();
  166. this.tip = block.hash;
  167. if (entries.length === 0)
  168. return;
  169. this.logger.debug(
  170. 'Removed %d txs from mempool for block %d.',
  171. entries.length, block.height);
  172. }
  173. /**
  174. * Notify the mempool that a block has been disconnected
  175. * from the main chain (reinserts transactions into the mempool).
  176. * @method
  177. * @param {ChainEntry} block
  178. * @param {TX[]} txs
  179. * @returns {Promise}
  180. */
  181. async removeBlock(block, txs) {
  182. const unlock = await this.locker.lock();
  183. try {
  184. return await this._removeBlock(block, txs);
  185. } finally {
  186. unlock();
  187. }
  188. }
  189. /**
  190. * Notify the mempool that a block
  191. * has been disconnected without a lock.
  192. * @method
  193. * @private
  194. * @param {ChainEntry} block
  195. * @param {TX[]} txs
  196. * @returns {Promise}
  197. */
  198. async _removeBlock(block, txs) {
  199. if (this.map.size === 0) {
  200. this.tip = block.prevBlock;
  201. return;
  202. }
  203. let total = 0;
  204. for (let i = 1; i < txs.length; i++) {
  205. const tx = txs[i];
  206. const hash = tx.hash();
  207. if (this.hasEntry(hash))
  208. continue;
  209. try {
  210. await this.insertTX(tx, -1);
  211. total++;
  212. } catch (e) {
  213. this.emit('error', e);
  214. continue;
  215. }
  216. this.emit('unconfirmed', tx, block);
  217. }
  218. this.rejects.reset();
  219. this.cache.sync(block.prevBlock);
  220. await this.cache.flush();
  221. this.tip = block.prevBlock;
  222. if (total === 0)
  223. return;
  224. this.logger.debug(
  225. 'Added %d txs back into the mempool for block %d.',
  226. total, block.height);
  227. }
  228. /**
  229. * Sanitize the mempool after a reorg.
  230. * @private
  231. * @returns {Promise}
  232. */
  233. async _handleReorg() {
  234. const height = this.chain.height + 1;
  235. const mtp = await this.chain.getMedianTime(this.chain.tip);
  236. const remove = [];
  237. for (const [hash, entry] of this.map) {
  238. const {tx} = entry;
  239. if (!tx.isFinal(height, mtp)) {
  240. remove.push(hash);
  241. continue;
  242. }
  243. if (tx.version > 1) {
  244. let hasLocks = false;
  245. for (const {sequence} of tx.inputs) {
  246. if (!(sequence & consensus.SEQUENCE_DISABLE_FLAG)) {
  247. hasLocks = true;
  248. break;
  249. }
  250. }
  251. if (hasLocks) {
  252. remove.push(hash);
  253. continue;
  254. }
  255. }
  256. if (entry.coinbase)
  257. remove.push(hash);
  258. }
  259. for (const hash of remove) {
  260. const entry = this.getEntry(hash);
  261. if (!entry)
  262. continue;
  263. this.evictEntry(entry);
  264. }
  265. }
  266. /**
  267. * Reset the mempool.
  268. * @method
  269. * @returns {Promise}
  270. */
  271. async reset() {
  272. const unlock = await this.locker.lock();
  273. try {
  274. return await this._reset();
  275. } finally {
  276. unlock();
  277. }
  278. }
  279. /**
  280. * Reset the mempool without a lock.
  281. * @private
  282. */
  283. async _reset() {
  284. this.logger.info('Mempool reset (%d txs removed).', this.map.size);
  285. this.size = 0;
  286. this.waiting.clear();
  287. this.orphans.clear();
  288. this.map.clear();
  289. this.spents.clear();
  290. this.addrindex.reset();
  291. this.freeCount = 0;
  292. this.lastTime = 0;
  293. if (this.fees)
  294. this.fees.reset();
  295. this.rejects.reset();
  296. if (this.options.persistent) {
  297. await this.cache.wipe();
  298. this.cache.clear();
  299. }
  300. this.tip = this.chain.tip.hash;
  301. }
  302. /**
  303. * Ensure the size of the mempool stays below `maxSize`.
  304. * Evicts entries by timestamp and cumulative fee rate.
  305. * @param {MempoolEntry} added
  306. * @returns {Promise}
  307. */
  308. limitSize(added) {
  309. const maxSize = this.options.maxSize;
  310. if (this.size <= maxSize)
  311. return false;
  312. const threshold = maxSize - (maxSize / 10);
  313. const expiryTime = this.options.expiryTime;
  314. const now = util.now();
  315. let start = util.bench();
  316. const queue = new Heap(cmpRate);
  317. for (const entry of this.map.values()) {
  318. if (this.hasDepends(entry.tx))
  319. continue;
  320. if (now < entry.time + expiryTime) {
  321. queue.insert(entry);
  322. continue;
  323. }
  324. this.logger.debug(
  325. 'Removing package %h from mempool (too old).',
  326. entry.hash());
  327. this.evictEntry(entry);
  328. }
  329. if (this.size <= threshold)
  330. return !this.hasEntry(added);
  331. this.logger.debug(
  332. '(bench) Heap mempool traversal: %d.',
  333. util.bench(start));
  334. start = util.bench();
  335. this.logger.debug(
  336. '(bench) Heap mempool queue size: %d.',
  337. queue.size());
  338. while (queue.size() > 0) {
  339. const entry = queue.shift();
  340. const hash = entry.hash();
  341. assert(this.hasEntry(hash));
  342. this.logger.debug(
  343. 'Removing package %h from mempool (low fee).',
  344. entry.hash());
  345. this.evictEntry(entry);
  346. if (this.size <= threshold)
  347. break;
  348. }
  349. this.logger.debug(
  350. '(bench) Heap mempool map removal: %d.',
  351. util.bench(start));
  352. return !this.hasEntry(added);
  353. }
  354. /**
  355. * Retrieve a transaction from the mempool.
  356. * @param {Hash} hash
  357. * @returns {TX}
  358. */
  359. getTX(hash) {
  360. const entry = this.map.get(hash);
  361. if (!entry)
  362. return null;
  363. return entry.tx;
  364. }
  365. /**
  366. * Retrieve a transaction from the mempool.
  367. * @param {Hash} hash
  368. * @returns {MempoolEntry}
  369. */
  370. getEntry(hash) {
  371. return this.map.get(hash);
  372. }
  373. /**
  374. * Retrieve a coin from the mempool (unspents only).
  375. * @param {Hash} hash
  376. * @param {Number} index
  377. * @returns {Coin}
  378. */
  379. getCoin(hash, index) {
  380. const entry = this.map.get(hash);
  381. if (!entry)
  382. return null;
  383. if (this.isSpent(hash, index))
  384. return null;
  385. if (index >= entry.tx.outputs.length)
  386. return null;
  387. return Coin.fromTX(entry.tx, index, -1);
  388. }
  389. /**
  390. * Check whether coin is still unspent.
  391. * @param {Hash} hash
  392. * @param {Number} index
  393. * @returns {boolean}
  394. */
  395. hasCoin(hash, index) {
  396. const entry = this.map.get(hash);
  397. if (!entry)
  398. return false;
  399. if (this.isSpent(hash, index))
  400. return false;
  401. if (index >= entry.tx.outputs.length)
  402. return false;
  403. return true;
  404. }
  405. /**
  406. * Check to see if a coin has been spent. This differs from
  407. * {@link ChainDB#isSpent} in that it actually maintains a
  408. * map of spent coins, whereas ChainDB may return `true`
  409. * for transaction outputs that never existed.
  410. * @param {Hash} hash
  411. * @param {Number} index
  412. * @returns {Boolean}
  413. */
  414. isSpent(hash, index) {
  415. const key = Outpoint.toKey(hash, index);
  416. return this.spents.has(key);
  417. }
  418. /**
  419. * Get an output's spender entry.
  420. * @param {Hash} hash
  421. * @param {Number} index
  422. * @returns {MempoolEntry}
  423. */
  424. getSpent(hash, index) {
  425. const key = Outpoint.toKey(hash, index);
  426. return this.spents.get(key);
  427. }
  428. /**
  429. * Get an output's spender transaction.
  430. * @param {Hash} hash
  431. * @param {Number} index
  432. * @returns {MempoolEntry}
  433. */
  434. getSpentTX(hash, index) {
  435. const key = Outpoint.toKey(hash, index);
  436. const entry = this.spents.get(key);
  437. if (!entry)
  438. return null;
  439. return entry.tx;
  440. }
  441. /**
  442. * Find all transactions pertaining to a certain address.
  443. * @param {Address} addr
  444. * @param {Object} options
  445. * @param {Number} options.limit
  446. * @param {Number} options.reverse
  447. * @param {Buffer} options.after
  448. * @returns {TX[]}
  449. */
  450. getTXByAddress(addr, options) {
  451. return this.addrindex.get(addr, options);
  452. }
  453. /**
  454. * Find all transactions pertaining to a certain address.
  455. * @param {Address} addr
  456. * @param {Object} options
  457. * @param {Number} options.limit
  458. * @param {Number} options.reverse
  459. * @param {Buffer} options.after
  460. * @returns {TXMeta[]}
  461. */
  462. getMetaByAddress(addr, options) {
  463. return this.addrindex.getMeta(addr, options);
  464. }
  465. /**
  466. * Retrieve a transaction from the mempool.
  467. * @param {Hash} hash
  468. * @returns {TXMeta}
  469. */
  470. getMeta(hash) {
  471. const entry = this.getEntry(hash);
  472. if (!entry)
  473. return null;
  474. const meta = TXMeta.fromTX(entry.tx);
  475. meta.mtime = entry.time;
  476. return meta;
  477. }
  478. /**
  479. * Test the mempool to see if it contains a transaction.
  480. * @param {Hash} hash
  481. * @returns {Boolean}
  482. */
  483. hasEntry(hash) {
  484. return this.map.has(hash);
  485. }
  486. /**
  487. * Test the mempool to see if it
  488. * contains a transaction or an orphan.
  489. * @param {Hash} hash
  490. * @returns {Boolean}
  491. */
  492. has(hash) {
  493. if (this.locker.has(hash))
  494. return true;
  495. if (this.hasOrphan(hash))
  496. return true;
  497. return this.hasEntry(hash);
  498. }
  499. /**
  500. * Test the mempool to see if it
  501. * contains a transaction or an orphan.
  502. * @private
  503. * @param {Hash} hash
  504. * @returns {Boolean}
  505. */
  506. exists(hash) {
  507. if (this.locker.pending(hash))
  508. return true;
  509. if (this.hasOrphan(hash))
  510. return true;
  511. return this.hasEntry(hash);
  512. }
  513. /**
  514. * Test the mempool to see if it
  515. * contains a recent reject.
  516. * @param {Hash} hash
  517. * @returns {Boolean}
  518. */
  519. hasReject(hash) {
  520. return this.rejects.test(hash);
  521. }
  522. /**
  523. * Add a transaction to the mempool. Note that this
  524. * will lock the mempool until the transaction is
  525. * fully processed.
  526. * @method
  527. * @param {TX} tx
  528. * @param {Number?} id
  529. * @returns {Promise}
  530. */
  531. async addTX(tx, id) {
  532. const hash = tx.hash();
  533. const unlock = await this.locker.lock(hash);
  534. try {
  535. return await this._addTX(tx, id);
  536. } finally {
  537. unlock();
  538. }
  539. }
  540. /**
  541. * Add a transaction to the mempool without a lock.
  542. * @method
  543. * @private
  544. * @param {TX} tx
  545. * @param {Number?} id
  546. * @returns {Promise}
  547. */
  548. async _addTX(tx, id) {
  549. if (id == null)
  550. id = -1;
  551. let missing;
  552. try {
  553. missing = await this.insertTX(tx, id);
  554. } catch (err) {
  555. if (err.type === 'VerifyError') {
  556. if (!tx.hasWitness() && !err.malleated)
  557. this.rejects.add(tx.hash());
  558. }
  559. throw err;
  560. }
  561. if (util.now() - this.lastFlush > 10) {
  562. await this.cache.flush();
  563. this.lastFlush = util.now();
  564. }
  565. return missing;
  566. }
  567. /**
  568. * Add a transaction to the mempool without a lock.
  569. * @method
  570. * @private
  571. * @param {TX} tx
  572. * @param {Number?} id
  573. * @returns {Promise}
  574. */
  575. async insertTX(tx, id) {
  576. assert(!tx.mutable, 'Cannot add mutable TX to mempool.');
  577. const lockFlags = common.lockFlags.STANDARD_LOCKTIME_FLAGS;
  578. const height = this.chain.height;
  579. const hash = tx.hash();
  580. // Basic sanity checks.
  581. // This is important because it ensures
  582. // other functions will be overflow safe.
  583. const [valid, reason, score] = tx.checkSanity();
  584. if (!valid)
  585. throw new VerifyError(tx, 'invalid', reason, score);
  586. // Coinbases are an insta-ban.
  587. // Why? Who knows.
  588. if (tx.isCoinbase()) {
  589. throw new VerifyError(tx,
  590. 'invalid',
  591. 'coinbase',
  592. 100);
  593. }
  594. // Do not allow CSV until it's activated.
  595. if (this.options.requireStandard) {
  596. if (!this.chain.state.hasCSV() && tx.version >= 2) {
  597. throw new VerifyError(tx,
  598. 'nonstandard',
  599. 'premature-version2-tx',
  600. 0);
  601. }
  602. }
  603. // Do not allow segwit until it's activated.
  604. if (!this.chain.state.hasWitness() && !this.options.prematureWitness) {
  605. if (tx.hasWitness()) {
  606. throw new VerifyError(tx,
  607. 'nonstandard',
  608. 'no-witness-yet',
  609. 0,
  610. true);
  611. }
  612. }
  613. // Non-contextual standardness checks.
  614. if (this.options.requireStandard) {
  615. const [valid, reason, score] = tx.checkStandard();
  616. if (!valid)
  617. throw new VerifyError(tx, 'nonstandard', reason, score);
  618. if (!this.options.replaceByFee) {
  619. if (tx.isRBF()) {
  620. throw new VerifyError(tx,
  621. 'nonstandard',
  622. 'replace-by-fee',
  623. 0);
  624. }
  625. }
  626. }
  627. // Verify transaction finality (see isFinal()).
  628. if (!await this.verifyFinal(tx, lockFlags)) {
  629. throw new VerifyError(tx,
  630. 'nonstandard',
  631. 'non-final',
  632. 0);
  633. }
  634. // We can maybe ignore this.
  635. if (this.exists(hash)) {
  636. throw new VerifyError(tx,
  637. 'alreadyknown',
  638. 'txn-already-in-mempool',
  639. 0);
  640. }
  641. // We can test whether this is an
  642. // non-fully-spent transaction on
  643. // the chain.
  644. if (await this.chain.hasCoins(tx)) {
  645. throw new VerifyError(tx,
  646. 'alreadyknown',
  647. 'txn-already-known',
  648. 0);
  649. }
  650. // Quick and dirty test to verify we're
  651. // not double-spending an output in the
  652. // mempool.
  653. if (this.isDoubleSpend(tx)) {
  654. this.emit('conflict', tx);
  655. throw new VerifyError(tx,
  656. 'duplicate',
  657. 'bad-txns-inputs-spent',
  658. 0);
  659. }
  660. // Get coin viewpoint as it
  661. // pertains to the mempool.
  662. const view = await this.getCoinView(tx);
  663. // Maybe store as an orphan.
  664. const missing = this.maybeOrphan(tx, view, id);
  665. // Return missing outpoint hashes.
  666. if (missing)
  667. return missing;
  668. // Create a new mempool entry
  669. // at current chain height.
  670. const entry = MempoolEntry.fromTX(tx, view, height);
  671. // Contextual verification.
  672. await this.verify(entry, view);
  673. // Add and index the entry.
  674. await this.addEntry(entry, view);
  675. // Trim size if we're too big.
  676. if (this.limitSize(hash)) {
  677. throw new VerifyError(tx,
  678. 'insufficientfee',
  679. 'mempool full',
  680. 0);
  681. }
  682. return null;
  683. }
  684. /**
  685. * Verify a transaction with mempool standards.
  686. * @method
  687. * @param {TX} tx
  688. * @param {CoinView} view
  689. * @returns {Promise}
  690. */
  691. async verify(entry, view) {
  692. const height = this.chain.height + 1;
  693. const lockFlags = common.lockFlags.STANDARD_LOCKTIME_FLAGS;
  694. const tx = entry.tx;
  695. // Verify sequence locks.
  696. if (!await this.verifyLocks(tx, view, lockFlags)) {
  697. throw new VerifyError(tx,
  698. 'nonstandard',
  699. 'non-BIP68-final',
  700. 0);
  701. }
  702. // Check input an witness standardness.
  703. if (this.options.requireStandard) {
  704. if (!tx.hasStandardInputs(view)) {
  705. throw new VerifyError(tx,
  706. 'nonstandard',
  707. 'bad-txns-nonstandard-inputs',
  708. 0);
  709. }
  710. if (this.chain.state.hasWitness()) {
  711. if (!tx.hasStandardWitness(view)) {
  712. throw new VerifyError(tx,
  713. 'nonstandard',
  714. 'bad-witness-nonstandard',
  715. 0,
  716. true);
  717. }
  718. }
  719. }
  720. // Annoying process known as sigops counting.
  721. if (entry.sigops > policy.MAX_TX_SIGOPS_COST) {
  722. throw new VerifyError(tx,
  723. 'nonstandard',
  724. 'bad-txns-too-many-sigops',
  725. 0);
  726. }
  727. // Make sure this guy gave a decent fee.
  728. const minFee = policy.getMinFee(entry.size, this.options.minRelay);
  729. if (this.options.relayPriority && entry.fee < minFee) {
  730. if (!entry.isFree(height)) {
  731. throw new VerifyError(tx,
  732. 'insufficientfee',
  733. 'insufficient priority',
  734. 0);
  735. }
  736. }
  737. // Continuously rate-limit free (really, very-low-fee)
  738. // transactions. This mitigates 'penny-flooding'.
  739. if (this.options.limitFree && entry.fee < minFee) {
  740. const now = util.now();
  741. // Use an exponentially decaying ~10-minute window.
  742. this.freeCount *= Math.pow(1 - 1 / 600, now - this.lastTime);
  743. this.lastTime = now;
  744. // The limitFreeRelay unit is thousand-bytes-per-minute
  745. // At default rate it would take over a month to fill 1GB.
  746. if (this.freeCount > this.options.limitFreeRelay * 10 * 1000) {
  747. throw new VerifyError(tx,
  748. 'insufficientfee',
  749. 'rate limited free transaction',
  750. 0);
  751. }
  752. this.freeCount += entry.size;
  753. }
  754. // Important safety feature.
  755. if (this.options.rejectAbsurdFees && entry.fee > minFee * 10000)
  756. throw new VerifyError(tx, 'highfee', 'absurdly-high-fee', 0);
  757. // Why do we have this here? Nested transactions are cool.
  758. if (this.countAncestors(entry) + 1 > this.options.maxAncestors) {
  759. throw new VerifyError(tx,
  760. 'nonstandard',
  761. 'too-long-mempool-chain',
  762. 0);
  763. }
  764. // Contextual sanity checks.
  765. const [fee, reason, score] = tx.checkInputs(view, height);
  766. if (fee === -1)
  767. throw new VerifyError(tx, 'invalid', reason, score);
  768. // Script verification.
  769. let flags = Script.flags.STANDARD_VERIFY_FLAGS;
  770. try {
  771. await this.verifyInputs(tx, view, flags);
  772. } catch (err) {
  773. if (tx.hasWitness())
  774. throw err;
  775. // Try without segwit and cleanstack.
  776. flags &= ~Script.flags.VERIFY_WITNESS;
  777. flags &= ~Script.flags.VERIFY_CLEANSTACK;
  778. // If it failed, the first verification
  779. // was the only result we needed.
  780. if (!await this.verifyResult(tx, view, flags))
  781. throw err;
  782. // If it succeeded, segwit may be causing the
  783. // failure. Try with segwit but without cleanstack.
  784. flags |= Script.flags.VERIFY_WITNESS;
  785. // Cleanstack was causing the failure.
  786. if (await this.verifyResult(tx, view, flags))
  787. throw err;
  788. // Do not insert into reject cache.
  789. err.malleated = true;
  790. throw err;
  791. }
  792. // Paranoid checks.
  793. if (this.options.paranoidChecks) {
  794. const flags = Script.flags.MANDATORY_VERIFY_FLAGS;
  795. assert(await this.verifyResult(tx, view, flags),
  796. 'BUG: Verify failed for mandatory but not standard.');
  797. }
  798. }
  799. /**
  800. * Verify inputs, return a boolean
  801. * instead of an error based on success.
  802. * @method
  803. * @param {TX} tx
  804. * @param {CoinView} view
  805. * @param {VerifyFlags} flags
  806. * @returns {Promise}
  807. */
  808. async verifyResult(tx, view, flags) {
  809. try {
  810. await this.verifyInputs(tx, view, flags);
  811. } catch (err) {
  812. if (err.type === 'VerifyError')
  813. return false;
  814. throw err;
  815. }
  816. return true;
  817. }
  818. /**
  819. * Verify inputs for standard
  820. * _and_ mandatory flags on failure.
  821. * @method
  822. * @param {TX} tx
  823. * @param {CoinView} view
  824. * @param {VerifyFlags} flags
  825. * @returns {Promise}
  826. */
  827. async verifyInputs(tx, view, flags) {
  828. if (await tx.verifyAsync(view, flags, this.workers))
  829. return;
  830. if (flags & Script.flags.ONLY_STANDARD_VERIFY_FLAGS) {
  831. flags &= ~Script.flags.ONLY_STANDARD_VERIFY_FLAGS;
  832. if (await tx.verifyAsync(view, flags, this.workers)) {
  833. throw new VerifyError(tx,
  834. 'nonstandard',
  835. 'non-mandatory-script-verify-flag',
  836. 0);
  837. }
  838. }
  839. throw new VerifyError(tx,
  840. 'nonstandard',
  841. 'mandatory-script-verify-flag',
  842. 100);
  843. }
  844. /**
  845. * Add a transaction to the mempool without performing any
  846. * validation. Note that this method does not lock the mempool
  847. * and may lend itself to race conditions if used unwisely.
  848. * This function will also resolve orphans if possible (the
  849. * resolved orphans _will_ be validated).
  850. * @method
  851. * @param {MempoolEntry} entry
  852. * @param {CoinView} view
  853. * @returns {Promise}
  854. */
  855. async addEntry(entry, view) {
  856. const tx = entry.tx;
  857. this.trackEntry(entry, view);
  858. this.updateAncestors(entry, addFee);
  859. this.emit('tx', tx, view);
  860. this.emit('add entry', entry);
  861. if (this.fees)
  862. this.fees.processTX(entry, this.chain.synced);
  863. this.logger.debug(
  864. 'Added %h to mempool (txs=%d).',
  865. tx.hash(), this.map.size);
  866. this.cache.save(entry);
  867. await this.handleOrphans(tx);
  868. }
  869. /**
  870. * Remove a transaction from the mempool.
  871. * Generally only called when a new block
  872. * is added to the main chain.
  873. * @param {MempoolEntry} entry
  874. */
  875. removeEntry(entry) {
  876. const tx = entry.tx;
  877. const hash = tx.hash();
  878. this.untrackEntry(entry);
  879. if (this.fees)
  880. this.fees.removeTX(hash);
  881. this.cache.remove(hash);
  882. this.emit('remove entry', entry);
  883. }
  884. /**
  885. * Remove a transaction from the mempool.
  886. * Recursively remove its spenders.
  887. * @param {MempoolEntry} entry
  888. */
  889. evictEntry(entry) {
  890. this.removeSpenders(entry);
  891. this.updateAncestors(entry, removeFee);
  892. this.removeEntry(entry);
  893. }
  894. /**
  895. * Recursively remove spenders of a transaction.
  896. * @private
  897. * @param {MempoolEntry} entry
  898. */
  899. removeSpenders(entry) {
  900. const tx = entry.tx;
  901. const hash = tx.hash();
  902. for (let i = 0; i < tx.outputs.length; i++) {
  903. const spender = this.getSpent(hash, i);
  904. if (!spender)
  905. continue;
  906. this.removeSpenders(spender);
  907. this.removeEntry(spender);
  908. }
  909. }
  910. /**
  911. * Count the highest number of
  912. * ancestors a transaction may have.
  913. * @param {MempoolEntry} entry
  914. * @returns {Number}
  915. */
  916. countAncestors(entry) {
  917. return this._countAncestors(entry, new BufferSet(), entry, nop);
  918. }
  919. /**
  920. * Count the highest number of
  921. * ancestors a transaction may have.
  922. * Update descendant fees and size.
  923. * @param {MempoolEntry} entry
  924. * @param {Function} map
  925. * @returns {Number}
  926. */
  927. updateAncestors(entry, map) {
  928. return this._countAncestors(entry, new BufferSet(), entry, map);
  929. }
  930. /**
  931. * Traverse ancestors and count.
  932. * @private
  933. * @param {MempoolEntry} entry
  934. * @param {Object} set
  935. * @param {MempoolEntry} child
  936. * @param {Function} map
  937. * @returns {Number}
  938. */
  939. _countAncestors(entry, set, child, map) {
  940. const tx = entry.tx;
  941. for (const {prevout} of tx.inputs) {
  942. const hash = prevout.hash;
  943. const parent = this.getEntry(hash);
  944. if (!parent)
  945. continue;
  946. if (set.has(hash))
  947. continue;
  948. set.add(hash);
  949. map(parent, child);
  950. if (set.size > this.options.maxAncestors)
  951. break;
  952. this._countAncestors(parent, set, child, map);
  953. if (set.size > this.options.maxAncestors)
  954. break;
  955. }
  956. return set.size;
  957. }
  958. /**
  959. * Count the highest number of
  960. * descendants a transaction may have.
  961. * @param {MempoolEntry} entry
  962. * @returns {Number}
  963. */
  964. countDescendants(entry) {
  965. return this._countDescendants(entry, new BufferSet());
  966. }
  967. /**
  968. * Count the highest number of
  969. * descendants a transaction may have.
  970. * @private
  971. * @param {MempoolEntry} entry
  972. * @param {Object} set
  973. * @returns {Number}
  974. */
  975. _countDescendants(entry, set) {
  976. const tx = entry.tx;
  977. const hash = tx.hash();
  978. for (let i = 0; i < tx.outputs.length; i++) {
  979. const child = this.getSpent(hash, i);
  980. if (!child)
  981. continue;
  982. const next = child.hash();
  983. if (set.has(next))
  984. continue;
  985. set.add(next);
  986. this._countDescendants(child, set);
  987. }
  988. return set.size;
  989. }
  990. /**
  991. * Get all transaction ancestors.
  992. * @param {MempoolEntry} entry
  993. * @returns {MempoolEntry[]}
  994. */
  995. getAncestors(entry) {
  996. return this._getAncestors(entry, [], new BufferSet());
  997. }
  998. /**
  999. * Get all transaction ancestors.
  1000. * @private
  1001. * @param {MempoolEntry} entry
  1002. * @param {MempoolEntry[]} entries
  1003. * @param {Object} set
  1004. * @returns {MempoolEntry[]}
  1005. */
  1006. _getAncestors(entry, entries, set) {
  1007. const tx = entry.tx;
  1008. for (const {prevout} of tx.inputs) {
  1009. const hash = prevout.hash;
  1010. const parent = this.getEntry(hash);
  1011. if (!parent)
  1012. continue;
  1013. if (set.has(hash))
  1014. continue;
  1015. set.add(hash);
  1016. entries.push(parent);
  1017. this._getAncestors(parent, entries, set);
  1018. }
  1019. return entries;
  1020. }
  1021. /**
  1022. * Get all a transaction descendants.
  1023. * @param {MempoolEntry} entry
  1024. * @returns {MempoolEntry[]}
  1025. */
  1026. getDescendants(entry) {
  1027. return this._getDescendants(entry, [], new BufferSet());
  1028. }
  1029. /**
  1030. * Get all a transaction descendants.
  1031. * @param {MempoolEntry} entry
  1032. * @param {MempoolEntry[]} entries
  1033. * @param {Object} set
  1034. * @returns {MempoolEntry[]}
  1035. */
  1036. _getDescendants(entry, entries, set) {
  1037. const tx = entry.tx;
  1038. const hash = tx.hash();
  1039. for (let i = 0; i < tx.outputs.length; i++) {
  1040. const child = this.getSpent(hash, i);
  1041. if (!child)
  1042. continue;
  1043. const next = child.hash();
  1044. if (set.has(next))
  1045. continue;
  1046. set.add(next);
  1047. entries.push(child);
  1048. this._getDescendants(child, entries, set);
  1049. }
  1050. return entries;
  1051. }
  1052. /**
  1053. * Find a unconfirmed transactions that
  1054. * this transaction depends on.
  1055. * @param {TX} tx
  1056. * @returns {Hash[]}
  1057. */
  1058. getDepends(tx) {
  1059. const prevout = tx.getPrevout();
  1060. const depends = [];
  1061. for (const hash of prevout) {
  1062. if (this.hasEntry(hash))
  1063. depends.push(hash);
  1064. }
  1065. return depends;
  1066. }
  1067. /**
  1068. * Test whether a transaction has dependencies.
  1069. * @param {TX} tx
  1070. * @returns {Boolean}
  1071. */
  1072. hasDepends(tx) {
  1073. for (const {prevout} of tx.inputs) {
  1074. if (this.hasEntry(prevout.hash))
  1075. return true;
  1076. }
  1077. return false;
  1078. }
  1079. /**
  1080. * Return the full balance of all unspents in the mempool
  1081. * (not very useful in practice, only used for testing).
  1082. * @returns {Amount}
  1083. */
  1084. getBalance() {
  1085. let total = 0;
  1086. for (const [hash, entry] of this.map) {
  1087. const tx = entry.tx;
  1088. for (let i = 0; i < tx.outputs.length; i++) {
  1089. const coin = this.getCoin(hash, i);
  1090. if (coin)
  1091. total += coin.value;
  1092. }
  1093. }
  1094. return total;
  1095. }
  1096. /**
  1097. * Retrieve _all_ transactions from the mempool.
  1098. * @returns {TX[]}
  1099. */
  1100. getHistory() {
  1101. const txs = [];
  1102. for (const entry of this.map.values())
  1103. txs.push(entry.tx);
  1104. return txs;
  1105. }
  1106. /**
  1107. * Retrieve an orphan transaction.
  1108. * @param {Hash} hash
  1109. * @returns {TX}
  1110. */
  1111. getOrphan(hash) {
  1112. return this.orphans.get(hash);
  1113. }
  1114. /**
  1115. * @param {Hash} hash
  1116. * @returns {Boolean}
  1117. */
  1118. hasOrphan(hash) {
  1119. return this.orphans.has(hash);
  1120. }
  1121. /**
  1122. * Maybe store an orphaned transaction.
  1123. * @param {TX} tx
  1124. * @param {CoinView} view
  1125. * @param {Number} id
  1126. */
  1127. maybeOrphan(tx, view, id) {
  1128. const hashes = new BufferSet();
  1129. const missing = [];
  1130. for (const {prevout} of tx.inputs) {
  1131. if (view.hasEntry(prevout))
  1132. continue;
  1133. if (this.hasReject(prevout.hash)) {
  1134. this.logger.debug(
  1135. 'Not storing orphan %h (rejected parents).',
  1136. tx.hash());
  1137. this.rejects.add(tx.hash());
  1138. return missing;
  1139. }
  1140. if (this.hasEntry(prevout.hash)) {
  1141. this.logger.debug(
  1142. 'Not storing orphan %h (non-existent output).',
  1143. tx.hash());
  1144. this.rejects.add(tx.hash());
  1145. return missing;
  1146. }
  1147. hashes.add(prevout.hash);
  1148. }
  1149. // Not an orphan.
  1150. if (hashes.size === 0)
  1151. return null;
  1152. // Weight limit for orphans.
  1153. if (tx.getWeight() > policy.MAX_TX_WEIGHT) {
  1154. this.logger.debug('Ignoring large orphan: %h', tx.hash());
  1155. if (!tx.hasWitness())
  1156. this.rejects.add(tx.hash());
  1157. return missing;
  1158. }
  1159. if (this.options.maxOrphans === 0)
  1160. return missing;
  1161. this.limitOrphans();
  1162. const hash = tx.hash();
  1163. for (const prev of hashes.keys()) {
  1164. if (!this.waiting.has(prev))
  1165. this.waiting.set(prev, new BufferSet());
  1166. this.waiting.get(prev).add(hash);
  1167. missing.push(prev);
  1168. }
  1169. this.orphans.set(hash, new Orphan(tx, missing.length, id));
  1170. this.logger.debug('Added orphan %h to mempool.', tx.hash());
  1171. this.emit('add orphan', tx);
  1172. return missing;
  1173. }
  1174. /**
  1175. * Resolve orphans and attempt to add to mempool.
  1176. * @method
  1177. * @param {TX} parent
  1178. * @returns {Promise} - Returns {@link TX}[].
  1179. */
  1180. async handleOrphans(parent) {
  1181. const resolved = this.resolveOrphans(parent);
  1182. for (const orphan of resolved) {
  1183. let tx, missing;
  1184. try {
  1185. tx = orphan.toTX();
  1186. } catch (e) {
  1187. this.logger.warning('%s %s',
  1188. 'Warning: possible memory corruption.',
  1189. 'Orphan failed deserialization.');
  1190. continue;
  1191. }
  1192. try {
  1193. missing = await this.insertTX(tx, orphan.id);
  1194. } catch (err) {
  1195. if (err.type === 'VerifyError') {
  1196. this.logger.debug(
  1197. 'Could not resolve orphan %h: %s.',
  1198. tx.hash(), err.message);
  1199. if (!tx.hasWitness() && !err.malleated)
  1200. this.rejects.add(tx.hash());
  1201. this.emit('bad orphan', err, orphan.id);
  1202. continue;
  1203. }
  1204. throw err;
  1205. }
  1206. // Can happen if an existing parent is
  1207. // evicted in the interim between fetching
  1208. // the non-present parents.
  1209. if (missing && missing.length > 0) {
  1210. this.logger.debug(
  1211. 'Transaction %h was double-orphaned in mempool.',
  1212. tx.hash());
  1213. this.removeOrphan(tx.hash());
  1214. continue;
  1215. }
  1216. this.logger.debug('Resolved orphan %h in mempool.', tx.hash());
  1217. }
  1218. }
  1219. /**
  1220. * Potentially resolve any transactions
  1221. * that redeem the passed-in transaction.
  1222. * Deletes all orphan entries and
  1223. * returns orphan objects.
  1224. * @param {TX} parent
  1225. * @returns {Orphan[]}
  1226. */
  1227. resolveOrphans(parent) {
  1228. const hash = parent.hash();
  1229. const set = this.waiting.get(hash);
  1230. if (!set)
  1231. return [];
  1232. assert(set.size > 0);
  1233. const resolved = [];
  1234. for (const hash of set.keys()) {
  1235. const orphan = this.getOrphan(hash);
  1236. assert(orphan);
  1237. if (--orphan.missing === 0) {
  1238. this.orphans.delete(hash);
  1239. resolved.push(orphan);
  1240. }
  1241. }
  1242. this.waiting.delete(hash);
  1243. return resolved;
  1244. }
  1245. /**
  1246. * Remove a transaction from the mempool.
  1247. * @param {Hash} tx
  1248. * @returns {Boolean}
  1249. */
  1250. removeOrphan(hash) {
  1251. const orphan = this.getOrphan(hash);
  1252. if (!orphan)
  1253. return false;
  1254. let tx;
  1255. try {
  1256. tx = orphan.toTX();
  1257. } catch (e) {
  1258. this.orphans.delete(hash);
  1259. this.logger.warning('%s %s',
  1260. 'Warning: possible memory corruption.',
  1261. 'Orphan failed deserialization.');
  1262. return false;
  1263. }
  1264. for (const prev of tx.getPrevout()) {
  1265. const set = this.waiting.get(prev);
  1266. if (!set)
  1267. continue;
  1268. assert(set.has(hash));
  1269. set.delete(hash);
  1270. if (set.size === 0)
  1271. this.waiting.delete(prev);
  1272. }
  1273. this.orphans.delete(hash);
  1274. this.emit('remove orphan', tx);
  1275. return true;
  1276. }
  1277. /**
  1278. * Remove a random orphan transaction from the mempool.
  1279. * @returns {Boolean}
  1280. */
  1281. limitOrphans() {
  1282. if (this.orphans.size < this.options.maxOrphans)
  1283. return false;
  1284. let index = random.randomRange(0, this.orphans.size);
  1285. let hash;
  1286. for (hash of this.orphans.keys()) {
  1287. if (index === 0)
  1288. break;
  1289. index--;
  1290. }
  1291. assert(hash);
  1292. this.logger.debug('Removing orphan %h from mempool.', hash);
  1293. this.removeOrphan(hash);
  1294. return true;
  1295. }
  1296. /**
  1297. * Test all of a transactions outpoints to see if they are doublespends.
  1298. * Note that this will only test against the mempool spents, not the
  1299. * blockchain's. The blockchain spents are not checked against because
  1300. * the blockchain does not maintain a spent list. The transaction will
  1301. * be seen as an orphan rather than a double spend.
  1302. * @param {TX} tx
  1303. * @returns {Promise} - Returns Boolean.
  1304. */
  1305. isDoubleSpend(tx) {
  1306. for (const {prevout} of tx.inputs) {
  1307. const {hash, index} = prevout;
  1308. if (this.isSpent(hash, index))
  1309. return true;
  1310. }
  1311. return false;
  1312. }
  1313. /**
  1314. * Get coin viewpoint (lock).
  1315. * Note: this does not return
  1316. * historical view of coins from the indexers.
  1317. * @method
  1318. * @param {TX} tx
  1319. * @returns {Promise} - Returns {@link CoinView}.
  1320. */
  1321. async getSpentView(tx) {
  1322. const unlock = await this.locker.lock();
  1323. try {
  1324. return await this._getSpentView(tx);
  1325. } finally {
  1326. unlock();
  1327. }
  1328. }
  1329. /**
  1330. * Get coin viewpoint
  1331. * @param {TX} tx
  1332. * @returns {Promise} - Returns {@link CoinView}
  1333. */
  1334. async _getSpentView(tx) {
  1335. const view = new CoinView();
  1336. for (const {prevout} of tx.inputs) {
  1337. const {hash, index} = prevout;
  1338. const tx = this.getTX(hash);
  1339. if (tx) {
  1340. if (index < tx.outputs.length)
  1341. view.addIndex(tx, index, -1);
  1342. continue;
  1343. }
  1344. const coin = await this.chain.readCoin(prevout);
  1345. if (coin)
  1346. view.addEntry(prevout, coin);
  1347. }
  1348. return view;
  1349. }
  1350. /**
  1351. * Get coin viewpoint (no lock).
  1352. * @method
  1353. * @param {TX} tx
  1354. * @returns {Promise} - Returns {@link CoinView}.
  1355. */
  1356. async getCoinView(tx) {
  1357. const view = new CoinView();
  1358. for (const {prevout} of tx.inputs) {
  1359. const {hash, index} = prevout;
  1360. const tx = this.getTX(hash);
  1361. if (tx) {
  1362. if (this.hasCoin(hash, index))
  1363. view.addIndex(tx, index, -1);
  1364. continue;
  1365. }
  1366. const coin = await this.chain.readCoin(prevout);
  1367. if (coin)
  1368. view.addEntry(prevout, coin);
  1369. }
  1370. return view;
  1371. }
  1372. /**
  1373. * Get a snapshot of all transaction hashes in the mempool. Used
  1374. * for generating INV packets in response to MEMPOOL packets.
  1375. * @returns {Hash[]}
  1376. */
  1377. getSnapshot() {
  1378. const keys = [];
  1379. for (const hash of this.map.keys())
  1380. keys.push(hash);
  1381. return keys;
  1382. }
  1383. /**
  1384. * Check sequence locks on a transaction against the current tip.
  1385. * @param {TX} tx
  1386. * @param {CoinView} view
  1387. * @param {LockFlags} flags
  1388. * @returns {Promise} - Returns Boolean.
  1389. */
  1390. verifyLocks(tx, view, flags) {
  1391. return this.chain.verifyLocks(this.chain.tip, tx, view, flags);
  1392. }
  1393. /**
  1394. * Check locktime on a transaction against the current tip.
  1395. * @param {TX} tx
  1396. * @param {LockFlags} flags
  1397. * @returns {Promise} - Returns Boolean.
  1398. */
  1399. verifyFinal(tx, flags) {
  1400. return this.chain.verifyFinal(this.chain.tip, tx, flags);
  1401. }
  1402. /**
  1403. * Map a transaction to the mempool.
  1404. * @private
  1405. * @param {MempoolEntry} entry
  1406. * @param {CoinView} view
  1407. */
  1408. trackEntry(entry, view) {
  1409. const tx = entry.tx;
  1410. const hash = tx.hash();
  1411. assert(!this.map.has(hash));
  1412. this.map.set(hash, entry);
  1413. assert(!tx.isCoinbase());
  1414. for (const {prevout} of tx.inputs) {
  1415. const key = prevout.toKey();
  1416. this.spents.set(key, entry);
  1417. }
  1418. if (this.options.indexAddress && view)
  1419. this.indexEntry(entry, view);
  1420. this.size += entry.memUsage();
  1421. }
  1422. /**
  1423. * Unmap a transaction from the mempool.
  1424. * @private
  1425. * @param {MempoolEntry} entry
  1426. */
  1427. untrackEntry(entry) {
  1428. const tx = entry.tx;
  1429. const hash = tx.hash();
  1430. assert(this.map.has(hash));
  1431. this.map.delete(hash);
  1432. assert(!tx.isCoinbase());
  1433. for (const {prevout} of tx.inputs) {
  1434. const key = prevout.toKey();
  1435. this.spents.delete(key);
  1436. }
  1437. if (this.options.indexAddress)
  1438. this.unindexEntry(entry);
  1439. this.size -= entry.memUsage();
  1440. }
  1441. /**
  1442. * Index an entry by address.
  1443. * @private
  1444. * @param {MempoolEntry} entry
  1445. * @param {CoinView} view
  1446. */
  1447. indexEntry(entry, view) {
  1448. this.addrindex.insert(entry, view);
  1449. }
  1450. /**
  1451. * Unindex an entry by address.
  1452. * @private
  1453. * @param {MempoolEntry} entry
  1454. */
  1455. unindexEntry(entry) {
  1456. const hash = entry.tx.hash();
  1457. this.addrindex.remove(hash);
  1458. }
  1459. /**
  1460. * Recursively remove double spenders
  1461. * of a mined transaction's outpoints.
  1462. * @private
  1463. * @param {TX} tx
  1464. */
  1465. removeDoubleSpends(tx) {
  1466. for (const {prevout} of tx.inputs) {
  1467. const {hash, index} = prevout;
  1468. const spent = this.getSpent(hash, index);
  1469. if (!spent)
  1470. continue;
  1471. this.logger.debug(
  1472. 'Removing double spender from mempool: %h.',
  1473. spent.hash());
  1474. this.evictEntry(spent);
  1475. this.emit('double spend', spent);
  1476. }
  1477. }
  1478. /**
  1479. * Calculate the memory usage of the entire mempool.
  1480. * @see DynamicMemoryUsage()
  1481. * @returns {Number} Usage in bytes.
  1482. */
  1483. getSize() {
  1484. return this.size;
  1485. }
  1486. /**
  1487. * Prioritise transaction.
  1488. * @param {MempoolEntry} entry
  1489. * @param {Number} pri
  1490. * @param {Amount} fee
  1491. */
  1492. prioritise(entry, pri, fee) {
  1493. if (-pri > entry.priority)
  1494. pri = -entry.priority;
  1495. entry.priority += pri;
  1496. if (-fee > entry.deltaFee)
  1497. fee = -entry.deltaFee;
  1498. if (fee === 0)
  1499. return;
  1500. this.updateAncestors(entry, prePrioritise);
  1501. entry.deltaFee += fee;
  1502. entry.descFee += fee;
  1503. this.updateAncestors(entry, postPrioritise);
  1504. }
  1505. }
  1506. /**
  1507. * Mempool Options
  1508. * @alias module:mempool.MempoolOptions
  1509. */
  1510. class MempoolOptions {
  1511. /**
  1512. * Create mempool options.
  1513. * @constructor
  1514. * @param {Object}
  1515. */
  1516. constructor(options) {
  1517. this.network = Network.primary;
  1518. this.chain = null;
  1519. this.logger = null;
  1520. this.workers = null;
  1521. this.fees = null;
  1522. this.limitFree = true;
  1523. this.limitFreeRelay = 15;
  1524. this.relayPriority = true;
  1525. this.requireStandard = this.network.requireStandard;
  1526. this.rejectAbsurdFees = true;
  1527. this.prematureWitness = false;
  1528. this.paranoidChecks = false;
  1529. this.replaceByFee = false;
  1530. this.maxSize = policy.MEMPOOL_MAX_SIZE;
  1531. this.maxOrphans = policy.MEMPOOL_MAX_ORPHANS;
  1532. this.maxAncestors = policy.MEMPOOL_MAX_ANCESTORS;
  1533. this.expiryTime = policy.MEMPOOL_EXPIRY_TIME;
  1534. this.minRelay = this.network.minRelay;
  1535. this.prefix = null;
  1536. this.location = null;
  1537. this.memory = true;
  1538. this.maxFiles = 64;
  1539. this.cacheSize = 32 << 20;
  1540. this.compression = true;
  1541. this.persistent = false;
  1542. this.fromOptions(options);
  1543. }
  1544. /**
  1545. * Inject properties from object.
  1546. * @private
  1547. * @param {Object} options
  1548. * @returns {MempoolOptions}
  1549. */
  1550. fromOptions(options) {
  1551. assert(options, 'Mempool requires options.');
  1552. assert(options.chain && typeof options.chain === 'object',
  1553. 'Mempool requires a blockchain.');
  1554. this.chain = options.chain;
  1555. this.network = options.chain.network;
  1556. this.logger = options.chain.logger;
  1557. this.workers = options.chain.workers;
  1558. this.requireStandard = this.network.requireStandard;
  1559. this.minRelay = this.network.minRelay;
  1560. if (options.logger != null) {
  1561. assert(typeof options.logger === 'object');
  1562. this.logger = options.logger;
  1563. }
  1564. if (options.workers != null) {
  1565. assert(typeof options.workers === 'object');
  1566. this.workers = options.workers;
  1567. }
  1568. if (options.fees != null) {
  1569. assert(typeof options.fees === 'object');
  1570. this.fees = options.fees;
  1571. }
  1572. if (options.limitFree != null) {
  1573. assert(typeof options.limitFree === 'boolean');
  1574. this.limitFree = options.limitFree;
  1575. }
  1576. if (options.limitFreeRelay != null) {
  1577. assert((options.limitFreeRelay >>> 0) === options.limitFreeRelay);
  1578. this.limitFreeRelay = options.limitFreeRelay;
  1579. }
  1580. if (options.relayPriority != null) {
  1581. assert(typeof options.relayPriority === 'boolean');
  1582. this.relayPriority = options.relayPriority;
  1583. }
  1584. if (options.requireStandard != null) {
  1585. assert(typeof options.requireStandard === 'boolean');
  1586. this.requireStandard = options.requireStandard;
  1587. }
  1588. if (options.rejectAbsurdFees != null) {
  1589. assert(typeof options.rejectAbsurdFees === 'boolean');
  1590. this.rejectAbsurdFees = options.rejectAbsurdFees;
  1591. }
  1592. if (options.prematureWitness != null) {
  1593. assert(typeof options.prematureWitness === 'boolean');
  1594. this.prematureWitness = options.prematureWitness;
  1595. }
  1596. if (options.paranoidChecks != null) {
  1597. assert(typeof options.paranoidChecks === 'boolean');
  1598. this.paranoidChecks = options.paranoidChecks;
  1599. }
  1600. if (options.replaceByFee != null) {
  1601. assert(typeof options.replaceByFee === 'boolean');
  1602. this.replaceByFee = options.replaceByFee;
  1603. }
  1604. if (options.maxSize != null) {
  1605. assert((options.maxSize >>> 0) === options.maxSize);
  1606. this.maxSize = options.maxSize;
  1607. }
  1608. if (options.maxOrphans != null) {
  1609. assert((options.maxOrphans >>> 0) === options.maxOrphans);
  1610. this.maxOrphans = options.maxOrphans;
  1611. }
  1612. if (options.maxAncestors != null) {
  1613. assert((options.maxAncestors >>> 0) === options.maxAncestors);
  1614. this.maxAncestors = options.maxAncestors;
  1615. }
  1616. if (options.expiryTime != null) {
  1617. assert((options.expiryTime >>> 0) === options.expiryTime);
  1618. this.expiryTime = options.expiryTime;
  1619. }
  1620. if (options.minRelay != null) {
  1621. assert((options.minRelay >>> 0) === options.minRelay);
  1622. this.minRelay = options.minRelay;
  1623. }
  1624. if (options.prefix != null) {
  1625. assert(typeof options.prefix === 'string');
  1626. this.prefix = options.prefix;
  1627. this.location = path.join(this.prefix, 'mempool');
  1628. }
  1629. if (options.location != null) {
  1630. assert(typeof options.location === 'string');
  1631. this.location = options.location;
  1632. }
  1633. if (options.memory != null) {
  1634. assert(typeof options.memory === 'boolean');
  1635. this.memory = options.memory;
  1636. }
  1637. if (options.maxFiles != null) {
  1638. assert((options.maxFiles >>> 0) === options.maxFiles);
  1639. this.maxFiles = options.maxFiles;
  1640. }
  1641. if (options.cacheSize != null) {
  1642. assert(Number.isSafeInteger(options.cacheSize));
  1643. assert(options.cacheSize >= 0);
  1644. this.cacheSize = options.cacheSize;
  1645. }
  1646. if (options.compression != null) {
  1647. assert(typeof options.compression === 'boolean');
  1648. this.compression = options.compression;
  1649. }
  1650. if (options.persistent != null) {
  1651. assert(typeof options.persistent === 'boolean');
  1652. this.persistent = options.persistent;
  1653. }
  1654. if (options.indexAddress != null) {
  1655. assert(typeof options.indexAddress === 'boolean');
  1656. this.indexAddress = options.indexAddress;
  1657. }
  1658. return this;
  1659. }
  1660. /**
  1661. * Instantiate mempool options from object.
  1662. * @param {Object} options
  1663. * @returns {MempoolOptions}
  1664. */
  1665. static fromOptions(options) {
  1666. return new MempoolOptions().fromOptions(options);
  1667. }
  1668. }
  1669. /**
  1670. * Orphan
  1671. * @ignore
  1672. */
  1673. class Orphan {
  1674. /**
  1675. * Create an orphan.
  1676. * @constructor
  1677. * @param {TX} tx
  1678. * @param {Hash[]} missing
  1679. * @param {Number} id
  1680. */
  1681. constructor(tx, missing, id) {
  1682. this.raw = tx.toRaw();
  1683. this.missing = missing;
  1684. this.id = id;
  1685. }
  1686. toTX() {
  1687. return TX.fromRaw(this.raw);
  1688. }
  1689. }
  1690. /**
  1691. * Mempool Cache
  1692. * @ignore
  1693. */
  1694. class MempoolCache {
  1695. /**
  1696. * Create a mempool cache.
  1697. * @constructor
  1698. * @param {Object} options
  1699. */
  1700. constructor(options) {
  1701. this.logger = options.logger;
  1702. this.chain = options.chain;
  1703. this.network = options.network;
  1704. this.db = null;
  1705. this.batch = null;
  1706. if (options.persistent)
  1707. this.db = bdb.create(options);
  1708. }
  1709. async getVersion() {
  1710. const data = await this.db.get(layout.v.encode());
  1711. if (!data)
  1712. return -1;
  1713. return data.readUInt32LE(0, true);
  1714. }
  1715. async getTip() {
  1716. return this.db.get(layout.R.encode());
  1717. }
  1718. async getFees() {
  1719. const data = await this.db.get(layout.F.encode());
  1720. if (!data)
  1721. return null;
  1722. let fees = null;
  1723. try {
  1724. fees = Fees.fromRaw(data);
  1725. } catch (e) {
  1726. this.logger.warning(
  1727. 'Fee data failed deserialization: %s.',
  1728. e.message);
  1729. }
  1730. return fees;
  1731. }
  1732. getEntries() {
  1733. return this.db.values({
  1734. gte: layout.e.min(),
  1735. lte: layout.e.max(),
  1736. parse: data => MempoolEntry.fromRaw(data)
  1737. });
  1738. }
  1739. getKeys() {
  1740. return this.db.keys({
  1741. gte: layout.e.min(),
  1742. lte: layout.e.max()
  1743. });
  1744. }
  1745. async open() {
  1746. if (!this.db)
  1747. return;
  1748. await this.db.open();
  1749. await this.db.verify(layout.V.encode(), 'mempool', 0);
  1750. await this.verify();
  1751. this.batch = this.db.batch();
  1752. }
  1753. async close() {
  1754. if (!this.db)
  1755. return;
  1756. await this.db.close();
  1757. this.batch = null;
  1758. }
  1759. save(entry) {
  1760. if (!this.db)
  1761. return;
  1762. this.batch.put(layout.e.encode(entry.hash()), entry.toRaw());
  1763. }
  1764. remove(hash) {
  1765. if (!this.db)
  1766. return;
  1767. this.batch.del(layout.e.encode(hash));
  1768. }
  1769. sync(tip) {
  1770. if (!this.db)
  1771. return;
  1772. this.batch.put(layout.R.encode(), tip);
  1773. }
  1774. writeFees(fees) {
  1775. if (!this.db)
  1776. return;
  1777. this.batch.put(layout.F.encode(), fees.toRaw());
  1778. }
  1779. clear() {
  1780. this.batch.clear();
  1781. this.batch = this.db.batch();
  1782. }
  1783. async flush() {
  1784. if (!this.db)
  1785. return;
  1786. await this.batch.write();
  1787. this.batch = this.db.batch();
  1788. }
  1789. async init(hash) {
  1790. const batch = this.db.batch();
  1791. batch.put(layout.v.encode(), fromU32(MempoolCache.VERSION));
  1792. batch.put(layout.R.encode(), hash);
  1793. await batch.write();
  1794. }
  1795. async verify() {
  1796. let version = await this.getVersion();
  1797. let tip;
  1798. if (version === -1) {
  1799. version = MempoolCache.VERSION;
  1800. tip = this.chain.tip.hash;
  1801. this.logger.info(
  1802. 'Mempool cache is empty. Writing tip %h.',
  1803. tip);
  1804. await this.init(tip);
  1805. }
  1806. if (version !== MempoolCache.VERSION) {
  1807. this.logger.warning(
  1808. 'Mempool cache version mismatch (%d != %d)!',
  1809. version,
  1810. MempoolCache.VERSION);
  1811. this.logger.warning('Invalidating mempool cache.');
  1812. await this.wipe();
  1813. return false;
  1814. }
  1815. tip = await this.getTip();
  1816. if (!tip || !tip.equals(this.chain.tip.hash)) {
  1817. this.logger.warning(
  1818. 'Mempool tip not consistent with chain tip (%h != %h)!',
  1819. tip,
  1820. this.chain.tip.hash);
  1821. this.logger.warning('Invalidating mempool cache.');
  1822. await this.wipe();
  1823. return false;
  1824. }
  1825. return true;
  1826. }
  1827. async wipe() {
  1828. const batch = this.db.batch();
  1829. const keys = await this.getKeys();
  1830. for (const key of keys)
  1831. batch.del(key);
  1832. batch.put(layout.v.encode(), fromU32(MempoolCache.VERSION));
  1833. batch.put(layout.R.encode(), this.chain.tip.hash);
  1834. batch.del(layout.F.encode());
  1835. await batch.write();
  1836. this.logger.info('Removed %d mempool entries from disk.', keys.length);
  1837. }
  1838. }
  1839. MempoolCache.VERSION = 2;
  1840. /*
  1841. * Helpers
  1842. */
  1843. function nop(parent, child) {
  1844. ;
  1845. }
  1846. function addFee(parent, child) {
  1847. parent.descFee += child.deltaFee;
  1848. parent.descSize += child.size;
  1849. }
  1850. function removeFee(parent, child) {
  1851. parent.descFee -= child.descFee;
  1852. parent.descSize -= child.descSize;
  1853. }
  1854. function prePrioritise(parent, child) {
  1855. parent.descFee -= child.deltaFee;
  1856. }
  1857. function postPrioritise(parent, child) {
  1858. parent.descFee += child.deltaFee;
  1859. }
  1860. function cmpRate(a, b) {
  1861. let xf = a.deltaFee;
  1862. let xs = a.size;
  1863. let yf = b.deltaFee;
  1864. let ys = b.size;
  1865. let x, y;
  1866. if (useDesc(a)) {
  1867. xf = a.descFee;
  1868. xs = a.descSize;
  1869. }
  1870. if (useDesc(b)) {
  1871. yf = b.descFee;
  1872. ys = b.descSize;
  1873. }
  1874. x = xf * ys;
  1875. y = xs * yf;
  1876. if (x === y) {
  1877. x = a.time;
  1878. y = b.time;
  1879. }
  1880. return x - y;
  1881. }
  1882. function useDesc(a) {
  1883. const x = a.deltaFee * a.descSize;
  1884. const y = a.descFee * a.size;
  1885. return y > x;
  1886. }
  1887. function fromU32(num) {
  1888. const data = Buffer.allocUnsafe(4);
  1889. data.writeUInt32LE(num, 0, true);
  1890. return data;
  1891. }
  1892. /*
  1893. * Expose
  1894. */
  1895. module.exports = Mempool;