READ THE CODE

Inside Bitcoin

The code behind the network, with room to understand it.

Stable release v32.1bitcoin/bitcoin · f0de87f04062 ↗3,020 source files · 47.5 MB stored on the server340 file guides

Release published 2026-10-28 · Snapshot fetched 2026-11-01. Latest stable release at fetch time; development branches and Git history are excluded. Only the selected code window and visible folders load here.

38,314 bytes · SHA-256 bb9482549c8a686d… · View upstream ↗

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 <node/txorphanage.h>
6
7#include <consensus/validation.h>
8#include <policy/policy.h>
9#include <primitives/transaction.h>
10#include <util/feefrac.h>
11#include <util/hasher.h>
12#include <util/log.h>
13#include <util/time.h>
14
15#include <boost/multi_index/indexed_by.hpp>
16#include <boost/multi_index/ordered_index.hpp>
17#include <boost/multi_index/tag.hpp>
18#include <boost/multi_index_container.hpp>
19
20#include <cassert>
21#include <cmath>
22#include <unordered_map>
23
24namespace node {
25/** Minimum NodeId for lower_bound lookups (in practice, NodeIds start at 0). */
26static constexpr NodeId MIN_PEER{std::numeric_limits<NodeId>::min()};
27/** Maximum NodeId for upper_bound lookups. */
28static constexpr NodeId MAX_PEER{std::numeric_limits<NodeId>::max()};
29class TxOrphanageImpl final : public TxOrphanage {
30    // Type alias for sequence numbers
31    using SequenceNumber = uint64_t;
32    /** Global sequence number, increment each time an announcement is added. */
33    SequenceNumber m_current_sequence{0};
34
35    /** One orphan announcement. Each announcement (i.e. combination of wtxid, nodeid) is unique. There may be multiple
36     * announcements for the same tx, and multiple transactions with the same txid but different wtxid are possible. */
37    struct Announcement
38    {
39        const CTransactionRef m_tx;
40        /** Which peer announced this tx */
41        const NodeId m_announcer;
42        /** What order this transaction entered the orphanage. */
43        const SequenceNumber m_entry_sequence;
44        /** Whether this tx should be reconsidered. Always starts out false. A peer's workset is the collection of all
45         * announcements with m_reconsider=true. */
46        bool m_reconsider{false};
47
48        Announcement(const CTransactionRef& tx, NodeId peer, SequenceNumber seq) :
49            m_tx{tx}, m_announcer{peer}, m_entry_sequence{seq}
50        { }
51
52        /** Get an approximation for "memory usage". The total memory is a function of the memory used to store the
53         * transaction itself, each entry in m_orphans, and each entry in m_outpoint_to_orphan_wtxids. We use weight because
54         * it is often higher than the actual memory usage of the transaction. This metric conveniently encompasses
55         * m_outpoint_to_orphan_wtxids usage since input data does not get the witness discount, and makes it easier to
56         * reason about each peer's limits using well-understood transaction attributes. */
57        TxOrphanage::Usage GetMemUsage()  const {
58            return GetTransactionWeight(*m_tx);
59        }
60
61        /** Get an approximation of how much this transaction contributes to latency in EraseForBlock and EraseForPeer.
62         * The computation time is a function of the number of entries in m_orphans (thus 1 per announcement) and the
63         * number of entries in m_outpoint_to_orphan_wtxids (thus an additional 1 for every 10 inputs). Transactions with a
64         * small number of inputs (9 or fewer) are counted as 1 to make it easier to reason about each peer's limits in
65         * terms of "normal" transactions. */
66        TxOrphanage::Count GetLatencyScore() const {
67            return 1 + (m_tx->vin.size() / 10);
68        }
69    };
70
71    // Index by wtxid, then peer
72    struct ByWtxid {};
73    using ByWtxidView = std::tuple<Wtxid, NodeId>;
74    struct WtxidExtractor
75    {
76        using result_type = ByWtxidView;
77        result_type operator()(const Announcement& ann) const
78        {
79            return ByWtxidView{ann.m_tx->GetWitnessHash(), ann.m_announcer};
80        }
81    };
82
83    // Sort by peer, then by whether it is ready to reconsider, then by recency.
84    struct ByPeer {};
85    using ByPeerView = std::tuple<NodeId, bool, SequenceNumber>;
86    struct ByPeerViewExtractor {
87        using result_type = ByPeerView;
88        result_type operator()(const Announcement& ann) const
89        {
90            return ByPeerView{ann.m_announcer, ann.m_reconsider, ann.m_entry_sequence};
91        }
92    };
93
94    using AnnouncementMap = boost::multi_index::multi_index_container<
95        Announcement,
96        boost::multi_index::indexed_by<
97            boost::multi_index::ordered_unique<boost::multi_index::tag<ByWtxid>, WtxidExtractor>,
98            boost::multi_index::ordered_unique<boost::multi_index::tag<ByPeer>, ByPeerViewExtractor>
99        >
100    >;
101    template<typename Tag>
102    using Iter = typename AnnouncementMap::index<Tag>::type::iterator;
103    AnnouncementMap m_orphans;
104
105    const TxOrphanage::Count m_max_global_latency_score{DEFAULT_MAX_ORPHANAGE_LATENCY_SCORE};
106    const TxOrphanage::Usage m_reserved_usage_per_peer{DEFAULT_RESERVED_ORPHAN_WEIGHT_PER_PEER};
107
108    /** Number of unique orphans by wtxid. Less than or equal to the number of entries in m_orphans. */
109    TxOrphanage::Count m_unique_orphans{0};
110
111    /** Memory used by orphans (see Announcement::GetMemUsage()), deduplicated by wtxid. */
112    TxOrphanage::Usage m_unique_orphan_usage{0};
113
114    /** The sum of each unique transaction's latency scores including the inputs only (see Announcement::GetLatencyScore
115     * but subtract 1 for the announcements themselves). The total orphanage's latency score is given by this value +
116     * the number of entries in m_orphans. */
117    TxOrphanage::Count m_unique_rounded_input_scores{0};
118
119    /** Index from the parents' outputs to wtxids that exist in m_orphans. Used to find children of
120     * a transaction that can be reconsidered and to remove entries that conflict with a block.*/
121    std::unordered_map<COutPoint, std::set<Wtxid>, SaltedOutpointHasher> m_outpoint_to_orphan_wtxids;
122
123    /** Set of Wtxids for which (exactly) one announcement with m_reconsider=true exists. */
124    std::set<Wtxid> m_reconsiderable_wtxids;
125
126    struct PeerDoSInfo {
127        TxOrphanage::Usage m_total_usage{0};
128        TxOrphanage::Count m_count_announcements{0};
129        TxOrphanage::Count m_total_latency_score{0};
130        bool operator==(const PeerDoSInfo& other) const
131        {
132            return m_total_usage == other.m_total_usage &&
133                   m_count_announcements == other.m_count_announcements &&
134                   m_total_latency_score == other.m_total_latency_score;
135        }
136        void Add(const Announcement& ann)
137        {
138            m_total_usage += ann.GetMemUsage();
139            m_total_latency_score += ann.GetLatencyScore();
140            m_count_announcements += 1;
141        }
142        bool Subtract(const Announcement& ann)
143        {
144            Assume(m_total_usage >= ann.GetMemUsage());
145            Assume(m_total_latency_score >= ann.GetLatencyScore());
146            Assume(m_count_announcements >= 1);
147
148            m_total_usage -= ann.GetMemUsage();
149            m_total_latency_score -= ann.GetLatencyScore();
150            m_count_announcements -= 1;
151            return m_count_announcements == 0;
152        }
153        /** There are 2 DoS scores:
154        * - Latency score (ratio of total latency score / max allowed latency score)
155        * - Memory score (ratio of total memory usage / max allowed memory usage).
156        *
157        * If the peer is using more than the allowed for either resource, its DoS score is > 1.
158        * A peer having a DoS score > 1 does not necessarily mean that something is wrong, since we
159        * do not trim unless the orphanage exceeds global limits, but it means that this peer will
160        * be selected for trimming sooner. If the global latency score or global memory usage
161        * limits are exceeded, it must be that there is a peer whose DoS score > 1. */
162        FeeFrac GetDosScore(TxOrphanage::Count max_peer_latency_score, TxOrphanage::Usage max_peer_memory) const
163        {
164            assert(max_peer_latency_score > 0);
165            assert(max_peer_memory > 0);
166            const FeeFrac latency_score(m_total_latency_score, max_peer_latency_score);
167            const FeeFrac mem_score(m_total_usage, max_peer_memory);
168            return std::max<ByRatioNegSize<FeeFrac>>(latency_score, mem_score);
169        }
170    };
171    /** Store per-peer statistics. Used to determine each peer's DoS score. The size of this map is used to determine the
172     * number of peers and thus global {latency score, memory} limits. */
173    std::unordered_map<NodeId, PeerDoSInfo> m_peer_orphanage_info;
174
175    /** Erase from m_orphans and update m_peer_orphanage_info. */
176    template<typename Tag>
177    void Erase(Iter<Tag> it);
178
179    /** Erase by wtxid. */
180    bool EraseTxInternal(const Wtxid& wtxid);
181
182    /** Check if there is exactly one announcement with the same wtxid as it. */
183    bool IsUnique(Iter<ByWtxid> it) const;
184
185    /** Check if the orphanage needs trimming. */
186    bool NeedsTrim() const;
187
188    /** Limit the orphanage to MaxGlobalLatencyScore and MaxGlobalUsage. */
189    void LimitOrphans();
190
191public:
192    TxOrphanageImpl() = default;
193    TxOrphanageImpl(Count max_global_latency_score, Usage reserved_peer_usage) :
194        m_max_global_latency_score{max_global_latency_score},
195        m_reserved_usage_per_peer{reserved_peer_usage}
196    {}
197    ~TxOrphanageImpl() noexcept override = default;
198
199    TxOrphanage::Count CountAnnouncements() const override;
200    TxOrphanage::Count CountUniqueOrphans() const override;
201    TxOrphanage::Count AnnouncementsFromPeer(NodeId peer) const override;
202    TxOrphanage::Count LatencyScoreFromPeer(NodeId peer) const override;
203    TxOrphanage::Usage UsageByPeer(NodeId peer) const override;
204
205    TxOrphanage::Count MaxGlobalLatencyScore() const override;
206    TxOrphanage::Count TotalLatencyScore() const override;
207    TxOrphanage::Usage ReservedPeerUsage() const override;
208
209    /** Maximum allowed (deduplicated) latency score for all transactions (see Announcement::GetLatencyScore()). Dynamic
210     * based on number of peers. Each peer has an equal amount, but the global maximum latency score stays constant. The
211     * number of peers times MaxPeerLatencyScore() (rounded) adds up to MaxGlobalLatencyScore().  As long as every peer's
212     * m_total_latency_score / MaxPeerLatencyScore() < 1, MaxGlobalLatencyScore() is not exceeded. */
213    TxOrphanage::Count MaxPeerLatencyScore() const override;
214
215    /** Maximum allowed (deduplicated) memory usage for all transactions (see Announcement::GetMemUsage()). Dynamic based
216     * on number of peers. More peers means more allowed memory usage. The number of peers times ReservedPeerUsage()
217     * adds up to MaxGlobalUsage(). As long as every peer's m_total_usage / ReservedPeerUsage() < 1, MaxGlobalUsage() is
218     * not exceeded. */
219    TxOrphanage::Usage MaxGlobalUsage() const override;
220
221    bool AddTx(const CTransactionRef& tx, NodeId peer) override;
222    bool AddAnnouncer(const Wtxid& wtxid, NodeId peer) override;
223    CTransactionRef GetTx(const Wtxid& wtxid) const override;
224    bool HaveTx(const Wtxid& wtxid) const override;
225    bool HaveTxFromPeer(const Wtxid& wtxid, NodeId peer) const override;
226    CTransactionRef GetTxToReconsider(NodeId peer) override;
227    bool EraseTx(const Wtxid& wtxid) override;
228    void EraseForPeer(NodeId peer) override;
229    void EraseForBlock(const CBlock& block) override;
230    std::vector<std::pair<Wtxid, NodeId>> AddChildrenToWorkSet(const CTransaction& tx, FastRandomContext& rng) override;
231    bool HaveTxToReconsider(NodeId peer) override;
232    std::vector<CTransactionRef> GetChildrenFromSamePeer(const CTransactionRef& parent, NodeId nodeid) const override;
233    std::vector<OrphanInfo> GetOrphanTransactions() const override;
234    TxOrphanage::Usage TotalOrphanUsage() const override;
235    void SanityCheck() const override;
236};
237
238template<typename Tag>
239void TxOrphanageImpl::Erase(Iter<Tag> it)
240{
241    // Update m_peer_orphanage_info and clean up entries if they point to an empty struct.
242    // This means peers that are not storing any orphans do not have an entry in
243    // m_peer_orphanage_info (they can be added back later if they announce another orphan) and
244    // ensures disconnected peers are not tracked forever.
245    auto peer_it = m_peer_orphanage_info.find(it->m_announcer);
246    Assume(peer_it != m_peer_orphanage_info.end());
247    if (peer_it->second.Subtract(*it)) m_peer_orphanage_info.erase(peer_it);
248
249    if (IsUnique(m_orphans.project<ByWtxid>(it))) {
250        m_unique_orphans -= 1;

src/wallet/receive.cpp

src/wallet/coinselection.cpp

src/consensus/validation.h

src/primitives/transaction.cpp

src/script/descriptor.cpp

src/bitcoin-cli.cpp

src/rpc/blockchain.cpp

src/rpc/rawtransaction.cpp

src/init.cpp

src/crypto/sha256.cpp

src/consensus/merkle.h

src/consensus/tx_check.h

src/consensus/tx_verify.h

src/policy/feerate.h

src/policy/feerate.cpp

src/primitives/transaction_identifier.h

src/chainparamsbase.h

src/chainparamsbase.cpp

src/util/moneystr.cpp

src/crypto/ripemd160.h

src/crypto/sha1.h

src/crypto/sha512.h

src/crypto/hmac_sha256.h

src/crypto/hmac_sha512.h

src/crypto/hmac_sha256.cpp

src/crypto/hmac_sha512.cpp

src/crypto/hkdf_sha256_32.h

src/crypto/hkdf_sha256_32.cpp

src/support/cleanse.h

src/support/cleanse.cpp

src/crypto/siphash.cpp

src/crypto/muhash.h

src/crypto/chacha20.h

src/crypto/poly1305.h

src/crypto/chacha20poly1305.h

src/crypto/chacha20poly1305.cpp

src/util/chaintype.cpp

src/util/obfuscation.h

src/util/byte_units.h

src/util/overflow.h

src/blockencodings.cpp

src/net_permissions.cpp

src/policy/packages.cpp

src/policy/rbf.cpp

src/policy/truc_policy.cpp

src/policy/ephemeral_policy.cpp

src/policy/settings.cpp

src/policy/policy.cpp

src/node/transaction.cpp

src/node/coin.cpp

src/rpc/client.cpp

src/rpc/external_signer.cpp

src/rpc/request.cpp

src/rpc/server_util.cpp

src/rpc/fees.cpp

src/rpc/output_script.cpp

src/rpc/rawtransaction_util.cpp

src/rpc/rawtransaction_util.h

src/rpc/register.h

src/rpc/request.h

src/rpc/server_util.h

src/rpc/protocol.h

src/rpc/server.h

src/rpc/signmessage.cpp

src/rpc/txoutproof.cpp

src/rpc/util.cpp

src/rpc/util.h

src/wallet/rpc/addresses.cpp

src/wallet/rpc/backup.cpp

src/wallet/rpc/coins.cpp

src/wallet/rpc/encrypt.cpp

src/wallet/rpc/signmessage.cpp

src/wallet/rpc/util.cpp

src/wallet/rpc/util.h

src/wallet/coincontrol.cpp

src/wallet/coincontrol.h

src/wallet/context.cpp

src/wallet/context.h

src/wallet/crypter.cpp

src/wallet/crypter.h

src/wallet/db.cpp

src/wallet/export.cpp

src/wallet/external_signer_scriptpubkeyman.cpp

src/wallet/rpc/spend.cpp

src/wallet/rpc/transactions.cpp

src/wallet/rpc/wallet.cpp

src/wallet/feebumper.cpp

src/wallet/feebumper.h

src/index/base.h

src/index/base.cpp

src/index/txindex.h

src/index/txindex.cpp

src/index/txindex_key.h

src/index/txospenderindex.h

src/index/txospenderindex.cpp

src/index/blockfilterindex.h

src/index/blockfilterindex.cpp

src/index/coinstatsindex.h

src/index/coinstatsindex.cpp

src/index/db_key.h

src/index/disktxpos.h

src/kernel/chain.cpp

src/kernel/chain.h

src/kernel/checks.cpp

src/kernel/checks.h

src/kernel/context.cpp

src/kernel/context.h

src/kernel/cs_main.cpp

src/kernel/cs_main.h

src/kernel/disconnected_transactions.cpp

src/kernel/disconnected_transactions.h

src/kernel/mempool_removal_reason.cpp

src/kernel/mempool_removal_reason.h

src/kernel/coinstats.cpp

src/kernel/coinstats.h

src/kernel/chainparams.cpp

src/kernel/chainparams.h

src/wallet/sqlite.cpp

src/wallet/sqlite.h

src/wallet/transaction.cpp

src/wallet/transaction.h

src/wallet/dump.cpp

src/wallet/dump.h

src/wallet/init.cpp

src/wallet/walletutil.cpp

src/wallet/walletutil.h

src/wallet/wallettool.cpp

src/wallet/wallettool.h

src/wallet/export.h

src/wallet/migrate.cpp

src/wallet/migrate.h

src/wallet/db.h

src/wallet/walletdb.cpp

src/wallet/interfaces.cpp

src/wallet/scriptpubkeyman.cpp

src/wallet/scriptpubkeyman.h

src/kernel/bitcoinkernel.cpp

src/kernel/bitcoinkernel.h

src/kernel/bitcoinkernel_wrapper.h

src/node/chainstate.cpp

src/node/chainstate.h

src/node/blockstorage.cpp

src/node/blockstorage.h

src/node/mempool_persist.cpp

src/node/mempool_persist.h

src/node/utxo_snapshot.cpp

src/node/utxo_snapshot.h

src/node/kernel_notifications.cpp

src/node/kernel_notifications.h

src/node/blockmanager_args.cpp

src/kernel/blockmanager_opts.h

src/util/expected.cpp

src/policy/settings.h

src/util/types.h

src/kernel/messagestartchars.h

src/kernel/warning.h

src/util/exception.h

src/common/license_info.h

src/node/coins_view_args.h

src/node/database_args.h

src/util/batchpriority.h

src/util/ui_change_type.h

src/node/coins_view_args.cpp

src/node/peerman_args.h

src/util/serfloat.h

src/node/blockmanager_args.h

src/node/database_args.cpp

src/util/overloaded.h

src/interfaces/types.h

src/node/chainstatemanager_args.h

src/node/minisketchwrapper.h

src/util/macros.h

src/util/syserror.h

src/common/run_command.h

src/util/bytevectorhash.cpp

src/node/mempool_persist_args.cpp

src/util/exec.h

src/util/rbf.h

src/crypto/hex_base.h

src/node/mempool_persist_args.h

src/interfaces/echo.h

src/util/any.h

src/util/batchpriority.cpp

src/util/threadnames.h

src/node/coin.h

src/node/mempool_args.h

src/util/asmap.h

src/util/bytevectorhash.h

src/node/context.cpp

src/util/insert.h

src/util/readwritefile.h

src/node/peerman_args.cpp

src/node/interface_ui.cpp

src/interfaces/handler.h

src/node/mining_args.h

src/util/hasher.cpp

src/common/init.h

src/kernel/mempool_limits.h

src/common/system.h

src/crypto/sha3.h

src/util/threadinterrupt.cpp

src/node/protocol_version.h

src/util/exception.cpp

src/common/messages.h

src/node/connection_types.cpp

src/util/bip32.h

src/common/license_info.cpp

src/util/stdmutex.h

src/common/run_command.cpp

src/util/check.cpp

src/util/golombrice.h

src/node/types.h

src/node/timeoffsets.h

src/util/readwritefile.cpp

src/util/fastrange.h

src/util/signalinterrupt.h

src/util/task_runner.h

src/util/syserror.cpp

src/common/interfaces.cpp

src/common/types.h

src/util/threadinterrupt.h

src/kernel/chainstatemanager_opts.h

src/node/psbt.h

src/policy/ephemeral_policy.h

src/util/trace.h

src/common/url.cpp

src/kernel/mempool_options.h

src/util/serfloat.cpp

src/kernel/notifications_interface.h

src/node/timeoffsets.cpp

src/node/warnings.cpp

src/util/hash_type.h

src/crypto/hex_base.cpp

src/node/eviction.h

src/util/tokenbucket.h

src/crypto/aes.h

src/common/pcp.h

src/util/feefrac.cpp

src/node/transaction.h

src/util/threadnames.cpp

src/common/signmessage.h

src/util/exec.cpp

src/util/signalinterrupt.cpp

Independent explanations by MyBitcoinExplorer. Not affiliated with or endorsed by Bitcoin Core. Guides are educational and do not replace the source or its tests.

Bitcoin Core source © its contributors, distributed under the MIT license. Original notices and bundled third-party licenses are retained in the source tree.