Method
How a search works, in prose
Two search classes, not one. A 2019 spend published twenty catalog public keys. The first four scalars look like a staircase and then stop. Calculators live under Tools.
Address HASH160 versus known public key
The catalog splits unsolved rows by what an observer actually has. That split decides the algorithm. It is not the same as spent versus unspent.
Address-only: the observer has a P2PKH address, which encodes HASH160 of a compressed public key. There is no point P to aim a discrete-log algorithm at. The work is to try candidate scalars in [2N−1, 2N - 1], compute compressed P, HASH160, and compare. #71 is this class: interval width 270, expected HASH160 comparisons about 269 if the unknown key is uniform.
Known public key: the observer has compressed P and the same bounded interval. Then kangaroo or BSGS apply, and expected work is on the order of the square root of the interval (or of a chosen window), counted in group operations. #140 is this class: interval width 2139. A w-bit window is not the puzzle.
Address-only (#71 and like it)
270 interval for #71. No public key in this catalog. The scanner derives HASH160 of each candidate scalar and compares it to the address. Expected work is about half the interval under uniformity. That is still 269 hashes, not an inventory you finish because a card is fast. Higher address-only N doubles the list again.
Known public key (#140 and like it)
2139 interval for #140. Public key known to this catalog from the 1,000-sat spend of 1 June 2019, not from a theorem that every unspent address hides P. Kangaroo or BSGS on a w-bit window. Containment 2w−139. At w=96 that is 2−43. Hitting a work budget of about 2 * sqrt(window) group operations does not prove enumeration of the puzzle.
Exhaustive, random, and probabilistic group search
People say search as if it were one verb. The mean, the tail, and the unit of work depend on which process you actually run.
Uniform exhaustive scan
Walk every remaining candidate once. If the unknown key is uniformly placed, the expected number of trials is half the remaining list (2N−2 for a full unused interval of width 2N−1). The median is also near half. Finishing the list is a proof of absence. Partial progress is exactly the fraction walked, not a square-root miracle.
Random sampling
Draw candidates uniformly. With replacement, repeats waste work and you never finish the set in finite time almost surely. Without replacement you have shuffled exhaustive search. Neither process becomes kangaroo because you sampled. Odds tools that treat independent Bernoulli trials are modelling replacement or a fresh window, not a sequential scan of a list.
Probabilistic group operations
Kangaroo and BSGS operate on P = kG inside an interval. Expected group operations scale with the square root of interval size. A finished budget is not a certificate that the key was absent, and it is not a certificate that a contained key was found. Distinguished-point walks collide in expectation; they can miss. Window containment 2w−(N−1) is a separate number from that success probability.
Exact ranges, as integers
Range for puzzle N is the closed interval [2N−1, 2N - 1]. Inclusive width is 2N−1, identical to the start value. Compute that with big integers. IEEE binary64 can hold 270 and 2159 exactly (they are powers of two); it cannot represent 271 − 1, so do not round the endpoints in floating point.
Example: #71 starts at 270 = 0x400000000000000000 and ends at 271 - 1 = 0x7fffffffffffffffff. Candidate count 270. Expected exhaustive HASH160 comparisons 269.
Example: #140 starts at 2139 and ends at 2140 - 1. Candidate count 2139. A 96-bit window inside that interval covers 296 keys, not 2139.
Search bits = N-1 names the width. Catalog bits = N names the scalar length. Do not feed a calculator a fractional, negative, or empty bit width and expect a keyspace.
How a P2PKH spend can publish the public key
A legacy P2PKH spend publishes the public key in its scriptSig the first time any UTXO of that address moves. A receive never does. This catalog's known public keys for the every-fifth series come from that channel. It is not the only theoretical channel, and spent is not a synonym for public key known.
01 — The address stores a hash
The address stores HASH160 of the compressed public key, not the public key.
02 — A receive does not publish P
Until a publication event, an observer of a typical unused P2PKH output has only the hash. The 16 May 2019 deposits of 1,000 sat did not reveal keys.
03 — A legacy spend puts P in scriptSig
A legacy P2PKH spend puts in the scriptSig: signature, then the public key. The 1 June 2019 21-input spend is how this catalog learned the twenty series public keys (#65 to #160, step 5).
04 — P plus a bounded range enables kangaroo
That public key plus the bounded range enable kangaroo or BSGS. Without P they do not. HASH160 search remains the address-only method.
05 — Publication is not a biconditional
Do not write public key available if and only if spent. P can appear with no P2PKH spend (owner publication, a signed message, or the same scalar used in another script). A partial spend can reveal P while a puzzle output remains. Spent does not mean balance zero. A public broadcast shows P before confirmation; on low ranges that is a race. See Claim, and cases #66 and #69.
Kangaroo constants, named
Expected kangaroo work is Theta(sqrt(N)) group operations on an interval of size N. Quote a defined constant. Do not treat a program flag as classical Pollard's formula.
Order-of-magnitude heuristic used on this atlas: about 2 * sqrt(N) group operations. Galbraith, Pollard and Ruprai (ePrint 2010/617) give the van Oorschot–Wiener kangaroo average as (2+o(1))√N.
RCKangaroo's README uses 1.15 times sqrt(range) for its SOTA path and also lists classic K about 2.1 and three-way about 1.6. Those numbers are implementation constants. Quote them as named program parameters, not as an unnamed textbook formula.
A 96-bit window on #140 therefore has expected group operations on the order of 2 * 248, not 296 hashes, and still only containment 2−43 against the full 2139 interval.
The first keys are not a method
saatoshi_rising wrote that there is no pattern. The first four published scalars look like a staircase. Then it stops. Finding #1 does not give #71.
These four scalars are already-public historical solved keys, listed here as arithmetic, not as wallet material. Do not send coins to spent addresses. Do not import them.
#1 scalar 1
1 in binary is 1. Interval [1, 1]. A one-element range is a special case; there is no 20-versus-21 confusion worth turning into a system.
#2 scalar 3
3 in binary is 11. Interval [2, 3].
#3 scalar 7
7 in binary is 111. Interval [4, 7].
#4 scalar 8
8 in binary is 1000. Interval [8, 15]. The run of all-ones integers ends here. Later solved scalars are not a continuation of that picture, and none of this is an algorithm for #71.
Calculators
Exact ranges, kangaroo containment and budget, expected-value arithmetic, log comparisons, and address checks. Public addresses and public keys only. No private keys, WIF, or broadcasts.