Part II: Advanced

Figure 1: A toy example of twelve transactions with their corresponding sizes (red) and fees (green). For example, t3 has size s3 = 1 and fee f3 = 2. The dependency among transactions is represented by arrows: tj → ti means that tj depends on ti . For instance, t7 depends on t3, which in turn depends on t1. The block size limit is b = 18.

Problem 4. Profit maximisation in block mining - version 2∗ .

After executing your algorithms that select a set I of transactions from a pool of n unconfirmed transactions (waiting to be included in a block) that has total size P i∈I si ≤ b, where b is the block size limit, while achieving maximum total fee P i∈I fi , you discovered a problem with this formulation. It dawned on you that the transactions are NOT independent of each other. For instance, if Alice pays 1 bitcoin to Bob in Transaction ti , who in turn uses this coin to pay Carl in Transaction tj , then tj will depend on ti . More specifically, in Bitcoin, tj depends on ti if an output of ti is used as an input of tj (Figure 2). Hence, to include tj in the current block, ti must be either already included in an existing block or in the same block as tj . This is the Dependency Rule. Note that ti in its turn may depend on other transactions, which also need to be included, and so on. 

Figure 2: Dependency among Bitcoin transactions. Transaction j uses one output of Transaction i as its input. In such a case, Transaction j depends on Transaction i.

Suppose that you have run a preprocessing algorithm that returns the dependency list Lj that comprises of all i where tj depends on ti , for each 1 ≤ j ≤ n. For instance, in the toy example in Figure 1, L10 = {6,8} and L11 = {2,7}.

a) Design an efficient algorithm (worst-case complexity O(n 2 )) that takes as input the number of transactions n, the sizes si and fees fi , the dependency lists Li , i = 1,...,n, and an index set J ⊆ {1,2,...,n}, and returns the list TJ (J ⊆ TJ) of ALL the transactions (indices) that must be included if the transactions {tj : j ∈ J} are to be included in a block, so that the Dependency Rule is respected. For example, when J = {4,7}, we have TJ = {1,2,3,4,7}. Note that TJ must contain J as a subset. The solution must include:

– algorithm description,

– short pseudocode, and

– complexity analysis, and

–  the list of transactions TJ output by the algorithm applied to the toy example in Figure 1 with J = {5,10,11} and the corresponding total size & fee.

b) Based on Part a), design an exhaustive search (algorithm) that returns a set of transactions (indices) J ∗ to form a block that respects the Dependency Rule and has total size at most b while maximising the total transaction fee. Input to the algorithm: n, b, si , fi , Li , i = 1,...,n. The solution must include:

– algorithm description, and

– the set of transactions (indices) J ∗ output by the exhaustive search, its total size and its (maximum) total profit for the toy example in Figure 1.