[NO MERGE] BIP331 Ancestor Package Relay #27742

glozow · 2023-05-24T15:38:55Z

WORK IN PROGRESS. Please do not run it for any use other than testing.

This PR is not meant for merge. This branch exists to help reviewers see what package relay would look like all together. I will open separate PRs for these components and expect to add more tests, docs, and polish along the way. This PR contains all of the functionality built in a linear manner. However, since there are pieces in various areas of the codebase and they can make progress in parallel, commits don't necessarily need to be merged in this order.

See #27463 for what PR(s) are open for review right now.

Note to Reviewers

The major purpose of this PR is to solicit "approach" review.

This is a large project, and the first few p2p commits essentially define the interface. I'd like to get rough consensus on approach before we start looking at code details and merging PRs, because I believe it will help us "get useful stuff in" faster and avoid premature optimizations.

Here are some questions I hope are answered before we try to merge anything (originally #27742 (comment)):

Does the proposed protocol look sound?
Are these 3 milestones appropriate?
Is there important functionality that is in the "todo improvements" section but should be included in one of the 3 milestones? Alternatively, is there not-that-important stuff in the milestones that we should defer until later?
Does it make sense to have this PeerManager <-> TxDownloadMan interface?

Comments about naming, typos, code details, etc. are also appreciated but please note I may wait until their respective PRs are open to incorporate your comments. Thank you for your patience.

Design Docs

BIP: bitcoin/bips#1382
Orphanage changes: https://gist.github.com/glozow/7c0ff639f996e660146314edffa6f06c

Project Structure

3 Major Milestones

This project is split into 3 milestones, each of which gives us something useful.

Modularize and improve orphan-handling (also some refactoring).
- Introduce a TxDownloadManager class, responsible for downloading transactions that have been announced to us.
- Use all announcers as potential candidates for resolving an orphan. Add a TxRequestTracker Orphan Request Tracker which helps track orphans we need to resolve. Preferentially request orphan resolution from outbounds, preferred relay, etc., over inbounds.
When package relay peers are available, use ancpkginfo instead of missing parents when handling orphans.
- Add sendpackages negotiation logic.
- Add a separate rejections filter for transactions that are eligible for reconsideration when validated together as a package, so that children of low-feerate transactions are still considered.
- Send getdata(MSG_ANCPKGINFO) to package relay peers for orphan resolution. Use ancpkginfo to request missing ancestors through normal individual transaction relay.
Download and validate ancestor packages using getpkgtxns and pkgtxns.
- Add support for getpkgtxns and pkgtxns. Send a pkgtxns using the list of missing transactions from ancpkginfo.
- Ensure we can process "normal" orphans even if a peer is trying to overwhelm/churn our orphanage. Do this by "opportunistically" protecting orphans from random eviction if they were sent by package relay peers, and redownloading orphans if we cannot afford to protect them. Each peer is allocated a certain amount of orphans they can protect at a time ("token bucket" style but the number of tokens is static for now). Outbound peers get more than inbounds.
- If a transaction's parent(s) are below the fee filter, don't announce it (save the bandwidth of legacy nodes).

Todo improvements

These could be added to the milestones or deferred until basic functionality is deployed.

Store orphans serialized instead of as CTransactionRefs to significantly reduce their memory usage.
Perhaps try to keep orphans in disk and/or process them asynchronously, given the incredibly DoSable nature of orphan handling.
Dynamically allocate tokens for orphan protection. For example, if a long-standing inbound peer continuously provides good packages for orphans, they should have more tokens. If a peer is obviously serving us garbage, reduce their tokens.
Detect when we have received all the transactions for a package, regardless of how (individual or block or other), and return PackageToValidate in GetTxToReconsider.
New format for mempool.dat, packages instead of transactions.

DrahtBot · 2023-05-24T15:38:59Z

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Code Coverage

For detailed information about the code coverage, see the test coverage report.

Reviews

See the guideline for information on the review process.
A summary of reviews will appear here.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#28107 (rfc: Type-safe transaction identifiers by dergoegge)
#28066 (fuzz: Generate process_message targets individually by MarcoFalke)
#28043 (fuzz: Test headers pre-sync through p2p interface by dergoegge)
#28031 (Package Relay 1/3: Introduce TxPackageTracker as Orphan Resolution Module by glozow)
#27837 (net: introduce block tracker to retry to download blocks after failure by furszy)
#27675 (p2p: Drop m_recently_announced_invs bloom filter by ajtowns)
#27509 (Relay own transactions only via short-lived Tor or I2P connections by vasild)
#27499 (net processing, refactor: Decouple PeerManager from gArgs by dergoegge)
#27452 (test: cover addrv2 anchors by adding TorV3 to CAddress in messages.py by pinheadmz)
#27385 (net, refactor: extract Network and BIP155Network logic to node/network by jonatack)
#26711 (validate package transactions with their in-package ancestor sets by glozow)
#26697 (logging: use bitset for categories by LarryRuane)
#26621 (refactor: Continue moving application data from CNode to Peer by dergoegge)
#26451 (Enforce incentive compatibility for all RBF replacements by sdaftuar)
#25572 (refactor: Introduce EvictionManager and use it for the inbound eviction logic by dergoegge)
#25268 (refactor: Introduce EvictionManager by dergoegge)
#20892 (tests: Run both descriptor and legacy tests within a single test invocation by achow101)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

instagibbs · 2023-06-01T14:12:00Z

Approach review is very welcome on this PR

didn't real whole OP until now. In my not expert opinion, the orphan handling seems reasonable, and I think it makes to open it ASAP to take it out of draft

glozow · 2023-06-01T14:51:07Z

Offline feedback suggested I clarify what I mean by "approach feedback welcome" before "I open separate PRs."

This is a large project, and the first few p2p commits essentially define the interface. I'd like to get rough consensus on approach before we start looking at code details and merging PRs, because I believe it will help us "get useful stuff in" faster and avoid premature optimizations.

Here are some approach questions I think we should answer before diving in:

Does the proposed protocol look sound?
Are these 3 milestones appropriate?
Is there important functionality that is in the "todo improvements" section but should be included in one of the 3 milestones? Alternatively, is there not-that-important stuff in the milestones that we should defer until later?
Does it make sense to have this PeerManager <-> TxPackageTracker <-> TxOrphanage relationship?

instagibbs · 2023-06-01T17:50:43Z

redownloading orphans if we cannot afford to protect them

Is the idea here that protection is a bandiwdth optimization to avoid fetching an orphan twice in a row in the presence of malicious peers or random churn? Reasonable if so, just want this to be explicitly stated if so.

glozow · 2023-06-02T10:38:52Z

redownloading orphans if we cannot afford to protect them

Is the idea here that protection is a bandiwdth optimization to avoid fetching an orphan twice in a row in the presence of malicious peers or random churn? Reasonable if so, just want this to be explicitly stated if so.

Yes exactly. Worse is we want to avoid a situation where we requested the rest of the package while the orphan was in our orphanage, but then it fell out while we were waiting for the rest of the transactions. Then, we should re-download the orphan, but what do we do with the rest of them? We basically have to redownload the whole thing again, otherwise we might end up in an endless cycle of redownloading if we put them into an orphanage but don't necessarily protect them from eviction.

Here is a more detailed doc for the orphanage protection and "token bucket" scheme: https://gist.github.com/glozow/7c0ff639f996e660146314edffa6f06c.

instagibbs

Along with the gist, focused on orphan protection and bucketing for concept understanding. Dumping comments related to those, and left a note on the gist.

src/net_processing.cpp

src/node/txpackagetracker.cpp

src/node/txpackagetracker.h

src/node/txpackagetracker.cpp

instagibbs · 2023-06-01T18:26:51Z

src/node/txpackagetracker.cpp


        // Skip if already requested in the (recent-ish) past.
        if (packageinfo_requested.contains(GetPackageInfoRequestId(nodeid, wtxid, PKG_RELAY_ANCPKG))) return;

+        // Skip if this peer is already using a lot of space in the orphanage.
+        if (m_orphanage.BytesFromPeer(nodeid) > MAX_ORPHANAGE_USAGE) return;


BytesFromPeer counts all announced orphans, even if duplicates, correct?

also, think we should use the new orphan tx size as well here to avoid going past MAX_ORPHANAGE_USAGE?

instagibbs · 2023-06-01T18:37:53Z

src/node/txpackagetracker.cpp

@@ -303,6 +376,9 @@ class TxPackageTracker::Impl {
            auto pending_iter = pending_package_info.find(packageid);
            Assume(pending_iter != pending_package_info.end());
            if (pending_iter != pending_package_info.end()) {
+                for (const auto& [wtxid, missing] : pending_iter->second.m_txdata_status) {
+                    if (!missing) MaybeUnprotectOrphan(nodeid, wtxid);


what is the conditional guarding against?

src/txorphanage.cpp

instagibbs · 2023-06-01T20:33:43Z

src/txorphanage.h

+     * that the number of non-protected orphan entries does not exceed 100. Afterward, Size() may
+     * return a number greater than 100.  It is the caller's responsibility to ensure that not too
+     * many orphans are protected.
+     */
    void LimitOrphans(unsigned int max_orphans) EXCLUSIVE_LOCKS_REQUIRED(!m_mutex);


rename arg max_unprotected_orphans?

instagibbs · 2023-06-02T14:38:20Z

src/txorphanage.cpp

-        auto it_last = m_orphan_list.back();
-        m_orphan_list[old_pos] = it_last;
-        it_last->second.list_pos = old_pos;
+    if (it->second.list_pos >= 0) {


Should this function ever be called with a protected orphan? Tests don't cover these lines for protected peers(added an assert, never hit), and seems suspect that it would delete things below this block if it's protected.

Should this function ever be called with a protected orphan?

Yes. It's called when orphans expire as well.

Tests don't cover these lines for protected peers

Sounds like I neglected to write a test for this. Expiry is pretty long, but theoretically we can hit this if we have multiple peers stalling us on the resolution of this orphan. We might happen to be trying package relay with one of the peers when the expiration is reached.

Ah! Didn't put 2 and 2 together. Comment-worthy

instagibbs

Along with the gist, focused on orphan protection and bucketing for concept understanding. Dumping comments related to those, and left a note on the gist.

ariard · 2023-06-02T18:42:45Z

src/txorphanage.h

@@ -72,6 +72,13 @@ class TxOrphanage {
        LOCK(m_mutex);
        return m_total_orphan_bytes;
    }
+    size_t BytesFromPeer(NodeId peer) const EXCLUSIVE_LOCKS_REQUIRED(!m_mutex)


I think this introduces an interdependency between the number of outgoing transaction bytes we can receive from a peer and the maximum flow of LN commitment transaction+CPFP in weight a direct transaction-relay peer can announce to us and therefore we can validate. An option_anchors_zero_fee_htlc_tx LN commitment transaction weight is 900 WU with no pending HTLCs. As the orphan memory usage is implemented, it’s unclear if there is any processing guarantees for a peer announcing transaction to us, such processing guarantees are hard to enforce as we would be dependent on the full-node host performance.

Note current MAX_ORPHANAGE_USAGE is defined as MAX_ORPHANAGE_USAGE{10*MAX_ORPHANAGE_PROTECTION_OUTBOUND} though it sounds applied on processing inbound announcement (L276 in src/node/txpackagetracker.cpp).

Orphan usage would effect the CPFP transactions, IIUC, not the commitment transactions. The CPFP is deemed high enough, sent to the peer, the peer holds the child tx in orphan set and requests the full package, which isn't size-bound(beyond current mempool limits).

Just to be sure we’re in sync on BytesFromPeer and MAX_ORPHANAGE_USAGE, it’s correct this a per-peer limit on the space in vbytes occupied by received orphans ?

If yes, I think this still introduce an interdependency between the number of outgoing transactions bytes and the maximum flow of LN commitment transactions and this limit should be documented (a la doc/policy/), or even better announced as part of sendpackages info.

ariard · 2023-06-02T18:57:00Z

src/node/txpackagetracker.h

@@ -58,6 +59,36 @@ class TxPackageTracker {
    /** Return how many entries exist in the orphange */
    size_t OrphanageSize();

+    /** Received an announcement from this peer for a tx we already know is an orphan; should be
+     * called for every peer that announces the tx, even if they are not a package relay peer.


There is a argument that can be made if memory and throughputs limits (e.g MAX_PEER_ANNOUNCEMENTS) are applied in function of the type of transactions received (e.g v3 transactions) and that can be used to nudge multi-party and contracting protocols transactions broadcasters to use fee-bumping efficient mechanism such as one CPFP covering multiple parents due to the package limits. This would be a discount incentive by analogy with SegWit spending discounted by consensus validation rules.

On the other hand, such incentive might have “bad incentives” as such package topology might be unsafe (i.e if all the parents confirmation are time-sensitive) and this can become a further complication of our transaction-relay stack.

There is still a last open question if such lack of dissociation between type of traffic (e.g packages from simple transactions) could be abused when package validation is deployed, and CPU performance processing asymmetries (i.e AcceptSingleTransaction vs AcceptMultipleTransactions vs AcceptPackageWrappingSingle vs AcceptAncestorPackage) between our code paths could be exploited by a transaction-relay jamming adversary.

src/node/txpackagetracker.h

src/txorphanage.h

ariard · 2023-07-11T01:15:06Z

src/net_processing.cpp

+    LOCK(cs_main);
+    // We won't re-validate the exact same transaction or package again.
+    if (m_recent_rejects_reconsiderable.contains(GetPackageHash(package.m_unvalidated_txns))) {
+        // Should we do anything else here?


So m_recent_rejects_reconsiderable logs transaction on its wtxid (which is good to avoid witness inflation changing the result) however isn’t that two restrictive if you have PKG1 submitted with A+B, A is too low with B and then you have A+B’ where A is good enough ? Or is that TX_LOW_FEE when the transaction isn’t good enough to meet “mempool min fee not meet” / “min relay fee not met” ?

If it’s correct, I would still favor to exempt package transaction from min relay fee checks as it’s some awful interdependency for pre-signed lightning transaction :)

Yes, that's the idea of "reconsiderable." If you get A again with a different package, you reconsider it. If you get A+B again, you don't. In this set of changes, TX_LOW_FEE is used to decide to put something in the reconsiderable cache.

Okay “reconsiderable” makes sense to me, still have to review it’s correctly implemented.

If it’s correct, I would still favor to exempt package transaction from min relay fee checks as it’s some awful interdependency for pre-signed lightning transaction :)

For this concern, in fact it’s already addressed by the latest state of bip 331 code and nversion=3 documentation, confusion is mine, I thought mempool min fee checks on parent was still present from previous package / acceptance relay reviews.

ariard · 2023-07-15T03:53:45Z

src/validation.cpp

+            if (single_res_it != subpackage_result.m_tx_results.end()) {
+                const auto single_res = single_res_it->second;
+                if (single_res.m_state.GetResult() != TxValidationResult::TX_MEMPOOL_POLICY &&
+                    single_res.m_state.GetResult() != TxValidationResult::TX_LOW_FEE &&


I think this check is correct in what it aims to achieve, i.e not apply the two mempool min fee checks on ancestor package transaction, if it received as such from AcceptAncestorPackage / ProcessNewPackage, however this is unclear if this exemption apply for all BIP331 package, indifferently of their transactions versions, or only for nversion=3 ones.

For context, see lightningdevkit/rust-lightning#2415 (comment)

mzumsande

Some initial comments on part 2 (Negotiate Package Relay, Request Ancestor Package Info For Orphans) - will move on to part 3 soon.

mzumsande · 2023-07-16T21:05:13Z

src/policy/packages.cpp

+}
+uint256 GetPackageHash(const std::vector<CTransactionRef>& transactions)
+{
+    std::vector<uint256> wtxids_copy;


nit: wtxids, this one is not a copy.

src/consensus/validation.h

mzumsande · 2023-07-17T15:15:08Z

src/net_processing.cpp

+     * Memory used: 1.3 MB
+     * FIXME: this filter can probably be smaller, but how much smaller?
+     */
+    CRollingBloomFilter m_recent_rejects_reconsiderable GUARDED_BY(::cs_main){120'000, 0.000'001};


3494f96:
Do we need to adjust the logic in ProcessOrphanTx() too, by inserting there into m_recent_rejects_reconsiderable instead of m_recent_rejects if the reason was low-fee? It currently adds the wtxid of a reconsidered orphan to m_recent_rejects if it fails for policy/fee-related reasons. But if that resolved orphan is itself one of the parent of another orphan we wouldn't consider that (possibly high-fee) child because a parent was rejected.

src/node/txpackagetracker.cpp

mzumsande · 2023-07-17T19:24:05Z

src/net_processing.cpp

@@ -5077,6 +5131,13 @@ void PeerManagerImpl::ProcessMessage(CNode& pfrom, const std::string& msg_type,
                    // If we receive a NOTFOUND message for a tx we requested, mark the announcement for it as
                    // completed in TxRequestTracker.
                    m_txrequest.ReceivedResponse(pfrom.GetId(), inv.hash);
+                } else if (inv.IsMsgAncPkgInfo() && m_enable_package_relay) {
+                    if (!m_txpackagetracker->PkgInfoAllowed(pfrom.GetId(), inv.hash, node::PKG_RELAY_ANCPKG)) {
+                        LogPrint(BCLog::NET, "\nUnsolicited ancpkginfo sent, disconnecting peer=%d\n", pfrom.GetId());


It's an unsolicited NOTFOUND of type MSG_ANCPKGINFO, would be good to distinguish between the inv type and the actual ANCPKGINFO message.

mzumsande · 2023-07-17T19:30:00Z

src/node/txpackagetracker.cpp

+        if (!packageinfo_requested.contains(GetPackageInfoRequestId(nodeid, wtxid, version))) {
+            return false;
+        }
+        orphan_request_tracker.ReceivedResponse(nodeid, wtxid);


PkgInfoAllowed() calling ReceivedResponse() as a side effect is surprising to me. Wouldn't it be better if the caller would also have to explicitly call ForgetPkgInfo() if they want to forget about the package? This is also not mentioned in its doc.

mzumsande · 2023-07-17T20:00:27Z

src/node/txpackagetracker.cpp

+                Assume(info_per_peer.find(nodeid) != info_per_peer.end());
+                // Add the orphan's wtxid as-is.
+                LogPrint(BCLog::TXPACKAGES, "\nResolving orphan %s, requesting by ancpkginfo from peer=%d\n", gtxid.GetHash().ToString(), nodeid);
+                results.emplace_back(gtxid);


I think that the splitting into commits is not ideal here: In ae26647, we add logic to return the wtxid, expecting it to be requested by MSG_ANCPKGINFO. But the net_processing code to actually do this is only added in dd6fb13, so that at ae26647, we'd send out a MSG_TX getdata, thus re-requesting a TX we already know. These two things should go together into one commit.

mzumsande · 2023-07-17T20:18:41Z

src/net_processing.cpp

@@ -3440,6 +3457,16 @@ void PeerManagerImpl::ProcessMessage(CNode& pfrom, const std::string& msg_type,

        if (greatest_common_version >= WTXID_RELAY_VERSION) {
            m_connman.PushMessage(&pfrom, msg_maker.Make(NetMsgType::WTXIDRELAY));
+            if (m_enable_package_relay) {
+                m_txpackagetracker->ReceivedVersion(peer->m_id);
+                if (!m_ignore_incoming_txs) {


We should also disable sending "sendpackages" for outgoing block-relay-only connections and probably also feelers, would suggest to just use RejectIncomingTxs().
Also, I think this should be moved up and combined with the m_enable_package_relay check two lines above, because I see no reason to call m_txpackagetracker->ReceivedVersion() in these scenarios.

DrahtBot · 2023-07-20T10:52:10Z

🐙 This pull request conflicts with the target branch and needs rebase.

instagibbs · 2023-08-28T18:00:24Z

I suspect this implementation, with an absurdly high ancestor chain limit being set, would violate the 100 txn limit for getpackagetxns: https://github.com/bitcoin/bips/blob/02ec218c7857ef60914e9a3d383b68caf987f70b/bip-0331.mediawiki#getpkgtxns

glozow · 2023-08-29T09:37:21Z

I suspect this implementation, with an absurdly high ancestor chain limit being set, would violate the 100 txn limit for getpackagetxns: https://github.com/bitcoin/bips/blob/02ec218c7857ef60914e9a3d383b68caf987f70b/bip-0331.mediawiki#getpkgtxns

Are you sure? We still require an ancpkginfo to have (non-configurable) MAX_PACKAGE_COUNT or fewer transactions, otherwise we exit "discarding packageinfo, too many transactions". But I can add a check that the list is <= MAX_PKGTXNS_COUNT prior to sending.

glozow · 2023-08-29T11:00:50Z

Added check that outbound getpkgtxns is <= MAX_PKGTXNS_COUNT. Also changed the combined hash from double-sha256 to single-sha256 (which was changed in the BIP recently).

instagibbs · 2023-09-05T13:07:49Z

Dropping note from offline discussion: probably worthwhile to just to advise users that setting ancestor count higher than 25 may end in weird behavior with chains longer than what package relay can support. I don't know of anyone who sets this value higher manually for production usage, and the value can be updated later easily as an implementation detail.

ariard · 2023-09-18T16:56:34Z

src/net_processing.cpp

+     *
+     * Upon receiving an announcement for a transaction, if it exists in this filter, do not
+     * download the txdata. Upon receiving a package info, if it contains a transaction in this
+     * filter, do not download the tx data.


I think it can say do not download "the whole package data", if this is referencing to the check L4415 in src/net_processing.cpp as pkg info itself is discarded.

DrahtBot · 2023-12-18T00:37:09Z

There hasn't been much activity lately and the patch still needs rebase. What is the status here?

Is it still relevant? ➡️ Please solve the conflicts to make it ready for review and to ensure the CI passes.
Is it no longer relevant? ➡️ Please close.
Did the author lose interest or time to work on this? ➡️ Please close it and mark it 'Up for grabs' with the label, so that it can be picked up in the future.

glozow · 2023-12-18T09:45:17Z

Not intended for merge. Not planning on rebasing right now since this should be built on top of cluster mempool and other WIP projects.

DrahtBot · 2024-03-16T00:09:17Z