10 ms·

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 findin

by tromp 4y ago

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.

jmercan 4y ago
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 :^)
hackcasual 4y ago
Only works if they have been moved. Addresses start out as hashes of ECC keys, not the keys themselves
- Strilanc 4y ago
  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".
  - tromp 4y ago
    Besides, Satoshi's coins are P2PK (Pay to Public Key), not P2PKH (Pay to Public Key Hash), so the point is moot.
pcwalton 4y ago
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.)
- tromp 4y ago
  > 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...
  - xorvoid 4y ago
    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.
  - bagels 4y ago
    That is not how the law works. It's equivalent to knowing your bank account number and routing number and making an unauthorized transaction.
  - remram 4y ago
    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.
Kranar 4y ago
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.
- tromp 4y ago
  Having an efficient algorithm for SAT (or any NP complete problem) immediately gives you an efficient algorithm for ALL problems in NP, including ECDLP.
  - Kranar 4y ago
    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.
    - tromp 4y ago
      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.
      - Kranar 4y ago
        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.

by tromp 4y ago

jmercan 4y ago

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 :^)

hackcasual 4y ago

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

Strilanc 4y ago
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".
- tromp 4y ago
  Besides, Satoshi's coins are P2PK (Pay to Public Key), not P2PKH (Pay to Public Key Hash), so the point is moot.

pcwalton 4y ago

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.)

tromp 4y ago
> 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...
- xorvoid 4y ago
  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.
- bagels 4y ago
  That is not how the law works. It's equivalent to knowing your bank account number and routing number and making an unauthorized transaction.
- remram 4y ago
  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.

Kranar 4y ago

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.

tromp 4y ago
Having an efficient algorithm for SAT (or any NP complete problem) immediately gives you an efficient algorithm for ALL problems in NP, including ECDLP.
- Kranar 4y ago
  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.
  - tromp 4y ago
    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.
    - Kranar 4y ago
      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.