Mempool limiting with descendant package tracking

sdaftuar commented at 7:30 pm on August 14, 2015: member

This builds off #6470 by adding additional state to CTxMemPoolEntry to track the size/fees of a transaction with all its in-mempool descendants (“packages”), and then sorts the mempool based on max(feerate of tx alone, feerate of tx with descendants), in order to improve the effectiveness of mempool limiting/eviction code.

This introduces 4 new policy limits which serve the limit the length and size of chains in the mempool, in order to ensure computational feasibility of the calculations being done to track descendant packages and effectiveness of the mempool limiting algorithms. A detailed description of the changes made to the mempool as part of this pull can be found in txmempool.h.

See also this email to the bitcoin-dev list, describing the policy limits proposed: http://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-August/010221.html

sdaftuar force-pushed on Aug 14, 2015

sipa commented at 4:13 pm on August 17, 2015: member

Concept ACK. It’ll take me more time to go through the code.

laanwj added the label Mempool on Aug 20, 2015

ABISprotocol commented at 6:14 am on September 3, 2015: none

First #6201 then #6455 and now #6470 all closed out and leading here

will this one be closed also and lead to yet another one?
At any rate, please recall a resolution from the original one (6201) which stated, “Mempool limiting and dynamic fee determination are superior to a static parameter change” Thank you.

laanwj commented at 3:59 pm on September 3, 2015: member

@ABISprotocol please be constructive and help reviewing/testing this pull instead of criticizing, this isn’t helping.

TheBlueMatt commented at 4:36 am on September 6, 2015: member

As an alternative, https://github.com/TheBlueMatt/bitcoin/commit/88a3b8d52432f437a3d194748e446461f721cf9b is much, much simpler (based on the first two commits from here). It is mostly untested, but should work well and doesnt have any obviously exploitable flaws as far as I know. Decendant package tracking and limiting should also be limited on top of it, but I really dont think mempool limiting itself needs to be this complicated.

jtimon commented at 5:00 pm on September 6, 2015: contributor

I really prefer to merge something simple first and work on more complex solution later on top of those initial changes, utACK to @TheBlueMatt ’s alternative. That seems a path that is less conflicting with other related changes like simplifying free transaction’s management or making the min relay fee dynamic, than blocking all the other changes while the more complex solution is not fully ready for whatever reason.

morcos commented at 8:34 pm on September 8, 2015: member

NACK on TheBlueMatt@88a3b8d. -Amount of work done trying to fine a transaction to evict is not reasonably bounded. -Relay fee can (and likely will) be effectively set very high when a high fee transaction happens to evict a high fee package. This will render relay impossible for most normal transactions.

I do however agree that mempool limiting doesn’t have to be this complicated as long as we have the descendant package tracking/limiting first.

TheBlueMatt commented at 9:38 pm on September 8, 2015: member

Yea, turns out I was naive and didn’t spend time to think about how sipa’s removal code actually worked :/. I don’t agree it’s not trivial to appropriately limit it’s runtime, but that’s not so relevant since it doesn’t with to begin with. In any case, my point was more that, yes, let’s do descendant package tracking separately first, and then discuss how to do mempool limiting.

On September 8, 2015 1:34:39 PM PDT, Alex Morcos notifications@github.com wrote:

NACK on TheBlueMatt@88a3b8d. -Amount of work done trying to fine a transaction to evict is not reasonably bounded. -Relay fee can (and likely will) be effectively set very high when a high fee transaction happens to evict a high fee package. This will render relay impossible for most normal transactions.

I do however agree that mempool limiting doesn’t have to be this complicated as long as we have the descendant package tracking/limiting first.

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

ABISprotocol commented at 9:29 am on September 15, 2015: none

Why not this one also: https://github.com/sipa/bitcoin/commit/6498673f99da9976df170052648ff2f0026210d2

dcousens commented at 7:08 am on September 16, 2015: contributor

concept ACK, will review

ABISprotocol commented at 11:25 pm on September 16, 2015: none

@dcousens TY

dcousens commented at 3:13 am on September 19, 2015: contributor

@sdaftuar should this be rebased on #6654?

Reverse the sort on the mempool's feerate index e7c3fa5f06

Add work limit to CTxMemPool::CalculateDescendants ef80cab476

Move orphan tx handling to a separate log class 7721d934e5

Implement on-the-fly mempool size limitation.

Uses a notion of reserved space:
The mempool will now have a soft cap set below its hard cap.  After it fills up
to the soft cap, transactions must first try using TrimMempool to evict the
amount of size they are adding.  If they fail they can still be let into the
mempool if they pass a higher relay minimum.  The minimum increases at every
band between the soft cap and hard cap.

Also implement a perioidic trim from reserve space:
Use reserve space between soft cap and hard cap as a reservoir of surplus fees
that have been paid above the minRelayTxFee and occasionally use the aggregate
usage there to trim from the bottom of the mempool.

This is based on earlier work by Pieter Wuille.

7008233767

Mempool expiry

(note the 9x multiplier on (void*)'s for CTxMemPool::DynamicMemoryUsage was accidentally introduced in 5add7a7 but should have waited for this commit which adds the extra index)

4c1404aebf

sdaftuar force-pushed on Sep 25, 2015

sdaftuar commented at 8:43 pm on September 25, 2015: member

@morcos and I have reworked this pull, now that #6654 has been merged, to try to simplify the code.

The overall approach is as follows:

Limit the mempool to some hard cap (default: 500MB).
Set a “soft cap” equal to 1/2 the maximum. Space above the soft cap is “reserve” space, which can be used for transactions that have some multiple of the relay fee.
- When a new tx arrives, if we’re under the soft cap, let it in as usual.
- If we’re above the soft cap, let it in if it can evict enough room for itself in the mempool, using eviction rules that are designed to prevent free relay attacks.
- If eviction fails, still let it in if the fee on the transaction exceeds the higher relay fee required to take up reserve space (the threshold increases exponentially as usage grows).
Periodically use transactions in the “reserve” space to trim the mempool, by aggregating them together as though they are one large transaction with one large fee (which is more likely to be able to evict transaction packages than individual small transactions could).

There’s also a commit here which will expire old transactions (default: 1 week) from the mempool.

Still to do:

Consider carefully how we want wallet transactions to interact with this behavior. In the current version, wallet transactions (and transaction from a disconnected block) get to bypass the mempool limits. It’s not clear that this is being done the right way, and if the right thing happens when wallet transactions get evicted, etc. Also, we reused the fLimitFree variable to accomplish this, which maybe should be renamed if we stick with this approach.

TheBlueMatt commented at 10:25 pm on September 25, 2015: member

There are a few basic things that we should probably unify across mempool limiting pulls - how wallet is handled (calling a transaction “conflicted” (or rewording that a bit) if it gets dropped from mempool because it has too little fee is probably not a bad thing, IMO, especially when the obvious alternative is a deanonymization attack). Also, and I don’t think this is a hard patch, we should probably all be handling orphans as blocks when considering fees, so that CPFP txn can be related as a block by sending them in reverse dependency order.

On September 25, 2015 1:43:14 PM PDT, Suhas Daftuar notifications@github.com wrote:

@morcos and I have reworked this pull, now that #6654 has been merged, to try to simplify the code.

The overall approach is as follows:

Limit the mempool to some hard cap (default: 500MB).

Set a “soft cap” equal to 1/2 the maximum. Space above the soft cap is “reserve” space, which can be used for transactions that have some multiple of the relay fee.

When a new tx arrives, if we’re under the soft cap, let it in as usual.

If we’re above the soft cap, let it in if it can evict enough room for itself in the mempool, using eviction rules that are designed to prevent free relay attacks.

If eviction fails, still let it in if the fee on the transaction exceeds the higher relay fee required to take up reserve space (the threshold increases exponentially as usage grows).

Periodically use transactions in the “reserve” space to trim the mempool, by aggregating them together as though they are one large transaction with one large fee (which is more likely to be able to evict transaction packages than individual small transactions could).

There’s also a commit here which will expire old transactions (default: 1 week) from the mempool.

Still to do:

Consider carefully how we want wallet transactions to interact with this behavior. In the current version, wallet transactions (and transaction from a disconnected block) get to bypass the mempool limits. It’s not clear that this is being done the right way, and if the right thing happens when wallet transactions get evicted, etc. Also, we reused the fLimitFree variable to accomplish this, which maybe should be renamed if we stick with this approach.

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

ABISprotocol commented at 11:00 pm on September 25, 2015: none

I’m generally pleased to see where this has gone, however ~ these remarks intended for @sdaftuar and @morcos ~ I am interested in seeing the concerns inherent in my remarks here addressed as well as the statement clarifying that “mempool limiting and dynamic fee determination are superior to a static parameter change”. To this end I am curious if there will be incorporated a floating relay fee ~ e.g., @sipa’s https://github.com/sipa/bitcoin/commit/6498673f99da9976df170052648ff2f0026210d2 ~ which was removed by @morcos from a prior iteration in the process of getting to this point. Shouldn’t this (or something like it) be reincorporated at this point, or am I misunderstanding / jumping the gun?

sipa commented at 11:05 pm on September 25, 2015: member

@ABISprotocol This PR effectively results in a floating relay fee, by not accepting lower fee transactions anymore as the mempool grows fuller, but without explicitly changing the “nMinRelayFee” variable.

sipa commented at 11:06 pm on September 25, 2015: member

@ABISprotocol For the rest of your comments, the mailing list is probably better suited.

ABISprotocol commented at 11:07 pm on September 25, 2015: none

@sipa TY

sdaftuar commented at 1:17 am on September 26, 2015: member

@TheBlueMatt Agreed, the right wallet behavior should likely be the same regardless of which mempool limiting approach we take. I think this pull is now in good enough shape to try to digest, so that people who are interested can look at this, #6673, #6722, or any other suggestions that are proposed so that we we can pick an approach to focus on, which we can then try to refine.

I am definitely curious if people have ideas about whether it’s problematic for a wallet’s transactions to not make it into the mempool in the first place, or get evicted from the mempool? Or if there are downsides to accepting one’s own transactions into your mempool if you can only do so by bypassing the limiting logic?

Regarding your CPFP comment, that seems like an interesting idea but I don’t have a clear picture in my head of how that could actually be implemented. Seems like the tx relay logic would need to be reworked (along with the logic for not re-requesting rejected transactions), and I’m not sure what the logic would be of how to figure out which combinations of transaction bundles to try (the naive algorithm seems like it’s n^2 in the length of the chain? maybe I’m missing something….).

morcos commented at 10:34 pm on September 28, 2015: member

Unfortunately this needs a bit more work, so please don’t do extensive code review yet. But in terms of strategy direction, still looking for input on this vs #6722 (and possibly vs #6673).

Upcoming changes.

When considering a new tx and the mempool is over the soft cap, use the minimum of its feerate and its ancestor package feerate for eviction code and the reserve space check.
Use exact counting of the surplus fees paid in the reserve space to be more effective at periodic evictions.

ABISprotocol commented at 0:26 am on September 29, 2015: none

—–BEGIN PGP SIGNED MESSAGE—– Hash: SHA512

Keep / focus on #6557.

Alex Morcos:

Unfortunately this needs a bit more work, so please don’t do extensive code review yet. But in terms of strategy direction, still looking for input on this vs #6722 (and possibly vs #6673).

Upcoming changes. - When considering a new tx and the mempool is over the soft cap, use the minimum of its feerate and its ancestor package feerate for eviction code and the reserve space check. - Use exact counting of the surplus fees paid in the reserve space to be more effective at periodic evictions.

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

http://abis.io ~ “a protocol concept to enable decentralization and expansion of a giving economy, and a new social good” https://keybase.io/odinn —–BEGIN PGP SIGNATURE—–

iQEcBAEBCgAGBQJWCdqoAAoJEGxwq/inSG8CMOYH/3qihbcGRIWLdgvjTOBOWfhU m/zPV2GWTXwo73k4UcXXBfFPlFXtr7WzHs6BEGTbtS6WscuOemIuEPM/ev/fRtWF I9joIcNlSvYuRteJ+iCKL7uxV2R5ji6cT/kQMgiuB4hMR8ubQ9pJ+St0RTY1d7ZN jkxFv4UIHFHZqUzKH9TC1NqVHw4gh+/Sp59aI3KcCoQk6zvFHAOWjbDexPwgrzPd xEZHJ6z5PsViExTh+Mz4z3vmCpANngNsstIX9geY/f/6FJP4QoGTSgUpIiHAlTHY OM0qj9IEhBYKWQjp+lWKr/zj/vbk74JPZU95L0Nt5v8bC2wGJPIMG/K2OmqJWbw= =cNWF —–END PGP SIGNATURE—–

Switch exponential relay to continuous.

Easier to more accurately account for surplus fees paid by txs in the reserve space.

0169bbdd67

Consider ancestor fee rate for acceptance to mempool 9bc6546e8c

sdaftuar commented at 2:27 pm on September 30, 2015: member

Added two commits that address the points @morcos mentioned above.

morcos commented at 5:52 pm on September 30, 2015: member

I think this pull works and accomplishes the job. However #6722 seems to also achieve the same goals and may be a better solution due to its simpler design. I’ll leave this open for now, but will close if consensus appears to converge on #6722.

sdaftuar commented at 4:18 pm on October 20, 2015: member

Closing in favor of #6722.

sdaftuar closed this on Oct 20, 2015

DrahtBot locked this on Sep 8, 2021

Mempool limiting with descendant package tracking #6557