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 D2865