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.

22,393 bytes · SHA-256 11af1cf067a6218f… · View upstream ↗

1// Copyright (c) 2017-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 <crypto/muhash.h>
6
7#include <crypto/chacha20.h>
8#include <crypto/common.h>
9#include <hash.h>
10#include <span.h>
11#include <uint256.h>
12#include <util/check.h>
13
14#include <bit>
15#include <cstring>
16#include <limits>
17
18namespace {
19
20using limb_t = Num3072::limb_t;
21using signed_limb_t = Num3072::signed_limb_t;
22using double_limb_t = Num3072::double_limb_t;
23using signed_double_limb_t = Num3072::signed_double_limb_t;
24constexpr int LIMB_SIZE = Num3072::LIMB_SIZE;
25constexpr int SIGNED_LIMB_SIZE = Num3072::SIGNED_LIMB_SIZE;
26constexpr int LIMBS = Num3072::LIMBS;
27constexpr int SIGNED_LIMBS = Num3072::SIGNED_LIMBS;
28constexpr int FINAL_LIMB_POSITION = 3072 / SIGNED_LIMB_SIZE;
29constexpr int FINAL_LIMB_MODULUS_BITS = 3072 % SIGNED_LIMB_SIZE;
30constexpr limb_t MAX_LIMB = (limb_t)(-1);
31constexpr limb_t MAX_SIGNED_LIMB = (((limb_t)1) << SIGNED_LIMB_SIZE) - 1;
32/** 2^3072 - 1103717, the largest 3072-bit safe prime number, is used as the modulus. */
33constexpr limb_t MAX_PRIME_DIFF = 1103717;
34/** The modular inverse of (2**3072 - MAX_PRIME_DIFF) mod (MAX_SIGNED_LIMB + 1). */
35constexpr limb_t MODULUS_INVERSE = limb_t(0x70a1421da087d93);
36
37
38/** Extract the lowest limb of [c0,c1,c2] into n, and left shift the number by 1 limb. */
39inline void extract3(limb_t& c0, limb_t& c1, limb_t& c2, limb_t& n)
40{
41    n = c0;
42    c0 = c1;
43    c1 = c2;
44    c2 = 0;
45}
46
47/** [c0,c1] = a * b */
48inline void mul(limb_t& c0, limb_t& c1, const limb_t& a, const limb_t& b)
49{
50    double_limb_t t = (double_limb_t)a * b;
51    c1 = t >> LIMB_SIZE;
52    c0 = t;
53}
54
55/* [c0,c1,c2] += n * [d0,d1,d2]. c2 is 0 initially */
56inline void mulnadd3(limb_t& c0, limb_t& c1, limb_t& c2, limb_t& d0, limb_t& d1, limb_t& d2, const limb_t& n)
57{
58    double_limb_t t = (double_limb_t)d0 * n + c0;
59    c0 = t;
60    t >>= LIMB_SIZE;
61    t += (double_limb_t)d1 * n + c1;
62    c1 = t;
63    t >>= LIMB_SIZE;
64    c2 = t + d2 * n;
65}
66
67/* [c0,c1] *= n */
68inline void muln2(limb_t& c0, limb_t& c1, const limb_t& n)
69{
70    double_limb_t t = (double_limb_t)c0 * n;
71    c0 = t;
72    t >>= LIMB_SIZE;
73    t += (double_limb_t)c1 * n;
74    c1 = t;
75}
76
77/** [c0,c1,c2] += a * b */
78inline void muladd3(limb_t& c0, limb_t& c1, limb_t& c2, const limb_t& a, const limb_t& b)
79{
80    double_limb_t t = (double_limb_t)a * b;
81    limb_t th = t >> LIMB_SIZE;
82    limb_t tl = t;
83
84    c0 += tl;
85    th += (c0 < tl) ? 1 : 0;
86    c1 += th;
87    c2 += (c1 < th) ? 1 : 0;
88}
89
90/**
91 * Add limb a to [c0,c1]: [c0,c1] += a. Then extract the lowest
92 * limb of [c0,c1] into n, and left shift the number by 1 limb.
93 * */
94inline void addnextract2(limb_t& c0, limb_t& c1, const limb_t& a, limb_t& n)
95{
96    limb_t c2 = 0;
97
98    // add
99    c0 += a;
100    if (c0 < a) {
101        c1 += 1;
102
103        // Handle case when c1 has overflown
104        if (c1 == 0) c2 = 1;
105    }
106
107    // extract
108    n = c0;
109    c0 = c1;
110    c1 = c2;
111}
112
113} // namespace
114
115/** Indicates whether d is larger than the modulus. */
116bool Num3072::IsOverflow() const
117{
118    if (this->limbs[0] <= std::numeric_limits<limb_t>::max() - MAX_PRIME_DIFF) return false;
119    for (int i = 1; i < LIMBS; ++i) {
120        if (this->limbs[i] != std::numeric_limits<limb_t>::max()) return false;
121    }
122    return true;
123}
124
125void Num3072::FullReduce()
126{
127    limb_t c0 = MAX_PRIME_DIFF;
128    limb_t c1 = 0;
129    for (int i = 0; i < LIMBS; ++i) {
130        addnextract2(c0, c1, this->limbs[i], this->limbs[i]);
131    }
132}
133
134namespace {
135/** A type representing a number in signed limb representation. */
136struct Num3072Signed
137{
138    /** The represented value is sum(limbs[i]*2^(SIGNED_LIMB_SIZE*i), i=0..SIGNED_LIMBS-1).
139     *  Note that limbs may be negative, or exceed 2^SIGNED_LIMB_SIZE-1. */
140    signed_limb_t limbs[SIGNED_LIMBS];
141
142    /** Construct a Num3072Signed with value 0. */
143    Num3072Signed()
144    {
145        memset(limbs, 0, sizeof(limbs));
146    }
147
148    /** Convert a Num3072 to a Num3072Signed. Output will be normalized and in
149     *  range 0..2^3072-1. */
150    void FromNum3072(const Num3072& in)
151    {
152        double_limb_t c = 0;
153        int b = 0, outpos = 0;
154        for (int i = 0; i < LIMBS; ++i) {
155            c += double_limb_t{in.limbs[i]} << b;
156            b += LIMB_SIZE;
157            while (b >= SIGNED_LIMB_SIZE) {
158                limbs[outpos++] = limb_t(c) & MAX_SIGNED_LIMB;
159                c >>= SIGNED_LIMB_SIZE;
160                b -= SIGNED_LIMB_SIZE;
161            }
162        }
163        Assume(outpos == SIGNED_LIMBS - 1);
164        limbs[SIGNED_LIMBS - 1] = c;
165        c >>= SIGNED_LIMB_SIZE;
166        Assume(c == 0);
167    }
168
169    /** Convert a Num3072Signed to a Num3072. Input must be in range 0..modulus-1. */
170    void ToNum3072(Num3072& out) const
171    {
172        double_limb_t c = 0;
173        int b = 0, outpos = 0;
174        for (int i = 0; i < SIGNED_LIMBS; ++i) {
175            c += double_limb_t(limbs[i]) << b;
176            b += SIGNED_LIMB_SIZE;
177            if (b >= LIMB_SIZE) {
178                out.limbs[outpos++] = c;
179                c >>= LIMB_SIZE;
180                b -= LIMB_SIZE;
181            }
182        }
183        Assume(outpos == LIMBS);
184        Assume(c == 0);
185    }
186
187    /** Take a Num3072Signed in range 1-2*2^3072..2^3072-1, and:
188     *  - optionally negate it (if negate is true)
189     *  - reduce it modulo the modulus (2^3072 - MAX_PRIME_DIFF)
190     *  - produce output with all limbs in range 0..2^SIGNED_LIMB_SIZE-1
191     */
192    void Normalize(bool negate)
193    {
194        // Add modulus if this was negative. This brings the range of *this to 1-2^3072..2^3072-1.
195        signed_limb_t cond_add = limbs[SIGNED_LIMBS-1] >> (LIMB_SIZE-1); // -1 if this is negative; 0 otherwise
196        limbs[0] += signed_limb_t(-MAX_PRIME_DIFF) & cond_add;
197        limbs[FINAL_LIMB_POSITION] += (signed_limb_t(1) << FINAL_LIMB_MODULUS_BITS) & cond_add;
198        // Next negate all limbs if negate was set. This does not change the range of *this.
199        signed_limb_t cond_negate = -signed_limb_t(negate); // -1 if this negate is true; 0 otherwise
200        for (int i = 0; i < SIGNED_LIMBS; ++i) {
201            limbs[i] = (limbs[i] ^ cond_negate) - cond_negate;
202        }
203        // Perform carry (make all limbs except the top one be in range 0..2^SIGNED_LIMB_SIZE-1).
204        for (int i = 0; i < SIGNED_LIMBS - 1; ++i) {
205            limbs[i + 1] += limbs[i] >> SIGNED_LIMB_SIZE;
206            limbs[i] &= MAX_SIGNED_LIMB;
207        }
208        // Again add modulus if *this was negative. This brings the range of *this to 0..2^3072-1.
209        cond_add = limbs[SIGNED_LIMBS-1] >> (LIMB_SIZE-1); // -1 if this is negative; 0 otherwise
210        limbs[0] += signed_limb_t(-MAX_PRIME_DIFF) & cond_add;
211        limbs[FINAL_LIMB_POSITION] += (signed_limb_t(1) << FINAL_LIMB_MODULUS_BITS) & cond_add;
212        // Perform another carry. Now all limbs are in range 0..2^SIGNED_LIMB_SIZE-1.
213        for (int i = 0; i < SIGNED_LIMBS - 1; ++i) {
214            limbs[i + 1] += limbs[i] >> SIGNED_LIMB_SIZE;
215            limbs[i] &= MAX_SIGNED_LIMB;
216        }
217    }
218};
219
220/** 2x2 transformation matrix with signed_limb_t elements. */
221struct SignedMatrix
222{
223    signed_limb_t u, v, q, r;
224};
225
226/** Compute the transformation matrix for SIGNED_LIMB_SIZE divsteps.
227 *
228 * eta: initial eta value
229 * f:   bottom SIGNED_LIMB_SIZE bits of initial f value
230 * g:   bottom SIGNED_LIMB_SIZE bits of initial g value
231 * out: resulting transformation matrix, scaled by 2^SIGNED_LIMB_SIZE
232 * return: eta value after SIGNED_LIMB_SIZE divsteps
233 */
234inline limb_t ComputeDivstepMatrix(signed_limb_t eta, limb_t f, limb_t g, SignedMatrix& out)
235{
236    /** inv256[i] = -1/(2*i+1) (mod 256) */
237    static const uint8_t NEGINV256[128] = {
238        0xFF, 0x55, 0x33, 0x49, 0xC7, 0x5D, 0x3B, 0x11, 0x0F, 0xE5, 0xC3, 0x59,
239        0xD7, 0xED, 0xCB, 0x21, 0x1F, 0x75, 0x53, 0x69, 0xE7, 0x7D, 0x5B, 0x31,
240        0x2F, 0x05, 0xE3, 0x79, 0xF7, 0x0D, 0xEB, 0x41, 0x3F, 0x95, 0x73, 0x89,
241        0x07, 0x9D, 0x7B, 0x51, 0x4F, 0x25, 0x03, 0x99, 0x17, 0x2D, 0x0B, 0x61,
242        0x5F, 0xB5, 0x93, 0xA9, 0x27, 0xBD, 0x9B, 0x71, 0x6F, 0x45, 0x23, 0xB9,
243        0x37, 0x4D, 0x2B, 0x81, 0x7F, 0xD5, 0xB3, 0xC9, 0x47, 0xDD, 0xBB, 0x91,
244        0x8F, 0x65, 0x43, 0xD9, 0x57, 0x6D, 0x4B, 0xA1, 0x9F, 0xF5, 0xD3, 0xE9,
245        0x67, 0xFD, 0xDB, 0xB1, 0xAF, 0x85, 0x63, 0xF9, 0x77, 0x8D, 0x6B, 0xC1,
246        0xBF, 0x15, 0xF3, 0x09, 0x87, 0x1D, 0xFB, 0xD1, 0xCF, 0xA5, 0x83, 0x19,
247        0x97, 0xAD, 0x8B, 0xE1, 0xDF, 0x35, 0x13, 0x29, 0xA7, 0x3D, 0x1B, 0xF1,
248        0xEF, 0xC5, 0xA3, 0x39, 0xB7, 0xCD, 0xAB, 0x01
249    };
250    // Coefficients of returned SignedMatrix; starts off as identity matrix. */

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.