Problem 4 (7 marks, 2 pages). Each Bitcoin transaction, in its simplest form, has one input coin and several output coin

[answerhappygod]

Problem 4 7 Marks 2 Pages Each Bitcoin Transaction In Its Simplest Form Has One Input Coin And Several Output Coin 1 (88.41 KiB) Viewed 53 times

Problem 4 (7 marks, 2 pages). 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. Transaction i 10 BTC 1 BTC In Out 9 BTC Out Figure 3: Example of input and output coins in a Bitcoin transaction. C T T: C2 T2 C2 T2 T3 C T3 C4 T4 T4 b) 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 confusce an observer as there are two possibilitics to match the coins with the transactions. Tho mixing strategy sometimes fails because not all mixings are done in a propor way.

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. 6 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 trans- actions, and there is an edge between a coin C; and a transaction T; if C; is included in T; 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 num- ber 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) [3 marks] Describe the algorithm in plain English together with a short pseu- docode. 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 L; (abbreviation for "Left") that include the coin C as an in- put, i = 1,2,...,n, and the adjacency) lists of coins R; (abbreviation for "Right") that are inputs of Transaction Tj, j = 1,2,...,n. The output of the algorithm is ei- ther 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) [2 marks] Demonstrate your algorithm with an example, e.g., in Fig. 4 a).