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.

9,749 bytes · SHA-256 916f3f0b6045a11a… · View upstream ↗

1// Copyright (c) 2012-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 <common/bloom.h>
6
7#include <hash.h>
8#include <primitives/transaction.h>
9#include <random.h>
10#include <script/script.h>
11#include <script/solver.h>
12#include <span.h>
13#include <streams.h>
14#include <util/fastrange.h>
15#include <util/overflow.h>
16
17#include <algorithm>
18#include <cmath>
19#include <compare>
20#include <vector>
21
22static constexpr double LN2SQUARED = 0.4804530139182014246671025263266649717305529515945455;
23static constexpr double LN2 = 0.6931471805599453094172321214581765680755001343602552;
24
25CBloomFilter::CBloomFilter(const unsigned int nElements, const double nFPRate, const unsigned int nTweakIn, unsigned char nFlagsIn) :
26    /**
27     * The ideal size for a bloom filter with a given number of elements and false positive rate is:
28     * - nElements * log(fp rate) / ln(2)^2
29     * We ignore filter parameters which will create a bloom filter larger than the protocol limits
30     */
31    vData(std::min((unsigned int)(-1  / LN2SQUARED * nElements * log(nFPRate)), MAX_BLOOM_FILTER_SIZE * 8) / 8),
32    /**
33     * The ideal number of hash functions is filter size * ln(2) / number of elements
34     * Again, we ignore filter parameters which will create a bloom filter with more hash functions than the protocol limits
35     * See https://en.wikipedia.org/wiki/Bloom_filter for an explanation of these formulas
36     */
37    nHashFuncs(std::min((unsigned int)(vData.size() * 8 / nElements * LN2), MAX_HASH_FUNCS)),
38    nTweak(nTweakIn),
39    nFlags(nFlagsIn)
40{
41}
42
43inline unsigned int CBloomFilter::Hash(unsigned int nHashNum, std::span<const unsigned char> vDataToHash) const
44{
45    // 0xFBA4C795 chosen as it guarantees a reasonable bit difference between nHashNum values.
46    return MurmurHash3(nHashNum * 0xFBA4C795 + nTweak, vDataToHash) % (vData.size() * 8);
47}
48
49void CBloomFilter::insert(std::span<const unsigned char> vKey)
50{
51    if (vData.empty()) // Avoid divide-by-zero (CVE-2013-5700)
52        return;
53    for (unsigned int i = 0; i < nHashFuncs; i++)
54    {
55        unsigned int nIndex = Hash(i, vKey);
56        // Sets bit nIndex of vData
57        vData[nIndex >> 3] |= (1 << (7 & nIndex));
58    }
59}
60
61void CBloomFilter::insert(const COutPoint& outpoint)
62{
63    DataStream stream{};
64    stream << outpoint;
65    insert(MakeUCharSpan(stream));
66}
67
68bool CBloomFilter::contains(std::span<const unsigned char> vKey) const
69{
70    if (vData.empty()) // Avoid divide-by-zero (CVE-2013-5700)
71        return true;
72    for (unsigned int i = 0; i < nHashFuncs; i++)
73    {
74        unsigned int nIndex = Hash(i, vKey);
75        // Checks bit nIndex of vData
76        if (!(vData[nIndex >> 3] & (1 << (7 & nIndex))))
77            return false;
78    }
79    return true;
80}
81
82bool CBloomFilter::contains(const COutPoint& outpoint) const
83{
84    DataStream stream{};
85    stream << outpoint;
86    return contains(MakeUCharSpan(stream));
87}
88
89bool CBloomFilter::IsWithinSizeConstraints() const
90{
91    return vData.size() <= MAX_BLOOM_FILTER_SIZE && nHashFuncs <= MAX_HASH_FUNCS;
92}
93
94bool CBloomFilter::IsRelevantAndUpdate(const CTransaction& tx)
95{
96    bool fFound = false;
97    // Match if the filter contains the hash of tx
98    //  for finding tx when they appear in a block
99    if (vData.empty()) // zero-size = "match-all" filter
100        return true;
101    const Txid& hash = tx.GetHash();
102    if (contains(hash.ToUint256()))
103        fFound = true;
104
105    for (unsigned int i = 0; i < tx.vout.size(); i++)
106    {
107        const CTxOut& txout = tx.vout[i];
108        // Match if the filter contains any arbitrary script data element in any scriptPubKey in tx
109        // If this matches, also add the specific output that was matched.
110        // This means clients don't have to update the filter themselves when a new relevant tx
111        // is discovered in order to find spending transactions, which avoids round-tripping and race conditions.
112        CScript::const_iterator pc = txout.scriptPubKey.begin();
113        std::vector<unsigned char> data;
114        while (pc < txout.scriptPubKey.end())
115        {
116            opcodetype opcode;
117            if (!txout.scriptPubKey.GetOp(pc, opcode, data))
118                break;
119            if (data.size() != 0 && contains(data))
120            {
121                fFound = true;
122                if ((nFlags & BLOOM_UPDATE_MASK) == BLOOM_UPDATE_ALL)
123                    insert(COutPoint(hash, i));
124                else if ((nFlags & BLOOM_UPDATE_MASK) == BLOOM_UPDATE_P2PUBKEY_ONLY)
125                {
126                    std::vector<std::vector<unsigned char> > vSolutions;
127                    TxoutType type = Solver(txout.scriptPubKey, vSolutions);
128                    if (type == TxoutType::PUBKEY || type == TxoutType::MULTISIG) {
129                        insert(COutPoint(hash, i));
130                    }
131                }
132                break;
133            }
134        }
135    }
136
137    if (fFound)
138        return true;
139
140    for (const CTxIn& txin : tx.vin)
141    {
142        // Match if the filter contains an outpoint tx spends
143        if (contains(txin.prevout))
144            return true;
145
146        // Match if the filter contains any arbitrary script data element in any scriptSig in tx
147        CScript::const_iterator pc = txin.scriptSig.begin();
148        std::vector<unsigned char> data;
149        while (pc < txin.scriptSig.end())
150        {
151            opcodetype opcode;
152            if (!txin.scriptSig.GetOp(pc, opcode, data))
153                break;
154            if (data.size() != 0 && contains(data))
155                return true;
156        }
157    }
158
159    return false;
160}
161
162CRollingBloomFilter::CRollingBloomFilter(const unsigned int nElements, const double fpRate)
163{
164    double logFpRate = log(fpRate);
165    /* The optimal number of hash functions is log(fpRate) / log(0.5), but
166     * restrict it to the range 1-50. */
167    nHashFuncs = std::max(1, std::min((int)round(logFpRate / log(0.5)), 50));
168    /* In this rolling bloom filter, we'll store between 2 and 3 generations of nElements / 2 entries. */
169    nEntriesPerGeneration = CeilDiv(nElements, 2u);
170    uint32_t nMaxElements = nEntriesPerGeneration * 3;
171    /* The maximum fpRate = pow(1.0 - exp(-nHashFuncs * nMaxElements / nFilterBits), nHashFuncs)
172     * =>          pow(fpRate, 1.0 / nHashFuncs) = 1.0 - exp(-nHashFuncs * nMaxElements / nFilterBits)
173     * =>          1.0 - pow(fpRate, 1.0 / nHashFuncs) = exp(-nHashFuncs * nMaxElements / nFilterBits)
174     * =>          log(1.0 - pow(fpRate, 1.0 / nHashFuncs)) = -nHashFuncs * nMaxElements / nFilterBits
175     * =>          nFilterBits = -nHashFuncs * nMaxElements / log(1.0 - pow(fpRate, 1.0 / nHashFuncs))
176     * =>          nFilterBits = -nHashFuncs * nMaxElements / log(1.0 - exp(logFpRate / nHashFuncs))
177     */
178    uint32_t nFilterBits = (uint32_t)ceil(-1.0 * nHashFuncs * nMaxElements / log(1.0 - exp(logFpRate / nHashFuncs)));
179    data.clear();
180    /* For each data element we need to store 2 bits. If both bits are 0, the
181     * bit is treated as unset. If the bits are (01), (10), or (11), the bit is
182     * treated as set in generation 1, 2, or 3 respectively.
183     * These bits are stored in separate integers: position P corresponds to bit
184     * (P & 63) of the integers data[(P >> 6) * 2] and data[(P >> 6) * 2 + 1]. */
185    data.resize(CeilDiv(nFilterBits, 64u) << 1);
186    reset();
187}
188
189/* Similar to CBloomFilter::Hash */
190static inline uint32_t RollingBloomHash(unsigned int nHashNum, uint32_t nTweak, std::span<const unsigned char> vDataToHash)
191{
192    return MurmurHash3(nHashNum * 0xFBA4C795 + nTweak, vDataToHash);
193}
194
195void CRollingBloomFilter::insert(std::span<const unsigned char> vKey)
196{
197    if (nEntriesThisGeneration == nEntriesPerGeneration) {
198        nEntriesThisGeneration = 0;
199        nGeneration++;
200        if (nGeneration == 4) {
201            nGeneration = 1;
202        }
203        uint64_t nGenerationMask1 = 0 - (uint64_t)(nGeneration & 1);
204        uint64_t nGenerationMask2 = 0 - (uint64_t)(nGeneration >> 1);
205        /* Wipe old entries that used this generation number. */
206        for (uint32_t p = 0; p < data.size(); p += 2) {
207            uint64_t p1 = data[p], p2 = data[p + 1];
208            uint64_t mask = (p1 ^ nGenerationMask1) | (p2 ^ nGenerationMask2);
209            data[p] = p1 & mask;
210            data[p + 1] = p2 & mask;
211        }
212    }
213    nEntriesThisGeneration++;
214
215    for (int n = 0; n < nHashFuncs; n++) {
216        uint32_t h = RollingBloomHash(n, nTweak, vKey);
217        int bit = h & 0x3F;
218        /* FastMod works with the upper bits of h, so it is safe to ignore that the lower bits of h are already used for bit. */
219        uint32_t pos = FastRange32(h, data.size());
220        /* The lowest bit of pos is ignored, and set to zero for the first bit, and to one for the second. */
221        data[pos & ~1U] = (data[pos & ~1U] & ~(uint64_t{1} << bit)) | (uint64_t(nGeneration & 1)) << bit;
222        data[pos | 1] = (data[pos | 1] & ~(uint64_t{1} << bit)) | (uint64_t(nGeneration >> 1)) << bit;
223    }
224}
225
226bool CRollingBloomFilter::contains(std::span<const unsigned char> vKey) const
227{
228    for (int n = 0; n < nHashFuncs; n++) {
229        uint32_t h = RollingBloomHash(n, nTweak, vKey);
230        int bit = h & 0x3F;
231        uint32_t pos = FastRange32(h, data.size());
232        /* If the relevant bit is not set in either data[pos & ~1] or data[pos | 1], the filter does not contain vKey */
233        if (!(((data[pos & ~1U] | data[pos | 1]) >> bit) & 1)) {
234            return false;
235        }
236    }
237    return true;
238}
239
240void CRollingBloomFilter::reset()
241{
242    nTweak = FastRandomContext().rand<unsigned int>();
243    nEntriesThisGeneration = 0;
244    nGeneration = 1;
245    std::fill(data.begin(), data.end(), 0);
246}
247

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.