Discrete-Log Solver
Why decryption requires solving a discrete log
ElGamal in exponential form encrypts a scalar m as the point m·G. This is what makes it additively homomorphic — m·G + n·G = (m+n)·G — but it means decryption only recovers the point m·G, not the scalar m itself. Recovering m from m·G is the Elliptic Curve Discrete Logarithm Problem (ECDLP).
Why we can solve it
The general ECDLP over Grumpkin's ~254-bit order is computationally infeasible — that's what makes elliptic curve cryptography secure. But we don't need to solve the general problem. We're solving the bounded case: given m·G, find m knowing that 0 ≤ m < N for some known bound N.
This bounded variant has complexity O(√N) using algorithms like Baby-Step Giant-Step or Pollard's Kangaroo, compared to O(√p) for the general case where p ≈ 2²⁵⁴. The difference is the entire gap between feasible and infeasible.
The bound comes directly from the use case: m represents a token balance. Any ERC-20 token has a finite totalSupply, and no account can hold more than that. Stablecoins with 6 decimals keep the numbers particularly small — even $10M is only 10¹³ micro-units, roughly 2⁴³. Solving the discrete log over a 2⁴³ search space takes milliseconds, not millennia.
Implementation
The solver uses Boosted Kangaroos — a Pollard's Kangaroo variant where tame distinguished points are precomputed offline and embedded in the binary. At runtime, only wild kangaroos run, checking collisions against the precomputed tables. This cuts roughly half of the online work.
The solver searches 7 progressive tiers with increasing bounds ($500 → $10M), trying the smallest tier first. Precomputed tame DP tables can be embedded in the binary (configurable per tier via feature flags) or accumulated at runtime through a caching strategy where DPs grow across multiple solve calls. The solver is implemented in Rust (crates/solver) with support for sequential and parallel execution (one thread per tier). The sibling crates/solver-tools crate hosts the platform bindings (wasm-bindgen for browsers, with optional rayon threading; UniFFI for iOS) and the build pipeline that produces them.