<p>You are correct, it is infact equivalent to knapsack problem. To the best of my knowledge most miners simply sort by fee and this gives a good approximation for optimal solution.
A couple of things of things to highlight how difficult the transaction slection is:</p>

<p>1) Knapsack problem as you pointed out.</p>

<p>2) But even if the constraint in knapsack were removed(i.e infinite blocksize), still calculating optimal fees is NP hard problem. </p>

<blockquote>
  <p>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. <a href="https://freedom-to-tinker.com/2014/10/27/bitcoin-mining-is-np-hard/" rel="nofollow noreferrer">(Source)</a></p>
</blockquote>

<p>I presume the double-spend instances are rare and so are dependant transactions(child pays for parent known as CPFP). Therefore, my best guess is that simple greedy algorithm(taking CPFP into account) is close to optimal. Furthermore, there is also the tradeoff of time complexity which is very crutial for miners when we attempt alogrithms which are not simple.</p>

CC BY-SA 3.0
2017-12-06T10:34:02.077Z
2017-12-06T10:34:02.077Z
sanket1729
<p>The Knapsack problem assumes you have multiple items of value v and weight w. This is not the case with Bitcoin's mempool where each transaction is unique and the selection algorithm is simply ordering the items by fee/size and inserting them into the block till its full or close to.</p>

CC BY-SA 3.0
2017-12-05T16:20:32.253Z
I don't see how this is not Knapsack. How the uniqueness of txns change things?
SpiderRico
CC BY-SA 3.0
2017-12-05T16:27:35.670Z
The Knapsack problem assumes you have an unlimited number of items with the same v/w ratio. With Bitcoin this is not the case and the solution to maximize v is to order the list by v/w and do a greedy selection from the top. (This is default algorithm, some miners might have custom ones)
Emil R
CC BY-SA 3.0
2017-12-05T16:29:16.493Z
I don't remember learning such assumption on Knapsack problem. Can you provide me a source?
SpiderRico
CC BY-SA 3.0
2017-12-05T16:31:08.627Z
The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine **the number of each item** to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
https://en.wikipedia.org/wiki/Knapsack_problem
Emil R
CC BY-SA 3.0
2017-12-06T07:12:30.197Z
This is wrong. It is possible to construct 2 blocks where fee/size is not the best algorithm. I still think it is not possible to opitmal block in linear time. The greedy algorithm is just a good approximation
sanket1729
CC BY-SA 3.0
2017-12-05T16:18:08.297Z
2017-12-05T16:18:08.297Z
Emil R
<p>Each tx has an associated fee and size. Moreover, we have a size limit on blocks. Finding txs that maximize the profit under this restriction is basically the Knapsack problem.</p>

<p>So, do default client miners really employ Knapsack algorithm when they do their selection ? </p>

<transactions><mining-theory>
What's the default strategy miners employ when they select txs from their pool?
SpiderRico
# What's the default strategy miners employ when they select txs from their pool?

(Asked by: username_0 on 2017-12-05)

Each tx has an associated fee and size. Moreover, we have a size limit on blocks. Finding txs that maximize the profit under this restriction is basically the Knapsack problem.

So, do default client miners really employ Knapsack algorithm when they do their selection ?

**Tags:** transactions, mining-theory


---

## 2 answers

### Answer by username_1 on 2017-12-06. Score: 2 | Accepted answer

You are correct, it is infact equivalent to knapsack problem. To the best of my knowledge most miners simply sort by fee and this gives a good approximation for optimal solution.
A couple of things of things to highlight how difficult the transaction slection is:

1) Knapsack problem as you pointed out.

2) But even if the constraint in knapsack were removed(i.e infinite blocksize), still calculating optimal fees is NP hard 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. [(Source)](https://freedom-to-tinker.com/2014/10/27/bitcoin-mining-is-np-hard/)

I presume the double-spend instances are rare and so are dependant transactions(child pays for parent known as CPFP). Therefore, my best guess is that simple greedy algorithm(taking CPFP into account) is close to optimal. Furthermore, there is also the tradeoff of time complexity which is very crutial for miners when we attempt alogrithms which are not simple.


---

### Answer by username_2 on 2017-12-05. Score: 0

The Knapsack problem assumes you have multiple items of value v and weight w. This is not the case with Bitcoin's mempool where each transaction is unique and the selection algorithm is simply ordering the items by fee/size and inserting them into the block till its full or close to.

> **Comments:**
> **username_0**: I don't see how this is not Knapsack. How the uniqueness of txns change things?  
> **username_2**: The Knapsack problem assumes you have an unlimited number of items with the same v/w ratio. With Bitcoin this is not the case and the solution to maximize v is to order the list by v/w and do a greedy selection from the top. (This is default algorithm, some miners might have custom ones)  
> **username_0**: I don't remember learning such assumption on Knapsack problem. Can you provide me a source?  
> **username_2**: The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine **the number of each item** to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. https://en.wikipedia.org/wiki/Knapsack_problem  
> **username_1**: This is wrong. It is possible to construct 2 blocks where fee/size is not the best algorithm. I still think it is not possible to opitmal block in linear time. The greedy algorithm is just a good approximation  

---

