Dynamic priority calculation

morcos commented at 8:26 pm on June 30, 2015: member

This is still a work in progress and needs some testing. But this should fix the CTxMemPoolEntry::GetPriority calculation

petertodd commented at 9:37 pm on June 30, 2015: contributor

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.

coinx-ltc commented at 0:09 am on July 1, 2015: none

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

morcos force-pushed on Jul 1, 2015

morcos commented at 8:06 pm on July 1, 2015: member

(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.

laanwj added the label Mempool on Jul 2, 2015

in src/txmempool.cpp: in 13d22c66c3 outdated

243@@ -212,6 +244,7 @@ void CTxMemPool::removeForBlock(const std::vector<CTransaction>& vtx, unsigned i
244     BOOST_FOREACH(const CTransaction& tx, vtx)
245     {
246         std::list<CTransaction> dummy;
247+        updateDependentPriorities(tx, nBlockHeight, true);

sipa commented at 4:17 pm on July 9, 2015:

If a block contains transactions that depend on other transactions in the same block, won’t this cause recalcPriority to be called multiple times for them?

sipa commented at 4:17 pm on July 9, 2015:

I think you need to pass in a queue of transactions to update, and call this function once for the whole block.

sipa commented at 4:18 pm on July 9, 2015: member

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

morcos commented at 9:41 pm on July 9, 2015: member

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.

morcos force-pushed on Jul 10, 2015

morcos commented at 4:14 pm on July 10, 2015: member

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

petertodd commented at 1:34 pm on July 11, 2015: contributor

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.

morcos force-pushed on Nov 2, 2015

morcos force-pushed on Nov 3, 2015

morcos commented at 2:25 am on November 3, 2015: member

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.

morcos commented at 8:09 pm on November 5, 2015: member

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.

dcousens commented at 10:19 pm on November 5, 2015: contributor

@morcos could you please elaborate on:

But this should fix the CTxMemPoolEntry::GetPriority calculation

in src/coins.cpp: in 6bfccf743a outdated

228@@ -229,8 +229,9 @@ bool CCoinsViewCache::HaveInputs(const CTransaction& tx) const
229     return true;
230 }
231 
232-double CCoinsViewCache::GetPriority(const CTransaction &tx, int nHeight) const
233+double CCoinsViewCache::GetPriority(const CTransaction &tx, int nHeight, CAmount &inChainInputValue) const

jtimon commented at 3:44 pm on November 11, 2015:

Style nit: https://github.com/bitcoin/bitcoin/blob/master/src/.clang-format#L41

jtimon commented at 4:09 pm on November 11, 2015: contributor

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.

morcos commented at 8:35 pm on November 12, 2015: member

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

jtoomim commented at 10:46 pm on November 12, 2015: none

@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

in src/txmempool.h: in 6bfccf743a outdated

146+    update_priority(unsigned int _height, CAmount _value) :
147+        height(_height), value(_value)
148+    {}
149+
150+    void operator() (CTxMemPoolEntry &e)
151+    { e.UpdateCachedPriority(height, value); }

sipa commented at 11:05 pm on November 12, 2015:

Style nit :)

morcos force-pushed on Nov 14, 2015

morcos commented at 7:02 pm on November 14, 2015: member

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

Remove default arguments for CTxMemPoolEntry() 58e444ee5e

Modify variable names for entry height and priority 4cac8a5333

Change GetPriority calculation.

Compute the value of inputs that already are in the chain at time of mempool entry and only increase priority due to aging for those inputs.  This effectively changes the CTxMemPoolEntry's GetPriority calculation from an upper bound to a lower bound.

bea369e0ed

Change GetPriority calculation to dynamically update

Track the value of inputs that get confirmed in the chain and keep a cached value of priority at a given height and return current priority by only assuming these in chain inputs are aging.

90898ac834

Add consistency check for on the fly priority calculations 848d623b4e

morcos force-pushed on Nov 18, 2015

laanwj closed this on Nov 30, 2015

MarcoFalke locked this on Sep 8, 2021

Dynamic priority calculation #6357