2 Part II: Advanced

Problem 4. Each Bitcoin transaction, in its simplest form, has one input coin and several output coins (see Fig. 3). The input coin is genuine in the sense that it is spent by the transaction. This creates the issue of traceability for Bitcoin, that is, the entire history of each coin can be traced, e.g., how it was created, split, spent, and by which users, etc., which can sometimes be too revealing and undesirable for the users. To make the cryptocurrency untraceable, it has been proposed that instead of using only genuine inputs, the cryptocurrency wallet should also include other fake inputs so that an observer won’t know which input is the genuine one for that transaction. We will ignore the fact how this can be done technically and only focus on the mixing part where genuine and fake inputs are mixed in the transactions to provide untraceability. Assume that each coin can be used as a genuine input for exactly one transaction and that the number of coins is the same as the number of transactions in the system.

Figure 4: Examples of mixing genuine and fake inputs for transactions to provide untraceability. The mixing strategy in a) fails because an observer can determine a unique mapping M that matches genuine coins with transactions: M[1] = 2, M[2] = 3, M[3] = 4, and M[4] = 1. The mixing in b) is not the best in disguising the actual mapping, but still confuses an observer as there are two possibilities to match the coins with the transactions.

The mixing strategy sometimes fails because not all mixings are done in a proper way. For example, in Fig. 4 a), an observer can determine which coin is the genuine input of which transaction for ALL the coins. We refer to such a mixing as a bad mixing strategy.

Note that a mixing strategy can be described by a bipartite graph with the left-side vertices corresponding to the coins and the right-side vertices corresponding to the transactions, and there is an edge between a coin Ci and a transaction Tj if Ci is included in Tj as an input (genuine or fake). Design an algorithm of time complexity O(n+m), where n is the number of coins (or equivalently, the number of transactions) and m is the number of edges in the bipartite graph, that determines if a particular mixing is bad, i.e., a unique mapping M that maps ALL coins to their corresponding transactions could be found. The algorithm must output M if the mixing is bad.

a) Describe the algorithm in plain English together with a short pseudocode. The algorithm must be described in an unambiguous and concise way and provides enough details so that another student can understand how it works and why it solves the problem. The input of the algorithm is n, m, the (adjacency) lists of transactions Li (abbreviation for “Left”) that include the coin Ci as an input, i = 1,2,...,n, and the (adjacency) lists of coins Rj (abbreviation for “Right”) that are inputs of Transaction Tj , j = 1,2,...,n. The output of the algorithm is either the unique mapping M of coins and transactions or None, which indicates that an unique mapping can’t be found, i.e., there are more than one valid mappings.

c) Demonstrate your algorithm with an example, e.g., in Fig. 4 a).

d) Show that the complexity is indeed in O(n + m), which means that there are constants a and b such that the complexity is at most a×n+b×m, e.g. 3n+2m.