LCOV - code coverage report
Current view: top level - src/policy - packages.cpp (source / functions) Hit Total Coverage
Test: fuzz_coverage.info Lines: 51 69 73.9 %
Date: 2023-11-12 01:39:15 Functions: 10 15 66.7 %
Branches: 55 102 53.9 %

           Branch data     Line data    Source code
       1                 :            : // Copyright (c) 2021-2022 The Bitcoin Core developers
       2                 :            : // Distributed under the MIT software license, see the accompanying
       3                 :            : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
       4                 :            : 
       5                 :            : #include <policy/packages.h>
       6                 :            : #include <policy/policy.h>
       7                 :            : #include <primitives/transaction.h>
       8                 :            : #include <uint256.h>
       9                 :            : #include <util/check.h>
      10                 :            : 
      11                 :            : #include <algorithm>
      12                 :            : #include <cassert>
      13                 :            : #include <iterator>
      14                 :            : #include <memory>
      15                 :            : #include <numeric>
      16                 :            : 
      17                 :            : /** IsTopoSortedPackage where a set of txids has been pre-populated. The set is assumed to be correct and
      18                 :            :  * is mutated within this function (even if return value is false). */
      19                 :      21827 : bool IsTopoSortedPackage(const Package& txns, std::unordered_set<uint256, SaltedTxidHasher>& later_txids)
      20                 :            : {
      21                 :            :     // Avoid misusing this function: later_txids should contain the txids of txns.
      22                 :      21827 :     Assume(txns.size() == later_txids.size());
      23                 :            : 
      24                 :            :     // later_txids always contains the txids of this transaction and the ones that come later in
      25                 :            :     // txns. If any transaction's input spends a tx in that set, we've found a parent placed later
      26                 :            :     // than its child.
      27         [ +  + ]:      57585 :     for (const auto& tx : txns) {
      28         [ +  + ]:     170971 :         for (const auto& input : tx->vin) {
      29         [ +  + ]:     135213 :             if (later_txids.find(input.prevout.hash) != later_txids.end()) {
      30                 :            :                 // The parent is a subsequent transaction in the package.
      31                 :          6 :                 return false;
      32                 :            :             }
      33                 :            :         }
      34                 :            :         // Avoid misusing this function: later_txids must contain every tx.
      35                 :      35758 :         Assume(later_txids.erase(tx->GetHash()) == 1);
      36                 :            :     }
      37                 :            : 
      38                 :            :     // Avoid misusing this function: later_txids should have contained the txids of txns.
      39                 :      21821 :     Assume(later_txids.empty());
      40                 :      21821 :     return true;
      41                 :      21827 : }
      42                 :            : 
      43                 :          0 : bool IsTopoSortedPackage(const Package& txns)
      44                 :            : {
      45                 :          0 :     std::unordered_set<uint256, SaltedTxidHasher> later_txids;
      46 [ #  # ][ #  # ]:          0 :     std::transform(txns.cbegin(), txns.cend(), std::inserter(later_txids, later_txids.end()),
      47                 :          0 :                    [](const auto& tx) { return tx->GetHash(); });
      48                 :            : 
      49         [ #  # ]:          0 :     return IsTopoSortedPackage(txns, later_txids);
      50                 :          0 : }
      51                 :            : 
      52                 :      21821 : bool IsConsistentPackage(const Package& txns)
      53                 :            : {
      54                 :            :     // Don't allow any conflicting transactions, i.e. spending the same inputs, in a package.
      55                 :      21821 :     std::unordered_set<COutPoint, SaltedOutpointHasher> inputs_seen;
      56         [ +  + ]:      55324 :     for (const auto& tx : txns) {
      57         [ +  - ]:      35637 :         if (tx->vin.empty()) {
      58                 :            :             // This function checks consistency based on inputs, and we can't do that if there are
      59                 :            :             // no inputs. Duplicate empty transactions are also not consistent with one another.
      60                 :            :             // This doesn't create false negatives, as unconfirmed transactions are not allowed to
      61                 :            :             // have no inputs.
      62                 :          0 :             return false;
      63                 :            :         }
      64         [ +  + ]:     161491 :         for (const auto& input : tx->vin) {
      65 [ +  - ][ +  + ]:     127988 :             if (inputs_seen.find(input.prevout) != inputs_seen.end()) {
      66                 :            :                 // This input is also present in another tx in the package.
      67                 :       2134 :                 return false;
      68                 :            :             }
      69                 :            :         }
      70                 :            :         // Batch-add all the inputs for a tx at a time. If we added them 1 at a time, we could
      71                 :            :         // catch duplicate inputs within a single tx.  This is a more severe, consensus error,
      72                 :            :         // and we want to report that from CheckTransaction instead.
      73 [ +  - ][ +  - ]:      33503 :         std::transform(tx->vin.cbegin(), tx->vin.cend(), std::inserter(inputs_seen, inputs_seen.end()),
      74                 :     115087 :                        [](const auto& input) { return input.prevout; });
      75                 :            :     }
      76                 :      19687 :     return true;
      77                 :      21821 : }
      78                 :            : 
      79                 :      22132 : bool IsWellFormedPackage(const Package& txns, PackageValidationState& state, bool require_sorted)
      80                 :            : {
      81                 :      22132 :     const unsigned int package_count = txns.size();
      82                 :            : 
      83         [ +  + ]:      22132 :     if (package_count > MAX_PACKAGE_COUNT) {
      84 [ +  - ][ +  - ]:         42 :         return state.Invalid(PackageValidationResult::PCKG_POLICY, "package-too-many-transactions");
                 [ +  - ]
      85                 :            :     }
      86                 :            : 
      87                 :      22090 :     const int64_t total_weight = std::accumulate(txns.cbegin(), txns.cend(), 0,
      88                 :      39991 :                                [](int64_t sum, const auto& tx) { return sum + GetTransactionWeight(*tx); });
      89                 :            :     // If the package only contains 1 tx, it's better to report the policy violation on individual tx weight.
      90 [ +  + ][ +  + ]:      22090 :     if (package_count > 1 && total_weight > MAX_PACKAGE_WEIGHT) {
      91 [ +  - ][ +  - ]:         37 :         return state.Invalid(PackageValidationResult::PCKG_POLICY, "package-too-large");
                 [ +  - ]
      92                 :            :     }
      93                 :            : 
      94                 :      22053 :     std::unordered_set<uint256, SaltedTxidHasher> later_txids;
      95 [ +  - ][ +  - ]:      22053 :     std::transform(txns.cbegin(), txns.cend(), std::inserter(later_txids, later_txids.end()),
      96                 :      39188 :                    [](const auto& tx) { return tx->GetHash(); });
      97                 :            : 
      98                 :            :     // Package must not contain any duplicate transactions, which is checked by txid. This also
      99                 :            :     // includes transactions with duplicate wtxids and same-txid-different-witness transactions.
     100         [ +  + ]:      22053 :     if (later_txids.size() != txns.size()) {
     101 [ +  - ][ +  - ]:        226 :         return state.Invalid(PackageValidationResult::PCKG_POLICY, "package-contains-duplicates");
                 [ +  - ]
     102                 :            :     }
     103                 :            : 
     104                 :            :     // Require the package to be sorted in order of dependency, i.e. parents appear before children.
     105                 :            :     // An unsorted package will fail anyway on missing-inputs, but it's better to quit earlier and
     106                 :            :     // fail on something less ambiguous (missing-inputs could also be an orphan or trying to
     107                 :            :     // spend nonexistent coins).
     108 [ +  - ][ +  - ]:      21827 :     if (require_sorted && !IsTopoSortedPackage(txns, later_txids)) {
                 [ +  + ]
     109 [ +  - ][ +  - ]:          6 :         return state.Invalid(PackageValidationResult::PCKG_POLICY, "package-not-sorted");
                 [ -  + ]
     110                 :            :     }
     111                 :            : 
     112                 :            :     // Don't allow any conflicting transactions, i.e. spending the same inputs, in a package.
     113 [ +  - ][ +  + ]:      21821 :     if (!IsConsistentPackage(txns)) {
     114 [ +  - ][ +  - ]:       2134 :         return state.Invalid(PackageValidationResult::PCKG_POLICY, "conflict-in-package");
                 [ +  - ]
     115                 :            :     }
     116                 :      19687 :     return true;
     117                 :      22132 : }
     118                 :            : 
     119                 :      10310 : bool IsChildWithParents(const Package& package)
     120                 :            : {
     121         [ +  - ]:      29854 :     assert(std::all_of(package.cbegin(), package.cend(), [](const auto& tx){return tx != nullptr;}));
     122         [ +  + ]:      10310 :     if (package.size() < 2) return false;
     123                 :            : 
     124                 :            :     // The package is expected to be sorted, so the last transaction is the child.
     125                 :       8623 :     const auto& child = package.back();
     126                 :       8623 :     std::unordered_set<uint256, SaltedTxidHasher> input_txids;
     127         [ +  - ]:       8623 :     std::transform(child->vin.cbegin(), child->vin.cend(),
     128         [ +  - ]:       8623 :                    std::inserter(input_txids, input_txids.end()),
     129                 :      34302 :                    [](const auto& input) { return input.prevout.hash; });
     130                 :            : 
     131                 :            :     // Every transaction must be a parent of the last transaction in the package.
     132 [ +  - ][ +  - ]:      17246 :     return std::all_of(package.cbegin(), package.cend() - 1,
     133                 :      17857 :                        [&input_txids](const auto& ptx) { return input_txids.count(ptx->GetHash()) > 0; });
     134                 :      10310 : }
     135                 :            : 
     136                 :          0 : bool IsChildWithParentsTree(const Package& package)
     137                 :            : {
     138         [ #  # ]:          0 :     if (!IsChildWithParents(package)) return false;
     139                 :          0 :     std::unordered_set<uint256, SaltedTxidHasher> parent_txids;
     140 [ #  # ][ #  # ]:          0 :     std::transform(package.cbegin(), package.cend() - 1, std::inserter(parent_txids, parent_txids.end()),
     141                 :          0 :                    [](const auto& ptx) { return ptx->GetHash(); });
     142                 :            :     // Each parent must not have an input who is one of the other parents.
     143         [ #  # ]:          0 :     return std::all_of(package.cbegin(), package.cend() - 1, [&](const auto& ptx) {
     144         [ #  # ]:          0 :         for (const auto& input : ptx->vin) {
     145         [ #  # ]:          0 :             if (parent_txids.count(input.prevout.hash) > 0) return false;
     146                 :            :         }
     147                 :          0 :         return true;
     148                 :          0 :     });
     149                 :          0 : }

Generated by: LCOV version 1.14