3 ms·

Misleading title. The article talks about how choosing the optimal set of transactions to include in a block is NP-Hard, and the typical implementation uses a

Misleading title. The article talks about how choosing the optimal set of transactions to include in a block is NP-Hard, and the typical implementation uses a simple greedy approximation. But I thought I was going to read about someone doing a security proof showing that a fast way to generate blocks and extend the chain would give us a polynomial algorithm for 3-SAT. Which would have been awesome.

exacube 12y ago
haha, in which case the article title could've been "P=NP!"
dllthomas 12y ago
Finding the hash for a block is NP-complete, I believe [edited to add: I should note that this is more speculative than my wording may have implied; the rest holds]. We don't have, algorithmically, "a fast way to generate blocks" - we do it through brute force, and size the problem such that collectively someone can solve with reasonable frequency.
- nhaehnle 12y ago
  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.
xanderjanz 12y ago
Isn't it impossible to prove if something is NP-hard, since we don't know if p=np

exacube 12y ago

haha, in which case the article title could've been "P=NP!"

dllthomas 12y ago

Finding the hash for a block is NP-complete, I believe [edited to add: I should note that this is more speculative than my wording may have implied; the rest holds]. We don't have, algorithmically, "a fast way to generate blocks" - we do it through brute force, and size the problem such that collectively someone can solve with reasonable frequency.

nhaehnle 12y ago
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.

xanderjanz 12y ago

Isn't it impossible to prove if something is NP-hard, since we don't know if p=np