Hacker News Reader

Comment by tromp | Hacker News Reader

I'd be more inclined to believe their P=NP claim if they used it to grab all of Satoshi's bitcoins. That should be the first order of business for anyone finding an efficient algorithm for the ECDLP (Elliptic Curve Discrete Log Problem), as implied by their constructive proof.

View on HN

A proof that P=NP doesn't necessarily mean that NP-hard problems are solvable in any practical sense. The time complexity claimed by the paper, O(n^2 * m^3), grows quickly, and the constant factors may be high. In fact, I'd go so far as to say it's very unlikely that a P=NP proof would make any difference in practice, since SAT solvers are so good for real-world problems.

(I'm leaving aside the fact that cryptocurrency theft is a crime that most people would be disinclined to commit, as well as the extraordinarily high likelihood that this proof is incorrect.)

> cryptocurrency theft is a crime

If you know the private key, then you own the coins.

At least that's the whole basis that crypto currency is founded on...

Except most legal systems don’t see it that way. When you say this, they hear “if you have a copy of the key to a house/car/etc, then you also own it”. Cryptocurrency theft is a crime by the basic definitions of the legal system.

That is not how the law works. It's equivalent to knowing your bank account number and routing number and making an unauthorized transaction.

That's just not how keys work. If someone finds the key to my house and uses it to open the door and take something, it's still theft.

Only works if they have been moved. Addresses start out as hashes of ECC keys, not the keys themselves

The problem of "find a series of bytes that is a valid transaction sending these bitcoins to me" is an NP problem. When you can solve arbitrary "find satisfying input" problems, details like "the public key is hashed" don't matter. It's adjusting what it means to be valid, not changing the nature of the problem to be out of scope of "find satisfying input".

Besides, Satoshi's coins are P2PK (Pay to Public Key), not P2PKH (Pay to Public Key Hash), so the point is moot.

The decision problem for ECDLP is not known to be NP-complete, in fact it's likely not NP-complete but rather NP-hard and therefore proving that P = NP would not provide any insight into finding a polynomial time solution for it.

Having an efficient algorithm for SAT (or any NP complete problem) immediately gives you an efficient algorithm for ALL problems in NP, including ECDLP.

It is not known if the decision problem for ECDLP is in NP, in fact it's likely not in NP.

NP-hard does not mean NP, it means a problem that is ATLEAST as hard as NP. NP-hard problems that are in NP are known as NP-Complete.

Finally ECDLP itself is not a decision problem, so even if the decision problem for ECDLP is in NP and P = NP, that does not mean that ECDLP itself has a polynomial time solution.

NP, NP-Complete, NP-Hard etc... only refer to decision problems, not to general purpose computations.

The decision problem for ECDLP

  { (Curve_spec, P, x) : x is a prefix of the discrete log of point P on the specified elliptic curve }

is trivially in NP.

I think you're mixing up quite a lot of things here. For one, apart from the impreciseness of your statement of the decision problem, it wouldn't be a decision problem for ECDLP but rather for the more general discrete logarithm problem (DLP). ECDLP is assumed to be in a higher complexity class than DLP.

With that said, even if the decision problem for ECDLP is in NP and P = NP, that does not mean that a solution to ECDLP is in P.

> ECDLP is assumed to be in a higher complexity class than DLP.

No, it's not. All instances of DLP, including ECDLP, are just asking for an x such that b^x = a, as Wikpedia will tell you [1]. They only differ in the choice of group, but exponentiation within the group is assumed to be an efficient operation.

> With that said, even if the decision problem for ECDLP is in NP, that does not mean that a solution to ECDLP is in P.

It trivially does. You simply start with an empty prefix x and extend it 1 bit at a time by repeatedly asking if (Curve_spec, P, x0) is in the language. If so you continue with x0, if not you continue with x1.

[1] https://en.wikipedia.org/wiki/Discrete_logarithm

A decision problem as used to define the classes NP and P is of the form: does there exist an x such that F(x) = 1, where F is a P-time computable function.

If you can solve that problem in P-time then you can also solve the functional version (find an x for which F(x) = 1) in P-time simply by setting each bit to a value for which the decision problem is satisfiable, one by one.

There is an upper bound in the number of private keys available even if it isn't an issue in practice.

You can target anyone's wallet in O(1) time, no proofs needed :^)

Reply on news.ycombinator.com