3 ms·

If you could do it, you'd be famous for more than BTC. It would mean that you could factor numbers in polynomial time. Long story short, calculating the hash

If you could do it, you'd be famous for more than BTC. It would mean that you could factor numbers in polynomial time. Long story short, calculating the hash for BTC is intended to be a non-polynomial problem. If you can find a method (any method) that will reduce the search space of the answer such that you can calculate it in polynomial time, then you have proved that NP=P (If you can find a way to solve any non-polynomial-time-hard problem in polynomial time, then it means that all NP hard problems can be solved in P time). This would completely break all current encryption. Most people think that this is impossible, but it has not been proven yet. Unless you had some reason for believing the technique would work, it's probably not worth the effort to try.

schoen 7y ago
One minor correction to this (although I agree with you conceptually) is that there are no formal security proofs of the complexity class of hash function attacks for actually-existing hash functions. So there is no guarantee that the most efficient way to break a hash function security property is a generalizable attack on NP problems! It might just be that the specific hash function is weak in a previously unknown way. A sort-of precedent for that kind of problem which I mentioned in my sibling comment is the correlation weaknesses in RC4. While they're not the most powerful possible break of RC4, by any means, they are unanticipated flaws in the structure of RC4 specifically, and they might well have been discovered by software tools that can't solve NP problems in general. It seems to me that we don't have security proofs for symmetric cryptography at all, including for block cipher security properties as well as hash function security properties, and so while your observation is totally right in general, in any specific case it might just turn out that the cryptographic primitive we were using was weak in an unanticipated way that's specific to that class of functions. Compare https://en.wikipedia.org/wiki/Random_oracle https://en.wikipedia.org/wiki/Random_oracle (although reading that article reminds me of how much I don't understand about this topic)!
kragen 7y ago
In some ways you are correct, but you have made some errors. As schoen pointed out, no common hash function, including the ones used in Bitcoin, has a proof of NP-completeness. Moreover, none of those hash functions involve factoring numbers, and factoring numbers is also not known to be NP-complete, although it is also not known to be tractable in polynomial time. One reason commonly-used proof-of-work functions do not involve integer factorization is that, while integer factorization is not known to be doable in polynomial time, there are a number of algorithms that require subexponential time, so an integer-factorization-based proof-of-work witness would be much larger than an equivalent hash-function-based proof-of-work witness. Also, it is not the case that efficient integer factorization would completely break all current encryption. Not only do no commonly-used hash functions depend on it, neither do any commonly-used symmetric ciphers (such as AES), and the currently-most-popular asymmetric cryptosystems also do not depend on the difficulty of integer factorization; instead they depend on the difficulty of the elliptic-curve discrete logarithm problem. ECDLP is also not known to be NP-complete, but the currently-known algorithms for it are much worse than currently-known algorithms for integer factorization, so elliptic-curve cryptosystems require much smaller keys and less computation to resist the known attacks than integer-factorization-based cryptosystems. As little as ten years ago, algorithms that could be broken by better integer factorization algorithms were relatively much more important than they are today, because elliptic-curve cryptography was much less widely used. Many vulgar accounts of the situation intended for the ignorant are not up to date. Finally, it is not true that a proof that P=NP would "completely break all current encryption", for two reasons. First, it might not be a constructive proof — it might show that a polynomial-time algorithm for factoring integers, solving ECDLP, or computing hash preimages exists without actually telling you how to compute it. Second, even a constructive proof of P=NP might not provide an algorithm that was adequately efficient — if it takes O(n²) time to encrypt and decrypt, where n is the size of a key, but O(n⁸) time to break a message or a key, you might be adequately safe with, say, RSA-4096. But an O(n⁸) algorithm for 3-SAT would definitely be a constructive proof of P=NP. (Shor's algorithm on a quantum computer can break RSA, because it does depend on integer factorization, in O(n³) time, if quantum computers can exist, which they probably can. This would not make it impossible to do RSA encryption securely, but it would require much larger keys than are currently used.) However, your fundamental point is that a successful attack on Bitcoin's hashing algorithm, using artificial neural networks or anything else, would be very surprising and have major implications, because that proof-of-work scheme is designed to require exponential work, and as far as anyone knows, it does. And that fundamental point is correct, even though you have made a number of errors in your supporting points.

schoen 7y ago

One minor correction to this (although I agree with you conceptually) is that there are no formal security proofs of the complexity class of hash function attacks for actually-existing hash functions. So there is no guarantee that the most efficient way to break a hash function security property is a generalizable attack on NP problems! It might just be that the specific hash function is weak in a previously unknown way. A sort-of precedent for that kind of problem which I mentioned in my sibling comment is the correlation weaknesses in RC4. While they're not the most powerful possible break of RC4, by any means, they are unanticipated flaws in the structure of RC4 specifically, and they might well have been discovered by software tools that can't solve NP problems in general. It seems to me that we don't have security proofs for symmetric cryptography at all, including for block cipher security properties as well as hash function security properties, and so while your observation is totally right in general, in any specific case it might just turn out that the cryptographic primitive we were using was weak in an unanticipated way that's specific to that class of functions. Compare https://en.wikipedia.org/wiki/Random_oracle https://en.wikipedia.org/wiki/Random_oracle (although reading that article reminds me of how much I don't understand about this topic)!

kragen 7y ago

In some ways you are correct, but you have made some errors. As schoen pointed out, no common hash function, including the ones used in Bitcoin, has a proof of NP-completeness. Moreover, none of those hash functions involve factoring numbers, and factoring numbers is also not known to be NP-complete, although it is also not known to be tractable in polynomial time. One reason commonly-used proof-of-work functions do not involve integer factorization is that, while integer factorization is not known to be doable in polynomial time, there are a number of algorithms that require subexponential time, so an integer-factorization-based proof-of-work witness would be much larger than an equivalent hash-function-based proof-of-work witness. Also, it is not the case that efficient integer factorization would completely break all current encryption. Not only do no commonly-used hash functions depend on it, neither do any commonly-used symmetric ciphers (such as AES), and the currently-most-popular asymmetric cryptosystems also do not depend on the difficulty of integer factorization; instead they depend on the difficulty of the elliptic-curve discrete logarithm problem. ECDLP is also not known to be NP-complete, but the currently-known algorithms for it are much worse than currently-known algorithms for integer factorization, so elliptic-curve cryptosystems require much smaller keys and less computation to resist the known attacks than integer-factorization-based cryptosystems. As little as ten years ago, algorithms that could be broken by better integer factorization algorithms were relatively much more important than they are today, because elliptic-curve cryptography was much less widely used. Many vulgar accounts of the situation intended for the ignorant are not up to date. Finally, it is not true that a proof that P=NP would "completely break all current encryption", for two reasons. First, it might not be a constructive proof — it might show that a polynomial-time algorithm for factoring integers, solving ECDLP, or computing hash preimages exists without actually telling you how to compute it. Second, even a constructive proof of P=NP might not provide an algorithm that was adequately efficient — if it takes O(n²) time to encrypt and decrypt, where n is the size of a key, but O(n⁸) time to break a message or a key, you might be adequately safe with, say, RSA-4096. But an O(n⁸) algorithm for 3-SAT would definitely be a constructive proof of P=NP. (Shor's algorithm on a quantum computer can break RSA, because it does depend on integer factorization, in O(n³) time, if quantum computers can exist, which they probably can. This would not make it impossible to do RSA encryption securely, but it would require much larger keys than are currently used.) However, your fundamental point is that a successful attack on Bitcoin's hashing algorithm, using artificial neural networks or anything else, would be very surprising and have major implications, because that proof-of-work scheme is designed to require exponential work, and as far as anyone knows, it does. And that fundamental point is correct, even though you have made a number of errors in your supporting points.