Mastering Bitcoin 3rd edition goes through the math of ECDSA, if that helps.
Discussion
I'll go back to that and check it out as a resource.
I'm looking for a good "why". A lot of text just make the assertion that it's harder for log than exponent without digging into the "why".
Intuitively, discrete log is hard for the same reason that division is harder than multiplication in standard arithmetic—you have to search for the answer.
In standard multiplication, there’s a straightforward, if tedious, process for finding the answer. You multiply the component digits, then add everything up.
In long division, you have to guess the right number, then multiply, then subtract, then guess again. It’s the guesses that are expensive.
In standard long division, you develop an intuition about what number to guess. That’s because the numeric field is continuous and linear (number line).
But in cryptography we use modulo arithmetic over discrete fields. Modulo means it wraps around. Discrete means no fractions.
So, for example, math in mod 7 would only use the numbers 0, 1, 2, 3, 4, 5, and 6. Any mathematical result that would normally be outside these bounds gets capped by wrapping back to the beginning. 5 + 3 = 1, for instance, because there is no 7 so you wrap around back to 0.
On such a small field (mod 7), division isn’t very expensive. You can just check all 7 choices to see what multiplies to the chosen value. But the fields used by cryptography are enormous. The prime field used by secpk256 (#Bitcoin’s elliptic curve) is only slightly smaller than 2^256.
To make things even harder, rather than having all the numbers be scalars in a line (0, 1, 2, …), elliptic curve cryptography uses points on a curve. The formula for secpk256 is:
y^2 = x^3 + 7
Given any two points that both satisfy this equation, you can add them together, much like in standard arithmetic. Adding a point to itself is like multiplication (2x). Division is the opposite operation: finding the number, which multiplied by a given point gives another given point.
For some reason, these multiplication and division operations are called power and log in elliptic curve math. So the “discrete log problem” is really performing division in the elliptic curve space of an extremely large prime field.
The discrete log problem is hard because there’s no way to go back through the modulus operator that clips the discrete field, causing it to wrap around. The only way to perform division on the elliptic curve is to search, but the prime field is so large as to make this impossible.
I think the reason texts assert that it’s hard, rather than explaining, is that the above is a relatively short explanation. And even at this length has to hand-wave away some details.
So most texts leave the explanation to actual math discussion. To explain why requires a bit of a a side quest to describe modulo arithmetic, prime fields and elliptic curves.
aren't there also "shortcuts" for doing multiplication and thus exponentials?
Yes in multiplication. No in division.
In naive multiplication, you repeat addition over and over. So 5 x 7 = 5 + 5 + 5 + 5 + 5 + 5 + 5
You can reduce the number of steps by converting the multiplicand to binary, and then going through the 0’s and 1’s. At each digit, you double the previous number (bit shift), then add it again if the digit is a 1. This shortcut works in elliptic curve math to make multiplication fast.
Division, the inverse operation, has no known comparable shortcut. The security of Bitcoin keys rests on such a shortcut not existing, or at least not being discovered.
Part of the hubbub over quantum computing is that, at sufficient scale, it would offer such a shortcut. The search space of the large prime field is too large for a conventional computer to search. But a sufficiently advanced quantum computer could, in principle, test all values in parallel.
this makes Sense, thanks for sharing
The idea that a singular centralized entity can even perform a meaningful computation with qubits is entirely speculative and has not been proven real.
Not to mention the inherent flawed approach by attempting to compute via a singular computer (node) with a singular observer (miner) and a forced consensus mechanism. Yet physicists still think they can solve decoherence that way 😂.
Bitcoins been here for 16 years; all
UTXOs remain coherent.
Agreed that there is a lot of hype around quantum. Hard to predict if/how/when practical applications will be developed.
The history of cryptographic systems shows that they tend to fall over long enough time scales. For this reason, my baseline expectation (Baysian prior) is that weaknesses in ECDSA will eventually be found and exploited. Whether by conventional computing or quantum.
As long as these weaknesses are discovered and exploited slowly, #Bitcoin can adapt. We can soft-fork in new signature schemes. The bulk of existing UTXOs can be migrated, even if a few get cracked in the process.
A zero-day fast crack of ECDSA would break “your keys, your coins”. This is the only existential threat to Bitcoin that I know of. Fortunately, it seems incredibly unlikely.
Yeah I see it much differently. Bitcoin is the missing language to quantum mechanics; it’s the same system of rules as Bitcoin. Like identical. A peer to peer electron(ic) cash system just is the transactional mechanics which uphold conservation of energy.
There’s a quantum computer, it’s called Bitcoin. There is no second best. The most important thing for a quantum computer to compute is perfect money, that’s already been computed….No one wants to admit we’ve all been wrong for 16 years. We as users compute the meaning to our UTXOs, not central authority.
I believe ECDSA is a mathematical and universal thermodynamic limit. The premise of quantum computing is that you can force close state and brute force coherence via artificial temperature without any recognition of the energy required to for a shared resolution process.
It’s attempting to break Planck Time, yet Bitcoin and Lightning specifically highlights the ability for unresolved states to exist between Blocks. It’s fiat.
Bitcoins biggest vulnerability is in the social domain, where users are convinced to adopt a BIP/hardfork to protect against something the universe fundamentally doesn’t allow. Trust the physicists; we’re too stupid to understand quantum mechanics.