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 Passed
Unit
No Test Coverage
Build Status
Buildable 5574
Build 9210: Bitcoin ABC Buildbot (legacy)
Build 9209: arc lint + arc unit

Event Timeline

Owners added a reviewer: Restricted Owners Package.Apr 23 2019, 01:37

Fix rebase error on packageOrder

src/miner.cpp
700 ↗(On Diff #8230)

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

src/miner.cpp
480 ↗(On Diff #8234)

after before -> are before

Rebase on diffs that were split up more for clarity.

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