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.

9,796 bytes · SHA-256 3608a703fa74c1c6… · View upstream ↗

1# Prover implementation for Weierstrass curves of the form
2# y^2 = x^3 + A * x + B, specifically with a = 0 and b = 7, with group laws
3# operating on affine and Jacobian coordinates, including the point at infinity
4# represented by a 4th variable in coordinates.
5
6load("group_prover.sage")
7
8
9class affinepoint:
10  def __init__(self, x, y, infinity=0):
11    self.x = x
12    self.y = y
13    self.infinity = infinity
14  def __str__(self):
15    return "affinepoint(x=%s,y=%s,inf=%s)" % (self.x, self.y, self.infinity)
16
17
18class jacobianpoint:
19  def __init__(self, x, y, z, infinity=0):
20    self.X = x
21    self.Y = y
22    self.Z = z
23    self.Infinity = infinity
24  def __str__(self):
25    return "jacobianpoint(X=%s,Y=%s,Z=%s,inf=%s)" % (self.X, self.Y, self.Z, self.Infinity)
26
27
28def point_at_infinity():
29  return jacobianpoint(1, 1, 1, 1)
30
31
32def negate(p):
33  if p.__class__ == affinepoint:
34    return affinepoint(p.x, -p.y)
35  if p.__class__ == jacobianpoint:
36    return jacobianpoint(p.X, -p.Y, p.Z)
37  assert(False)
38
39
40def on_weierstrass_curve(A, B, p):
41  """Return a set of zero-expressions for an affine point to be on the curve"""
42  return constraints(zero={p.x^3 + A*p.x + B - p.y^2: 'on_curve'})
43
44
45def tangential_to_weierstrass_curve(A, B, p12, p3):
46  """Return a set of zero-expressions for ((x12,y12),(x3,y3)) to be a line that is tangential to the curve at (x12,y12)"""
47  return constraints(zero={
48    (p12.y - p3.y) * (p12.y * 2) - (p12.x^2 * 3 + A) * (p12.x - p3.x): 'tangential_to_curve'
49  })
50
51
52def colinear(p1, p2, p3):
53  """Return a set of zero-expressions for ((x1,y1),(x2,y2),(x3,y3)) to be collinear"""
54  return constraints(zero={
55    (p1.y - p2.y) * (p1.x - p3.x) - (p1.y - p3.y) * (p1.x - p2.x): 'colinear_1',
56    (p2.y - p3.y) * (p2.x - p1.x) - (p2.y - p1.y) * (p2.x - p3.x): 'colinear_2',
57    (p3.y - p1.y) * (p3.x - p2.x) - (p3.y - p2.y) * (p3.x - p1.x): 'colinear_3'
58  })
59
60
61def good_affine_point(p):
62  return constraints(nonzero={p.x : 'nonzero_x', p.y : 'nonzero_y'})
63
64
65def good_jacobian_point(p):
66  return constraints(nonzero={p.X : 'nonzero_X', p.Y : 'nonzero_Y', p.Z^6 : 'nonzero_Z'})
67
68
69def good_point(p):
70  return constraints(nonzero={p.Z^6 : 'nonzero_X'})
71
72
73def finite(p, *affine_fns):
74  con = good_point(p) + constraints(zero={p.Infinity : 'finite_point'})
75  if p.Z != 0:
76    return con + reduce(lambda a, b: a + b, (f(affinepoint(p.X / p.Z^2, p.Y / p.Z^3)) for f in affine_fns), con)
77  else:
78    return con
79
80def infinite(p):
81  return constraints(nonzero={p.Infinity : 'infinite_point'})
82
83
84def law_jacobian_weierstrass_add(A, B, pa, pb, pA, pB, pC):
85  """Check whether the passed set of coordinates is a valid Jacobian add, given assumptions"""
86  assumeLaw = (good_affine_point(pa) +
87               good_affine_point(pb) +
88               good_jacobian_point(pA) +
89               good_jacobian_point(pB) +
90               on_weierstrass_curve(A, B, pa) +
91               on_weierstrass_curve(A, B, pb) +
92               finite(pA) +
93               finite(pB) +
94               constraints(nonzero={pa.x - pb.x : 'different_x'}))
95  require = (finite(pC, lambda pc: on_weierstrass_curve(A, B, pc) +
96             colinear(pa, pb, negate(pc))))
97  return (assumeLaw, require)
98
99
100def law_jacobian_weierstrass_double(A, B, pa, pb, pA, pB, pC):
101  """Check whether the passed set of coordinates is a valid Jacobian doubling, given assumptions"""
102  assumeLaw = (good_affine_point(pa) +
103               good_affine_point(pb) +
104               good_jacobian_point(pA) +
105               good_jacobian_point(pB) +
106               on_weierstrass_curve(A, B, pa) +
107               on_weierstrass_curve(A, B, pb) +
108               finite(pA) +
109               finite(pB) +
110               constraints(zero={pa.x - pb.x : 'equal_x', pa.y - pb.y : 'equal_y'}))
111  require = (finite(pC, lambda pc: on_weierstrass_curve(A, B, pc) +
112             tangential_to_weierstrass_curve(A, B, pa, negate(pc))))
113  return (assumeLaw, require)
114
115
116def law_jacobian_weierstrass_add_opposites(A, B, pa, pb, pA, pB, pC):
117  assumeLaw = (good_affine_point(pa) +
118               good_affine_point(pb) +
119               good_jacobian_point(pA) +
120               good_jacobian_point(pB) +
121               on_weierstrass_curve(A, B, pa) +
122               on_weierstrass_curve(A, B, pb) +
123               finite(pA) +
124               finite(pB) +
125               constraints(zero={pa.x - pb.x : 'equal_x', pa.y + pb.y : 'opposite_y'}))
126  require = infinite(pC)
127  return (assumeLaw, require)
128
129
130def law_jacobian_weierstrass_add_infinite_a(A, B, pa, pb, pA, pB, pC):
131  assumeLaw = (good_affine_point(pa) +
132               good_affine_point(pb) +
133               good_jacobian_point(pA) +
134               good_jacobian_point(pB) +
135               on_weierstrass_curve(A, B, pb) +
136               infinite(pA) +
137               finite(pB))
138  require = finite(pC, lambda pc: constraints(zero={pc.x - pb.x : 'c.x=b.x', pc.y - pb.y : 'c.y=b.y'}))
139  return (assumeLaw, require)
140
141
142def law_jacobian_weierstrass_add_infinite_b(A, B, pa, pb, pA, pB, pC):
143  assumeLaw = (good_affine_point(pa) +
144               good_affine_point(pb) +
145               good_jacobian_point(pA) +
146               good_jacobian_point(pB) +
147               on_weierstrass_curve(A, B, pa) +
148               infinite(pB) +
149               finite(pA))
150  require = finite(pC, lambda pc: constraints(zero={pc.x - pa.x : 'c.x=a.x', pc.y - pa.y : 'c.y=a.y'}))
151  return (assumeLaw, require)
152
153
154def law_jacobian_weierstrass_add_infinite_ab(A, B, pa, pb, pA, pB, pC):
155  assumeLaw = (good_affine_point(pa) +
156               good_affine_point(pb) +
157               good_jacobian_point(pA) +
158               good_jacobian_point(pB) +
159               infinite(pA) +
160               infinite(pB))
161  require = infinite(pC)
162  return (assumeLaw, require)
163
164
165laws_jacobian_weierstrass = {
166  'add': law_jacobian_weierstrass_add,
167  'double': law_jacobian_weierstrass_double,
168  'add_opposite': law_jacobian_weierstrass_add_opposites,
169  'add_infinite_a': law_jacobian_weierstrass_add_infinite_a,
170  'add_infinite_b': law_jacobian_weierstrass_add_infinite_b,
171  'add_infinite_ab': law_jacobian_weierstrass_add_infinite_ab
172}
173
174
175def check_exhaustive_jacobian_weierstrass(name, A, B, branches, formula, p):
176  """Verify an implementation of addition of Jacobian points on a Weierstrass curve, by executing and validating the result for every possible addition in a prime field"""
177  F = Integers(p)
178  print("Formula %s on Z%i:" % (name, p))
179  points = []
180  for x in range(0, p):
181    for y in range(0, p):
182      point = affinepoint(F(x), F(y))
183      r, e = concrete_verify(on_weierstrass_curve(A, B, point))
184      if r:
185        points.append(point)
186
187  ret = True
188  for za in range(1, p):
189    for zb in range(1, p):
190      for pa in points:
191        for pb in points:
192          for ia in range(2):
193            for ib in range(2):
194              pA = jacobianpoint(pa.x * F(za)^2, pa.y * F(za)^3, F(za), ia)
195              pB = jacobianpoint(pb.x * F(zb)^2, pb.y * F(zb)^3, F(zb), ib)
196              for branch in range(0, branches):
197                assumeAssert, assumeBranch, pC = formula(branch, pA, pB)
198                pC.X = F(pC.X)
199                pC.Y = F(pC.Y)
200                pC.Z = F(pC.Z)
201                pC.Infinity = F(pC.Infinity)
202                r, e = concrete_verify(assumeAssert + assumeBranch)
203                if r:
204                  match = False
205                  for key in laws_jacobian_weierstrass:
206                    assumeLaw, require = laws_jacobian_weierstrass[key](A, B, pa, pb, pA, pB, pC)
207                    r, e = concrete_verify(assumeLaw)
208                    if r:
209                      if match:
210                        print("  multiple branches for (%s,%s,%s,%s) + (%s,%s,%s,%s)" % (pA.X, pA.Y, pA.Z, pA.Infinity, pB.X, pB.Y, pB.Z, pB.Infinity))
211                      else:
212                        match = True
213                      r, e = concrete_verify(require)
214                      if not r:
215                        ret = False
216                        print("  failure in branch %i for (%s,%s,%s,%s) + (%s,%s,%s,%s) = (%s,%s,%s,%s): %s" % (branch, pA.X, pA.Y, pA.Z, pA.Infinity, pB.X, pB.Y, pB.Z, pB.Infinity, pC.X, pC.Y, pC.Z, pC.Infinity, e))
217
218  print()
219  return ret
220
221
222def check_symbolic_function(R, assumeAssert, assumeBranch, f, A, B, pa, pb, pA, pB, pC):
223  assumeLaw, require = f(A, B, pa, pb, pA, pB, pC)
224  return check_symbolic(R, assumeLaw, assumeAssert, assumeBranch, require)
225
226def check_symbolic_jacobian_weierstrass(name, A, B, branches, formula):
227  """Verify an implementation of addition of Jacobian points on a Weierstrass curve symbolically"""
228  R.<ax,bx,ay,by,Az,Bz,Ai,Bi> = PolynomialRing(QQ,8,order='invlex')
229  lift = lambda x: fastfrac(R,x)
230  ax = lift(ax)
231  ay = lift(ay)
232  Az = lift(Az)
233  bx = lift(bx)
234  by = lift(by)
235  Bz = lift(Bz)
236  Ai = lift(Ai)
237  Bi = lift(Bi)
238
239  pa = affinepoint(ax, ay, Ai)
240  pb = affinepoint(bx, by, Bi)
241  pA = jacobianpoint(ax * Az^2, ay * Az^3, Az, Ai)
242  pB = jacobianpoint(bx * Bz^2, by * Bz^3, Bz, Bi)
243
244  res = {}
245
246  for key in laws_jacobian_weierstrass:
247    res[key] = []
248
249  print("Formula " + name + ":")
250  count = 0

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.