Page MenuHomePhabricator

[mining] Implement new package selection code which is independent of chain length
Needs RevisionPublic

Authored by schancel on Apr 23 2019, 01:37.

Details

Reviewers
deadalnix
jasonbcox
Group Reviewers
Restricted Owners Package(Owns No Changed Paths)
Restricted Project
Summary

Currently the addPackageTxn function requires recomputing package fees and sizes as each
transaction is added to a block. Additionally, it requires updating a priority queue as
package information is updated. This is to ensure that blocks are nearly optimally packed.

However, the knapsack problem is NP in general, and specifically these updates are factorial
in chain length. This prevents miners and other nodes from allowing long chains to be relayed,
as they would severely impact the function of the network.

In order to remove these computational expenses, we switch to a simple model. We give each
transaction an "order" equal to the number of levels of transactions that will need to go into
a block before it would be a valid inclusion (due to ancestors). In addition to this order, we
track the maximum packageFee/packageSize for all ancestor packages.

If the fee for the package ending in the inspected transaction has a higher packageFee/packageSize
than the maximum seen so far for dependencies, we reset the order of that transaction to Zero.
We can do this because we know that when order 0 transactions are sorted, this transaction will
be the first of any packages already in order 0. Therefor, it will be reasonable to include it
and all its parents.

We then process transactions based on order, and within order by feerate, including all parent transactions
as we go.

The result is that the complexity is O(nlogn) for the sort, and O(n+m) where M is the number of edges
in the transaction graph. This is significantly lower complexity than the existing algorithm,
while allowing some rudimentary CPFP functionality.

Depends on D3164

Test Plan
make check && ./test/functional/test_runner.py

Diff Detail

Repository
rABC Bitcoin ABC
Branch
chains-for-real5 (branched from master)
Lint
Lint OK
Unit
No Unit Test Coverage
Build Status
Buildable 6111
Build 10270: Bitcoin ABC Buildbot (legacy)
Build 10269: arc lint + arc unit

Event Timeline

schancel created this revision.Apr 23 2019, 01:37
Owners added a reviewer: Restricted Owners Package.Apr 23 2019, 01:37
Herald added a reviewer: Restricted Project. · View Herald TranscriptApr 23 2019, 01:37
schancel updated this revision to Diff 8233.Apr 23 2019, 02:05

Update some comments

schancel updated this revision to Diff 8234.Apr 23 2019, 02:09

Fix rebase error on packageOrder

schancel added inline comments.Apr 23 2019, 02:18
src/miner.cpp
700 ↗(On Diff #8230)

This is left just to avoid making the diff un-reviewable. Another patch can delete it.

schancel added inline comments.May 31 2019, 02:10
src/miner.cpp
480 ↗(On Diff #8234)

after before -> are before

schancel updated this revision to Diff 9034.May 31 2019, 06:16

Rebase on diffs that were split up more for clarity.

schancel updated this revision to Diff 9055.Jun 1 2019, 07:19

size_t -> bool ...

schancel updated this revision to Diff 9070.Jun 2 2019, 07:29

Rebase

jasonbcox requested changes to this revision.Jun 21 2019, 22:00
This revision now requires changes to proceed.Jun 21 2019, 22:00