Kangaroo

GPU で高速化された Pollard's Kangaroo アルゴリズム。secp256k1 上の楕円曲線離散対数問題（ECDLP）を解くためのツールです。

特徴

🖥️ クロスプラットフォーム GPU — Vulkan（AMD、NVIDIA、Intel）、Metal（Apple Silicon）、DX12（Windows）を wgpu 経由でサポート
🦀 Pure Rust + WGSL — CUDA に依存せず、コンピュートシェーダーを実行時にコンパイル
⚡ Distinguished Points — 自動調整される DP ビットによる効率的な衝突検出
🔄 Negation map — Y パリティによる方向付きウォークとサイクルガードにより約 1.29 倍の高速化
🦘 マルチセットカンガルー — タame、ワイルド1、ワイルド2 の群れにより衝突確率を向上
🎯 モジュラー制約 — k ≡ R (mod M) の場合、探索空間を M 分の 1 に削減
⚙️ 自動キャリブレーション — 起動時に GPU ディスパッチタイミングとワークグループサイズを調整
📊 組み込みベンチマーク — --benchmark でハードウェアをテスト、--save-benchmarks で結果を記録
📦 データプロバイダー — プラグイン可能なパズルソース（boha 連携によるビットコインパズル対応）
💻 CPU フォールバック — テスト・比較用の純粋な CPU ソルバー

なぜこのプロジェクトか？

既存の Kangaroo 実装（JeanLucPons/Kangaroo、RCKangaroo など）は CUDA 経由で NVIDIA GPU のみをサポートしています。この実装では WebGPU/wgpu を使用しており、Vulkan、Metal、DX12 を通じてクロスプラットフォームの GPU 計算を提供します。

インストール

Arch Linux（AUR）

paru -S kangaroo

Cargo

cargo install kangaroo

ソースから

git clone https://github.com/oritwoen/kangaroo
cd kangaroo
cargo build --release

boha プロバイダーを使用する場合

cargo build --release --features boha

使い方

kangaroo --pubkey <PUBKEY> --start <START> --range <BITS>

引数

--target または --pubkey のいずれかが必要です。

例

データプロバイダー（boha）を使用する場合：

# boha データを使ってパズルを解く（自動：pubkey、start、range）
kangaroo --target boha:b1000/66

# 範囲を上書き（より小さな部分集合を検索）
kangaroo --target boha:b1000/66 --range 60

# 利用可能なパズルを一覧表示
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 分の 1 に削減されます。鍵の部分構造が分かっている場合（例：予測可能なステップパターンで生成された鍵）に便利です。

仕組み

Pollard's Kangaroo アルゴリズムは、離散対数問題を O(√n) 時間で解きます（n は探索範囲）。動作は以下の通りです。

タame カンガルー は既知の点からスタートし、ランダムなジャンプを行います
ワイルドカンガルー はターゲットの公開鍵からスタートし、同じ種類のジャンプを行います
ワイルドとタame のカンガルーが同じ点に着地した（衝突）場合、秘密鍵を計算できます

Distinguished Points（DP）最適化： 訪問したすべての点を保存する代わりに、x 座標が特定の数の先頭ゼロビットを持つ点のみを保存します。これによりメモリ使用量が大幅に削減されつつ、衝突検出が可能になります。

パフォーマンス

期待される操作数：約 2^(range_bits/2)

kangaroo --benchmark を実行して、ファイルに触れることなくハードウェアをテストできます。kangaroo --benchmark --save-benchmarks を使用して BENCHMARKS.md を更新してください。

ユースケース

ユースケース	例
部分的な鍵が復号された	パズルが約 240 ビットを提供し、残り約 16 ビットを見つける必要がある
鍵が既知の範囲内にある	鍵が X と Y の間にあることが分かっている
ニアソリューションの検証	候補があり、その周辺 ±N ビットを検索する

役に立たない用途：

フル 256 ビット鍵の探索（数学的に不可能）
BIP39 パスフレーズのブルートフォース（代わりに辞書攻撃を使用）
部分的な鍵情報のないパズル

ライブラリとしての使用

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(())
}

データプロバイダー

Kangaroo はパズルソース用の外部データプロバイダーをサポートしています。プロバイダーは公開鍵、鍵範囲、その他のパズルメタデータを供給します。

boha（オプション機能）

boha は、ビットコインパズルトランザクション（b1000）を含む暗号パズルデータを提供します。

boha サポート付きでビルド：

cargo build --release --features boha

使い方：

# 特定のパズルを解く
kangaroo --target boha:b1000/66

# 解けるパズルを一覧表示（未解決で公開鍵が既知のもの）
kangaroo --list-providers

プロバイダーは範囲の上書きを検証します。パズルの鍵範囲外を検索することはできません。

アーキテクチャ

src/
├── main.rs              # CLI エントリポイント
├── lib.rs               # ライブラリエントリ + Args + run()
├── solver.rs            # GPU ソルバー調整
├── cli.rs               # CLI ユーティリティ（トレーシング、プログレスバー）
├── benchmark.rs         # 組み込みベンチマークスイート
├── modular.rs           # モジュラー制約変換
├── math.rs              # 256 ビット演算、DP マスク生成
├── convert.rs           # GPU↔CPU の Limb/バイト変換
├── provider/
│   ├── mod.rs           # プロバイダーシステムインターフェース
│   └── boha.rs          # boha プロバイダー（機能ゲート）
├── cpu/
│   ├── cpu_solver.rs    # 純粋な CPU ソルバー（テスト・比較用）
│   ├── dp_table.rs      # Distinguished Points 衝突検出
│   └── init.rs          # カンガルー初期化 + ジャンプテーブル
├── crypto/
│   └── mod.rs           # k256/secp256k1 ラッパー
├── gpu/
│   ├── pipeline.rs      # 計算パイプラインのセットアップ
│   └── buffers.rs       # GPU バッファ管理
├── gpu_crypto/
│   ├── context.rs       # GPU コンテキスト + バックエンド選択
│   └── shaders/         # WGSL シェーダーライブラリ
│       ├── field.wgsl   # secp256k1 体演算
│       └── curve.wgsl   # ヤコビアン点演算
└── shaders/
    └── kangaroo_affine.wgsl  # メインの Kangaroo 計算シェーダー

要件

Rust 1.70+
Vulkan 対応 GPU（AMD、NVIDIA、Intel）または Metal（macOS）
Linux で AMD RADV を使用する場合、Mesa 25.x 以降が必要（古い Mesa バージョンではシェーダーループ内の WGSL 動的インデックスでクラッシュする可能性あり）
GPU ドライバーがインストールされていること

ライセンス

MIT ライセンス - 詳細は LICENSE を参照してください。

`-t, --target`	-	データプロバイダーのターゲット（例：`boha:b1000/135`）
`-p, --pubkey`	-	ターゲットの公開鍵（圧縮 hex、33 バイト）
`-s, --start`	0	検索範囲の開始値（hex、0x プレフィックスなし）
`-r, --range`	32	検索範囲のビット数（鍵は [start, start + 2^range - 1] の範囲）
`-d, --dp-bits`	auto	Distinguished point のビット数
`-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	GPU の代わりに CPU ソルバーを使用
`--json`	false	ベンチマーク結果を JSON 形式で出力
`--benchmark`	false	ベンチマークスイートを実行
`--save-benchmarks`	false	`--benchmark` 使用時にベンチマーク結果を `BENCHMARKS.md` に保存
`--mod-step`	1	モジュラーステップ M（hex）：k ≡ R (mod M) のみ検索
`--mod-start`	0	モジュラー剰余 R（hex）：0 ≤ R < M
`--list-providers`	false	プロバイダーから利用可能なパズルを一覧表示

kangaroo

人気