5

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 ?

2

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)

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.

1

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.

  • I don't see how this is not Knapsack. How the uniqueness of txns change things? – SpiderRico Dec 5 '17 at 16:20
  • 1
    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 Dec 5 '17 at 16:27
  • I don't remember learning such assumption on Knapsack problem. Can you provide me a source? – SpiderRico Dec 5 '17 at 16:29
  • 1
    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. en.wikipedia.org/wiki/Knapsack_problem – Emil R Dec 5 '17 at 16:31
  • 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 Dec 6 '17 at 7:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.