[WIP] [Mempool] Add space for priority transactions #6992

sdaftuar commented at 8:28 PM on November 11, 2015: member

This is a work-in-progress that certainly needs more testing and cleanup -- sharing now in light of discussions happening elsewhere (#6972) about some of the drawbacks from introducing mempool limiting in #6722.

Overall I agree with @sturles in that the existing notion of priority is largely a useful one to differentiate transactions that might be part of an attack from ones that likely are not. On the other hand, coming up with a mempool limiting algorithm like #6722 that we believe is robust against attack was challenging enough without having to also try to maintain this particular existing policy.

However after further thought I think we can restore some of the useful features of priority without major re-engineering of the mempool. I propose to reserve some fraction of the mempool (defaults to the blockprioritysize/blockmaxsize) for transactions that have no unconfirmed parents. Transactions in that space will be sorted by priority at the time of entry to the mempool.

If the priority space in the mempool exceeds its limit, priority transactions will be moved to the feerate portion of the mempool (where they will be sorted based on their feerate and the feerate of any descendants). Once moved to the feerate area, transactions never move back to the priority area.

New transactions that don't meet the mempool reject fee must meet the new GetMinPriority(), which is increased when priority transactions are moved to the feerate part of the mempool, and decayed as time passes (just like the mempool's minimum fee).

Note that this relies on the rate limiting of free transactions to prevent relay bandwidth DoS attacks using priority transactions.

Add priority space to mempool

Reserve part of the mempool for transactions that have no in-mempool
parents.  Change the feerate index to sort that part of the mempool
by priority at the time of entry.

Transactions at the bottom of the priority sort get moved to the fee
rate area when the priority area exceeds its size limit.

New transactions that don't meet the mempool reject fee must meet
the new GetMinPriority(), which is increased when priority transactions
are moved to the feerate part of the mempool, and decayed as time passes.

32520bfb9e

sdaftuar force-pushed on Nov 11, 2015

MarcoFalke commented at 9:09 PM on November 11, 2015: member

Concept ACK.

in src/main.cpp:None in 32520bfb9e

2325 | @@ -2316,8 +2326,13 @@ static bool ActivateBestChainStep(CValidationState &state, CBlockIndex *pindexMo
2326 |      }
2327 |      }
2328 |  
2329 | -    if (fBlocksDisconnected)
2330 | -        mempool.TrimToSize(GetArg("-maxmempool", DEFAULT_MAX_MEMPOOL_SIZE) * 1000000);
2331 | +    if (fBlocksDisconnected) {
2332 | +        size_t mempoolLimit = GetArg("-maxmempool", DEFAULT_MAX_MEMPOOL_SIZE) * 1000000;
2333 | +        const double defaultPriorityLimit = (double) GetArg("-blockprioritysize", DEFAULT_BLOCK_PRIORITY_SIZE) / (double) GetArg("-blockmaxsize", DEFAULT_BLOCK_MAX_SIZE);
2334 | +        size_t priorityLimit = GetArg("-prioritylimit", defaultPriorityLimit * mempoolLimit);

dcousens commented at 9:43 PM on November 11, 2015:

This algorithm is done several times, and is a cluster to read. Could you extract it out at all to make review easier?

dcousens commented at 9:48 PM on November 11, 2015: contributor

I'm not sure we need a separate 'space' for the priority transactions. Conceptually the entire mempool algorithm shouldn't be more complicated than:

Sort transactions by descending, comparing fees, then priority.
Fees less than minRelayTxFee should be considered 0, allowing priority to take precedence
Drop transactions on the lower part of the spectrum until ideal memory usage is met.

Even a simplistic 'fitness' function could be used which combines priority and fees in a way that is considered sane, and that function used rather than this mix-match combination of fee/priority comparisons everywhere.

edit: And then there is that which @TheBlueMatt points out, is priority even worth it?

TheBlueMatt commented at 9:52 PM on November 11, 2015: member

NAK. I thought there was agreement that priority space is a bad idea in general. The amount of developer time that has gone into making priority space work properly is no where near the gains from having it.

sturles commented at 10:18 PM on November 11, 2015: none

I am testing now it to see if it solves my problems. It can't possibly be worse than the current version, which almost led to loss of coins for me due to transactions with negative confirmations reappearing as unconfirmed after a restart, and loss of trust from other people when my client double spent inputs instead of rebroadcasting high priority transactions.

TheBlueMatt commented at 10:21 PM on November 11, 2015: member

The solution, as mentioned by @morcos in #6972 is the last commit in #6134, not re-adding priority area when there is actual fee-paying traffic.

sipa commented at 10:27 PM on November 11, 2015: member

My idea was that we'd get rid of priority, and replace it with a small adjustment to the fee or size of a transaction.

One idea is to treat the total bitcoindays of the UTXO set as limited resource and treat it as currency, and that burning it should be treated like extra fee, with a small factor. Specifically:

for each transaction you compute the bitcoin-days-destroyed
divide it by the average UTXO entry age weighed by amount (around 800 days currently)
the result is a value in BTC; take some configurable fraction of it (0.5% for example)
treat the result as extra fee (which gets divided by the tx size to obtain the feerate).

This is simple (don't bother recalculating this equivalent fee on every mempool change; just infrequently in the background or even not at all and keep using the value from entry time), and using 0.5% as factor would give a 250-byte 1 BTC-day-destroyed transaction (the limit for high priority earlier) the equivalent of 2500 satoshi/kB feerate boost.

The downside is that it has no guarantees on how much a miner could lose by using this approach. For example, 100 BTC of 1 year old coins would be treated equal to a 1 BTC fee. We can cap the maximum amount of feerate replaced, but that may make the scheme pretty useless if the cap is easy to hit.

sipa commented at 10:31 PM on November 11, 2015: member

@sturles I believe that the wallet treating evicted transactions as spendable again is an outright bug, and a blocker we should fix before release (so thanks for reporting that). What the right solution is w.r.t. priority, I don't know - it's a hard problem that tries to balance the advantage of allowing a small amount of free transactions on the network (but only to the privileged few who have enough stashed coins...) and extra solftware complexity and incentive-incompatibility for mining...

sturles commented at 10:37 PM on November 11, 2015: none

@TheBlueMatt The last commit in #6134 is a kludge to hide some symptoms. It doesn't solve the bugs I just mentioned here. It would just have added a fee to one of the transactions I mentioned. The rest would still be treated the same. If this patch works as advertised, it will solve all the problems I mentioned. (Not guaranteed, in case a lot of extremely high priority transactions suddenly show up, but likewise the commit in #6134 is not guaranteed to fix the problem in case a lot of high fee transactions suddenly show up.)

TheBlueMatt commented at 10:45 PM on November 11, 2015: member

@sipa I'm not sure its worth the incentive-incompatibility for miners to do that. You could probably get away with it (with a cap) for some time yet, but we'll be back here in 6-12 months getting rid of priority at that point.

dcousens commented at 11:51 PM on November 11, 2015: contributor

Agreed, NACK

sdaftuar commented at 1:37 AM on November 12, 2015: member

To me the most important question is, is priority something that miners want to use?

If a non-negligible amount of hashpower intends to use it in their transaction selection, then I think it makes sense for nodes to use it too, because it's generally helpful to have your mempool predict the UTXO as much as possible, and for nodes to be able to have reasonable fee and priority estimates (which won't happen unless they track the priority transactions somehow -- I'm presuming that miners run with much bigger mempools than regular nodes).

If the answer is no, then that's fine and I don't see a reason to push in this direction. I sort of assumed there was enough hashpower mining with priority, since last time I checked estimatepriority was still giving meaningful results for low-ish blockheights, but I haven't done any kind of real analysis.

morcos commented at 2:47 AM on November 12, 2015: member

Concept ACK from me. Although it looks like a fair amount of code, its not a terribly invasive change.

Fundamentally I agree that supporting priority is probably more trouble than it's worth. However I think we backed ourselves into a bit of a corner by not more clearly communicating and building consensus that priority based transactions were going away before now.

We can of course still do that, but I don't like releasing a 0.12 which breaks priority before that has happened. If we had no choice, then thats one thing, but if a few peoples time to review this code is all it takes to avoid that scenario, we should avoid it.

We need to make an analogous decision with respect to #6357. If we're ok making miners who are using priority space only care about the starting priority of the tx for filling that space (the same way this pull uses that for eviction), then we can skip #6357, but otherwise we have to have it in order to speed up CreateNewBlock.

pstratem commented at 3:19 AM on November 12, 2015: contributor

Strong NACK.

Free transactions are a thing of the past.

We've made the mistake in the past of failing to signal that things are going away.

Lets not make that mistake again.

jgarzik commented at 3:33 AM on November 12, 2015: contributor

"My idea was that we'd get rid of priority, and replace it with a small adjustment to the fee or size of a transaction."

that's pretty much exactly what my remove-priority PR did...

Removing priority vastly simplifies a lot of the code. Fee deltas continue to exist...

TheBlueMatt commented at 3:35 AM on November 12, 2015: member

Fee deltas continue to exist as an RPC interface for manual control, sure, though I'm not sure I understand why we should be applying a "default" fee delta to all transactions.

sturles commented at 6:51 AM on November 12, 2015: none

I have been running this since yesterday evening, and made a few free transactions with varying priority to test. This morning I checked if my transactions were still in my mempool. They were not. Even the lowest priority transactions I made were mined, not evicted. From this I can conclude:

The patch has worked so far, but the transactions were probably mined before my mempool was full.
Free transactions certainly still get mined, disproving @pstratem and others who got think otherwise.

After sending the transactions, I made this change to wallet/wallet.cpp to avoid making free transactions with too low priority when priorityestimate returns -1. If people have the impression that free transactions aren't getting mined, the reason is probably because Bitcoin Core use this too low default priority when it lacks a useful estimate. It usually does at very low txconfirmtarget:

diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp index d51b8dd..7f3385c 100644 --- a/src/wallet/wallet.cpp +++ b/src/wallet/wallet.cpp @@ -2034,9 +2034,11 @@ bool CWallet::CreateTransaction(const vector<CRecipient>& vecSend, CWalletTx& wt { // Not enough fee: enough priority? double dPriorityNeeded = mempool.estimatePriority(nTxConfirmTarget);

               // Not enough mempool history to estimate: use hard-coded AllowFree.

               if (dPriorityNeeded <= 0 && AllowFree(dPriority))

```
                   break;
```

               // Not enough mempool history to estimate: use first available estimate.

              unsigned int i = nTxConfirmTarget;

               while (i++ < 24 && dPriorityNeeded <= 0) {

                  dPriorityNeeded = mempool.estimatePriority(i);

              } 

             // Small enough, and priority high enough, to send for free
             if (dPriorityNeeded > 0 && dPriority >= dPriorityNeeded)

TheBlueMatt commented at 9:27 AM on November 12, 2015: member

@sturles No one claimed free transactions would not be mined today. Most miners will absolutely mine free transactions since that is still the default policy in released versions of Bitcoin Core. The point was that a few miners have already turned this off, and more will in the future (it is the only incentive-compatible outcome...if they arent receiving enough in fees for them to strongly want to do this, Bitcoin has failed). Setting expectations that these will be mined in the medium term is crazy.

sturles commented at 10:00 AM on November 12, 2015: none

@TheBlueMatt I may be crazy, but at least I know I can't predict the future accurately. Right now there is no difference in income between reserving half the block for high priority transactions or reserving nothing. If you drop the rest of the anti spam measures, e.g. by accepting dust outputs and other non standard transactions, you can make a few satoshis more. Introducing bugs by purpose to make free transactions harder is premature at best. If you want to remove the priority system, you should do it properly without introducing bug, and remove all references to priority and priority calculations, using fees only, and make 0 fee transactions non-standard.

I don't think anyone expect free transactions to be mined in the first block. bitcoin-cli estimatepriority 1 agrees with that, returning -1. Unfortunately, due to the problem I mentioned above, bitcoin will generate free transactions with much lower priority than needed if the estimate returns -1. I can make a pull request for that fix.

TheBlueMatt commented at 10:04 AM on November 12, 2015: member

I didn't mean to even imply that the way things are now in master is acceptable. Indeed, it is not. And, yes, my preference would be to remove priority in its entirety.

On November 12, 2015 2:00:52 AM PST, sturles notifications@github.com wrote:

@TheBlueMatt I may be crazy, but at least I know I can't predict the future accurately. Right now there is no difference in income between reserving half the block for high priority transactions or reserving nothing. If you drop the rest of the anti spam measures, e.g. by accepting dust outputs and other non standard transactions, you can make a few satoshis more. Introducing bugs by purpose to make free transactions harder is premature at best. If you want to remove the priority system, you should do it properly without introducing bug, and remove all references to priority and priority calculations, using fees only, and make 0 fee transactions non-standard.

I don't think anyone expect free transactions to be mined in the first block. bitcoin-cli estimatepriority 1 agrees with that, returning -1. Unfortunately, due to the problem I mentioned above, bitcoin will generate free transactions with much lower priority than needed if the estimate returns -1. I can make a pull request for that fix.

Reply to this email directly or view it on GitHub: #6992 (comment)

MarcoFalke commented at 10:44 AM on November 12, 2015: member

I like what @sipa proposed (translate priority into additional fee). This should simplify the code and make it easier to configure by just setting the conversion rate via parameters. Also, the default conversion rate could be adjusted based on how the future turns out. (Similar to minRelayTxFee)

morcos commented at 11:18 AM on November 12, 2015: member

@sturles The problem you reference with with defaulting to too low a priority is fixed by the rest of #6134. Obviously if this PR is merged, I'll modify #6134 to look at the appropriate minimum priority of the mempool instead if the mempool reject fee is non zero. @MarcoFalke I don't think its possible to accomplish the same goals by translating priority into fee. @TheBlueMatt Yes thats part of what I don't like about the current state of affairs, its so inconsistent. If we can build consensus to remove priority, then lets do that. Until then, lets continue to support it.

Whey don't we issue a release note saying supporting free priority based transactions is deprecated.

sdaftuar commented at 5:21 PM on November 12, 2015: member

I think if we are deciding to stop supporting priority, then we need a reasonable plan for how to make that happen (something better than silently allowing performance degradation without adequate communication to users in advance).

I propose that if the consensus here is to deprecate priority (which is okay with me in principle) that we do the following:

For 0.12, set the default block priority size to 0 and update the release notes explaining that bitcoin core is deprecating priority.
If we can get adequate review, consider something like this pull for 0.12 to improve the performance of limited mempools at matching up with miner policy. (If we do set the default block priority size to 0, I'll need to update this pull to change its default behavior to include a priority space in the mempool anyway.)

In a future release (maybe 0.13), we can consider removing priority support from CreateNewBlock (especially if indeed miners stop using priority after the defaults are changed) and from the mempool.

in src/main.cpp:None in 32520bfb9e

 929 | @@ -921,7 +930,8 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa
 930 |          // Continuously rate-limit free (really, very-low-fee) transactions
 931 |          // This mitigates 'penny-flooding' -- sending thousands of free transactions just to
 932 |          // be annoying or make others' transactions take longer to confirm.
 933 | -        if (fLimitFree && nFees < ::minRelayTxFee.GetFee(nSize))
 934 | +        if (fLimitFree && (nFees < ::minRelayTxFee.GetFee(nSize) ||
 935 | +                    (mempoolRejectFee > 0 && nFees < mempoolRejectFee)))

morcos commented at 6:12 PM on November 12, 2015:

you don't need this mempoolRejectFee > 0 &&

in src/txmempool.cpp:None in 32520bfb9e

 946 | +        assert(lastPriTx != mapTx.get<1>().begin()); // must have something to evict!
 947 | +        lastPriTx--;
 948 | +        assert(lastPriTx->IsPriorityTx());
 949 | +
 950 | +        trackPriorityRemoved(lastPriTx->GetPriority());
 951 | +        LogPrint("mempool", "TrimToSize: priority usage too high (%d > %d); moving tx %s (%lu bytes %f priority; rolling min priority=%f)\n",

morcos commented at 6:24 PM on November 12, 2015:

Too much debugging

in src/txmempool.h:None in 32520bfb9e

 133 | @@ -127,6 +134,16 @@ struct set_dirty
 134 |          { e.SetDirty(); }
 135 |  };
 136 |  
 137 | +struct set_prioritytx
 138 | +{
 139 | +    set_prioritytx(bool flag) : fPriorityTx(flag) {}
 140 | +
 141 | +    void operator() (CTxMemPoolEntry &e)
 142 | +        { e.SetPriorityTx(fPriorityTx); }

morcos commented at 6:28 PM on November 12, 2015:

sipa didn't let me do this.

TheBlueMatt commented at 6:29 PM on November 12, 2015: member

@morcos Yes, last I checked there was consensus to remove priority (see #6405 and #6675)

morcos commented at 6:35 PM on November 12, 2015: member

Initial code review ACK. I will do a more thorough review and testing when it's clear the fate of this.

sturles commented at 7:10 PM on November 12, 2015: none

ACK from me fwiw. I have not been able to reproduce #6972 or #6959 using this patch.

When comparing periodic output from getmempoolinfo on the node running this patch since yesterday, and a different node which run current git version as of two days ago, more transactions are removed from the mempool for each new block on the node running this patch. Mempool size is the same. The difference is usually between 50 and 200 transactions, but hardware differences may be a factor here as well. Nevertheless it is an indication that this version keep more of the transactions most likely to be mined in mempool. I will try this patch with a smaller mempool on the weaker hardware, and see if it still performs better.

sdaftuar commented at 7:34 PM on November 12, 2015: member

Closing after discussion on IRC

sdaftuar closed this on Nov 12, 2015

dcousens commented at 1:09 AM on November 13, 2015: contributor

@sdaftuar what was your conclusion for those of us who weren't there?

sdaftuar commented at 3:29 PM on November 13, 2015: member

@dcousens Well most developers seemed to favor deprecating priority at a slightly faster pace than I proposed above. @TheBlueMatt sent an email to the -dev list yesterday summarizing the discussion on priority (http://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-November/011713.html).

Along those lines, there was a general sentiment to not merge changes like this one or #6357 to improve the way priority is handled.

IRC discussion is logged at http://bitcoinstats.com/irc/bitcoin-dev/logs/2015/11/12#l1447354922.0 if you want to read for yourself...

sturles commented at 3:49 PM on November 13, 2015: none

In that case the current mempool limiting code must be removed and added later when priority transactions have been deprecated, to avoid bugs #6972 and #6959. The current code is broken.

sturles commented at 4:17 PM on November 13, 2015: none

From what I can see from the IRC discussion, only one person is in favor of removing support for priority in 0.12 (BlueMatt). Most want to warn users first, starting in 0.12, before removing support later, or to replace priority with another mechanism. One is against removing priority (Luke-Jr).

As long as priority is supported, this patch is wanted by at least me, as it fixes two bugs and works very well in my testing. It is much better than the current mempool limiting code at keeping transactions which will go into the next block.

DrahtBot locked this on Sep 8, 2021