CUDA Coin Cracker

Coin Cracker is an experimental CUDA/Rust secp256k1 interval DLP solver using a Gaudry-Schost-style walk. Given a compressed secp256k1 public key and a private-key interval, it searches the interval and prints the recovered private key when found.

Warning

No warranty. Use at your own risk. The author is not responsible for damage, loss, misuse, or illegal activity. Only run this against keys and ranges you are authorized to test.

Build requirements

• Rust toolchain.
• NVIDIA GPU with a working CUDA driver and CUDA Toolkit.
• CMake 4.2 or newer.

The CUDA architecture is configured as native.

Build

cargo build --release

The CUDA cubin is generated under Cargo's build output directory and embedded into the final binary.

Usage

coin-cracker \
  --dp-bits <DP_BITS> \
  --public-key <PUBLIC_KEY_HEX> \
  --begin <BEGIN_HEX> \
  --range-bits <BITS>

Use either --range-bits <BITS> or --end <END_HEX>. --begin and --end are parsed as hexadecimal integers. --public-key expects a SEC1 compressed public key hex string.

Other useful options:

• --blocks <N>: override CUDA block count; default is cuda_cores / 128.
• --seed <HEX>: 32-byte RNG seed, encoded as 64 hex characters (for deterministic runs).
• --max-walks <N>: stop after a fixed number of walk calls, useful for smoke tests and benchmarks.

Example

This example searches Bitcoin Puzzle #70:

coin-cracker \
  --dp-bits 16 \
  --public-key 0290e6900a58d33393bc1097b5aed31f2e4e7cbd3e5466af958665bc0121248483 \
  --begin 200000000000000000 \
  --range-bits 69

On success, stdout contains only:

0000000000000000000000000000000000000000000000349B84B6431A6C4EF1

Progress and metrics are logged to stderr:

INFO *** Coin Cracker by lleoha (2026) ***
WARN No warranty. Use at your own risk; the author is not responsible for any damage, loss, or misuse.
INFO gpu_name=NVIDIA GeForce RTX 5060 gpu_cuda_cores=3840
INFO blocks=30
INFO rng_seed=9cbdb115d957c5b8969342918a23be9a76004d7e575fcdd1dcf61bc20abc2eec
INFO kernel_jumps_per_walk=943718400
INFO walk=1 processed_kernels=0 kernel_ms=0.000 kernel_jumps/s=0.000 dp=0 full_buffers=0
INFO walk=2 processed_kernels=6 kernel_ms=337.310 kernel_jumps/s=2797774125.129 dp=14365 full_buffers=0
(...)
INFO walk=46 processed_kernels=6 kernel_ms=350.746 kernel_jumps/s=2690601098.749 dp=14501 full_buffers=0
INFO summary walk_calls=46 processed_kernels=270 startup_wall_s=0.379 gpu_setup_wall_s=0.026 initial_fill_wall_s=0.823 precompute_wall_s=1.228 solve_wall_s=15.722 kernel_ms=15710.930 kernel_jumps=42467328000 event_kernel_jumps/s=2703043570.886 solve_wall_kernel_jumps/s=2701122451.718 dp=647049 dp/s=41155.370 full_buffers=0
INFO centered_secret=0000000000000000000000000000000000000000000000049B84B6431A6C4EF1
INFO total_wall_s=17.244

Gaudry-Schost method

Coin Cracker uses the Gaudry-Schost method for solving DLP in an interval and does NOT use equivalence classes. I decided not to use equivalence classes because this makes the raw jumps/s much higher (about 42% in my hand-wavy tests). Using negation-map equivalence classes would require about 41.4% fewer jumps, but the raw speed would also be about 42% lower, so these effects roughly balance and cancel each other out, while keeping the implementation simpler (no fruitless-cycle handling, etc.). The number of walks is rather large, so DP overhead is also high, and I might work on that in the near future.

The method uses custom tame and wild interval shapes and custom sampling patterns based on the research in Kang-1. This project was heavily inspired by it, so credit goes to RetiredCoder.

Coin Cracker vs RCKangaroo

RCKangaroo uses neither the Pollard Kangaroo method (also known as Pollard Lambda) nor the Gaudry-Schost method. Unlike Pollard Kangaroo, RCKangaroo uses the negation-map equivalence class; unlike Gaudry-Schost, it does not restart the walk when a distinguished point is hit. Instead, it jumps to another part of the interval using a different jump table, so it is a kind of hybrid of the two. Coin Cracker uses vanilla Gaudry-Schost (with interval shapes and sampling patterns borrowed from the SOTAv2 method), which means walks are restarted when DP is hit. New walk start points are computed on CPU, so it also requires a moderately high-end CPU when the DP bits setting is relatively low.

On my test GPU (NVIDIA RTX 5060), RCKangaroo reports throughput of ~1.9 G/s vs. Coin Cracker at ~2.7 G/s.

SOTAv2

The inventor of the SOTAv2 method estimates the average number of samples required to solve DLP to be $\approx 1.15\sqrt{N} = k\sqrt{N}$, but there is not much to back it up from a theoretical math point of view, so I gave it a shot and tried to calculate the theoretical value for the SOTAv2 method.

Caution

I am not a mathematician (actually far from it), so this might be invalid.

The two wild sets are:

$$\begin{aligned} W_1 &= x + E \\\ W_2 &= -x + E \end{aligned}$$

where $E$ is the set of even integers in $\left[-\frac{N}{2}, \frac{N}{2}\right]$. Each wild set has about $\frac{N}{2}$ elements.

The tame interval is $\left[-\alpha\frac{N}{2}, \alpha\frac{N}{2}\right]$ with $0 <\alpha \le 1$ and is split into two sets of odd and even integers, so each tame parity set ($T_1$, $T_2$) has about $\alpha\frac{N}{2}$ elements.

The sampling pattern is: $T_1$, $T_2$, $W_1$, $W_2$, $W_1$, $W_2$.

A key parity point: both wild sets have the same parity as $x$, so if $x$ is even, only one of the tame sets can collide with the wild sets; if $x$ is odd, only $T_1$ can collide, and if $x$ is even, only $T_2$ can collide.

Define:

$$h(u) = \begin{cases} \alpha & 0 \le u \le \frac{1-\alpha}{2} \\\ \frac{1+\alpha}{2} - u & \frac{1-\alpha}{2} \le u \le \frac{1}{2} \\\ \end{cases}$$

to be the scaled overlap length between a wild interval and the tame interval.

For one draw from the active tame parity and one draw from either wild set, the probability of a collision is approximately:

$$\eta_{TW}(u) \sim \frac{2 h(u)}{\alpha N}$$

For one draw from $W_1$ and one draw from $W_2$, the overlap length is $N-2|x| = N(1-2u)$, so:

$$\eta_{WW}(u) \sim \frac{2\left(1-2u\right)}{N}$$

For a given sampling pattern, sampling rates are: $q_T=\frac{1}{6}$, $q_W=\frac{1}{3}$ and the expected number of relevant collisions after $t$ total samples is approximately:

$$\lambda(u) \sim t^2\left[\frac{1}{6}\frac{1}{3}\eta_{TW} + 2\frac{1}{6}\frac{1}{3}\eta_{WW} \right] = \frac{t^2}{9N}\left[\frac{2h(u)}{\alpha} + 2\left(1-2u\right) \right]$$

Let

$$D(u) = \frac{2h(u)}{\alpha} + 2\left(1-2u\right)$$

Then the no-collision probability is approximately:

$$z(t, u) \approx \exp \left(-\frac{t^2D(u)}{9N}\right)$$

so the expected number of samples is:

$$E(u) \sim \frac{3\sqrt{\pi}}{2\sqrt{D(u)}}\sqrt{N} = k\sqrt{N}$$

Averaging over $x \in \left[-\frac{N}{2}, \frac{N}{2}\right]$, or equivalently over $u \in \left[0, \frac{1}{2}\right]$ with density 2, gives:

$$k(\alpha) = 3\sqrt{\pi}\int^{\frac{1}{2}}_0 \frac{du}{\sqrt{D(u)}}$$

The piecewise form of $D(u)$ is:

$$D(u) = \begin{cases} 4 - 4u & 0 \le u \le \frac{1-\alpha}{2} \\\ 3 + \frac{1}{\alpha} - \left(4 + \frac{2}{\alpha}\right)u & \frac{1-\alpha}{2} \le u \le \frac{1}{2} \\\ \end{cases}$$

Integrating gives the closed form:

$$k(\alpha) = 3\sqrt{\pi}\left[1 - \sqrt{\frac{1+\alpha}{2}} + \frac{\alpha}{2\alpha+1} \left( \sqrt{2\left(1+\alpha\right)} - 1 \right) \right]$$

For $\alpha=\frac{1}{64}$ this gives $k \approx 1.565$. To verify this result, I added the SOTAv2 method without equivalence classes to my KangarooLab project, which compares the theoretical $k$ value against empirical results for different methods (BSGS, Pollard Kangaroo, Gaudry-Schost). See the "Gaudry-Schost six-sets" method; it matches almost perfectly.

So what is the theoretical $k$ value of the SOTAv2 method that RCKangaroo uses? Retired Coder uses $\alpha=\frac{1}{8}$, and equivalence classes, which means RCKangaroo's $k$ is:

$$k = \frac{k(\frac{1}{8})}{\sqrt{2}} \approx 1.128$$

The author estimates their $k$ to be $1.15$, which is off by about 2% (probably because of DP overhead and fruitless-cycle handling), which I must say is impressive.

Contributions

Contributions are very welcome. If you see a correctness issue, performance opportunity, cleanup, documentation improvement, or a better way to explain the algorithm, please open an issue or submit a pull request.

This project is experimental and performance-sensitive, so changes are easiest to review when they are focused, include the reasoning behind the approach, and explain how they were tested. Improvements to the CUDA kernel, Rust host code, benchmarks, documentation, and reproducibility are all appreciated.

License

Licensed under either of:

• Apache License, Version 2.0 (LICENSE-APACHE)
• MIT license (LICENSE-MIT)

at your option.