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 reference implementation 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 ~50% 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.