Bitcoin mining is NP-hard

https://freedom-to-tinker.com/blog/jbonneau/bitcoin-mining-is-np-hard/

by frrp • 12 years ago

57 15 12 years ago

patio11• 12 years ago

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.

0x0• 12 years ago

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?

lockes5hadow• 12 years ago

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.

neurobro• 12 years ago

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.

boxcardavin2• 12 years ago

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

Why is this good/important?

Jtsummers• 12 years ago

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.

boxcardavin2• 12 years ago

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.

cma• 12 years ago

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.

Strilanc• 12 years ago

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• 12 years ago

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

dllthomas2• 12 years 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• 12 years 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.

xanderjanz• 12 years ago

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

j2kun• 12 years ago

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

Bitcoin mining is NP-hard

Related Stories