F find v0.1.6
Install
Educational · Research · Rust 2021

secp256k1, decomposed into 512 parallel paths.

A research-grade Rust engine that finds secp256k1 scalars with sub-second throughput. Powered by 512-variant range-splitting, Montgomery batch inversion, and a Radix16 fixed-base table — wired together with zero unsafe in the hot path.

Install Star on GitHub crates.io
Throughput
10⁶/s
Hot-path unsafe
1 block
Variants
512
y x y² = x³ + 7 (mod p) G −G P −P j·G x ≡ x(P − V·G)
Pure Rust 2021 MSRV 1.81 Linux · macOS · Windows x86_64 · aarch64 MIT licensed
What it does

A working reference for Montgomery-batch elliptic-curve search.

Given a secp256k1 target P = d·G, the engine searches for scalars j and offsets V such that x(j·G) = x(P − V·G) , yielding candidate keys d = V ± j (mod n) — a textbook multi-variant range-splitting implementation, end-to-end tested.

~/find — zsh — 92×24

512-variant range-splitting

The search space is decomposed via powers-of-two and cumulative-sum offsets. Metadata is interned OnceLock<[OffsetVariant; 512]> — zero allocations per session.

Montgomery batch inversion

One inversion per batch_size-point batch instead of N. Drops the normalization phase by ~15–20× on a default batch of 32.

Radix16 fixed-base table

A 33-entry lookup table (~30 KB static, lazily built) roughly halves the bootstrap scalar-mul cost. Measured end-to-end speedup: 2.80×.

Engineered details

Built for clarity, tuned for speed.

Lock-free early-exit

OnceLock<SearchMatch> replaces the classic Mutex + AtomicBool pair. The first thread to find a hit publishes the result; the rest exit through rayon’s work-stealing scheduler with zero contention.

Atomic checkpointing

Write-then-rename persists every boundary with an integrity anchor. Crash mid-sweep, restart from the exact j — no duplicate work, no corrupted state.

Runtime-sized batches

Vec<ProjectivePoint> sized against Config::batch_size (1..=256). --batch-size is finally honoured at runtime; peak heap is bounded by your input, not a hard-coded constant.

Binary cache (~100×)

Optional precomputation persists X-coordinates to disk. On NVMe, the cached sweep path hits 10⁸ scalars/sec — about 100× the CPU-bound path. Auto-disabled in address mode.

Structured observability

tracing + tracing-subscriber with non-blocking daily-rolling files. RUST_LOG-style filtering, audit boundaries every TRILLION scalars, and rayon-panic-safe worker handlers.

Five verification layers

KAT against SEC1 §2.7.1, differential vs libsecp256k1, end-to-end audit, randomized integration, and six cargo-fuzz targets — all reproducible with a single cargo test.

Strict lints, zero noise

Curated pedantic + nursery clippy sets gated by -D warnings. Documented allow-list, no #[allow(unused)] scattered in the source. If clippy is silent, the code is clean.

Pure search domain

find::search owns no I/O. All persistence is behind the CacheWriter trait — the hot loop stays pure, testable, and free of side effects.

Clean public crate API

find::config, find::ecc, find::orchestrator, find::search, find::error. Result<Option<SearchMatch>, FindError> at every public boundary. #![warn(missing_docs)] on the crate root.

Performance

Measured, not promised.

Reproducible on an Apple M3 Pro at opt-level=3, lto=fat, criterion 100 samples. Numbers are pinned to a single canonical commit and propagated identically through the changelog and benchmarks doc.

10M scalars end-to-end

1.88 ms

vs 5.27 ms before precomputed-tables

End-to-end speedup

2.80×

Radix16 fixed-base table (commit series)

Less per-batch cycles

18%

chain + Montgomery + match, batch_size=64

Cached-sweep speedup

100×

NVMe binary cache vs CPU path

cargo bench --bench bench
Apple M3 Pro · LTO fat
Benchmark Before After Speedup
plus_g_chain / chain_32_plus_g 33.78 µs 17.99 µs 1.88×
plus_g_chain / naive_32_scalar_muls 919.88 µs 423.73 µs 2.17×
match_x / aligned_slice — 31.6 ns —
batch_normalization / 32_points — 38.5 µs ~15–20×
end_to_end_small_scalar_12345 / 10M 5.27 ms 1.886 ms 2.80×
Two input modes

Pubkey sweep, or address-keyed range search.

Same engine, two entry points. Config::new vs Config::new_address_mode select the surface — the hot loop stays identical and the verification layers apply to both.

Default ADR ↗

Pubkey mode

Search the full scalar space for an X-coordinate match against a SEC1 compressed public key. The traditional variant-keyed sweep used by the discovery engine.

terminal 
find --pubkey 0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
find --pubkey 0279be66... \
     --cache-points \
     --batch-size 64 \
     --variants 256
Address mode ADR ↗

Hash40-targeted discovery

Search a user-specified scalar range [from, to] for the scalar behind a Bitcoin mainnet P2PKH/P2SH address. Hash40 compare keeps the inner loop cheap.

terminal 
find --address 1A1zP1eP5QGefi2DMPTfTL5SLmv7DivfNa \
     --from 1 --to 100000000
find --address 1A1zP1eP5QGefi2DMPTfTL5SLmv7DivfNa \
     --from 0x1 --to 0x5F5E100
--pubkey <hex> · --address <base58> · --from <int|hex> · --to <int|hex> · --batch-size 1..=256 · --variants 1..=512 · --cache-points
Architecture

One pipeline, eight stages.

The orchestrator is a thin coordinator. The heavy lifting lives in find::search — a pure, I/O-free module whose entire surface is exercised by 200+ integration cases.

  1. 01

    parse_pubkey stage

    SEC1 compressed · 33 bytes · deep validate

  2. 02

    generate_variants stage

    512 × (label, offset, x_bytes) · OnceLock-interned

  3. 03

    VariantIndex stage

    flat sorted Vec, L1-resident, O(log 512)

  4. 04

    sweep_parallel stage

    rayon · batch_size · match_x binary search

  5. 05

    batch_normalize stage

    Montgomery simultaneous inversion · 1 + N mults

  6. 06

    publish match stage

    OnceLock<SearchMatch> · lock-free early-exit

  7. 07

    checkpoint stage

    atomic write-then-rename · fsync · JSON

Verification

Five layers. One local gate.

Every public function has a unit test. Every pipeline has an integration test. Every change is gated by the same five commands CI runs — no separate local recipe.

KAT

13

Known-answer tests against SEC1 §2.7.1 vectors and k256 reference outputs, plus a to_hex_x ↔ x_bytes round-trip regression.

Differential

12

Cross-check vs the reference C libsecp256k1 across boundary scalars (1, 2, 7, 100, 1k, 1M, 1.2G, 2³², 2⁶³, u64::MAX, …).

Audit

21

End-to-end pipeline (parse → variants → sweep → recover) for the known scalar 1234567890, plus a 20-case proptest over [2, 10_000].

Integration

60+

Randomized discovery, prop_batch_size_runtime (1..=256), prop_search_finds_any_scalar_in_range, edge cases.

Fuzz

6

cargo-fuzz targets for every public API: parse_pubkey, parse_pubkey_roundtrip, hex_to_scalar, scalar_mul_g, generate_variants, match_x.

Suite size

71

lib unit tests

200+

integration

13

KAT vectors

12

differential

6

fuzz targets

9

criterion benches

make all-checks
CI · Ubuntu · macOS · Windows
  1. 01 cargo fmt --all -- --check
  2. 02 cargo clippy --all-targets --all-features -- -D warnings
  3. 03 cargo test --all-targets --all-features
  4. 04 cargo test --doc
  5. 05 RUSTDOCFLAGS=-D warnings cargo doc --no-deps --all-features
Get started

Three commands to your first sweep.

Install from crates.io, build from source, or use the library API. The whole crate compiles in seconds on a modern laptop and produces a single statically-linked binary.

Install from crates.io View on GitHub Browse the API
shell 
# Install
$ cargo install find

# Or build from source
$ git clone https://github.com/sachncs/find
$ cd find && cargo build --release

# Run
$ find --pubkey 0279be66...

  "match": null,
  "probed": 1247823104,
  "elapsed_secs": 2.84