/root/bitcoin/src/policy/packages.cpp

Source
// Copyright (c) 2021-present The Bitcoin Core developers
// Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.

#include <policy/packages.h>
#include <policy/policy.h>
#include <primitives/transaction.h>
#include <uint256.h>
#include <util/check.h>

#include <algorithm>
#include <cassert>
#include <iterator>
#include <memory>
#include <numeric>

/** IsTopoSortedPackage where a set of txids has been pre-populated. The set is assumed to be correct and
 * is mutated within this function (even if return value is false). */
bool IsTopoSortedPackage(const Package& txns, std::unordered_set<Txid, SaltedTxidHasher>& later_txids)
{
    // Avoid misusing this function: later_txids should contain the txids of txns.
    Assume(txns.size() == later_txids.size());

    // later_txids always contains the txids of this transaction and the ones that come later in
    // txns. If any transaction's input spends a tx in that set, we've found a parent placed later
    // than its child.
    for (const auto& tx : txns) {
        for (const auto& input : tx->vin) {
            if (later_txids.contains(input.prevout.hash)) {
                // The parent is a subsequent transaction in the package.
                return false;
            }
        }
        // Avoid misusing this function: later_txids must contain every tx.
        Assume(later_txids.erase(tx->GetHash()) == 1);
    }

    // Avoid misusing this function: later_txids should have contained the txids of txns.
    Assume(later_txids.empty());
    return true;
}

bool IsTopoSortedPackage(const Package& txns)
{
    std::unordered_set<Txid, SaltedTxidHasher> later_txids;
    std::transform(txns.cbegin(), txns.cend(), std::inserter(later_txids, later_txids.end()),
                   [](const auto& tx) { return tx->GetHash(); });

    return IsTopoSortedPackage(txns, later_txids);
}

bool IsConsistentPackage(const Package& txns)
{
    // Don't allow any conflicting transactions, i.e. spending the same inputs, in a package.
    std::unordered_set<COutPoint, SaltedOutpointHasher> inputs_seen;
    for (const auto& tx : txns) {
        if (tx->vin.empty()) {
            // This function checks consistency based on inputs, and we can't do that if there are
            // no inputs. Duplicate empty transactions are also not consistent with one another.
            // This doesn't create false negatives, as unconfirmed transactions are not allowed to
            // have no inputs.
            return false;
        }
        for (const auto& input : tx->vin) {
            if (inputs_seen.contains(input.prevout)) {
                // This input is also present in another tx in the package.
                return false;
            }
        }
        // Batch-add all the inputs for a tx at a time. If we added them 1 at a time, we could
        // catch duplicate inputs within a single tx.  This is a more severe, consensus error,
        // and we want to report that from CheckTransaction instead.
        std::transform(tx->vin.cbegin(), tx->vin.cend(), std::inserter(inputs_seen, inputs_seen.end()),
                       [](const auto& input) { return input.prevout; });
    }
    return true;
}

bool IsWellFormedPackage(const Package& txns, PackageValidationState& state)
{
    const unsigned int package_count = txns.size();

    if (package_count > MAX_PACKAGE_COUNT) {
        return state.Invalid(PackageValidationResult::PCKG_POLICY, "package-too-many-transactions");
    }

    const int64_t total_weight = std::accumulate(txns.cbegin(), txns.cend(), 0,
                               [](int64_t sum, const auto& tx) { return sum + GetTransactionWeight(*tx); });
    // If the package only contains 1 tx, it's better to report the policy violation on individual tx weight.
    if (package_count > 1 && total_weight > MAX_PACKAGE_WEIGHT) {
        return state.Invalid(PackageValidationResult::PCKG_POLICY, "package-too-large");
    }

    std::unordered_set<Txid, SaltedTxidHasher> later_txids;
    std::transform(txns.cbegin(), txns.cend(), std::inserter(later_txids, later_txids.end()),
                   [](const auto& tx) { return tx->GetHash(); });

    // Package must not contain any duplicate transactions, which is checked by txid. This also
    // includes transactions with duplicate wtxids and same-txid-different-witness transactions.
    if (later_txids.size() != txns.size()) {
        return state.Invalid(PackageValidationResult::PCKG_POLICY, "package-contains-duplicates");
    }

    // Require the package to be sorted in order of dependency, i.e. parents appear before children.
    // An unsorted package will fail anyway on missing-inputs, but it's better to quit earlier and
    // fail on something less ambiguous (missing-inputs could also be an orphan or trying to
    // spend nonexistent coins).
    if (!IsTopoSortedPackage(txns, later_txids)) {
        return state.Invalid(PackageValidationResult::PCKG_POLICY, "package-not-sorted");
    }

    // Don't allow any conflicting transactions, i.e. spending the same inputs, in a package.
    if (!IsConsistentPackage(txns)) {
        return state.Invalid(PackageValidationResult::PCKG_POLICY, "conflict-in-package");
    }
    return true;
}

bool IsChildWithParents(const Package& package)
{
    assert(std::all_of(package.cbegin(), package.cend(), [](const auto& tx){return tx != nullptr;}));
    if (package.size() < 2) return false;

    // The package is expected to be sorted, so the last transaction is the child.
    const auto& child = package.back();
    std::unordered_set<Txid, SaltedTxidHasher> input_txids;
    std::transform(child->vin.cbegin(), child->vin.cend(),
                   std::inserter(input_txids, input_txids.end()),
                   [](const auto& input) { return input.prevout.hash; });

    // Every transaction must be a parent of the last transaction in the package.
    return std::all_of(package.cbegin(), package.cend() - 1,
                       [&input_txids](const auto& ptx) { return input_txids.contains(ptx->GetHash()); });
}

bool IsChildWithParentsTree(const Package& package)
{
    if (!IsChildWithParents(package)) return false;
    std::unordered_set<Txid, SaltedTxidHasher> parent_txids;
    std::transform(package.cbegin(), package.cend() - 1, std::inserter(parent_txids, parent_txids.end()),
                   [](const auto& ptx) { return ptx->GetHash(); });
    // Each parent must not have an input who is one of the other parents.
    return std::all_of(package.cbegin(), package.cend() - 1, [&](const auto& ptx) {
        for (const auto& input : ptx->vin) {
            if (parent_txids.contains(input.prevout.hash)) return false;
        }
        return true;
    });
}

uint256 GetPackageHash(const std::vector<CTransactionRef>& transactions)
{
    // Create a vector of the wtxids.
    std::vector<Wtxid> wtxids_copy;
    std::transform(transactions.cbegin(), transactions.cend(), std::back_inserter(wtxids_copy),
        [](const auto& tx){ return tx->GetWitnessHash(); });

    // Sort in ascending order
    std::sort(wtxids_copy.begin(), wtxids_copy.end(), [](const auto& lhs, const auto& rhs) {
        return std::lexicographical_compare(std::make_reverse_iterator(lhs.end()), std::make_reverse_iterator(lhs.begin()),
                                            std::make_reverse_iterator(rhs.end()), std::make_reverse_iterator(rhs.begin()));
    });

    // Get sha256 hash of the wtxids concatenated in this order
    HashWriter hashwriter;
    for (const auto& wtxid : wtxids_copy) {
        hashwriter << wtxid;
    }
    return hashwriter.GetSHA256();
}

Line	Count	Source
1		// Copyright (c) 2021-present 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		bool IsTopoSortedPackage(const Package& txns, std::unordered_set<Txid, SaltedTxidHasher>& later_txids)
20	1.17M	{
21		// Avoid misusing this function: later_txids should contain the txids of txns.
22	1.17M	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	2.26M	for (const auto& tx : txns) { Branch (27:25): [True: 2.26M, False: 1.17M]
28	15.1M	for (const auto& input : tx->vin) { Branch (28:32): [True: 15.1M, False: 2.26M]
29	15.1M	if (later_txids.contains(input.prevout.hash)) { Branch (29:17): [True: 974, False: 15.1M]
30		// The parent is a subsequent transaction in the package.
31	974	return false;
32	974	}
33	15.1M	}
34		// Avoid misusing this function: later_txids must contain every tx.
35	2.26M	Assume(later_txids.erase(tx->GetHash()) == 1);
36	2.26M	}
37
38		// Avoid misusing this function: later_txids should have contained the txids of txns.
39	1.17M	Assume(later_txids.empty());
40	1.17M	return true;
41	1.17M	}
42
43		bool IsTopoSortedPackage(const Package& txns)
44	0	{
45	0	std::unordered_set<Txid, 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		bool IsConsistentPackage(const Package& txns)
53	1.17M	{
54		// Don't allow any conflicting transactions, i.e. spending the same inputs, in a package.
55	1.17M	std::unordered_set<COutPoint, SaltedOutpointHasher> inputs_seen;
56	2.06M	for (const auto& tx : txns) { Branch (56:25): [True: 2.06M, False: 1.09M]
57	2.06M	if (tx->vin.empty()) { Branch (57:13): [True: 14, False: 2.06M]
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	14	return false;
63	14	}
64	10.5M	for (const auto& input : tx->vin) { Branch (64:32): [True: 10.5M, False: 1.97M]
65	10.5M	if (inputs_seen.contains(input.prevout)) { Branch (65:17): [True: 85.5k, False: 10.4M]
66		// This input is also present in another tx in the package.
67	85.5k	return false;
68	85.5k	}
69	10.5M	}
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	1.97M	std::transform(tx->vin.cbegin(), tx->vin.cend(), std::inserter(inputs_seen, inputs_seen.end()),
74	10.0M	[](const auto& input) { return input.prevout; });
75	1.97M	}
76	1.09M	return true;
77	1.17M	}
78
79		bool IsWellFormedPackage(const Package& txns, PackageValidationState& state)
80	1.21M	{
81	1.21M	const unsigned int package_count = txns.size();
82
83	1.21M	if (package_count > MAX_PACKAGE_COUNT) { Branch (83:9): [True: 1.15k, False: 1.21M]
84	1.15k	return state.Invalid(PackageValidationResult::PCKG_POLICY, "package-too-many-transactions");
85	1.15k	}
86
87	1.21M	const int64_t total_weight = std::accumulate(txns.cbegin(), txns.cend(), 0,
88	2.56M	[](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	1.21M	if (package_count > 1 && total_weight > MAX_PACKAGE_WEIGHT) { Branch (90:9): [True: 599k, False: 611k] Branch (90:30): [True: 1.69k, False: 597k]
91	1.69k	return state.Invalid(PackageValidationResult::PCKG_POLICY, "package-too-large");
92	1.69k	}
93
94	1.20M	std::unordered_set<Txid, SaltedTxidHasher> later_txids;
95	1.20M	std::transform(txns.cbegin(), txns.cend(), std::inserter(later_txids, later_txids.end()),
96	2.52M	[](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	1.20M	if (later_txids.size() != txns.size()) { Branch (100:9): [True: 30.4k, False: 1.17M]
101	30.4k	return state.Invalid(PackageValidationResult::PCKG_POLICY, "package-contains-duplicates");
102	30.4k	}
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	1.17M	if (!IsTopoSortedPackage(txns, later_txids)) { Branch (108:9): [True: 974, False: 1.17M]
109	974	return state.Invalid(PackageValidationResult::PCKG_POLICY, "package-not-sorted");
110	974	}
111
112		// Don't allow any conflicting transactions, i.e. spending the same inputs, in a package.
113	1.17M	if (!IsConsistentPackage(txns)) { Branch (113:9): [True: 85.5k, False: 1.09M]
114	85.5k	return state.Invalid(PackageValidationResult::PCKG_POLICY, "conflict-in-package");
115	85.5k	}
116	1.09M	return true;
117	1.17M	}
118
119		bool IsChildWithParents(const Package& package)
120	424k	{
121	424k	assert(std::all_of(package.cbegin(), package.cend(), [](const auto& tx){return tx != nullptr;})); Branch (121:5): [True: 424k, False: 0]
122	424k	if (package.size() < 2) return false; Branch (122:9): [True: 0, False: 424k]
123
124		// The package is expected to be sorted, so the last transaction is the child.
125	424k	const auto& child = package.back();
126	424k	std::unordered_set<Txid, SaltedTxidHasher> input_txids;
127	424k	std::transform(child->vin.cbegin(), child->vin.cend(),
128	424k	std::inserter(input_txids, input_txids.end()),
129	2.25M	[](const auto& input) { return input.prevout.hash; });
130
131		// Every transaction must be a parent of the last transaction in the package.
132	424k	return std::all_of(package.cbegin(), package.cend() - 1,
133	658k	[&input_txids](const auto& ptx) { return input_txids.contains(ptx->GetHash()); });
134	424k	}
135
136		bool IsChildWithParentsTree(const Package& package)
137	21	{
138	21	if (!IsChildWithParents(package)) return false; Branch (138:9): [True: 21, False: 0]
139	0	std::unordered_set<Txid, 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) { Branch (144:32): [True: 0, False: 0]
145	0	if (parent_txids.contains(input.prevout.hash)) return false; Branch (145:17): [True: 0, False: 0]
146	0	}
147	0	return true;
148	0	});
149	21	}
150
151		uint256 GetPackageHash(const std::vector<CTransactionRef>& transactions)
152	60.6k	{
153		// Create a vector of the wtxids.
154	60.6k	std::vector<Wtxid> wtxids_copy;
155	60.6k	std::transform(transactions.cbegin(), transactions.cend(), std::back_inserter(wtxids_copy),
156	121k	[](const auto& tx){ return tx->GetWitnessHash(); });
157
158		// Sort in ascending order
159	93.1k	std::sort(wtxids_copy.begin(), wtxids_copy.end(), [](const auto& lhs, const auto& rhs) {
160	93.1k	return std::lexicographical_compare(std::make_reverse_iterator(lhs.end()), std::make_reverse_iterator(lhs.begin()),
161	93.1k	std::make_reverse_iterator(rhs.end()), std::make_reverse_iterator(rhs.begin()));
162	93.1k	});
163
164		// Get sha256 hash of the wtxids concatenated in this order
165	60.6k	HashWriter hashwriter;
166	121k	for (const auto& wtxid : wtxids_copy) { Branch (166:28): [True: 121k, False: 60.6k]
167	121k	hashwriter << wtxid;
168	121k	}
169	60.6k	return hashwriter.GetSHA256();
170	60.6k	}

Coverage Report

Created: 2026-09-01 13:35