📅 Original date posted:2022-11-07
📝 Original message:Hello bitcoin-dev,
The description in the OP is completely broken for the simple reason that
Bitcoin transactions can have multiple inputs, and so a single transaction
can conflict with multiple in-mempool transactions. The proposal would
limit the number of descendants of each in-mempool transaction to
MAX_REPLACEMENT_CANDIDATES (note that this is duplicative of the existing
Bitcoin Core descendant limits), but a transaction that has, say, 500
inputs might arrive and conflict with 500 unrelated in-mempool
transactions. This could result in 12,500 evictions -- far more than the
100 that was intended.
Also, note that those 500 transactions might instead have 24 ancestors each
(again, using the default chain limits in Bitcoin Core) -- this would
result in 12,000 transactions whose state would be updated as a result of
evicting those 500 transactions. Hopefully this gives some perspective on
why we have a limit.
On Mon, Nov 7, 2022 at 3:17 PM Peter Todd via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> tl;dr: We can remove the problem of Rule #5 pinning by ensuring that all
> transactions in the mempool are always replaceable.
>
>
> Currently Bitcoin Core implements rule #5 of BIP-125:
>
> The number of original transactions to be replaced and their descendant
> transactions which will be evicted from the mempool must not exceed a
> total
> of 100 transactions.
>
> As of Bitcoin Core v24.0rc3, this rule is implemented via the
> MAX_REPLACEMENT_CANDIDATES limit in GetEntriesForConflicts:
>
> // Rule #5: don't consider replacing more than
> MAX_REPLACEMENT_CANDIDATES
> // entries from the mempool. This potentially overestimates the number
> of actual
> // descendants (i.e. if multiple conflicts share a descendant, it will
> be counted multiple
> // times), but we just want to be conservative to avoid doing too much
> work.
> if (nConflictingCount > MAX_REPLACEMENT_CANDIDATES) {
> return strprintf("rejecting replacement %s; too many potential
> replacements (%d > %d)\n",
> txid.ToString(),
> nConflictingCount,
> MAX_REPLACEMENT_CANDIDATES);
> }
>
> There is no justification for this rule beyond avoiding "too much work";
> the
> exact number was picked at random when the BIP was written to provide an
> initial conservative limit, and is not justified by benchmarks or memory
> usage
> calculations. It may in fact be the case that this rule can be removed
> entirely
> as the overall mempool size limits naturally limit the maximum number of
> possible replacements.
>
>
> But for the sake of argument, let's suppose some kind of max replacement
> limit
> is required. Can we avoid rule #5 pinning? The answer is yes, we can, with
> the
> following invariant:
>
> No transaction may be accepted into the mempool that would cause
> another
> transaction to be unable to be replaced due to Rule #5.
>
> We'll call this the Replaceability Invariant. Implementing this rule is
> simple:
> for each transaction maintain an integer, nReplacementCandidates. When a
> non-conflicting transaction is considered for acceptance to the mempool,
> verify
> that nReplacementCandidates + 1 < MAX_REPLACEMENT_CANDIDATES for each
> unconfirmed parent. When a transaction is accepted, increment
> nReplacementCandidates by 1 for each unconfirmed parent.
>
> When a *conflicting* transaction is considered for acceptance, we do _not_
> need
> to verify anything: we've already guaranteed that every transaction in the
> mempool is replaceable! The only thing we may need to do is to decrement
> nReplacementCandidates by however many children we have replaced, for all
> unconfirmed parents.
>
> When a block is mined, note how the nReplacementCandidates of all
> unconfirmed
> transactions remains unchanged because a confirmed transaction can't spend
> an
> unconfirmed txout.
>
> The only special case to handle is a reorg that changes a transaction from
> confirmed to unconfirmed. Setting nReplacementCandidates to
> MAX_REPLACEMENT_CANDIDATES would be fine in that very rare case.
>
>
> Note that like the existing MAX_REPLACEMENT_CANDIDATES check, the
> Replaceability Invariant overestimates the number of transactions to be
> replaced in the event that multiple children are spent by the same
> transaction.
> That's ok: diamond tx graphs are even more unusual than unconfirmed
> children,
> and there's no reason to bend over backwards to accomodate them.
>
> Prior art: this proposed rule is similar in spirit to the package limits
> aready
> implemented in Bitcoin Core.
>
> --
> https://petertodd.org 'peter'[:-1]@petertodd.org
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20221107/200b5236/attachment.html>;
Suhas Daftuar [ARCHIVE] /
npub1ss…e0am4
2023-06-07 23:16:44
in reply to nevent1q…7k02
Author Public Key
npub1ss2s89s938xfh3zzz0j2mhp25tlrlcrj0duljr0ne0t8v2r4cv0q5e0am4Published at
2023-06-07 23:16:44Event JSON
{
"id": "5db505896b8041d05d7d2a24128d997e7283a1c7e1186b36abbfaa5ab3481190",
"pubkey": "841503960589cc9bc44213e4addc2aa2fe3fe0727b79f90df3cbd6762875c31e",
"created_at": 1686179804,
"kind": 1,
"tags": [
[
"e",
"1c27197b3e9dca0fd49b79bdd6e6a81a5b75b6448a9b794f0cec95a2f9743cb8",
"",
"root"
],
[
"e",
"055ced459e088763c65fc29770e79e5f161997cf7dbb6173cd5a5c152962711c",
"",
"reply"
],
[
"p",
"daa2fc676a25e3b5b45644540bcbd1e1168b111427cd0e3cf19c56194fb231aa"
]
],
"content": "📅 Original date posted:2022-11-07\n📝 Original message:Hello bitcoin-dev,\n\nThe description in the OP is completely broken for the simple reason that\nBitcoin transactions can have multiple inputs, and so a single transaction\ncan conflict with multiple in-mempool transactions. The proposal would\nlimit the number of descendants of each in-mempool transaction to\nMAX_REPLACEMENT_CANDIDATES (note that this is duplicative of the existing\nBitcoin Core descendant limits), but a transaction that has, say, 500\ninputs might arrive and conflict with 500 unrelated in-mempool\ntransactions. This could result in 12,500 evictions -- far more than the\n100 that was intended.\n\nAlso, note that those 500 transactions might instead have 24 ancestors each\n(again, using the default chain limits in Bitcoin Core) -- this would\nresult in 12,000 transactions whose state would be updated as a result of\nevicting those 500 transactions. Hopefully this gives some perspective on\nwhy we have a limit.\n\n\nOn Mon, Nov 7, 2022 at 3:17 PM Peter Todd via bitcoin-dev \u003c\nbitcoin-dev at lists.linuxfoundation.org\u003e wrote:\n\n\u003e tl;dr: We can remove the problem of Rule #5 pinning by ensuring that all\n\u003e transactions in the mempool are always replaceable.\n\u003e\n\u003e\n\u003e Currently Bitcoin Core implements rule #5 of BIP-125:\n\u003e\n\u003e The number of original transactions to be replaced and their descendant\n\u003e transactions which will be evicted from the mempool must not exceed a\n\u003e total\n\u003e of 100 transactions.\n\u003e\n\u003e As of Bitcoin Core v24.0rc3, this rule is implemented via the\n\u003e MAX_REPLACEMENT_CANDIDATES limit in GetEntriesForConflicts:\n\u003e\n\u003e // Rule #5: don't consider replacing more than\n\u003e MAX_REPLACEMENT_CANDIDATES\n\u003e // entries from the mempool. This potentially overestimates the number\n\u003e of actual\n\u003e // descendants (i.e. if multiple conflicts share a descendant, it will\n\u003e be counted multiple\n\u003e // times), but we just want to be conservative to avoid doing too much\n\u003e work.\n\u003e if (nConflictingCount \u003e MAX_REPLACEMENT_CANDIDATES) {\n\u003e return strprintf(\"rejecting replacement %s; too many potential\n\u003e replacements (%d \u003e %d)\\n\",\n\u003e txid.ToString(),\n\u003e nConflictingCount,\n\u003e MAX_REPLACEMENT_CANDIDATES);\n\u003e }\n\u003e\n\u003e There is no justification for this rule beyond avoiding \"too much work\";\n\u003e the\n\u003e exact number was picked at random when the BIP was written to provide an\n\u003e initial conservative limit, and is not justified by benchmarks or memory\n\u003e usage\n\u003e calculations. It may in fact be the case that this rule can be removed\n\u003e entirely\n\u003e as the overall mempool size limits naturally limit the maximum number of\n\u003e possible replacements.\n\u003e\n\u003e\n\u003e But for the sake of argument, let's suppose some kind of max replacement\n\u003e limit\n\u003e is required. Can we avoid rule #5 pinning? The answer is yes, we can, with\n\u003e the\n\u003e following invariant:\n\u003e\n\u003e No transaction may be accepted into the mempool that would cause\n\u003e another\n\u003e transaction to be unable to be replaced due to Rule #5.\n\u003e\n\u003e We'll call this the Replaceability Invariant. Implementing this rule is\n\u003e simple:\n\u003e for each transaction maintain an integer, nReplacementCandidates. When a\n\u003e non-conflicting transaction is considered for acceptance to the mempool,\n\u003e verify\n\u003e that nReplacementCandidates + 1 \u003c MAX_REPLACEMENT_CANDIDATES for each\n\u003e unconfirmed parent. When a transaction is accepted, increment\n\u003e nReplacementCandidates by 1 for each unconfirmed parent.\n\u003e\n\u003e When a *conflicting* transaction is considered for acceptance, we do _not_\n\u003e need\n\u003e to verify anything: we've already guaranteed that every transaction in the\n\u003e mempool is replaceable! The only thing we may need to do is to decrement\n\u003e nReplacementCandidates by however many children we have replaced, for all\n\u003e unconfirmed parents.\n\u003e\n\u003e When a block is mined, note how the nReplacementCandidates of all\n\u003e unconfirmed\n\u003e transactions remains unchanged because a confirmed transaction can't spend\n\u003e an\n\u003e unconfirmed txout.\n\u003e\n\u003e The only special case to handle is a reorg that changes a transaction from\n\u003e confirmed to unconfirmed. Setting nReplacementCandidates to\n\u003e MAX_REPLACEMENT_CANDIDATES would be fine in that very rare case.\n\u003e\n\u003e\n\u003e Note that like the existing MAX_REPLACEMENT_CANDIDATES check, the\n\u003e Replaceability Invariant overestimates the number of transactions to be\n\u003e replaced in the event that multiple children are spent by the same\n\u003e transaction.\n\u003e That's ok: diamond tx graphs are even more unusual than unconfirmed\n\u003e children,\n\u003e and there's no reason to bend over backwards to accomodate them.\n\u003e\n\u003e Prior art: this proposed rule is similar in spirit to the package limits\n\u003e aready\n\u003e implemented in Bitcoin Core.\n\u003e\n\u003e --\n\u003e https://petertodd.org 'peter'[:-1]@petertodd.org\n\u003e _______________________________________________\n\u003e bitcoin-dev mailing list\n\u003e bitcoin-dev at lists.linuxfoundation.org\n\u003e https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev\n\u003e\n-------------- next part --------------\nAn HTML attachment was scrubbed...\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20221107/200b5236/attachment.html\u003e",
"sig": "3e963e4883b14399f1f5e83cd3be21369250e21afe24f1da9a18ce9b5ac175f8fc3dcd007e5914e5e55abc717cdfbda27f8caa74acb8e95405e5dc8d4e28a1e0"
}