Discrete Logarithm Problem (DLP)
The discrete logarithm problem is the mathematical hardness assumption underlying elliptic curve cryptography and Bitcoin's digital signatures.
Key Takeaways
- The discrete logarithm problem (DLP) is the mathematical foundation of elliptic curve cryptography: given two points on a curve, it is computationally infeasible to determine the scalar that maps one to the other, even though computing the forward operation is fast.
- Bitcoin relies on the DLP for key security: a private key is multiplied by a generator point on the secp256k1 curve to produce a public key, and the best classical attack requires roughly 2128 operations.
- Quantum computers running Shor's algorithm could solve the DLP efficiently, which is why post-quantum cryptography research is critical for Bitcoin's long-term security.
What Is the Discrete Logarithm Problem?
The discrete logarithm problem (DLP) asks: given a generator point G and a resulting point Q on an elliptic curve, find the integer k such that Q = kG. In plain terms, if someone tells you the starting point and the destination, can you figure out how many "steps" were taken? For elliptic curves over large finite fields, no known classical algorithm can answer this efficiently.
This asymmetry is what makes public-key cryptography possible. Computing Q from k and G (called scalar multiplication or point multiplication) takes microseconds. Reversing the operation to recover k from Q and G would take longer than the age of the universe with current hardware. The DLP is not proven to be unsolvable: rather, decades of research have failed to produce an efficient classical solution, and cryptographers treat this empirical hardness as a security guarantee.
Every time a Bitcoin user generates a key pair, creates a digital signature, or broadcasts a transaction, they depend on the DLP being hard. If the DLP were easy, anyone who saw a public key could derive the corresponding private key and steal the associated funds.
How It Works
The DLP exists in several mathematical settings, but Bitcoin uses the elliptic curve variant (sometimes called ECDLP). Here is how the problem maps to Bitcoin's key generation:
- A private key k is chosen as a random 256-bit integer between 1 and n-1, where n is the order of the secp256k1 curve
- The public key Q is computed as Q = kG, where G is the curve's fixed generator point
- Q is published (embedded in a Bitcoin address), while k remains secret
- Anyone can verify signatures made with k by checking them against Q, but cannot recover k from Q
The security of this scheme rests entirely on the assumption that step 2 cannot be reversed: given Q and G, there is no efficient way to compute k.
The secp256k1 Curve
Bitcoin uses the secp256k1 curve, defined by the equation y2 = x3 + 7 over a prime field GF(p), where p = 2256 − 232 − 977. The curve has a cofactor of 1, meaning every point (other than the point at infinity) has the same prime order n. This eliminates certain small-subgroup attacks that affect curves with larger cofactors.
# secp256k1 domain parameters (from SEC 2 standard)
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a = 0x0
b = 0x7
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
h = 0x1 # cofactor
# Forward operation (fast): public_key = k * G
# Reverse operation (hard): k = ??? given public_key and GThe order n is approximately 2256, which defines the size of the private key space. The best generic classical attack (Pollard's rho algorithm) requires roughly the square root of n operations: approximately 2128 group operations. At a trillion operations per second, that would take roughly 1019 years.
Why Scalar Multiplication Is a Trapdoor
Scalar multiplication uses the double-and-add algorithm, which is analogous to square-and-multiply for modular exponentiation. For a 256-bit scalar, this requires at most 256 point doublings and 256 point additions: a few hundred operations total.
Going in reverse, there is no shortcut that exploits the structure of the multiplication. Unlike regular division, "dividing" one elliptic curve point by another has no efficient algorithm. The best approaches (Pollard's rho, baby-step giant-step) are all generic group algorithms that work by systematically searching the space of possible scalars. None exploits the specific algebraic structure of the curve to gain a significant advantage.
Comparison with Hash Functions
The DLP is often compared to hash function preimage resistance, but the two hardness assumptions differ in important ways:
| Property | DLP (secp256k1) | Hash preimage (SHA-256) |
|---|---|---|
| Security level | ~128 bits (Pollard's rho) | ~256 bits (brute force) |
| Quantum impact | Broken by Shor's algorithm | Halved to ~128 bits by Grover's algorithm |
| Mathematical structure | Algebraic (group operations) | Unstructured (bitwise operations) |
| Proof of hardness | No formal proof | No formal proof |
The key difference under quantum attack is structural. SHA-256 mining security drops from 2256 to 2128 under Grover's algorithm: still astronomically hard. The DLP, however, falls completely to Shor's algorithm, which solves it in polynomial time. This is why quantum threats to Bitcoin focus on signatures (DLP-based) rather than mining (hash-based).
Use Cases
The DLP's hardness is not just a Bitcoin detail: it is the foundation of most modern public-key cryptography.
- Bitcoin key generation: every key pair relies on the ECDLP over secp256k1 to keep private keys secret while allowing public key distribution
- Digital signatures: both ECDSA and Schnorr signatures derive their unforgeability from the DLP. Without it, anyone could forge signatures and spend others' funds
- Diffie-Hellman key exchange: two parties can establish a shared secret over an insecure channel because an eavesdropper cannot solve the DLP to recover the secret
- Adaptor signatures and scriptless scripts: advanced Bitcoin protocols use DLP-related constructions to build atomic swaps and conditional payments without on-chain scripts
- Pedersen commitments and confidential transactions: hiding transaction amounts while allowing verification depends on the DLP and a related assumption called the computational Diffie-Hellman problem
Why It Matters for Spark
Spark, a Bitcoin Layer 2 protocol, uses FROST threshold signatures for its cooperative signing model. FROST is built on Schnorr signatures, which in turn rely on the DLP over secp256k1. The security of every virtual UTXO in Spark ultimately traces back to the assumption that the DLP is hard. If the DLP were broken, both on-chain Bitcoin and Layer 2 systems like Spark would need to migrate to post-quantum signature schemes.
Risks and Considerations
The Quantum Threat
Shor's algorithm, running on a sufficiently large quantum computer, can solve the elliptic curve DLP in polynomial time. A March 2026 paper from Google Quantum AI estimated that breaking secp256k1 would require fewer than 1,200 logical qubits and roughly 90 million Toffoli gates: translating to under 500,000 physical qubits on superconducting hardware with current error rates. While no quantum computer with this capability exists today, the estimate represents a roughly 20-fold reduction from prior projections.
The quantum vulnerability primarily affects exposed public keys. Early Bitcoin addresses (Pay-to-Public-Key format) and addresses that have already spent funds (revealing the public key) are most at risk. Modern address types like P2WPKH and P2TR protect the public key behind a hash until spending time, but the key is exposed in the mempool between broadcast and confirmation. For a deeper analysis, see the research article on harvest-now-decrypt-later attacks and post-quantum cryptography threats to Bitcoin.
Assumed, Not Proven
The hardness of the DLP is a conjecture, not a theorem. No one has proved that an efficient classical algorithm cannot exist. Cryptographers rely on the fact that decades of intense research have failed to produce one. This is similar to the status of P vs NP: widely believed to be hard, but unproven.
Index calculus methods, which provide subexponential attacks on DLP in certain finite field settings, have been adapted to elliptic curves under heuristic assumptions. So far, these adaptations have not produced practical attacks on curves like secp256k1 with prime-order groups, but ongoing research means the landscape could shift.
Curve Choice Matters
Not all elliptic curves offer the same DLP hardness. Supersingular curves and anomalous curves (where the curve order equals the field size) admit efficient discrete logarithm algorithms. The security of secp256k1 depends on its specific parameter choices: a large prime field, a prime-order group, and a cofactor of 1. Using a poorly chosen curve could reduce the DLP to a trivial problem.
Post-Quantum Migration
Bitcoin proposals like BIP-360 introduce quantum-resistant address formats using hash-based or lattice-based signature schemes that do not rely on the DLP. The challenge is migrating the existing UTXO set, especially coins in addresses with exposed public keys, before quantum computers reach sufficient scale. For details on the migration roadmap, see the research on Taproot's quantum vulnerability and NIST post-quantum standards.
This glossary entry is for informational purposes only and does not constitute financial or investment advice. Always do your own research before using any protocol or technology.