Bitcoin mining is NP-hard

This post is (mostly) a theoretical curiosity, but a discussion last week at CITP during our new course on Bitcoin led us to realize that being an optimal Bitcoin miner is in fact NP-hard. NP-hardness is a complexity classification used in computer science to describe many optimization problems for which we believe there is no algorithm which can always solve such problems efficiently. We’re not talking about the well-known hash puzzle portion of Bitcoin mining here in which miners race to find a block with an unusually low hash value-that’s hard by design. Before hashing anything miners first have to assemble a candidate block by choosing which transactions to include from the set of all pending transactions. As it turns out, this requires solving two optimization problems, both of which are NP-hard!

At any time, there is a set of outstanding transactions which have been relayed to the Bitcoin network but not yet included in any blocks. Miners are free to include any of these transactions they like, subject to the constraint that all included transactions are well-formed, only reference other transactions which have been published (possibly in the same block), and don’t conflict (double-spend) with any other published transaction. They also must ensure the total block size is less than 1MB. Each transaction also has an attached fee. Miners’ goal in assembling a block is to choose a block of transactions with the greatest aggregate transaction fees. This leads to two optimization problems:

Problem 1: Transaction sizes and fees (the knapsack problem)

Transactions have different sizes (depending on the number of previous transactions they redeem and also the complexity of their input and output scripts). Transactions can also have arbitrary transaction fees, chosen by the users relaying those transactions. Miners need to solve the problem of selecting the set of transactions with the greatest total transaction fee but still below the 1MB block limit. This is exactly equivalent to the classic knapsack problem in which you want to fill a knapsack of limited weight capacity with the most valuable subset of items from some set of possible items with varying weight and value. Building a Bitcoin block is just a knapsack problem with  “weight” being the size of each transaction, “value” being the transaction fee, and the total “capacity” as the 1 MB block limit.

The knapsack problem is well-studied. Finding the optimal solution is NP-hard and deciding if a solution exists above some fixed value threshold is NP-complete. These conclusions also apply to assembling a Bitcoin block as long as there are varying transaction sizes and fees, even without the extra complexity from the fact that some transactions conflict with others.

Problem 2: Transaction conflicts (the maximum independent-set problem)

Transactions also have dependencies and conflicts. We’ll take conflicts first, which come from the prohibition on double-spending. We’ll also make the problem considerably easier by ignoring the block size limit and assuming all transactions have a constant fee. If transactions B and B’ both claim funds from transaction A, then only one of B and B’ can be published and we say they conflict. If this is the only constraint, we can simply draw a graph of all transactions with edges between transactions which conflict. The miner’s task is to find the largest set of vertices (transactions) with no edge between then (no conflict). Solving this is exactly the maximum independent set problem. Once again, this means finding the optimal solution is NP-hard and deciding if a solution exists above a certain size (which would indicate the total transaction fee since we assumed fixed transaction fees) is NP-complete.

There are also dependencies, but we can roll these in to the conflicts graph which means they don’t make the problem any harder from a complexity perspective. Dependencies come from the fact that if transaction B redeems funds from transaction A, transaction A must be published if transaction B is. It is legal in Bitcoin for A and B to appear in the same block. It appears this requires adding a new type of (directed) edge to our graph with transaction conflicts. However, since we’re ignoring the total block size limit, we can remove the dependency edges and say that if we want to publish B which depends on A, we’ll just publish A as well. We’re also using the fact that transaction fees are strictly non-negative. We’ll need to add extra conflict edges though: If B depends on A, and A conflicts with A’, then B also conflicts with A’. So for each transaction, we need to add as conflicts the set of all conflicting transactions of all of its dependencies. This is a polynomial-time transformation and with the modified graph we can still find the largest conflict-free and dependency-satisfying set of transactions by solving the maximum independent set problem.

In this case we’ve ignored varying transaction sizes and fees completely, and the problem is NP-hard simply because of conflicts.

Not so much a problem in practice?

In practice, assembling optimum Bitcoin blocks requires solving both problems simultaneously. The two-headed beast is clearly NP-hard, since both sub-problems are. The decision version of the problem (is there a block above a certain transaction fee threshold) is also NP-complete, since it’s also NP-hard and it’s in NP because there’s clearly a polynomial time algorithm to verify correct solutions.

Does any of this matter in practice? Many problems are NP-hard in theory, but practical instance are typically easy to solve or approximate. It’s not clear if typical instances of “the Bitcoin block problem” are hard. Double-spends a relatively rare, as is publishing a transaction in the same block as its parent transaction, so the maximum independent set problem is probably easy in practice today. The knapsack problem may be non-trivial in practice. Typical Bitcoin blocks are assembled from a pool thousands or tens of thousands of possible transactions, of which the size and fees do vary considerably (here’s an example block).

The current default Bitcoin implementation makes no effort to solve or even really approximately this problem: transactions are simply sorted using a heuristic “priority” formula and then greedily added. It’s possible miners could profit slightly more by improving on this, but this formula has other benefits as it enforces minimum transaction fee amounts and it makes the process transparent for end users. Because almost all mining rewards still come from minting new coins rather than collecting fees, there’s not a great incentive to do better. This might change in the future with the planned transition towards mining fees in place of fixed block rewards. If it does, perhaps miners will want to learn a little bit about complexity theory and optimization problems.

There’s also the chance that if miners do start trying harder to solve the problem, they will be subject to denial-of-service by algorithmic complexity attacks, in which attackers deliberately broadcast blocks so as to make the problem very computationally challenging to solve.

In any case, this is yet another cool example of how Bitcoin manages to touch seemingly all areas of computer science. As we’ve said before, this makes Bitcoin a fantastic topic for any computer science curriculum to cover!

Thanks to Jeremy Clark for comments on a draft of this post.