Bitcoin mining is NP-hard | Hacker News Reader

Bitcoin mining is NP-hard

freedom-to-tinker.com

57 pointsfrrp15 comments

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.

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

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.

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.

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

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

Optimal blocks aren't really a priority for miners because the fact that you win the race is worth, ballpark, 250X (the coinbase transaction's segniorage award of 25 BTC) what the transaction fees for the transactions included in the block is. Optimizing for a few percent extra transaction fees doesn't meaningfully change the economics, and if it slows you appreciably, could potentially cost you that segniorage if someone else beats you to the punch.

Accoringly most miners appear to just use really cheap heuristics.

Aren't block awards supposed to reach 0 after a while, so that tx fees become the only incentive for mining? In those cases optimizing may be well worth the effort?

Hopefully by that point the block size will be bigger. If the block size is bigger, than the problem is just "include every transaction". But yes, the bitcoin rewards will continue halving until sometime in 2110-2140, where they hit zero. At some point, transaction fees will be more important than the block reward. Therefore, to be efficient miners would need to solve the knapsack problem if they wanted to create a maximum value block. However, we are lucky here, the knapsack problems is one of the few NP-complete problems that isn't a total mess to deal with, and can be solved in O(nW) time, where W is the greatest common divisor for the weights and n is the length of the input.

If blocks were closer to optimal, it should have the effect of raising transaction fees to ensure timely confirmation, which would improve the reward ratio somewhat. Maybe it still wouldn't be significant.

"but this formula has other benefits as it enforces minimum transaction fee amounts"

Why is this good/important?

It would reduce friction in the bitcoin economy. Consider, in a more conventional economy, a significant tax levied by the government. This tax either reduces the profits for the seller or increases the cost for the buyer or both.

1. The seller can optionally soak the cost of the transaction fee. But this means less profit for them while the buyer sees no changes (until later when the seller finds this is unsustainable as fees increase).

2. The seller can raise prices by the fee amount (how sales tax works in the US, effectively). The buyer is then paying more and more over time as fee amounts increase.

3. Some combination, seller determines the amount they can afford to lose while keeping prices low enough to not lose too many customers.

In the end, all 3 options will create a drag on the economy. Either by reduced buying power or reduced profits resulting in reduced future growth.

We also see this with credit/debit card transaction processing. Sellers, per their agreements with CC companies, aren't supposed to have different prices between CC and cash transactions. This means they lose part of their profits on CC transactions, with some companies (AMEX) costing them more than others.

Maybe I misunderstood, does "minimum" in this case mean that fees must be "at least ฿X"? So wouldn't a fee minimum enforce a higher drag on the BC economy?

I will also google this question down later.

Those kind of credit card agreements were outlawed under an Obama consumer-protection law. You can now offer a discount for people who pay in cash, though I believe the agreements can still require it be advertised as a discount for cash, not as a fee for credit card usage, even if they are effectively the same.

Unfortunately, the problems he reduces from are not so hard in practice. Knapsack has what's called an FPTAS, which means you can get as good an approximation as you want, and the runtime only scales polynomially with your desired accuracy. And independent set has nice approximation algorithms for bounded degree graphs and other restricted graph classes (though there is no general constant-factor approximation unless P = NP).

So it's funny that the author quotes knapsack as the possible true difficulty...

Reply on news.ycombinator.com