4 ms·

Actually, no. Proving that finding the has is NP-complete would require a proof that any boolean formula (the SAT problem) can be translated into a Bitcoin bloc

Actually, no. Proving that finding the has is NP-complete would require a proof that any boolean formula (the SAT problem) can be translated into a Bitcoin block such that a nonce yielding a small hash (which is what Bitcoin asks for) would somehow encode a solution to the SAT problem. Nothing like this has been proved (neither directly nor indirectly), and it seems very unlikely to happen in the foreseeable future. In fact, none of the commonly used cryptographic primitives have NP-hardness proofs.

dllthomas 12y ago
"X is NP-Complete" is a different statement than "X is proved to be NP-Complete". I said "I believe" the former. Bitcoin mining is clearly in NP - you can check blocks in polynomial time. The only real question is whether it is also NP-Hard. Contrary to your implication, there is nothing about the shape of the problem that implies other NP problems couldn't be reduced to it - indeed, we can express any NP problem as a pile of bits that, fed to an appropriate algorithm, generates a single 1 bit; that is the nature of a decision problem. I fully recognize that the NP-Hard-ness of SHA256 is speculative, and I run a not-insignificant risk of being wrong. The strongest case for my correctness, so far, is that no one has found a polynomial attack against any of the SHA functions - this is far from conclusive, of course.