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. Transactions can also have arbitrary transaction fees, chosen by the users relaying those transactions. Transactions have different sizes (depending on the number of previous transactions they redeem and also the complexity of their input and output scripts). This leads to two optimization problems: Problem 1: Transaction sizes and fees (the knapsack problem) Miners’ goal in assembling a block is to choose a block of transactions with the greatest aggregate transaction fees. Each transaction also has an attached fee. They also must ensure the total block size is less than 1MB.
Tinkers knapsack free#
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. As it turns out, this requires solving two optimization problems, both of which are NP-hard!Īt any time, there is a set of outstanding transactions which have been relayed to the Bitcoin network but not yet included in any blocks. Before hashing anything miners first have to assemble a candidate block by choosing which transactions to include from the set of all pending transactions. 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. 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. 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.
0 kommentar(er)
