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 uses progressive tiers with increasing bounds (up to $10M), trying the smallest tier first. Most of the precomputed tables are embedded in the WASM binary; larger tiers are lazy-loaded on demand. The solver is implemented in Rust, compiled to WASM for browser and Node.js, with a native build for iOS.