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 server440 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.

15,153 bytes · SHA-256 1c1463fe6a36d9a9… · View upstream ↗

1#ifndef _MINISKETCH_H_
2#define _MINISKETCH_H_ 1
3
4#include <stdint.h>
5#include <stdlib.h>
6
7#ifdef _MSC_VER
8#  include <BaseTsd.h>
9   typedef SSIZE_T ssize_t;
10#else
11#  include <unistd.h>
12#endif
13
14#ifndef MINISKETCH_API
15# if defined(_WIN32)
16#  ifdef MINISKETCH_BUILD
17#   define MINISKETCH_API __declspec(dllexport)
18#  else
19#   define MINISKETCH_API
20#  endif
21# elif defined(__GNUC__) && (__GNUC__ >= 4) && defined(MINISKETCH_BUILD)
22#  define MINISKETCH_API __attribute__ ((visibility ("default")))
23# else
24#  define MINISKETCH_API
25# endif
26#endif
27
28#ifdef __cplusplus
29#  if __cplusplus >= 201103L
30#    include <memory>
31#    include <vector>
32#    include <cassert>
33#    if __cplusplus >= 201703L
34#      include <optional>
35#    endif // __cplusplus >= 201703L
36#  endif // __cplusplus >= 201103L
37extern "C" {
38#endif // __cplusplus
39
40/** Opaque type for decoded sketches. */
41typedef struct minisketch minisketch;
42
43/** Determine whether support for elements of `bits` bits was compiled in. */
44MINISKETCH_API int minisketch_bits_supported(uint32_t bits);
45
46/** Determine the maximum number of implementations available.
47 *
48 * Multiple implementations may be available for a given element size, with
49 * different performance characteristics on different hardware.
50 *
51 * Each implementation is identified by a number from 0 to the output of this
52 * function call, inclusive. Note that not every combination of implementation
53 * and element size may exist (see further).
54*/
55MINISKETCH_API uint32_t minisketch_implementation_max(void);
56
57/** Determine if the a combination of bits and implementation number is available.
58 *
59 * Returns 1 if it is, 0 otherwise.
60 */
61MINISKETCH_API int minisketch_implementation_supported(uint32_t bits, uint32_t implementation);
62
63/** Construct a sketch for a given element size, implementation and capacity.
64 *
65 * If the combination of `bits` and `implementation` is unavailable, or when
66 * OOM occurs, NULL is returned. If minisketch_implementation_supported
67 * returns 1 for the specified bits and implementation, this will always succeed
68 * (except when allocation fails).
69 *
70 * If the result is not NULL, it must be destroyed using minisketch_destroy.
71 */
72MINISKETCH_API minisketch* minisketch_create(uint32_t bits, uint32_t implementation, size_t capacity);
73
74/** Get the element size of a sketch in bits. */
75MINISKETCH_API uint32_t minisketch_bits(const minisketch* sketch);
76
77/** Get the capacity of a sketch. */
78MINISKETCH_API size_t minisketch_capacity(const minisketch* sketch);
79
80/** Get the implementation of a sketch. */
81MINISKETCH_API uint32_t minisketch_implementation(const minisketch* sketch);
82
83/** Set the seed for randomizing algorithm choices to a fixed value.
84 *
85 * By default, sketches are initialized with a random seed. This is important
86 * to avoid scenarios where an attacker could force worst-case behavior.
87 *
88 * This function initializes the seed to a user-provided value (any 64-bit
89 * integer is acceptable, regardless of field size).
90 *
91 * When seed is -1, a fixed internal value with predictable behavior is
92 * used. It is only intended for testing.
93 */
94MINISKETCH_API void minisketch_set_seed(minisketch* sketch, uint64_t seed);
95
96/** Clone a sketch.
97 *
98 * The result must be destroyed using minisketch_destroy.
99 */
100MINISKETCH_API minisketch* minisketch_clone(const minisketch* sketch);
101
102/** Destroy a sketch.
103 *
104 * The pointer that was passed in may not be used anymore afterwards.
105 */
106MINISKETCH_API void minisketch_destroy(minisketch* sketch);
107
108/** Compute the size in bytes for serializing a given sketch. */
109MINISKETCH_API size_t minisketch_serialized_size(const minisketch* sketch);
110
111/** Serialize a sketch to bytes. */
112MINISKETCH_API void minisketch_serialize(const minisketch* sketch, unsigned char* output);
113
114/** Deserialize a sketch from bytes. */
115MINISKETCH_API void minisketch_deserialize(minisketch* sketch, const unsigned char* input);
116
117/** Add an element to a sketch.
118 *
119 * If the element to be added is too large for the sketch, the most significant
120 * bits of the element are dropped. More precisely, if the element size of
121 * `sketch` is b bits, then this function adds the unsigned integer represented
122 * by the b least significant bits of `element` to `sketch`.
123 *
124 * If the element to be added is 0 (after potentially dropping the most significant
125 * bits), then this function is a no-op. Sketches cannot contain an element with
126 * the value 0.
127 *
128 * Note that adding the same element a second time removes it again.
129 */
130MINISKETCH_API void minisketch_add_uint64(minisketch* sketch, uint64_t element);
131
132/** Merge the elements of another sketch into this sketch.
133 *
134 * After merging, `sketch` will contain every element that existed in one but not
135 * both of the input sketches. It can be seen as an exclusive or operation on
136 * the set elements.  If the capacity of `other_sketch` is lower than `sketch`'s,
137 * merging reduces the capacity of `sketch` to that of `other_sketch`.
138 *
139 * This function returns the capacity of `sketch` after merging has been performed
140 * (where this capacity is at least 1), or 0 to indicate that merging has failed because
141 * the two input sketches differ in their element size or implementation. If 0 is
142 * returned, `sketch` (and its capacity) have not been modified.
143 *
144 * It is also possible to perform this operation directly on the serializations
145 * of two sketches with the same element size and capacity by performing a bitwise XOR
146 * of the serializations.
147 */
148MINISKETCH_API size_t minisketch_merge(minisketch* sketch, const minisketch* other_sketch);
149
150/** Decode a sketch.
151 *
152 * `output` is a pointer to an array of `max_element` uint64_t's, which will be
153 * filled with the elements in this sketch.
154 *
155 * The return value is the number of decoded elements, or -1 if decoding failed.
156 */
157MINISKETCH_API ssize_t minisketch_decode(const minisketch* sketch, size_t max_elements, uint64_t* output);
158
159/** Compute the capacity needed to achieve a certain rate of false positives.
160 *
161 * A sketch with capacity c and no more than c elements can always be decoded
162 * correctly. However, if it has more than c elements, or contains just random
163 * bytes, it is possible that it will still decode, but the result will be
164 * nonsense. This can be counteracted by increasing the capacity slightly.
165 *
166 * Given a field size bits, an intended number of elements that can be decoded
167 * max_elements, and a false positive probability of 1 in 2**fpbits, this
168 * function computes the necessary capacity. It is only guaranteed to be
169 * accurate up to fpbits=256.
170 */
171MINISKETCH_API size_t minisketch_compute_capacity(uint32_t bits, size_t max_elements, uint32_t fpbits);
172
173/** Compute what max_elements can be decoded for a certain rate of false positives.
174 *
175 * This is the inverse operation of minisketch_compute_capacity. It determines,
176 * given a field size bits, a capacity of a sketch, and an acceptable false
177 * positive probability of 1 in 2**fpbits, what the maximum allowed
178 * max_elements value is. If no value of max_elements would give the desired
179 * false positive probability, 0 is returned.
180 *
181 * Note that this is not an exact inverse of minisketch_compute_capacity. For
182 * example, with bits=32, fpbits=16, and max_elements=8,
183 * minisketch_compute_capacity will return 9, as capacity 8 would only have a
184 * false positive chance of 1 in 2^15.3. Increasing the capacity to 9 however
185 * decreases the fp chance to 1 in 2^47.3, enough for max_elements=9 (with fp
186 * chance of 1 in 2^18.5). Therefore, minisketch_compute_max_elements with
187 * capacity=9 will return 9.
188 */
189MINISKETCH_API size_t minisketch_compute_max_elements(uint32_t bits, size_t capacity, uint32_t fpbits);
190
191#ifdef __cplusplus
192}
193
194#if __cplusplus >= 201103L
195/** Simple RAII C++11 wrapper around the minisketch API. */
196class Minisketch
197{
198    struct Deleter
199    {
200        void operator()(minisketch* ptr) const
201        {
202            minisketch_destroy(ptr);
203        }
204    };
205
206    std::unique_ptr<minisketch, Deleter> m_minisketch;
207
208public:
209    /** Check whether the library supports fields of the given size. */
210    static bool BitsSupported(uint32_t bits) noexcept { return minisketch_bits_supported(bits); }
211
212    /** Get the highest supported implementation number. */
213    static uint32_t MaxImplementation() noexcept { return minisketch_implementation_max(); }
214
215    /** Check whether the library supports fields with a given size and implementation number.
216     *  If a particular field size `bits` is supported, implementation 0 is always supported for it.
217     *  Higher implementation numbers may or may not be available as well, up to MaxImplementation().
218     */
219    static bool ImplementationSupported(uint32_t bits, uint32_t implementation) noexcept { return minisketch_implementation_supported(bits, implementation); }
220
221    /** Given field size and a maximum number of decodable elements n, compute what capacity c to
222     *  use so that sketches with more elements than n have a chance no higher than 2^-fpbits of
223     *  being decoded incorrectly (and will instead fail when decoding for up to n elements).
224     *
225     *  See minisketch_compute_capacity for more details. */
226    static size_t ComputeCapacity(uint32_t bits, size_t max_elements, uint32_t fpbits) noexcept { return minisketch_compute_capacity(bits, max_elements, fpbits); }
227
228    /** Reverse operation of ComputeCapacity. See minisketch_compute_max_elements. */
229    static size_t ComputeMaxElements(uint32_t bits, size_t capacity, uint32_t fpbits) noexcept { return minisketch_compute_max_elements(bits, capacity, fpbits); }
230
231    /** Construct a clone of the specified sketch. */
232    Minisketch(const Minisketch& sketch) noexcept
233    {
234        if (sketch.m_minisketch) {
235            m_minisketch = std::unique_ptr<minisketch, Deleter>(minisketch_clone(sketch.m_minisketch.get()));
236        }
237    }
238
239    /** Make this Minisketch a clone of the specified one. */
240    Minisketch& operator=(const Minisketch& sketch) noexcept
241    {
242        if (this != &sketch && sketch.m_minisketch) {
243            m_minisketch = std::unique_ptr<minisketch, Deleter>(minisketch_clone(sketch.m_minisketch.get()));
244        }
245        return *this;
246    }
247
248    /** Check whether this Minisketch object is valid. */
249    explicit operator bool() const noexcept { return bool{m_minisketch}; }
250

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

src/clientversion.cpp

src/common/signmessage.cpp

src/compat/assumptions.h

src/compat/byteswap.h

src/deploymentinfo.cpp

src/deploymentinfo.h

src/deploymentstatus.cpp

src/deploymentstatus.h

src/dummywallet.cpp

src/external_signer.h

src/init/bitcoin-gui.cpp

src/init/bitcoin-node.cpp

src/init/bitcoin-qt.cpp

src/init/bitcoin-wallet.cpp

src/init/bitcoind.cpp

src/init/common.h

src/interfaces/init.h

src/interfaces/ipc.h

src/key_io.h

src/logging/categories.h

src/logging/timer.h

src/mapport.h

src/musig.h

src/net_permissions.h

src/netgroup.h

src/netmessagemaker.h

src/node/chainstatemanager_args.cpp

src/node/connection_types.h

src/node/context.h

src/node/interface_ui.h

src/node/mempool_args.cpp

src/node/mining_args.cpp

src/node/minisketchwrapper.cpp

src/node/txreconciliation.h

src/policy/fees/estimator_args.cpp

src/policy/fees/estimator_args.h

src/policy/fees/estimator_man.cpp

src/policy/fees/estimator_man.h

src/policy/packages.h

src/policy/rbf.h

src/policy/truc_policy.h

src/pow.h

src/primitives/block.cpp

src/randomenv.h

src/rest.h

src/script/keyorigin.h

src/script/parsing.cpp

src/script/parsing.h

src/script/script_error.h

src/script/sigcache.cpp

src/script/sigcache.h

src/script/solver.h

src/script/verify_flags.h

src/semaphore_grant.h

src/signet.h

src/span.h

src/support/allocators/secure.h

src/support/allocators/zeroafterfree.h

src/util/tokenpipe.cpp

src/util/translation.h

src/util/vector.h

src/versionbits.h

src/versionbits_impl.h

src/wallet/external_signer_scriptpubkeyman.h

src/wallet/fees.h

src/wallet/load.h

src/wallet/receive.h

src/wallet/rpc/wallet.h

src/wallet/types.h

src/walletinitinterface.h

src/zmq/zmqabstractnotifier.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.