Merge #12634: [refactor] Make TransactionWithinChainLimit more flexible

f77e1d34fd5f17304ce319b5f962b8005592501a test: Add MempoolAncestryTests (Karl-Johan Alm)
a08d76bcfee6f563a268933357931abe32060668 mempool: Calculate descendant maximum thoroughly (Karl-Johan Alm)
6d3568371eb2559d65a3e2334252d36a262319e8 wallet: Switch to using ancestor/descendant limits (Karl-Johan Alm)
6888195b062c8c58dd776fd10b44b25554eb1f15 wallet: Strictly greater than for ancestor caps (Karl-Johan Alm)
322b12ac4e0a8c892e81a760ff7225619248b74f Remove deprecated TransactionWithinChainLimit (Karl-Johan Alm)
47847515473b054929af0c8de3d54b6672500cab Switch to GetTransactionAncestry() in OutputEligibleForSpending (Karl-Johan Alm)
475a385a80198a46a6d99846f99b968f04e9b470 Add GetTransactionAncestry to CTxMemPool for general purpose chain limit checking (Karl-Johan Alm)
46847d69d2c1cc908fd779daac7884e365955dbd mempool: Fix max descendants check (Karl-Johan Alm)
b9ef21dd727dde33f5bd3c33226b05d07eb12aac mempool: Add explicit max_descendants (Karl-Johan Alm)

Pull request description:

  Currently, `TransactionWithinChainLimit` is restricted to single-output use, and needs to be called every time for different limits. If it is replaced with a chain limit value calculator, that can be called once and reused, and is generally more flexible (see e.g. #12257).

  Update: this PR now corrects usage of max ancestors / max descendants, including calculating the correct max descendant value, as advertised for the two limits.

  ~~This change also makes `nMaxAncestors` signed, as the replacement method will return `-1` for "not in the mempool", which is different from "0", which means "no ancestors/descendants in mempool".~~

  ~~This is a subset of #12257.~~

Tree-SHA512: aa59c849360542362b3126c0e29d44d3d58f11898e277d38c034dc4b86a5b4500f77ac61767599ce878c876b5c446fec9c02699797eb2fa41e530ec863a00cf9

1 files changed, 178 insertions, 0 deletions

diff --git a/src/test/mempool_tests.cpp b/src/test/mempool_tests.cpp
index 5ca243f42e..4070642537 100644
--- a/src/test/mempool_tests.cpp
+++ b/src/test/mempool_tests.cpp
@@ -571,4 +571,182 @@ BOOST_AUTO_TEST_CASE(MempoolSizeLimitTest)
     SetMockTime(0);
 }
 
+inline CTransactionRef make_tx(std::vector<CAmount>&& output_values, std::vector<CTransactionRef>&& inputs=std::vector<CTransactionRef>(), std::vector<uint32_t>&& input_indices=std::vector<uint32_t>())
+{
+    CMutableTransaction tx = CMutableTransaction();
+    tx.vin.resize(inputs.size());
+    tx.vout.resize(output_values.size());
+    for (size_t i = 0; i < inputs.size(); ++i) {
+        tx.vin[i].prevout.hash = inputs[i]->GetHash();
+        tx.vin[i].prevout.n = input_indices.size() > i ? input_indices[i] : 0;
+    }
+    for (size_t i = 0; i < output_values.size(); ++i) {
+        tx.vout[i].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
+        tx.vout[i].nValue = output_values[i];
+    }
+    return MakeTransactionRef(tx);
+}
+
+#define MK_OUTPUTS(amounts...) std::vector<CAmount>{amounts}
+#define MK_INPUTS(txs...) std::vector<CTransactionRef>{txs}
+#define MK_INPUT_IDX(idxes...) std::vector<uint32_t>{idxes}
+
+BOOST_AUTO_TEST_CASE(MempoolAncestryTests)
+{
+    size_t ancestors, descendants;
+
+    CTxMemPool pool;
+    TestMemPoolEntryHelper entry;
+
+    /* Base transaction */
+    //
+    // [tx1]
+    //
+    CTransactionRef tx1 = make_tx(MK_OUTPUTS(10 * COIN));
+    pool.addUnchecked(tx1->GetHash(), entry.Fee(10000LL).FromTx(tx1));
+
+    // Ancestors / descendants should be 1 / 1 (itself / itself)
+    pool.GetTransactionAncestry(tx1->GetHash(), ancestors, descendants);
+    BOOST_CHECK_EQUAL(ancestors, 1ULL);
+    BOOST_CHECK_EQUAL(descendants, 1ULL);
+
+    /* Child transaction */
+    //
+    // [tx1].0 <- [tx2]
+    //
+    CTransactionRef tx2 = make_tx(MK_OUTPUTS(495 * CENT, 5 * COIN), MK_INPUTS(tx1));
+    pool.addUnchecked(tx2->GetHash(), entry.Fee(10000LL).FromTx(tx2));
+
+    // Ancestors / descendants should be:
+    // transaction  ancestors   descendants
+    // ============ =========== ===========
+    // tx1          1 (tx1)     2 (tx1,2)
+    // tx2          2 (tx1,2)   2 (tx1,2)
+    pool.GetTransactionAncestry(tx1->GetHash(), ancestors, descendants);
+    BOOST_CHECK_EQUAL(ancestors, 1ULL);
+    BOOST_CHECK_EQUAL(descendants, 2ULL);
+    pool.GetTransactionAncestry(tx2->GetHash(), ancestors, descendants);
+    BOOST_CHECK_EQUAL(ancestors, 2ULL);
+    BOOST_CHECK_EQUAL(descendants, 2ULL);
+
+    /* Grand-child 1 */
+    //
+    // [tx1].0 <- [tx2].0 <- [tx3]
+    //
+    CTransactionRef tx3 = make_tx(MK_OUTPUTS(290 * CENT, 200 * CENT), MK_INPUTS(tx2));
+    pool.addUnchecked(tx3->GetHash(), entry.Fee(10000LL).FromTx(tx3));
+
+    // Ancestors / descendants should be:
+    // transaction  ancestors   descendants
+    // ============ =========== ===========
+    // tx1          1 (tx1)     3 (tx1,2,3)
+    // tx2          2 (tx1,2)   3 (tx1,2,3)
+    // tx3          3 (tx1,2,3) 3 (tx1,2,3)
+    pool.GetTransactionAncestry(tx1->GetHash(), ancestors, descendants);
+    BOOST_CHECK_EQUAL(ancestors, 1ULL);
+    BOOST_CHECK_EQUAL(descendants, 3ULL);
+    pool.GetTransactionAncestry(tx2->GetHash(), ancestors, descendants);
+    BOOST_CHECK_EQUAL(ancestors, 2ULL);
+    BOOST_CHECK_EQUAL(descendants, 3ULL);
+    pool.GetTransactionAncestry(tx3->GetHash(), ancestors, descendants);
+    BOOST_CHECK_EQUAL(ancestors, 3ULL);
+    BOOST_CHECK_EQUAL(descendants, 3ULL);
+
+    /* Grand-child 2 */
+    //
+    // [tx1].0 <- [tx2].0 <- [tx3]
+    //              |
+    //              \---1 <- [tx4]
+    //
+    CTransactionRef tx4 = make_tx(MK_OUTPUTS(290 * CENT, 250 * CENT), MK_INPUTS(tx2), MK_INPUT_IDX(1));
+    pool.addUnchecked(tx4->GetHash(), entry.Fee(10000LL).FromTx(tx4));
+
+    // Ancestors / descendants should be:
+    // transaction  ancestors   descendants
+    // ============ =========== ===========
+    // tx1          1 (tx1)     4 (tx1,2,3,4)
+    // tx2          2 (tx1,2)   4 (tx1,2,3,4)
+    // tx3          3 (tx1,2,3) 4 (tx1,2,3,4)
+    // tx4          3 (tx1,2,4) 4 (tx1,2,3,4)
+    pool.GetTransactionAncestry(tx1->GetHash(), ancestors, descendants);
+    BOOST_CHECK_EQUAL(ancestors, 1ULL);
+    BOOST_CHECK_EQUAL(descendants, 4ULL);
+    pool.GetTransactionAncestry(tx2->GetHash(), ancestors, descendants);
+    BOOST_CHECK_EQUAL(ancestors, 2ULL);
+    BOOST_CHECK_EQUAL(descendants, 4ULL);
+    pool.GetTransactionAncestry(tx3->GetHash(), ancestors, descendants);
+    BOOST_CHECK_EQUAL(ancestors, 3ULL);
+    BOOST_CHECK_EQUAL(descendants, 4ULL);
+    pool.GetTransactionAncestry(tx4->GetHash(), ancestors, descendants);
+    BOOST_CHECK_EQUAL(ancestors, 3ULL);
+    BOOST_CHECK_EQUAL(descendants, 4ULL);
+
+    /* Make an alternate branch that is longer and connect it to tx3 */
+    //
+    // [ty1].0 <- [ty2].0 <- [ty3].0 <- [ty4].0 <- [ty5].0
+    //                                              |
+    // [tx1].0 <- [tx2].0 <- [tx3].0 <- [ty6] --->--/
+    //              |
+    //              \---1 <- [tx4]
+    //
+    CTransactionRef ty1, ty2, ty3, ty4, ty5;
+    CTransactionRef* ty[5] = {&ty1, &ty2, &ty3, &ty4, &ty5};
+    CAmount v = 5 * COIN;
+    for (uint64_t i = 0; i < 5; i++) {
+        CTransactionRef& tyi = *ty[i];
+        tyi = make_tx(MK_OUTPUTS(v), i > 0 ? MK_INPUTS(*ty[i-1]) : std::vector<CTransactionRef>());
+        v -= 50 * CENT;
+        pool.addUnchecked(tyi->GetHash(), entry.Fee(10000LL).FromTx(tyi));
+        pool.GetTransactionAncestry(tyi->GetHash(), ancestors, descendants);
+        BOOST_CHECK_EQUAL(ancestors, i+1);
+        BOOST_CHECK_EQUAL(descendants, i+1);
+    }
+    CTransactionRef ty6 = make_tx(MK_OUTPUTS(5 * COIN), MK_INPUTS(tx3, ty5));
+    pool.addUnchecked(ty6->GetHash(), entry.Fee(10000LL).FromTx(ty6));
+
+    // Ancestors / descendants should be:
+    // transaction  ancestors           descendants
+    // ============ =================== ===========
+    // tx1          1 (tx1)             5 (tx1,2,3,4, ty6)
+    // tx2          2 (tx1,2)           5 (tx1,2,3,4, ty6)
+    // tx3          3 (tx1,2,3)         5 (tx1,2,3,4, ty6)
+    // tx4          3 (tx1,2,4)         5 (tx1,2,3,4, ty6)
+    // ty1          1 (ty1)             6 (ty1,2,3,4,5,6)
+    // ty2          2 (ty1,2)           6 (ty1,2,3,4,5,6)
+    // ty3          3 (ty1,2,3)         6 (ty1,2,3,4,5,6)
+    // ty4          4 (y1234)           6 (ty1,2,3,4,5,6)
+    // ty5          5 (y12345)          6 (ty1,2,3,4,5,6)
+    // ty6          9 (tx123, ty123456) 6 (ty1,2,3,4,5,6)
+    pool.GetTransactionAncestry(tx1->GetHash(), ancestors, descendants);
+    BOOST_CHECK_EQUAL(ancestors, 1ULL);
+    BOOST_CHECK_EQUAL(descendants, 5ULL);
+    pool.GetTransactionAncestry(tx2->GetHash(), ancestors, descendants);
+    BOOST_CHECK_EQUAL(ancestors, 2ULL);
+    BOOST_CHECK_EQUAL(descendants, 5ULL);
+    pool.GetTransactionAncestry(tx3->GetHash(), ancestors, descendants);
+    BOOST_CHECK_EQUAL(ancestors, 3ULL);
+    BOOST_CHECK_EQUAL(descendants, 5ULL);
+    pool.GetTransactionAncestry(tx4->GetHash(), ancestors, descendants);
+    BOOST_CHECK_EQUAL(ancestors, 3ULL);
+    BOOST_CHECK_EQUAL(descendants, 5ULL);
+    pool.GetTransactionAncestry(ty1->GetHash(), ancestors, descendants);
+    BOOST_CHECK_EQUAL(ancestors, 1ULL);
+    BOOST_CHECK_EQUAL(descendants, 6ULL);
+    pool.GetTransactionAncestry(ty2->GetHash(), ancestors, descendants);
+    BOOST_CHECK_EQUAL(ancestors, 2ULL);
+    BOOST_CHECK_EQUAL(descendants, 6ULL);
+    pool.GetTransactionAncestry(ty3->GetHash(), ancestors, descendants);
+    BOOST_CHECK_EQUAL(ancestors, 3ULL);
+    BOOST_CHECK_EQUAL(descendants, 6ULL);
+    pool.GetTransactionAncestry(ty4->GetHash(), ancestors, descendants);
+    BOOST_CHECK_EQUAL(ancestors, 4ULL);
+    BOOST_CHECK_EQUAL(descendants, 6ULL);
+    pool.GetTransactionAncestry(ty5->GetHash(), ancestors, descendants);
+    BOOST_CHECK_EQUAL(ancestors, 5ULL);
+    BOOST_CHECK_EQUAL(descendants, 6ULL);
+    pool.GetTransactionAncestry(ty6->GetHash(), ancestors, descendants);
+    BOOST_CHECK_EQUAL(ancestors, 9ULL);
+    BOOST_CHECK_EQUAL(descendants, 6ULL);
+}
+
 BOOST_AUTO_TEST_SUITE_END()