Merge bitcoin/bitcoin#28970: p2p: opportunistically accept 1-parent-1-child packages

e518a8bf8abf3d7b83c9013f56d0dca18ae04d6f [functional test] opportunistic 1p1c package submission (glozow)
87c5c524d63c833cf490c7f2f73d72695ad480df [p2p] opportunistically accept 1-parent-1-child packages (glozow)
6c51e1d7d021ed6523107a6db87a865aaa8fc4c9 [p2p] add separate rejections cache for reconsiderable txns (glozow)
410ebd6efaf20fe4715c9b825103b74db69f35ac [fuzz] break out parent functions and add GetChildrenFrom* coverage (glozow)
d095316c1c23e9460dfbd9fdbaf292063adcd080 [unit test] TxOrphanage::GetChildrenFrom* (glozow)
2f51cd680fb4323f1c792dae37d4c4e0e0e35804 [txorphanage] add method to get all orphans spending a tx (glozow)
092c978a42e8f4a02291b994713505ba8aac8b28 [txpackages] add canonical way to get hash of package (glozow)
c3c1e15831c463df7968b028a77e787da7e6256d [doc] restore comment about why we check if ptx HasWitness before caching rejected txid (glozow)
6f4da19cc3b1b7cd23cb4be95a6bb9acb79eb3bf guard against MempoolAcceptResult::m_replaced_transactions (glozow)

Pull request description:

  This enables 1p1c packages to propagate in the "happy case" (i.e. not reliable if there are adversaries) and contains a lot of package relay-related code. See https://github.com/bitcoin/bitcoin/issues/27463 for overall package relay tracking.

  Rationale: This is "non-robust 1-parent-1-child package relay" which is immediately useful.
  - Relaying 1-parent-1-child CPFP when mempool min feerate is high would be a subset of all package relay use cases, but a pretty significant improvement over what we have today, where such transactions don't propagate at all. [1]
  - Today, a miner can run this with a normal/small maxmempool to get revenue from 1p1c CPFP'd transactions without losing out on the ones with parents below mempool minimum feerate.
  - The majority of this code is useful for building more featureful/robust package relay e.g. see the code in #27742.

  The first 2 commits are followups from #29619:
  - https://github.com/bitcoin/bitcoin/pull/29619#discussion_r1523094034
  - https://github.com/bitcoin/bitcoin/pull/29619#discussion_r1519819257

  Q: What makes this short of a more full package relay feature?

  (1) it only supports packages in which 1 of the parents needs to be CPFP'd by the child. That includes 1-parent-1-child packages and situations in which the other parents already pay for themselves (and are thus in mempool already when the package is submitted). More general package relay is a future improvement that requires more engineering in mempool and validation - see #27463.

  (2) We rely on having kept the child in orphanage, and don't make any attempt to protect it while we wait to receive the parent. If we are experiencing a lot of orphanage churn (e.g. an adversary is purposefully sending us a lot of transactions with missing inputs), we will fail to submit packages. This limitation has been around for 12+ years, see #27742 which adds a token bucket scheme for protecting package-related orphans at a limited rate per peer.

  (3) Our orphan-handling logic is somewhat opportunistic; we don't make much effort to resolve an orphan beyond asking the child's sender for the parents. This means we may miss packages if the first sender fails to give us the parent (intentionally or unintentionally). To make this more robust, we need receiver-side logic to retry orphan resolution with multiple peers. This is also an existing problem which has a proposed solution in #28031.

  [1]: see this writeup and its links https://github.com/bitcoin/bips/blob/02ec218c7857ef60914e9a3d383b68caf987f70b/bip-0331.mediawiki#propagate-high-feerate-transactions

ACKs for top commit:
  sr-gi:
    tACK e518a8bf8abf3d7b83c9013f56d0dca18ae04d6f
  instagibbs:
    reACK e518a8bf8abf3d7b83c9013f56d0dca18ae04d6f
  theStack:
    Code-review ACK e518a8bf8abf3d7b83c9013f56d0dca18ae04d6f :package:
  dergoegge:
    light Code review ACK e518a8bf8abf3d7b83c9013f56d0dca18ae04d6f
  achow101:
    ACK e518a8bf8abf3d7b83c9013f56d0dca18ae04d6f

Tree-SHA512: 632579fbe7160cb763bbec6d82ca0dab484d5dbbc7aea90c187c0b9833b8d7c1e5d13b8587379edd3a3b4a02a5a1809020369e9cd09a4ebaf729921f65c15943

1 files changed, 97 insertions, 1 deletions

diff --git a/src/test/txpackage_tests.cpp b/src/test/txpackage_tests.cpp
index b948ea8acb..8112f5f685 100644
--- a/src/test/txpackage_tests.cpp
+++ b/src/test/txpackage_tests.cpp
@@ -8,9 +8,12 @@
 #include <policy/policy.h>
 #include <primitives/transaction.h>
 #include <script/script.h>
+#include <serialize.h>
+#include <streams.h>
 #include <test/util/random.h>
 #include <test/util/script.h>
 #include <test/util/setup_common.h>
+#include <util/strencodings.h>
 #include <test/util/txmempool.h>
 #include <validation.h>
 
@@ -40,6 +43,93 @@ inline CTransactionRef create_placeholder_tx(size_t num_inputs, size_t num_outpu
     return MakeTransactionRef(mtx);
 }
 
+// Create a Wtxid from a hex string
+inline Wtxid WtxidFromString(std::string_view str)
+{
+    return Wtxid::FromUint256(uint256S(str.data()));
+}
+
+BOOST_FIXTURE_TEST_CASE(package_hash_tests, TestChain100Setup)
+{
+    // Random real segwit transaction
+    DataStream stream_1{
+        ParseHex("02000000000101964b8aa63509579ca6086e6012eeaa4c2f4dd1e283da29b67c8eea38b3c6fd220000000000fdffffff0294c618000000000017a9145afbbb42f4e83312666d0697f9e66259912ecde38768fa2c0000000000160014897388a0889390fd0e153a22bb2cf9d8f019faf50247304402200547406380719f84d68cf4e96cc3e4a1688309ef475b150be2b471c70ea562aa02206d255f5acc40fd95981874d77201d2eb07883657ce1c796513f32b6079545cdf0121023ae77335cefcb5ab4c1dc1fb0d2acfece184e593727d7d5906c78e564c7c11d125cf0c00"),
+    };
+    CTransaction tx_1(deserialize, TX_WITH_WITNESS, stream_1);
+    CTransactionRef ptx_1{MakeTransactionRef(tx_1)};
+
+    // Random real nonsegwit transaction
+    DataStream stream_2{
+        ParseHex("01000000010b26e9b7735eb6aabdf358bab62f9816a21ba9ebdb719d5299e88607d722c190000000008b4830450220070aca44506c5cef3a16ed519d7c3c39f8aab192c4e1c90d065f37b8a4af6141022100a8e160b856c2d43d27d8fba71e5aef6405b8643ac4cb7cb3c462aced7f14711a0141046d11fee51b0e60666d5049a9101a72741df480b96ee26488a4d3466b95c9a40ac5eeef87e10a5cd336c19a84565f80fa6c547957b7700ff4dfbdefe76036c339ffffffff021bff3d11000000001976a91404943fdd508053c75000106d3bc6e2754dbcff1988ac2f15de00000000001976a914a266436d2965547608b9e15d9032a7b9d64fa43188ac00000000"),
+    };
+    CTransaction tx_2(deserialize, TX_WITH_WITNESS, stream_2);
+    CTransactionRef ptx_2{MakeTransactionRef(tx_2)};
+
+    // Random real segwit transaction
+    DataStream stream_3{
+        ParseHex("0200000000010177862801f77c2c068a70372b4c435ef8dd621291c36a64eb4dd491f02218f5324600000000fdffffff014a0100000000000022512035ea312034cfac01e956a269f3bf147f569c2fbb00180677421262da042290d803402be713325ff285e66b0380f53f2fae0d0fb4e16f378a440fed51ce835061437566729d4883bc917632f3cff474d6384bc8b989961a1d730d4a87ed38ad28bd337b20f1d658c6c138b1c312e072b4446f50f01ae0da03a42e6274f8788aae53416a7fac0063036f7264010118746578742f706c61696e3b636861727365743d7574662d3800357b2270223a226272632d3230222c226f70223a226d696e74222c227469636b223a224342414c222c22616d74223a2236393639227d6821c1f1d658c6c138b1c312e072b4446f50f01ae0da03a42e6274f8788aae53416a7f00000000"),
+    };
+    CTransaction tx_3(deserialize, TX_WITH_WITNESS, stream_3);
+    CTransactionRef ptx_3{MakeTransactionRef(tx_3)};
+
+    // It's easy to see that wtxids are sorted in lexicographical order:
+    Wtxid wtxid_1{WtxidFromString("0x85cd1a31eb38f74ed5742ec9cb546712ab5aaf747de28a9168b53e846cbda17f")};
+    Wtxid wtxid_2{WtxidFromString("0xb4749f017444b051c44dfd2720e88f314ff94f3dd6d56d40ef65854fcd7fff6b")};
+    Wtxid wtxid_3{WtxidFromString("0xe065bac15f62bb4e761d761db928ddee65a47296b2b776785abb912cdec474e3")};
+    BOOST_CHECK_EQUAL(tx_1.GetWitnessHash(), wtxid_1);
+    BOOST_CHECK_EQUAL(tx_2.GetWitnessHash(), wtxid_2);
+    BOOST_CHECK_EQUAL(tx_3.GetWitnessHash(), wtxid_3);
+
+    BOOST_CHECK(wtxid_1.GetHex() < wtxid_2.GetHex());
+    BOOST_CHECK(wtxid_2.GetHex() < wtxid_3.GetHex());
+
+    // The txids are not (we want to test that sorting and hashing use wtxid, not txid):
+    Txid txid_1{TxidFromString("0xbd0f71c1d5e50589063e134fad22053cdae5ab2320db5bf5e540198b0b5a4e69")};
+    Txid txid_2{TxidFromString("0xb4749f017444b051c44dfd2720e88f314ff94f3dd6d56d40ef65854fcd7fff6b")};
+    Txid txid_3{TxidFromString("0xee707be5201160e32c4fc715bec227d1aeea5940fb4295605e7373edce3b1a93")};
+    BOOST_CHECK_EQUAL(tx_1.GetHash(), txid_1);
+    BOOST_CHECK_EQUAL(tx_2.GetHash(), txid_2);
+    BOOST_CHECK_EQUAL(tx_3.GetHash(), txid_3);
+
+    BOOST_CHECK(txid_2.GetHex() < txid_1.GetHex());
+
+    BOOST_CHECK(txid_1.ToUint256() != wtxid_1.ToUint256());
+    BOOST_CHECK(txid_2.ToUint256() == wtxid_2.ToUint256());
+    BOOST_CHECK(txid_3.ToUint256() != wtxid_3.ToUint256());
+
+    // We are testing that both functions compare using GetHex() and not uint256.
+    // (in this pair of wtxids, hex string order != uint256 order)
+    BOOST_CHECK(wtxid_2 < wtxid_1);
+    // (in this pair of wtxids, hex string order == uint256 order)
+    BOOST_CHECK(wtxid_2 < wtxid_3);
+
+    // All permutations of the package containing ptx_1, ptx_2, ptx_3 have the same package hash
+    std::vector<CTransactionRef> package_123{ptx_1, ptx_2, ptx_3};
+    std::vector<CTransactionRef> package_132{ptx_1, ptx_3, ptx_2};
+    std::vector<CTransactionRef> package_231{ptx_2, ptx_3, ptx_1};
+    std::vector<CTransactionRef> package_213{ptx_2, ptx_1, ptx_3};
+    std::vector<CTransactionRef> package_312{ptx_3, ptx_1, ptx_2};
+    std::vector<CTransactionRef> package_321{ptx_3, ptx_2, ptx_1};
+
+    uint256 calculated_hash_123 = (HashWriter() << wtxid_1 << wtxid_2 << wtxid_3).GetSHA256();
+
+    uint256 hash_if_by_txid = (HashWriter() << wtxid_2 << wtxid_1 << wtxid_3).GetSHA256();
+    BOOST_CHECK(hash_if_by_txid != calculated_hash_123);
+
+    uint256 hash_if_use_txid = (HashWriter() << txid_2 << txid_1 << txid_3).GetSHA256();
+    BOOST_CHECK(hash_if_use_txid != calculated_hash_123);
+
+    uint256 hash_if_use_int_order = (HashWriter() << wtxid_2 << wtxid_1 << wtxid_3).GetSHA256();
+    BOOST_CHECK(hash_if_use_int_order != calculated_hash_123);
+
+    BOOST_CHECK_EQUAL(calculated_hash_123, GetPackageHash(package_123));
+    BOOST_CHECK_EQUAL(calculated_hash_123, GetPackageHash(package_132));
+    BOOST_CHECK_EQUAL(calculated_hash_123, GetPackageHash(package_231));
+    BOOST_CHECK_EQUAL(calculated_hash_123, GetPackageHash(package_213));
+    BOOST_CHECK_EQUAL(calculated_hash_123, GetPackageHash(package_312));
+    BOOST_CHECK_EQUAL(calculated_hash_123, GetPackageHash(package_321));
+}
+
 BOOST_FIXTURE_TEST_CASE(package_sanitization_tests, TestChain100Setup)
 {
     // Packages can't have more than 25 transactions.
@@ -190,6 +280,9 @@ BOOST_FIXTURE_TEST_CASE(noncontextual_package_tests, TestChain100Setup)
         BOOST_CHECK_EQUAL(state.GetRejectReason(), "package-not-sorted");
         BOOST_CHECK(IsChildWithParents({tx_parent, tx_child}));
         BOOST_CHECK(IsChildWithParentsTree({tx_parent, tx_child}));
+        BOOST_CHECK(GetPackageHash({tx_parent}) != GetPackageHash({tx_child}));
+        BOOST_CHECK(GetPackageHash({tx_child, tx_child}) != GetPackageHash({tx_child}));
+        BOOST_CHECK(GetPackageHash({tx_child, tx_parent}) != GetPackageHash({tx_child, tx_child}));
     }
 
     // 24 Parents and 1 Child
@@ -450,6 +543,8 @@ BOOST_FIXTURE_TEST_CASE(package_witness_swap_tests, TestChain100Setup)
     BOOST_CHECK_EQUAL(ptx_child1->GetHash(), ptx_child2->GetHash());
     // child1 and child2 have different wtxids
     BOOST_CHECK(ptx_child1->GetWitnessHash() != ptx_child2->GetWitnessHash());
+    // Check that they have different package hashes
+    BOOST_CHECK(GetPackageHash({ptx_parent, ptx_child1}) != GetPackageHash({ptx_parent, ptx_child2}));
 
     // Try submitting Package1{parent, child1} and Package2{parent, child2} where the children are
     // same-txid-different-witness.
@@ -503,7 +598,8 @@ BOOST_FIXTURE_TEST_CASE(package_witness_swap_tests, TestChain100Setup)
                                                         /*output_destination=*/grandchild_locking_script,
                                                         /*output_amount=*/CAmount(47 * COIN), /*submit=*/false);
     CTransactionRef ptx_grandchild = MakeTransactionRef(mtx_grandchild);
-
+    // Check that they have different package hashes
+    BOOST_CHECK(GetPackageHash({ptx_child1, ptx_grandchild}) != GetPackageHash({ptx_child2, ptx_grandchild}));
     // We already submitted child1 above.
     {
         Package package_child2_grandchild{ptx_child2, ptx_grandchild};