davide
fabefbbb6a
Tre modifiche, tutte a parità di risultato (verificate end-to-end): - Ammortamento della moltiplicazione scalare: prima scalar_mult_basic (l'operazione di gran lunga più costosa) veniva rieseguita a ogni batch, cioè 40 volte per kernel launch. Ora viene eseguita UNA sola volta per launch; il punto base P0 viene poi fatto avanzare di GPU_EC_BATCH_SIZE*G a ogni round con una semplice addizione EC affine, ripiegata nella batch inversion già presente (nuovo slot NEXT negli array Zj/prefix). La scalar mult è così ammortizzata su ~5120 chiavi invece di 128. - Una sola inversione di campo per round invece di due: la normalizzazione del nuovo P0 condivide l'inversione di Montgomery del batch. - Inversione modulare tramite la catena di addizione di libsecp256k1 (255 quadrati + 15 moltiplicazioni) al posto del quadrato-e-moltiplica ingenuo (~256 + ~128). Rimosso il vecchio modinv_fermat e la costante FIELD_P_MINUS_2 non più usata. - Rimosso l'array locale invZ[] (passaggio all'indietro fuso con la conversione affine + match), riducendo la memoria locale per-thread e migliorando l'occupancy. Misurato nello stesso ambiente/scheda: 15.0M -> ~30M keys/sec. Correttezza verificata end-to-end con privkey nota a offset 0, 50, 127, 128 (avanzamento del punto base), 200 e 5119 (40 avanzamenti consecutivi): tutte trovate con la chiave privata corretta. Nessun falso positivo su chiave pubblica valida casuale.
86 lines
8.6 KiB
Markdown
86 lines
8.6 KiB
Markdown
# CLAUDE.md
|
||
|
||
This file provides guidance to Claude Code (claude.ai/code) when working with code in this repository.
|
||
|
||
## Project purpose
|
||
|
||
Educational/research suite for studying Bitcoin P2PK (Pay-to-Public-Key) transactions and demonstrating why ECDSA secp256k1 bruteforce is computationally infeasible (keyspace 2^256). All docs and CLI output are in Italian. Two independent components share data via files, not code:
|
||
|
||
1. `databases/` — Python scanner that walks the Bitcoin blockchain via the mempool.space API, finds P2PK outputs, stores them in SQLite, and checks UTXO spent/unspent status.
|
||
2. `bruteforce/` — CPU (C++/pthreads) and GPU (CUDA) programs that load target public keys and search the private-key space for matches, as a performance demonstration (not a realistic attack — success probability is ~2^-256).
|
||
|
||
Data flows one way: scanner → SQLite DB (`databases/bitcoin_p2pk_study.db`) → `extract_p2pk_utxo.py` filters unspent P2PK → `target_keys.txt` → C++ bruteforce consumes it.
|
||
|
||
## Commands
|
||
|
||
### Python scanner (`databases/`)
|
||
```bash
|
||
python3 -m venv .venv && source .venv/bin/activate
|
||
pip install -r requirements.txt
|
||
|
||
cd databases
|
||
python3 scan_blockchain.py # interactive: prompts for start/end block + delay
|
||
python3 view_db.py # generates p2pk_report.html
|
||
python3 view_db.py --stats # prints stats to terminal
|
||
```
|
||
|
||
### C++ bruteforce (`bruteforce/`)
|
||
```bash
|
||
cd bruteforce
|
||
make install-deps # apt packages: build-essential, libsecp256k1-dev, libgmp-dev, autoconf, libtool, pkg-config
|
||
make # builds secp256k1 locally from source if bruteforce/secp256k1/ doesn't exist (~5 min first time), then compiles p2pk_bruteforce
|
||
make clean # remove binaries/object files
|
||
make clean-all # also removes the locally-built secp256k1 tree
|
||
make debug # -g -O0 build: p2pk_bruteforce_debug
|
||
make bench # 10-second timed run
|
||
make pgo # profile-guided optimization build (3-step: generate → run 30s → use)
|
||
make valgrind # leak check on the debug build
|
||
make help # list all targets
|
||
|
||
python3 extract_p2pk_utxo.py [db_path] [output.txt] # default: ../databases/bitcoin_p2pk_study.db -> target_keys.txt
|
||
python3 extract_p2pk_utxo.py --stats # DB stats only, no extraction
|
||
|
||
./p2pk_bruteforce [target_keys.txt] # runs until Ctrl+C; logs to progress.csv, matches to found_keys.txt
|
||
|
||
# GPU version (CUDA), much faster if an NVIDIA GPU + driver + CUDA Toolkit are available
|
||
make gpu-info # checks nvidia-smi and nvcc are present
|
||
make gpu # NVCC_ARCH defaults to sm_61 (Pascal) — override for other GPUs, e.g. make gpu NVCC_ARCH=sm_86
|
||
./p2pk_bruteforce_gpu [target_keys.txt]
|
||
```
|
||
|
||
There is no test suite in this repo.
|
||
|
||
## Architecture notes
|
||
|
||
### `bruteforce/p2pk_bruteforce.cpp` (CPU, single file, everything lives here)
|
||
- One pthread per (core count − 1); each thread gets a disjoint slice of the 256-bit keyspace via `partition_keyspace` (only the top 64 bits are partitioned — the search relies on random start offsets within each thread's slice, not a full 256-bit range split).
|
||
- Target pubkeys are loaded from a `.txt` file (uncompressed hex, `04` prefix, one per line, header line skipped) into both an `unordered_map<std::array<uint8_t,64>,...>` keyed on raw X||Y bytes (exact match) and a 64MB Bloom filter (fast negative rejection, checked first via `check_match_fast_raw`).
|
||
- Performance trick: one EC scalar multiplication (via libsecp256k1) produces a base point P0, then the next `EC_BATCH_SIZE` (256) keys are derived via Jacobian-coordinate EC point addition (`ec_add_affine_affine`, formulas specialized for Z1=1) against precomputed multiples of G, converted back to affine with a single shared modular inversion per batch (Montgomery's batch-inversion trick, via GMP) instead of one inversion per key.
|
||
- `increment_privkey`/`add_to_privkey` treat the 32-byte scalar as 4 native 64-bit words (little-endian on x86), not as one big-endian integer — this still enumerates the keyspace without collisions, just in a "scrambled" order; don't reuse them to reconstruct an exact scalar from EC math (use `add_small_be256` for that, as `save_found_key` does).
|
||
- Build system auto-detects a local `bruteforce/secp256k1/` (built by `build_secp256k1.sh` targeting this specific CPU with `-march=native`) and links against it via rpath instead of the system lib; falls back to system `libsecp256k1`/`libgmp` if absent.
|
||
- Matches are written to `found_keys.txt`; throughput stats (instantaneous rate, summed across threads) print to stdout and `progress.csv` every `PROGRESS_INTERVAL_SEC` (2s).
|
||
|
||
### `bruteforce/p2pk_bruteforce_gpu.cu` (GPU, CUDA, single file)
|
||
- Same algorithmic strategy as the CPU version (Jacobian batch add + Montgomery batch inversion), but GMP doesn't run on-device, so 256-bit field arithmetic mod the secp256k1 prime is hand-written (`u256` = 4×uint64 limbs, schoolbook multiply via `unsigned __int128`, fast reduction using `2^256 ≡ 2^32+977 (mod p)`). Verified bit-for-bit against `secp256k1_ec_pubkey_create` before trusting it (see conversation/test methodology — no separate test file is checked in).
|
||
- Each CUDA thread is an independent search lane (own random starting privkey, own local batch state), same as a CPU thread — just thousands of them instead of ~11. Per-thread batch size is `GPU_EC_BATCH_SIZE` (128), smaller than the CPU's 256, to keep per-thread local-memory footprint (Jacobian batch arrays) bounded across tens of thousands of concurrent threads.
|
||
- Scalar multiplication (`scalar_mult_basic`, plain double-and-add) runs **once per kernel launch**, not once per batch: the base point P0 is then advanced by `GPU_EC_BATCH_SIZE·G` each round via a cheap affine EC add folded into the batch inversion (the `NEXT` slot in the Zj/prefix arrays), so the expensive scalar mult is amortized over all `GPU_OUTER_ITERS_PER_LAUNCH × GPU_EC_BATCH_SIZE` keys. There is exactly one field inversion per round (Montgomery batch trick), done with the libsecp256k1 addition-chain `modinv` (255 sqr + 15 mul), not naive square-and-multiply.
|
||
- Remaining optimization headroom: double-and-add scalar mult (no wNAF/windowing), schoolbook `mulmod`, and occupancy tuning (grid size / batch size vs per-thread local memory).
|
||
- Host side still uses libsecp256k1 (CPU) only for one-time setup: precomputing G-multiples and validating/loading target keys into a host-sorted array + Bloom filter, both uploaded once to device memory. Device-side matching = Bloom filter check + binary search over the sorted target array.
|
||
- `NVCC_ARCH` in the Makefile defaults to `sm_61` (Pascal) — must match the actual GPU (`make gpu-info` shows compute capability via `nvidia-smi`, then pick the matching `sm_XX`).
|
||
- On WSL2, the NVIDIA driver comes from the Windows host (visible as `nvidia-smi` working out of the box) — only the CUDA Toolkit needs installing inside WSL, never a driver.
|
||
|
||
### `databases/scan_blockchain.py`
|
||
- `P2PKBlockchainScanner` class wraps all mempool.space API access (`get_block_hash`, `get_block_transactions` with pagination, `check_utxo_status`) and SQLite persistence.
|
||
- P2PK detection is deliberately redundant — a script is classified as P2PK if ANY of 4 independent checks match: explicit `scriptpubkey_type`, script byte length (67 or 35 bytes), ASM pattern (`<pubkey> OP_CHECKSIG`), or raw hex pattern (`41<pubkey>ac` / `21<pubkey>ac`). This exists because the API's `scriptpubkey_type` field is not reliable for very old (pre-2012) P2PK outputs.
|
||
- Scanning is resumable: `scan_progress` table (single row, `id=1`) tracks `last_scanned_block`; reruns default to `last_scanned_block + 1`. `UNIQUE(txid, output_index)` on `p2pk_addresses` prevents duplicate inserts, so overlapping scan ranges are safe.
|
||
- This script and its SQLite DB/CSV outputs are intended to be committed and shared across contributors scanning different block ranges (see `.gitignore` — DB/CSV/HTML are NOT excluded).
|
||
|
||
### `bruteforce/extract_p2pk_utxo.py`
|
||
- Reads only `is_unspent = 1` rows from the scanner's DB, strips the `41.../21...ac` script wrapper to get the raw pubkey, and re-adds the `04` prefix.
|
||
- Compressed pubkeys (33-byte, script length 70/hex prefix `21`) are explicitly skipped — the C++ bruteforce only generates and matches uncompressed public keys.
|
||
|
||
## Key coupling to be aware of
|
||
|
||
- The bruteforce binary's target file format (uncompressed hex pubkeys, `04` prefix, header line) is produced exclusively by `extract_p2pk_utxo.py` — if editing one side's format, update the other.
|
||
- `Makefile` CFLAGS use `-march=native`/`-mtune=native` and `-ffast-math`; binaries are not portable across different CPUs and should be rebuilt (`make clean && make`) after moving to different hardware.
|