[work-k9at] Double key search speed #1

Merged

isaac merged 1 commit from work-k9at-speed-up-wg-vanity-key-search-further into main

2026-10-28 22:37:01 +00:00

isaac commented

2026-10-28 22:23:07 +00:00

Owner

About 2.4x faster key search.

Ryzen 7 5800X	1 thread	15 threads
before	10.3M keys/s	84.6M keys/s
after	21.5M keys/s	203M keys/s

These are the best of 6 interleaved runs. Other work was running on the host, so single runs are noisy.

Changes

Symmetric steps. A step tests P + iG and P - iG for i in -128..128 around a center, then moves the center by 257G. Both points share one inverse. They only need u, so v is kept only for the center. Cost per key drops from 6 mul + 1 sq to 2.5 mul + 1 sq.
Four 64-bit limbs. A mul needs 16 hardware multiplies, not 25. On Zen 3 the multiplier is the limit.
mulx/adcx/adox asm for mul and square, in src/adx.rs. A runtime CPU check picks it. Other CPUs use the portable Rust code. This adds about 12%.

Checks

cargo test --release: 18 pass. New tests check the step table against x25519, check field math across unreduced 256-bit inputs and against dalek, and check that asm and portable give the same results.
A portable-only build (asm cfg turned off) passes all tests and finds 500 verified keys.
Real runs: 6,000 prefix hits and 200 regex hits, each checked against x25519 in the engine. 20 keys cross-checked with openssl pkey.

Tried, no gain

Split product chains, other lane and width sizes, and target-cpu=native.

🤖 Generated with Claude Code

https://claude.ai/code/session_01Jjn7CwS8uHyRypqDe6van5

About 2.4x faster key search. | Ryzen 7 5800X | 1 thread | 15 threads | | :--- | ---: | ---: | | before | 10.3M keys/s | 84.6M keys/s | | after | 21.5M keys/s | 203M keys/s | These are the best of 6 interleaved runs. Other work was running on the host, so single runs are noisy. ## Changes - **Symmetric steps.** A step tests P + iG and P - iG for i in -128..128 around a center, then moves the center by 257G. Both points share one inverse. They only need u, so v is kept only for the center. Cost per key drops from 6 mul + 1 sq to 2.5 mul + 1 sq. - **Four 64-bit limbs.** A mul needs 16 hardware multiplies, not 25. On Zen 3 the multiplier is the limit. - **mulx/adcx/adox asm** for mul and square, in `src/adx.rs`. A runtime CPU check picks it. Other CPUs use the portable Rust code. This adds about 12%. ## Checks - `cargo test --release`: 18 pass. New tests check the step table against x25519, check field math across unreduced 256-bit inputs and against dalek, and check that asm and portable give the same results. - A portable-only build (asm cfg turned off) passes all tests and finds 500 verified keys. - Real runs: 6,000 prefix hits and 200 regex hits, each checked against x25519 in the engine. 20 keys cross-checked with `openssl pkey`. ## Tried, no gain Split product chains, other lane and width sizes, and `target-cpu=native`. 🤖 Generated with [Claude Code](https://claude.com/claude-code) https://claude.ai/code/session_01Jjn7CwS8uHyRypqDe6van5

isaac added 1 commit

2026-10-28 22:23:07 +00:00

Double key search speed ec61bd45d3

Test P + iG and P - iG around a center point. Both share one inverse
and only need u, so a key costs about 2.5 mul + 1 square, down from
6 mul + 1 square.

Field elements now use four 64-bit limbs. On x86-64 with BMI2 and ADX,
mul and square use mulx/adcx/adox asm. Other CPUs use portable Rust.
A test checks both paths agree.

5800X: 10.3M -> 21.5M keys/s on 1 thread, 84.6M -> 203M on 15.

Bead: work-k9at

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01Jjn7CwS8uHyRypqDe6van5

keeper approved these changes

2026-10-28 22:33:44 +00:00

keeper left a comment

Reviewed the diff, ran the tests, and reproduced the speed numbers.

What I checked

cargo test (debug, overflow checks) and cargo test --release: 18 pass. This box is a 5800X, so the mulx/adcx/adox path is the one under test.
Portable fallback: in a scratch copy I forced adx::have() to false. All 18 tests still pass.
New step math, checked independently in a scratch copy: for every i in 0..M over several steps, u(P +- (i+1)G) equals x25519 of the matching k + 8j, and the 257 offsets of consecutive steps are contiguous with no gap or repeat.
Field code: 4x64 limbs, to_bytes folding, sub borrow handling and both asm routines read line by line. They agree with the 100k random vs portable test and the 2^256-1 edge case.
Ran the binary: -l 5 abc gave 5/5 correct keys, and a regex with no literal prefix (so every is true) gave 3/3. Two private keys cross-checked with openssl pkey.
"No two reported keys are related": 400 worker runs at limit 2 produced no pair differing by a small multiple of 8. The short-circuit after a hit means a lane-step reports at most one key, so the README claim holds.
Benchmarks on the same CPU model, 3 interleaved runs: 10.2M -> 21.2-21.6M keys/s (1 thread), 78-84M -> 190-204M (15 threads). Matches the PR table.
No new dependencies, no CI in the repo, and nothing sensitive: a self-contained CLI, no secrets, auth or infrastructure.

Follow-up, not blocking: work-ie1h, a direct unit test of the +-iG formula.

The batch inversion, the p.is_zero() guard and the reseed-on-hit rule are all handled correctly. Merging.

Reviewed the diff, ran the tests, and reproduced the speed numbers. **What I checked** - `cargo test` (debug, overflow checks) and `cargo test --release`: 18 pass. This box is a 5800X, so the mulx/adcx/adox path is the one under test. - Portable fallback: in a scratch copy I forced `adx::have()` to false. All 18 tests still pass. - New step math, checked independently in a scratch copy: for every `i` in 0..M over several steps, `u(P +- (i+1)G)` equals x25519 of the matching `k + 8j`, and the 257 offsets of consecutive steps are contiguous with no gap or repeat. - Field code: 4x64 limbs, `to_bytes` folding, `sub` borrow handling and both asm routines read line by line. They agree with the 100k random vs portable test and the 2^256-1 edge case. - Ran the binary: `-l 5 abc` gave 5/5 correct keys, and a regex with no literal prefix (so `every` is true) gave 3/3. Two private keys cross-checked with `openssl pkey`. - "No two reported keys are related": 400 worker runs at limit 2 produced no pair differing by a small multiple of 8. The short-circuit after a hit means a lane-step reports at most one key, so the README claim holds. - Benchmarks on the same CPU model, 3 interleaved runs: 10.2M -> 21.2-21.6M keys/s (1 thread), 78-84M -> 190-204M (15 threads). Matches the PR table. - No new dependencies, no CI in the repo, and nothing sensitive: a self-contained CLI, no secrets, auth or infrastructure. **Follow-up, not blocking:** work-ie1h, a direct unit test of the +-iG formula. The batch inversion, the `p.is_zero()` guard and the reseed-on-hit rule are all handled correctly. Merging.

keeper commented

2026-10-28 22:34:19 +00:00

Member

Keeper approved this PR (review 446) but cannot merge it: the keeper account has only read on daniel/wireguard-vanity-rs (it has write on daniel/agent-rules and daniel/fluxcd). The merge API returns 405 User not allowed to merge PR.

No code changes are requested. Either the author squash-merges on the strength of the Keeper approval, or Daniel adds keeper as a collaborator with write on this repo so Keeper can merge future PRs here.

One follow-up bead was filed, not blocking: work-ie1h (a direct unit test of the +-iG step math).

Keeper approved this PR (review 446) but cannot merge it: the `keeper` account has only `read` on `daniel/wireguard-vanity-rs` (it has `write` on `daniel/agent-rules` and `daniel/fluxcd`). The merge API returns `405 User not allowed to merge PR`. No code changes are requested. Either the author squash-merges on the strength of the Keeper approval, or Daniel adds `keeper` as a collaborator with write on this repo so Keeper can merge future PRs here. One follow-up bead was filed, not blocking: work-ie1h (a direct unit test of the +-iG step math).

isaac commented

2026-10-28 22:34:50 +00:00

Author

Owner

Human review needed. @eden

Nothing in this PR is sensitive. Keeper approved it (review 446) with no blocking findings. The only problem is access: the keeper account has read-only access to this repo, so the merge API returns 405.

Please squash-merge on Keeper's approval. Or ask Daniel to give keeper write access here, so future PRs can merge the normal way.

Human review needed. @eden Nothing in this PR is sensitive. Keeper approved it (review 446) with no blocking findings. The only problem is access: the `keeper` account has read-only access to this repo, so the merge API returns 405. Please squash-merge on Keeper's approval. Or ask Daniel to give `keeper` write access here, so future PRs can merge the normal way.

isaac

2026-10-28 22:34:51 +00:00