FWIW a decent chunk of the hashing power has disabled the priority space, and more are likely to follow. Further priority work is probably a wasted effort.

@petertodd Majority still accepts free transactions (at least BitFury, Antpool and BTCChina). But I agree this will change soon (reaching 1mb cap).

(pushed and squashed a bug fix)

@petertodd I completely agree. However I would really like to see #6331 merged, and I don't want that to be held up debating whether priority should be removed, so in the meantime, if we want priority to be calculated correctly, I think this does it.

Can you add a consistency check for verifying that the (re)computed priorities match freshly computed ones, in CTxMempool::check()?

Thanks for the review @sipa. I commented on IRC, but I think the updateDependentPriorities is correct, I don't think its doing any redundant work.
However in trying to implement your consistency check I definitely uncovered several bugs. Will push a fix hopefully tomorrow.

OK, fixed some bugs brought out by the consistency check and added said check.

So, let's assume that all blocks contain 30KB of priority txs. At 1cent/KB we'd be looking at $16k/year of tx fees avoided due to priority.

Meanwhile, if we screw this we just need to lose 2.2 blocks to wipe out all these savings, which comes out of miners' pockets anyway.

I'm with @jgarzik here: better to remove priority and simplify the codebase, particularly when other than Bitcoin Core nearly no wallets use it anyway. (Electrum is apparently an exception)

It's also notable how this patch will make "priority camping" easier: broadcast a broadcast a lowish priority tx, and wait until it gets confirmed, over and over again to waste priority on useless txs. I've seen people do this before when we had that bug where the same tx would be included multiple times; I don't doubt it'll happen again.

This has been rebased.
It's important to have a quick priority calculation for running CreateNewBlock.
If we want to use the current definition of priority, then I think logic like that in this pull is important to make calculating priority on the fly not require looking up inputs.

An alternative to this pull would be to redefine priority to only consist of coins that were in-chain at the time a tx was received in the mempool. That's basically just a subset of this pull without the UpdateDependentPriorities and UpdateCachedPriority functionality.

@morcos could you please elaborate on:

But this should fix the CTxMemPoolEntry::GetPriority calculation

Concept ACK, although I agree it would be much simpler to just remove the reserved space and all its logic. I believe that would simplify many mempool limiting, RBF or policy-encapsulation related patches. If a competitor PR that removes the reserved space is created, I will try to utACK that.

@dcousens See #6292. The existing calculation in CTxMemPoolEntry is broken. It assumes all coins the tx is spending are aging, even unconfirmed ones.

@morcos I was working on a patch to CNB that appears to be very similar to this one except written for BitcoinXT, and consequently without all of the new mempool refactoring stuff that you guys have been done (which is great (except for the eviction policy), and which I intended to sort through and pull eventually). I haven't had a chance to review this in detail, but I have a few comments which are based on what I've seen in the old code and not based on what you've done. It looks like you're quite a bit ahead of me, though, so I apologize if my suggestions seem outdated.

TestBlockValidity on the block template is mostly redundant. Blocks should be validated after having been returned from the miner/poolserver in the submitblock rpc because there is no assurance that the poolserver has not modified the blocks (like p2pool does) and accidentally broken something. My strategy (which I didn't finish implementing) was to take a timestamp the first time CNB is run, and to execute TestBlockValidity synchronously in CNB for 1 hour after that timestamp. After that, exec TBV in a background thread after sending the temple to the miner. If TBV fails once, then return to executing it synchronously before sending the template to the miner. This method runs the risk of allowing the miner to send out an invalid block under very rare circumstances, which I think is fine. Even sending out an invalid block under semi-common circumstances shouldn't be a problem. Yes, SPV mining blah blah, but even SPV miners should be verifying the chain they're working on in the background, and I think/hope the BIP66 soft fork fiasco taught them that they will lose money if they don't. I'll leave it to the rest of you to decide if this approach is safe enough.

You probably know this, but CheckInputs() is really slow, but only because it does ECDSA verifications. If you set it to not verify signatures (setting one of the arguments to false), it's 100x faster, but then you have to watch out for a corner case with reorgs that end up with locktimes.

You can keep dPriority and fees both if you create a means of interconverting between the two. My preferred method for doing this is by assigning weighting to the different metrics based on their normalized score. For example, if the average transaction feerate is 1 and the average transaction priority is 5000, and you want your transactions to be ordered 95% according to fee, then you could sort them according to (feerate/(1_0.95) + dPriority/(5000_0.05)). Then if a miner wants to change their policy, all they change is that weighting. It's also a more efficient an algorithm in terms of the total priority and total fees in the block; on average, this algorithm will produce higher average block fees and priority than an algorithm that evaluates each transaction on only one criteria per pass through the mempool and makes two passes.

The first CNB call after a new block is found is much slower than all subsequent CNB calls for that block. This is due to the CCoinsViewCache objects being cold, especially pcoinsTip. Performance is much improved if you set dbcache=2500 or something else large enough for the UTXO to fit in RAM. The algorithm for choosing the amount of RAM allocated to UTXO based on the total dbcache setting could probably use some tweaking, as I think it does not give enough to UTXO. It may also be a good idea to make a call to GBT bypass or change the dbcache setting, possibly by adding another command-line option like miningutxocache which would increase the available utxo cache if the node is mining.

Some relevant threads from the bitcoinxt list:

https://groups.google.com/forum/#!topic/bitcoin-xt/e2SbLuMyw8s

https://groups.google.com/forum/#!topic/bitcoin-xt/9Y1kUrqW1rk

https://groups.google.com/forum/#!topic/bitcoin-xt/NRre7ZbG66U

Rebased this off of #7008 so it is easier to make decisions on them independently.