基于GPU加速的Pollard袋鼠算法，用于求解secp256k1上的椭圆曲线离散对数问题（ECDLP）。
--benchmark测试硬件，使用--save-benchmarks记录结果现有的大多数袋鼠算法实现（如JeanLucPons/Kangaroo、RCKangaroo等）仅通过CUDA支持NVIDIA GPU。本实现采用WebGPU/wgpu，通过Vulkan、Metal和DX12提供跨平台GPU计算。
paru -S kangaroo
cargo install kangaroo
git clone https://github.com/oritwoen/kangaroo
cd kangaroo
cargo build --release
cargo build --release --features boha
kangaroo --pubkey <PUBKEY> --start <START> --range <BITS>
必须提供--target或--pubkey。
使用数据提供者（boha）：
# Solve puzzle using boha data (auto: pubkey, start, range)
kangaroo --target boha:b1000/66
# Override range (search smaller subset)
kangaroo --target boha:b1000/66 --range 60
# List available puzzles
kangaroo --list-providers
手动参数：
kangaroo \
--pubkey 03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4 \
--start 8000000000 \
--range 40
带模约束（k ≡ 37 mod 60）：
kangaroo \
--pubkey 03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4 \
--start 8000000000 \
--range 40 \
--mod-step 3c \
--mod-start 25
这将搜索空间缩小约60倍。当部分密钥结构已知时（例如，密钥由可预测的步长模式生成），此功能很有用。
Pollard袋鼠算法在O(√n)时间内解决离散对数问题，其中n为搜索范围。其工作原理如下：
区分点（DP）优化：不存储所有访问过的点，而是仅存储x坐标具有特定位数前导零的点。这大大减少了内存使用，同时仍能进行碰撞检测。
Expected operations: ~2^(range_bits/2)
运行kangaroo --benchmark测试硬件，无需修改文件。使用kangaroo --benchmark --save-benchmarks更新BENCHMARKS.md。
| 使用场景 | 示例 |
|---|---|
| 部分密钥已解码 | 谜题给出约240位，需找到剩余约16位 |
| 密钥在已知范围内 | 已知密钥在X与Y之间 |
| 验证近解 | 已有候选值，在其周围搜索±N位 |
不适用于：
use kangaroo::{KangarooSolver, GpuContext, GpuBackend, parse_pubkey, parse_hex_u256, verify_key};
fn main() -> anyhow::Result<()> {
let pubkey = parse_pubkey("03...")?;
let start = parse_hex_u256("8000000000")?;
let ctx = pollster::block_on(GpuContext::new(0, GpuBackend::Auto))?;
let mut solver = KangarooSolver::new(
ctx,
pubkey.clone(),
start,
40, // range_bits
12, // dp_bits
1024, // num_kangaroos
)?;
loop {
if let Some(key) = solver.step()? {
if verify_key(&key, &pubkey) {
println!("Found: {}", hex::encode(&key));
break;
}
}
}
Ok(())
}
袋鼠支持用于谜题来源的外部数据提供者。提供者提供公钥、密钥范围及其他谜题元数据。
boha 提供包括比特币谜题交易（b1000）在内的加密谜题数据。
使用boha支持编译：
cargo build --release --features boha
用法：
# Solve specific puzzle
kangaroo --target boha:b1000/66
# List solvable puzzles (unsolved with known pubkey)
kangaroo --list-providers
提供者会验证范围覆盖 – 你不能搜索超出谜题密钥范围的值。
src/
├── main.rs # CLI entry point
├── lib.rs # Library entry + Args + run()
├── solver.rs # GPU solver coordination
├── cli.rs # CLI utilities (tracing, progress bar)
├── benchmark.rs # Built-in benchmark suite
├── modular.rs # Modular constraint transformation
├── math.rs # 256-bit arithmetic, DP mask generation
├── convert.rs # Limb/byte conversions for GPU↔CPU
├── provider/
│ ├── mod.rs # Provider system interface
│ └── boha.rs # boha provider (feature-gated)
├── cpu/
│ ├── cpu_solver.rs # Pure CPU solver (testing/comparison)
│ ├── dp_table.rs # Distinguished Points collision detection
│ └── init.rs # Kangaroo initialization + jump tables
├── crypto/
│ └── mod.rs # k256/secp256k1 wrappers
├── gpu/
│ ├── pipeline.rs # Compute pipeline setup
│ └── buffers.rs # GPU buffer management
├── gpu_crypto/
│ ├── context.rs # GPU context + backend selection
│ └── shaders/ # WGSL shader library
│ ├── field.wgsl # secp256k1 field arithmetic
│ └── curve.wgsl # Jacobian point operations
└── shaders/
└── kangaroo_affine.wgsl # Main Kangaroo compute shader
MIT许可证 - 详见LICENSE。
| 参数 | 默认值 | 描述 |
|---|
-t, --target | - | 数据提供者目标（例如 boha:b1000/135） |
-p, --pubkey | - | 目标公钥（压缩十六进制，33字节） |
-s, --start | 0 | 搜索范围起始（十六进制，不含0x前缀） |
-r, --range | 32 | 搜索范围位数（密钥在[start, start + 2^range - 1]内） |
-d, --dp-bits | auto | 区分点位数 |
-k, --kangaroos | auto | 并行袋鼠数量 |
--gpu | 0 | GPU设备索引 |
--backend | auto | GPU后端：auto、vulkan、dx12、metal、gl |
-o, --output | - | 结果输出文件 |
-q, --quiet | false | 最小输出，仅打印找到的密钥 |
--max-ops | 0 | 最大操作数（0 = 无限制） |
--cpu | false | 使用CPU求解器替代GPU |
--json | false | 以JSON格式输出基准测试结果 |
--benchmark | false | 运行基准测试套件 |
--save-benchmarks | false | 当使用--benchmark时将基准测试结果保存到BENCHMARKS.md |
--mod-step | 1 | 模步长M（十六进制）：仅搜索k ≡ R (mod M) |
--mod-start | 0 | 模余数R（十六进制）：0 ≤ R < M |
--list-providers | false | 列出提供者中的可用谜题 |