Discrete Logarithm Problem

The discrete logarithm problem (DLP) is the mathematical hardness assumption that secures every Bitcoin key. In its elliptic-curve form (ECDLP), the challenge is: given the generator point G and a public point Q = kG, recover the scalar k. Computing Q from k via point multiplication is fast, but going backward is believed to be computationally infeasible for properly chosen curves. That one-way gap is what lets you safely publish a public key while keeping the matching private key secret.

Why it is hard

The points of an elliptic curve over a finite field form a group with no useful ordering or shortcut structure, so an attacker cannot binary-search or interpolate toward the answer. The best known general attacks, such as baby-step giant-step and Pollard's rho, run in roughly the square root of the group order. For secp256k1, whose order n is about 2²⁵⁶, that means on the order of 2¹²⁸ operations: far beyond the reach of any conceivable classical machine.

The quantum caveat

The discrete logarithm problem is hard only for classical computers. A sufficiently large fault-tolerant quantum computer running Shor's algorithm could solve ECDLP efficiently, which is the threat behind discussions of post-quantum upgrades to Bitcoin. No such machine exists today, and the timeline remains uncertain.

Understanding this problem clarifies why exposing a private key, or reusing addresses in ways that leak structure, is dangerous: the security model assumes the discrete log stays unsolved.